È il rifiuto di campionamento l'unico modo per ottenere una distribuzione veramente uniforme dei numeri casuali?

Question

Supponiamo di avere un generatore casuale che uscite numeri nell'intervallo $ [0..R-1] $ con distribuzione uniforme e noi necessità di generare numeri casuali nella gamma $ [0..n-1] $ con distribuzione uniforme.

Supponiamo che $ N distribuzione veramente uniforme si può utilizzare il rifiuto di campionamento metodo :

• se $ k $ è il più grande intero tale che $ k N
• scegliere un numero casuale $ r $ a $ [0..R-1] $
• Se $ r

È il rifiuto di campionamento l'unico modo per ottenere una distribuzione discreta veramente uniforme?

Se la risposta è sì, perché?

Nota: se $ N> R $ l'idea è la stessa: generare un numero casuale $ r '$ a $ [0..R ^ m-1], R ^ m> = N $, ad esempio $ r '= R (... R (R R_1 + R_2) ...) + r_m $ dove $ $ r_i è un numero casuale nel range $ [0..R-1] $

Answer 1

Sì e no, a seconda di cosa si intende per “l'unico modo”. Sì, nel senso che non esiste un metodo che è garantito per terminare, il meglio che si può fare (per i valori generici di $ N $ e $ R $) è un algoritmo che termina con probabilità 1. No, nel senso che si può fare la “ sprecare”piccolo come ti piace.

Perché terminazione garantito è impossibile in generale

Si supponga di avere un motore di calcolo deterministico (una macchina di Turing o qualunque sia la tua barca galleggia), oltre a un oracolo che genera elementi casuali del $ R $ -element set $ [0..R-1] $. Il vostro obiettivo è quello di generare un elemento di $ N $ -element set $ [0, N-1] $. L'uscita del motore dipende solo dalla sequenza di valori restituiti dalla oracolo; si tratta di una funzione $ f $ di quella potenzialmente infinita sequenza di $ (r_0, R_1, R_2, \ ldots) $.

Supponiamo che il vostro motore chiama l'oracolo di maggior $ m $ volte. Ci potrebbero essere le tracce per le quali l'oracolo è chiamato meno di $ m $ volte; in caso affermativo, chiamando i tempi supplementari Oracle in modo che sia sempre chiamato esattamente $ m $ volte non cambia l'uscita. Quindi, senza perdita di generalità, si assume che l'oracolo si chiama esattamente $ m $ volte. Quindi la probabilità che il risultato $ x $ è il numero di sequenze $ (r_0, \ ldots, r_ {m-1}) $ tale che $ f (r_0, \ ldots, r_ {m-1}) = x $. Poiché l'oracolo è un generatore casuale uniforme, ciascuna sequenza è equiprobabili ed ha la probabilità $ 1 / R ^ m $. Quindi la probabilità di ogni risultato è nella forma $ A / R ^ m $ dove $ A $ è un numero intero compreso tra $ 0 $ e $ R ^ m $.

Se $ N $ divide $ R ^ m $ per un po '$ m $, quindi è possibile generare una distribuzione uniforme su $ N $ elementi chiamando generatore casuale $ m $ volte (questo è lasciato come esercizio per il lettore ). In caso contrario, questo è impossibile: non esiste un modo per ottenere un risultato con probabilità $ 1 / N $. Si noti che la condizione equivale a dire che tutti i fattori primi $ N $ s 'sono anche fattori di $ R $ (questo è più permissiva di quello che hai scritto nella tua domanda, ad esempio si può scegliere un elemento casuale tra 4 con un fiera dado a 6 facce, anche se 4 non divide 6).

Ridurre i rifiuti

Nella vostra strategia, quando $ r \ ge k \, N $, non c'è bisogno di ri-disegnare immediatamente. Intuitivamente, c'è un po 'di entropia sinistra in $ [K \, N .. R-1] $ che si può tenere nel mix.

Si supponga per un momento che si continui in realtà la generazione di numeri casuali di sotto di $ N $ per sempre, e si genera $ u $ di loro alla volta, facendo $ d $ disegna. Se fate un rifiuto diretto di campionamento su questa generazione raggruppati, i rifiuti di oltre $ d $ trae è di $ \ dfrac {R ^ d - k \, N ^ u} {d} $, vale a dire la parte restante $ R ^ d \ mathbin { \ mathrm {mod}} N ^ U $ diviso per il numero di estrazioni. Questo può essere un minimo di $ \ MCD (R, N) $. Quando $ R $ e $ N $ sono primi tra loro, è possibile rendere i rifiuti arbitrariamente piccola con la scelta sufficientemente grandi valori di $ d $. Per i valori generali di $ R $ e $ N $, il calcolo è più complicato perché è necessario prendere in considerazione la generazione di $ \ MCD (R, N) $ e $ N / \ MCD (R, N) $ a parte, ma ancora una volta si può fare i rifiuti arbitrariamente piccola con grandi gruppi a sufficienza.

In pratica, anche con numeri casuali relativamente inefficienti (ad esempio nella crittografia), è raramente la pena di fare tutt'altro che semplice campionamento rifiuto, a meno che $ N $ è piccolo. Ad esempio, nella crittografia, dove R $ $ è tipicamente una potenza di 2 e $ N $ è tipicamente centinaia o migliaia di bit, uniforme generazione di numeri casuali procede generalmente per campionamento rifiuto dritto nell'intervallo desiderato.

Answer 2

fonte di Shannon codifica teorema mostra che, in un certo senso esatto, avete bisogno di $ \ log N / \ log R $ campioni (in media) del tipo $ [0, \ ldots, R-1] $ per generare un caso numero del tipo $ [0, \ ldots, N-1] $. Più precisamente, Shannon dà una (inefficiente) algoritmo che dato $ m $ campioni del primo tipo, uscite $ m (\ log N / \ log R - \ epsilon) $ campioni del secondo tipo, con alta probabilità. Ha anche spettacoli che l'output $ m (\ log N / \ log R + \ epsilon) $ campioni con alta probabilità è impossibile.

Il teorema di Shannon funziona anche nel caso più generale di una distribuzione asimmetrica di ingresso (e probabilmente anche la distribuzione di uscita asimmetrica). In tal caso, è necessario sostituire il logaritmo con l'entropia. Mentre l'algoritmo proposta dal teorema è definita in modo casuale, in alcuni casi è possibile derandomize esso (a costo della prestazione po 'peggio).

Answer 3

In realtà, no, il campionamento rifiuto è ben lungi dall'essere l'unico modo di procedere. Purtroppo, se si considera che i computer memorizzano tutte le informazioni come bit, e quindi possono manipolare solo bit casuali di informazione, qualsiasi algoritmo per disegnare una variabile aleatoria uniforme gamma $ N $ sarà infinita, se lo sviluppo di base binaria di $ N $ è infinito.

Questo teorema è un risultato classico da Knuth e Yao (1976), che ha sviluppato il quadro di DDG-alberi (alberi discreta distribuzione di generazione).

I metodi esposti da Gilles sono il genere tipico di cosa che è stato fatto per mitigare i rifiuti sostenute dal rifiuto, ma ovviamente se uno in grado di generare a seguito Knuth e gli alberi di Yao è molto, molto più efficiente - in media il 96% di bit casuali vengono salvate.

I hanno dato ulteriori informazioni su questo nel seguente CStheory posta .