Paradoks dnia urodzin

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.