Födelsedagsparadoxen

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 februari 2022; kontroller kräver 2 redigeringar .

Födelsedagsparadoxen är ett påstående om att i en grupp på 23 eller fler personer överstiger sannolikheten för sammanträffande av födelsedagar (dag och månad) för minst två personer 50 % . Till exempel, om det finns 23 eller fler elever i en klass är det mer troligt att ett par klasskamrater fyller år samma dag än att var och en har en unik födelsedag [1] . Detta problem övervägdes först av Richard Mises 1939 [2] [3] .

För 57 eller fler personer överstiger sannolikheten för en sådan sammanträffande 99% , även om den når 100% , enligt Dirichlet-principen (sunt förnuft), endast när det finns minst 367 personer i gruppen (exakt 1 fler än antalet antal dagar under ett skottår ; med hänsyn tagen till skottår ).

Ett sådant uttalande kan tyckas icke-uppenbart, eftersom sannolikheten att två personers födelsedagar sammanfaller med vilken dag som helst på året , multiplicerat med antalet personer i gruppen (23), endast ger . Detta resonemang är felaktigt, eftersom antalet möjliga par avsevärt överstiger antalet personer i gruppen ( 253 > 23 ). Således är uttalandet inte en paradox i strikt vetenskaplig mening: det finns ingen logisk motsägelse i det, och paradoxen ligger bara i skillnaderna mellan en persons intuitiva uppfattning av situationen och resultaten av en matematisk beräkning. $({\tfrac {1}{365}}=0{,}27\,\%)$ ${\tfrac {1}{365}}\times 23=6{,}3\,\%$ $({\tfrac {23\times 22}{2}}=253)$

Intuitiv perception

I en grupp på 23 personer är sannolikheten för att två personer ska ha samma födelsedag så hög eftersom sannolikheten för att två personer i gruppen ska ha samma födelsedag beaktas. Denna sannolikhet bestäms av antalet par personer som kan utgöras av 23 personer. Eftersom ordningen på personer i par inte spelar någon roll, är det totala antalet sådana par lika med antalet kombinationer av 23 gånger 2, det vill säga (23 × 22) / 2 = 253 par .

I formuleringen av paradoxen talar vi om sammanträffandet av födelsedagar för två av gruppens medlemmar. En vanlig missuppfattning är att detta fall förväxlas med ett annat till synes liknande fall där en person väljs från en grupp och sannolikheten att födelsedagen för andra medlemmar i gruppen kommer att sammanfalla med födelsedagen för den valda personen uppskattas. I det senare fallet är sannolikheten för en matchning mycket lägre.

Sannolikhetsberäkning

Det krävs för att bestämma sannolikheten att i en grupp av n personer har minst två av dem samma födelsedag.

Låt födelsedagarna fördelas jämnt , det vill säga vi antar att:

det finns 365 dagar på ett år (inga skottår );
det finns inga personer i gruppen som uppenbarligen föddes samma dag (till exempel tvillingar );
födelsetalen beror inte på veckodag, tid på året och andra faktorer.

I verkligheten är detta inte helt sant - i synnerhet i vissa länder, på grund av sjukhusens natur , föds fler barn vissa dagar i veckan. Men ojämn fördelning kan bara öka sannolikheten för sammanträffande av födelsedagar, men inte minska: om alla människor föddes endast på 3 dagar av 365, då skulle sannolikheten för sammanträffande av födelsedagar vara mycket hög.

Låt oss först beräkna sannolikheten att i en grupp människor kommer alla människors födelsedagar att vara olika. Om , då, i kraft av Dirichlet-principen , är sannolikheten noll. Om , då kommer vi att argumentera enligt följande. Låt oss slumpmässigt ta en person från gruppen och komma ihåg hans födelsedag. Sedan tar vi den andra personen slumpmässigt, medan sannolikheten att hans födelsedag inte sammanfaller med den första personens födelsedag är lika med . Ta sedan den tredje personen; sannolikheten att hans födelsedag inte kommer att sammanfalla med födelsedagen för en av de två första är lika med . Genom att argumentera analogt kommer vi att nå den sista personen för vilken sannolikheten för en oöverensstämmelse mellan hans födelsedag och alla föregående kommer att vara lika med . Multiplicerar vi alla dessa sannolikheter får vi sannolikheten att alla födelsedagar i gruppen kommer att vara olika: ${\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!  \över 365^{n}(365-n)!}.

Då är sannolikheten att minst två personer av n har samma födelsedag lika med

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

Värdet på denna funktion överstiger 1/2 vid , medan sannolikheten för tillfällighet är cirka 50,73 %, och . Listan över n värden och deras motsvarande sannolikheter ges i följande tabell. $n=23$ $p(22)\approx 47.57\%$

