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:
A csoportból senki sem született február 29-én.
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:
Hogy az első N-1 embernek mind különböző napon van a születésnapja.
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:
Ugyanannyi számú ember született bármely napon, ami nem február 29-e.
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:
Hogy az N számú személy február 29-étől eltérő N számú napon született.
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