Il paradosso del compleanno

Il paradosso

Chiedi a qualcuno quanti invitati servono a una festa perché due di loro abbiano probabilmente lo stesso compleanno, e quasi tutti risponderanno circa 180, la metà di 365. La risposta vera è 23: la probabilità è allora del 50,7%. Con 57 invitati è del 99%. Si chiama paradosso non perché sia contraddittorio, ma perché va così fortemente contro la nostra intuizione.

Perché l’intuizione sbaglia

In una stanza ragioniamo inconsciamente a partire da noi stessi: qual è la probabilità che qualcuno abbia il mio stesso compleanno? Con 365 giorni questa probabilità è piccola. Ma il paradosso riguarda tutte le coppie possibili nella stanza, non una coincidenza con una persona in particolare: A e B, B e C, A e C, e così via. Con 23 persone si possono formare 253 coppie diverse, e ognuna di esse potrebbe avere lo stesso compleanno.

Le coppie crescono con il quadrato

n persone formano n × (n − 1) / 2 coppie: 10 persone formano 45 coppie, 23 ne formano 253, 57 ne formano 1.596 e 100 ne formano 4.950. Ogni coppia ha lo stesso compleanno con probabilità 1/365, quindi 253 coppie danno in media 253/365 ≈ 0,69 coppie con il compleanno in comune. Raddoppiando il gruppo le coppie all’incirca si quadruplicano, ed è per questo che la probabilità di un compleanno in comune schizza verso l’alto.

Il calcolo passo dopo passo

Il modo più semplice è calcolare la probabilità che nessuno abbia il compleanno in comune con un altro e sottrarla dal 100%. La prima persona occupa un giorno qualsiasi. La seconda persona ha una probabilità di 364/365 di non avere lo stesso compleanno. La terza ha una probabilità di 363/365 di differire dalle prime due, e così via. Per 23 persone:

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3%

Poiché la probabilità che tutti abbiano compleanni diversi è del 49,3%, l’evento contrario, almeno un compleanno in comune, ha probabilità 100% − 49,3% = 50,7%.

Qualcuno con il tuo stesso compleanno

La probabilità che qualcuno abbia il tuo stesso compleanno è un’altra questione. Ciascuna delle altre n − 1 persone manca il tuo compleanno con probabilità 364/365, quindi la probabilità che qualcuno ce l’abbia è 1 − (364/365)ⁿ⁻¹. Con 23 persone è solo del 5,9%, e servono altre 253 persone prima che superi il 50%. Solo 22 delle 253 coppie in un gruppo di 23 ti includono.

La regola della radice quadrata e gli attacchi del compleanno

Con N valori equiprobabili, una ripetizione diventa probabile dopo circa 1,2 × √N estrazioni: √365 ≈ 19, e 1,2 × 19 ≈ 23. Questo conta moltissimo nella sicurezza informatica. Gli attaccanti usano gli attacchi del compleanno per trovare due input con lo stesso hash crittografico, una collisione, per esempio per falsificare una firma digitale. Grazie al paradosso del compleanno servono loro molti meno tentativi di quanto suggerisca l’intuizione: circa 2⁶⁴ per un hash a 128 bit invece di 2¹²⁸. Per questo le funzioni di hash moderne come SHA-256 hanno output lunghi.

Esploralo in PictorX

Apri il paradosso del compleanno e un gruppo di 23 persone si forma su un cerchio, una persona alla volta. Ogni nuovo arrivato aggiunge una linea verso ciascuna persona già presente, e la didascalia conta le coppie. I loro compleanni cadono su un calendario, e un giorno con due o più compleanni si illumina. Sotto, il calcolo per la dimensione del gruppo sta accanto alla percentuale di gruppi testati con un compleanno in comune, e il grafico mostra la probabilità per ogni dimensione del gruppo, per due persone qualsiasi e per qualcuno con il tuo stesso compleanno. Aggiungi le persone una alla volta, scegli da 2 a 366 persone, testa fino a 100.000 gruppi a un ritmo fino a 10.000 al secondo, oppure testa tutte le dimensioni del gruppo e guarda i punti tracciare la curva.