Fødselsdagsparadokset

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. februar 2022; checks kræver 2 redigeringer .

Fødselsdagsparadokset er et udsagn om, at i en gruppe på 23 eller flere personer overstiger sandsynligheden for sammenfald af fødselsdage (dag og måned) for mindst to personer 50 % . For eksempel, hvis der er 23 eller flere elever i en klasse , så er det mere sandsynligt, at et par klassekammerater har fødselsdag på samme dag, end at hver enkelt har en unik fødselsdag [1] . Dette problem blev først overvejet af Richard Mises i 1939 [2] [3] .

For 57 eller flere personer overstiger sandsynligheden for en sådan tilfældighed 99% , selvom den når 100% ifølge Dirichlet-princippet (sund fornuft), kun når der er mindst 367 personer i gruppen (præcis 1 mere end antallet af dage i et skudår ; med hensyntagen til skudår ) .

Et sådant udsagn kan virke ikke-oplagt, da sandsynligheden for, at to personers fødselsdage falder sammen med en hvilken som helst dag på året , ganget med antallet af personer i gruppen (23), kun giver . Dette ræsonnement er forkert, da antallet af mulige par væsentligt overstiger antallet af personer i gruppen ( 253 > 23 ). Udsagnet er således ikke et paradoks i streng videnskabelig forstand: der er ingen logisk modsigelse i det, og paradokset ligger kun i forskellene mellem en persons intuitive opfattelse af situationen og resultaterne af en matematisk beregning. $({\tfrac {1}{365}}=0{,}27\,\%)$ ${\tfrac {1}{365}}\times 23=6{,}3\,\%$ $({\tfrac {23\times 22}{2}}=253)$

Intuitiv opfattelse

I en gruppe på 23 personer er sandsynligheden for, at to personer har samme fødselsdag, så høj, fordi der tages højde for sandsynligheden for, at to personer i gruppen har samme fødselsdag. Denne sandsynlighed bestemmes af antallet af personpar , der kan bestå af 23 personer. Da rækkefølgen af personer i par ikke betyder noget, er det samlede antal af sådanne par lig med antallet af kombinationer af 23 gange 2, det vil sige (23 × 22) / 2 = 253 par .

I formuleringen af paradokset taler vi om sammenfaldet af fødselsdage for alle to medlemmer af gruppen. En almindelig misforståelse er, at denne sag forveksles med en anden tilsyneladende lignende sag, hvor en person er udvalgt fra en gruppe, og sandsynligheden for, at fødselsdagen for andre medlemmer af gruppen vil falde sammen med den valgte persons fødselsdag. I sidstnævnte tilfælde er sandsynligheden for et match meget lavere.

Sandsynlighedsberegning

Det er nødvendigt at bestemme sandsynligheden for, at i en gruppe på n personer har mindst to af dem samme fødselsdag.

Lad fødselsdagene fordele sig ligeligt , det vil sige, vi antager, at:

der er 365 dage i et år (ingen skudår );
der er ingen personer i gruppen, der åbenlyst er født samme dag (f.eks. tvillinger );
fødselsraten afhænger ikke af ugedag, tidspunkt på året og andre faktorer.

I virkeligheden er dette ikke helt sandt - især i nogle lande bliver der på grund af hospitalernes karakter født flere børn på bestemte dage i ugen. Ujævn fordeling kan dog kun øge sandsynligheden for sammenfald af fødselsdage, men ikke reducere: hvis alle mennesker kun blev født på 3 dage ud af 365, så ville sandsynligheden for sammenfald af fødselsdage være meget høj.

Lad os først beregne sandsynligheden for, at alle menneskers fødselsdage vil være forskellige i en gruppe mennesker. Hvis , så i kraft af Dirichlet-princippet , er sandsynligheden nul. Hvis , så vil vi argumentere som følger. Lad os tilfældigt tage en person fra gruppen og huske hans fødselsdag. Så tager vi anden person tilfældigt, mens sandsynligheden for, at hans fødselsdag ikke falder sammen med fødselsdagen for første person, er lig med . Så tag den tredje person; sandsynligheden for, at hans fødselsdag ikke falder sammen med fødselsdagen for en af de to første er lig med . Ved at argumentere analogt vil vi nå den sidste person, for hvem sandsynligheden for en mismatch af hans fødselsdag med alle de foregående vil være lig med . Multiplicerer vi alle disse sandsynligheder, får vi sandsynligheden for, at alle fødselsdage i gruppen vil være forskellige: ${\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)!}.

Så er sandsynligheden for, at mindst to personer ud af n har samme fødselsdag lig med

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

