Az ember ösztönösen a 365 vagy 366 felére, olyan 180 körüli értékre gondol, de a valódi megoldás mindössze 23. Ez születésnap paradoxonként ismert, és pl. it is olvashatunk róla: https://en.wikipedia.org/wiki/Birthday_problem.
Egyszerűbb azt kiszámolni, hogy mekkora eséllyel nincs két ilyen ember. Ill. számoljunk azzal, hogy egy év 365 napból áll.
- 1 ember esetén 100%.
- 2 ember esetén a következő a helyzet: rögzítsük le az első ember születésnapját. A második ember születésnapja nem eshet arra a dátumra, tehát 364/365 esélye annak, hogy nem ugyanarra a napra esnek.
- 3 ember esetén ha az első kettő ember születésnapja nem ugyanarra a napra esik (amit feltételezünk), akkor a harmadik ember születésnapja nem eshet erre a 2 napra, azaz 363/365 eséllyel fog különbözni.
- Általános esetben, N ember esetén $\frac{366-N}{365}$ lesz az arány.
Ezeket össze kell szorozni, az eredményt ki kell vonni 1-ből, és megkapjuk az eredményt:
$1 - \frac{364}{365}\cdot\frac{363}{365}\cdot\dots\cdot\frac{366-N}{365}$
Programmal a következőképpen tudjuk kiszámolni azt, hogy adott számú emberre mekkora a valószínűség:
def calculate_birthday_probability(number_of_persons):
product = 1
for i in range(number_of_persons):
product *= (365 - i) / 365
return 1 - product
Néhány kiszámolt érték:
- 10: 11,7%
- 22: 47,6%
- 23: 50,7%
- 24: 53,8%
- 30: 70,6%
- 50: 97,0%
- 100: 99.99997%
Az értékek jelentése az eredeti feladat alapján: 11,5% esélye van annak, hogy 10 ember között van legalább kettő, akinek ugyanarra a napra esik a születésnapja.
Általánosítsunk! Számoljuk ki a valószínűséget tetszőleges összes esettel és tetszőleges elemszámmal:
def calculate_probability_having_common(number_of_all_cases, number_of_items):
product = 1
for i in range(number_of_items):
product *= (number_of_all_cases - i) / number_of_all_cases
return 1 - product
Tehát a kérdés, amire a függvény a választ adja az az, hogy az első paraméterként átadott érték az összes eset száma, a második pedig az, hogy hány véletlenszerű eset van, az eredmény pedig a valószínűség.
A függvény jelentése a születésnap paradoxon esetén: az összes eset száma (number_of_all_cases) 365, a véletlenszerű esetek száma (number_of_items) 23, az eredmény (calculate_probability_having_common(365, 23)) pedig azt jelenti, hogy mekkora az esélye annak, hogy 23 véletlenszerűen kiválasztott ember esetén lesz legalább kettő, akinek ugyanarra a napra esik a születésnapja: 0,503.
Egy másik példa: mekkora az esélye annak, hogy egy véletlenszerű, 6 emberből álló társaságban van kettő vagy több olyan ember, akik ugyanabban a hónapban születtek? calculate_probability_having_common(12, 6), és az eredmény kb. 77.7%.
További általánosítás: tetszőleges elemszámnál hol jön ki az 50%?
def calculate_element_number_for_fifty_percent(number_of_all_cases):
product = 1
for i in range(number_of_all_cases):
product *= (number_of_all_cases - i) / number_of_all_cases
if product < 0.5:
return i + 1
return number_of_all_cases
Lefuttatva kisebb-nagyobb méretű elemekre azt kapjuk, hogy az érték elég jól közelíti és arányos az összes eset négyzetgyökével. (A sejtésért és az általánosításokért is Kelemen Dávidé az érdem.) Az alábbi táblázat néhány 10 hatvány eredményeit tartalmazza:
Kitevő |
Összes lehetőség száma |
50% körüli elemek száma |
Négyzetgyök |
Az 50%-os érték és a négyzetgyök aránya |
1 |
10 |
5 |
3.16227766 |
1.581139 |
2 |
100 |
13 |
10 |
1.300000 |
3 |
1000 |
38 |
31.6227766 |
1.201666 |
4 |
10000 |
119 |
100 |
1.190000 |
5 |
100000 |
373 |
316.227766 |
1.179530 |
6 |
1000000 |
1178 |
1000 |
1.178000 |
7 |
10000000 |
3724 |
3162.27766 |
1.177632 |
8 |
100000000 |
11775 |
10000 |
1.177500 |
9 |
1000000000 |
37234 |
31622.7766 |
1.177442 |
10 |
10000000000 |
117742 |
100000 |
1.177420 |
11 |
100000000000 |
372331 |
316227.766 |
1.177414 |
12 |
1000000000000 |
1177411 |
1000000 |
1.177411 |
Ennek jelentése a születésnap paradoxon esetén az alábbi. Általánosítsuk a születésnapot valami másra. Pl. a 10000 szintén jelenthet napokat. Ez esetben ez egy bő 27 éves intervallumot jelent. Pl. vegyünk egy céget, és azokat az alkalmazottakat, akik 25 és 52 év közöttiek. A kérdés az az, hogy hány ember esetén lesz kb. 50% annak az esélye, hogy napra pontosan egyforma életkorúak. Az eredmény 119 fő, a négyzetgyök pedig 100. Ebben a példában a tényleges eredmény minden bizonnyal ennél alacsonyabb, ugyanis az kor eloszlása nem egyenletes, tehát pl. több a 30 év körüli kolléga mint az 50 év körüli. Az utolsó szám a következő. Az eredeti születésnap paradoxon esetében kijött a 23-as érték. Ez kb. 20%-kal magasabb mint a 365 négyzetgyöke (≈19.1). A kérdés az az, hogy ha az összes eset számét (tehát az eredetileg 365-öt) növeljük, akkor az eredmény hogyan alakul a négyzetgyökhöz képest.
Vajon hány elemnél lesz az utolsó oszlop aránya 1? Ehhez a calculate_probability_having_common függvényt kell használni úgy, hogy a második paraméter az első négyzetgyöke. Kellően nagy számokkal számolva 39,34%-ra jön ki. Ennek a jelentése a születésnap paradoxon esetén a következő. Azt tudjuk, hogy 365 lehetőség esetén 23 esetnek kell lennie ahhoz, hogy 50% eséllyel legyen két esetnek ugyanaz az értéke. Viszont 365 négyzetgyöke kb. 19.1, kerekítve, 19, tehát a kérdés az az, hogy 19 ember esetén mekkora az esélye annak, hogy van két ember, akinek ugyanarra a napra esik a születésnapja. Ez az érték konkrétan 37.9%. De ha növeljük a lehetőségek számát, akkor a fenti, 40% körüli értéken stabilizálódik.
Végül azt is nézzük meg, hogy adott lehetőségek száma és adott százalék esetén mekkora az elemszám. Tehát pl. 365 nappal számolva legkevesebb hány emberre van szükség ahhoz, hogy elérje a 80%-ot annak a valószínűsége, hogy van két ember, akinek ugyanarra a napra esik a születésnapja. Itt egészen pontosan fordítva adjuk meg, mert a lebegőpontos számábrázolás miatt a 0 közeli értékeket sokkal pontosabban meg lehet adni, mint az 1-hez közelieket. A függvény értelmezése a születésnapos példával tehát a következő: 365 nappal számolva legkevesebb hány emberre van szükség ahhoz, hogy 20% alatt legyen annak a valószínűsége, hogy nincs két ember, akinek ugyanarra a napra esik a születésnapja. A függvény:
def calculate_element_number_for_given_percent(number_of_all_cases, percent):
product = 1
for i in range(number_of_all_cases):
product *= (number_of_all_cases - i) / number_of_all_cases
if product < percent:
return i + 1
return number_of_all_cases
Itt tehát így kell meghívni: calculate_element_number_for_given_percent(365, 0.2), és az eredmény 35. Néhány érték:
- 1%: 57
- 0.1%: 70
- 0.01%: 80
- 1 az egymillióhoz: 97
- 1 az egymilliárdhoz: 117
- 1 a $10^{81}$: 300
Tehát 100 körül már közel nulla annak az esélye, hogy nincs két olyan ember, akinek ugyanarra a napra esik a születésnapja.