In una stanza con 23 persone, la probabilità che almeno due compiano gli anni lo stesso giorno supera il 50%. Con 50 persone si arriva intorno al 97%. Quasi tutti, sentendolo per la prima volta, pensano a un errore: con 365 giorni disponibili, 23 persone sembrano pochissime. Non è un vero paradosso, ma un esempio di come sottovalutiamo il numero di coppie che si possono formare in un gruppo. E ha conseguenze molto concrete in informatica.
Il calcolo esatto
Assumiamo 365 giorni equiprobabili e ignoriamo gli anni bisestili. Calcolare direttamente «almeno due persone condividono il compleanno» è scomodo, perché i casi sono tanti. Conviene usare il complementare: la probabilità che tutti i compleanni siano diversi.
- La prima persona può avere qualunque compleanno: 365/365.
- La seconda deve evitare quello della prima: 364/365.
- La terza deve evitare i due già presi: 363/365.
- E così via, fino alla n-esima: (365 − n + 1)/365.
Moltiplicando:
P(tutti diversi) = (365 · 364 · … · (365 − n + 1)) / 365ⁿ
e la probabilità cercata è 1 meno questo valore.
| Persone | P(almeno un compleanno in comune) |
|---|---|
| 10 | circa 12% |
| 23 | circa 51% |
| 30 | circa 71% |
| 40 | circa 89% |
| 57 | circa 99% |
Perché il numero è così basso
L'intuizione sbaglia perché pensiamo alla domanda sbagliata. Ci chiediamo: «qualcuno compie gli anni il mio stesso giorno?». Quella probabilità, con 22 altre persone, è davvero bassa: 1 − (364/365)²² ≈ 6%. Ma la domanda riguarda qualunque coppia del gruppo. Con 23 persone le coppie possibili sono 23 · 22 / 2 = 253. Ogni coppia ha una piccola probabilità di coincidere, ma 253 piccole occasioni sommate diventano tante.
Il numero di coppie cresce con il quadrato del numero di persone, mentre il numero di giorni resta fisso. È questa crescita quadratica a rendere le collisioni sorprendentemente rapide.
Una formula approssimata
Per valori grandi c'è un'approssimazione molto comoda. Se n oggetti vengono assegnati a caso tra N valori possibili, la probabilità di almeno una collisione è circa:
P ≈ 1 − e^(−n² / 2N)
Da qui si ricava una regola pratica: la probabilità di collisione arriva al 50% quando n è circa 1,18 · √N. Per N = 365 si ottiene circa 22,5, coerente con il risultato esatto. Più in generale, le collisioni diventano probabili quando il numero di elementi si avvicina alla radice quadrata dello spazio disponibile.
Le conseguenze in informatica
Funzioni hash
Una funzione hash con un'uscita di b bit ha 2ᵇ valori possibili. Si potrebbe pensare che servano circa 2ᵇ tentativi per trovare due input con lo stesso hash. Il paradosso del compleanno dice invece che ne bastano circa 2^(b/2). Un hash a 64 bit offre quindi una resistenza alle collisioni dell'ordine di 2³², circa quattro miliardi di tentativi: un numero alla portata di un normale computer. È il motivo per cui, quando serve resistenza alle collisioni, si usano hash con uscite di almeno 256 bit: la sicurezza effettiva contro le collisioni è circa la metà dei bit.
Identificativi casuali
Lo stesso ragionamento vale per gli ID generati a caso: codici di prenotazione, token, nomi di file temporanei, chiavi primarie casuali. Supponiamo di generare codici casuali di 6 cifre, un milione di valori possibili. Con circa 1.180 codici emessi, c'è già una probabilità del 50% che due coincidano. Se il sistema non controlla i duplicati, una collisione non è un evento remoto ma quasi una certezza dopo qualche migliaio di emissioni.
Gli UUID versione 4 contengono 122 bit casuali. La radice quadrata dello spazio è dell'ordine di 2⁶¹, un numero enorme: per questo, in condizioni normali, le collisioni sono trascurabili, a patto che il generatore di numeri casuali sia di buona qualità.
Tabelle hash
Anche nelle strutture dati le collisioni arrivano presto. Inserendo elementi in una tabella con m posizioni, la prima collisione è attesa dopo circa √m inserimenti, ben prima che la tabella sia piena. Per questo le tabelle hash sono progettate per gestire le collisioni come caso normale, non come eccezione.
Le ipotesi contano
Il calcolo assume compleanni uniformemente distribuiti. Nella realtà le nascite non sono perfettamente uniformi durante l'anno, e una distribuzione non uniforme aumenta la probabilità di coincidenze: se alcuni valori sono più frequenti, è più facile che due elementi cadano sullo stesso. Lo stesso vale per i generatori casuali difettosi: un generatore che produce alcuni valori più spesso di altri provoca collisioni prima di quanto preveda la teoria.
In sintesi
- Con 23 persone la probabilità di un compleanno condiviso supera il 50%.
- Il punto chiave è il numero di coppie, che cresce con il quadrato del gruppo.
- Le collisioni diventano probabili intorno alla radice quadrata dello spazio dei valori.
- Per questo un hash a b bit resiste alle collisioni solo fino a circa 2^(b/2) tentativi.
- Distribuzioni non uniformi rendono le collisioni ancora più probabili.
