Esta é uma tradução automática e o artigo original está em inglês. Ler o original
Vinte e três pessoas, e a coincidência que deve esperar
Vinte e três pessoas formam 253 pares. Ninguém calcula os 253, e essa é a razão inteira pela qual a resposta parece errada.
Junte 23 pessoas numa sala e a probabilidade de duas delas partilharem o aniversário é de 50,7%. Com 70 pessoas é de 99,9%.
Quase toda a gente estima um número muito mais elevado, e a razão prende-se com o facto de colocarem a pergunta errada. O instinto é pensar em si próprio: qual é a probabilidade de alguém aqui partilhar o meu aniversário? Esse é um evento muito mais raro, e seriam necessárias cerca de 253 pessoas para ultrapassar metade.
A verdadeira pergunta diz respeito a qualquer par. E os pares não são escassos.
Contar pares, não pessoas
Vinte e três pessoas formam 23 × 22 ÷ 2 = 253 pares distintos. Cada par tem uma probabilidade de 1 em 365 de coincidir. O número de pares cresce com o quadrado do número de pessoas, pelo que duplicar a sala quadruplica as oportunidades de ocorrer uma coincidência.
O cálculo exato faz-se no sentido inverso — a probabilidade de nenhuns dois coincidirem, que é 365/365 × 364/365 × 363/365 × … para 23 termos, perfazendo 0,493. Um menos esse valor é 0,507.
A regra geral que vale a pena recordar
Para N possibilidades igualmente prováveis, precisa de sensivelmente √N extrações antes que uma repetição se torne mais provável do que o contrário. Para aniversários, √365 ≈ 19, e a constante resulta em cerca de 1,18 × √N ≈ 22,5. Suficientemente perto de 23.
Raiz quadrada, não metade. É esse o número em que as pessoas se enganam, e o erro vai no sentido de esperar que as coincidências sejam mais raras do que na realidade são.
Onde deixa de ser um truque de festa
Colisões de hash. Uma tabela de dispersão com mil posições não começa a ter colisões quando se aproxima das mil entradas. Começa a ter colisões por volta das trinta. É por isso que as implementações de tabelas de dispersão se preocupam com o tratamento de colisões logo a partir da primeira inserção, e por que a medição isolada do fator de carga revela muito pouco sobre o número de sondagens exigido por uma pesquisa. A ferramenta Hash Table mostra as colisões a surgirem muito antes do esperado.
Criptografia. É aqui que a raiz quadrada define o parâmetro de segurança. Para encontrar dois documentos diferentes com o mesmo hash de 64 bits não são necessárias 2⁶⁴ tentativas; são necessárias cerca de 2³² — sensivelmente quatro mil milhões, o que corresponde a minutos de trabalho. Este é o ataque do aniversário, e é por isso que uma função hash concebida para oferecer n bits de resistência a colisões deve produzir 2n bits de saída. É a razão pela qual os hashes de 128 bits são considerados como oferecendo 64 bits de resistência a colisões e já não são aceitáveis para assinaturas.
Interpretar coincidências. Qualquer conjunto de dados suficientemente grande contém coincidências impressionantes, e o seu número varia com os pares, não com os registos. Duas pessoas de uma cidade ganharem a lotaria, o foco de uma doença numa mesma rua, duas canções com um som semelhante: estes acontecimentos tornam-se quase certezas em grande escala, e tratar cada um deles como individualmente improvável é o mesmo erro aritmético cometido em relação a pessoas e aniversários.
A pergunta correta nunca é "quão improvável é esta coincidência em particular?" É "quantas oportunidades existiram para ocorrer uma coincidência deste género?" Esses dois números diferem por um fator que cresce quadraticamente, o que é mais do que suficiente para transformar o espanto numa expectativa.
Duas objeções, ambas dignas de resposta
"Os aniversários não são uniformes." E não são — ocorrem mais nascimentos no final do verão no hemisfério norte, menos a 25 de dezembro e a 29 de fevereiro, e há uma queda visível aos fins de semana devido a partos agendados. Mas a não uniformidade torna as coincidências sempre mais prováveis, nunca menos: o agrupamento concentra as pessoas em menos dias efetivos. A hipótese de uniformidade é, portanto, conservadora, e 23 é, quando muito, uma ligeira sobreestimativa.
"Gémeos e pessoas que vieram juntas." As salas reais não são amostras aleatórias. Uma sala contendo irmãos, ou uma turma escolar selecionada por limite de idade, apresenta correlações que o modelo não inclui. O cálculo é uma linha de base para extrações independentes e, quando as extrações não são independentes, é a independência que precisa de ser defendida, não a aritmética.
A versão a guardar de memória
Se existirem N categorias igualmente prováveis e fizer k extrações, o número esperado de pares em colisão é cerca de k²/2N. Igualando esse valor a um, obtém-se k ≈ √(2N) — a mesma raiz quadrada, alcançada através da contagem de colisões esperadas em vez de probabilidades, e mais fácil de calcular de cabeça.
Para mil posições de hash: √2000 ≈ 45, portanto espere a primeira colisão por volta dos quarenta. Para um checksum de 32 bits: 2¹⁶ = 65,536 itens, valor que um ficheiro de registo atinge numa tarde. Para 365 dias: 27, suficientemente perto de 23 para que a estimativa seja de confiar.
O hábito consiste em recorrer à raiz quadrada sempre que ouve "qual é a probabilidade de um duplicado", e em notar que a resposta chega muito mais cedo do que a dimensão do espaço sugere. A ferramenta Birthday Paradox traça a curva, e a sua inclinação em redor das 20 a 30 pessoas é a parte que não resiste a ser descrita por palavras.