Værdien af denne funktion overstiger 1/2 ved , mens sandsynligheden for tilfældighed er cirka 50,73 %, og . Listen over n værdier og deres tilsvarende sandsynligheder er angivet i følgende tabel. $n=23$ $p(22)\ca. 47,57\%$

n	p ( n )
ti	12 %
tyve	41 %
tredive	70 %
halvtreds	97 %
100	99,99996 %
200	99,999999999999999999999999999998 %
300	(1 − 7×10 −73 ) × 100 %
350	(1 − 3×10 −131 ) × 100 %
367	100 %

Denne problemstilling kan omformuleres i form af det klassiske "tilfældighedsproblem". Lade:

urnen indeholder kugler (i dette tilfælde antallet af dage i et år, antaget at være 365 dage); $M$ $M$
kugler nummereret 1, 2, …, ; $M$
flere prøver er lavet af n kugler fra urnen (i dette tilfælde er n antallet af personer i gruppen);
de tilbagetrukne bolde returneres til urnen efter hvert valg;
prøverne betragtes som bestilte, dvs. prøverne og anses for forskellige. $\{ 1, 2, 4, 6 \}$ $\{ 4, 2, 6, 1 \}$

Det er nødvendigt at beregne sandsynligheden for, at en begivenhed består i fravær af gentagelser i stikprøven. Alle beregninger er de samme som ovenfor .

Alternativ metode

Sandsynligheden for, at to personer i en gruppe på n har samme fødselsdag kan også beregnes ved hjælp af kombinatoriske formler [4] . Forestil dig, at hver dag i året er ét bogstav i alfabetet, og alfabetet består af 365 bogstaver. Fødselsdagene for n personer kan repræsenteres af en streng bestående af n bogstaver i dette alfabet. Ved Hartleys formel er antallet af mulige rækker

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

Antallet af mulige strenge, hvor bogstaver ikke gentages ( placering af 365 gange n ) vil være

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

Hvis rækkerne er valgt tilfældigt (med en ensartet fordeling ), er sandsynligheden for at vælge en række, hvor mindst to bogstaver matcher

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

kl og

n\leqslant 365

p(n)=1

kl .

n>365

På denne måde

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

og dette udtryk svarer til det ovenfor præsenterede .

Det samlede antal mulige rækker kan også beregnes ved hjælp af den kombinatoriske formel for antallet af placeringer med gentagelser A (gentagelser)  n /365 = 365 n .

Approksimationer

Eksponentiel funktion

Brug af Taylor-seriens udvidelse af eksponentialfunktionen

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

Ovenstående udtryk for kan tilnærmes som følger: ${\bar p}(n)$

{\bar p}(n)\ca. 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ølgelig:

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

Bemærk, at den forenklede tilnærmelse

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

som du kan se på grafen, giver den stadig tilstrækkelig nøjagtighed.

Lad os give endnu en tilnærmelse .

Sandsynligheden for at to personer har samme fødselsdag er 364/365. I en gruppe mennesker , par. Derfor kan sandsynligheden , forudsat at disse hændelser er uafhængige , tilnærmes med tallet $n$ $C(n,2)={\frac {n(n-1)}{2}}$ ${\bar p}(n)$

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

Derfor får vi en tilnærmelse for den krævede sandsynlighed p ( n ) :

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

Poisson-tilnærmelse

Ved at bruge Poisson- tilnærmelsen for binomialet , baseret på den tidligere tilnærmelse for , får vi lidt mere end 50 % : $p(n)$

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

Beregning af antallet af personer, hvor sandsynligheden er 50 %

