A regra dos 37%

Os candidatos chegam um a um, por ordem aleatória. Pode comparar cada um com os anteriores, mas tem de decidir logo se o aceita ou rejeita. Não pode voltar atrás. Escolha quantos rejeitar à partida; a regra escolhe depois o primeiro candidato que superar todos os rejeitados.

Probabilidade de escolher o melhor, rejeitando k	$P(k)=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Melhor ponto de corte, n grande	$k^*\approx\frac{n}{e}$
Probabilidade correspondente	$P(k^*)\to\frac{1}{e}\approx0.3679$

Exemplo resolvido — A regra dos 37%

Probabilidade de escolher o melhor, rejeitando 4	39,84%
Melhor ponto de corte k*	4
Probabilidade de escolher o melhor com k*	39,84%
n/e, para comparação	4,05
Probabilidade de escolher o melhor ao acaso	9,09%
Probabilidade de chegar ao último candidato	40%
Menor classificação esperada possível	2,6136

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — A regra dos 37%

No problema da secretária, n candidatos chegam por ordem aleatória. Cada candidato só pode ser comparado com os anteriores e tem de ser aceite ou rejeitado no momento, sem possibilidade de rever a decisão. A regra de corte rejeita os primeiros k e aceita depois o primeiro candidato que os superar a todos.

De onde vem a fórmula

Separe os casos pela posição do melhor. Seja B a posição do melhor candidato e W o acontecimento de o escolher. Todas as posições de 1 a n são igualmente prováveis para B.
$P(B=i)=\frac{1}{n},\qquad i=1,\dots,n$
Se o melhor estiver entre os primeiros k, perde-se. A regra não permite voltar atrás, por isso essas posições não contribuem para a probabilidade de sucesso.
$B\le k:\quad P(W\mid B)=0$
O melhor, na posição i > k, só chega a ser escolhido se nenhum candidato entre k + 1 e i − 1 tiver sido aceite. Isso acontece precisamente quando o melhor dos primeiros i − 1 está entre os primeiros k: só assim nenhum dos candidatos intermédios supera a referência. Qualquer um dos i − 1 tem a mesma probabilidade de ser o melhor desse grupo.
$B=i>k:\quad P(W\mid B=i)=\frac{k}{i-1}$
Some as contribuições de todas as posições.
$P(k)=\sum_{i=k+1}^{n}\frac{1}{n}\cdot\frac{k}{i-1}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Faça n crescer. Com x = k/n, a soma dá lugar a um integral e a probabilidade tende para −x ln x. A derivada, −ln x − 1, anula-se em x = 1/e, onde a probabilidade é 1/e ≈ 36,79%.
$P\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x,\qquad\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\iff x=\frac{1}{e}$

Pressupõe: Conhece-se apenas a classificação relativa, nunca as pontuações; todas as ordens são igualmente prováveis; não se pode recuperar um candidato rejeitado e o candidato escolhido aceita sempre; qualquer escolha que não seja o melhor candidato conta como uma derrota.

Problemas resolvidos na íntegra

Três candidatos, todas as ordens possíveis 3 passos
Três candidatos chegam por ordem aleatória. Represente cada ordem pelas classificações dos candidatos à chegada (1 = melhor). Se rejeitar o primeiro e escolher depois o primeiro que superar todos os anteriores, em quantas das seis ordens escolhe o melhor? Confirme o resultado com a fórmula.

Abrir este problema na ferramenta
1. As seis ordens:
  
  $123,\quad 132,\quad 213,\quad 231,\quad 312,\quad 321$
2. O primeiro candidato estabelece a referência. Nas ordens 213 e 231, o melhor supera o 2; em 312, o 1 chega em segundo lugar e é escolhido. Em 123 e 132, ninguém supera o 1 rejeitado, pelo que se escolhe o último. Em 321, o 2 supera o 3 e é escolhido antes de chegar o 1:
  
  $213\to1,\quad 231\to1,\quad 312\to1;\qquad 123\to3,\quad 132\to2,\quad 321\to2$
