Paradoks dni urodzin

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

Prawdopodobieństwo, że dwie spośród $n$ osób obchodzą urodziny tego samego dnia.

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 $\{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.

Według Iana Stewarta, kiedy grupa badaczy zadała to pytanie studentom, mediana udzielonych odpowiedzi wyniosła 385. 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, co uzasadnia użycie terminu „paradoks”.

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

Rozwiązanie problemu

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

$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 $k,$ że $p_{k}\leq 1/2.$ Ponieważ ciąg $(p_{k})$ jest nierosnący (co nietrudno zauważyć), wystarczy bezpośrednio obliczyć przy pomocy komputera, że

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

by dojść do prawidłowej odpowiedzi.

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 $x$ prawdziwa jest nierówność

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

przy czym $e$ jest podstawą logarytmu naturalnego. Zatem

$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 $1/2,$ musi zachodzić

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

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

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

co jest oczywiście mniejsze od 23.

Uogólnienia i powiązane problemy

Inna liczba dni w roku

Przy założeniu, że rok ma $n$ dni, rozwiązanie problemu dni urodzin równe jest w przybliżeniu

${\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:

Problem dni urodzin na różnych planetach

Nazwa planety	Czas obiegu wokół Słońca (zaokrąglony)	Minimalna liczność grupy osób
Merkury	88 dni	12
Wenus	225 dni	18
Ziemia	365 dni	23
Mars	687 dni	32
Jowisz	4 333 dni	78
Saturn	10 756 dni	123
Uran	30 708 dni	207
Neptun	60 223 dni	290

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:

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 $n$ dni, odpowiedź na powyższe pytanie jest równa w przybliżeniu

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

Związek z kryptografią

Paradoks dni urodzin ma znaczenie w kryptografii i jest podstawą działania tzw. ataku urodzinowego. Niech dana będzie funkcja skrótu $H,$ która zwraca kod o $m$ bitach, czyli daje $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 $w_{1}$ i $w_{2},$ o których wiadomo, że $H(w_{1})=H(w_{2})$).

Każdy kwantyl rozkładu liczby prób $n$ potrzebnych do znalezienia kolizji wśród $k=2^{m}$ kodów, spełnia zależność (5), gdzie $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.