Paradoks dnia urodzin

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Prawdopodobieństwo, że dwie osoby w grupie n ludzi będą miały urodziny tego samego dnia w roku

Paradoks dnia urodzinparadoks 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[edytuj | edytuj kod]

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

  dla

Stąd prawdopodobieństwo tego, że istnieją 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
  • 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[edytuj | edytuj kod]

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

Ponieważ jest niemalejąca, więc

dla
dla

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

Metoda analityczna[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.