3. Pela fórmula, com n = 3 e k = 1:
  
  $P(1)=\frac{1}{3}\left(\frac{1}{1}+\frac{1}{2}\right)=\frac{1}{3}\cdot\frac{3}{2}=\frac{1}{2}$
Resposta

3 das 6 ordens, ou seja, uma probabilidade de 1/2, contra 1/3 se escolher o primeiro candidato.

$P(1)=\frac{3}{6}=\frac{1}{2}>\frac{1}{3}=P(0)$
Quatro candidatos, todos os pontos de corte 2 passos
Com quatro candidatos, calcule a probabilidade de escolher o melhor para cada ponto de corte k = 0, 1, 2, 3 e determine o melhor ponto de corte.

Abrir este problema na ferramenta
Mostrar solução
1. Com k = 0, escolhe-se o primeiro candidato, que é o melhor com probabilidade 1/4. Para k ≥ 1, use a fórmula:
  
  $P(1)=\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{3}\right)=\frac{11}{24},\quad P(2)=\frac{2}{4}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12},\quad P(3)=\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{4}$
2. Compare os quatro resultados:
  
  $P(0)=\frac{6}{24},\quad P(1)=\frac{11}{24},\quad P(2)=\frac{10}{24},\quad P(3)=\frac{6}{24}$
Resposta

Rejeite o primeiro e escolha depois o primeiro que o superar: 11/24 ≈ 45,83%.

$k^*=1,\qquad P(1)=\frac{11}{24}\approx0.4583$
As onze candidatas de Kepler 3 passos
Em 1611, Johannes Kepler começou a procurar uma segunda esposa e, ao longo de quase dois anos, considerou onze candidatas. Aplicando a regra de corte com n = 11, qual é o melhor ponto de corte, que probabilidade oferece e qual é a primeira candidata que a regra pode escolher?

Abrir este problema na ferramenta
Mostrar solução
1. Calcule a fórmula para valores próximos de n/e = 11/e ≈ 4,05:
  
  $P(4)=\frac{4}{11}\left(\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{10}\right)=\frac{4}{11}\times1.0956=0.3984$
2. A probabilidade é máxima em k = 4; tanto k = 3 como k = 5 dão valores inferiores:
  
  $P(3)=\frac{3}{11}\left(\frac{1}{3}+\dots+\frac{1}{10}\right)=0.3897,\qquad P(5)=\frac{5}{11}\left(\frac{1}{5}+\dots+\frac{1}{10}\right)=0.3844$
3. Rejeitadas as primeiras quatro, a quinta é a primeira candidata que a regra pode aceitar. Kepler casou de facto com a quinta, mas não seguiu esta regra. Segundo o relato que Ferguson faz da sua carta, depois de conhecer a quinta, Kepler foi convencido a pedir a quarta em casamento. Ela recusou, e ele voltou à quinta. A regra não permite voltar atrás.
Resposta

Rejeite as primeiras 4: a probabilidade é 39,84%. A quinta é a primeira candidata que a regra pode escolher.

$k^*=4,\qquad P(4)\approx0.3984$
Muitos candidatos: de onde vem 1/e 3 passos
Para n grande, escreva a proporção rejeitada como x = k/n e determine o melhor valor de x e a probabilidade correspondente. Compare depois com n = 100.

Abrir este problema na ferramenta
Mostrar solução
1. A soma é uma soma de Riemann da função 1/t no intervalo [x, 1]:
  
  $\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}=x\sum_{j=k}^{n-1}\frac{1}{n}\cdot\frac{1}{j/n}\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x$
2. Iguale a derivada a zero:
  
  $\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\ \Rightarrow\ x=\frac{1}{e},\qquad -\frac{1}{e}\ln\frac{1}{e}=\frac{1}{e}\approx0.3679$
