Original Article: Simulation of Ant's The Birthday Paradox

Author: Philip J. Erdelsky

O Paradoxo de Aniversário Philip J. Erdelsky 4 de julho de 2001

Envie comentários por e-mail, correções e adições ao webmaster em [email protected].

Um problema favorito em cursos de probabilidade elementar e estatística é o problema do aniversário: qual é a probabilidade de pelo menos duas das N pessoas selecionadas aleatoriamente terem o mesmo aniversário? (Mesmo mês e dia, mas não necessariamente no mesmo ano.)

Uma segunda parte do problema: Quão grande deve ser N para que a probabilidade seja superior a 50%? A resposta é 23, que atinge a maioria das pessoas tão pouco razoável. Por esse motivo, o problema é chamado de Paradoxo de Aniversário. Algumas notas recomendam apostar, mesmo em dinheiro, que há aniversários duplicados entre qualquer grupo de 23 pessoas ou mais. Presumivelmente, há alguns otários mal informados que aceitarão a aposta.

O problema geralmente é simplificado assumindo duas coisas:

1. Ninguém nasceu em 29 de fevereiro.
2. Os aniversários das pessoas são distribuídos igualmente nos outros 365 dias do ano.

Uma das primeiras coisas a notar sobre esse problema é que é muito mais fácil resolver o problema complementar: qual é a probabilidade de que N pessoas escolhidas aleatoriamente tenham todos os aniversários diferentes? Podemos escrever isso como uma função recursiva:

double different_birthdays(int n)
{
  return n == 1 ? 1.0 : different_birthdays(n-1) * (365.0-(n-1))/365.0;
}

Obviamente, para N = 1, a probabilidade é 1. Para N> 1, a probabilidade é o produto de duas probabilidades:

1. Que as primeiras N-1 pessoas tenham todos os aniversários diferentes.
2. Que a N-ésima pessoa tenha um aniversário diferente de qualquer um dos primeiros N-1.

Um programa para exibir as probabilidades é algo como isto:

void main(void)
{
  int n;
  for (n = 1; n <= 365; n++)
    printf("%3d: %e\n", n, 1.0-different_birthdays(n));
}

O resultado é algo como isto:

  1: 0.000000e+00
  2: 2.739726e-03
  3: 8.204166e-03
  4: 1.635591e-02
  5: 2.713557e-02
      ***
 20: 4.114384e-01
 21: 4.436883e-01
 22: 4.756953e-01
 23: 5.072972e-01
 24: 5.383443e-01
 25: 5.686997e-01
      ***

A probabilidade de que pelo menos duas das N pessoas tenham o mesmo aniversário sobe acima de 0,5 quando N = 23.

MAS SOBRE O ANO LEAP?

O problema original pode ser resolvido com uma regra de slide, o que é exatamente o que eu fiz quando o ouvi falar há muitos anos atrás.

Se adicionarmos 29 de fevereiro à mistura, fica consideravelmente mais complicado. Nesse caso, fazemos algumas suposições adicionais:

1. Igual número de pessoas nasceu em dias que não são 29 de fevereiro.
2. O número de pessoas nascidas em 29 de fevereiro é um quarto do número de pessoas nascidas em qualquer outro dia.

Portanto, a probabilidade de uma pessoa selecionada aleatoriamente nascer em 29 de fevereiro é de 0,25 / 365,25, e a probabilidade de uma pessoa selecionada aleatoriamente nascer em outro dia específico é 1 / 365,25.

A probabilidade de que N pessoas, possivelmente incluindo uma nascida em 29 de fevereiro, tenham aniversários distintos é a soma de duas probabilidades:

1. Que as N pessoas nasceram em N dias diferentes a 29 de fevereiro.
2. Que as N pessoas nasceram em N dias diferentes e incluem uma pessoa nascida em 29 de fevereiro.

As probabilidades acrescentam porque os dois casos são mutuamente exclusivos.

Agora, cada probabilidade pode ser expressa de forma recursiva:

double different_birthdays_excluding_Feb_29(int n)
{
  return n == 1 ? 365.0/365.25  :
    different_birthdays_excluding_Feb_29(n-1) * (365.0-(n-1)) / 365.25;
}

double different_birthdays_including_Feb_29(int n)
{
  return n == 1 ? 0.25 / 365.25 :
    different_birthdays_including_Feb_29(n-1) * (365.0-(n-2)) / 365.25 +
    different_birthdays_excluding_Feb_29(n-1) * 0.25 / 365.25;
}

Um programa para exibir as probabilidades é algo como isto:

void main(void)
{
  int n;
  for (n = 1; n <= 366; n++)
    printf("%3d: %e\n", n, 1.0-different_birthdays_excluding_Feb_29(n) -
      different_birthdays_including_Feb_29(n));
}

O resultado é algo como isto:

  1: -8.348357e-18
  2: 2.736445e-03
  3: 8.194354e-03
  4: 1.633640e-02
  5: 2.710333e-02
      ***
 20: 4.110536e-01
 21: 4.432853e-01
 22: 4.752764e-01
 23: 5.068650e-01
 24: 5.379013e-01
 25: 5.682487e-01
      ***

Como esperado, as probabilidades são ligeiramente mais baixas, porque há uma menor probabilidade de combinar aniversários quando há mais aniversários possíveis. Mas o número mais pequeno com probabilidade superior a 0,5 ainda é 23.

Claro, um purista matemático pode argumentar que os anos bissextos nem sempre vem a cada quatro anos, então os cálculos precisam ser modificados. No entanto, o último ano quadrienal que não foi um ano bissexto foi de 1900, e o próximo será 2100. O número de pessoas que vivem agora que nasceram em 1900 é tão pequeno que acho nossa aproximação válida para todos os propósitos práticos. Mas você pode fazer as modificações necessárias se desejar.

O Paradoxo de Aniversário tem implicações além do mundo das apostas em salões. Uma técnica padrão no armazenamento de dados é atribuir a cada item um número chamado código hash. O item é então armazenado em um compartimento correspondente ao seu código hash. Isso acelera a recuperação porque apenas um único compartimento deve ser pesquisado. O Paradoxo de Aniversário mostra que a probabilidade de que dois ou mais itens acabem no mesmo compartimento é alta, mesmo que o número de itens seja consideravelmente menor do que o número de caixas. Portanto, o manuseio eficiente de caixas contendo dois ou mais itens é necessário em todos os casos.