Mescolare è più difficile di quanto sembri: un milione di esecuzioni del mescolamento in una riga

Un milione di mescolamenti di quattro elementi

Quattro elementi hanno ventiquattro ordinamenti. È abbastanza piccolo da contare in modo esaustivo, ed è questo che ne fa il caso di prova giusto: lancia un mescolamento un milione di volte, conta quanto spesso esce ciascuno dei ventiquattro, e un mescolamento equo deve mettere circa 41 667 in ogni casella. Tutto ciò che favorisce sistematicamente alcuni ordinamenti si vedrà come una gobba, e un solo numero — il chi quadrato — condensa l'intera tabella in un verdetto. Con 23 gradi di libertà un metodo equo segna intorno a 23, e qualsiasi cosa sopra 27,32 accadrebbe per puro caso in meno del 5 % dei casi.

La riga singola ha segnato 125 397. Non 30, non 300 — cinquemila volte la soglia. L'ordinamento più frequente, BADC, è uscito 62 810 volte; il più raro, DBCA, 30 998. L'ordine iniziale ABCD è sopravvissuto intatto 62 485 volte, una volta e mezza più del dovuto. Lo stesso milione passato per un Fisher-Yates scritto bene ha prodotto 10,3, che è l'aspetto di un metodo equo: gli estremi erano 41 434 e 41 879, una dispersione di circa l'1 %. Estendere la prova a cinque elementi allarga ancora il divario — 229 683 contro 89,0 — perché ogni elemento in più dà all'algoritmo di ordinamento una decisione in più da prendere male.

Non ventiquattro probabilità, ma due

I conteggi non sono sparsi. Ordinati, cadono in due gruppi stretti: otto ordinamenti intorno a 62 500 e sedici intorno a 31 250. Sono esattamente 1/16 e 1/32 di un milione, e l'aritmetica torna — 8 × (1/16) + 16 × (1/32) = 1. Altri quattro milioni di esecuzioni hanno testato direttamente quell'ipotesi e prodotto un chi quadrato di 19,7 con 23 gradi di libertà, un buon adattamento. Quindi il mescolamento in una riga su questo motore non è approssimativamente uniforme con un tremolio: è una distribuzione a due valori in cui metà della massa di probabilità è stipata in un terzo dei risultati.

Gli otto ordinamenti favoriti condividono una proprietà che vale la pena notare: ABCD, ABDC, ADBC, BACD, BADC, BDAC, DABC e DBAC tengono tutti la C fuori dalle prime due posizioni. Non è misticismo, è l'algoritmo di ordinamento che traspare. Un array di quattro elementi è corto, quindi V8 non lascia mai il suo percorso di inserimento binario; il comparatore viene chiamato 4,5 volte in media, e 4,5 lanci di moneta non possono generare 24 esiti equiprobabili, perché 24 non divide alcuna potenza di due. La distorsione è cotta nella forma dell'albero decisionale ancor prima che intervenga il caso.

La distorsione appartiene al motore, non al linguaggio

ECMA-262 richiede che la funzione di confronto passata a sort sia un comparatore coerente: transitivo, antisimmetrico e che dia la stessa risposta per la stessa coppia ogni volta. Un comparatore costruito su Math.random rompe tutti e tre in una sola chiamata. La risposta della specifica non è definire che cosa accade, ma dire che se il comparatore è incoerente il risultato dell'ordinamento è definito dall'implementazione. Quella sola frase è tutta la storia. Non hai scritto un mescolamento con statistiche insolite — hai scritto un programma la cui uscita lo standard rifiuta di specificare.

La conseguenza pratica è che questi conteggi misurano un motore a una versione, non una costante universale. V8 ha cambiato il suo ordinamento più di una volta; un'esecuzione su un altro motore, o sullo stesso dopo un aggiornamento, produrrà un'altra distribuzione bitorzoluta, e un array abbastanza lungo da innescare il percorso di fusione ne produrrà un'altra ancora. Nulla nello standard lo vieta, e nulla ti avvisa quando succede. Un mescolamento le cui proprietà statistiche si spostano quando si applica una patch al runtime non è un mescolamento testabile.

Fisher-Yates e l'errore di indice che lo rovina