3. Para n = 100, tem-se n/e ≈ 36,79, e o melhor ponto de corte exato é 37:
  
  $P(36)=0.37101,\qquad P(37)=0.37104,\qquad P(38)=0.37080$
Resposta

Rejeite uma proporção 1/e ≈ 36,79%; a probabilidade tende para 1/e. Para n = 100, o melhor ponto de corte é 37, com probabilidade 37,1%.

$x^*=\frac{1}{e},\qquad P\to\frac{1}{e}\approx0.3679;\qquad n=100:\ k^*=37,\ P(37)\approx0.3710$
Ficar com o último candidato 3 passos
Há 100 candidatos e rejeitam-se os primeiros 37. Calcule a probabilidade de o melhor estar entre os rejeitados, a de a seleção chegar ao último candidato e a de chegar ao último candidato e este ser o melhor.

Abrir este problema na ferramenta
Mostrar solução
1. O melhor tem a mesma probabilidade de ocupar qualquer posição, pelo que está entre os primeiros 37 com probabilidade:
  
  $\frac{k}{n}=\frac{37}{100}=0.37$
2. A seleção chega ao candidato 100 precisamente quando nenhum dos candidatos de 38 a 99 é escolhido, ou seja, quando o melhor dos primeiros 99 está entre os primeiros 37:
  
  $\frac{k}{n-1}=\frac{37}{99}\approx0.3737$
3. A diferença corresponde ao caso em que a seleção chega ao fim e o último candidato é o melhor:
  
  $\frac{37}{99}-\frac{37}{100}=\frac{37}{9900}\approx0.0037$
Resposta

37%, 37,37% e 0,37%: mais de uma seleção em cada três termina no último candidato, quase nunca por ele ser o melhor.

$0.37,\qquad 0.3737,\qquad 0.0037$
Três candidatos e a menor classificação esperada 3 passos
Com três candidatos, o objetivo passa a ser a menor classificação esperada (1 = melhor). Determine a regra ótima por indução retrospetiva e calcule a sua classificação esperada.

Abrir este problema na ferramenta
Mostrar solução
1. Um candidato que chega na posição i e ocupa o lugar j entre os já observados tem classificação global esperada j(n + 1)/(i + 1). O terceiro candidato tem de ser escolhido e a sua classificação esperada é (n + 1)/2:
  
  $\frac{j(n+1)}{i+1}=\frac{4j}{i+1},\qquad c_2=\frac{3+1}{2}=2$
2. Ao chegar o segundo candidato, escolha-o se a sua classificação esperada for menor ou igual a 2; caso contrário, continue:
  
  $i=2:\ \ j=1:\ \tfrac{4}{3}<2,\quad j=2:\ \tfrac{8}{3}>2;\qquad c_1=\frac{1}{2}\left(\frac{4}{3}+2\right)=\frac{5}{3}$
3. Escolher o primeiro dá uma classificação esperada de 2, superior a 5/3, pelo que se deve continuar:
  
  $i=1:\ \ \frac{4}{2}=2>\frac{5}{3}\ \Rightarrow\ c_0=c_1=\frac{5}{3}$
Resposta

Rejeite o primeiro, escolha o segundo se superar o primeiro e, caso contrário, escolha o terceiro: a classificação esperada é 5/3 ≈ 1,67. Com três candidatos, esta é precisamente a regra de corte com k = 1.

$c_0=\frac{5}{3}\approx1.6667$
Dois candidatos com pontuações conhecidas 2 passos
Dois candidatos têm pontuações independentes, com distribuição uniforme entre 0 e 1. Conhece a pontuação de cada um quando chega. Determine a regra que escolhe mais vezes a pontuação mais alta e calcule a sua probabilidade de sucesso. Compare com o caso em que só se conhece a classificação relativa.

Abrir este problema na ferramenta
Mostrar solução
1. Se rejeitar o primeiro, cuja pontuação é x, terá de escolher o segundo. Ganha quando a pontuação do segundo é superior: probabilidade 1 − x. Se escolher o primeiro, ganha quando a pontuação do segundo é inferior: probabilidade x.
  
  $S(x)=x,\qquad C(x)=1-x;\qquad S(x)\ge C(x)\iff x\ge\tfrac{1}{2}$
