Paradoks urodzinowy

Co się właśnie stało?

W grupie 10 osób prawdopodobieństwo, że co najmniej dwie mają urodziny tego samego dnia, wynosi 11.7%. Intuicja większości ludzi podpowiada, że potrzeba połowy z 365 dni — czyli ok. 183 osób — żeby przekroczyć 50%. To błąd: wystarczy już 23 osoby.

Zdarzenie przeciwne — klucz do obliczeń:

Łatwiej policzyć prawdopodobieństwo, że wszyscy mają różne urodziny, i odjąć je od 1:

co jest równoważne iloczynowi malejących ułamków:

Dlaczego to działa? (niezmiennik)

P(n) rośnie monotonicznie wraz z n i dąży do 100%. Sekret nie leży w pojedynczych osobach względem jednej ustalonej daty — liczy się każda możliwa para osób. Przy n osobach istnieje $n(n-1)/2$ par: przy n=23 to już 253 pary, każda z niewielką szansą 1/365 na zbieżność dat, ale sumarycznie dającą ponad 50%. Przy n=70 prawdopodobieństwo przekracza już 99,9%.

Historia paradoksu

Problem opublikował po raz pierwszy Richard von Mises w 1939 roku — był on prawdopodobnie znany nieformalnie już wcześniej, np. Haroldowi Davenportowi ok. 1927 r., ale to von Mises jako pierwszy przedstawił go w druku. Dziś to klasyczny przykład tego, jak intuicja zawodzi w rachunku prawdopodobieństwa — wykorzystywany też do ilustracji „kolizji” w informatyce, np. w funkcjach skrótu (hashowania).

Po co Ci to na maturze:

Zdarzenie przeciwne to jedna z najużyteczniejszych sztuczek w kombinatoryce i prawdopodobieństwie — gdy „co najmniej jedno/dwa” trudno policzyć wprost, policz „żadne” i odejmij od 1. Chwyt: zawsze sprawdź, czy liczysz pojedyncze elementy, czy pary/kombinacje — to one najczęściej „napędzają” zaskakująco wysokie wyniki.

Zapamiętaj: już 23 osoby wystarczą, by szansa wspólnych urodzin przekroczyła 50% — bo liczy się liczba par, nie liczba osób. P = 1 − 365!/(365ⁿ·(365−n)!).