Narozeninový paradox

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. února 2022; kontroly vyžadují 2 úpravy .

Narozeninový paradox je tvrzení, že ve skupině 23 a více osob pravděpodobnost shody narozenin (den a měsíc) u alespoň dvou osob přesahuje 50 % . Pokud je například ve třídě 23 nebo více studentů , pak je pravděpodobnější, že pár spolužáků bude mít narozeniny ve stejný den, než že každý bude mít jedinečné narozeniny [1] . Poprvé se tímto problémem zabýval Richard Mises v roce 1939 [2] [3] .

U 57 a více lidí pravděpodobnost takové náhody přesahuje 99 % , i když podle Dirichletova principu (selského rozumu) dosahuje 100 % pouze tehdy, když je ve skupině alespoň 367 osob (přesně o 1 více než je počet dnů v přestupném roce; s přihlédnutím k přestupným rokům).

Takové tvrzení se může zdát jako samozřejmé, protože pravděpodobnost, že se narozeniny dvou lidí shodují s kterýmkoli dnem v roce , vynásobená počtem lidí ve skupině (23), dává pouze . Tato úvaha je nesprávná, protože počet možných párů výrazně převyšuje počet lidí ve skupině ( 253 > 23 ). Tvrzení tedy není paradoxem v přísném vědeckém smyslu: není v něm žádný logický rozpor a paradox spočívá pouze v rozdílech mezi intuitivním vnímáním situace člověkem a výsledky matematického výpočtu. $({\tfrac {1}{365}}=0{,}27\,\%)$ ${\tfrac {1}{365}}\times 23=6{,}3\,\%$ $({\tfrac {23\times 22}{2}}=253)$

Intuitivní vnímání

Ve skupině 23 lidí je pravděpodobnost, že dva lidé budou mít stejné narozeniny, tak vysoká, protože se bere v úvahu pravděpodobnost, že libovolní dva lidé ve skupině budou mít stejné narozeniny. Tato pravděpodobnost je určena počtem párů lidí, které mohou tvořit 23 lidí. Protože na pořadí osob ve dvojicích nezáleží, celkový počet takových dvojic se rovná počtu kombinací 23 x 2, tedy (23 × 22) / 2 = 253 dvojic .

Při formulaci paradoxu mluvíme o shodě narozenin libovolných dvou členů skupiny. Jednou z běžných mylných představ je, že tento případ je zaměňován s jiným zdánlivě podobným případem, kdy je ze skupiny vybrána jedna osoba a odhaduje se pravděpodobnost, že narozeniny kteréhokoli jiného člena skupiny se budou shodovat s narozeninami vybrané osoby. V druhém případě je pravděpodobnost shody mnohem nižší.

Výpočet pravděpodobnosti

Je třeba určit pravděpodobnost, že ve skupině n lidí mají alespoň dva z nich stejné narozeniny.

Nechť jsou narozeniny rozděleny rovnoměrně , to znamená, že předpokládáme, že:

rok má 365 dní (žádné přestupné roky );
ve skupině nejsou žádní lidé, kteří se zjevně narodili ve stejný den (například dvojčata );
porodnost nezávisí na dni v týdnu, roční době a dalších faktorech.

Ve skutečnosti to není tak úplně pravda – zejména v některých zemích se kvůli povaze nemocnic rodí více dětí v určité dny v týdnu. Nerovnoměrné rozložení však může pravděpodobnost shody narozenin pouze zvýšit, nikoli však snížit: pokud by se všichni lidé narodili pouze 3 dny z 365, pak by pravděpodobnost shody narozenin byla velmi vysoká.

