Paradoks dni urodzin

Paradoks dni urodzin^[1], paradoks urodzin^[2] – paradoks związany z rozwiązaniem poniższego zadania z rachunku prawdopodobieństwa^[1]:

Jak liczna musi być grupa osób, aby prawdopodobieństwo znalezienia w niej dwóch osób obchodzących urodziny tego samego dnia było równe co najmniej 1/2?

Zakłada się zwykle, że dni urodzin to liczby wybrane z rozkładem jednostajnym ze zbioru ${\displaystyle \{1,2,\dots ,365\},}$ co nie odbiega znacząco od rzeczywistości. W szczególności w rozwiązaniu problemu nie uwzględnia się lat przestępnych^[1].

Według Iana Stewarta, kiedy grupa badaczy zadała to pytanie studentom, mediana udzielonych odpowiedzi wyniosła 385^[3]. Tymczasem już przy 366 osobach zasada szufladkowa Dirichleta gwarantuje, że pewne dwie z nich urodziły się tego samego dnia w roku. Poprawną odpowiedzią jest jednak zaskakująco niewielka liczba 23 osób^[1][3], co uzasadnia użycie terminu „paradoks”^[1].

Autorstwo problemu przypisuje się Haroldowi Davenportowi^[4], który miał wymyślić go około 1927 roku^[5]. Davenport wyrzeka się jednak autorstwa^[4].

Rozwiązanie problemu

Prawdopodobieństwo zdarzenia przeciwnego do rozpatrywanego, czyli tego, że każda z osób ma inny dzień urodzin, jest przy ${\displaystyle k}$ osobach równe

${\displaystyle p_{k}={\frac {365\cdot 364\cdot \ldots \cdot (365-k+1)}{365^{k}}}=1\cdot \left(1-{\frac {1}{365}}\right)\cdot \ldots \cdot \left(1-{\frac {k-1}{365}}\right)}$.

Rozwiązanie problemu równoważne jest ze znalezieniem najmniejszego takiego ${\displaystyle k,}$ że ${\displaystyle p_{k}\leq 1/2.}$ Ponieważ ciąg ${\displaystyle (p_{k})}$ jest nierosnący (co nietrudno zauważyć), wystarczy bezpośrednio obliczyć przy pomocy komputera, że

${\displaystyle {\begin{aligned}p_{22}&=0{,}524\dots \\p_{23}&=0{,}493\dots \end{aligned}}}$,

by dojść do prawidłowej odpowiedzi^[1].

Aby wykazać, że wystarczą 23 osoby (choć już bez dowodu, że jest to najmniejsza taka liczba), można posłużyć się pewnymi przybliżeniami. Dla każdej liczby rzeczywistej ${\displaystyle x}$ prawdziwa jest nierówność

${\displaystyle 1+x\leq e^{x}}$,

przy czym ${\displaystyle e}$ jest podstawą logarytmu naturalnego. Zatem

${\displaystyle p_{k}\leq e^{-{\frac {1}{365}}}\cdot \ldots \cdot e^{-{\frac {k-1}{365}}}=e^{-{\frac {1+2+\dots +(k-1)}{365}}}=e^{-{\frac {k(k-1)}{730}}}}$.

Aby prawa strona powyższej nierówności była nie większa od ${\displaystyle 1/2,}$ musi zachodzić

${\displaystyle k^{2}-k-730\ln {2}\geq 0}$.

Najmniejszym dodatnim rozwiązaniem tej nierówności jest

${\displaystyle {\frac {1+{\sqrt {1+4\cdot 730\ln {2}}}}{2}}=22{,}99994315\dots }$,

co jest oczywiście mniejsze od 23^[1].

Uogólnienia i powiązane problemy

Inna liczba dni w roku

Przy założeniu, że rok ma ${\displaystyle n}$ dni, rozwiązanie problemu dni urodzin równe jest w przybliżeniu^[1]

${\displaystyle {\sqrt {2\ln {2}}}\cdot {\sqrt {n}}=1{,}177410\ldots \cdot {\sqrt {n}}}$.

Dla przykładu można rozważyć wspomniany problem dla osób urodzonych na innych planetach Układu Słonecznego^[1]:

Ustalony dzień urodzin

Problem dni urodzin można zmodyfikować, przyjmując, że przed wykonaniem doświadczenia została wybrana pewna data. Dla ustalenia uwagi, niech będzie to data urodzin przeprowadzającego eksperyment. Należy wówczas znaleźć odpowiedź na pytanie^[1]:

Jak liczna musi być grupa osób, aby prawdopodobieństwo znalezienia w niej osoby urodzonej tego samego dnia co eksperymentator było równe co najmniej 1/2?

Okazuje się, że potrzeba aż 253 osób. Przy ogólniejszym założeniu, że w roku jest ${\displaystyle n}$ dni, odpowiedź na powyższe pytanie jest równa w przybliżeniu^[1]

${\displaystyle n\ln {2}=0{,}693147\ldots \cdot n}$.

Związek z kryptografią

 Zobacz też: Atak urodzinowy.

Ta sekcja od 2024-05 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w sekcji mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tej sekcji. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tej sekcji.

Paradoks dni urodzin ma znaczenie w kryptografii i jest podstawą działania tzw. ataku urodzinowego. Niech dana będzie funkcja skrótu ${\displaystyle H,}$ która zwraca kod o ${\displaystyle m}$ bitach, czyli daje ${\displaystyle 2^{m}}$ możliwych odpowiedzi (jest to moc jej przeciwdziedziny). Jej jakość można ocenić, badając jej jądro, a więc jej kolizje (kolizję tworzą każde dwie znane wiadomości ${\displaystyle w_{1}}$ i ${\displaystyle w_{2},}$ o których wiadomo, że ${\displaystyle H(w_{1})=H(w_{2})}$).

Każdy kwantyl rozkładu liczby prób ${\displaystyle n}$ potrzebnych do znalezienia kolizji wśród ${\displaystyle k=2^{m}}$ kodów, spełnia zależność (5), gdzie ${\displaystyle 1-p}$ to rząd kwantyla. Średni czas łamania funkcji skrótu (tj. znalezienia kolizji) rośnie więc w przybliżeniu proporcjonalnie do pierwiastka liczby wszystkich możliwych odpowiedzi tej funkcji.

Przypisy