Gimimo dienų paradoksas

Gimimo dienų paradoksas – matematinis paradoksas, teigiantis, kad 23 ir daugiau žmonių grupei yra didesnė nei 50 % tikimybė, kad bent du žmonės iš grupės švenčia gimimo dieną tą pačią metų dieną. 60 ir daugiau žmonių grupei tokia tikimybė yra didesnė nei 99 %, nors 100 % tikimybė bus pasiekta tik kai grupėje bus daugiau, kaip 365 žmonės (atsižvelgus į keliamuosius metus – 366). Atrodo, kad toks tvirtinimas prieštarauja sveikai nuovokai, nes tikimybė gimti nustatytą dieną labai maža, o tikimybė gimti dviem tą pačią dieną – dar mažesnė, bet yra tiksli pagal tikimybių teoriją. Tokiu būdu tai yra paradoksas moksliniu požiūriu – logiško prieštaravimo jame nėra, o paradoksas slypi tik skirtumuose tarp žmogaus intuityvumo ir matematinių apskaičiavimų.

Iš sveikos nuovokos požiūrio taško

Norint suprasti, kodėl iš 23 žmonių grupės dviejų žmonių gimimo dienos sutapimas toksai didelis, reikia atsižvelgti į tokį faktą: gali sutapti bet kurių dviejų žmonių iš 23 žmonių grupės gimimo diena. Kai žmonių eiliškumas porose nėra svarbus, tai tokių nesikartojančių porų skaičius lygus 23 × 22/2 = 253 poros. Gavus skaičių 253, darosi aišku, kad gimimo dienų sutapimo tikimybė labai didelė.

Tikimybė tokia didelė dėl to, kad gali sutapti bet kurių dviejų žmonių gimtadienis. Skaičiuojant dažnai daroma klaida, kai iš grupės išrenkamas vienas žmogus ir skaičiuojama, kokia yra tikimybė, kad su jo gimtadieniu sutaptų kito žmogaus gimtadienis. Žinoma, tokiu atveju tikimybė, kad dar kieno nors gimtadienis bus tą pačią dieną, labai sumažėja.

Tikimybės apskaičiavimas

Skaičiuodami gimtadienių sutapimo tikimybę n žmonių grupėje turime daryti prielaidą, kad gimimo dienos pasiskirsčiusios tolygiai, t. y. nėra keliamųjų metų, dvynių, gimimai nepriklauso nuo metų laiko ar savaitės dienos ir kitų faktorių (ceteris paribus). Iš tikrųjų taip nėra – įprastai vasarą vaikų gimsta daugiau, be to, kartais dėl gimdymo namų darbo laiko daugiau vaikų gimsta vienodomis savaitės dienomis (darbo dienomis). Gimimų netolygus pasiskirstymas tik dar daugiau didina gimimo dienų sutapimo tikimybę – net intuityviai aišku, kad jei žmonės gimtų tik 3 dienas iš 365, tai tikimybė, kad jų gimtadieniai sutaps, bus labai aukšta.

Pirma apskaičiuosime, kokia tikimybė p (n) to, kad grupėje iš n žmonių visų gimtadieniai bus skirtingomis dienomis. Jeigu n > 365, tai pagal Dirihlė principą tikimybė lygi nuliui. Jeigu n ≤ 365, galvosime taip. Atsitiktinai parinksime vieną žmogų ir atsiminsime jo gimtadienį. Paskui atsitiktinai parinksime kitą žmogų – tikimybė, kad jo gimtadienis nesutaps su pirmo žmogaus gimtadieniu, lygi 1 – 1/365 x 100 %. Paskui atsitiktinai parinksime trečią žmogų – tikimybė, kad jo gimtadienis nesutaps su pirmų dviejų, lygi 1 – 2/365 x 100 %. Analogiškai mąstant, tikimybė, kad paskutinio grupės žmogaus gimtadienis nesutaps su visų likusių, bus lygus 1 – (n – 1)/365 x 100 %. Dauginant visas šitas tikimybes gausime tikimybę to, kad visos grupėje gimimo dienos bus skirtingos:

