Paradoks dnia urodzin

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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 i rodzeństw bliźniaczych, 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]

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

(1)

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

(2)

czyli

(3)

Metoda numeryczna[edytuj]

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

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

Metoda analityczna[edytuj]

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

(4)

Wystarczy w tym celu znaleźć minimum funkcji

Podstawiając do wzoru (4) , uzyskujemy:

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

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

co prowadzi do warunku:

czyli

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

Po podstawieniu uzyskujemy:

Stąd statystycznie wystarczą 23 osoby.

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

(5)

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

Zastosowanie w kryptografii[edytuj]

Paradoks dnia urodzin ma znaczenie w kryptografii i jest podstawą działania tzw. ataku urodzinowego. Załóżmy, że badamy funkcję haszującą , która zwraca kod o bitach, czyli daje możliwych odpowiedzi. Szukamy kolizji, czyli dwóch takich wiadomości i , że . Każdy kwantyl rozkładu liczby prób potrzebnych do znalezienia kolizji wśród kodów, spełnia zależność (5), gdzie 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.