Spočítejme si nejprve pravděpodobnost, že ve skupině lidí budou narozeniny všech lidí odlišné. Jestliže , pak na základě Dirichletova principu je pravděpodobnost nulová. Pokud , pak budeme argumentovat následovně. Vezměme namátkou jednoho člověka ze skupiny a připomeňme si jeho narozeniny. Pak vezmeme náhodně druhého člověka, přičemž pravděpodobnost, že se jeho narozeniny neshodují s narozeninami první osoby, se rovná . Pak vezměte třetí osobu; pravděpodobnost, že se jeho narozeniny nebudou shodovat s narozeninami jednoho z prvních dvou, se rovná . Analogicky se dostaneme k poslednímu člověku, u kterého bude pravděpodobnost neshody jeho narozenin se všemi předchozími rovna . Vynásobením všech těchto pravděpodobností dostaneme pravděpodobnost, že všechny narozeniny ve skupině se budou lišit: ${\bar p} (n)$ $n$ $n>365$ ${\bar p} (n)$ $n\leqslant 365$ $1-{\frac {1}{365}}$ $1-{\frac {2}{365}}$ $1-{\frac {n-1}{365}}$

{\bar p}(n)=

\left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdot \ldots \cdot \left( 1-{\frac {n-1}{365}}\right)=

{365\cdot 364\cdot \ldots \cdot (365-n+1) \over 365^{n}}=

{365!  \over 365^{n}(365-n)!}.

Pak je pravděpodobnost, že alespoň dva lidé z n mají stejné narozeniny, rovna

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

Hodnota této funkce přesahuje 1/2 at , přičemž pravděpodobnost shody je přibližně 50,73 % a . Seznam n hodnot a jejich odpovídajících pravděpodobností je uveden v následující tabulce. $n=23$ $p(22)\cca 47,57\%$

n	p ( n )
deset	12 %
dvacet	41 %
třicet	70 %
padesáti	97 %
100	99,99996 %
200	99,999999999999999999999999998 %
300	(1 − 7×10 −73 ) × 100 %
350	(1 − 3×10 −131 ) × 100 %
367	100 %

Tento problém lze přeformulovat z hlediska klasického „problému náhody“. Nechat:

urna obsahuje koule (v tomto případě počet dní v roce, předpokládá se, že je 365 dní); $M$ $M$
koule očíslované 1, 2, …, ; $M$
několik vzorků je vyrobeno z n kuliček z urny (v tomto případě n je počet lidí ve skupině);
odebrané koule jsou po každém výběru vráceny do urny;
vzorky jsou považovány za objednané, tedy vzorky a jsou považovány za odlišné. $\{ 1, 2, 4, 6 \}$ $\{ 4, 2, 6, 1 \}$

Je nutné vypočítat pravděpodobnost události spočívající v absenci opakování ve vzorku. Všechny výpočty jsou stejné jako výše .

Alternativní metoda

Pravděpodobnost, že dva lidé ve skupině n budou mít stejné narozeniny , lze také vypočítat pomocí kombinatorických vzorců [4] . Představte si, že každý den v roce je jedno písmeno v abecedě a abeceda se skládá z 365 písmen. Narozeniny n lidí mohou být reprezentovány řetězcem skládajícím se z n písmen této abecedy. Podle Hartleyho vzorce je počet možných řádků

n_{\text{total}}=365^{n}.

Počet možných řetězců, ve kterých se písmena neopakují ( umístění 365 x n ) bude

n_{\text{unique}}={\frac {365!}{(365-n)!}}.

Pokud jsou řádky vybrány náhodně (s rovnoměrným rozdělením ), pravděpodobnost výběru řádku, ve kterém se shodují alespoň dvě písmena, je

p(n)=1-{\frac {n_{\text{unikátní))}{n_{\text{total))))=1-{\frac {\frac {365!}{(365 -n)!}}{365^{n}}}

v a

n\leqslant 365

p(n)=1

v .

n>365

Takto,

{\frac {\left({\frac {365!}{(365-n)!}}\right)}{365^{n}}}={\frac {365\cdot 364\cdot 363 \cdots (365-n+1)}{365^{n}}}={}

{\frac {365}{365}}\cdot {\frac {364}{365}}\cdot {\frac {363}{365}}\cdots {\frac {365-n+1}{ 365}}={}

1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1 -{\frac {n-1}{365}}\right),

a tento výraz je ekvivalentní výrazu uvedenému výše .

Celkový počet možných řad lze také vypočítat pomocí kombinatorického vzorce pro počet umístění s opakováním A (opakování)  n /365 = 365 n .

Aproximace

Exponenciální funkce

Použití Taylorovy řady rozšíření exponenciální funkce

e^{x}=1+x+{\frac {x^{2}}{2!}}+\ldots,

