Paradoks av bursdager

De bursdager paradoks Resultatene fra sannsynlighetsestimat for antall personer som må bringes sammen for å ha minst én sjanse i to som to personer i denne gruppen har sine bursdager på samme dag. Det viser seg at tallet er 23, noe som sjokkerer intuisjonen litt. Fra en gruppe på 57 personer er sannsynligheten større enn 99%.

Dette er et paradoks ikke i betydningen logisk motsetning , men i den forstand at det er en matematisk sannhet som strider mot intuisjonen : de fleste anslår at denne sannsynligheten er mye mindre enn 50%.

Denne studien er av Richard von Mises .

Forstå problemet

For enkelhets skyld er artikkelen skrevet forutsatt at alle år ikke er sprang . Ta hensyn til29. februar ville endre resultatene lite, men ville gjøre beregningene veldig delikate.

Intuitiv mening

Problemet med bursdager kommer ned på å velge et antall n elementer i et sett som inkluderer N , uten uttak; det vil si uten å fjerne de valgte elementene, slik at noen kan være identiske. Paradokset med bursdager er virkelig et tilfelle av denne typen, fordi hver og en har en mer eller mindre tilfeldig jubileumsdato, og det er ingen a priori grunn til annet enn sannsynligheten for at to datoer er identiske eller forskjellige.

Forestille seg for eksempel at i løpet av en kveld høsting n mennesker, små papirer, på hvilke det er bemerket tallene fra 1 til N , er plassert i en kurv. Hver av dem tegner et stykke papir, leser nummeret han bærer, og legger det deretter i kurven. Hva er sjansene for at minst to tall som er trukket er like? eller tvert imot slik at alle er forskjellige?

For å beregne den numeriske sannsynligheten er det lettere å telle sjansene for at alle tallene er forskjellige. Det ikke åpenbare nøkkelpunktet som villeder vår intuisjon, snarere tvert imot, gjelder sjansene for at minst to tall er identiske. Til slutt er de to tilnærmingene selvsagt likeverdige.

Hvis vi vurderer et gitt tall tegnet, hva er sjansene for å være identiske med et annet? Det kan være lik alle andre; Det totale antall muligheter begrenses sine sjanser: så vi intuitivt proporsjonal hell $n / N$ . Men denne mulighet gjelder for alle de tall som trekkes, slik at til slutt, er sjansen for at et hvilket som helst antall trukket er identisk med et hvilket som helst annet tall trukket er i en mengde på ca. $N 2 / N$ . Det er her intuisjonen vår blir lurt, og vi forutser en sannsynlighet på 50% for n nær $N / 2$ mens $\sqrt N$ er en bedre tilnærming.

Dette tilsvarer å si at vi forveksler det stilte spørsmålet: sjansene for at et valgt element er identisk med et annet, med et annet lignende spørsmål: sjansene for at et valgt element er identisk med et annet gitt element . Når det gjelder bursdager, har vi en tendens til å intuitivt vurdere sannsynligheten for at noens bursdag er den samme som en gitt bursdag (f.eks. Min); i stedet for sannsynligheten for at noen bursdag er det samme som noens andres.

Det gjenstår å se hvorfor vår intuisjon blir lurt, det vil si hvorfor den ikke virker spontant i stand til å nærme seg et problem av denne typen riktig. Dette er et spørsmål for kognitiv vitenskap .

Demonstrasjon

Vi gir et bevis for den opprinnelige saken, med bursdager, men dette overføres ganske enkelt til saken om den oppgitte generaliseringen. En hyppig feil i demonstrasjonen er å telle antall par, så utelater vi det faktum at hendelsene ikke er usammenhengende, og at tre personer godt kan dele samme fødselsdato: disse hendelsene er ikke usammenhengende . Den enkleste måten å oppnå det annonserte resultatet er å beregne sannsynligheten for at hver person har en annen bursdag enn de andres: det motsatte av det vi leter etter.

