Paradoks dnia urodzin - Nauka

Paradoks dnia urodzin

Z Wikipedii

Skocz do: nawigacji, szukaj
Prawdopodobieństwo, że dwie osoby w grupie n ludzi będą miały tę samą datę urodzenia

Pytanie stawiane w paradoksie dnia urodzin brzmi: Ile osób należy wybrać, żeby prawdopodobieństwo, że co najmniej dwie z nich mają urodziny tego samego dnia w roku, było większe od 0,5.

Odpowiedzią jest zaskakująco niskie 23. Wynik ten został obliczony bez uwzględniania osób urodzonych 29 lutego, bliźniaków, które zaburzają statystyczną niezależność dat urodzeń oraz sezonowości rocznej w urodzeniach. Uwzględnienie tych (stosunkowo drobnych) poprawek nie zmieniłoby jednak rzędu wielkości odpowiedzi.

Spis treści

[edytuj] Wyprowadzenie

Jeśli losowo przyporządkujemy każdemu z n obiektów jedną z k etykietek, to prawdopodobieństwo, że każda etykietka będzie inna, wyniesie:

\bar p(n,k) = 1 \cdot \left(1-\frac{1}{k}\right) \cdot \left(1-\frac{2}{k}\right) \cdots \left(1-\frac{n-1}{k}\right)=
=\prod_{i=1}^{n-1}\left(1-{i \over k}\right) (1)


Jeśli chcemy obliczyć dla jakiego n prawdopodobieństwo tego, że przynajmniej dwa obiekty będą miały tę samą etykietkę przekroczy 50%, wystarczy sprawdzić, kiedy:

1-\bar p(n,k)> \frac{1}{2}

czyli

\bar p(n,k)< \frac{1}{2} (2)


[edytuj] Metoda numeryczna

Najprostszą metodą sprawdzenia, że 23 osoby są wystarczające, a 22 nie, jest po prostu numeryczne wyliczenie z powyższych wzorów:

\bar p(23,365)=0.492703
\bar p(22,365)=0.524305

Metoda ta nie pozwala jednak zaobserwować ogólnej zależności.

[edytuj] Metoda analityczna

Można udowodnić, że dla każdego rzeczywistego x:

e^x \ge 1+x\;

Wystarczy w tym celu znaleźć minimum funkcji f(x) = ex − (1 + x)

Podstawiając do powyższego wzoru x=-\tfrac{i}{k} uzyskujemy:

e^{-i/k}\ge 1-\frac{i}{k}

Teraz możemy podać górne oszacowanie wielkości (1):

\bar p(n,k) = \prod_{i=1}^{n-1}\left(1-{i \over k}\right) \le \prod_{i=1}^{n-1}\left(e^{-i/k}\right) = e^{\frac{-n(n-1)}{2k}}

Nierówność (2) będzie tym bardziej spełniona, gdy będzie spełniona nierówność z górnym oszacowaniem podstawionym zamiast \bar p(n,k):

e^{\frac{-n(n-1)}{2k}} < \frac{1}{2}

co prowadzi do warunku:

\frac{-n(n-1)}{2k}<\operatorname{ln} \frac{1}{2}

czyli

n(n-1)>2k\cdot\operatorname{ln}2

Rozwiązując tę nierówność kwadratową dla n > 0 uzyskujemy górne oszacowanie minimalnej wartości n:

n>\frac{1+\sqrt{1+8k\cdot \operatorname{ln}2}}{2}

Po podstawieniu k = 365 uzyskujemy:

n>22,99994\

Stąd na pewno wystarczą 23 osoby.

[edytuj] Zastosowanie w kryptografii

Paradoks dnia urodzin ma znaczenie w kryptografii i jest podstawą działania tzw. ataku urodzinowego; np. jeśli funkcje haszujące zwracają 2k możliwych odpowiedzi, to znalezienie kolizji, czyli dwóch takich wiadomości m1 i m2, że H(m1) = H(m2) wymaga sprawdzenia stosunkowo niewielkiej liczby kombinacji (c2k / 2, gdzie c jest stałą).






Kobaltowe, przenośne dyski twarde
Buffalo dodaje do swojej oferty serię kieszonkowych dysków twardych o pojemności od 160 do 500 GB, które posiadają porty USB 2.0 oraz odporne na wstrząsy stylowe obudowy.
CES 2009: Bezprzewodowy telewizor Full HD o przekątnej 55 cali
LG LHX to bezprzewodowy, płaski telewizor LCD z podświetleniem diodami LED o przekątnej ekranu 55 cali, który oferuje dynamiczny kontrast na poziomie 2 000 000:1.
CES 2009: Seria odtwarzaczy Network Blu-Ray od LG
LG zaprezentuje na tegorocznych targach nową serię odtwarzaczy Blu-Ray, złożoną z dwóch modeli - BD370 i BD390 - a także trzy nowe systemy kina domowego, oparte na technologii Blu-Ray.
Pierwszy notebook z 512-gigabajtową stacją SSD
Asus przedstawia pierwszy na świecie notebook, wyposażony w stację SSD o pojemności 512 GB. W wyposażeniu znajdziemy również procesor Atom oraz do 2 GB pamięci RAM.
Zielone, 100-gigabajtowe stacje SSD Samsunga
Samsung przedstawia bardzo szybkie, energooszczędne 2,5-calowe stacje SSD o pojemności 100 GB, które oparto na układach SLC NAND. Urządzenia pobierają zaledwie 1,9 W mocy.

sprawdz strone 906 no host niezarejestrowana strona 906