Paradoks rođendana

Original: http://efgh.com/math/birthday.htm

LOGO

Philip J. Erdelsky

4. juli 2001

 

 

Omiljeni problem u osnovnim kursevima vjerovatnoće i statistike je problem rođendana: kolika je vjerojatnost da barem dvije od N nasumično odabranih osoba imaju isti rođendan? (Isti mjesec i dan, ali ne nužno iste godine.)

Drugi dio problema: Kolika je N mora biti tako da je vjerojatnost veća od 50%? Odgovor je 23, što pogađa većinu ljudi kao nerazumno male. Iz tog razloga, problem se često naziva rođendanski paradoks. Neke oštrice preporučuju klađenje, čak i na novac, da postoje duple rođendane u bilo kojoj grupi od 23 ili više ljudi. Pretpostavljam da postoje neki loše informisani odojak koji će prihvatiti opkladu.

Problem je obično pojednostavljen pretpostavljajući dvije stvari:

  1. Niko nije rođen 29. februara.
  2. Rođendani su jednako raspoređeni po ostalim 365 dana u godini.

Jedna od prvih stvari koje treba primijetiti u vezi s ovim problemom je da je mnogo lakše riješiti komplementarni problem: Koja je vjerojatnost da N nasumično odabranih ljudi ima sve različite rođendane? Možemo ovo napisati kao rekurzivnu funkciju:

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

Očigledno, za N = 1 vjerovatnoća je 1. Za N>1, vjerojatnost je proizvod dvije vjerojatnosti:

  1. Da prvi N-1 ima sve različite rođendane.
  2. Da N-ta osoba ima rođendan drugačiji od bilo kojeg prvog N-1.

Program za prikaz vjerovatnoća ide ovako:

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

Rezultat je nešto ovako:

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
      ***

Verovatnoća da najmanje dva od N ljudi imaju isti rođendan raste iznad 0,5 kada je N=23.

ALI ŠTA O LEAP GODINI?

Prvobitni problem se može riješiti slajd pravilom, što je upravo ono što sam učinio kada sam je prvi put čuo prije mnogo godina.

Ako dodamo 29. februar u mix, to postaje znatno komplikovanije. U ovom slučaju, donosimo neke dodatne pretpostavke:

  1. Jednak broj ljudi rođen je na dane koji nisu 29. februar.
  2. Broj ljudi rođenih 29. februara je jedna četvrtina broja ljudi rođenih bilo kog drugog dana.

Stoga je vjerovatnoća da je slučajno odabrana osoba rođena 29. veljače 0,25/365,25, a vjerojatnost da je slučajno odabrana osoba rođena u određenom danu iznosi 1/365,25.

Vjerovatnoća da N osoba, možda uključujući i jednu rođenu 29. februara, ima različite rođendane, je zbir dvije vjerovatnoće:

  1. Da su N osobe rođene N različitih dana, osim 29. februara.
  2. Da su N osobe rođene u različite dane i da je jedna osoba rođena 29. februara.

Verovatnoće se dodaju jer se dva slučaja međusobno isključuju.

Sada se svaka vjerovatnoća može izraziti rekurzivno:

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;
}

Program za prikaz vjerovatnoća ide ovako nešto:

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));
}

Rezultat je nešto ovako:

  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
      ***

Kao što se i očekivalo, vjerovatnoće su nešto niže, jer postoji manja vjerojatnost podudaranja rođendana kada postoji više mogućih rođendana. Ipak, najmanji broj sa verovatnoćom većom od 0.5 je još uvek 23.

Naravno, matematički purist može tvrditi da prestupne godine ne dolaze uvijek svake četiri godine, tako da je za izračunavanje potrebna daljnja modifikacija. Međutim, posljednja četverogodišnja godina koja nije bila prijestupna godina bila je 1900, a sljedeća 2100. Broj osoba koje sada žive, rođene 1900. godine, toliko je mali da mislim da naša aproksimacija vrijedi za sve praktične svrhe. Ali, ako želite, možete napraviti potrebne izmjene.

Paradoks rođendana ima implikacije izvan svijeta klađenja. Standardna tehnika u skladištenju podataka je dodijeliti svakom elementu broj koji se zove hes-kod. Stavka se zatim pohranjuje u bin koji odgovara njegovoj šifri. Ovo ubrzava dohvat jer se mora pretraživati ​​samo jedna ladica. Rođendanski paradoks pokazuje da je vjerovatnoća da će dvije ili više stavki završiti u istoj ladici visoka čak i ako je broj stavki znatno manji od broja kontejnera. Stoga je u svim slučajevima potrebno efikasno rukovanje posudama koje sadrže dvije ili više stavki.