Il paradosso del compleanno è un famoso paradosso legato alla teoria della probabilità. La soluzione di questo paradosso va contro il senso comune: bastano \( 23 \) persone affinché si abbia una probabilità del \( 50 \%\) che almeno due di esse compiano gli anni nello stesso giorno.
IN BREVE
Indice
IL PARADOSSO DEL COMPLEANNO
Il paradosso del compleanno venne pubblicato nel 1939 da un matematico statunitense, Richard von Miles. Il paradosso, legato alla teoria della probabilità, afferma che, controintuitivamente, la probabilità che in un gruppo di sole \( 23 \) persone almeno due di esse compiano gli anni lo stesso giorno è superiore al \( 50 \% \). Questa probabilità supera il \( 70 \% \) con un gruppo di \( 30 \) individui ed arriva al \( 97 \% \) se si considera un gruppo di \( 50 \) persone. Ovviamente, per avere l’evento certo, ovvero il \( 100 \% \) di probabilità, sono necessarie \( 366 \) persone, se si considera un anno non bisestile, o \( 367 \) in caso di anno bisestile, in quanto la \( 366esima \) persona (o la \( 367esima \)) condivide necessariamente il giorno del compleanno con un altro.
Procedimento matematico
Per effettuare il calcolo, si può assumere che le nascite nel corso dell’anno siano equiprobabili e che gli anni siano tutti di \( 365 \) giorni. Per calcolare la probabilità che vi siano almeno due persone nate lo stesso giorno in un gruppo di \( n \) persone, conviene calcolare prima la probabilità dell’evento complementare, ovvero che ciò non accada. Quindi, si considerino \( 4 \) persone del gruppo: \( P_1, P_2, P_3 \mbox{ e } P_4 \). La persona \( P_1 \) compirà gli anni in un giorno a scelta dei \( 365 \) giorni dell’anno; affinché la persona \( P_2 \) compia gli anni in un giorno diverso della persona \( 1 \), dovrà festeggiare il compleanno in uno dei \( 364 \mbox { su } 365\) giorni rimanenti, quindi la probabilità che ciò avvenga è:
$$P( \mbox{Compleanno } P_1 \neq P_2) = \frac{364}{365}. $$
Affinché la persona \( P_3 \) abbia un compleanno diverso da \( P_1 \mbox{ e } P_2 \), dovrà compiere gli anni in un giorno diverso da loro, ovvero in uno dei \( 363 \mbox { su } 365\); quindi la probabilità che le \( 3 \) compiano gli anni in giorni diversi è pari al prodotto delle singole probabilità, in quanto gli eventi sono indipendenti (il giorno di nascita di una persona non dipende dalla data di nascita di un’altra persona):
$$P( \mbox{Compleanno } P_1 \neq P_2 \neq P_3) = \frac{364}{365} \cdot \frac{363}{365}.$$
Analogamente, affinché la persona \( P_4 \) abbia un compleanno diverso da \( P_1, P_2 \mbox{ e } P_3 \) deve festeggiare gli anni in uno dei \( 362 \mbox { giorni rimanenti su } 365\); quindi la probabilità che le \( 4 \) persone abbiano compleanni in giorni diversi è:
$$P( \mbox{Compleanno } P_1 \neq P_2 \neq P_3 \neq P_4) = \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365}.$$
Il discorso si può ripetere per la quinta persona del gruppo, la sesta persona del gruppo e così via. Si considerino l’evento \( E= “n \mbox{ persone compiono gli anni in giorni diversi}” \) e l’evento \( E^C= “\mbox{Almeno } 2 \mbox{ persone compiono gli anni lo stesso giorno}” \), complementare di \( E \). Generalizzando il discorso fatto sopra, si ottiene la probabilità dell’evento \( E \):
$$P(E)= \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365 -n +1}{365}=\frac{365!}{365^{n} \cdot (365 -n )!}=\frac{364!}{365^{n-1} \cdot (365 -n )!}. $$
A questo punto, la probabilità che almeno due persone compiano gli anni lo stesso giorno, ovvero l’evento complementare, è data da \(P(E^C)= 1 -P(E) \):
$$P(E^C) = 1 – P(E)=1-\frac{364!}{365^{n-1} \cdot (365 -n )!}. $$
Ad esempio, se si volesse calcolare la probabilità dell’evento \( F=”\mbox{In un gruppo di } 4 \mbox{ persone ci sono almeno due persone che compiono gli anni} \) \(\mbox{ lo stesso giorno}”\), si dovrebbe effettuare il calcolo precedente con \( n=4 \):
$$P(F)=1-\frac{364!}{365^{4-1} \cdot (365 -4 )!}=1-\frac{364!}{365^{3} \cdot 361!}=0,016=1,6 \%.$$
Nel caso di \( 23 \) persone, come detto inizialmente, questa probabilità verrebbe maggiore del \( 50 \% \).
Approssimazione
Si consideri l’approssimazione di Taylor della funzione esponenziale (\( e^x=1+x+\frac{x^2}{2}+\frac{x^3}{3}+\cdots \)) al primo ordine:
$$e^x \approx 1+x. $$
La probabilità dell’evento \( E= “n \mbox{ persone compiono gli anni in giorni diversi}” \) è data da:
$$ \begin{array}{rl}
P(E) &= \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365 -n +1}{365} \\
&=\frac{365!}{365^{n} \cdot (365 -n )!}\\
& =1 \cdot \bigl(1-\frac{1}{365} \bigr) \cdot \bigl(1-\frac{2}{365} \bigr) \cdots \bigl(1-\frac{n-1}{365} \bigr). \\
\end{array} $$
Se si sostituisce \( x= – \frac{k}{365} \), allora \( e^{-\frac{k}{365}}=1-\frac{k}{365} \). Quindi, sostituendo nell’espressione sopra e utilizzando la proprietà delle potenze del prodotto di potenze con stessa base e diverso esponente (\( a^x \cdot a^y=a^{x+y} \)), si ottiene:
$$ \begin{array}{rl}
P(E) &= 1 \cdot e^{-\frac{1}{365}} \cdot e^{-\frac{2}{365}} \cdots e^{-\frac{(n-1)}{365}} \\
&=e^{-\frac{1+2+\cdots+(n-1)}{365}} \\
&=e^{-\frac{[(n-1)\cdot n]/2 }{365}}\\
&= e^{-\frac{(n-1)\cdots n }{730}}.
\end{array} $$
Di conseguenza, la probabilità dell’evento \( E^C= “\mbox{almeno } 2 \mbox{ persone compiano gli anni lo stesso giorno}” \), sarà data da:
$$P(E^C) \approx 1- e^{-\frac{(n-1)\cdot n }{730}}. $$
Applicazioni: attacco del compleanno
Questo paradosso trova applicazione in crittografia, tramite l’”attacco del compleanno”, utilizzato per trovare collisioni, (due input che producono lo stesso valore di output), per le funzioni hash. Una funzione hash è una funzione non invertibile che, data in input una sequenza di caratteri di lunghezza arbitraria, restituisce in output una stringa di caratteri alfanumerici, caratteristici del file, di lunghezza predefinita. Spesse volte viene utilizzato il codice di hash per identificare in modo univoco la sequenza di input, come se fosse un’impronta digitale della sequenza in ingresso. Lo scopo dell’attacco del compleanno è quello di cercare di falsificare la sequenza in input affinché, applicando la funzione di hash si ottenga lo stesso output. Per fare questo, vengono valutati diversi dati in input che possono essere scelti in modo casuale. Per avere una probabilità del \( 50 \% \) che l’attacco abbia successo, occorre effettuare \( 1,25 \cdot \sqrt{C} \) tentativi, dove \( C \) è la cardinalità del numero degli elementi generabili dalla funzione di hash. Per ridurre la probabilità che un attacco di questo tipo abbia successo, occorre aumentare la cardinalità dell’insieme.
Fonte
- Il paradosso del compleanno
YouPhysics - Extensions of the birthday surprise
ScienceDirect