Narozeninový problém

Tento článek potřebuje úpravy.

Můžete Wikipedii pomoci tím, že ho vylepšíte. Jak by měly články vypadat, popisují stránky Vzhled a styl, Encyklopedický styl a Odkazy.

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). Matematika skrytá za tímto problémem vede k známému kryptografickému útoku zvanému narozeninový útok.

Pochopení problému

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

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%