Otwórz menu główne
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 problemuEdytuj

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ą 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ązanieEdytuj

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 analitycznaEdytuj

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 kryptografiiEdytuj

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.