Vi kan fortsette med induksjon : den første personen har derfor 365 valg, den andre 364, den tredje 363, den fjerde 362, og så videre. Vi vil fortsette her ved å telle , det vil si, vi vil telle antall tilfeller der n mennesker har forskjellige bursdager, og vi vil dele på antall muligheter. I begge tilfeller legger vi til grunn antrekkbarhet for fødselsdagene.

Det er mennesker, for hver er det 365 mulige dager, så totalt sett hvis vi ikke setter noen begrensninger, er det $365$ $n$ muligheter. Hvis nå ønsker vi dagene annerledes , får vi en forståelse av fra 365, enten: . $ikke$ $ikke$ $A _ {{365}} ^ {n} = (365-0) (365-1) ... (365-n + 1) = {\ frac {365!} {(365-n)!}}$

Så det har vi gjort

\ overline {p} (n) = {\ frac {365!} {(365-n)!}} \ cdot {\ frac {1} {365 ^ {n}}}

Vi kan også se det som en multiplikasjon av sannsynligheten for uavhengige hendelser:

{\ displaystyle {\ overline {p}} (n) = \ underbrace {{\ frac {365} {365}} \ cdot {\ frac {364} {365}} \ cdot {\ frac {363} {365} } \ cdot \ cdots \ cdot {\ frac {365-n + 1} {365}}} _ {n \, {\ text {factors}}}}

Arrangementet "en annen jubileumsdag per person" er imidlertid komplementet til "minst to identiske". Derfor er sannsynligheten som er søkt . $p (n) = 1- \ overlinje {p} (n)$

Ved å lage den digitale applikasjonen er det 50,73% sjanse for to identiske fødselsdager i en samling på tjuetre 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	${\ displaystyle \ left (1- \ left (6.10 ^ {- 82} \ right) \ right) \ cdot 100 \%}$
350	$\ venstre (1- \ venstre (3.10 ^ {{- 131}} \ høyre) \ høyre) \ cdot 100 \%$
> 365	100% (etter skuffeprinsippet )

Generalisering

Dette paradokset av bursdager generaliserer til den mer abstrakte situasjonen som kan angis i formen:

La være et endelig sett med kardinal . Sannsynligheten for at minst to elementer er like mellom elementene i at hvert element blir tegnet jevnt gjennom hele settet , er: $E$ $IKKE$ $p (n)$ $ikke$ $E$ $E$

{\ displaystyle p (n) = 1 - {\ frac {N!} {(Nn)!}} \ cdot {\ frac {1} {N ^ {n}}}.}

Sannsynlighetstilnærming

Sannsynligheten kan skrives om som: $\ overline {p} (n) = 1-p (n)$

{\ displaystyle {\ overline {p}} (n) = \ left (1 - {\ frac {1} {N}} \ right) \ left (1 - {\ frac {2} {N}} \ right) ... \ left (1 - {\ frac {n-1} {N}} \ right)}

Imidlertid har vi den begrensede utvidelsen for x nær 0. Dette fører til tilnærmingen: $e ^ {x} = 1 + x + o (x)$

{\ displaystyle {\ overline {p}} (n) \ approx \ prod _ {k = 0} ^ {n-1} e ^ {- {\ frac {k} {N}}}}

{\ displaystyle {\ overline {p}} (n) \ approx e ^ {- {\ frac {\ sum _ {k = 0} ^ {n-1} k} {N}}}}

Summen av heltall fra 0 til er imidlertid verdt , noe som til slutt gir: $n-1$ $n (n-1) / 2$

{\ displaystyle {\ overline {p}} (n) \ approx e ^ {- {\ frac {n (n-1)} {2 \ cdot N}}}}

Kommer tilbake til : $p (n)$

{\ displaystyle p (n) \ approx 1-e ^ {- {\ frac {n (n-1)} {2 \ cdot N}}}}

Anslag for antall trekk for en gitt sannsynlighet

