Paradosso dei compleanni

Il paradosso dei compleanni risulta dalla stima probabilistica del numero di persone che devono essere riunite per avere almeno una possibilità su due che due persone in questo gruppo compiano il loro compleanno lo stesso giorno. Si scopre che il numero è 23, il che sconvolge un po 'l'intuizione. Da un gruppo di 57 persone, la probabilità è maggiore del 99%.

Questo è un paradosso non nel senso di contraddizione logica , ma nel senso che è una verità matematica che contraddice l' intuizione : la maggior parte delle persone stima che questa probabilità sia molto inferiore al 50%.

Questo studio è di Richard von Mises .

Comprendi il problema

Per semplicità, l'articolo è scritto assumendo che tutti gli anni non siano salti . Prendi in considerazione il file29 febbraio cambierebbe poco i risultati, ma renderebbe i calcoli molto delicati.

Significato intuitivo

Il problema dei compleanni si riduce alla scelta di un numero n di elementi in un insieme che include N , senza ritiro; vale a dire senza rimuovere gli elementi selezionati, in modo che alcuni possano essere identici. Il paradosso dei compleanni è infatti un caso di questo tipo, perché ognuno ha una data di anniversario più o meno casuale, e non c'è altra ragione a priori se non la probabilità che due date siano identiche o diverse.

Immagina ad esempio che durante un raduno serale n persone, piccoli fogli, su cui sono annotati i numeri da 1 a N , vengano posti in un cestino. Ognuno a turno disegna un foglio di carta, legge il numero che sta portando, quindi lo rimette nel cestino. Quali sono le possibilità che almeno 2 numeri estratti siano uguali? o al contrario in modo che siano tutti diversi?

Per calcolare la probabilità numerica , è più facile contare le possibilità che tutti i numeri siano diversi. Il punto chiave non ovvio che inganna la nostra intuizione riguarda invece le possibilità che almeno 2 numeri siano identici. Alla fine, i due approcci sono ovviamente equivalenti.

Se consideriamo un dato numero estratto, quali sono le sue possibilità di essere identico a un altro? Può essere uguale a qualsiasi altro; tuttavia, il numero totale di possibilità limitato le sue possibilità: così abbiamo intuitivamente proporzionale fortuna $n / N$ . Ma questa possibilità si applica a tutti i numeri estratti, in modo che alla fine, le probabilità che un qualsiasi numero trarre è identico a qualsiasi altro numero estratto è in una proporzione di circa $n 2 / N$ . È qui che la nostra intuizione viene ingannata e prevediamo una probabilità del 50% per n vicino a $N / 2$ mentre $\sqrt N$ è un'approssimazione migliore.

Ciò equivale a dire che confondiamo la domanda posta: le possibilità di qualsiasi elemento scelto di essere identico a un altro, con un'altra domanda simile: le possibilità di qualsiasi elemento scelto di essere identico a un altro dato elemento . Nel caso dei compleanni, tendiamo a valutare intuitivamente la probabilità che il compleanno di qualcuno sia lo stesso di un dato compleanno (es. Il mio); invece della probabilità che il compleanno di qualcuno sia uguale a quello di chiunque altro.

Resta da vedere perché la nostra intuizione viene così ingannata, cioè perché non sembra spontaneamente capace di affrontare correttamente un problema di questo tipo. Questa è una domanda per la scienza cognitiva .

Dimostrazione

Diamo una prova per il caso originale, con i giorni dei compleanni, ma questo si limita a trasporre al caso della generalizzazione dichiarata. Un errore frequente nella dimostrazione è quello di contare il numero di coppie, omettiamo quindi il fatto che gli eventi non sono disgiunti e che tre persone potrebbero condividere la stessa data di nascita: questi eventi non sono disgiunti . Il modo più semplice per ottenere il risultato annunciato è calcolare la probabilità che ogni persona abbia un compleanno diverso da quello degli altri: il contrario di quello che stiamo cercando.

Possiamo procedere per induzione : la prima persona ha quindi 365 scelte, la seconda 364, la terza 363, la quarta 362 e così via. Procederemo qui contando , cioè conteremo il numero di casi in cui n persone hanno compleanni diversi e lo divideremo per il numero di possibilità. In entrambi i casi si ipotizza l'equiprobabilità dei giorni di nascita.

