Narozeninový problém

V teorii pravděpodobnosti je narozeninový problém úloha vypočítat minimální početnost skupiny lidí, ve které je alespoň 50% pravděpodobnost nalezení dvojice se stejným datem narození (den a měsíc). Narozeninovým paradoxem je pak označována skutečnost, že tento počet (23) je mnohem menší než intuitivní odhad. Pro skupinu 57 a více lidí je tato pravděpodobnost už více než 99 %, postupně rostoucí až ke 100 % pro 366 lidí (za předpokladu že pracujeme s rokem o 365 dnech).[p. 1] Matematika skrytá za tímto problémem vede k známému kryptografickému útoku zvanému narozeninový útok.

Výpočet pravděpodobnosti

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:

p ¯ ( n ) = 1 ⋅ ( 1 − 1 365 ) ⋅ ( 1 − 2 365 ) ⋯ ( 1 − n − 1 365 ) = = 365 ⋅ 364 ⋯ ( 365 − n + 1 ) 365 n = = 365 ! 365 n ( 365 − n ) ! {\displaystyle {\begin{aligned}{\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)!}\end{aligned}}}

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šechna data narozenin jsou různá. Proto pravděpodobnost p(n) je

p ( n ) = 1 − p ¯ ( n ) . {\displaystyle 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):

Tento problém může být vypočítán také jako (1 − variace (365, počet studentů) / variace s opakováním (365, počet studentů)).

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

Odkazy

Poznámky

  1. ↑ Úloha předpokládá stejnou pravděpodobnost narození v každém dni roku, 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.[1]

Reference

  1. ↑ CHIBANA, Nayomi. Do humans have mating seasons? This heat map reveals the surprising link between birthdays and seasons

Externí odkazy

  • Logo Wikimedia Commons Obrázky, zvuky či videa k tématu narozeninový problém na Wikimedia Commons