Paradoks urodzin

Q: Dlaczego 23, skoro dni jest 365?

Bo liczy się liczba par, a nie osób. W grupie 23 osób jest ich 253 - i każda para to osobna szansa na wspólne urodziny.

Q: Ile osób potrzeba, żeby ktoś miał urodziny tego samego dnia co ja?

Około 253. To zupełnie inne pytanie: tu jedna konkretna data zamiast dowolnej pary. Prawdopodobieństwo wynosi 1 - (364/365)^n i przekracza 50\% dopiero przy n = 253.

Q: Czy nierównomierny rozkład urodzin psuje wynik?

Nie, wręcz przeciwnie - każde odstępstwo od równomierności zwiększa szansę na powtórkę. Założenie o równych prawdopodobieństwach daje więc oszacowanie najostrożniejsze.

W grupie $n$ osób prawdopodobieństwo, że co najmniej dwie obchodzą urodziny tego samego dnia, wynosi

$P(n) = 1 - \frac{365}{365} \cdot \frac{364}{365} \cdot \ldots \cdot \frac{365 - n + 1}{365}.$

Już dla $n = 23$ mamy $P(23) \approx 50{,}7\%$ , a dla $n = 57$ ponad $99\%$ .

Na czym polega paradoks

To nie jest paradoks w sensie sprzeczności - to zderzenie poprawnego rachunku z zawodną intuicją. Zapytany „ile osób potrzeba, by szanse na wspólne urodziny przekroczyły połowę?”, człowiek zwykle odpowiada „około $180$ ” - bo dni w roku jest $365$ , więc połowa to jakieś $180$ .

Prawidłowa odpowiedź brzmi: $23$ osoby. W typowej klasie szkolnej dwie osoby obchodzą urodziny tego samego dnia częściej niż nie.

Skąd bierze się błąd intuicji

Intuicja podpowiada odpowiedź na inne pytanie: „ile osób potrzeba, żeby ktoś miał urodziny tego samego dnia co ja?”. To rzeczywiście wymaga wielkiej grupy - około $253$ osób.

Tymczasem paradoks urodzin pyta o dowolną parę. A par jest zdecydowanie więcej niż osób:

$\binom{23}{2} = \frac{23 \cdot 22}{2} = 253.$

W grupie $23$ osób jest $253$ par - i każda z nich to osobna szansa na trafienie. Ta liczba rośnie kwadratowo: podwojenie grupy czterokrotnie zwiększa liczbę par.

Dowód

Pokaż dowódUkryj dowód

Liczymy zdarzenie przeciwne: wszyscy mają urodziny w różne dni. Zakładamy, że każdy z $365$ dni jest jednakowo prawdopodobny i pomijamy $29$ lutego.

Krok 1. Pierwsza osoba może mieć urodziny kiedykolwiek - $365$ możliwości na $365$ , czyli prawdopodobieństwo $1$ .

Krok 2. Druga osoba musi trafić w jeden z pozostałych $364$ dni:

$\frac{364}{365}.$

Krok 3. Trzecia osoba ma do dyspozycji $363$ dni, i tak dalej. Dla $n$ -tej osoby zostaje $365 - n + 1$ dni.

Krok 4. Mnożymy prawdopodobieństwa (kolejne osoby są niezależne):

$P'(n) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \ldots \cdot \frac{365 - n + 1}{365}.$

Krok 5. Przechodzimy do zdarzenia przeciwnego.

$P(n) = 1 - P'(n) = 1 - \frac{365!}{365^n \, (365 - n)!}.$

Krok 6. Podstawiamy $n = 23$ . Iloczyn dwudziestu dwóch ułamków daje

$P'(23) \approx 0{,}4927 \quad\Longrightarrow\quad P(23) \approx 0{,}5073 = 50{,}7\%. \qquad \blacksquare$

Ile osób dla jakiej pewności

$10$ osób - około $11{,}7\%$ ;
$20$ osób - około $41{,}1\%$ ;
$23$ osoby - około $50{,}7\%$ (pierwsza liczba przekraczająca połowę);
$30$ osób - około $70{,}6\%$ ;
$40$ osób - około $89{,}1\%$ ;
$50$ osób - około $97{,}0\%$ ;
$57$ osób - około $99{,}0\%$ ;
$70$ osób - około $99{,}9\%$ ;
$366$ osób - dokładnie $100\%$ (zasada szufladkowa!).

