Paradoks dnia urodzin

Prawdopodobieństwo, że dwie osoby w grupie n ludzi będą miały urodziny tego samego dnia w roku

Pytanie stawiane w paradoksie dnia urodzin brzmi: Ile osób należy wybrać, żeby prawdopodobieństwo, że co najmniej dwie z nich mają urodziny tego samego dnia w roku, było większe od 0,5.

Odpowiedź to: 23. W obliczeniach nie uwzględniono osób urodzonych 29 lutego, bliźniaków, które zaburzają statystyczną niezależność dat urodzeń oraz sezonowości rocznej urodzin. Uwzględnienie tych (stosunkowo drobnych) poprawek nie zmieniłoby jednak znacząco odpowiedzi.

Wyprowadzenie

Jeśli losowo przyporządkujemy każdemu z n obiektów jedną z k etykietek, to prawdopodobieństwo, że każda etykietka będzie inna, wyniesie:

$\bar p(n,k) = 1 \cdot \left(1-\frac{1}{k}\right) \cdot \left(1-\frac{2}{k}\right) \cdots \left(1-\frac{n-1}{k}\right)=$

$=\prod_{i=1}^{n-1}\left(1-{i \over k}\right)$

(1)

Jeśli chcemy obliczyć dla jakiego n prawdopodobieństwo tego, że przynajmniej dwa obiekty będą miały tę samą etykietkę przekroczy 50%, wystarczy sprawdzić, kiedy:

$1-\bar p(n,k)> \frac{1}{2}$

(2)

czyli

$\bar p(n,k)< \frac{1}{2}$

(3)

Metoda numeryczna

Najprostszą metodą sprawdzenia, że 23 osoby są wystarczające, a 22 nie, jest bezpośredni rachunek, prowadzący do równości:

$\bar p(23,365)=0.492703$

$\bar p(22,365)=0.524305$

Metoda ta nie pozwala jednak zaobserwować ogólnej zależności.

Metoda analityczna

Można udowodnić, że dla każdego rzeczywistego x:

$e^x \geqslant 1+x\;$

(4)

(wystarczy w tym celu znaleźć minimum funkcji f(x) = e^x − (1 + x))

Podstawiając do wzoru (4) $x=-\tfrac{i}{k}$ uzyskujemy:

$e^{-i/k}\geqslant 1-\frac{i}{k}$

Teraz możemy podać górne oszacowanie wielkości (1):

$\bar p(n,k) = \prod_{i=1}^{n-1}\left(1-{i \over k}\right) \leqslant \prod_{i=1}^{n-1}\left(e^{-i/k}\right) = e^{\frac{-n(n-1)}{2k}}$

Nierówność (3) będzie tym bardziej spełniona, gdy będzie spełniona nierówność z górnym oszacowaniem podstawionym zamiast $\bar p(n,k)$, więc następujący warunek jest wystarczający:

$e^{\frac{-n(n-1)}{2k}} < \frac{1}{2}$

co prowadzi do warunku:

$\frac{-n(n-1)}{2k}<\operatorname{ln} \frac{1}{2}$

czyli

$n(n-1)>2k\cdot\operatorname{ln}2$

Rozwiązując tę nierówność kwadratową dla n > 0 uzyskujemy warunek wystarczający na n:

$n>\frac{1+\sqrt{1+8k\cdot \operatorname{ln}2}}{2}$

Po podstawieniu $k=365\;$ uzyskujemy:

$n>22,99994\$

Stąd statystycznie wystarczą 23 osoby.

Ogólnie dla zadanego minimalnego prawdopodobieństwa $p\;$ z prawej strony nierówności (2) dostajemy:

$n>\frac{1+\sqrt{1-8k\cdot \operatorname{ln}(1-p)}}{2}$

(5)

Widać stąd, że potrzebna liczba obiektów n rośnie w przybliżeniu proporcjonalnie do pierwiastka liczby etykietek k.

Zastosowanie w kryptografii

Paradoks dnia urodzin ma znaczenie w kryptografii i jest podstawą działania tzw. ataku urodzinowego; Załóżmy że badamy funkcję haszującą $H\;$, która zwraca kod o $m\;$ bitach, czyli daje $2^m\;$ możliwych odpowiedzi. Szukamy kolizji, czyli dwóch takich wiadomości $w_1\;$ i $w_2\;$, ż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 haszującej rośnie więc w przybliżeniu proporcjonalnie do pierwiastka liczby wszystkich możliwych odpowiedzi tej funkcji.