Problém s narozeninami - Birthday problem

v teorie pravděpodobnosti, narozeninový problém nebo narozeninový paradox týká se pravděpodobnost že v sadě n náhodně vybraní lidé, některé z nich budou mít stejné narozeniny. Podle princip 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 ). Pravděpodobnosti 99,9% je však dosaženo pouze u 70 osob a 50% pravděpodobnosti u 23 osob. Tyto závěry jsou založeny na předpokladu, že každý den v roce (s výjimkou 29. února) je stejně pravděpodobný pro narozeniny.
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ě.[1] Například pokud se polovina lidí narodila v jeden den a druhá polovina v jiný den, pak vůbec dva lidé by měli 50% šanci sdílet narozeniny.
Může se zdát překvapivé, že skupina pouhých 23 jedinců musí dosáhnout 50% pravděpodobnosti, že alespoň dva jedinci ve skupině mají stejné narozeniny: tento výsledek je možná pravděpodobnější, když vezmeme v úvahu, že srovnání narozenin bude mezi každým možným párem jednotlivců = 23 × 22/2 = 253 srovnání, což je výrazně více než poloviční počet dní v roce (maximálně 183), na rozdíl od fixace na jednoho jednotlivce a porovnání jeho narozenin s všichni ostatní. Problém s narozeninami neníparadox „v doslovném logickém smyslu, že si odporuje, ale na první pohled je pouze neintuitivní.
Skutečné aplikace pro problém s narozeninami zahrnují kryptografický útok zvaný narozeninový útok, který používá tento pravděpodobnostní model ke snížení složitosti hledání a srážka pro hashovací funkce, jakož i výpočet přibližného rizika kolize hash existující v haších dané velikosti populace.
Historie problému je nejasná. Výsledek byl připsán Harold Davenport;[2] verzi verze, která je dnes považována za problém narozenin, však navrhl dříve Richard von Mises.[3]
Výpočet pravděpodobnosti
Problém je spočítat přibližnou pravděpodobnost, že ve skupině n lidé alespoň dva mají stejné narozeniny. Pro jednoduchost, variace v distribuci, jako např přestupné roky, dvojčata, sezónní variace nebo variace v pracovní dny nejsou brány v úvahu 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ě není jednotná, protože ne všechna data jsou stejně pravděpodobná, ale tyto nesrovnalosti mají malý vliv na analýzu.[poznámka 1] Ve skutečnosti je nejhorší případ jednotného rozdělení dat narození.[5])
Cílem je počítat P(A), pravděpodobnost, že alespoň dva lidé v místnosti mají stejné narozeniny. Výpočet je však jednodušší P(A′), pravděpodobnost, že žádní dva lidé v místnosti nebudou mít stejné narozeniny. Potom, protože A a A′ jsou jediné dvě možnosti a jsou také vzájemně se vylučující, P(A) = 1 − P(A′).
V úctě k široce publikovaným řešením[který? ] k závěru, že 23 je minimální počet lidí nezbytných pro a P(A) to je více než 50%, následující výpočet P(A) použije jako příklad 23 lidí. Pokud jedna čísla 23 lidí od 1 do 23, událost že všech 23 lidí má jiné narozeniny, je stejné jako v případě, že osoba 2 nemá stejné narozeniny jako osoba 1 a tato osoba 3 nemá stejné narozeniny jako osoba 1 nebo osoba 2 atd. a nakonec 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“, odpovídající události osoby 1, která má narozeniny a která nastane s pravděpodobností 1. Tuto spojku událostí lze vypočítat pomocí podmíněná pravděpodobnost: pravděpodobnost události 2 je 364/365, protože osoba 2 může mít jiné narozeniny než narozeniny osoby 1. Podobně pravděpodobnost události 3 vzhledem k tomu, že k události 2 došlo, je 363/365, protože osoba 3 může mít kteroukoli z narozeniny, které osoby 1 a 2 dosud nebral A konečně, ze zásady podmíněné pravděpodobnosti to vyplývá P(A′) se rovná součinu těchto individuálních pravděpodobností:
(1)
Podmínky rovnice (1) lze vyzvednout na adrese:
(2)
Vyhodnocovací rovnice (2) dává P(A′) ≈ 0.492703
Proto, P(A) ≈ 1 − 0.492703 = 0.507297 (50.7297%).
Tento proces lze zobecnit na skupinu n lidi, kde str(n) je pravděpodobnost alespoň dvou z n lidé sdílející narozeniny. Je snazší nejprve vypočítat pravděpodobnost str(n) to všechno n narozeniny jsou odlišný. Podle princip pigeonhole, str(n) je nula, když n > 365. Když n ≤ 365:
kde ! je faktoriál operátor, (365
n) je binomický koeficient a kPr označuje permutace.
Rovnice vyjadřuje skutečnost, že první osoba nemá nikoho, kdo by měl 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ě nth narozeniny nemohou být stejné jako kterékoli z n − 1 předchozí narozeniny.
The událost nejméně dvou z n osoby se stejnými narozeninami jsou komplementární všem n narozeniny jsou jiné. Proto je jeho pravděpodobnost str(n) je
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é):