n	p ( n )
tio	12 %
tjugo	41 %
trettio	70 %
femtio	97 %
100	99,99996 %
200	99,999999999999999999999999999998 %
300	(1 − 7×10 −73 ) × 100 %
350	(1 − 3×10 −131 ) × 100 %
367	100 %

Detta problem kan omformuleras i termer av det klassiska "slumpproblemet". Låta:

urnan innehåller bollar (i detta fall antalet dagar på ett år, antas vara 365 dagar); $M$ $M$
bollar numrerade 1, 2, …, ; $M$
flera prover är gjorda av n bollar från urnan (i detta fall är n antalet personer i gruppen);
de tillbakadragna kulorna returneras till urnan efter varje val;
proverna anses vara beställda, det vill säga proverna och anses olika. $\{ 1, 2, 4, 6 \}$ $\{ 4, 2, 6, 1 \}$

Det krävs att man beräknar sannolikheten för en händelse som består i frånvaro av upprepningar i urvalet. Alla beräkningar är desamma som ovan .

Alternativ metod

Sannolikheten för att två personer i en grupp av n ska ha samma födelsedag kan också beräknas med hjälp av kombinatoriska formler [4] . Föreställ dig att varje dag på året är en bokstav i alfabetet, och alfabetet består av 365 bokstäver. Födelsedagar för n personer kan representeras av en sträng som består av n bokstäver i detta alfabet. Enligt Hartleys formel är antalet möjliga rader

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

Antalet möjliga strängar där bokstäver inte upprepas ( placering av 365 gånger n ) kommer att vara

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

Om raderna väljs slumpmässigt (med en enhetlig fördelning ) är sannolikheten att välja en rad där minst två bokstäver matchar

p(n)=1-{\frac {n_{\text{unik))}{n_{\text{totalt))))=1-{\frac {\frac {365!}{(365 -n)!}}{365^{n}}}

vid och

n\leqslant 365

p(n)=1

kl .

n>365

På det här sättet,

{\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),

och detta uttryck är ekvivalent med det som presenteras ovan .

Dessutom kan det totala antalet möjliga rader beräknas med hjälp av den kombinatoriska formeln för antalet placeringar med upprepningar A (upprepningar)  n /365 = 365 n .

Approximationer

Exponentiell funktion

Med hjälp av Taylor-seriens expansion av exponentialfunktionen

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

Ovanstående uttryck för kan approximeras enligt följande: ${\bar p}(n)$

{\bar p}(n)\approx 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 } } .

Följaktligen:

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

Observera att den förenklade approximationen

p(n)\approx 1-e^{{-{\frac {n^{2}}{2\cdot 365}}}},

som du kan se från grafen ger den fortfarande tillräcklig noggrannhet.

Låt oss ge ytterligare en uppskattning .

Sannolikheten att två personer har samma födelsedag är 364/365. I en grupp människor , par. Därför kan sannolikheten , förutsatt att dessa händelser är oberoende , approximeras med antalet $n$ $C(n,2)={\frac {n(n-1)}{2}}$ ${\bar p}(n)$

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

Därför får vi en approximation för den erforderliga sannolikheten p ( n ) :

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

Poisson approximation

Genom att använda Poisson- approximationen för binomialen , baserat på den tidigare approximationen för , får vi lite mer än 50 % : $p(n)$

\operatörsnamn{Poi} \left( \frac{ C(23,2) }{365} \right) = \operatörsnamn{Poi} \left( \frac{253}{365} \right) \approx \operatörsnamn{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 .

Beräkning av antalet personer där sannolikheten är 50 %

Låt oss uttrycka n från formeln ovan . Sedan, istället för p ( n ), ersätter vi 50 % (0,5). Som ett resultat får vi: ${\displaystyle p(n)=1-{\bar {p}}(n)\approx 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.

Det finns ett annat sätt att uppskatta n med 50 % sannolikhet . Som bevisats ovan :

{\bar {p}}(n)=1-p(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}} \höger).

Hitta det minsta n för vilket

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

eller, vilket är detsamma,

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

Låt oss använda ovanstående approximation av funktionen med ${\bar p}(n)$ exponentialfunktionen :

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

Ersätter istället i uttrycket får vi ${\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}}.

Att lösa för n får vi

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

Härifrån hittar vi n och avrundar uppåt till ett heltal :

n =23 .

Född samma dag som en given person

Låt oss jämföra sannolikheten p ( n ) med sannolikheten att i en grupp på n personer kommer födelsedagen för någon person från gruppen att sammanfalla med födelsedagen för någon förvald person som inte tillhör gruppen. Denna sannolikhet är

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

