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.

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:

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:

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

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

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

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

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

vid och kl .

På det här sättet,

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

Ovanstående uttryck för kan approximeras enligt följande:

Följaktligen:

Observera att den förenklade approximationen

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

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

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 % :

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:

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

Hitta det minsta n för vilket

eller, vilket är detsamma,

Låt oss använda ovanstående approximation av funktionen  med exponentialfunktionen :

Ersätter istället i uttrycket får vi

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

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

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:

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

Omvänt problem:

Lösning:

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

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

Omvända problem

  1. Att hitta det minsta talet n så att sannolikheten p ( n ) är större än ett givet tal p .
  1. 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:

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

var

Fungera

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

Med M = 365 är det genomsnittliga antalet personer

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

  1. Mazur, 2017 , sid. 116.
  2. Mazur, 2017 , sid. 119.
  3. 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.
  4. Mazur, 2017 , sid. 117.

Litteratur

Länkar