Paradoks dnia urodzin
Ten artykuł od 2020-06 wymaga zweryfikowania podanych informacji. |
Paradoks dnia urodzin – paradoks powstający przy rozwiązaniu następującego problemu:
- 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 obiektów jednej z etykietek każda etykietka będzie inna, wynosi:
(1) |
dodatkowo
Stąd prawdopodobieństwo tego, że istnieją co najmniej dwa obiekty spośród mające tę samą etykietkę, wynosi:
Dla ustalonego tak zdefiniowana funkcja ma własności:
- jest ściśle rosnąca dla
- (są to zdarzenia pewne, patrz zasada szufladkowa Dirichleta).
Przedmiotem problemu jest ustalenie dla danego najmniejszej liczby dla której zachodzi:
(2) |
Oczywiście nierówności
są równoważne.
Rozwiązanie
Aby rozwiązać problem dla wystarczy, korzystając ze wzoru (1), bezpośrednio obliczyć:
Ponieważ jest niemalejąca, więc
Oznacza to, że 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 począwszy są rozwiązaniami problemu. Ustalenie tej liczby można także przeprowadzić metodą analityczną. Wprawdzie metoda ta nie wykazuje, że jest najmniejszą liczbą o tej własności, ale pozwala podejść do problemu znacznie ogólniej.
Funkcję można oszacować od góry następująco:
wykorzystano tu nierówność prawdziwą dla każdej liczby rzeczywistej
Aby ustalić, dla jakich zachodzi wystarczy ustalić, dla jakich zachodzi nierówność
która jest równoważna nierówności kwadratowej zmiennej
Rozwiązując ją dla otrzymuje się warunek wystarczający na
Podstawienie daje
skąd statystycznie wystarczą 23 osoby.
Ogólnie dla zadanego minimalnego prawdopodobieństwa z prawej strony nierówności (2) jest
(5) |
Dlatego potrzebna liczba obiektów rośnie w przybliżeniu proporcjonalnie do pierwiastka liczby etykietek
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 która zwraca kod o bitach, czyli daje 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 i o których wiadomo, ż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 skrótu (tj. znalezienia kolizji) rośnie więc w przybliżeniu proporcjonalnie do pierwiastka liczby wszystkich możliwych odpowiedzi tej funkcji.
Media użyte na tej stronie
Paradoks dnia urodzin