Problém k narozeninám - Birthday problem

Vypočítaná pravděpodobnost, že alespoň dva lidé budou sdílet narozeniny, v porovnání s počtem lidí

V teorii pravděpodobnosti se problém narozenin nebo paradox narozenin týká pravděpodobnosti, že v souboru n náhodně vybraných lidí bude mít pár z nich stejné narozeniny . Ve skupině 23 lidí pravděpodobnost sdílených narozenin přesahuje 50%, zatímco skupina 70 má 99,9% šanci na sdílené narozeniny. (Podle principu pigeonhole pravděpodobnost dosáhne 100%, když počet lidí dosáhne 367, protože existuje pouze 366 možných narozenin, včetně 29. února .)

Tyto závěry jsou založeny na předpokladu, že každý den v roce je stejně pravděpodobný k narozeninám. Skutečné záznamy o narození ukazují, že se v různé dny rodí různé počty lidí. V tomto případě lze prokázat, že počet lidí potřebných k dosažení 50% hranice je 23 nebo méně .

Narozeninový problém je skutečným paradoxem : tvrzení, které se zpočátku jeví jako neintuitivní, ale ve skutečnosti je pravdivé. I když se může zdát překvapivé, že k dosažení 50% pravděpodobnosti sdílených narozenin je zapotřebí pouze 23 jedinců, je tento výsledek intuitivnější, když vezmeme v úvahu, že srovnání narozenin bude provedeno mezi každou možnou dvojicí jednotlivců. U 23 jedinců je třeba uvažovat (23 × 22) / 2 = 253 párů, což je více než poloviční počet dní v roce (182,5 nebo 183).

Mezi reálné aplikace pro problém s narozeninami patří kryptografický útok zvaný narozeninový útok , který pomocí tohoto pravděpodobnostního modelu snižuje složitost hledání kolize pro hashovací funkci a také vypočítává přibližné riziko kolize hash existující v hashe. dané velikosti populace.

Historie problému je nejasná. Výsledek byl připsán Haroldovi Davenportovi ; verzi toho, co je dnes považováno za problém narozenin, však navrhl dříve Richard von Mises .

Výpočet pravděpodobnosti

Problém je spočítat přibližnou pravděpodobnost, že ve skupině n lidí mají alespoň dva stejné narozeniny. Pro jednoduchost nejsou brány v úvahu rozdíly v distribuci, jako jsou přestupné roky , dvojčata , sezónní nebo pracovní dny, a předpokládá se, že všech 365 možných narozenin je stejně pravděpodobných. (Distribuce narozenin v reálném životě nejsou jednotná, protože ne všechna data jsou stejně pravděpodobná, ale tyto nepravidelnosti mají malý vliv na analýzu. Ve skutečnosti je nejhorší případ jednotné rozdělení dat narození.)

