Come funzionano i generatori di numeri casuali e come capire se sono equi

Quando premi "Genera" su un generatore di numeri casuali, un computer, che è progettato per eseguire istruzioni con precisione, produce qualcosa che nessuno può prevedere. Questa guida spiega come funziona, qual è il modo più comune in cui un generatore può essere sottilmente iniquo e come valutare se i risultati sono davvero casuali.

Tre tipi di casualità

Generatori di numeri pseudocasuali

Un generatore di numeri pseudocasuali (PRNG) è una formula. Parte da un valore chiamato seme (seed) e lo trasforma ripetutamente per produrre una sequenza che sembra casuale. Con lo stesso seme, produce di nuovo esattamente la stessa sequenza. È utile per simulazioni e videogiochi che hanno bisogno di risultati ripetibili.

Math.random() di JavaScript è un PRNG. Va bene per animazioni e giochi informali. Tuttavia, i browser non garantiscono che il suo output sia imprevedibile e la specifica non richiede alcun livello di qualità particolare. Non andrebbe usato per password, estrazioni a premi o qualsiasi situazione in cui qualcuno potrebbe trarre vantaggio dall'indovinare il risultato successivo.

Generatori crittograficamente sicuri

Un PRNG crittograficamente sicuro (CSPRNG) è progettato in modo che osservare gli output precedenti non aiuti a prevedere il successivo. I sistemi operativi lo inizializzano a partire da eventi fisici imprevedibili, come il rumore nelle temporizzazioni dell'hardware, e continuano ad aggiungervi nuova entropia. Nei browser è disponibile tramite la Web Crypto API come crypto.getRandomValues().

Generatori hardware di numeri casuali

Un generatore hardware misura un processo fisico, come il rumore elettrico, e lo converte in bit. I processori moderni ne includono uno e i sistemi operativi ne combinano l'output con altre fonti per inizializzare il proprio CSPRNG. La maggior parte delle persone non ha mai bisogno di accedervi direttamente.

Cosa usa Randomify: ogni risultato viene estratto con crypto.getRandomValues() nel tuo browser, supportato da tutti i browser attuali. I numeri vengono generati sul tuo dispositivo e le liste che inserisci non vengono caricate online per generare un risultato.

L'iniquità nascosta: il bias del modulo

Una fonte casuale fornisce bit, non "un numero da 1 a 6". È proprio nel passaggio dall'uno all'altro che molti generatori sbagliano.

Supponiamo che una fonte produca un byte casuale, cioè un numero intero da 0 a 255, e che un programma debba simulare il lancio di un dado. La scorciatoia è prendere il resto della divisione per 6 e aggiungere 1. Ma 256 non è un multiplo di 6: 256 = 42 × 6 + 4. I resti 0, 1, 2 e 3 si possono ottenere ciascuno in 43 modi, mentre 4 e 5 solo in 42. Le facce da 1 a 4 sono leggermente più probabili del 5 e del 6.

La differenza è piccola, 43/256 invece di 42/256, ma si tratta di una distorsione sistematica, non di una variazione casuale. Più l'intervallo è grande rispetto alla fonte, più la distorsione cresce.

La soluzione è il campionamento con rifiuto (rejection sampling): si scarta ogni valore grezzo che cade nell'ultimo blocco incompleto e si estrae di nuovo. Nell'esempio del byte vengono accettati solo i valori da 0 a 251, quindi ogni faccia ha esattamente 42 modi di uscire. Randomify usa valori a 32 bit con campionamento con rifiuto, perciò ogni numero del tuo intervallo è ugualmente probabile.

Provalo con qualsiasi intervallo:

Mescolare in modo equo

Estrarre nomi da una lista o dividere le persone in squadre richiede un mescolamento equo: ogni ordine possibile deve essere ugualmente probabile.

Il metodo standard è l'algoritmo di Fisher–Yates. Partendo dall'ultimo elemento, lo si scambia con un elemento scelto in modo uniformemente casuale tra quelli non ancora fissati, compreso sé stesso, poi ci si sposta di una posizione a sinistra. Con n elementi, produce ciascuno degli n! ordini possibili con uguale probabilità.

Una scorciatoia molto diffusa è ordinare la lista con confronti casuali. Non produce ordini equiprobabili e la distorsione dipende dall'algoritmo di ordinamento. Il selettore di nomi e il generatore di squadre di Randomify usano Fisher–Yates.

I risultati casuali sembrano meno casuali di quanto ci si aspetti

Le persone tendono ad aspettarsi che le sequenze casuali si alternino più di quanto facciano davvero. Una vera sequenza casuale contiene serie, raggruppamenti e ripetizioni.

Quindi una serie di sei teste su cento lanci non è la prova di un problema: sarebbe più sorprendente non vederla. Lo stesso vale per un generatore di numeri casuali che restituisce lo stesso numero due volte di fila. Con un intervallo da 1 a 10, succederà più o meno una volta ogni dieci estrazioni.

Provalo tu stesso: lancia 100 monete insieme e cerca la serie più lunga.

Come verificare se un generatore è equo

Non puoi dimostrare che un generatore sia equo partendo da pochi risultati, ma puoi controllare se ci sono problemi evidenti:

1. Raccogli molti risultati. I campioni piccoli variano molto. Per un generatore da 1 a 6, raccogli centinaia o migliaia di estrazioni, non venti.
2. Confronta le frequenze con quelle attese. Ogni valore dovrebbe comparire all'incirca con la stessa frequenza. Gli statistici usano il test del chi quadrato per misurare se le differenze sono più grandi di quelle che il caso produrrebbe di solito.
3. Guarda le sequenze, non solo i conteggi. Un generatore potrebbe produrre frequenze perfette ripetendo ciclicamente 1, 2, 3, 4, 5, 6. Controlla anche ripetizioni e serie.
4. Chiedi come funziona. Uno strumento affidabile dovrebbe dire quale fonte casuale usa e come la converte in un intervallo.

Per usi in cui la posta in gioco è alta, come chiavi di sicurezza, estrazioni regolamentate per legge o campionamenti scientifici, usa un generatore documentato che rispetti lo standard pertinente e conserva una documentazione del procedimento.

Domande frequenti

Il numero casuale di un computer è davvero casuale? Un CSPRNG è deterministico una volta inizializzato, ma il suo seme deriva da fenomeni fisici imprevedibili e in pratica il suo output non può essere previsto senza conoscerne lo stato interno. Per estrazioni quotidiane, giochi e password è la scelta giusta.

Posso riprodurre un risultato in seguito? Non con un generatore crittografico, ed è voluto. Per rendere verificabile un'estrazione, registra lo schermo o falla davanti a testimoni, come descritto in come organizzare una lotteria online equa.

Perché ho ottenuto lo stesso numero due volte? Perché ogni estrazione è indipendente. Disattiva "Consenti duplicati" se ti serve che ogni risultato sia diverso, ad esempio quando estrai più vincitori.