Születésnap-paradoxon

A Wikipédiából, a szabad enciklopédiából

A születésnap-paradoxon az a jelenség, miszerint megdöbbentően nagy az elméleti valószínűsége annak, hogy viszonylag sok, egy szobában tartózkodó személy közül kettőt találomra kiválasztva, születésnapjuk azonos hónap azonos sorszámú napjára essen. Pl. ha egy szobában 23-an vannak, akkor valamivel több, mint 50% az elméletileg számított esélye annak, hogy legalább kettőjüknek ugyanarra a napra esik a születésnapja. Ha legalább 58 ember van a szobában (teremben), ugyanennek a valószínűsége több, mint 99%. Ez nem abban az értelemben paradoxon, hogy logikai ellentmondásra jutunk, hanem abban, hogy ellentmond az intuíció által sugalltaknak, a legtöbb ember ugyanis 50%-nál lényegesen alacsonyabbra becsüli a fenti esemény valószínűségét. A probléma és első alapos vizsgálata valószínűsíthetően Harold Davenporttól ered.

„Elméletileg számítotton” azt értjük, hogy a számítás során feltételezzük, hogy egy ember azonos statisztikai eséllyel születik az év bármely hónapjának bármely napján, amely hipotézis egyébként valójában hamis (pl. az Egyesült Államokban a Harvard kutatójának adatai szerint hetvenes és kilencvenes évek közt eltelt időben szeptember 16.-án született abszolút értelemben (nem átlagosan stb.) a legtöbb csecsemő. [1] Ez azonban a számított eredmény józan észt meglepő voltát nem érintő körülmény (nem emiatt a rejtett feltétel miatt lesz az eredmény paradox).

A valószínűség közelítő kiszámítása[szerkesztés | forrásszöveg szerkesztése]

A fenti esemény (és a hozzá hasonló) pontos valószínűségének kiszámítása klasszikus probléma, rendszeresen tanítják valószínűség-számítási kurzusok részeként az egyetemeken.

A paradoxon megértéséhez kulcsfontosságú, hogy észrevegyük, noha kevés ember van a szobában, már így is nagyon sok pár van, akiknél a születésnap-egyezést vizsgálni kell. 23 ember esetén 23 × 22 / 2 = 253 pár van, mindegyik pár egy lehetséges egyezés. Más szemszögből megközelítve: képzeljük el, hogy belépünk egy szobába, ahol már 22-en vannak, és azt vizsgáljuk, hogy a közülük valakinek ugyanakkor van-e a születésnapja, mint nekünk. Ez természetesen sokkal kisebb, mint 50%. A születésnap-paradoxon azonban azt kérdezi, hogy bármelyik két embernek a huszonháromból megegyezik-e a születésnapja.

A valószínűség közelítő kiszámításához elhanyagolunk pár részletet, így a szökőéveket, azt, hogy az emberek között lehetnek ikrek, valamint a különböző születési statisztikákat, ehelyett feltesszük, hogy ha valakinek nem ismerjük a születésnapját, akkor az a 365 napos év minden napján azonos valószínűséggel születhetett.

Az ötlet a következő: először számoljuk ki, hogy mi a valószínűsége annak, hogy n emberből mindenki más napon született:

p = \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdots \frac{365-n+1}{365}
Annak valószínűsége, hogy valahány emberből kettőnek egy napra esik a születésnapja.

mert ha (tetszőlegesen) sorba állítjuk az embereket, akkor a másodiknak nem lehet ugyanakkor a születésnapja, mint az elsőnek (364/365), a harmadiknak nem lehet ugyanakkor, mint az első kettőnek (363/365), és így tovább. A faktoriális jelölést használva ugyanezt így is felírhatjuk:

p = { 365! \over 365^n (365-n)! }.

A képletben a „kedvező esetek” kerülnek a számlálóba, itt a 365 elem n. osztályú ismétlés nélküli variációit értjük alatta. A nevezőben az összes előforduló esetet pedig a 365 n. osztályú ismétléses variációi jelentik.

Ezek után 1 ‒ p annak a valószínűsége, hogy legalább két embernek egy napra esik a születésnapja. n = 23-ra ez az érték kb. 0,507.

Vegyük észre, hogy a két embert nem választjuk ki elsőre. Ha az a kérdés, hogy milyen valószínűséggel van n emberből legalább egynek ugyanakkor a születésnapja, mint egy konkrét embernek, akkor a válasz:

 1- \left( \frac{364}{365} \right)^n

ami n = 22-re kb. 0,059, vagyis csak kicsivel több, mint 1/17. Ahhoz, hogy ennek a valószínűsége legyen több, mint 50%, nem 22, hanem 253 emberre lenne szükség! Ebben a képletben szintén ismétléses variációval állítottuk elő a kívánt esemény komplementerét.

A születésnap-paradoxon általánosítva értelmezhető hash függvényekre is: N-bites lenyomatokból (hashértékekből) valószínű ütközés nélkül sajnos nem 2N, hanem csak kb. 2N/2 generálható. Ezt használja ki az ún. születésnap-támadás különböző hashfüggvényeken alapuló titkosító algoritmusok ellen.

A paradoxon analitikus megközelítése[szerkesztés | forrásszöveg szerkesztése]

Így ír önéletrajzában Halmos Pál Richárd magyar származású matematikus:

„A probléma megközelítésének egyik módja, hogy megfordítva tesszük fel a kérdést: »Legalább hány embernek kell a szobában lennie ahhoz, hogy kevesebb, mint 1/2 valószínűséggel legyen csupa különböző születésnapjuk?« […] a probléma lényegében a következő: találjuk meg a legkisebb n-et, amire
\prod_{k=0}^{n-1}\left(1-\frac{k}{365}\right)<\frac{1}{2}.
A szorzat felülről becsülhető a következőképpen:
\left(\frac{1}{n}\sum_{k=0}^{n-1}\left(1-\frac{k}{365}\right)\right)^n
<\left(\frac{1}{n}\int_0^n\left(1-\frac{x}{365}\right)\,dx\right)^n
=\left(1-\frac{n}{730}\right)^n<e^{-n^2/730}.
Az első felső becslés a mértani és a számtani közepek közötti összefüggésből következik. Ez ismét becsülhető a határozott integrál definícióját felhasználva, amelynek analitikus módon kiszámított értéke pedig ismét felülről becsülhető az 1 ‒ x < ex összefüggést alapul véve. […] Az bizonyítás olyan fontos eszközöket használ fel, amellyel minden matematikát tanulónak illik elsajátítania. Csodálatos példája annak, hogy tisztán gondolkodással mennyi számítástól megkímélhetjük magunkat: az egyenlőtlenségek egy-két perc alatt felírhatók, míg a szorzatok kiszámítása lényegesen több időt venne igénybe, és a hibázás lehetősége is nagyobb lenne, akár papíron-ceruzával, akár számítógéppel végezzük. A számológép hasznos eszköz, de nem segít a probléma mélyebb megértésében, matematikai képességek elsajátításában, sem összetettebb, általánosabb elméletek megalkotásában.”

Hiba Halmos bizonyításában[szerkesztés | forrásszöveg szerkesztése]

A fenti érvelésbe sajnos hiba csúszott, szerencsére nem végzetes. A

\sum_{k=0}^{n-1} \left(1-{k \over 365}\right)
<\int_0^n \left(1-{x \over 365}\right)\,dx

egyenlőtlenség bizony hibás, amint az számítással egyszerűen ellenőrizhető (az egyenlőtlenség bal és jobb oldalának különbsége n/730, azaz pozitív). De az érvelés korrigálható. A

\prod_{k=0}^{n-1}\left(1-{k \over 365}\right)

szorzatban az első tényező értéke 1, ezért elhagyható. Innen

\prod_{k=1}^{n-1}\left(1-{k \over 365}\right)
<\left({1 \over n-1}\sum_{k=1}^{n-1}\left(1-{k \over 365}\right)\right)^{n-1}
=\left(1-{n \over 730}\right)^{n-1}<\left(e^{-n/730}\right)^{n-1}=e^{-(n^2-n)/730}.

ahol az első egyenlőtlenség ismét számtani és mértani közepek egyenlőtlensége, a második pedig az 1 ‒ x < ex összefüggésből következik.

Az utolsó kifejezés értéke akkor és csak akkor kisebb, mint 1/2, ha

n^2-n>730\ln 2\cong 505,997\dots

Ez „alig” kevesebb, mint 506, amellyel az n2n kifejezés pontosan n = 23 esetén egyenlő.

Kísérleti ellenőrzés[szerkesztés | forrásszöveg szerkesztése]

A születésnap-paradoxon jól szimulálható számítógépes program segítségével. A következő parancs a Ruby programozási nyelv segítségét veszi igénybe:

 puts (1..30).collect {rand(365)+1}.uniq.length

ahol 30 az emberek száma, 365 pedig az egy évbe eső napok száma. Ha az eredmény (szintén egy szám) megegyezik az emberek számával (tehát ez esetben 30-cal), akkor mindenkinek más-más napon van a véletlenül sorsolt születésnapja. Ha kisebb, akkor voltak egyezések (méghozzá pontosan annyi, amennyi a különbség a kiírt és az eredeti szám között).

A következő kódrészlet Perl programozási nyelven íródott. Ez kilistázza azokat a számokat, amelyek a generált számsorban ismétlődnek.

 for (1..23) {$h{int(rand(365)+1)}++};
 for (keys %h) {print $_, ": ", $h{$_}, " times\n" if $h{$_} > 1}

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  1. How Common Is Your Birthday?. New York Times, hiv. beill.: 2011-03-25.

További információk[szerkesztés | forrásszöveg szerkesztése]