A Születésnap-paradoxon

Philip J. Erdelsky

2001. július 4.

Kérjük, küldje el észrevételeit, javításait és kiegészítéseit e-mailben a webmesternek a pje@efgh.com címen . 

Az elemi valószínűség számítási és statisztikai kurzusok egyik kedvenc problematikája a Születésnap-paradoxon: mi a valószínűsége annak, hogy N véletlenszerűen kiválasztott személy közül legalább kettőnek azonos napon van a születésnapja? (Ugyanaz a hónap és nap, de nem feltétlenül ugyanaz az év).

A probléma második része: Milyen nagynak kell lennie N-nek, hogy a valószínűség meghaladja az 50%-ot? A válasz 23, ami a legtöbbek számára ésszerűtlenül kicsinek tűnhet. Ezért nevezik a problémát gyakran Születésnap-paradoxonnak. Néhányan akár pénzben is hajlandóak fogadni, hogy egy 23 vagy annál nagyobb fős csoportban lesznek olyanok, akiknek ugyanazon a napon van a születésnapjuk. Feltehetően vannak olyan rosszul tájékozott játékosok, akik belemennek egy ilyen fogadásba.

A problémát két dolog feltételezésével egyszerűsíthetjük:

  1. A csoportból senki sem született február 29-én.

  2. Az emberek születésnapjai egyenlően oszlanak el az év többi 365 napjára.

Az egyik első fontos dolog, amit érdemes észrevenni, hogy a kiegészítő problémát sokkal könnyebb megoldani, vagyis, hogy mi a valószínűsége annak, hogy N véletlenszerűen kiválasztott embernek más-más napon van a születésnapja? Ezt egy rekurzív függvényként írhatjuk le:

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

Nyilvánvaló, hogy N = 1 esetén a valószínűség 1. Ha N>1, akkor a valószínűség két valószínűség szorzata:

  1. Hogy az első N-1 embernek mind különböző napon van a születésnapja.

  2. Hogy az N-edik személy születésnapja eltér az első N-1-edik személy születésnapjától.

A valószínűségeket megjelenítő program működése:

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

Az eredmény pedig valami ehhez hasonló:

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

Az a valószínűség, hogy N személy közül legalább kettőnek ugyanazon a napon van a születésnapja, 0,5 fölé emelkedik, ha N = 23.

DE MI A HELYZET SZÖKŐÉV ESETÉN?

Az eredeti problémát egy logarléc segítségével meg lehet oldani, pontosan ezt is tettem, amikor először, sok-sok évvel ezelőtt hallottam róla.

Ha a február 29-et hozzáadjuk az elegyhez, az jelentősen megbonyolítja a dolgokat. Ebben az esetben néhány további feltevést vagyunk kénytelenek tenni:

  1. Ugyanannyi számú ember született bármely napon, ami nem február 29-e.

  2. A február 29-én született emberek száma csak egynegyede a bármely más napon született emberek számának.

Ennélfogva annak a valószínűsége, hogy egy véletlenszerűen kiválasztott személy február 29-én született, 0,25 / 365,25, és annak valószínűsége, hogy egy véletlenszerűen kiválasztott személy egy másik meghatározott napon született, 1 / 365,25.

Az a valószínűség, hogy N számú személy - köztük egy olyannal, aki február 29-én született – születésnapja különböző napokra essen, a két valószínűség összege:

  1. Hogy az N számú személy február 29-étől eltérő N számú napon született.

  2. Hogy az N számú személy N számú különböző napon született, beleértve egyet, aki február 29-én született.

A valószínűségek összeadódnak, mivel a két eset kölcsönösen kizárja egymást.

Most már minden valószínűség rekurzív módon kifejezhető:

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

A valószínűségeket megjelenítő program:

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

Az eredmény pedig a következő:

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

Ahogy az várható volt, a valószínűségek kissé alacsonyabbak, mivel alacsonyabb a valószínűsége annak, hogy a születésnapok megegyeznek, ha több lehetséges születésnap van. De a legkisebb szám, amelynek valószínűsége meghaladja a 0,5-öt, továbbra is 23.

Természetesen egy matematikai purista azzal érvelhet, hogy a szökő évek nem mindig négyévente érkeznek, tehát a számításokat további kell módosítani. Azonban az utolsó ciklus, amikor nem volt szökőév, 1900-ban volt, a következő pedig 2100-ban lesz. A most élő, 1900-ban született személyek száma olyan kicsi, hogy véleményem szerint közelítésünk minden gyakorlati célra érvényesnek tekinthető. De kérésre szívesen elvégzem a szükséges módosításokat.

A Születésnap-paradoxonnak a fogadások világán túl is van jelentősége. Az adattárolás szokásos módja az, hogy minden elemhez egy hash kódnak nevezett számot rendelünk. Az elemet ezután a hash kódjának megfelelő tárolóban tároljuk. Ez felgyorsítja a visszakeresést, mert csak egyetlen tárolót kell keresni. A Születésnap-paradoxon azt mutatja meg, hogy annak a valószínűsége, hogy két vagy több elem ugyanabba a tárolóba kerül magas, még akkor is, ha az elemek száma jóval kevesebb, mint a tárolók száma. Ezért minden esetben szükséges a két vagy több elemet tartalmazó tárolók hatékony kezelésére.

Fordította: pepebet.com