Paradoks dnia urodzin

Paradoks

Zapytaj ludzi, ilu gości musi przyjść na przyjęcie, żeby dwoje z nich prawdopodobnie miało urodziny tego samego dnia, a większość odpowie, że około 180, czyli połowa z 365. Prawidłowa odpowiedź to 23: wtedy szansa wynosi 50,7%. Przy 57 gościach to 99%. Nazywa się to paradoksem nie dlatego, że zawiera sprzeczność, ale dlatego, że tak mocno kłóci się z naszą intuicją.

Dlaczego intuicja zawodzi

W pokoju nieświadomie rozumujemy z własnej perspektywy: jaka jest szansa, że ktoś ma urodziny tego samego dnia co ja? Przy 365 dniach ta szansa jest mała. Paradoks dotyczy jednak wszystkich możliwych par w pokoju, a nie zgodności z jedną konkretną osobą: A i B, B i C, A i C i tak dalej. Z 23 osób można utworzyć 253 różne pary i w każdej z nich może trafić się wspólny dzień urodzin.

Liczba par rośnie z kwadratem

n osób tworzy n × (n − 1) / 2 par: 10 osób tworzy 45 par, 23 osoby – 253, 57 osób – 1596, a 100 osób – 4950. Każda para ma wspólny dzień urodzin z prawdopodobieństwem 1/365, więc 253 pary dają średnio 253/365 ≈ 0,69 pary z tym samym dniem urodzin. Podwojenie grupy mniej więcej czterokrotnie zwiększa liczbę par i dlatego szansa na wspólny dzień urodzin tak gwałtownie rośnie.

Obliczenia krok po kroku

Najłatwiej obliczyć szansę, że nikt nie ma wspólnego dnia urodzin, i odjąć ją od 100%. Pierwsza osoba zajmuje dowolny dzień. Druga ma szansę 364/365, że nie ma urodzin tego samego dnia. Trzecia ma szansę 363/365, że różni się od dwóch pierwszych, i tak dalej. Dla 23 osób:

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3%

Skoro szansa, że wszyscy mają urodziny w różne dni, wynosi 49,3%, to zdarzenie przeciwne, czyli co najmniej jeden wspólny dzień urodzin, ma prawdopodobieństwo 100% − 49,3% = 50,7%.

Ktoś z twoim dniem urodzin

Szansa, że ktoś ma urodziny tego samego dnia co ty, to inne pytanie. Każda z pozostałych n − 1 osób omija twój dzień urodzin z prawdopodobieństwem 364/365, więc szansa, że ktoś go ma, wynosi 1 − (364/365)ⁿ⁻¹. Przy 23 osobach to tylko 5,9%, a żeby przekroczyć 50%, potrzeba 253 innych osób. Spośród 253 par w grupie 23 osób tylko 22 obejmują ciebie.

Reguła pierwiastka kwadratowego i ataki urodzinowe

Przy N jednakowo prawdopodobnych wartościach powtórzenie staje się prawdopodobne po około 1,2 × √N losowaniach: √365 ≈ 19, a 1,2 × 19 ≈ 23. Ma to duże znaczenie w bezpieczeństwie komputerowym. Atakujący używają ataków urodzinowych, aby znaleźć dwie wiadomości o tym samym skrócie kryptograficznym, czyli kolizję, na przykład po to, by podrobić podpis cyfrowy. Dzięki paradoksowi dnia urodzin potrzebują znacznie mniej prób, niż podpowiada intuicja: około 2⁶⁴ dla 128-bitowej funkcji skrótu zamiast 2¹²⁸. Dlatego nowoczesne funkcje skrótu, takie jak SHA-256, dają długie wyniki.

Poznaj to w PictorX

Otwórz Paradoks dnia urodzin, a na okręgu utworzy się grupa 23 osób, jedna osoba po drugiej. Każdy przybysz dodaje linię do każdej osoby, która już tam jest, a podpis liczy pary. Ich urodziny spadają na kalendarz, a dzień z dwiema lub więcej osobami się podświetla. Poniżej obliczenia dla danej wielkości grupy stoją obok odsetka przetestowanych grup, w których wystąpił wspólny dzień urodzin, a wykres pokazuje szansę dla każdej wielkości grupy – dla dowolnych dwóch osób i dla kogoś z twoim dniem urodzin. Dodawaj osoby po jednej, wybierz od 2 do 366 osób, przetestuj do 100 000 grup w tempie do 10 000 na sekundę albo przetestuj wszystkie wielkości grup i patrz, jak punkty wyznaczają krzywą.