Paradoks dnia urodzin

Z Wikipedii

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

1 Wyprowadzenie
- 1.1 Metoda numeryczna
- 1.2 Metoda analityczna
2 Zastosowanie w kryptografii

[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) = e x - (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ą $2 k$ możliwych odpowiedzi, to znalezienie kolizji, czyli dwóch takich wiadomości $m 1$ i $m 2$ , że $H (m 1) = H (m 2)$ wymaga sprawdzenia stosunkowo niewielkiej liczby kombinacji ( $c 2 k / 2$ , gdzie c jest stałą).

Paradoks dnia urodzin

Z Wikipedii

Spis treści

[edytuj] Wyprowadzenie

[edytuj] Metoda numeryczna

[edytuj] Metoda analityczna

[edytuj] Zastosowanie w kryptografii

osobiste

Szukaj

nawigacja

zmiany

dla edytorów

narzędzia

W innych językach