Come funziona la selezione casuale ponderata

La selezione casuale ponderata è ciò che usi quando le opzioni non dovrebbero avere la stessa probabilità. I pesi indicano quanto spesso ogni opzione dovrebbe vincere, in media.

Punti chiave

• Probabilità = peso diviso per il peso totale.
• I pesi cumulativi trasformano le opzioni in segmenti dell'intervallo da 0 a 1.
• Un valore casuale sicuro seleziona un punto; vince il segmento corrispondente.
• Ponderato senza sostituzione rimuove il vincitore e rinormalizza i pesi rimanenti.
• Testare l'equità confrontando le frequenze osservate e previste su molte estrazioni.

Casualità uguale rispetto a quella ponderata

Un normale selezionatore casuale tratta ogni opzione allo stesso modo. Ciò è corretto per un sorteggio in classe in cui ogni studente dovrebbe avere le stesse possibilità. Ma molte decisioni reali sono deliberatamente ineguali:

• Un gioco vuole che il bottino comune appaia spesso e che il bottino raro appaia raramente.
• Una lotteria dà ad alcuni partecipanti più biglietti di altri.
• Un test A/B indirizza l'80% degli utenti alla variante di controllo e il 20% a quella nuova.
• Un insegnante vuole che le domande difficili appaiano più spesso di quelle facili.

La casualità ponderata è pur sempre casualità. La differenza è che la distribuzione di probabilità è intenzionale.

I pesi sono probabilità, non conteggi

Il peso di un'opzione non è di per sé una probabilità. È un numero relativo. Per ottenere una probabilità, dividi il peso per la somma di tutti i pesi.

Supponiamo che le opzioni siano:

• A, peso 1.
• B, peso 2.
• C, peso 7.

Il peso totale è 10, quindi le probabilità sono 10%, 20% e 70%. Se pareggiate 100 volte, C dovrebbe vincere circa 70 volte. Se pareggiate solo 10 volte, C potrebbe vincere 4, 6 o anche 0 volte. I campioni piccoli sono rumorosi; i pesi descrivono le aspettative di lungo periodo.

La distribuzione cumulativa

La distribuzione cumulativa trasforma tali pesi in segmenti dell'intervallo da 0 a 1. Con lo stesso esempio:

• A copre da 0,00 a 0,10.
• B copre da 0,10 a 0,30.
• C copre da 0,30 a 1,00.

La larghezza di ogni segmento rappresenta la probabilità dell'opzione. I segmenti non si sovrappongono e insieme coprono l'intero intervallo.

Questo è il motivo per cui la selezione ponderata non necessita di una probabilità separata per ogni opzione. Hai solo bisogno dei pesi e del loro totale.

Campionamento con trasformazione inversa

Il campionamento con trasformata inversa è il modo standard per selezionare da tale distribuzione:

1. Calcolare il peso totale.
2. Scegli un valore casuale compreso tra 0 e il totale.
3. Esplora le opzioni, aggiungendo ciascun peso al totale parziale.
4. Fermarsi alla prima opzione il cui peso cumulativo è maggiore o uguale al valore casuale.

L'opzione selezionata è la vincitrice. Se il valore casuale si ferma nel segmento di A, A vince. Se finisce nel segmento di C, C vince.

L'algoritmo impiega O(n) tempo per estrazione, dove n è il numero di opzioni. È semplice, corretto e più che abbastanza veloce per una pagina con poche dozzine di opzioni.

Con e senza sostituzione

Con la sostituzione, ogni estrazione è indipendente. La stessa opzione può vincere più di una volta. Questo è il modello giusto quando ogni estrazione dovrebbe utilizzare le probabilità originali.

Senza sostituzione, l'opzione selezionata viene rimossa dal pool. I pesi rimanenti vengono rinormalizzati prima dell'estrazione successiva. Se A viene rimosso, il totale rimanente è inferiore, quindi B e C ottengono quote maggiori dell'estrazione successiva.

Senza sostituzione non è uno shuffle. Non produce ogni permutazione con uguale probabilità. Produce un ordine ponderato: le opzioni con pesi maggiori tendono ad apparire prima.

Il metodo alias per le scelte ad alto volume

Per un numero elevato di estrazioni o set di opzioni molto grandi, esiste un'alternativa più veloce chiamata metodo alias. Costruisce una tabella di ricerca una volta e poi risponde a ciascuna estrazione in tempo costante.

Il metodo alias è utile nei giochi e nelle simulazioni che richiedono milioni di scelte. Per uno strumento browser con un elenco ridotto, il campionamento cumulativo della trasformazione inversa è più semplice e perfettamente adeguato.

Errori comuni

I pesi sono facili da sbagliare. Fai attenzione a questi errori:

• Trattare un peso di 70 come 70% quando gli altri pesi non sono zero. È solo del 70% se la somma degli altri pesi è pari o inferiore a 30.
• Consentire pesi zero o negativi. Le opzioni a peso zero non potranno mai vincere. I pesi negativi rendono la distribuzione priva di significato.
• Utilizzo di Math.random() per un'estrazione che deve essere imprevedibile.
• Utilizzo di una mappatura distorta per trasformare valori casuali in segmenti.
• Giudicare l'equità da dieci o venti pareggi. Piccoli campioni possono apparire molto diversi dalla distribuzione prevista.

Un altro errore comune è confondere la ponderazione con il mescolamento. Se hai bisogno che ogni permutazione abbia la stessa probabilità, mescola l'elenco. Se hai bisogno di una prima scelta ponderata, usa un sorteggio ponderato.

Come verificare un pareggio ponderato

Confrontare le frequenze attese e osservate. Con i pesi 1, 2 e 7, le probabilità attese sono 10%, 20% e 70%. Nel corso di migliaia di estrazioni, le proporzioni osservate dovrebbero avvicinarsi a quei numeri.

Non sovrainterpretare un piccolo campione. Un pareggio equilibrato può produrre una serie di vittorie sorprendenti. Ciò che conta è se le frequenze osservate convergono man mano che il campione cresce e se l’implementazione è documentata.

Per un'estrazione ponderata pubblica, registra le opzioni, i pesi e il risultato. Ciò rende l'estrazione verificabile anche se non pubblichi mai il codice.

Come questo sito implementa la casualità ponderata

Il selettore ponderato su questo sito utilizza pesi cumulativi e un valore casuale crittograficamente sicuro. L'anteprima della probabilità mostra la distribuzione normalizzata prima del disegno. Le opzioni vengono selezionate con il campionamento della trasformazione inversa e le estrazioni senza sostituzione rimuovono l'opzione selezionata e rinormalizzano i pesi rimanenti.

Tutto viene eseguito localmente nel tuo browser. Le tue opzioni, pesi e risultati non vengono caricati.

Conclusione

La casualità ponderata modifica le probabilità, non la fonte della casualità. Normalizza i pesi, utilizza un valore casuale sicuro e seleziona il segmento cumulativo corrispondente. Ciò ti dà probabilità discrete e disuguali per tabelle di bottino, lotterie, test A/B e attività in classe.