2. Deve, portanto, escolher o primeiro quando x ≥ 1/2. Calcule a média em relação a x:
  
  $\int_{0}^{1/2}(1-x)\,dx+\int_{1/2}^{1}x\,dx=\frac{3}{8}+\frac{3}{8}=\frac{3}{4}$
Resposta

Escolha o primeiro se a sua pontuação for pelo menos 1/2: a probabilidade de sucesso é 3/4. Conhecendo apenas a classificação relativa, com dois candidatos a probabilidade é 1/2, qualquer que seja a decisão.

$P=\frac{3}{4}>\frac{1}{2}$

Problemas suplementares, só com a resposta

Com cinco candidatos, determine o melhor ponto de corte e a respetiva probabilidade.

Mostrar resposta

Rejeitar os primeiros 2: 13/30 ≈ 43,33%.

$k^*=2,\qquad P(2)=\frac{2}{5}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{13}{30}\approx0.4333$
Com dois candidatos e conhecendo apenas a classificação relativa, mostre que qualquer regra escolhe o melhor em metade dos casos.

Mostrar resposta

Escolher o primeiro dá uma probabilidade de sucesso de 1/2; rejeitá-lo obriga a escolher o segundo, também com probabilidade 1/2.

$P(0)=\frac{1}{2},\qquad P(1)=\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{2}$
Com dez candidatos e o melhor ponto de corte, calcule a probabilidade de o melhor estar entre os rejeitados e a de a seleção chegar ao último candidato.

Mostrar resposta

k = 3: 30% e 3/9 ≈ 33,33%.

$k^*=3:\quad\frac{3}{10}=0.3,\qquad\frac{3}{9}\approx0.3333$
No limite para n grande, calcule a probabilidade de escolher o melhor quando se rejeita um quinto dos candidatos e quando se rejeitam três quintos.

Mostrar resposta

−0,2 ln 0,2 ≈ 32,19% e −0,6 ln 0,6 ≈ 30,65%.

$-0.2\ln0.2\approx0.3219,\qquad-0.6\ln0.6\approx0.3065$
Com quatro candidatos, determine a menor classificação esperada que uma regra pode atingir.

Mostrar resposta

15/8 = 1,875.

$c_0=\frac{15}{8}=1.875$

Rejeitar um quarto ou metade dá a mesma probabilidade

A curva é quase plana no topo, o que torna a regra fácil de aplicar. Selecione Rejeitar um quarto: 35,04%. Selecione Rejeitar metade: 34,91%. Para 100 candidatos, o melhor ponto de corte, 37, dá 37,1%. Rejeitar entre um quarto e metade custa, portanto, no máximo 2,2 pontos percentuais. À medida que n cresce, a curva aproxima-se de −x ln x, onde x é a proporção rejeitada. Para um quarto e metade, esta função tem exatamente o mesmo valor, pois ¼ ln 4 = ½ ln 2 ≈ 34,66%. Não precisa, por isso, de conhecer n com grande precisão: mesmo que o estime um terço acima ou um terço abaixo do valor real e rejeite 37% dessa estimativa, para n grande mantém uma probabilidade de pelo menos 34,5%.

Procurar apenas o melhor leva ao último em mais de um terço dos casos

A regra aposta tudo no melhor candidato. Se ele estiver entre os rejeitados, o que acontece em 37% dos casos com 100 candidatos, nenhum dos seguintes consegue superar a referência. A seleção prossegue até ao fim e escolhe quem chegar em último. Selecione Cem, 37 rejeitados: a classificação esperada do candidato escolhido é 20,01. Em 1964, Chow, Moriguti, Robbins e Samuels procuraram uma regra que minimizasse a classificação esperada. Essa regra aceita um candidato que esteja apenas perto do topo entre os já observados, tornando-se menos exigente à medida que restam menos candidatos. Para n = 100, a classificação esperada é 3,60. Mantém-se abaixo de 4 para todos os valores de n disponíveis nesta página e tende para 3,8695. Com a regra dos 37%, a classificação esperada continua a crescer com n e chega a 185,54 para 1 000 candidatos.