Genom att ersätta n = 23 får vi q ( n ) ≈ 6,12 % . För att sannolikheten q ( n ) ska överstiga 50 % måste antalet personer i gruppen vara minst 253 ( q (252) ≈ 49,91 % ; q (253) ≈ 50,05 % ). Detta antal är mer än hälften av årets dagar ( 365/2 = 182,5 ); detta beror på att andra medlemmar i gruppen kan ha samma födelsedag, och detta minskar sannolikheten q ( n ) . Närmare bestämt beror detta på det faktum att när vi adderar sannolikheterna för tillfälligheter, subtraherar vi varje gång sannolikheten för den gemensamma förekomsten av dessa händelser, eftersom händelserna är gemensamma och sannolikheten för deras gemensamma förekomst i additionen tas med i beräkningen dubbelt. P ( A + B ) = P ( A ) + P ( B ) − P ( AB ) och så vidare med varje tillägg av en ny term.

Generaliseringar

Sammanfall av diskreta slumpvariabler

Det beskrivna problemet kan formuleras i allmän form:

givna slumptal;
slumpmässiga tal fördelas enhetligt i intervallet från 1 till d ;
n är antalet slumptal;
bestäm p ( n ; d ) - sannolikheten att minst två av de givna talen kommer att matcha.

Om du resonerar på samma sätt som beskrivs ovan kan du få allmänna lösningar:

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

p(n;d)\ungefär 1-e^{{-(n(n-1))/2d}};

q(n;d)=1-\vänster({\frac {d-1}{d}}\höger)^{n}.

Omvänt problem:

givet p är sannolikheten att minst två slumpmässiga tal matchar;
det är känt att slumptal är likformigt fördelade i intervallet från 1 till d ;
hitta n ( p ; d ) — antalet slumptal.

Lösning:

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

Flera typer av människor

Ovan presenterades födelsedagsparadoxen för en "typ" människor. Det är möjligt att generalisera problemet genom att introducera flera "typer", till exempel att dela in människor i manliga ( m ) och kvinnliga ( n ). Låt oss beräkna sannolikheten för att minst en kvinna och en man har samma födelsedag (sammanträffande av födelsedagar för två kvinnor eller två män beaktas inte):

p_{0}=1-{\frac {1}{d^{{m+n))))\summa _{{i=1}}^{m}\summa _{{j=1}}^ {n}S_{2}(m,i)S_{2}(n,j)\prod _{{k=0}}^{{i+j-1}}(dk),

där d \u003d 365 och S 2 () är Stirlingtal av det andra slaget . Intressant nog finns det inget entydigt svar på frågan om värdet av n + m för en given sannolikhet. Till exempel ger en sannolikhet på 0,5 både en uppsättning av 16 män och 16 kvinnor, och en uppsättning av 43 män och 6 kvinnor.

Närliggande födelsedagar

En annan generalisering av födelsedagsparadoxen är att ange problemet med hur många personer som krävs för att sannolikheten att ha i en grupp människor vars födelsedagar inte skiljer sig mer än en dag (eller två, tre dagar, och så vidare) överstiger 50 % . När man löser detta problem används principen om inkludering-uteslutning . Resultatet (igen om vi antar att födelsedagar är jämnt fördelade ) är:

Maximal skillnad i födelsedagar, antal dagar	Nödvändigt antal personer
ett	23
2	fjorton
3	elva
fyra	9
5	åtta
6	åtta
7	7
åtta	7

Således överstiger sannolikheten att även i en grupp på 7 personer födelsedagarna för minst två av dem inte kommer att skilja sig med mer än en vecka 50% .

Applikation

Födelsedagsparadoxen gäller generellt för hashfunktioner : om en hashfunktion genererar ett N -bitarsvärde, då är antalet slumpmässiga ingångar för vilka hashkoder högst sannolikt kommer att kollidera (det vill säga att det finns lika hashkoder som erhålls på olika indata ) är inte 2 N , utan endast cirka 2 N /2 . Denna observation utnyttjas i en attack mot kryptografiska hashfunktioner som kallas födelsedagsattacken .

N	Antal olika utgående kedjor (2 N )	Sannolikhet för minst en kollision ( p )
N	Antal olika utgående kedjor (2 N )	10 −18	10 −15	10 −12	10 −9	10 −6	0,1 %	ett %	25 %	femtio %	75 %
32	4,3 × 109	2	2	2	2.9	93	2,9×10³	9,3×10³	5,0×10⁴	7,7×10⁴	1,1x10⁵
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

De vita cellerna indikerar antalet personer i gruppen där en kollision kommer att inträffa med en given sannolikhet (i analogi med paradoxen är antalet utgående kedjor 365).