Výše uvedený výraz pro lze přiblížit takto : ${\bar p} (n)$

{\bar p}(n)\cca 1\cdot e^{{-1/365}}\cdot e^{{-2/365}}\cdots e^{{-(n-1)/365} }=

1 \cdot e^{ -( 1 + 2 + \cdots + ( n - 1 ) )/365 } =

e^{ -\frac{ n(n-1) }{ 2 \cdot 365 } } .

Tudíž:

p(n)=1-{\bar p}(n)\cca 1-e^{{-{\frac {n(n-1)}{2\cdot 365))))

Všimněte si, že zjednodušená aproximace

p(n)\přibližně 1-e^{{-{\frac {n^{2}}{2\cdot 365}}}},

jak můžete vidět z grafu, stále dává dostatečnou přesnost.

Uveďme ještě jedno přiblížení .

Pravděpodobnost, že dva lidé mají stejné narozeniny, je 364/365. Ve skupině lidí , párů. Pravděpodobnost , za předpokladu, že tyto události jsou nezávislé , lze tedy aproximovat číslem $n$ $C(n,2)={\frac {n(n-1)}{2}}$ ${\bar p} (n)$

\left({\frac {364}{365}}\right)^{{C(n,2)}}.

Získáme tedy aproximaci pro požadovanou pravděpodobnost p ( n ) :

p(n)\cca 1-\left({\frac {364}{365}}\right)^{{C(n,2))).

Poissonova aproximace

Použitím Poissonovy aproximace pro binom , na základě předchozí aproximace pro , dostaneme o něco více než 50 % : $p(n)$

\operatorname{Poi} \left( \frac{ C(23,2) }{365} \right) = \operatorname{Poi} \left( \frac{253}{365} \right) \approx \operatorname{Poi }( 0{,} 693\, 2);

\mathbb{P} \left( \{ X>0 \} \right) = 1 - \mathbb{P} \left( \{X=0\} \right) = 1 - e^{ -0{,} 693\,2 } = 1 – 0{,}499\,998 = 0{,}500\,002 .

Výpočet počtu lidí, u kterých je pravděpodobnost 50%

Vyjádřeme n z výše uvedeného vzorce . Potom místo p ( n ) dosadíme 50 % (0,5). V důsledku toho získáme: ${\displaystyle p(n)=1-{\bar {p}}(n)\cca 1-e^{-{\frac {n(n-1)}{2\cdot 365))))$

n\approx {\frac {1}{2}}+{\sqrt {{\frac {1}{4}}-2\cdot 365\cdot \ln 0{,}5}}=22{ ,}9999.

Existuje další způsob, jak odhadnout n s 50% pravděpodobností . Jak bylo prokázáno výše :

{\bar {p}}(n)=1-p(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}} \že jo).

Najděte nejmenší n , pro které

p(n)>{\frac {1}{2))

nebo, což je totéž,

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

Použijme výše uvedenou aproximaci funkce ${\bar p} (n)$ exponenciální funkcí :

{\bar {p}}_{\text{approx}}(n)=\prod _{k=1}^{n-1}e^{\frac {-k}{365}}= e^{\frac {-n(n-1)}{2\cdot 365)).

Dosazením místo toho ve výrazu dostaneme ${\bar {p}}_{\text{approx}}(n)$ ${\bar p} (n)$ ${\bar {p}}(n)<{\frac {1}{2}}$

e^{\frac {-n(n-1)}{2\cdot 365}}<{\frac {1}{2}}.

Řešením pro n dostaneme

n^{2}-n>2\cdot 365\cdot \ln 2.

Odtud najdeme n a zaokrouhlíme nahoru na celé číslo :

n = 23 .

Narozen ve stejný den jako daná osoba

Porovnejme pravděpodobnost p ( n ) s pravděpodobností, že ve skupině n lidí se budou datum narození některé osoby ze skupiny shodovat s narozeninami nějaké předem vybrané osoby, která do skupiny nepatří. Tato pravděpodobnost je

q(n)=1-\left({\frac {365-1}{365}}\right)^{n}.

