thumb|300px|Prawdopodobieństwo, że dwie spośród osób obchodzą urodziny tego samego dnia. Paradoks dni urodzin, paradoks urodzin – paradoks związany z rozwiązaniem poniższego zadania z rachunku prawdopodobieństwa: Jak liczna musi być grupa osób, aby prawdopodobieństwo znalezienia w niej dwóch osób obchodzących urodziny tego samego dnia było równe co najmniej ?
Zakłada się zwykle, że dni urodzin to liczby wybrane z rozkładem jednostajnym ze zbioru co nie odbiega znacząco od rzeczywistości. W szczególności w rozwiązaniu problemu nie uwzględnia się lat przestępnych.
Według Iana Stewarta, kiedy grupa badaczy zadała to pytanie studentom, mediana udzielonych odpowiedzi wyniosła . Tymczasem już przy osobach zasada szufladkowa Dirichleta gwarantuje, że pewne dwie z nich urodziły się tego samego dnia w roku. Poprawną odpowiedzią jest jednak zaskakująco niewielka liczba osób, co uzasadnia użycie terminu „paradoks”.
Autorstwo problemu przypisuje się Haroldowi Davenportowi, który miał wymyślić go około 1927 roku. Davenport wyrzeka się jednak autorstwa.
Rozwiązanie problemu Zauważmy na samym początku, że prawdopodobieństwo zdarzenia przeciwnego do zdarzenia rozpatrywanego w głównym pytaniu naszego paradoksu – a powiedzmy, że zdarzeniem przeciwnym jest w istocie następujące zdarzenie: każda z osób z rzeczonej grupy, ma swoje własne urodziny w inny dzień – jest, przy liczbie osób równej dokładnie ; równe właściwie:
Wyrażenie ułamkowe, występujące po pierwszym znaku równości w ciągu równości powyżej, wyraża następujące dwie obserwacje: (licznik – interesujące nas zdarzenie przeciwne) jedna z osób może mieć urodziny w każdy z dni; ale wtedy już jakaś kolejna osoba, może mieć urodziny tylko w któryś z odpowiednich dni (ponieważ należy wyłączyć z możliwości dla niej odpowiedni pojedynczy dzień, w który urodziny ma pierwsza rozważana przez nas osoba); (mianownik – wszystkie zdarzenia elementarne) w ogólności, każda z osób z grupy, może mieć urodziny w dowolny z dni roku; których to dni przyjmujemy (w ramach rzeczonego problemu), że jest .
Dalej, rozwiązanie problemu równoważne jest ze znalezieniem najmniejszego takiego że . Ponieważ ciąg jest nierosnący (co nietrudno zauważyć), wystarczy bezpośrednio obliczyć przy pomocy komputera, że
by dojść do prawidłowej odpowiedzi.
Aby wykazać, że wystarczą osoby (choć już bez dowodu, że jest to najmniejsza taka liczba), można posłużyć się pewnymi przybliżeniami. Dla każdej liczby rzeczywistej prawdziwa jest nierówność
przy czym jest podstawą logarytmu naturalnego. Zatem
Aby prawa strona powyższej nierówności była nie większa od , musi zachodzić:
Najmniejszym dodatnim rozwiązaniem tej nierówności jest
co jest oczywiście mniejsze od liczby .
Uogólnienia i powiązane problemy
Inna liczba dni w roku Przy założeniu, że rok ma dni, rozwiązanie problemu dni urodzin równe jest w przybliżeniu
Dla przykładu można rozważyć wspomniany problem dla osób urodzonych na innych planetach Układu Słonecznego: +Problem dni urodzin na różnych planetachNazwa planetyCzas obiegu wokół Słońca (zaokrąglony)Minimalna liczność grupy osóbMerkury88 dni12Wenus225 dni18Ziemia365 dni23Mars687 dni32Jowisz4 333 dni78Saturn10 756 dni123Uran30 708 dni207Neptun60 223 dni290
Ustalony dzień urodzin Problem dni urodzin można zmodyfikować, przyjmując, że przed wykonaniem doświadczenia została wybrana pewna data. Dla ustalenia uwagi, niech będzie to data urodzin przeprowadzającego eksperyment. Należy wówczas znaleźć odpowiedź na pytanie:
Jak liczna musi być grupa osób, aby prawdopodobieństwo znalezienia w niej osoby urodzonej tego samego dnia co eksperymentator było równe co najmniej ?
Okazuje się, że potrzeba aż osób. Przy ogólniejszym założeniu, że w roku jest dni, odpowiedź na powyższe pytanie jest równa w przybliżeniu:
Związek z kryptografią
Paradoks dni 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ść , gdzie to rząd kwantylu. Ś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.
Uwagi
Przypisy
Linki zewnętrzne Tajemnica dnia urodzin, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 10 października 2017 [dostęp 2024-09-04].
Kategoria:Kryptologia Kategoria:Paradoksy probabilistyczne