Ci sono persone, per ognuna ci sono 365 giorni possibili, quindi in totale se non poniamo vincoli ci sono $365$ $n$ possibilità. Se ora vogliamo i giorni differenti , otteniamo un comprensione di da 365, sia: . $non$ $non$ $A _ {{365}} ^ {n} = (365-0) (365-1) ... (365-n + 1) = {\ frac {365!} {(365-n)!}}$

Quindi abbiamo

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

Possiamo anche vederlo come una moltiplicazione delle probabilità di eventi indipendenti:

{\ 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 {fattori}}}}

Tuttavia, l'evento "un giorno di anniversario diverso per persona" è il complemento di "almeno due identici". Quindi la probabilità cercata è . $p (n) = 1- \ overline {p} (n)$

Realizzando l'applicazione digitale, c'è una probabilità del 50,73% di due compleanni identici in un'assemblea di ventitré persone.

non	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,9999999999999999999999999998%
300	${\ displaystyle \ sinistra (1- \ sinistra (6.10 ^ {- 82} \ destra) \ destra) \ cdot 100 \%}$
350	$\ left (1- \ left (3.10 ^ {{- 131}} \ right) \ right) \ cdot 100 \%$
> 365	100% (secondo il principio dei cassetti )

Generalizzazione

Questo paradosso dei compleanni si generalizza alla situazione più astratta che può essere enunciata nella forma:

Sia un insieme finito di cardinali . La probabilità che, tra gli elementi di , ogni elemento sia disegnato uniformemente in tutto l'insieme , almeno due elementi siano identici è: $E$ $NON$ $p (n)$ $non$ $E$ $E$

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

Approssimazione di probabilità

La probabilità può essere riscritta come: $\ 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)}

Tuttavia, abbiamo l' espansione limitata per x vicino a 0. Questo porta all'approssimazione: $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}}}}

Tuttavia, vale la somma di numeri interi da 0 a , che alla fine dà: $n-1$ $n (n-1) / 2$

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

Tornando a : $p (n)$

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

Stima del numero di pareggi per una data probabilità

L'approssimazione di permette di ottenere semplicemente un'approssimazione del numero di persone necessarie per avere una data probabilità di avere almeno due persone con lo stesso compleanno. Otteniamo così: $n (p)$ $p$

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

Alcuni valori numerici

La tabella sottostante indica nel caso originale ( ), per una probabilità , l'approssimazione , quindi, sulla stessa riga, l'approssimazione della probabilità per l'intero minore o uguale a (annotato ) e quella della probabilità per l'intero maggiore di o uguale a (annotato ). Normalmente, la probabilità fissata all'inizio dovrebbe essere compresa tra questi due valori. Le voci che non soddisfano questa condizione sono indicate a colori . ${\ displaystyle N = 365}$ $p$ $n (p)$ $n (p)$ $\ lfloor n \ rfloor$ $n (p)$ $\ lceil n \ rceil$ $p$

$p$	$non$	$\ 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	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

Collegamento con la legge di Rayleigh

Nell'espressione:

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

riconosciamo la funzione di distribuzione del Rayleigh :

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

Infatti, visto nel quadro più generale dei problemi di allocazione, il calcolo di cui sopra è interpretato come la convergenza di una funzione di distribuzione verso un'altra, traducendo la convergenza nella legge di una serie di variabili aleatorie: si consideri m caselle numerate da 1 a m , m essendo, per il momento, fisso . Supponiamo che le vengano assegnate delle palline, ciascuna delle quali viene collocata in una delle m caselle in modo equiprobabile, indipendentemente dalle assegnazioni precedenti, e questo a tempo indeterminato . Se m = 365 , questa è la situazione problematica del compleanno per un gruppo di persone in costante crescita . Notare il grado della prima palla che è assegnato in una scatola contenente già un'altra palla, che corrisponderebbe al grado della prima persona, arrivata nel gruppo, la cui data di anniversario è già quella di un altro membro del gruppo (prima del suo arrivo tutti i membri del gruppo hanno un compleanno diverso, dopo il suo arrivo non è più così). Allora $T_ {m}$

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

E l'approssimazione di cui sopra può quindi essere scritta:

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

Ciò riflette il fatto che la sequenza di variabili casuali converge di diritto verso la legge di Rayleigh e, per lo stesso motivo, rivela un paradosso, per il senso comune: probabilmente ci si aspetta che sia dello stesso ordine di grandezza di m , mentre questa convergenza di leggi rivela che è dello stesso ordine di grandezza di Il fenomeno della ripetizione dei compleanni si verifica quindi prima, per un gruppo più piccolo di quanto ci si aspetterebbe. $T_ {m} / {\ sqrt {m}}$ $T_ {m}$ $T_ {m}$ ${\ sqrt {m}}.$