Dosazením n = 23 dostaneme q ( n ) ≈ 6,12 % . Aby pravděpodobnost q ( n ) přesáhla 50 % , musí být počet lidí ve skupině alespoň 253 ( q (252) ≈ 49,91 % ; q (253) ≈ 50,05 % ). Toto číslo je více než polovina dnů v roce ( 365/2 = 182,5 ); je to dáno tím, že ostatní členové skupiny mohou mít stejné narozeniny a tím se snižuje pravděpodobnost q ( n ) . Přesněji řečeno, je to způsobeno tím, že při sčítání pravděpodobností náhod pokaždé odečteme pravděpodobnost společného výskytu těchto událostí, protože události jsou společné a pravděpodobnost jejich společného výskytu při sčítání se bere v úvahu. dvakrát. P ( A + B ) = P ( A ) + P ( B ) − P ( AB ) a tak dále s každým přidáním nového členu.

Zobecnění

Koincidence diskrétních náhodných veličin

Popsaný problém lze formulovat v obecné podobě:

daná náhodná čísla;
náhodná čísla jsou distribuována rovnoměrně v rozsahu od 1 do d ;
n je počet náhodných čísel;
určit p ( n ; d ) - pravděpodobnost , že se alespoň dvě z daných čísel budou shodovat.

Pokud uvažujete stejným způsobem, jak je popsáno výše , můžete získat obecná řešení:

p(n;d)={\begin{cases}1-\prod _{{k=1}}^{{n-1}}\left(1-{k \over d}\right)&n\leq d\\1&n>d\end{cases}};

p(n;d)\přibližně 1-e^{{-(n(n-1))/2d}};

q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.

Inverzní problém:

dané p je pravděpodobnost, že se shodují alespoň dvě náhodná čísla;
je známo, že náhodná čísla jsou rovnoměrně rozložena v rozsahu od 1 do d ;
find n ( p ; d ) — počet náhodných čísel.

Řešení:

n(p;d)\cca {\sqrt {2d\cdot \ln \left({1 \over 1-p}\right))).

Několik typů lidí

Výše byl uveden narozeninový paradox pro jeden „typ“ lidí. Problém je možné zobecnit zavedením několika „typů“, například rozdělením lidí na muže ( m ) a ženy ( n ). Vypočítejme pravděpodobnost, že alespoň jedna žena a jeden muž mají stejné narozeniny (nebere se v úvahu shoda narozenin dvou žen nebo dvou mužů):

p_{0}=1-{\frac {1}{d^{{m+n))))\součet _{{i=1}}^{m}\součet _{{j=1}}^ {n}S_{2}(m,i)S_{2}(n,j)\prod _{{k=0}}^{{i+j-1}}(neví),

kde d \u003d 365 a S 2 () jsou Stirlingova čísla druhého druhu . Zajímavé je, že na otázku o hodnotě n + m pro danou pravděpodobnost neexistuje jednoznačná odpověď . Například pravděpodobnost 0,5 dává jak soubor 16 mužů a 16 žen, tak soubor 43 mužů a 6 žen.

Blízké narozeniny

Dalším zobecněním narozeninového paradoxu je uvést problém, kolik lidí potřebuje k tomu, aby pravděpodobnost, že budou mít ve skupině lidí, jejichž narozeniny se neliší o více než jeden den (nebo dva, tři dny atd.), přesáhla 50 % . . Při řešení tohoto problému se používá princip inkluze-exkluze . Výsledek (opět za předpokladu, že narozeniny jsou rovnoměrně rozloženy ) je:

Maximální rozdíl v narozeninách, počtu dní	Požadovaný počet lidí
jeden	23
2	čtrnáct
3	jedenáct
čtyři	9
5	osm
6	osm
7	7
osm	7

Pravděpodobnost, že i ve skupině 7 lidí se narozeniny alespoň dvou z nich nebudou lišit o více než týden, tedy přesahuje 50 % .

Aplikace

Narozeninový paradox obecně platí pro hašovací funkce : pokud hašovací funkce generuje N - bitovou hodnotu, pak počet náhodných vstupů, u kterých se hašovací kódy s vysokou pravděpodobností střetnou (to znamená, že existují stejné hašovací kódy získané na různých vstupních datech). ) není 2 N , ale jen asi 2 N /2 . Toto pozorování je zneužito při útoku na kryptografické hašovací funkce zvané narozeninový útok .

