Paradoks dnia urodzin

Paradoks dnia urodzin – paradoks powstający przy rozwiązaniu następującego problemu:

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

Ile minimalnie osób należy wybrać, żeby prawdopodobieństwo znalezienia wśród nich co najmniej dwóch osób obchodzących urodziny tego samego dnia było większe od 0,5.

Rozwiązaniem problemu jest liczba 23. Ta zaskakująco mała liczba osób jest przyczyną określenia „Paradoks dnia urodzin”.

Rozwiązanie nie uwzględnia 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 nieistotnych dla rozwiązania) zjawisk nie zmienia znacząco podanego wyniku.

Analiza problemu

Prawdopodobieństwo tego, że po losowym przyporządkowaniu każdemu z $n$ obiektów jednej z $k\geqslant n$ etykietek każda etykietka będzie inna, wynosi:

${\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=0}^{n-1}\left(1-{\frac {i}{k}}\right),$

(1)

dodatkowo

${\bar {p}}(n,k)=0,\quad {\text{dla }}n>k.$

Stąd prawdopodobieństwo tego, że istnieją co najmniej dwa obiekty spośród $n$ mające tę samą etykietkę, wynosi:

$p(n,k)=1-{\bar {p}}(n,k).$

Dla ustalonego $k>0$ tak zdefiniowana funkcja $p(n,k)$ ma własności:

• $p(1,k)=0,$
• jest ściśle rosnąca dla $n=1,\dots ,k+1,$
• $p(n,k)=1,\quad {\text{dla }}n\geqslant k+1$ (są to zdarzenia pewne, patrz zasada szufladkowa Dirichleta).

Przedmiotem problemu jest ustalenie dla danego $k=365$ najmniejszej liczby $n,$ dla której zachodzi:

$p(n,k)>{\tfrac {1}{2}}.$

(2)

Oczywiście nierówności

$p(n,k)>{\tfrac {1}{2}},\quad {\bar {p}}(n,k)<{\tfrac {1}{2}}$

są równoważne.

Rozwiązanie

Aby rozwiązać problem dla $k=365,$ wystarczy, korzystając ze wzoru (1), bezpośrednio obliczyć:

$p(22,365)=0{,}475695<{\tfrac {1}{2}},$

$p(23,365)=0{,}507297>{\tfrac {1}{2}}.$

Ponieważ $p(n,365)$ jest niemalejąca, więc

$p(n,365)<{\tfrac {1}{2}}\quad {\text{dla }}n\leqslant 22,$

$p(n,365)>{\tfrac {1}{2}}\quad {\text{dla }}n\geqslant 23.$

Oznacza to, że $23$ spełnia warunki postawione w zadaniu i że jest to najmniejsza liczba o tej własności

Metoda analityczna

Rozwiązanie problemu polegało między innymi na wykazaniu, że wszystkie liczby naturalne od $23$ począwszy są rozwiązaniami problemu. Ustalenie tej liczby można także przeprowadzić metodą analityczną. Wprawdzie metoda ta nie wykazuje, że $23$ jest najmniejszą liczbą o tej własności, ale pozwala podejść do problemu znacznie ogólniej.

Funkcję ${\bar {p}}(n,k)$ można oszacować od góry następująco:

${\bar {p}}(n,k)=\prod _{i=0}^{n-1}\left(1-{\frac {i}{k}}\right)\quad \leqslant \quad \prod _{i=0}^{n-1}\left(e^{-i/k}\right)=e^{\frac {-n(n-1)}{2k}},$

wykorzystano tu nierówność $1-x\leqslant e^{-x}$ prawdziwą dla każdej liczby rzeczywistej $x.$

Aby ustalić, dla jakich $n$ zachodzi ${\bar {p}}(n,k)<{\tfrac {1}{2}}$ wystarczy ustalić, dla jakich $n$ zachodzi nierówność

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

która jest równoważna nierówności kwadratowej zmiennej $n{:}$

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

Rozwiązując ją dla $n>0,$ otrzymuje się warunek wystarczający na ${\bar {p}}(n,k)<{\tfrac {1}{2}}{:}$

$n>{\frac {1+{\sqrt {1-8k\cdot \ln {\tfrac {1}{2}}}}}{2}}.$

Podstawienie $k=365$ daje

$n>22{,}99994,$

skąd statystycznie wystarczą 23 osoby.

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

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

(5)

Dlatego 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. 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.