Cílem je vypočítat P ( A ) , pravděpodobnost, že alespoň dva lidé v místnosti mají stejné narozeniny. Je však jednodušší vypočítat P ( A ') , pravděpodobnost, že v místnosti nebudou mít dva lidé stejné narozeniny. Poté, protože A a A ′ jsou jediné dvě možnosti a také se vzájemně vylučují , P ( A ) = 1 - P ( A ′).

Na základě široce publikovaných řešení, které vedou k závěru, že 23 je minimální počet lidí nezbytných k dosažení P ( A ), který je větší než 50%, bude následující výpočet P ( A ) používat jako příklad 23 lidí. Pokud jedna čísluje 23 lidí od 1 do 23, událost, že všech 23 lidí má jiné narozeniny, je stejná jako událost, že osoba 2 nemá stejné narozeniny jako osoba 1 a tato osoba 3 nemá stejné narozeniny jako buď osoba 1 nebo osoba 2 atd. a konečně tato osoba 23 nemá stejné narozeniny jako žádná z osob 1 až 22. Nechť se tyto události nazývají „Událost 2“, „Událost 3“ atd. Lze také přidat „Událost 1“, která odpovídá události osoby 1, která má narozeniny a která nastává s pravděpodobností 1. Tuto spojku událostí lze vypočítat pomocí podmíněné pravděpodobnosti : pravděpodobnost události 2 je 364/365 jako osoby 2 může mít jakékoli narozeniny jiné než narozeniny osoby 1. Podobně je pravděpodobnost Události 3, vzhledem k tomu, že došlo k Události 2, 363/365, protože osoba 3 může mít kterékoli z narozenin, které osoby 1 a 2. již neberou. až nakonec je pravděpodobnost Události 23 vzhledem k tomu, že došlo ke všem předchozím událostem, 343/365. A konečně, princip podmíněné pravděpodobnosti naznačuje, že P ( A ') se rovná součinu těchto individuálních pravděpodobností:

${\ displaystyle P (A ') = {\ frac {365} {365}} \ krát {\ frac {364} {365}} \ krát {\ frac {363} {365}} \ krát {\ frac {362 } {365}} \ times \ cdots \ times {\ frac {343} {365}}}$

( 1 )

Podmínky rovnice ( 1 ) lze shromáždit, abychom dospěli k:

${\ displaystyle P (A ') = \ left ({\ frac {1} {365}} \ right) ^ {23} \ times (365 \ times 364 \ times 363 \ times \ cdots \ times 343)}$

( 2 )

Vyhodnocením rovnice ( 2 ) získáme P ( A ') ≈ 0,4992703

Proto P ( A ) ≈ 1 - 0,4992703 = 0,507297  (50,7297%).

Tento proces lze zobecnit na skupinu n lidí, kde p ( n ) je pravděpodobnost, že alespoň dva z n lidí budou mít narozeniny. Je snazší nejprve vypočítat pravděpodobnost p ( n ), že všech n narozenin je odlišných . Podle principu pigeonhole je p ( n ) nula, když n > 365 . Když n  ≤ 365 :

${\ displaystyle {\ begin {aligned} {\ bar {p}} (n) & = 1 \ times \ left (1 - {\ frac {1} {365}} \ right) \ times \ left (1- { \ frac {2} {365}} \ right) \ times \ cdots \ times \ left (1 - {\ frac {n-1} {365}} \ right) \\ [6pt] & = {\ frac {365 \ times 364 \ times \ cdots \ times (365-n + 1)} {365 ^ {n}}} \\ [6pt] & = {\ frac {365!} {365 ^ {n} (365-n) !}} = {\ frac {n! \ cdot {\ binom {365} {n}}} {365 ^ {n}}} = {\ frac {_ {365} P_ {n}} {365 ^ {n }}} \ end {zarovnáno}}}$

kde ! je faktoriální operátor, (³⁶⁵
_n) jebinomický koeficienta _k P _r označujepermutaci.

Rovnice vyjadřuje skutečnost, že první osoba nemá nikoho, kdo by sdílel narozeniny, druhá osoba nemůže mít stejné narozeniny jako první (364/365), třetí nemůže mít stejné narozeniny jako žádný z prvních dvou (363/365) a obecně n- té narozeniny nemohou být stejné jako kterékoli z n - 1 předcházejících narozenin.

Událost alespoň dvou z n osob, které mají stejné narozeniny je komplementární k všechna n narozeniny jsou odlišné. Proto je jeho pravděpodobnost p ( n ) je

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

Následující tabulka ukazuje pravděpodobnost pro některé další hodnoty n (u této tabulky je existence přestupných let ignorována a předpokládá se, že každé narozeniny jsou stejně pravděpodobné):

Pravděpodobnost, že žádné dva lidé nesdílejí narozeniny ve skupině n lidí. Všimněte si, že na svislé ose je logaritmická (každý krok dolů je 10 ²⁰ krát méně pravděpodobně).

n	p ( n )
1	00,0%
5	02,7%
10	11,7%
20	41,1%
23	50,7%
30	70,6%
40	89,1%
50	97,0%
60	99,4%
70	99,9%
75	99,97%
100	99,999 97 %
200	99,999 999 999 999 999 999 999 999 999 9998 %
300	(100 - 6 × 10 −80 )%
350	(100 - 3 × 10 −129 )%
365	(100 - 1,45 × 10 −155 )%
≥ 366	100%

Přestupné roky . Pokud ve vzorci dosadíme 366 za 365 , podobný výpočet ukazuje, že v přestupných letech je počet lidí potřebných k tomu, aby pravděpodobnost zápasu byla více než 50%, také 23; pravděpodobnost shody je v tomto případě 50,6%. ${\ displaystyle {\ bar {p}} (n)}$

Aproximace

Grafy zobrazující přibližné pravděpodobnosti nejméně dvou lidí sdílejících narozeniny ( červená ) a její doplňková událost ( modrá )

Graf ukazující přesnost přiblížení 1 - e ^{- n 2 / 730} ( červená )

Taylorovy řady expanze exponenciální funkce (konstanta e ≈2,718 281 828 )

${\ displaystyle e ^ {x} = 1 + x + {\ frac {x ^ {2}} {2!}} + \ cdots}$

poskytuje aproximaci prvního řádu pro e ^x pro : ${\ displaystyle | x | \ ll 1}$

${\ displaystyle e ^ {x} \ přibližně 1 + x.}$

Chcete-li použít tuto aproximaci na první výraz odvozený pro p ( n ) , nastavte x = -A/365. Tím pádem,

${\ displaystyle e ^ {- a / 365} \ přibližně 1 - {\ frac {a} {365}}.}$

Poté nahraďte a nezápornými celými čísly pro každý člen ve vzorci p ( n ), dokud a = n - 1 , například když a = 1 ,

${\ displaystyle e ^ {- 1/365} \ přibližně 1 - {\ frac {1} {365}}.}$

První výraz odvozený pro p ( n ) lze aproximovat jako

${\ displaystyle {\ begin {zarovnáno} {\ bar {p}} (n) & \ cca 1 \ cdot e ^ {- 1/365} \ cdot e ^ {- 2/365} \ cdots e ^ {- ( n-1) / 365} \\ [6pt] & = e ^ {- \ left. {\ big (} 1 + 2 + \, \ cdots \, + (n-1) {\ big)} \ right / 365} \\ [6pt] & = e ^ {- (n (n-1) / 2) / 365} = e ^ {- n (n-1) / 730}. \ End {zarovnáno}}}$

Proto,

${\ displaystyle p (n) = 1 - {\ bar {p}} (n) \ přibližně 1-e ^ {- n (n-1) / 730}.}$

Ještě hrubší aproximace je dána vztahem

${\ displaystyle p (n) \ přibližně 1-e ^ {- n ^ {2} / 730},}$

který, jak ukazuje graf, je stále poměrně přesný.

Podle aproximace lze stejný přístup použít na libovolný počet „lidí“ a „dnů“. Pokud spíše než 365 dní existují d , pokud existuje n osob, a pokud n ≪ d , pak použitím stejného přístupu jako výše dosáhneme výsledku, že pokud p ( n , d ) je pravděpodobnost, že alespoň dvě z n lidé sdílejí stejné narozeniny ze sady d dostupných dnů, poté:

${\ displaystyle {\ begin {zarovnáno} p (n, d) & \ cca 1-e ^ {- n (n-1) / (2d)} \\ [6pt] & \ cca 1-e ^ {- n ^ {2} / (2d)}. \ End {zarovnáno}}}$

Jednoduchá umocňování

Pravděpodobnost, že by dva lidé neměli stejné narozeniny, je 364/365. V místnosti s n lidmi je (ⁿ
₂) =n ( n  - 1)/2páry lidí, tj. (ⁿ
₂) události. Pravděpodobnost, že dva lidé nebudou sdílet stejné narozeniny, lze odhadnout za předpokladu, že tyto události jsou nezávislé, a tedy vynásobením jejich pravděpodobnosti dohromady. Ve zkratce364/365lze znásobit sám (ⁿ
₂) krát, což nám dává

${\ displaystyle {\ bar {p}} (n) \ přibližně \ vlevo ({\ frac {364} {365}} \ vpravo) ^ {\ binom {n} {2}}.}$

Jelikož se jedná o pravděpodobnost, že nikdo nebude mít stejné narozeniny, pak je pravděpodobnost, že někdo bude mít narozeniny

${\ displaystyle p (n) \ přibližně 1- \ vlevo ({\ frac {364} {365}} \ vpravo) ^ {\ binom {n} {2}}.}$

Poissonova aproximace

Uplatnění Poissonovy aproximace pro dvojčlen na skupinu 23 lidí,

${\ displaystyle \ operatorname {Poi} \ left ({\ frac {\ binom {23} {2}} {365}} \ right) = \ operatorname {Poi} \ left ({\ frac {253} {365}} \ right) \ přibližně \ operatorname {Poi} (0,6932)}$

tak

${\ displaystyle \ Pr (X> 0) = 1- \ Pr (X = 0) \ přibližně 1-e ^ {- 0,6932} \ přibližně 1-0,499998 = 0,500002.}$

Výsledek je více než 50% jako předchozí popisy. Tato aproximace je stejná jako výše uvedená na základě Taylorovy expanze, která se používá . ${\ displaystyle e ^ {x} \ přibližně 1 + x}$

Čtvercová aproximace

Dobrým pravidlem, které lze použít pro mentální výpočet, je vztah

${\ displaystyle p (n) \ přibližně {\ frac {n ^ {2}} {2m}}}$

které lze také zapsat jako

${\ displaystyle n \ cca {\ sqrt {2m \ krát p (n)}}}$

který funguje dobře pro pravděpodobnosti menší nebo rovné 1/2. V těchto rovnicích je m počet dní v roce.

Například pro odhad počtu lidí potřebných pro a 1/2 šance na společné narozeniny, máme

${\ displaystyle n \ přibližně {\ sqrt {2 \ krát 365 \ krát {\ tfrac {1} {2}}}} = {\ sqrt {365}} \ přibližně 19}$

Což není příliš daleko od správné odpovědi 23.

Přibližný počet lidí

To lze také aproximovat pomocí následujícího vzorce pro počet osob nutných k dosažení alespoň a1/2 šance na shodu:

${\ displaystyle n \ cca {\ tfrac {1} {2}} + {\ sqrt {{\ tfrac {1} {4}} + 2 \ krát \ ln (2) \ krát 365}} = 22,999943.}$

To je výsledek dobrého přiblížení, s nímž událost souvisí 1/k pravděpodobnost bude mít 1/2šance na výskyt alespoň jednou, pokud se opakuje k ln 2krát.

Pravděpodobnostní tabulka

délka hexadecimálního řetězce	Ne. z bitů ( b )	velikost hash prostoru ( 2 b )	Počet hašovaných prvků tak, že pravděpodobnost alespoň jedné hašovací srážky ≥  p
			p =10 −18	p =10 −15	p =10 −12	p =10 −9	p =10 −6	p = 0,001	p = 0,01	p = 0,25	p = 0,50	p = 0,75
8	32	4,3 × 10 9	2	2	2	2.9	93	2,9 × 10 3	9,3 × 10 3	5,0 × 10 4	7,7 × 10 4	1,1 × 10 5
(10)	(40)	(1,1 × 10 12 )	2	2	2	47	1,5 × 10 3	4,7 × 10 4	1,5 × 10 5	8,0 × 10 5	1,2 × 10 6	1,7 × 10 6
(12)	(48)	(2,8 × 10 14 )	2	2	24	7,5 × 10 2	2,4 × 10 4	7,5 × 10 5	2,4 × 10 6	1,3 × 10 7	2,0 × 10 7	2,8 × 10 7
16	64	1,8 × 10 19	6.1	1,9 × 10 2	6,1 × 10 3	1,9 × 10 5	6,1 × 10 6	1,9 × 10 8	6,1 × 10 8	3,3 × 10 9	5,1 × 10 9	7,2 × 10 9
(24)	(96)	(7,9 × 10 28 )	4,0 × 10 5	1,3 × 10 7	4,0 × 10 8	1,3 × 10 10	4,0 × 10 11	1,3 × 10 13	4,0 × 10 13	2,1 × 10 14	3,3 × 10 14	4,7 × 10 14
32	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
(48)	(192)	(6,3 × 10 57 )	1,1 × 10 20	3,5 × 10 21	1,1 × 10 23	3,5 × 10 24	1,1 × 10 26	3,5 × 10 27	1,1 × 10 28	6,0 × 10 28	9,3 × 10 28	1,3 × 10 29
64	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
(96)	(384)	(3,9 x 10 115 ),	8,9 × 10 48	2,8 × 10 50	8,9 × 10 51	2,8 × 10 53	8,9 × 10 54	2,8 × 10 56	8,9 × 10 56	4,8 × 10 57	7,4 × 10 57	1,0 × 10 58
128	512	1,3 × 10 154	1,6 × 10 68	5,2 × 10 69	1,6 × 10 71	5,2 × 10 72	1,6 × 10 74	5,2 × 10 75	1,6 × 10 76	8,8 × 10 76	1,4 × 10 77	1,9 × 10 77

Srovnání problému narozenin (1) a útoku na narozeniny (2):

V (1) jsou srážky nalezeny v rámci jedné sady, v tomto případě 3 z 276 párů 24 měsíčních astronautů.

V (2) jsou nalezeny kolize mezi dvěma sadami, v tomto případě 1 z 256 párování pouze prvních bytů hash SHA-256 16 variant, každá z neškodných a škodlivých smluv.

Světlejší pole v této tabulce ukazují počet zatřiďování potřebných k dosažení dané pravděpodobnosti kolize (sloupce) vzhledem k zatřiďovacímu prostoru určité velikosti v bitech (řádek). Použití analogie narozenin: „velikost hash prostoru“ se podobá „dostupným dnům“, „pravděpodobnost kolize“ se podobá „pravděpodobnosti sdílených narozenin“ a „požadovaný počet hashovaných prvků“ se podobá „požadovanému počtu osob v skupina". Dalo by se také použít tento graf k určení minimální požadované velikosti hash (vzhledem k horním mezím hash a pravděpodobnosti chyby) nebo pravděpodobnosti kolize (pro pevný počet hash a pravděpodobnost chyby).

Pro srovnání, 10 ⁻¹⁸ až10 ⁻¹⁵ je neopravitelná bitová chybovost typického pevného disku. Teoreticky by 128bitové hashovací funkce, jako je MD5 , měly zůstat v tomto rozsahu až do zhruba8,2 × 10 ¹¹ dokumentů, i když jeho možných výstupů je mnohem více.

Horní hranice pravděpodobnosti a dolní hranice počtu lidí

Níže uvedený argument je převzat z argumentu Paula Halmosa .

Jak je uvedeno výše, pravděpodobnost, že se žádné dva narozeniny neshodují, je

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

Stejně jako v předchozích odstavcích, zájem spočívá v nejmenším n takovém, že p ( n )>1/2; nebo ekvivalentně nejmenší n takové, že p ( n ) <1/2.

Použitím nerovnosti 1 - x < e ^{- x} ve výše uvedeném výrazu nahradíme 1 -k/365s e ^{- k / 365} . To přináší

${\ displaystyle {\ bar {p}} (n) = \ prod _ {k = 1} ^ {n-1} \ left (1 - {\ frac {k} {365}} \ right) <\ prod _ {k = 1} ^ {n-1} \ left (e ^ {- k / 365} \ right) = e ^ {- n (n-1) / 730}.}$

Proto se výraz výše není jen přiblížení, ale také horní hranici z p ( n ) . Nerovnost

${\ displaystyle e ^ {- n (n-1) / 730} <{\ frac {1} {2}}}$

znamená p ( n ) <1/2. Řešení pro n dává

${\ displaystyle n ^ {2} -n> 730 \ ln 2.}$

Nyní je 730 ln 2 přibližně 505 997, což je sotva pod 506, hodnoty n ² - n bylo dosaženo, když n = 23 . Postačuje tedy 23 lidí. Mimochodem, řešení n ² - n = 730 ln 2 pro n poskytuje přibližný vzorec Franka H. Mathise citovaného výše.

Toto odvození ukazuje pouze to, že k zajištění zápasu narozenin s rovnoměrnou šancí je potřeba maximálně 23 lidí; ponechává otevřenou možnost, že n je 22 nebo méně, může také fungovat.

Zobecnění

Libovolný počet dní

Vzhledem k roku s d dny si zobecněný problém s narozeninami žádá minimální počet n ( d ) , takže u množiny n náhodně vybraných lidí je pravděpodobnost shody narozenin nejméně 50%. Jinými slovy n ( d ) je minimální celé číslo n takové, že

${\ displaystyle 1- \ left (1 - {\ frac {1} {d}} \ right) \ left (1 - {\ frac {2} {d}} \ right) \ cdots \ left (1 - {\ frac {n-1} {d}} \ vpravo) \ geq {\ frac {1} {2}}.}$

Klasický narozeninový problém tedy odpovídá určení n (365) . Zde je uvedeno prvních 99 hodnot n ( d ) (sekvence A033810 v OEIS ):

d	1–2	3–5	6–9	10–16	17–23	24–32	33–42	43–54	55–68	69–82	83–99
n ( d )	2	3	4	5	6	7	8	9	10	11	12

Podobný výpočet ukazuje, že n ( d ) = 23, když d je v rozmezí 341–372.

Byla publikována řada hranic a vzorců pro n ( d ) . Pro libovolné d ≥ 1 vyhovuje číslo n ( d )

${\ displaystyle {\ frac {3-2 \ ln 2} {6}} <n (d) - {\ sqrt {2d \ ln 2}} \ leq 9 - {\ sqrt {86 \ ln 2}}.}$

Tyto hranice jsou optimální v tom smyslu, že posloupnost n ( d ) - √ 2 d ln 2 se libovolně přiblíží

${\ displaystyle {\ frac {3-2 \ ln 2} {6}} \ přibližně 0,27,}$

zatímco má

${\ displaystyle 9 - {\ sqrt {86 \ ln 2}} \ přibližně 1,28}$

jako jeho maximum, vzato pro d = 43 .

Hranice jsou dostatečně pevné, aby poskytly přesnou hodnotu n ( d ) v 99% všech případů, například n (365) = 23 . Z těchto mezí obecně vyplývá, že n ( d ) se vždy rovná buď

${\ displaystyle \ left \ lceil {\ sqrt {2d \ ln 2}} \, \ right \ rceil \ quad {\ text {nebo}} \ quad \ left \ lceil {\ sqrt {2d \ ln 2}} \, \ right \ rceil +1}$

kde ⌈ · ⌉ označuje funkci stropu . Vzorec

${\ displaystyle n (d) = \ vlevo \ lceil {\ sqrt {2d \ ln 2}} \, \ vpravo \ rceil}$

platí pro 73% všech celých čísel d . Vzorec

${\ displaystyle n (d) = \ vlevo \ lceil {\ sqrt {2d \ ln 2}} + {\ frac {3-2 \ ln 2} {6}} \ vpravo \ rceil}$

platí pro téměř všechna d , tj. pro množinu celých čísel d s asymptotickou hustotou 1.

Vzorec

${\ displaystyle n (d) = \ left \ lceil {\ sqrt {2d \ ln 2}} + {\ frac {3-2 \ ln 2} {6}} + {\ frac {9-4 (\ ln 2 ) ^ {2}} {72 {\ sqrt {2d \ ln 2}}}} \ vpravo \ rceil}$

platí pro všechny d ≤10 ¹⁸ , ale předpokládá se, že tohoto vzorce je nekonečně mnoho.

Vzorec

${\ displaystyle n (d) = \ left \ lceil {\ sqrt {2d \ ln 2}} + {\ frac {3-2 \ ln 2} {6}} + {\ frac {9-4 (\ ln 2 ) ^ {2}} {72 {\ sqrt {2d \ ln 2}}}} - {\ frac {2 (\ ln 2) ^ {2}} {135d}} \ right \ rceil}$

platí pro všechny d ≤10 ¹⁸ a předpokládá se, že tento vzorec platí pro všechny d .

Více než dva lidé sdílející narozeniny

Je možné problém rozšířit a zeptat se, kolik lidí ve skupině je nezbytných k tomu, aby byla více než 50% pravděpodobnost, že alespoň 3/4/5 / atd. skupiny sdílí stejné narozeniny.

Prvních několik hodnot je následující:> 50% pravděpodobnost sdílení 3 narozenin - 88 osob; > 50% pravděpodobnost sdílení 4 narozenin - 187 lidí (sekvence A014088 v OEIS ).

Pravděpodobnost sdílených narozenin (kolize)

Problém s narozeninami lze zobecnit takto:

Vzhledem k n náhodným celým číslům získaným z diskrétního rovnoměrného rozdělení s rozsahem [1, d ] , jaká je pravděpodobnost p ( n ; d ), že alespoň dvě čísla jsou stejná? ( d = 365 dává obvyklý problém s narozeninami.)

Obecné výsledky lze odvodit pomocí stejných argumentů, které jsou uvedeny výše.

${\ displaystyle {\ begin {aligned} p (n; d) & = {\ begin {cases} 1- \ displaystyle \ prod _ {k = 1} ^ {n-1} \ left (1 - {\ frac { k} {d}} \ right) & n \ leq d \\ 1 & n> d \ end {cases}} \\ [8px] & \ cca 1-e ^ {- {\ frac {n (n-1)} { 2d}}} \\ & \ přibližně 1- \ vlevo ({\ frac {d-1} {d}} \ vpravo) ^ {\ frac {n (n-1)} {2}} \ end {zarovnáno} }}$

Naopak, pokud n ( p ; d ) označuje počet náhodných celých čísel získaných z [1, d ] k získání pravděpodobnosti p, že alespoň dvě čísla jsou stejná, pak

${\ displaystyle n (p; d) \ cca {\ sqrt {2d \ cdot \ ln \ left ({\ frac {1} {1-p}} \ right)}}}$

Narozeninový problém v tomto obecnějším smyslu platí pro hashovací funkce : očekávaný počet N - bitových hashů, které lze generovat před získáním kolize, není 2 ^N , ale spíše pouze 2 ^{N / 2} . Toto je využíváno narozeninovými útoky na kryptografické hašovací funkce a je to důvod, proč je malý počet kolizí v hašovací tabulce z praktických důvodů nevyhnutelný.

Teorii, která stojí za problémem narozenin, použila Zoe Schnabel pod názvem statistika zachycení a vychytávání k odhadu velikosti populace ryb v jezerech.

Zobecnění na více typů lidí

Graf pravděpodobnosti alespoň jednoho společného narozenin mezi alespoň jedním mužem a jednou ženou

Základní problém považuje všechny pokusy za jeden „typ“. Problém s narozeninami byl zobecněn, aby zvážil libovolný počet typů. V nejjednodušším prodloužení existují dva typy lidí, řekněme m muži a n ženy, a problém se stává charakterizující pravděpodobnost sdíleného narozenin alespoň mezi jedním mužem a jednou ženou. (Sdílené narozeniny mezi dvěma muži nebo dvěma ženami se nepočítají.) Pravděpodobnost, že zde nebudou sdílené narozeniny, je

${\ displaystyle p_ {0} = {\ 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} dk}$

kde d = 365 a S ₂ jsou Stirlingova čísla druhého druhu . V důsledku toho je požadovaná pravděpodobnost 1 - p ₀ .

Tato variace problému s narozeninami je zajímavá, protože neexistuje jedinečné řešení pro celkový počet lidí m + n . Například obvyklá 50% hodnota pravděpodobnosti je realizována jak pro 32člennou skupinu 16 mužů a 16 žen, tak pro 49člennou skupinu 43 žen a 6 mužů.

Další problémy s narozeninami

První zápas

Související otázkou je, že když lidé vstupují do místnosti jeden po druhém, který z nich bude s největší pravděpodobností první, kdo bude mít stejné narozeniny jako někdo, kdo již v místnosti je? To znamená, pro co n je maximum p ( n ) - p ( n  - 1) ? Odpověď je 20 - pokud existuje cena za první zápas, nejlepší pozice v řadě je 20..

Stejné narozeniny jako ty

Porovnání p ( n ) = pravděpodobnost shody narozenin s q ( n ) = pravděpodobnost shody s vašimi narozeninami

V případě problému s narozeninami není ani jeden ze dvou lidí vybrán předem. Naproti tomu pravděpodobnost q ( n ), že někdo v místnosti n jiných lidí má stejné narozeniny jako konkrétní osoba (například vy), je dána

${\ displaystyle q (n) = 1- \ vlevo ({\ frac {365-1} {365}} \ vpravo) ^ {n}}$

a pro obecné d u

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

Ve standardním případě d = 365 dává nahrazení n = 23 asi 6,1%, což je méně než 1 šance v 16. Pro více než 50% šanci, že jedna osoba v místnosti plné n lidí má stejné narozeniny jako vy , n bude muset být alespoň 253. Toto číslo je výrazně vyšší než365/2= 182,5 : důvod je ten, že je pravděpodobné, že mezi ostatními lidmi v místnosti jsou nějaké narozeninové zápasy.

Počet lidí se sdílenými narozeninami

U jakékoli osoby ve skupině n lidí je pravděpodobnost, že sdílí své narozeniny s někým jiným , jak je vysvětleno výše. Očekávaný počet lidí se sdílenými (nejedinečnými) narozeninami lze nyní snadno vypočítat vynásobením pravděpodobnosti počtem lidí ( n ), takže je: ${\ displaystyle q (n-1; d)}$

${\ displaystyle nn \ left ({\ frac {d-1} {d}} \ right) ^ {n-1}}$

(Toto násobení lze provést tímto způsobem z důvodu linearity očekávané hodnoty proměnných indikátoru). To znamená, že očekávaný počet lidí s nesdílenými (jedinečnými) narozeninami je:

${\ displaystyle n \ left ({\ frac {d-1} {d}} \ right) ^ {n-1}}$

Podobné vzorce lze odvodit pro očekávaný počet lidí, kteří sdílejí tři, čtyři atd. S dalšími lidmi.

Blízké zápasy

Další zobecnění spočívá v požadavku na pravděpodobnost nalezení alespoň jednoho páru ve skupině n lidí s narozeninami do k kalendářních dnů od sebe, pokud existují d stejně pravděpodobné narozeniny.

${\ displaystyle {\ begin {zarovnáno} p (n, k, d) & = 1 - {\ frac {(d-nk-1)!} {d ^ {n-1} {\ bigl (} dn (k +1) {\ bigr)}!}} \ End {zarovnáno}}}$

Počet požadovaných osob, aby pravděpodobnost, že některý pár bude mít narozeniny oddělené k dny nebo méně, byla vyšší než 50%, je uvedena v následující tabulce:

k	n pro d = 365
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

Ve skupině pouhých sedmi náhodných lidí je tedy více než pravděpodobné, že dva z nich budou mít narozeniny do jednoho týdne od sebe.

Počet dní s určitým počtem narozenin

Počet dnů s alespoň jedním narozením

Očekávaný počet různých narozenin, tj. Počet dní, které mají narozeniny alespoň jedné osoby, je:

${\ displaystyle dd \ left ({\ frac {d-1} {d}} \ right) ^ {n}}$

Vyplývá to z očekávaného počtu dní, které nemají nikdo narozeniny:

${\ displaystyle d \ left ({\ frac {d-1} {d}} \ right) ^ {n}}$

což vyplývá z pravděpodobnosti, že konkrétní den není narozeninou, lze snadno shrnout kvůli linearitě očekávané hodnoty. ${\ displaystyle ((d-1) / d) ^ {n}}$

Například s d = 365 byste měli očekávat přibližně 21 různých narozenin, když má 22 lidí, nebo 46 různých narozenin, když je 50 lidí. Když bude mít 1 000 lidí, bude mít zhruba 341 různých narozenin (24 nevyzvednutých narozenin).

Počet dnů s alespoň dvěma narozeninami

Výše uvedené lze zobecnit z rozdělení počtu lidí s jejich narozeninami v kterýkoli konkrétní den, což je binomické rozdělení s pravděpodobností 1 / d . Vynásobením příslušné pravděpodobnosti číslem d získáte očekávaný počet dní. Například očekávaný počet dní, které jsou sdíleny; tj. které mají alespoň dva (tj. ne nulu a ani jeden) narozeniny lidí:

${\ displaystyle dd \ left ({\ frac {d-1} {d}} \ right) ^ {n} -d \ cdot {\ binom {d} {1}} \ left ({\ frac {1} { d}} \ vpravo) ^ {1} \ vlevo ({\ frac {d-1} {d}} \ vpravo) ^ {n-1} = dd \ vlevo ({\ frac {d-1} {d} } \ right) ^ {n} -d \ left ({\ frac {d-1} {d}} \ right) ^ {n-1}}$

Počet lidí, kteří opakují narozeniny

Pravděpodobnost, že k th celé číslo náhodně vybrané z [1, d ] bude opakovat alespoň jednu předchozí volbu, se rovná q ( k - 1; d ) výše. Očekávaný celkový počet případů, kdy výběr zopakuje předchozí výběr, protože n takových celých čísel je vybráno rovných

${\ displaystyle \ sum _ {k = 1} ^ {n} q (k-1; d) = n-d + d \ left ({\ frac {d-1} {d}} \ right) ^ {n }}$

Je vidět, že se to rovná počtu lidí minus očekávaný počet různých narozenin.

Průměrný počet lidí, kteří mají alespoň jedno sdílené narozeniny

V alternativní formulaci problému narozenin se člověk ptá na průměrný počet lidí potřebných k nalezení páru se stejnými narozeninami. Pokud vezmeme v úvahu pravděpodobnostní funkci Pr [ n lidé mají alespoň jedno společné narozeniny], tento průměr určuje průměr distribuce, na rozdíl od obvyklé formulace, která požaduje medián . Problém je relevantní pro několik hashovacích algoritmů analyzovaných Donaldem Knuthem ve své knize The Art of Computer Programming . Je možné ukázat, že pokud jeden vzorek rovnoměrně, s náhradou, z populace velikosti M , počet pokusů požadovaných pro první opakovaný odběr vzorku u nějaké osoby má očekávanou hodnotu n = 1 + Q ( M ) , kde

${\ displaystyle Q (M) = \ součet _ {k = 1} ^ {M} {\ frac {M!} {(Mk)! M ^ {k}}}.}$

Funkce

${\ displaystyle 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}}}}$

studoval Srinivasa Ramanujan a má asymptotickou expanzi :

${\ displaystyle 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 dní v roce je průměrný počet lidí potřebných k nalezení páru se stejnými narozeninami n = 1 + Q ( M ) ≈ 24,61659 , což je o něco více než 23, což je počet požadovaný pro 50% šanci. V nejlepším případě budou stačit dva lidé; v nejhorším případě je zapotřebí maximální možný počet M + 1 = 366 osob; ale v průměru je zapotřebí pouze 25 lidí

Analýza používající náhodné proměnné indikátoru může poskytnout jednodušší, ale přibližnou analýzu tohoto problému. Pro každý pár (i, j) pro k lidí v místnosti definujeme indikátor náhodnou proměnnou X _ij , pro , podle ${\ Displaystyle 1 \ leq já \ leq j \ leq k}$

${\ displaystyle {\ begin {alignedat} {2} X_ {ij} & = I \ {{\ text {osoba}} i {\ text {a osoba}} j {\ text {mají stejné narozeniny}} \} \\ & = {\ begin {cases} 1, & {\ text {if person}} i {\ text {and person}} j {\ text {have the same birthday;}} \\ 0, & {\ text {jinak.}} \ end {cases}} \ end {alignedat}}}$

${\ displaystyle {\ begin {alignedat} {2} E [X_ {ij}] & = \ Pr \ {{\ text {person}} i {\ text {a person}} j {\ text {mají stejné narozeniny }} \} \\ & = 1 / n \ end {alignedat}}}$

Nechť X je náhodná proměnná počítající páry jednotlivců se stejnými narozeninami.

${\ displaystyle X = \ sum _ {i = 1} ^ {k} \ sum _ {j = i + 1} ^ {k} X_ {ij}}$

${\ displaystyle {\ begin {alignedat} {3} E [X] & = \ sum _ {i = 1} ^ {k} \ sum _ {j = i + 1} ^ {k} E [X_ {ij} ] \\ & = {\ binom {k} {2}} {\ frac {1} {n}} \\ & = {\ frac {k (k-1)} {2n}} \\\ end {alignedat }}}$

Pro n = 365 , pokud k = 28 , je očekávaný počet se stejnými narozeninami Proto můžeme očekávat alespoň jeden odpovídající pár s alespoň 28 lidmi. ${\ Displaystyle (28 \ cdot 27) / (2 \ cdot 365) \ přibližně 1,0356.}$

Neformální demonstraci problému lze provést ze seznamu australských premiérů , kterých je od roku 2017 29, ve kterých sdílejí 24. předseda vlády Paul Keating a první předseda vlády Edmund Barton narozeniny, 18. ledna.

Na mistrovství světa FIFA 2014 mělo každý z 32 oddílů 23 hráčů. Analýza oficiálních seznamů týmů naznačila, že 16 oddílů mělo dvojice hráčů, které sdílely narozeniny, a z těchto 5 oddílů měly dva páry: Argentina, Francie, Írán, Jižní Korea a Švýcarsko měly vždy dva páry a Austrálie, Bosna a Hercegovina, Brazílie , Kamerun, Kolumbie, Honduras, Nizozemsko, Nigérie, Rusko, Španělsko a USA, každý s jedním párem.

Voracek, Tran a Formann ukázali, že většina lidí výrazně nadhodnocuje počet lidí, který je nezbytný pro dosažení dané pravděpodobnosti lidí, kteří mají stejné narozeniny, a výrazně podceňuje pravděpodobnost lidí, kteří mají stejné narozeniny, když je dána konkrétní velikost vzorku . Dalšími výsledky bylo, že studenti psychologie a ženy zvládli tento úkol lépe než návštěvníci / zaměstnanci kasina nebo muži, ale byli si méně jisti svými odhady.

Reverzní problém

Reverzním problémem je najít pro pevnou pravděpodobnost p největší n, pro které je pravděpodobnost p ( n ) menší než dané p , nebo nejmenší n, pro které je pravděpodobnost p ( n ) větší než dané p .

Vezmeme-li výše uvedený vzorec pro d  = 365 , jeden má

${\ displaystyle n (p; 365) \ přibližně {\ sqrt {730 \ ln \ vlevo ({\ frac {1} {1-p}} \ vpravo)}}.}$

Následující tabulka uvádí několik vzorových výpočtů.

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	8	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	30	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,03 485 √ 365 = 57,98081	57	0,99012	58	0,99166

Některé hodnoty spadající mimo hranice byly vybarveny, aby ukázaly, že aproximace není vždy přesná.

Problém s oddílem

Souvisejícím problémem je problém s oddíly , varianta batohového problému z operačního výzkumu. Některá závaží jsou uvedena na stupnici váhy ; každá váha je celé číslo gramu náhodně zvoleného mezi jedním gramem a milionem gramů (jedna tuna ). Otázkou je, zda lze obvykle (tj. S pravděpodobností blízkou 1) přenášet váhy mezi levou a pravou paží, aby se vyvážila váha. (V případě, že součet všech vah je lichý počet gramů, je povolen nesoulad jednoho gramu.) Pokud existují pouze dvě nebo tři váhy, odpověď je zcela jednoznačně ne; i když existují některé kombinace, které fungují, většina náhodně vybraných kombinací tří vah nefunguje. Pokud existuje velmi mnoho vah, odpověď je jednoznačně ano. Otázkou je, kolik jich stačí. To znamená, jaký je počet závaží, že je stejně pravděpodobné, že je možné je vyvážit, protože je nemožné?

Lidská intuice často spočívá v tom, že odpověď je výše 100 000 . Většina lidí má intuici, že se pohybuje v řádu tisíců nebo desítek tisíc, zatímco ostatní mají pocit, že by měla být alespoň v řádu stovek. Správná odpověď je 23.

Důvodem je, že správné srovnání je s počtem oddílů závaží do levé a pravé. Existují 2 různé oddíly ^{N - 1} pro N vah a levý součet mínus pravý součet lze považovat za novou náhodnou veličinu pro každý oddíl. Rozložení součtu hmotností je přibližně gaussovské , s vrcholem v1 000 000 N a šířka1 000 000 √ N , takže když 2 ^{N - 1} se přibližně rovná1 000 000 √ N dojde k přechodu. 2 ^{23 - 1} je asi 4 miliony, zatímco šířka distribuce je pouze 5 milionů.

V beletrii

Román Arthura C. Clarka Pád Moondustu , publikovaný v roce 1961, obsahuje část, kde hlavní postavy, uvězněné v podzemí na dobu neurčitou, slaví narozeniny a diskutují o platnosti problému narozenin. Jak uvedl cestující fyzik: „Máte-li skupinu více než dvaceti čtyř lidí, je pravděpodobnost lepší, než že dva z nich mají stejné narozeniny.“ Nakonec se z 22 přítomných ukázalo, že dvě postavy mají stejné narozeniny, 23. května.

Poznámky

Reference

Bibliografie

• Abramson, M .; Moser, WOJ (1970). „Další narozeninová překvapení“. Americký matematický měsíčník . 77 (8): 856–858. doi : 10,2307 / 2317022 . JSTOR  2317022 .
• Bloom, D. (1973). „Problém s narozeninami“. Americký matematický měsíčník . 80 (10): 1141–1142. doi : 10,2307 / 2318556 . JSTOR  2318556 .
• Kemeny, John G .; Snell, J. Laurie; Thompson, Gerald (1957). Úvod do konečné matematiky (první vydání).
• Klamkin, M .; Newman, D. (1967). "Prodloužení narozeninového překvapení" . Journal of Combinatorial Theory . 3 (3): 279–282. doi : 10,1016 / s0021-9800 (67) 80075-9 .
• McKinney, EH (1966). "Zobecněný problém s narozeninami". Americký matematický měsíčník . 73 (4): 385–387. doi : 10,2307 / 2315408 . JSTOR  2315408 .
• Schneps, Leila ; Colmez, Coralie (2013). "Matematická chyba číslo 5. Případ Diany Sylvesterové: analýza studeného zásahu". Math on Trial. Jak se čísla používají a zneužívají v soudní síni . Základní knihy. ISBN 978-0-465-03292-1.
• Sy M. Blinder (2013). Průvodce základní matikou: recenze pro studenty fyziky, chemie a techniky . Elsevier. s. 5–6. ISBN 978-0-12-407163-6.

externí odkazy

• The Birthday Paradox účtuje narozeniny v přestupném roce
• Weisstein, Eric W. „Narozeninový problém“ . MathWorld .
• Vtipný článek vysvětlující paradox
• Narozeninový experiment aktivit SOCR EduMaterials
• Porozumění problému s narozeninami (lépe vysvětleno)
• Eurobirthdays 2012. Narozeninový problém. Praktický fotbalový příklad narozeninového paradoxu.
• Špína, James. „23: Pravděpodobnost narozenin“ . Numberphile . Brady Haran . Archivovány od originálu na 2017-02-25 . Citováno 2013-04-02 .
• Výpočet pravděpodobnosti problému k narozeninám ve WolframAlpha