${\bar {p}}(n)=1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1-{\frac {n-1}{365}}\right)={365\cdot 364\cdots (365-n+1) \over 365^{n}}={365! \over 365^{n}(365-n)!},$

Tada tikimybė, kad nors dviejų žmonių n gimtadieniai sutaps, lygi:

$p(n)=1-{\bar {p}}(n).$

Šitos funkcijos reikšmė didesnė už 1/2, kai n = 23 (tada sutapimo tikimybė lygi 50.7 %). Kai kurių n reikšmių (kokia tikimybė, esant skirtingoms žmonių grupėms, kad tarp jų bus gimusių tą pačią dieną) tikimybė parodyta lentelėje:

n	p (n)
10	12 %
20	41 %
30	70 %
50	97 %
100	99.99996 %
200	99.9999999999999999999999999998 %
300	(1 − 7×10−73) × 100 %
350	(1 − 3×10−131) × 100 %
366	100 %

Alternatyvus apskaičiavimo būdas

Gimtadienių sutapimo tikimybę galima apskaičiuoti ir naudojant kombinatorikos formules. Įsivaizduokime, kad kiekviena metų diena – tai viena iš 365 raidžių. Gimimo dienos n gali būti pateiktos eilute, susidedančia iš n raidžių. Tokių eilučių bendras skaičius lygus:

$n_{\mathrm {total} }=365^{n}\,$

Bendras eilučių, kuriose raidės nesikartoja, skaičius bus:

$n_{\mathrm {unique} }={\frac {365!}{(365-n)!}}$

Tada, jei eilutės išrenkamos atsitiktinai (esant tolygiam pasiskirstymui), tai tikimybė išrinkti eilutę, kurioje bent dvi raidės sutaps, lygi:

$p(n)=1-{\frac {n_{\mathrm {unique} }}{n_{\mathrm {total} }}}=1-{\frac {\frac {365!}{(365-n)!}}{365^{n}}}$

dėl n ≤ 365 ir p  (n) = 1 dėl n > 365,

nes

${\frac {\left({\frac {365!}{(365-n)!}}\right)}{365^{n}}}={\frac {365\cdot 364\cdot 363\cdots (365-n+1)}{365^{n}}}=$

${\frac {365}{365}}{\frac {364}{365}}{\frac {363}{365}}\cdots {\frac {365-n+1}{365}}=1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1-{\frac {n-1}{365}}\right),$

tokia reikšmė parodyta aukščiau.

Aproksimacija

Jei išskaidysime eksponentinę funkciją į Teiloro eilę

$e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots$

aukščiau pateikta reikšmė duoda reikšmę p  (n), galima aproksimuoti (sugretinti) tokiu būdu:

Grafikas parodo santykį tarp tikslių reikšmių ir aproksimaciją p (n)

${\bar {p}}(n)\approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}$

$=1\cdot e^{-(1+2+\cdots +(n-1))/365}$

$=e^{-(n(n-1))/2\cdot 365}$

Dėl to

$p(n)=1-{\bar {p}}(n)\approx 1-e^{-(n(n-1))/2\cdot 365}$

Dar didesnei aproksimacijai galima paimti reikšmes

$p(n)\approx 1-e^{-n^{2}/{2\cdot 365}},\,$

kurios, kaip rodo grafikas, vis dar pateikia pakankamą tikslumą.

Gimę vieną dieną su pasirinktu žmogumi

Tikimybės sulyginimas p (n) ir q (n)

Įdomu sulyginti tikimybes p  (n) su tikimybę to, kad grupėje iš n žmonių kuris nors gimęs vieną dieną su anksčiau pasirinktu žmogumi. Tokia tikimybė lygi:

$q(n)=1-\left({\frac {365-1}{365}}\right)^{n}$

Įstate į n = 22, gausime q  (n) apytiksliai 5.9 % – ne ką daugiau, negu vienas šansas iš 17. Kad išrinkto žmogaus gimtadienis daugiau kaip 50 % sutaptų su vieno iš grupės gimtadieniu, grupėje turi būti ne mažiau, kaip 253 žmonės. Toks dienų skaičius akivaizdžiai didesnis, negu pusė metų (365/2 = 182.5): taip įvyksta dėl to, kad tarp likusių iš grupės žmonių gimtadieniai gali sutapti – tai mažina sutapimo su pasirinkto žmogaus gimimo diena tikimybę.