Caso non uniforme

Nel calcolo precedente era stata ipotizzata implicitamente la distribuzione dei compleanni nell'anno. Cosa succede se non lo assumiamo più? La risposta è che aumenta le probabilità di vincere la scommessa che due persone nascono lo stesso giorno, il che rafforza ulteriormente il paradosso.

Dimostrazione di questo fatto.

Poiché la dimostrazione sarà fatta per induzione sul numero di giorni nell'anno, annotiamo questo numero e il numero di persone; o la variabile casuale che indica il compleanno della persona n . Naturalmente, si presume che le variabili siano indipendenti con la stessa legge :, indipendenti da . $non$ ${\ displaystyle k \ leqslant n}$ ${\ displaystyle X_ {j}}$ $j$ ${\ displaystyle X_ {j}}$ ${\ displaystyle P \ sinistra (X_ {j} = i \ destra) = x_ {i}}$ $j$

L'evento ricercato (le persone nascono in giorni diversi) è l'incontro di eventi disgiunti essendo un arrangiamento di . ${\ displaystyle \ {(X_ {1}, ..., X_ {k}) = (i_ {1}, .., i_ {k}) \}, (i_ {1}, .., i_ {k })}$ ${\ displaystyle [\! \ sinistra [1, n \ destra] \!]}$

La probabilità desiderata è quindi

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

Come annunciato, mostreremo che per tutto tra 2 e , $K$ $non$

{\ 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}

Posando , dimostreremo ancora più in generale per induzione che per tutto tra 2 e : ${\ 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}}}$ $non$ $K$ $non$

{\ 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}

Perché l'unica possibilità è , e la disuguaglianza è facile. $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}}$

Supponiamo che la proprietà sia vera per order e mostrala per order . $non$ $n + 1$

Impostiamo e . ${\ Displaystyle \ sum _ {k = 1} ^ {n + 1} x_ {k} = s}$ ${\ displaystyle x_ {n + 1} = x}$

Notatelo . ${\ Displaystyle \ varphi _ {k} \ left (x_ {1}, ..., x_ {n}, x \ right) = x \ varphi _ {k-1} (x_ {1}, .., x_ {n}) + \ varphi _ {k} (x_ {1}, .., x_ {n})}$

Per ipotesi di induzione,

{\ 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 }}

e .

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

Quindi otteniamo . ${\ displaystyle \ varphi _ {k} \ left (x_ {1}, ..., x_ {n}, x \ right) \ leqslant x {\ binom {n} {k-1}} \ left ({\ dfrac {sx} {n}} \ right) ^ {k-1} + {\ binom {n} {k}} \ left ({\ dfrac {sx} {n}} \ right) ^ {k}}$

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

In posa , l'ultima parentesi è ${\ 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} - \ sinistra (n + 1 \ destra) \ sinistra (k-1 \ destra) y ^ {k}}

La derivata mostra che è massima per , cioè . ${\ 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}}}$

Quindi cosa completa la ricorrenza. ${\ displaystyle \ varphi _ {k} \ left (x_ {1}, ..., x_ {n}, x \ right) \ leqslant {\ dfrac {s} {n + 1}} {\ binom {n} {k-1}} \ sinistra ({\ dfrac {s} {n + 1}} \ destra) ^ {k-1} + {\ binom {n} {k}} \ sinistra ({\ dfrac {s} {n + 1}} \ right) ^ {k} = {\ binom {n + 1} {k}} \ left ({\ dfrac {s} {n + 1}} \ right) ^ {k}}$ ${\ displaystyle = \ varphi _ {k} \ left ({\ dfrac {s} {n + 1}}, ..., {\ dfrac {s} {n + 1}} \ right)}$

Si noti che ciò equivale a mostrare che l'aspettativa del prodotto di numeri distinti presi da numeri positivi di una data somma è massima quando questi numeri sono uguali. $K$ $non$ $non$

Geometricamente:

Tra tutti gli iperparallelepipedi rettangolari (o ortotopi) di dimensione della somma delle lunghezze dei bordi dati, quello che ha la media maggiore degli ipervolumi delle cellule è l'ipercubo. Per o 3: tra tutti i parallelepipedi rettangolari con la somma delle lunghezze dei bordi dati, quello con l'area (o volume) maggiore è il cubo. $non$ $K$ ${\ displaystyle n = 3, k = 2}$

Applicazioni

