Come utilizzare (3 passaggi)
- Seleziona Giorni (d=365/366) o Bit (d=2^b).
- Inserisci n oppure passa a "Target -> n".
- Copia un URL condivisibile o esegui una simulazione.
Ingressi
Risultati
- P(collisione)
- —
- P(nessuna collisione)
- —
- Circa (Poisson)
- —
- Errore approssimativo (abs/rel)
- — / —
Obiettivo → richiesto n
- Richiesto n (esatto)
- —
- Richiesto n (circa)
- —
Grafico
P(collisione) vs n (blu). La linea arancione segna il tuo attuale n.
Suggerimento: passa il mouse (o tocca) sul grafico per vedere la probabilità a uno specifico n. La tabella rapida seguente fornisce i valori accessibili.
Tavola veloce
| n | P(collisione) | p (0..1) |
|---|
Simulazione (Monte Carlo)
- P stimato (collisione)
- —
- IC al 95% (Wilson)
- —
- |p̂ − p_esatto|
- —
Note e formule
- Esatto: P(nessuna collisione) = (d)_n / d^n, P(collisione) = 1 − P(nessuna collisione).
- Approssimativamente: P(collisione) ≈ 1 − exp(−n(n−1)/(2d)).
- Ciò presuppone una distribuzione uniforme su valori d.
Esempi
Classico: d=365, n=23
P(collisione) è circa 0,5073 (≈ 50,7%).
Collisioni hash: 32 bit
Utilizza la modalità bit con b=32 (d=2^32). Il target 0,5 dà n≈77.164.
Come usare i risultati sulle collisioni
Parti dalla probabilità esatta per la dimensione attuale del gruppo, poi confrontala con approssimazione e simulazione per vedere quanto velocemente le collisioni diventano probabili.
Quando conta il valore esatto
Per esempi di classe o piccoli gruppi, il valore esatto è il riferimento. L'approssimazione è utile quando serve una stima rapida per domini grandi, come hash o generatori di ID.
Come leggere la simulazione
Usa la simulazione come controllo intuitivo. Se il risultato empirico si allontana dal valore esatto, aumenta il numero di prove o mantieni fisso il seme per riprodurre la corsa.
Esempio svolto
Con d = 365 e n = 23, la probabilità esatta di collisione è circa 50,7%. È l'esempio classico del compleanno e mostra perché il numero di coppie cresce rapidamente.
Vedi anche
Domande frequenti
Qual è il paradosso del compleanno?
È la probabilità di collisione quando si estraggono n campioni da d valori ugualmente probabili. Con d=365, n=23 dà già circa il 50%.
Perché si supera il 50% con sole 23 persone?
Il numero di coppie possibili cresce con C(n,2), quindi le collisioni diventano probabili rapidamente.
Qual è la formula esatta?
P(nessuna collisione) = (d)_n / d^n e P(collisione) = 1 − P(nessuna collisione).
Come si calcola l'n richiesto per una probabilità target?
Cerchiamo il più piccolo intero n tale che P(collisione) ≥ target.
In che modo questo si collega alle collisioni di hash (32 bit/64 bit)?
Utilizza la modalità bit (d=2^b). Per 32 bit, il punto del 50% è circa n≈77.164.
Qual è il seme della simulazione?
Un seme rende la simulazione deterministica e riproducibile.
I veri compleanni sono uniformi?
Non perfettamente. Questo strumento utilizza il modello uniforme standard.