n str(n) 1 0.0% 5 2.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.99997% 200 99.9999999999999999999999999998% 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%.
Aproximace


The Taylor série rozšíření exponenciální funkce (konstanta E ≈ 2.718281828)
poskytuje aproximaci prvního řádu pro EX pro :
Aplikovat tuto aproximaci na první výraz odvozený pro str(n), nastavit X = −A/365. Tím pádem,
Poté vyměňte A s nezápornými celými čísly pro každý člen ve vzorci str(n) dokud A = n − 1například když A = 1,
První výraz odvozený pro str(n) lze aproximovat jako
Proto,
Ještě hrubší aproximace je dána vztahem
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 existují n osob, a pokud n ≪ d, pak pomocí stejného přístupu jako výše dosáhneme výsledku, že pokud str(n, d) je pravděpodobnost, že alespoň dva z n lidé sdílejí stejné narozeniny ze sady d dostupné dny, pak:
Jednoduchá umocňování
Pravděpodobnost, že by dva lidé neměli stejné narozeniny, je 364/365. V místnosti obsahující n lidé, jsou (n
2) = n(n − 1)/2 páry lidí, tj. (n
2) 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 zkratce 364/365 lze znásobit sám (n
2) krát, což nám dává
Jelikož se jedná o pravděpodobnost, že nikdo nebude mít stejné narozeniny, pak je pravděpodobnost, že někdo bude mít narozeniny
Poissonova aproximace
Uplatnění jed přibližný odhad pro dvojčlen ve skupině 23 lidí,
tak
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á .
Čtvercová aproximace
Dobrý pravidlo pro které lze použít mentální výpočet je vztah
které lze také zapsat jako
který funguje dobře pro pravděpodobnosti menší nebo rovné 1/2. V těchto rovnicích m je počet dní v roce.
Například k odhadu počtu lidí potřebných pro a 1/2 šanci na společné narozeniny, máme
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 číslo lidí nutných mít alespoň a 1/2 šance na shodu:
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 2 krát.[6]
Pravděpodobnostní tabulka
délka
šestihranný řetězecNe. z
bity
(b)hash prostor
velikost
(2b)Počet hašovaných prvků, takže pravděpodobnost alespoň jedné hašovací srážky ≥str str = 10−18 str = 10−15 str = 10−12 str = 10−9 str = 10−6 str = 0.001 str = 0.01 str = 0.25 str = 0.50 str = 0.75 8 32 4.3×109 2 2 2 2.9 93 2.9×103 9.3×103 5.0×104 7.7×104 1.1×105 (10) (40) (1.1×1012) 2 2 2 47 1.5×103 4.7×104 1.5×105 8.0×105 1.2×106 1.7×106 (12) (48) (2.8×1014) 2 2 24 7.5×102 2.4×104 7.5×105 2.4×106 1.3×107 2.0×107 2.8×107 16 64 1.8×1019 6.1 1.9×102 6.1×103 1.9×105 6.1×106 1.9×108 6.1×108 3.3×109 5.1×109 7.2×109 (24) (96) (7.9×1028) 4.0×105 1.3×107 4.0×108 1.3×1010 4.0×1011 1.3×1013 4.0×1013 2.1×1014 3.3×1014 4.7×1014 32 128 3.4×1038 2.6×1010 8.2×1011 2.6×1013 8.2×1014 2.6×1016 8.3×1017 2.6×1018 1.4×1019 2.2×1019 3.1×1019 (48) (192) (6.3×1057) 1.1×1020 3.5×1021 1.1×1023 3.5×1024 1.1×1026 3.5×1027 1.1×1028 6.0×1028 9.3×1028 1.3×1029 64 256 1.2×1077 4.8×1029 1.5×1031 4.8×1032 1.5×1034 4.8×1035 1.5×1037 4.8×1037 2.6×1038 4.0×1038 5.7×1038 (96) (384) (3.9×10115) 8.9×1048 2.8×1050 8.9×1051 2.8×1053 8.9×1054 2.8×1056 8.9×1056 4.8×1057 7.4×1057 1.0×1058 128 512 1.3×10154 1.6×1068 5.2×1069 1.6×1071 5.2×1072 1.6×1074 5.2×1075 1.6×1076 8.8×1076 1.4×1077 1.9×1077
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 lidí 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−18 na 10−15 je neopravitelná bitová chybovost typického pevného disku.[7] Teoreticky jsou 128bitové hash funkce, jako např MD5, by měl zůstat v tomto rozsahu do asi 8.2×1011 dokumenty, 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 Paul Halmos.[pozn. 2]
Jak je uvedeno výše, pravděpodobnost, že se žádné dva narozeniny neshodují, je
Stejně jako v předchozích odstavcích je zájem nejmenší n takhle str(n) > 1/2; nebo ekvivalentně nejmenší n takhle str(n) < 1/2.
Použití nerovnosti 1 − X < E−X ve výše uvedeném výrazu nahradíme 1 − k/365 s E−k⁄365. To přináší
Výše uvedený výraz tedy není jen aproximací, ale také horní hranice z str(n). Nerovnost
naznačuje str(n) < 1/2. Řešení pro n dává
Nyní, 730 ln 2 je přibližně 505 997, což je sotva pod 506, což je hodnota n2 − n dosaženo, když n = 23. Postačuje tedy 23 lidí. Mimochodem, řešení n2 − n = 730 ln 2 pro n poskytuje přibližný vzorec Franka H. Mathise citovaného výše.
Toto odvození to pouze ukazuje nejvíce K zajištění narozeninového zápasu s rovnoměrnou šancí je zapotřebí 23 lidí; ponechává otevřenou možnost, že n je 22 nebo méně může také fungovat.
Zobecnění
Zobecněný problém s narozeninami
Vzhledem k tomu, rok s d dny zobecněný problém s narozeninami požádá o minimální počet n(d) takové, že v sadě n náhodně vybraných lidí, je pravděpodobnost narozeninové shody minimálně 50%. Jinými slovy, n(d) je minimální celé číslo n takhle
Klasický narozeninový problém tedy odpovídá určení n(365). Prvních 99 hodnot n(d) jsou uvedeny zde (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
To ukazuje podobný výpočet n(d) = 23 kdy d je v rozmezí 341–372.
Řada hranic a vzorců pro n(d) byly zveřejněny.[8]Pro všechny d ≥ 1, číslo n(d) splňuje[9]
Tyto hranice jsou optimální v tom smyslu, že posloupnost n(d) − √2d ln 2dostane libovolně blízko
zatímco má
jako jeho maximum, vzato za d = 43.
Hranice jsou dostatečně těsné, aby poskytly přesnou hodnotu n(d) například v 99% všech případů n(365) = 23. Z těchto mezí obecně vyplývá, že n(d) vždy se rovná buď
kde ⌈ · ⌉ označuje stropní funkce Vzorec
platí pro 73% všech celých čísel d.[10] Vzorec
platí pro téměř všechny d, tj. pro sadu celých čísel d s asymptotická hustota 1.[10]
Vzorec
platí pro všechny d ≤ 1018, ale předpokládá se, že tohoto vzorce je nekonečně mnoho.[11]
Vzorec
platí pro všechny d ≤ 1018a předpokládá se, že tento vzorec platí pro všechny d.[11]
Více než 2 lidé
Je možné rozšířit problém a zeptat se, kolik lidí ve skupině je potřeba, 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, že 4 lidé budou sdílet narozeniny - 187 lidí. Celý seznam lze najít jako sekvenci A014088 Online encyklopedie celočíselných sekvencí.[12]
Obsazení jako problém s kolizí
Problém s narozeninami lze zobecnit takto:
- Dáno n náhodná celá čísla získaná z a diskrétní rovnoměrné rozdělení s rozsahem [1,d], jaká je pravděpodobnost str(n; d) že alespoň dvě čísla jsou stejná? (d = 365 dává obvyklý problém s narozeninami.)[13]
Obecné výsledky lze odvodit pomocí stejných argumentů, které jsou uvedeny výše.
Naopak, pokud n(str; d) označuje počet náhodných celých čísel čerpaných z [1,d] získat pravděpodobnost str že tedy alespoň dvě čísla jsou stejná
Problém narozenin v tomto obecnějším smyslu platí pro hashovací funkce: očekávaný počet N-bit hash, které lze generovat před srážkou, není 2N, ale spíše jen 2N⁄2. Toto využívá narozeninové útoky na kryptografické hashovací funkce a je důvodem, proč malý počet kolizí v a hash tabulka jsou z praktických důvodů nevyhnutelné.
Teorii, která stála za problémem narozenin, použila Zoe Schnabel[14] pod jménem zajmout-znovuzískat statistiky pro odhad velikosti populace ryb v jezerech.
Zobecnění na více typů

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ů.[15] V nejjednodušším rozšíření existují dva typy lidí m muži a n problémem se stává charakterizace pravděpodobnosti sdílených narozenin mezi alespoň 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
kde d = 365 a S2 jsou Stirlingova čísla druhého druhu. V důsledku toho je požadovaná pravděpodobnost 1 − str0.
Tato variace narozeninového problému je zajímavá, protože pro celkový počet lidí neexistuje jedinečné řešení 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á, za co n je str(n) − str(n − 1) maximum? Odpověď je 20 - pokud existuje cena za první zápas, nejlepší pozice v řadě je 20..[Citace je zapotřebí ]
Stejné narozeniny jako ty

V případě problému s narozeninami není ani jeden ze dvou lidí vybrán předem. Naopak pravděpodobnost q(n) ten někdo v místnosti n ostatní lidé mají stejné narozeniny jako a konkrétní osoba (například vy) je dána uživatelem
a obecně d podle
Ve standardním případě d = 365, střídání n = 23 dává asi 6,1%, což je méně než 1 šance v 16. Pro více než 50% šanci, že jedna osoba v místnosti n lidé mají 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.
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 uvnitř k kalendářní dny navzájem, pokud existují d stejně pravděpodobné narozeniny.[16]
Počet požadovaných osob, aby byla pravděpodobnost, že některý pár bude mít narozeniny odděleny k počet dní nebo méně bude vyšší než 50% je uveden v následující tabulce:
k n
pro d = 3650 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.[16]
Počítání kolizí
Pravděpodobnost, že kcelé číslo náhodně vybrané z [1,d] bude opakovat alespoň jedna předchozí volba rovná se q(k − 1; d) výše. Očekávaný celkový počet opakování výběru jako předchozí n taková celá čísla jsou zvolena rovná[17]
Průměrný počet lidí
Při alternativní formulaci problému s narozeninami se člověk ptá 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 sdílené narozeniny], toto průměrný určuje znamenat distribuce, na rozdíl od obvyklé formulace, která požaduje medián. Problém je relevantní pro několik hashovací algoritmy analyzováno Donald Knuth ve své knize Umění počítačového programování. Může se zobrazit[18][19] že pokud jeden vzorkuje jednotně, s náhradou, z populace velikosti M, počet pokusů požadovaných pro první opakovaný odběr vzorků nějaký jednotlivec má očekávaná hodnota n = 1 + Q(M), kde
Funkce
byl studován uživatelem Srinivasa Ramanujan a má asymptotická expanze:
S 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, o něco více než 23, počet požadovaný pro 50% šanci. V nejlepším případě budou stačit dva lidé; v nejhorším případě maximální možný počet M + 1 = 366 lidé jsou potřební; 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.[20] Pro každý pár (i, j) pro k lidí v místnosti definujeme indikátor náhodnou proměnnou Xij, pro tím, že