Narozeninový problém

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V teorii pravděpodobnosti je narozeninovým problémem (či narozeninovým paradoxem) myšlena pravděpodobnost, že pro skupinu náhodně vybraných 23 (či více) lidí, je více než 50% pravděpodobnost, že nějací dva lidé budou mít narozeniny ve stejný den. Pro 57 a více lidí je ona pravděpodobnost více než 99%, postupně rostoucí až ke 100 % pro 366 lidí (za předpokladu že pracujeme s rokem o 365 dnech).[1] Matematika skrytá za tímto problémem vede k známému kryptografickému útoku zvanému narozeninový útok.

Pochopení problému[editovat | editovat zdroj]

Narozeninový problém se ptá, zdali „nějaký“ z 23 lidí má shodné datum narození jako „nějaký“ jiný, nikoliv nějaký konkrétní. Pokud v seznamu 23 lidí porovnáváme narozeniny první osoby s ostatními, máme 22 možností na úspěch z celkového počtu 365. Když však porovnáváme každého s každým, je těchto možností 253. To proto, že ve skupině 23 lidí je 23*22/2 = 253 dvojic.

Výpočet pravděpodobnosti[editovat | editovat zdroj]

Graf s křivkou přibližné pravděpodobnosti, že alespoň dva lidé sdílejí narozeniny v dané skupině lidí.

Pro výpočet pravděpodobnosti, že v místnosti s „n“ lidmi, alespoň dva mají narozeniny ve stejný den, budeme předpokládat rovnoměrné rozdělení narozenin během roku (tj. budeme ignorovat přestupné roky, dvojčata atd.)

Je jednodušší nejprve spočítat pravděpodobnost p(n), že všech „n“ narozenin je rozdílných. Pro „n“ > 365 je tato pravděpodobnost, s ohledem na Dirichletův princip, rovna nule. Pro „n“ ≤ 365 je dána vzorcem:

\bar p(n) = 1 \cdot \left(1-\frac{1}{365}\right) \cdot \left(1-\frac{2}{365}\right)  \cdots \left(1-\frac{n-1}{365}\right) = { 365 \cdot 364 \cdots (365-n+1) \over 365^n } = { 365! \over 365^n (365-n)!}

Protože druhá osoba nemůže mít stejné narozeniny jako první (364/365), třetí nemůže mít stejné narozeniny jako první dvě (363/365), atd.

Skutečnost, že nejméně dva z „n“ lidí mají stejné narozeniny je komplementární jevu, že všechny data narozenin jsou různé. Proto pravděpodobnost p(n) je

 p(n) = 1 - \bar p(n) .

Tato pravděpodobnost překračuje 1/2 pro „n“ = 23 (hodnota kolem 50,7 %). Následující tabulka ukazuje pravděpodobnosti pro některé další hodnoty „n“ (Tabulka ignoruje přestupné roky, jak již bylo výše popsáno):

n p(n)
10 12%
20 41%
23 50,7%
30 70%
50 97%
100 99,99996%
200 99,9999999999999999999999999998%
300 (100 − (6×10−80))%
350 (100 − (3×10−129))%
366 100%

Poznámky[editovat | editovat zdroj]

  1. Ve skutečnosti však nejsou data narození rozprostřena rovnoměrně v průběhu roku, a to nikoliv pouze kvůli 29. únoru, který se vyskytuje pouze jednou za čtyři roky.