De fødselsdage paradoks resultater fra probabilistiske estimat af det antal personer, der skal bringes sammen for at have mindst én chance i to, at to personer i denne gruppe har deres fødselsdag på samme dag. Det viser sig, at tallet er 23, hvilket chokerer intuitionen lidt. Fra en gruppe på 57 personer er sandsynligheden større end 99%.
Dette er et paradoks ikke i betydningen af logisk modsigelse , men i den forstand, at det er en matematisk sandhed, der modsiger intuition : de fleste mennesker vurderer, at denne sandsynlighed er meget mindre end 50%.
Denne undersøgelse er foretaget af Richard von Mises .
For enkelheds skyld er artiklen skrevet under antagelse af, at alle år ikke er sprang . Tag højde for29. februar ville ændre resultaterne lidt, men ville gøre beregningerne meget sarte.
Problemet med fødselsdage kommer ned til at vælge et antal n af elementer i et sæt, der inkluderer N , uden tilbagetrækning; det vil sige uden at fjerne de valgte elementer, så nogle kan være identiske. Fødselsdagsparadoxet er faktisk et tilfælde af denne type, fordi hver enkelt har en mere eller mindre tilfældig jubilæumsdato, og der ikke er en a priori grund til andet end sandsynligheden for, at to datoer er ens eller forskellige.
Forestil dig for eksempel, at der under en aften indsamles n mennesker, små stykker papir, hvori der er noteret tallene fra 1 til N , placeres i en kurv. Hver tegner til gengæld et stykke papir, læser det nummer, han bærer, og lægger det derefter tilbage i kurven. Hvad er chancerne for, at mindst to numre, der er tegnet, er ens? eller tværtimod, så alle er forskellige?
For at beregne den numeriske sandsynlighed er det lettere at tælle chancerne for, at alle tallene er forskellige. Det ikke-åbenlyse nøglepunkt, der vildlede vores intuition, tværtimod vedrører chancerne for, at mindst 2 tal er identiske. I sidste ende er de to tilgange naturligvis ækvivalente.
Hvis vi betragter et givet tal trukket, hvad er chancerne for at være identiske med et andet? Det kan være lig med ethvert andet; dog det totale antal muligheder begrænsede hans chancer: så vi intuitivt proportional held n / N . Men denne chance gælder for alle de udtrukne tal, således at til sidst, chancen for, at et vilkårligt antal trukket er identisk med andre antal trukket er i en andel på ca. n 2 / N . Det er her, vores intuition narre, og vi forudsiger en sandsynlighed på 50% for n tæt på N / 2, mens √ N er en bedre tilnærmelse.
Dette svarer til at sige, at vi forveksler det stillede spørgsmål: chancerne for, at ethvert valgt element er identisk med et andet, med et andet lignende spørgsmål: chancerne for, at ethvert valgt element er identisk med et andet givet element . I tilfælde af fødselsdage har vi en tendens til intuitivt at vurdere sandsynligheden for, at en persons fødselsdag er den samme som en given fødselsdag (f.eks. Min); i stedet for sandsynligheden for, at nogens fødselsdag er den samme som nogens andens.
Det er tilbage at se, hvorfor vores intuition således bliver bedraget, det vil sige, hvorfor det ikke synes spontant i stand til korrekt at nærme sig et problem af denne type. Dette er et spørgsmål til kognitiv videnskab .
Vi giver et bevis for den originale sag med fødselsdage, men dette overføres blot til tilfældet med den angivne generalisering. En hyppig fejl i demonstrationen er at tælle antallet af par, så udelader vi det faktum, at begivenhederne ikke er uensartede, og at tre mennesker muligvis deler den samme fødselsdato: disse begivenheder er ikke uensartede . Den nemmeste måde at opnå det annoncerede resultat er at beregne sandsynligheden for, at hver person har en anden fødselsdag end de andres: det modsatte af det, vi leder efter.
Vi kan fortsætte med induktion : den første person har derfor 365 valg, den anden 364, den tredje 363, den fjerde 362 osv. Vi fortsætter her ved at tælle , det vil sige, vi tæller antallet af tilfælde, hvor n mennesker har forskellige fødselsdage, og vi deler med antallet af muligheder. I begge tilfælde antager vi, at fødselsdagene er ekvivalente.
Der er mennesker, for hver er der 365 mulige dage, så i alt hvis vi ikke sætter nogen begrænsninger, er der 365 n muligheder. Hvis nu ønsker vi dagene anderledes , får vi en forståelse af fra 365, enten: .
Det har vi også
Vi kan også se det som en multiplikation af sandsynlighederne for uafhængige begivenheder:
Dog er begivenheden "en anden jubilæumsdag pr. Person" et supplement til "mindst to identiske". Derfor er den ønskede sandsynlighed .
Ved at lave den digitale applikation er der en 50,73% chance for to identiske fødselsdage i en samling på 23 personer.
ikke | p ( n ) |
---|---|
5 | 2,71% |
10 | 11,69% |
15 | 25,29% |
20 | 41,14% |
23 | 50,73% |
25 | 56,87% |
30 | 70,63% |
40 | 89,12% |
50 | 97,04% |
60 | 99,41% |
80 | 99,99% |
100 | 99,99997% |
200 | 99.99999999999999999999999998% |
300 | |
350 | |
> 365 | 100% (efter skuffeprincippet ) |
Dette paradoks af fødselsdage generaliserer til den mere abstrakte situation, der kan angives i formen:
Lad være et endeligt sæt kardinal . Sandsynligheden for , at mindst to elementer er ens mellem elementerne i , at hvert element trækkes ensartet i hele sættet , er:
Sandsynligheden kan omskrives som:
Vi har dog den begrænsede ekspansion for x tæt på 0. Dette fører til en tilnærmelse:
Summen af heltal fra 0 til er dog værd , hvilket i sidste ende giver:
Kommer tilbage til :
Tilnærmelsen af gør det muligt simpelthen at få en tilnærmelse af antallet af personer, der er nødvendige for at have en given sandsynlighed for at have mindst to personer med samme fødselsdag. Vi opnår således:
Tabellen nedenfor angiver i det oprindelige tilfælde ( ), for en sandsynlighed , tilnærmelsen , derefter på samme linje tilnærmelsen af sandsynligheden for heltal mindre end eller lig med (bemærket ) og sandsynligheden for heltal større end eller lig med (bemærket ). Normalt skal sandsynligheden, der er fastlagt i starten, være mellem disse to værdier. Angivelser, der ikke opfylder denne betingelse, er angivet i farve .
0,01 | 2.70864 | 2 | 0,00274 | 3 | 0,00820 |
0,05 | 6.11916 | 6 | 0,04046 | 7 | 0,05624 |
0,1 | 8,77002 | 8 | 0,07434 | 9 | 0,09462 |
0,2 | 12,76302 | 12 | 0,16702 | 13 | 0,19441 |
0,3 | 16.13607 | 16 | 0,28360 | 17 | 0,31501 |
0,5 | 22.49439 | 22 | 0,47570 | 23 | 0,50730 |
0,7 | 29,64625 | 29 | 0,68097 | 30 | 0,70632 |
0,8 | 34,27666 | 34 | 0,79532 | 35 | 0,81438 |
0,9 | 40.99862 | 40 | 0,89123 | 41 | 0,90315 |
0,95 | 46,76414 | 46 | 0,94825 | 47 | 0.95477 |
0,99 | 57,98081 | 57 | 0,99012 | 58 | 0,99166 |
I udtrykket:
vi genkender fordelingsfunktionen af Rayleigh :
Faktisk set i de mere generelle rammer for tildelingsproblemer fortolkes ovenstående beregning som konvergensen af en fordelingsfunktion mod en anden, oversætter konvergensen til loven for en række tilfældige variabler: lad os overveje m felter nummereret fra 1 til m , m idet de for øjeblikket fastsat . Antag at kugler er allokeret til den, idet hver kugle placeres i en af m- kasser på en equiprobable måde, uafhængigt af de foregående tildelinger, og dette på ubestemt tid . Hvis m = 365 , er dette fødselsdagsproblemet for en stadigt voksende gruppe mennesker . Bemærk rangen på den første bold, der er tildelt i en boks, der allerede indeholder en anden bold, der svarer til rangen for den første person, der ankommer til gruppen, hvis årsdag allerede er den for et andet medlem af gruppen (før hans ankomst alle medlemmer af gruppen har forskellige fødselsdage, efter hans ankomst er dette ikke længere tilfældet). Så
Og ovenstående tilnærmelse kan derfor skrives:
Dette afspejler det faktum, at sekvensen af tilfældige variabler konvergerer i loven mod Rayleighs lov, og på samme måde afslører dette et paradoks for sund fornuft: vi forventer sandsynligvis, at det er i samme størrelsesorden som m , mens dette lovkonvergens afslører, at det er af samme størrelsesorden som Fænomenet gentagelse af fødselsdage finder derfor sted tidligere for en mindre gruppe, end man kunne forvente.
I den tidligere beregning blev implicit antaget fordelingen af fødselsdage i året. Hvad sker der, hvis vi ikke længere antager det? Svaret er, at det øger oddsen for at vinde væddemålet, at to mennesker bliver født samme dag, hvilket yderligere styrker paradokset.
Demonstration af dette faktum.Da demonstrationen vil ske ved induktion på antallet af dage i året, bemærker vi dette antal og antallet af mennesker; eller den tilfældige variabel, der giver fødselsdag for person nr . Naturligvis antages variablerne at være uafhængige med samme lov :, uafhængige af .
Den efterspurgte begivenhed (mennesker er født på forskellige dage) er mødet med uensartede begivenheder, der er et arrangement af .
Den ønskede sandsynlighed er derfor
.Som annonceret, vil vi vise det for alt mellem 2 og ,
.Posering , vi vil endnu mere generelt bevise ved induktion på det for alt mellem 2 og :
.For den eneste mulighed er , og uligheden er let.
Antag, at ejendommen er ordensbestemt og viser den til ordre .
Lad os indstille og .
Bemærk, at .
Ved induktionshypotese,
og .Så vi får .
Er
.Poserer , den sidste parentes er
.De afledte viser, at er maksimal for , dvs. .
Så hvad fuldender gentagelsen.
Bemærk, at dette svarer til at vise, at forventningen til produktet af forskellige tal taget fra positive tal for en given sum er maksimal, når disse tal er ens.
Geometrisk:
Blandt alle de rektangulære hyperparallelepipeds (eller ortotoper) af dimensionen af summen af længderne af de opgivne kanter, er den der har det største gennemsnit af cellernes hypervolumes hypercube. For eller 3: blandt alle de rektangulære parallelepipeds med summen af længden af de givne kanter er den med det største areal (eller volumen) terningen.
I Le Trésor des Paradoxes (Éd Belin, 2007) bemærker forfatterne, at den amerikanske computerforsker Robert Mac Eliece etablerede interessen for paradoks fødselsdage inden for datalogi for at sikre pålideligheden af computerhukommelser takket være fejlregistreringskoder, baseret især om Richard Hammings arbejde ved Bell Laboratories . Strategien for fejlregistreringskoder viser sig fra et statistisk synspunkt at være magen til paradokset for fødselsdage. Fødselsdagsparadoxet bruges i kryptografi til at udvikle angreb på hash-funktioner . En af begrænsningerne for disse funktioner til kryptografisk brug er at producere få kollisioner , med andre ord sjældent at tage den samme værdi på forskellige input.
Fødselsdagsparadoxet giver et bundet af det gennemsnitlige antal elementer, der er nødvendige for at få en kollision med en sandsynlighed , nemlig i det væsentlige kvadratroden af antallet af mulige værdier for hashfunktionen under den antagelse, at denne funktion er ensartet fordelt på dens ankomstværdier.
Mere konkret, hvis en hash-funktion har et output på N bits, har ankomstsættet elementer, og det tager ca. hash af forskellige elementer at producere en kollision med en 50% chance; funktionens output kan sammenlignes med personer med fødselsdage fordelt på værdier.
Lad os antage, at Martine ønsker at tvinge Daniel til at underskrive en meget ugunstig kontrakt, hvor kontrakten skal valideres af hans aftryk (hashværdi), denne garanterer, at kontrakten ikke kunne ændres efter underskrift.
Hun forbereder en retfærdig kontrakt og en ugunstig kontrakt. Derefter genereres automatisk varianter af hver af kontrakterne med kosmetiske ændringer (tilføjelse af mellemrum, brug af synonymer, ombestilling af afsnit osv.). Det beregner fingeraftrykket for hver kontrakt ved at finde par med de samme fingeraftryk (med og uden ændringer). Så snart en kollision er fundet, giver hun den tilsvarende retfærdige kontrakt til Daniel, der verificerer den, underskriver den, beregner aftrykket og vedhæfter det til kontrakten.
Martine gør det samme med den ugunstige kontrakt og præsenterer den for Daniel. Hvis han bestrider betingelserne i den kontrakt, han underskrev, viser aftrykket, at det er umuligt, at det kunne have været ændret. Det vil stadig være muligt for ham at modsætte sig den oprindelige kontrakt med Martine, hvilket skulle føre til ugyldigheden af kontrakten.
I det retsmedicinske felt er identifikationssandsynlighederne tilvejebragt ved hjælp af DNA-fingeraftryksteknikken ofte dårligt forstået. Så hvis sandsynligheden for, at to individer deler ni loci, er omkring en ud af 13 milliarder, så i en database på 65.000 mennesker, ville omkring 116 par individer have 9 ud af de 13 loci til fælles. Brugt til identifikationsformål.
I The Book, der gør skøre , Raymond Smullyan siger, at han havde sine 19 elever etablere formlen. Han konkluderer efter digital ansøgning, at der er meget mindre end en chance ud af to (lidt mindre end 38%), at to elever har deres fødselsdag samme dag. En studerende svarer, at han satser på, at det hele er det samme. Læreren ringer ved at bede eleverne om at give deres fødselsdato og griner inden slutningen efterfulgt af hele klassen og huske at to af hans elever er tvillinger .