Lad os udtrykke n fra ovenstående formel . Så, i stedet for p ( n ), erstatter vi 50 % (0,5). Som et resultat får vi: ${\displaystyle p(n)=1-{\bar {p}}(n)\ca. 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.

Der er en anden måde at estimere n på 50% sandsynlighed . Som bevist ovenfor :

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

Find det mindste n for hvilket

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

eller, som er det samme,

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

Lad os bruge ovenstående tilnærmelse af funktionen ved den ${\bar p}(n)$ eksponentielle funktion :

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

Substituerer i stedet i udtrykket , får vi ${\bar {p}}_{\text{ca.}}(n)$ ${\bar p}(n)$ ${\bar {p}}(n)<{\frac {1}{2}}$

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

Løsning for n , får vi

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

Herfra finder vi n og runder op til et heltal :

n =23 .

Født samme dag som en given person

Lad os sammenligne sandsynligheden p ( n ) med sandsynligheden for, at i en gruppe på n personer vil fødselsdagen for en person fra gruppen falde sammen med fødselsdagen for en eller anden forudvalgt person, der ikke tilhører gruppen. Denne sandsynlighed er

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

Ved at erstatte n = 23 får vi q ( n ) ≈ 6,12 % . For at sandsynligheden for q ( n ) skal overstige 50 % , skal antallet af personer i gruppen være mindst 253 ( q (252) ≈ 49,91 % ; q (253) ≈ 50,05 % ). Dette tal er mere end halvdelen af årets dage ( 365/2 = 182,5 ); dette skyldes, at andre medlemmer af gruppen kan have samme fødselsdag, og det reducerer sandsynligheden q ( n ) . Mere præcist skyldes dette, at når vi tilføjer sandsynligheden for tilfældigheder, trækker vi hver gang sandsynligheden for den fælles forekomst af disse begivenheder, da begivenhederne er fælles, og sandsynligheden for deres fælles forekomst i additionen tages i betragtning. to gange. P ( A + B ) = P ( A ) + P ( B ) − P ( AB ) og så videre med hver tilføjelse af et nyt led.

Generaliseringer

Sammenfald af diskrete stokastiske variable

Det beskrevne problem kan formuleres i generel form:

givet tilfældige tal;
tilfældige tal er fordelt ensartet i området fra 1 til d ;
n er antallet af tilfældige tal;
bestem p ( n ; d ) - sandsynligheden for , at mindst to af de givne tal vil matche.

Hvis du ræsonnerer på samme måde som beskrevet ovenfor , kan du få generelle løsninger:

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

p(n;d)\ca. 1-e^{{-(n(n-1))/2d}};

q(n;d)=1-\venstre({\frac {d-1}{d}}\højre)^{n}.

Omvendt problem:

givet p er sandsynligheden for, at mindst to tilfældige tal matcher;
det er kendt, at tilfældige tal er ensartet fordelt i området fra 1 til d ;
find n ( p ; d ) - antallet af tilfældige tal.

Løsning:

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

Flere typer mennesker

Ovenfor blev fødselsdagsparadokset præsenteret for én "type" mennesker. Det er muligt at generalisere problemet ved at introducere flere "typer", for eksempel at opdele mennesker i mandlige ( m ) og kvindelige ( n ). Lad os beregne sandsynligheden for, at mindst én kvinde og én mand har samme fødselsdag (sammenfald af fødselsdage for to kvinder eller to mænd tages ikke i betragtning):

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

hvor d \u003d 365 og S 2 () er stirlingtal af anden art . Interessant nok er der ikke noget entydigt svar på spørgsmålet om værdien af n + m for en given sandsynlighed. For eksempel giver en sandsynlighed på 0,5 både et sæt på 16 mænd og 16 kvinder og et sæt på 43 mænd og 6 kvinder.

Nærliggende fødselsdage

En anden generalisering af fødselsdagsparadokset er at angive problemet med, hvor mange mennesker der skal til, for at sandsynligheden for at have i en gruppe mennesker, hvis fødselsdage ikke afviger mere end én dag (eller to, tre dage, og så videre) overstiger 50 % . Ved løsning af dette problem anvendes princippet om inklusion-eksklusion . Resultatet (igen forudsat at fødselsdage er jævnt fordelt ) er:

Maksimal forskel i fødselsdage, antal dage	Nødvendigt antal personer
en	23
2	fjorten
3	elleve
fire	9
5	otte
6	otte
7	7
otte	7

Således overstiger sandsynligheden for, at selv i en gruppe på 7 personer fødselsdagene for mindst to af dem højst vil afvige med en uge 50% .

Ansøgning

Fødselsdagsparadokset gælder generelt for hash-funktioner : hvis en hash-funktion genererer en N -bit-værdi, så er antallet af tilfældige input, for hvilke hash-koder højst sandsynligt vil kollidere (det vil sige, at der er ens hash-koder opnået på forskellige inputdata ) er ikke 2 N , men kun omkring 2 N /2 . Denne observation udnyttes i et angreb på kryptografiske hash-funktioner kaldet fødselsdagsangrebet .

N	Antal forskellige udgangskæder (2 N )	Sandsynlighed for mindst én kollision ( p )
N	Antal forskellige udgangskæder (2 N )	10-18 _	10-15 _	10-12 _	10-9 _	10-6 _	0,1 %	en %	25 %	halvtreds %	75 %
32	4,3× 109	2	2	2	2.9	93	2,9×10³	9,3×10³	5,0x104	7,7×104	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

De hvide celler angiver antallet af personer i gruppen, hvor en kollision vil ske med en given sandsynlighed (i analogi med paradokset er antallet af udgangskæder 365).

Et lignende matematisk apparat bruges til at estimere bestandsstørrelsen af fisk , der lever i søer . Metoden kaldes "capture-recapture" ("fang - fange igen"). Faktisk, hvis hver fanget fisk er markeret og genudsat, så vil sandsynligheden for at fange en markeret fisk vokse ikke-lineært (i overensstemmelse med grafen ovenfor) med en stigning i antallet af forsøg. Populationsstørrelsen kan groft estimeres som kvadratet af antallet af forsøg, der er gjort, før den første mærkede fisk fanges .

Løsningen af problemet i generelle vendinger finder anvendelse i mange grene af matematikken , for eksempel i ikke-deterministiske faktoriseringsalgoritmer . Så en af de enkleste forklaringer på Pollards ρ-metode ligner forklaringen på fødselsdagsparadokset: det er nok at have tilnærmelsesvis tilfældige tal fra 0 til , hvor er primtal, således at for mindst et af talparrene med stor sandsynlighed er der , hvilket vil være en divisor af tallet n . $\sqrt{p}$ $n=pq$ $p<q$ $\gcd \left(|xy|,n\right)>1$

Omvendte problemer

At finde det mindste tal n , således at sandsynligheden p ( n ) er større end et givet tal p .

At finde det største tal n , således at sandsynligheden p ( n ) er mindre end et givet tal p .

Ved at bruge formlen ovenfor får vi:

n(s;365)\ca. {\sqrt {2\cdot 365\cdot \ln \venstre({1 \over 1-p}\højre))).

s	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	otte	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	tredive	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 bedste position

Lad der være n - 1 personer i lokalet, og deres fødselsdage er forskellige. Lad g ( n ) være sandsynligheden for, at fødselsdagen for den person, der trådte ind, er den samme som fødselsdagen for en tilstedeværende i lokalet. Det er nødvendigt at finde værdien af n , hvor værdien af funktionen g ( n ) er maksimal.

Løsningen handler om at finde den maksimale værdi af udtrykket

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

Ved at bruge ovenstående formel for p ( n ) får vi n = 20 .

Gennemsnitligt antal personer

Lad os overveje et andet problem. Hvor mange mennesker skal der i gennemsnit til for at have mindst to af dem samme fødselsdag?

Dette problem havde at gøre med hashing- algoritmer og blev undersøgt af Donald Knuth . Det viser sig, at den for os interesserede stokastiske variabel har en matematisk forventning svarende til

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

hvor

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

Fungere

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

blev udforsket af Ramanujan . Han opnåede også følgende asymptotiske ekspansion for denne 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 er det gennemsnitlige antal personer

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

Dette tal er lidt større end antallet af personer, der giver en chance på 50 % . Overraskende nok er det nødvendige antal personer M + 1 = 366 (for 365 personer kan deres fødselsdage fordeles over hver af årets 365 dage uden overlap), selvom der i gennemsnit kun er brug for 25.

Se også

Noter

↑ Mazur, 2017 , s. 116.
↑ Mazur, 2017 , s. 119.
↑ Mironkin V. O., Chukhno A. B. Om en generalisering af "fødselsdage"-paradokset . Hentet 30. marts 2020. Arkiveret fra originalen 9. juli 2020. (ubestemt)
↑ Mazur, 2017 , s. 117.

Litteratur

Kemeny J. , Snell J., Thompson J. Introduction to Finite Mathematics = Introduction to Finite Mathematics. - Forlag for udenlandsk litteratur, 1963. - 488 s.
Kozlov MV Elementer af sandsynlighedsteori i eksempler og problemer. - Moscow State University, 1990 . — ISBN 5-211-00312-8 .
Mazur, Joseph. Fødselsdagsproblem // chancespil. Matematik og tilfældighedsmytologi. - Alpina faglitteratur, 2017. - S. 116-123. — 292 s. - ISBN 978-5-91671-636-8 .
Sekey G. Paradokser i sandsynlighedsteori og matematisk statistik. - RHD, 2003 . — ISBN 5-93972-150-8 .
Shiryaev A. N. Sandsynlighed-1. - MTsNMO, 2007 . - ISBN 978-5-94057-036-3 .
Goldberg S. Et direkte angreb på et fødselsdagsproblem // Mathematical Mathematics Magazine. - maj 1976 . — Iss. 49 . - S. 130-132 .

Mosteller F. Forståelse af fødselsdagsproblemet // Matematiklæreren. - maj 1962 . - S. 322-325 . _