Paradosso del compleanno

Il paradosso del compleanno (o problema del compleanno) è un paradosso di teoria della probabilità definito nel 1939 da Richard von Mises.^[1]^[2]

Il paradosso afferma che la probabilità che almeno due persone in un gruppo compiano gli anni lo stesso giorno è largamente superiore a quanto potrebbe dire l'intuito: infatti già in un gruppo di 23 persone la probabilità è circa 0,51 (51%); con 30 persone essa supera 0,70 (70%), con 50 persone tocca addirittura 0,97 (97%), anche se per arrivare all'evento certo occorre considerare un gruppo di almeno 366 persone (367 se si considera l'anno bisestile).^[3]

Per effettuare il calcolo, si ricorre alla formula per la probabilità condizionata: per rendere più semplice il calcolo si assume che gli anni siano tutti di 365 giorni. Aggiungere il giorno bisestile peggiora leggermente la probabilità, ma in compenso il fatto che i compleanni non siano equiprobabili la alza. Si assume che tutti i giorni dell'anno siano equiprobabili per nascere, anche se in realtà non è così.^[4]

Il modo più semplice per calcolare la probabilità P(p) che ci siano almeno due persone appartenenti ad un gruppo di p persone che compiano gli anni lo stesso giorno è calcolare dapprima la probabilità P₁(p) che ciò non accada. Il ragionamento è questo: data una qualunque persona del gruppo (indipendentemente dalla data del suo compleanno), vi sono 364 casi su 365 in cui il compleanno di una seconda persona avvenga in un giorno diverso; se si considera una terza persona, ci sono 363 casi su 365 in cui compie gli anni in un giorno diverso dalle prime due persone e via dicendo. Esprimendo in formule quanto sopra, la probabilità che tutti i p compleanni cadano in date diverse è:

P_{1}(p)={\frac {364}{365}}\cdot {\frac {363}{365}}\cdots {\frac {365-p+1}{365}}={\frac {364!}{365^{p-1}(365-p)!}}

e dunque la probabilità del suo evento complementare, cioè che esistano almeno due compleanni uguali, è

$P(p)=1-P_{1}(p)=1-{\frac {364!}{365^{p-1}(365-p)!}}$

Questo paradosso ha importanti ricadute nella crittografia e nel dimensionamento del blocco da cifrare. In particolare nell'ambito della crittografia si utilizza il paradosso del compleanno per indicare che le funzioni hash crittografiche abbiano la proprietà di "resistenza forte alle collisioni". Ad esempio una funzione di hash che produce un risultato su N bit sarà reputata insicura quando qualcuno sarà in grado di generare $2^{N/2}={\sqrt {2^{N}}}$ risultati. Con $2^{N/2}$ hash infatti, la probabilità che tra di essi ci siano delle collisioni è maggiore del 50%. Il risultato evidentemente è ben al di sotto dei $2^{N-1}$ elementi necessari suggeriti dall'intuito.

[1]
Jim Al-Khalili, Il paradosso del compleanno, su ilpost.it, 5 febbraio 2013.
[2]
Il termine paradosso non è da intendersi nel senso di una contraddizione logica (antinomia), ma nel senso che la verità matematica contraddice l'intuizione naturale. Molte persone credono che questa probabilità cresca molto più lentamente con la numerosità del gruppo. In particolare sembra quasi assurdo che bastino 50 persone per avere una probabilità prossima al 100%.
[3]
Si tratta di un'applicazione immediata del cosiddetto principio dei cassetti: con un numero di persone pari al numero dei giorni in un anno (365, o 366 in anno bisestile) permane la possibilità, pur minima, che esse compiano gli anni in giorni tutti distinti, coprendo in tal modo tutte le date possibili; è solo con l'aggiunta di un'ulteriore persona che questa, in assenza di altre date disponibili, dovrà necessariamente avere lo stesso compleanno di una delle precedenti, rendendo quindi certo l'evento che almeno due persone condividano il medesimo compleanno.
[4]
Gianni Balduzzi, Mese di nascita, quando si nasce di più in Europa?, su termometropolitico.it, 7 settembre 2017. URL consultato il 25 luglio 2022.