En liknande matematisk apparat används för att uppskatta populationsstorleken för fiskar som lever i sjöar . Metoden kallas "capture-recapture" ("fånga - fånga igen"). Faktum är att om varje fångad fisk markeras och släpps ut, kommer sannolikheten att fånga en markerad fisk att växa icke-linjärt (i enlighet med diagrammet ovan) med en ökning av antalet försök. Populationsstorleken kan grovt uppskattas som kvadraten på antalet försök som gjorts innan den första märkta fisken fångas.

Lösningen av problemet i allmänna termer finner tillämpning inom många grenar av matematiken , till exempel i icke-deterministiska faktoriseringsalgoritmer . Så, en av de enklaste förklaringarna av Pollards ρ-metod liknar förklaringen av födelsedagsparadoxen: det räcker med att ha ungefär slumpmässiga tal från 0 till , där är primtal, så att för åtminstone ett av talparen med hög sannolikhet finns , vilket kommer att vara en divisor av talet n . $\sqrt{p}$ $n=pq$ $p<q$ $\gcd \left(|xy|,n\right)>1$

Omvända problem

Att hitta det minsta talet n så att sannolikheten p ( n ) är större än ett givet tal p .

Att hitta det största talet n så att sannolikheten p ( n ) är mindre än ett givet tal p .

Med formeln ovan får vi:

n(s;365)\approx {\sqrt {2\cdot 365\cdot \ln \left({1 \över 1-p}\höger))).

sid	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	åtta	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	trettio	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

Den bästa positionen

Låt det vara n - 1 personer i rummet, och deras födelsedagar är olika. Låt g ( n ) vara sannolikheten att födelsedagen för personen som kom in är densamma som födelsedagen för någon närvarande i rummet. Det krävs att hitta värdet på n där värdet på funktionen g ( n ) är maximalt.

Lösningen handlar om att hitta det maximala värdet för uttrycket

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

Med formeln ovan för p ( n ) får vi n = 20 .

Genomsnittligt antal personer

Låt oss överväga ett annat problem. Hur många personer krävs i genomsnitt för att minst två av dem har samma födelsedag?

Detta problem hade att göra med hashalgoritmer och undersöktes av Donald Knuth . Det visar sig att den för oss intressanta slumpvariabeln har en matematisk förväntan lika med

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

var

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

Fungera

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))))

utforskades av Ramanujan . Han erhöll också följande asymptotiska expansion för denna funktion :

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

Med M = 365 är det genomsnittliga antalet personer

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

Detta antal är något större än antalet personer som ger 50 % chans . Överraskande nog är det nödvändiga antalet personer M + 1 = 366 (för 365 personer kan deras födelsedagar fördelas över var och en av årets 365 dagar utan överlappning), även om det i genomsnitt bara behövs 25.

Se även

Anteckningar

↑ Mazur, 2017 , sid. 116.
↑ Mazur, 2017 , sid. 119.
↑ Mironkin V. O., Chukhno A. B. Om en generalisering av "födelsedagar"-paradoxen . Hämtad 30 mars 2020. Arkiverad från originalet 9 juli 2020. (obestämd)
↑ Mazur, 2017 , sid. 117.

Litteratur

Kemeny J. , Snell J., Thompson J. Introduction to Finite Mathematics = Introduction to Finite Mathematics. - Förlag för utländsk litteratur, 1963. - 488 sid.
Kozlov MV Inslag av sannolikhetsteorin i exempel och problem. - Moscow State University, 1990 . — ISBN 5-211-00312-8 .
Mazur, Joseph. Födelsedagsproblem // Hasardspel. Matematik och slumpens mytologi. - Alpina facklitteratur, 2017. - S. 116-123. — 292 sid. - ISBN 978-5-91671-636-8 .
Sekey G. Paradoxer i sannolikhetsteori och matematisk statistik. - RHD, 2003 . — ISBN 5-93972-150-8 .
Shiryaev A. N. Sannolikhet-1. - MTsNMO, 2007 . - ISBN 978-5-94057-036-3 .
Goldberg S. En direkt attack mot ett födelsedagsproblem // Mathematical Mathematics Magazine. — maj 1976 . — Iss. 49 . - S. 130-132 .

Mosteller F. Att förstå födelsedagsproblemet // Matematikläraren. — maj 1962 . - S. 322-325 . _

Länkar

Paradoxer av sannolikhetsteorin .
Jämförande genomgång av PGP-algoritmer. "Födelsedagar"-paradoxen och kryptografins säkerhet .
Eurobirthdays 2012 (engelska) . Praktiskt exempel.