Conhecer as pontuações faz a probabilidade subir para 58%

A regra dos 37% usa apenas a classificação relativa: quem supera quem. Suponha agora que conhece a pontuação de cada candidato e a distribuição das pontuações, por exemplo, uniforme entre 0 e 1. Gilbert e Mosteller resolveram esta versão em 1966. Aqui, deixa de haver uma fase inicial de observação sem escolha. Desde o primeiro candidato, escolhe quem for o melhor até ao momento e tiver uma pontuação acima de um limiar. Esse limiar desce à medida que restam menos candidatos: 0,5 quando ainda falta 1, 0,6899 quando faltam 2 e 0,9240 quando faltam 10. A probabilidade de escolher o melhor é 60,6% com 11 candidatos e 58,29% com 100, tendendo para 58,02%, contra 36,79% quando só se conhece a classificação relativa. Saber reconhecer uma boa pontuação vale cerca de 21 pontos percentuais.

Percurso de aprendizagem

Escolher com base no que se vê

Referências (4)

The problem as now studied (n known, random order, relative ranks only, no recall, only the best counts), the cutoff rule and its chance, and the history the page uses: Kepler, after losing his first wife in 1611, spent nearly two years over at least eleven candidates, described in a letter to Baron Strahlendorf of 23 October 1613; friends persuaded him to propose to the fourth after he met the fifth, the fourth turned him down, and he chose the fifth. Ferguson notes that for n = 11 the rule's chance is largest when the fifth is the first candidate it may take, and that Kepler's recall breaks the problem's assumptions: T. S. Ferguson, Who solved the secretary problem? Statistical Science 4(3), 282–289 (1989). doi:10.1214/ss/1177012493
The classical secretary problem solved by backward induction, the limits the page quotes in insight blocks 2 and 3: the least expected rank tends to 3.8695 (Chow, Moriguti, Robbins and Samuels), and with the values revealed and their distribution known the chance of the best tends to 0.58016 (Gilbert and Mosteller), 'to be compared to the limiting value e⁻¹ when the intrinsic values are not revealed': T. S. Ferguson, Optimal Stopping and Applications, Chapter 2, Finite Horizon Problems, §§2.1–2.3. Mathematics Department, UCLA (online text).
The rank-minimising rule of insight block 2 and solved problem 6: accept a candidate whose relative rank is within a threshold that rises as the candidates run out, with expected rank tending to 3.8695: Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal selection based on relative rank (the "secretary problem"). Israel Journal of Mathematics 2(2), 81–90 (1964). doi:10.1007/BF02759948
The full-information problem of insight block 3 and solved problem 7: values seen, independent with a known distribution; the optimal rule takes a best-so-far above a threshold that depends on how many remain, and the chance of the best tends to 0.5802: J. P. Gilbert and F. Mosteller, Recognizing the maximum of a sequence. Journal of the American Statistical Association 61(313), 35–73 (1966). doi:10.1080/01621459.1966.10502008

Pela equipa 7 Raven Room · Verificado com fontes publicadas. Correções bem-vindas.

A regra dos 37%

De onde vem a fórmula

Problemas suplementares, só com a resposta

Rejeitar um quarto ou metade dá a mesma probabilidade 🖖

Procurar apenas o melhor leva ao último em mais de um terço dos casos 🖖

Conhecer as pontuações faz a probabilidade subir para 58% 🖖

Rejeitar um quarto ou metade dá a mesma probabilidade

Procurar apenas o melhor leva ao último em mais de um terço dos casos

Conhecer as pontuações faz a probabilidade subir para 58%