In Le Trésor des Paradoxes (Éd Belin, 2007), gli autori notano che l'informatico americano Robert Mac Eliece ha stabilito l'interesse del paradosso dei compleanni nell'informatica, per garantire l'affidabilità delle memorie del computer, grazie a codici di rilevamento degli errori, basati in particolare sul lavoro di Richard Hamming ai Bell Laboratories . La strategia dei codici di rilevamento degli errori risulta, da un punto di vista statistico, simile al paradosso dei compleanni. Il paradosso del compleanno viene utilizzato in crittografia per sviluppare attacchi alle funzioni hash . Uno dei vincoli imposti a queste funzioni, per uso crittografico, è quello di produrre poche collisioni , in altre parole, di assumere raramente lo stesso valore su input diversi.

Il paradosso dei compleanni fornisce un limite al numero medio di elementi necessari per avere una collisione con una probabilità , cioè essenzialmente la radice quadrata del numero di valori possibili per la funzione hash, assumendo che questa funzione sia distribuita uniformemente sul suo valori di arrivo. $p = {\ frac {1} {2}}$

Più concretamente, se una funzione hash ha un output di N bit, l'insieme di arrivo ha elementi e ci vuole circa hash di elementi distinti per produrre una collisione con una probabilità del 50%; le uscite della funzione possono essere paragonate a persone con compleanni ripartiti su valori. $2 ^ {N}$ $2 ^ {{\ frac N2}}$ $2 ^ {N}$

Applicazione pratica dell'attacco di compleanno

Supponiamo che Martine voglia costringere Daniel a firmare un contratto molto sfavorevole, il contratto deve essere convalidato dalla sua impronta (valore hash), questa garanzia che il contratto non può essere modificato dopo la firma.

Prepara un contratto equo e uno sfavorevole. Quindi genera automaticamente varianti di ciascuno dei contratti con modifiche estetiche (aggiunta di spazi, utilizzo di sinonimi, riordino dei paragrafi, ecc.). Calcola l'impronta digitale di ogni contratto trovando coppie delle stesse impronte (con e senza modifiche). Non appena riscontrata una collisione, consegna il corrispondente contratto equo a Daniel che lo verifica, lo firma, calcola l'impronta e lo allega al contratto.

Martine fa lo stesso con il contratto sfavorevole e lo presenta a Daniel. Se contesta i termini del contratto che ha firmato, l'impronta dimostra che è impossibile che possa essere cambiato. Sarà comunque possibile per lui opporsi al contratto originario con Martine che dovrebbe comportare la nullità del contratto.

Collegamento con l'identificazione del DNA

In campo forense, le probabilità di identificazione fornite dalla tecnica di fingerprinting del DNA sono spesso poco conosciute. Quindi, se la probabilità che due individui condividano nove loci è di circa uno su 13 miliardi, allora in un database di 65.000 persone, circa 116 coppie di individui avrebbero 9 dei 13 loci in comune usati per scopi di identificazione.

Aneddoto

In The Book That Makes Crazy , Raymond Smullyan dice di aver chiesto ai suoi 19 studenti di stabilire la formula. Dopo l'applicazione digitale, conclude che c'è molto meno di una possibilità su due (poco meno del 38%) che due alunni compiano il loro compleanno lo stesso giorno. Uno studente risponde che sta scommettendo che è lo stesso. L'insegnante chiama chiedendo agli studenti di dare la loro data di nascita e ride prima della fine, seguito da tutta la classe, ricordando che due dei suoi studenti sono gemelli .

Note e riferimenti

Ross 2014 , p. 37.
" Attacco" compleanni " "
Leila Schneps e Coralie Colmez ( tradotto dall'inglese da Coralie Colmez), la matematica in tribunale: errori di calcolo fanno errori giudiziari [ “ Math on Trial. Come i numeri vengono usati e maltrattati in aula ”], Paris, Seuil , coll. "Scienza aperta", 280 p. ( ISBN 978-2-02-110439-4 ) , cap. 5 ("L'affare Diana Sylvester: analisi di un colpo freddo").
Smullyan 1982 , p. 6.

Appendici

Bibliografia

[Ross 2014] (en) Sheldon Ross, A First Course in Probability , Pearson ,2014, 467 p. ( ISBN 978-0-321-79477-2 e 032179477X ) , cap. 2.
[Smullyan 1982] (en) Raymond Smullyan , The Lady or the Tiger? ["Il libro che ti fa impazzire"],1982, 226 p. ( ISBN 0-8129-2117-8 ).