L'algoritmo corretto — l'Algoritmo P di Knuth — percorre l'array dall'ultimo indice fino al secondo, e a ogni posizione i estrae un indice j uniformemente fra 0 e i incluso, poi scambia le posizioni i e j. Tre dettagli reggono l'intera dimostrazione. Il ciclo scende. L'estrazione include la stessa i, quindi un elemento può restare dov'è. E l'intervallo si restringe di uno a ogni iterazione, così il numero di percorsi di esecuzione è n × (n−1) × … × 2 = n!, esattamente il numero di permutazioni. Una biiezione fra percorsi di esecuzione ed esiti è ciò che significa uniformità, e vale per ogni n, non solo per quelli che hai provato.

Cambia un carattere e si rompe. La variante comune percorre l'array verso l'alto ed estrae j sull'intero array ogni volta, il che sembra più casuale e non lo è. Quella versione ha n^n percorsi di esecuzione, e n^n non è mai multiplo di n! per n oltre 2, quindi alcune permutazioni devono essere raggiungibili in più modi di altre. Misurata sullo stesso milione di esecuzioni ha segnato 29 913 — mille volte la soglia, con l'ordinamento più frequente a 58 698 e il più raro a 31 233. È il più pericoloso dei due errori proprio perché somiglia alla versione del manuale e supera ogni ispezione a occhio.

Distorsione del modulo: il secondo modo di storcere un mescolamento

Fisher-Yates ha bisogno di un intero uniforme in un intervallo, e il modo ovvio di ricavarlo da un valore casuale a 32 bit è prenderne il modulo rispetto alla dimensione dell'intervallo. È uniforme solo se l'intervallo divide esattamente 2^32. Di solito non lo fa: 2^32 modulo 52 è 48, quindi 48 dei 52 esiti ricevono una controimmagine in più degli altri quattro. A 32 bit l'eccesso che ne deriva è intorno al milionesimo di punto percentuale e nessuno lo vedrà mai. Riduci la sorgente a un singolo byte e la stessa aritmetica diventa brutale: 256 modulo 52 è ancora 48, ma ora 48 esiti ottengono 5 controimmagini e 4 ne ottengono solo 4 — un eccesso del 25 %, visibile in poche migliaia di estrazioni.

La correzione è il campionamento per rifiuto e non costa quasi nulla. Calcola il massimo multiplo dell'intervallo che entra nella tua sorgente — per un'estrazione a 32 bit e un intervallo di 52 è 2^32 meno 48 — riestrai ogni volta che il valore finisce sopra, e prendi il modulo solo dei valori accettati. La regione di rifiuto è di 48 valori su 4 294 967 296, quindi il numero atteso di estrazioni extra è circa uno su novanta milioni. Paghi un confronto per chiamata e compri uniformità esatta: il miglior scambio di tutto questo articolo.

Math.random non è una mescolatrice di carte

Anche un Fisher-Yates perfetto è limitato dal generatore sottostante. Un mazzo di 52 carte ha 52! ordinamenti, cioè 8,07 × 10^67, ovvero circa 2^225,6. Il generatore dietro Math.random in V8 porta 128 bit di stato interno, quindi può raggiungere al massimo 2^128 ≈ 3,4 × 10^38 ordini di mazzo — una frazione di 4,2 × 10^-30 del totale. La stragrande maggioranza dei mescolamenti di un mazzo standard semplicemente non è producibile, per quante volte tu lo chiami. È un tetto matematico duro, non un difetto di implementazione, e vale per ogni generatore pseudocasuale con meno stato dello spazio che gli si chiede di coprire.

Altre due proprietà contano nella pratica. Math.random non è inizializzabile con un seme né riproducibile: la specifica non offre modo di fissare un punto di partenza e richiede esplicitamente che realm distinti producano sequenze distinte, quindi un bug visto una volta non si può rigiocare. E non è imprevedibile in senso crittografico — un osservatore che veda abbastanza uscite può ricostruire lo stato e prevedere il resto. Se qualcuno potesse guadagnare indovinando il tuo mescolamento — una lotteria, un'estrazione con premio, un token di sicurezza, qualsiasi cosa mescolata davanti a un pubblico — usa crypto.getRandomValues, con il campionamento per rifiuto sopra. Se il mescolamento è una pianta dei posti o un quiz di allenamento, Math.random con un Fisher-Yates corretto va benissimo.

Domande frequenti

Ordinare con un comparatore casuale è sempre distorto, o solo in alcuni browser?