N	Počet různých výstupních řetězců (2 N )	Pravděpodobnost alespoň jedné kolize ( p )
N	Počet různých výstupních řetězců (2 N )	10 −18	10 −15	10 −12	10 −9	10 −6	0,1 %	jeden %	25 %	padesáti %	75 %
32	4,3 × 109	2	2	2	2.9	93	2,9×10³	9,3×10³	5,0×10⁴	7,7×10⁴	1,1×10⁵
64	1,8 × 10 19	6.1	1,9×10²	6,1×10³	1,9×10⁵	6,1×10⁶	1,9×10⁸	6,1×10⁸	3,3×10⁹	5,1×10⁹	7,2×10⁹
128	3,4 × 10 38	2,6 × 10 10	8,2 × 10 11	2,6 × 10 13	8,2 × 10 14	2,6 × 10 16	8,3 × 10 17	2,6 × 10 18	1,4 × 10 19	2,2 × 10 19	3,1 × 10 19
256	1,2 × 10 77	4,8 × 10 29	1,5 × 10 31	4,8 × 10 32	1,5×10 34	4,8 × 10 35	1,5 × 10 37	4,8 × 10 37	2,6 × 10 38	4,0 × 10 38	5,7 × 10 38
384	3,9 × 10 115	8,9 × 10 48	2,8 × 10 50	8,9 × 1051	2,8 × 1053	8,9 × 1054	2,8 × 1056	8,9 × 1056	4,8 × 1057	7,4× 1057	1,0 × 10 58
512	1,3× 10154	1,6 × 10 68	5,2 × 10 69	1,6 × 10 71	5,2 × 1072	1,6× 1074	5,2 × 1075	1,6 × 10 76	8,8 × 1076	1,4 × 10 77	1,9 × 10 77

Bílé buňky označují počet osob ve skupině, u kterých s danou pravděpodobností dojde ke kolizi (analogicky s paradoxem je počet výstupních řetězců 365).

Podobný matematický aparát se používá k odhadu velikosti populace ryb žijících v jezerech . Metoda se nazývá "capture-recapture" ("chytit - znovu chytit"). Pokud je totiž každá ulovená ryba označena a vypuštěna, pak pravděpodobnost ulovení označené ryby poroste nelineárně (v souladu s výše uvedeným grafem) s rostoucím počtem pokusů. Velikost populace lze zhruba odhadnout jako druhou mocninu počtu pokusů provedených před ulovením první označené ryby.

Řešení problému v obecných termínech nachází uplatnění v mnoha odvětvích matematiky , například v nedeterministických faktorizačních algoritmech . Jedno z nejjednodušších vysvětlení Pollardovy ρ-metody je tedy podobné vysvětlení narozeninového paradoxu: stačí mít přibližně náhodná čísla od 0 do , kde jsou prvočísla, takže pro alespoň jednu z dvojic čísel s existuje vysoká pravděpodobnost , která bude dělitelem čísla n . $\sqrt{p}$ $n=pq$ $p<q$ $\gcd \left(|xy|,n\right)>1$

Inverzní problémy

Nalezení nejmenšího čísla n takového , že pravděpodobnost p ( n ) je větší než dané číslo p .

Najít největší číslo n takové, že pravděpodobnost p ( n ) je menší než dané číslo p .

Pomocí výše uvedeného vzorce dostaneme:

n(p;365)\cca {\sqrt {2\cdot 365\cdot \ln \left({1 \over 1-p}\right))).

p	n	n ↓	p ( n ↓)	n ↑	p ( n ↑)
0,01	0,14178√365 = 2,70864	2	0,00274	3	0,00820
0,05	0,32029√365 = 6,11916	6	0,04046	7	0,05624
0,1	0,45904√365 = 8,77002	osm	0,07434	9	0,09462
0,2	0,66805√365 = 12,76302	12	0,16702	13	0,19441
0,3	0,84460√365 = 16,13607	16	0,28360	17	0,31501
0,5	1,17741√365 = 22,49439	22	0,47570	23	0,50730
0,7	1,55176√365 = 29,64625	29	0,68097	třicet	0,70632
0,8	1,79412√365 = 34,27666	34	0,79532	35	0,81438
0,9	2,14597√365 = 40,99862	40	0,89123	41	0,90315
0,95	2,44775√365 = 46,76414	46	0,94825	47	0,95477
0,99	3,03485√365 = 57,98081	57	0,99012	58	0,99166