Tilnærmingen av gjør det mulig å bare få en tilnærming til antall personer som er nødvendige for å ha en gitt sannsynlighet for å ha minst to personer med samme bursdag. Vi får dermed: $n (p)$ $s$

{\ displaystyle n (p) \ approx {\ sqrt {2 \ cdot N \ ln \ left ({\ frac {1} {1-p}} \ right)}}

Noen numeriske verdier

Tabellen nedenfor indikerer i det opprinnelige tilfellet ( ), for en sannsynlighet , tilnærmingen , deretter på samme linje, tilnærmingen av sannsynligheten for heltallet mindre enn eller lik (bemerket ) og sannsynligheten for heltallet større enn eller lik (bemerket ). Normalt bør sannsynligheten som er fast i starten være mellom disse to verdiene. Oppføringer som ikke oppfyller denne betingelsen er angitt i farger . ${\ displaystyle N = 365}$ $s$ $n (p)$ $n (p)$ $\ lfloor n \ rfloor$ $n (p)$ $\ lceil n \ rceil$ $s$

$s$	$ikke$	$\ lfloor n \ rfloor$	$p (\ lfloor n \ rfloor)$	$\ lceil n \ rceil$	$p (\ lceil n \ rceil)$
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	1. 3	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

Kobling til Rayleighs lov

I uttrykket:

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

vi gjenkjenner distribusjonsfunksjonen til Rayleigh :

F (x) = 1-e ^ {{- {\ frac {x ^ {2}} {2}}}}.

Faktisk, sett i det mer generelle rammeverket av tildelingsproblemer, blir beregningen ovenfor tolket som konvergensen til en distribusjonsfunksjon mot en annen, og oversetter konvergensen til loven til en serie tilfeldige variabler: la oss vurdere m bokser nummerert fra 1 til m , m er, for øyeblikket, fast . Anta at baller er allokert til den, hver ball blir plassert i en av m- boksene på en ekviprobabel måte, uavhengig av foregående tildelinger, og dette på ubestemt tid . Hvis m = 365 , er dette bursdagssituasjon for en stadig voksende gruppe mennesker . Legg merke til rangeringen til den første ballen som er tildelt i en boks som allerede inneholder en annen ball, som tilsvarer rangen til den første personen som ankommer gruppen, hvis jubileumsdato allerede er for et annet medlem av gruppen (før hans ankomst alle medlemmene i gruppen har forskjellige bursdager, etter ankomst er dette ikke lenger tilfelle). Så $T_ {m}$

p (n) = {\ mathbb {P}} (T _ {{365}} \ leq n),

Og tilnærmingen ovenfor kan derfor skrives:

{\ mathbb {P}} (T _ {{365}} / {\ sqrt {365}} \ leq x) \ approx 1-e ^ {{- {\ frac {x ^ {2}} {2}} }}.

Dette gjenspeiler det faktum at sekvensen av tilfeldige variabler konvergerer i lov mot Rayleighs lov, og på samme måte avslører dette et paradoks for sunn fornuft: vi forventer sannsynligvis at den skal være i samme størrelsesorden som m , mens dette konvergens i lov avslører at det er av samme størrelsesorden som Fenomenet gjentakelse av fødselsdager foregår derfor tidligere, for en mindre gruppe enn man forventer. $T_ {m} / {\ sqrt {m}}$ $T_ {m}$ $T_ {m}$ ${\ sqrt {m}}.$

Ikke-uniform sak

I forrige beregning ble det implisitt antatt fordeling av fødselsdager i året. Hva skjer hvis vi ikke lenger antar det? Svaret er at det øker sjansen for å vinne innsatsen at to personer blir født samme dag, noe som ytterligere forsterker paradokset.

Demonstrasjon av dette faktum.

Ettersom demonstrasjonen vil bli gjort ved induksjon på antall dager i året, noterer vi dette tallet og antall personer; eller den tilfeldige variabelen som gir fødselsdagen til person nr . Naturligvis antas variablene å være uavhengige med samme lov :, uavhengig av . $ikke$ ${\ displaystyle k \ leqslant n}$ ${\ displaystyle X_ {j}}$ $j$ ${\ displaystyle X_ {j}}$ ${\ displaystyle P \ left (X_ {j} = i \ right) = x_ {i}}$ $j$

Den etterspurte begivenheten (mennesker blir født på forskjellige dager) er møtet med usammenhengende hendelser som en ordning av . ${\ displaystyle \ {(X_ {1}, ..., X_ {k}) = (i_ {1}, .., i_ {k}) \}, (i_ {1}, .., i_ {k })}$ ${\ displaystyle [\! \ left [1, n \ right] \!]}$

Ønsket sannsynlighet er derfor

{\ displaystyle p_ {k} (x_ {1}, .., x_ {n}) = \ sum _ {(i_ {1}, .., i_ {k}) ~ {\ text {arrangement av}} [ \! \ left [1, n \ right] \!]} x_ {i_ {1}} \ cdot x_ {i_ {2}} \ cdot ... \ cdot x_ {i_ {k}} = k! {\ undersett {1 \ leqslant i_ {1} <.. <i_ {k} \ leqslant n} {\ sum}} x_ {i_ {1}} \ cdot x_ {i_ {2}} ... \ cdot x_ {i_ {k}}}

Som kunngjort vil vi vise at for alt mellom 2 og , $k$ $ikke$

{\ displaystyle p_ {k} (x_ {1}, .., x_ {n}) \ leqslant p_ {k} (1 / n, ..., 1 / n) {\ text {si}} \ sum _ {i = 1} ^ {n} x_ {i} = 1, x_ {i} \ geqslant 0}

Posering , vi vil enda mer generelt bevise ved induksjon på det for alt mellom 2 og : ${\ displaystyle \ varphi _ {k} (x_ {1}, .., x_ {n}) = \ sum _ {1 \ leqslant i_ {1} <.. <i_ {k} \ leqslant n} x_ {i_ {1}}. X_ {i_ {2}} .... x_ {i_ {k}}}$ $ikke$ $k$ $ikke$

{\ displaystyle \ varphi _ {k} (x_ {1}, .., x_ {n}) \ leqslant \ varphi _ {k} (s / n, ..., s / n) {\ text {si} } \ sum _ {i = 1} ^ {n} x_ {k} = s, x_ {i} \ geqslant 0}

For , den eneste muligheten for er , og ulikheten er lett. $n = 2$ $k$ $k = 2$ ${\ displaystyle \ varphi _ {2} \ left (x_ {1}, x_ {2} \ right) = x_ {1} x_ {2} \ leqslant \ left ({\ dfrac {x_ {1} + x_ {2 }} {2}} \ right) ^ {2}}$

Anta at eiendommen er ordensbestemt og viser den til bestilling . $ikke$ $n + 1$

La oss sette og . ${\ displaystyle \ sum _ {k = 1} ^ {n + 1} x_ {k} = s}$ ${\ displaystyle x_ {n + 1} = x}$

Legg merke til det . ${\ displaystyle \ varphi _ {k} \ left (x_ {1}, ..., x_ {n}, x \ right) = x \ varphi _ {k-1} (x_ {1}, .., x_ {n}) + \ varphi _ {k} (x_ {1}, .., x_ {n})}$

Ved induksjonshypotese,

{\ displaystyle \ varphi _ {k-1} (x_ {1}, .., x_ {n}) \ leqslant \ varphi _ {k-1} \ left ({\ dfrac {sx} {n}},. .., {\ dfrac {sx} {n}} \ right) = {\ binom {n} {k-1}} \ left ({\ dfrac {sx} {n}} \ right) ^ {k-1 }}

og .

{\ displaystyle \ varphi _ {k} (x_ {1}, .., x_ {n}) \ leqslant \ varphi _ {k} \ left ({\ dfrac {sx} {n}}, ..., { \ dfrac {sx} {n}} \ høyre) = {\ binom {n} {k}} \ venstre ({\ dfrac {sx} {n}} \ høyre) ^ {k}}

Så vi får . ${\ displaystyle \ varphi _ {k} \ left (x_ {1}, ..., x_ {n}, x \ right) \ leqslant x {\ binom {n} {k-1}} \ left ({\ dfrac {sx} {n}} \ høyre) ^ {k-1} + {\ binom {n} {k}} \ venstre ({\ dfrac {sx} {n}} \ høyre) ^ {k}}$

{\ displaystyle \ varphi _ {k} \ left (x_ {1}, ..., x_ {n}, x \ right) \ leqslant {\ dfrac {1} {kn ^ {k}}} {\ binom { n} {k-1}} \ venstre [knx \ venstre (sx \ høyre) ^ {k-1} + \ venstre (nk + 1 \ høyre) \ venstre (sx \ høyre) ^ {k} \ høyre]}

Posering , den siste parentesen er ${\ displaystyle y = sx}$

{\ displaystyle f \ left (y \ right) = kn \ left (sy \ right) y ^ {k-1} + \ left (n-k + 1 \ right) y ^ {k} = knsy ^ {k- 1} - \ venstre (n + 1 \ høyre) \ venstre (k-1 \ høyre) y ^ {k}}

De avledede viser som er maksimal for , det vil si . ${\ displaystyle f '(y) = k (k-1) y ^ {k-2} (ns- (n + 1) y)}$ $f$ ${\ displaystyle y = {\ dfrac {n} {n + 1}} s}$ ${\ displaystyle x = {\ dfrac {s} {n + 1}}}$

Så hva fullfører gjentakelsen. ${\ displaystyle \ varphi _ {k} \ left (x_ {1}, ..., x_ {n}, x \ right) \ leqslant {\ dfrac {s} {n + 1}} {\ binom {n} {k-1}} \ left ({\ dfrac {s} {n + 1}} \ right) ^ {k-1} + {\ binom {n} {k}} \ left ({\ dfrac {s} {n + 1}} \ høyre) ^ {k} = {\ binom {n + 1} {k}} \ venstre ({\ dfrac {s} {n + 1}} \ høyre) ^ {k}}$ ${\ displaystyle = \ varphi _ {k} \ left ({\ dfrac {s} {n + 1}}, ..., {\ dfrac {s} {n + 1}} \ right)}$

Merk at dette tilsvarer at forventningen til produktet av forskjellige tall hentet fra positive tall for en gitt sum er maksimum når disse tallene er like. $k$ $ikke$ $ikke$

Geometrisk:

Blant alle de rektangulære hyperparallelepepedene (eller ortotoper) av dimensjonen av summen av lengdene på de oppgitte kantene, er den som har størst gjennomsnitt av hypervolumene i cellene hypercube. For eller 3: blant alle de rektangulære parallellepipedene med summen av lengdene på de angitte kantene, er den med det største arealet (eller volumet) kuben. $ikke$ $k$ ${\ displaystyle n = 3, k = 2}$

applikasjoner

I Le Trésor des Paradoxes (Éd Belin, 2007) bemerker forfatterne at den amerikanske informatikeren Robert Mac Eliece etablerte interessen for paradokset til fødselsdager i datavitenskap, for å sikre påliteligheten til dataminner, takket være feiloppdagelseskoder, basert spesielt om arbeidet til Richard Hamming ved Bell Laboratories . Strategien for feiloppdagelseskoder viser seg fra et statistisk synspunkt å være lik bursdagsparadokset. Bursdagsparadokset brukes i kryptografi for å utvikle angrep på hashfunksjoner . En av begrensningene som pålegges disse funksjonene, for kryptografisk bruk, er å produsere få kollisjoner , med andre ord å sjelden ta den samme verdien på forskjellige innganger.

Fødselsdagsparadokset gir en avgrensning av det gjennomsnittlige antall elementer som er nødvendige for å ha en kollisjon med en sannsynlighet , nemlig i hovedsak kvadratroten til antall mulige verdier for hashfunksjonen, under antagelse om at denne funksjonen er jevnt fordelt på sin ankomstverdier. $p = {\ frac {1} {2}}$

Mer konkret, hvis en hash-funksjon har en utgang på N- bits , har ankomstsettet elementer og det tar omtrent hasj av forskjellige elementer for å produsere en kollisjon med 50% sjanse; resultatene av funksjonen kan sammenlignes med personer med bursdager spredt over verdier. $2 ^ {N}$ $2 ^ {{\ frac N2}}$ $2 ^ {N}$

Praktisk anvendelse av bursdagsangrepet

La oss anta at Martine ønsker å tvinge Daniel til å undertegne en veldig ugunstig kontrakt, og kontrakten må valideres av hans avtrykk (hash-verdi), og denne garanterer at kontrakten ikke kan endres etter signaturen.

Hun utarbeider en rettferdig kontrakt, og en ugunstig kontrakt. Deretter genererer den automatisk varianter av hver av avtalene med kosmetiske endringer (tillegg av mellomrom, bruk av synonymer, ombestilling av avsnitt osv.). Den beregner fingeravtrykket til hver kontrakt ved å se etter par med de samme fingeravtrykkene (med og uten modifikasjoner). Så snart en kollisjon er funnet, gir hun den tilsvarende rettferdige kontrakten til Daniel som verifiserer den, signerer den, beregner avtrykket og fester det til kontrakten.

Martine gjør det samme med den ugunstige kontrakten, og presenterer den for Daniel. Hvis han bestrider vilkårene for kontrakten han signerte, viser avtrykket at det er umulig at det kunne blitt endret. Det vil fremdeles være mulig for ham å motsette seg den opprinnelige kontrakten mot Martine, noe som skulle føre til at kontrakten blir ugyldig.

Kobling med DNA-identifikasjon

I det rettsmedisinske feltet er identifikasjonssannsynlighetene som gis med DNA-fingeravtrykksteknikken ofte dårlig forstått. Så hvis sannsynligheten for at to individer som deler ni lokus er omtrent en av 13 milliarder kroner, vil omtrent 116 par personer i en database på 65 000 mennesker ha 9 av de 13 lokene til felles. Brukt til identifikasjonsformål.

Anekdote

I boka som gjør Crazy , Raymond Smullyan sier han hadde sine 19 studenter etablere formelen. Han konkluderer etter digital søknad at det er mye mindre enn én sjanse av to (litt under 38%) at to elever har bursdag samme dag. En student svarer at han satser på at det hele er det samme. Læreren ringer ved å be elevene oppgi fødselsdato, og ler før slutten, etterfulgt av hele klassen, og husker at to av elevene hans er tvillinger .

Merknader og referanser

Ross 2014 , s. 37.
" Attack" bursdager " "
Leila Schneps og Coralie Colmez ( oversatt fra engelsk av Coralie Colmez), Matematikk i retten: feilberegninger gjør rettslige feil [“ Math on Trial. Hvordan numre blir brukt og misbrukt i rettssalen ”], Paris, Seuil , koll. "Åpen vitenskap", 280 s. ( ISBN 978-2-02-110439-4 ) , kap. 5 ("Diana Sylvester-affære: analyse av en kald hit").
Smullyan 1982 , s. 6.

Vedlegg

Bibliografi

[Ross 2014] (en) Sheldon Ross, A First Course in Probability , Pearson ,2014, 467 s. ( ISBN 978-0-321-79477-2 og 032179477X ) , kap. 2.
[Smullyan 1982] (no) Raymond Smullyan , The Lady or the Tiger? ["Boken som gjør deg gal"],1982, 226 s. ( ISBN 0-8129-2117-8 ).

Relaterte artikler