Come generare un numero casuale dalla distribuzione discreta specificata?

Question

Diciamo che abbiamo una distribuzione discreta con un numero finito di risultati possibili, è possibile generare un numero casuale da questa distribuzione più veloce rispetto a O (logn), dove n è il numero di risultati possibili?

Come rendere in O (log n):
- Fare un array con probabilità cumulativa (Array [i] = Probabilità che di numeri casuali sarà minore o uguale a i)
- Genera numeri casuali da distribuzione uniforme (diciamolo con k)
- Trova il più piccolo i tale che k < Array [i]. Può essere fatto usando la ricerca binaria.
- i è il nostro numero casuale.

Answer 1

Il metodo alias di Walker può disegnare un campione nel tempo di caso peggiore costante, utilizzando alcuni array ausiliari di dimensione n che devono essere precalcolati. Questo metodo è descritto nel Capitolo 3 di Devroye's book on sampling ed è implementato nella funzione R sample(). È possibile ottenere il codice dal codice sorgente di R o this thread. A 1991 paper by Vose afferma di ridurre il costo di inizializzazione.

Si noti che la domanda non è ben definita a meno che non si specifichi la forma esatta dell'input e quanti numeri casuali si desidera disegnare. Ad esempio, se l'input è una matrice che fornisce la probabilità di ciascun risultato, allora l'algoritmo non è O (log n) poiché richiede innanzitutto il calcolo delle probabilità cumulative che impiegano il tempo O (n) dall'array di input.

Se si intende disegnare molti campioni, il costo di generazione di un singolo campione non è così importante. Invece ciò che conta è il costo totale per generare m risultati e il picco di memoria richiesto. A questo proposito, il metodo alias è molto buono. Se si desidera generare tutti i campioni contemporaneamente, utilizzare l'algoritmo O (n + m) inviato here e quindi mescolare i risultati.