Bendro pobūdžio užduotis

Uždavinio sprendimas būdas apie gimtadienius gali būti panaudotas ir pasikartojančių skaičių sekos sutapimams apskaičiuoti. Konkrečiau uždavinio klausimas būtu toks: jeigu duota n tolygiai išsidėsčiusių atsitiktinių skaičių intervale nuo 1 iki d, tai kokia tikimybė p (n ; d), kad du skaičiai sutaps?

Taip samprotaujant galima gauti bendrą sprendimą:

$p(n;d)={\begin{cases}1-\prod _{k=1}^{n-1}\left(1-{k \over d}\right)&n\leq d\\1&n>d\end{cases}}$

$p(n;d)\approx 1-e^{-(n(n-1))/2d}$

$q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}$

Priedas

Gimimo dienų paradoksą panaudosime dar bendresne prasme maišos funkcijoje: jeigu maišos funkcija generuoja N-bitų reikšmę, tai elementų, kuriais galima operuoti be aukštos tikimybių kolizijos (tai vienodos reikšmės funkcijos sugrąžinimas dėl dviejų elementų), skaičius lygus ne 2^N, o tik apie 2^N/2. Kaip pasekmė nedidelis koalicijos skaičius maišos funkcijoje praktiniuose pavyzdžiuose atsiranda netikėtai. Toks efektas naudojamas „gimimų atakos“ (birthday attack) kriptografinėse maišos funkcijose.

Panašus matematinis metodas naudojamas žuvų populiacijai ežeruose įvertinti „capture - recapture“ metodu. Jei kiekvieną pagautą žuvį žymėsime ir paleisime, tai tikimybė pagauti pažymėtą žuvį augant bandymų skaičiui augs ne tiesiškai, o kaip parodyta grafike. Žuvų populiacijos dydis gali būti įvertintas kaip bandymų skaičiaus iki pirmos pagautos pažymėtos žuvies kvadratas.

Toks sprendimas gaunamas daugelyje matematikos sričių, sakykim, faktorizacijos nedeterminuotose algoritmuose. Vienas iš pačių paprasčiausių Poladro p - algoritmo paaiškinimų yra analogiškas gimimo dienų paaiškinimui: reikia turėti maždaug ${\sqrt {p}}$ atsitiktinių skaičių nuo 0 iki $n=pq$, kur $p<q$ – sveiki, kad nors vienoje iš porų su didele tikimybe atsirastų $\gcd \left(|x-y|,n\right)>1$, kuris dalintųsi iš skaičiaus n.

Artimos gimimo dienos

Kita paradokso dalis yra ta, kad reikia nedaug žmonių, kad dviejų iš jų gimimo dienų skirtumas būtu viena (dvi, trys ir t. t.) dienos, tikimybė būtu didesnė negu 50 %. Tai apskaičiuoti yra sunkiau, jos sprendimui naudojamas įjungimo – išjungimo principas. Rezultatas būtu toks (su sąlyga, kad gimimo dienos pasiskirsto tolygiai):

Didžiausias gimimo dienų skirtumas	Reikalingas žmonių skaičius
0	23
1	14
2	11
3	9
4	8
5	7
7	6

Tokiu atveju tikimybė, kad grupėje iš 6 žmonių nors dviejų žmonių gimimo diena skirsis mažiau kaip savaite, viršys 50 %.

Literatūra

• G. Sekejus Paradoksai tikimybių teorijoje ir matematinėje statistikoje. 2003. (ISBN 5-93972-150-8)
• M. V. Kozlovas Tikimybių teorijos elementai pavyzdžiuose ir uždaviniuose. 1990. (ISBN 5-211-00312-8)

Nuorodos

• Tikimybių teorijos paradoksai Archyvuota kopija 2007-02-16 iš Wayback Machine projekto.
• Gimimo dienų paradoksas heš – funkcijos teorijoje Archyvuota kopija 2007-03-13 iš Wayback Machine projekto.
• Gimimo dienų paradoksas ir kriptografijos statiškumas