Nejlepší pozice

Ať je v místnosti n - 1 lidí a jejich narozeniny jsou různé. Nechť g ( n ) je pravděpodobnost, že narozeniny osoby, která vstoupila, jsou stejné jako narozeniny někoho přítomného v místnosti. Je potřeba najít hodnotu n , při které je hodnota funkce g ( n ) maximální.

Řešením je nalezení maximální hodnoty výrazu

p ( n ) - p ( n - 1) .

Pomocí výše uvedeného vzorce pro p ( n ) dostaneme n = 20 .

Průměrný počet lidí

Podívejme se na další problém. Kolik lidí je v průměru potřeba, aby alespoň dva z nich sdíleli stejné narozeniny?

Tento problém měl co do činění s hašovacími algoritmy a zkoumal jej Donald Knuth . Ukazuje se, že náhodná veličina, která nás zajímá, má matematické očekávání rovné

\overline {n}\,=\,1+Q(M),

kde

Q(M)=\sum _{{k=1}}^{{M}}{\frac {M!}{(Mk)!M^{k}}}.

Funkce

Q(M)\,=\,1+{\frac {M-1}{M}}+{\frac {(M-1)(M-2)}{M^{2}}}+\cdots +{\frac {(M-1)(M-2)\cdots 1}{M^{{M-1))))

byl prozkoumán Ramanujanem . Získal také následující asymptotické rozšíření pro tuto funkci :

Q(M)\sim {\sqrt {{\frac {\pi M}{2))))-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt { {\frac {\pi }{2M))))-{\frac {4}{135M))+\cdots .

Při M = 365 je průměrný počet lidí

{\overline {n}}\,=\,1+Q(M)\cca 24,61658.

Toto číslo je o něco větší než počet lidí poskytujících 50% šanci . Potřebný počet lidí je překvapivě M + 1 = 366 (pro 365 lidí lze jejich narozeniny rozložit na každý z 365 dnů v roce bez překrývání), ačkoliv je jich v průměru potřeba jen 25.

Viz také

Poznámky

↑ Mazur, 2017 , str. 116.
↑ Mazur, 2017 , str. 119.
↑ Mironkin V. O., Chukhno A. B. O jednom zobecnění paradoxu „narozenin“ . Získáno 30. března 2020. Archivováno z originálu dne 9. července 2020. (neurčitý)
↑ Mazur, 2017 , str. 117.

Literatura

Kemeny J. , Snell J., Thompson J. Introduction to Finite Mathematics = Introduction to Finite Mathematics. - Nakladatelství zahraniční literatury, 1963. - 488 s.
Kozlov MV Základy teorie pravděpodobnosti v příkladech a úlohách. - Moskevská státní univerzita, 1990 . — ISBN 5-211-00312-8 .
Mazur, Josef. Problém s narozeninami // Hazardní hra. Matematika a mytologie náhody. - Alpina literatura faktu, 2017. - S. 116-123. — 292 s. - ISBN 978-5-91671-636-8 .
Sekey G. Paradoxy v teorii pravděpodobnosti a matematické statistice. - RHD, 2003 . — ISBN 5-93972-150-8 .
Shiryaev A. N. Pravděpodobnost-1. - MTsNMO, 2007 . - ISBN 978-5-94057-036-3 .
Goldberg S. Přímý útok na narozeninový problém // Magazín Mathematical Mathematics. — květen 1976 . — Iss. 49 . - S. 130-132 .

Mosteller F. Pochopení narozeninového problému // Učitel matematiky. — květen 1962 . - str . 322-325 . _

Odkazy

Paradoxy teorie pravděpodobnosti .
Srovnávací přehled PGP algoritmů. Paradox „narozenin“ a bezpečnost kryptografie .
Eurobirthdays 2012 (anglicky) . Praktický příklad.