Sempre distorto, ma distorto in modo diverso ovunque. Lo standard richiede un comparatore coerente e dichiara il risultato definito dall'implementazione quando non ne riceve uno, quindi ogni motore — e ogni versione di ogni motore — produce la propria distribuzione bitorzoluta. Su Node 26.3.0 il caso a quattro elementi collassa su due sole probabilità, 1/16 per otto ordinamenti e 1/32 per gli altri sedici, cosa che un test da quattro milioni di esecuzioni conferma con un chi quadrato di 19,7 su 23 gradi di libertà. Un altro motore non ti darà quei numeri esatti: te ne darà altri, sbagliati. È peggio di una distorsione nota e fissa, perché non c'è nulla di stabile su cui testare e un aggiornamento del runtime può cambiare la statistica della tua estrazione senza cambiare una riga di codice.

Come scrivo Fisher-Yates in modo che sia davvero corretto?

Parti dall'ultimo indice e scendi fino all'indice 1. A ogni posizione i, estrai j uniformemente fra 0 e i incluso, poi scambia gli elementi in i e j. Tre cose devono essere giuste insieme: il ciclo scende, l'estrazione include la stessa i, e l'intervallo si restringe di uno a ogni iterazione. Se le hai tutte e tre, il numero di percorsi di esecuzione è esattamente n fattoriale, uno per permutazione, ed è questo a rendere l'uscita uniforme per ogni lunghezza di array e non solo per quelle che hai provato. La variante che sale ed estrae j sull'intero array ogni volta è l'errore classico: ha n elevato a n percorsi, che sopra n = 2 non è mai multiplo di n fattoriale, e ha misurato un chi quadrato di 29 913 nel test a quattro elementi dove un mescolamento equo segna intorno a 23.

Mi serve crypto.getRandomValues, o basta Math.random?

Il test è se qualcuno potrebbe guadagnare prevedendo l'esito. Mescolare domande di un quiz, disporre una classe, randomizzare l'ordine di esercizi: Math.random dentro un Fisher-Yates corretto va bene, e la differenza non si vedrà mai. Estrarre un premio, scegliere un campione di audit, generare qualsiasi cosa che si comporti come un token: usa crypto.getRandomValues, perché Math.random è un generatore pseudocasuale il cui stato interno si ricostruisce da una serie modesta di uscite, dopodiché ogni valore futuro è prevedibile. C'è una seconda ragione, più silenziosa. Un mazzo di 52 carte ha circa 2^225,6 ordinamenti e il generatore di V8 porta 128 bit di stato, quindi raggiunge al massimo un ordine di mazzo su 10^30. Quel tetto deriva dalla dimensione dello stato, non dalla qualità dell'algoritmo.

Che cos'è esattamente la distorsione del modulo, e quando conta?

È ciò che accade quando comprimi un intervallo che non divide la tua sorgente. Prendi un valore casuale a 32 bit e riducilo modulo 52: ottieni un numero da 0 a 51, ma 2^32 diviso 52 lascia resto 48, quindi 48 di quegli esiti hanno un valore sorgente in più rispetto ai quattro restanti. A 32 bit l'eccesso che ne segue è intorno al milionesimo di punto percentuale — davvero trascurabile. La stessa aritmetica su una sorgente a 8 bit è un altro animale: 256 modulo 52 è anch'esso 48, ma ora gli esiti favoriti ricevono 5 valori sorgente e gli altri solo 4, un eccesso del 25 % che poche migliaia di estrazioni smascherano. La correzione è il campionamento per rifiuto: rifiuta ogni estrazione pari o superiore al massimo multiplo dell'intervallo che entra nella sorgente, il che per 32 bit e intervallo 52 scarta 48 valori su 4,29 miliardi, circa un'estrazione su novanta milioni.

Come testo il mio mescolamento senza basi di statistica?

Riduci il problema finché puoi contare tutto. Prendi un array di quattro elementi, mescolalo un milione di volte e tieni il conto di quante volte esce ciascuno dei ventiquattro ordinamenti — basta un dizionario indicizzato sulla stringa concatenata. Poi guarda due numeri: il conteggio più alto diviso il più basso, e il conteggio dell'ordine originale non mescolato. Un mescolamento equo dà un rapporto vicino a 1,01 a quella dimensione campionaria e lascia l'ordine originale intorno a 1 su 24. Nelle misure qui riportate, Fisher-Yates ha dato 1,011 e l'ordinamento in una riga 2,026, con l'ordine intatto che compare il 50 % più del dovuto. Non ti serve il chi quadrato per vedere quel divario; il chi quadrato ti dice solo quanto sia impossibile, e 125 397 contro una soglia di 27,32 è più o meno il massimo dell'impossibile che una misura possa raggiungere.