Ostatni wiersz to nasz stary znajomy: przy $366$ osobach i $365$ dniach zasada szufladkowa gwarantuje powtórkę bez żadnego rachunku prawdopodobieństwa.

Wygodne przybliżenie

Dla dużych $n$ i wielu „szuflad” $d$ (u nas $d = 365$ ) zachodzi przybliżenie

$P(n) \approx 1 - e^{-n^2 / (2d)}.$

Dla $n = 23$ daje ono $1 - e^{-0{,}7247} \approx 0{,}516$ - bardzo blisko dokładnych $0{,}507$ . Ze wzoru widać też, skąd bierze się „pierwiastkowa” reguła: żeby prawdopodobieństwo kolizji sięgnęło mniej więcej połowy, wystarczy

$n \approx 1{,}18 \sqrt{d}.$

Dla $d = 365$ daje to $n \approx 22{,}5$ - czyli nasze $23$ osoby.

Po co to komu - atak urodzinowy

Ta sama matematyka rządzi bezpieczeństwem funkcji skrótu (hashy). Jeśli funkcja zwraca skróty $b$ -bitowe, to możliwych wyników jest $d = 2^b$ . Z reguły pierwiastkowej wynika, że kolizję - dwie różne wiadomości o tym samym skrócie - znajdzie się już po około

$\sqrt{2^b} = 2^{b/2}$

próbach, a nie po $2^b$ , jak podpowiadałaby intuicja. To tak zwany atak urodzinowy.

Praktyczny wniosek: skrót $128$ -bitowy (np. MD5) daje realne bezpieczeństwo na poziomie $2^{64}$ , a to dziś za mało. Dlatego standardem jest SHA-256 - $256$ bitów, czyli $2^{128}$ operacji do znalezienia kolizji.

Paradoks urodzin bywa też narzędziem w informatyce: algorytm rho Pollarda do rozkładu liczb na czynniki celowo szuka „urodzinowej” kolizji reszt.

Kto i kiedy

Obliczenie przypisuje się zwykle Richardowi von Misesowi (lata 30. XX wieku), a szeroko spopularyzował je William Feller w klasycznym podręczniku rachunku prawdopodobieństwa. Nazwa „paradoks” przyjęła się właśnie dlatego, że wynik tak mocno kłóci się z przeczuciem.

Sprawdzenie doświadczalne bywa efektowne: w piłkarskich mistrzostwach świata drużyny liczą po $23$ zawodników - i rzeczywiście w mniej więcej połowie kadr znajdują się dwaj piłkarze z tą samą datą urodzin.

Najczęstsze pytania

Dlaczego $23$ , skoro dni jest $365$ ? Bo liczy się liczba par, a nie osób. W grupie $23$ osób jest ich $253$ - i każda para to osobna szansa na wspólne urodziny.

Ile osób potrzeba, żeby ktoś miał urodziny tego samego dnia co ja? Około $253$ . To zupełnie inne pytanie: tu jedna konkretna data zamiast dowolnej pary. Prawdopodobieństwo wynosi $1 - (364/365)^n$ i przekracza $50\%$ dopiero przy $n = 253$ .

Czy nierównomierny rozkład urodzin psuje wynik? Nie, wręcz przeciwnie - każde odstępstwo od równomierności zwiększa szansę na powtórkę. Założenie o równych prawdopodobieństwach daje więc oszacowanie najostrożniejsze.

A co z 29 lutego? Uwzględnienie roku przestępnego zmienia wynik nieznacznie (o ułamek punktu procentowego), bo ten dzień pojawia się cztery razy rzadziej niż pozostałe.

Czy to naprawdę paradoks? Nie w sensie logicznym - nic tu nie jest sprzeczne. To „paradoks” psychologiczny: intuicja myli pytanie o dowolną parę z pytaniem o konkretną osobę.

Podsumowanie

W grupie $23$ osób szansa na wspólne urodziny przekracza $50\%$ , a przy $57$ osobach - $99\%$ .
Rachunek prowadzimy przez zdarzenie przeciwne: $P(n) = 1 - \tfrac{365!}{365^n (365-n)!}$ .
Źródłem złej intuicji jest liczba par (rosnąca kwadratowo), a nie liczba osób.
Reguła pierwiastkowa: przy $d$ możliwościach kolizja pojawia się już po około $\sqrt{d}$ próbach.
Stąd atak urodzinowy na funkcje skrótu - powód, dla którego $128$ -bitowe skróty uznano za zbyt słabe.