Explorador do Paradoxo do Aniversário

Quantas pessoas têm de estar numa sala para que um aniversário partilhado seja mais provável do que não? Deduza o resultado e explique por que razão 23 parece um valor demasiado pequeno.

1. Calcule o oposto. “Pelo menos um partilhado” é complicado porque a coincidência pode ocorrer de muitas formas ao mesmo tempo; “todos diferentes” é uma única sequência límpida de escolhas.

   $$P(\text{all different})=\prod_{k=0}^{n-1}\frac{365-k}{365}$$

2. Cada nova pessoa deve evitar todos os aniversários já ocupados, pelo que os dias disponíveis diminuem um de cada vez. Multiplique as frações.

   $$n=23:\quad \frac{365}{365}\cdot\frac{364}{365}\cdots\frac{343}{365}=0.4927$$

3. Subtraia de um. O explorador acima exibe exatamente isto, e 23 é o primeiro n para o qual o resultado ultrapassa metade.

   $$P(\text{shared})=1-0.4927=0.5073=50.7\%$$

4. Não está apenas a comparar-se com outras 22 pessoas: todos os pares contam, e o seu número cresce com o quadrado do número de elementos do grupo.

   $$\binom{n}{2}=\frac{23\times22}{2}=253\ \text{pairs}$$

5. Esse crescimento ao quadrado é visível na aproximação: a probabilidade depende de n² sobre 730, pelo que o ponto de transição varia como uma raiz quadrada, e não como uma fração de 365.

   $$P\approx1-e^{-n^2/730}:\quad n=\sqrt{730\ln 2}=22.5$$

Vinte e três pessoas, 50,7 %. O número de que toda a gente se lembra é 23, e é a parte menos útil do resultado: pertence a um ano de 365 dias e a mais nada. Encontre a regra por baixo, a que continua a valer quando o calendário é uma função de dispersão.

1. A resposta exata é um produto: a segunda pessoa falha a primeira, a terceira falha as duas, e assim por diante pela sala fora. É esse produto que o painel avalia.

   $$Q(n)=\prod_{k=0}^{n-1}\frac{365-k}{365},\qquad P=1-Q(23)=0.507$$

2. Sobre produtos raciocina-se mal, portanto tome logaritmos — e enquanto k for pequeno face a 365, cada logaritmo é quase o seu próprio argumento. O que sobra é a soma dos primeiros n−1 inteiros.

   $$\ln Q=\sum_{k=0}^{n-1}\ln\!\left(1-\frac{k}{365}\right)\approx-\sum_{k=0}^{n-1}\frac{k}{365}=-\frac{n(n-1)}{730}$$

3. Iguale a probabilidade a meio e resolva. O termo n² domina o n, portanto a resposta é uma raiz quadrada, e cai a menos de meia pessoa dos 23 do painel.

   $$P=\tfrac12\ \Longrightarrow\ \frac{n(n-1)}{730}=\ln2\ \Longrightarrow\ n^{2}\approx730\ln2=506.0\ \Longrightarrow\ n\approx22.5$$

4. Escreva-a agora sem nenhum 365. O ano nunca foi especial: para N casas igualmente prováveis, o ponto de viragem está por volta de 1,1774√N.

   $$n\approx\sqrt{2N\ln2}=1.1774\sqrt{N}:\qquad N=365\ \Longrightarrow\ 22.49$$

5. Aplique isso onde realmente morde. Uma dispersão de 32 bits tem 2³² casas, o que soa enorme — mas a raiz quadrada de um número enorme não é enorme.

   $$N=2^{32}:\qquad n\approx1.1774\sqrt{2^{32}}=1.1774\times65\,536=77\,162$$

6. Meça isso contra o tamanho do espaço de onde é retirado.

   $$\frac{77\,162}{2^{32}}=1.8\times10^{-5}=0.0018\%$$