Generatore di numeri casuali senza pregiudizi con uno polarizzato

Question

Si dispone di un generatore di numeri casuali distorti che produce un 1 con probabilità p e 0 con una probabilità (1-p). Non conosci il valore di p. Usando questo crea un generatore di numeri casuali imparziale che produce 1 con una probabilità 0.5 e 0 con una probabilità 0.5.

Nota: questo problema è un problema di esercizio da Introduzione agli algoritmi di Cormen, Leiserson, Rivest, Stein (CLR)

Answer 1

Gli eventi (p) (1-p) e (1-p). (p) sono equiprobabili. Prendendo come 0 e 1 rispettivamente e scartando le altre due coppie di risultati si ottiene un generatore casuale imparziale.

In codice di questo è fatto il più semplice:

int UnbiasedRandom() 
{ 
    int x, y; 

    do 
    { 
     x = BiasedRandom(); 
     y = BiasedRandom(); 
    } while (x == y); 

    return x; 
} 

Answer 2

è necessario disegnare coppie di valori da RNG fino ad ottenere una sequenza di valori diversi, vale a dire zero seguito da una o uno seguito da zero. Quindi prendi il primo valore (o l'ultimo, non importa) di quella sequenza. (Cioè Ripetere finché la coppia disegnata è o due zeri o due più)

La matematica dietro questo è semplice: una sequenza di 0 allora 1 ha la stessa probabilità come sequenza 1 di zero. Prendendo sempre il primo (o l'ultimo) elemento di questa sequenza come output del tuo nuovo RNG, otteniamo una possibilità pari di ottenere uno zero o uno.

Answer 3

Ecco un modo, probabilmente non il più efficiente. Masticare un gruppo di numeri casuali fino a ottenere una sequenza del modulo [0 ..., 1, 0 ..., 1] (dove 0 ... è uno o più 0). Contare il numero di 0. Se la prima sequenza è più lunga, genera uno 0 (se sono uguali, prova di nuovo.)

Questo è come ciò che fa HotBits per generare numeri casuali da radioattivi decadimento delle particelle:

Poiché il tempo di un determinato decadimento è casuale, anche l'intervallo tra due decadimenti consecutivi è casuale. Quello che facciamo, quindi, è misurare una coppia di questi intervalli ed emettere uno zero o un bit in base alla lunghezza relativa dei due intervalli. Se si misura lo stesso intervallo per i due decadimenti, si scartano la misurazione e riprovare

HotBits: How It Works

Answer 4

Il trucco attribuita a von Neumann di ottenere due bit alla volta, con 01 conforme a 0 e 10 a 1, e ripetendo per 00 o 11 è già venuto fuori. Il valore atteso dei bit che devi estrarre per ottenere un singolo bit utilizzando questo metodo è 1/p(1-p), che può diventare piuttosto grande se p è particolarmente piccolo o grande, quindi vale la pena chiedersi se il metodo può essere migliorato, soprattutto dal momento che è evidente che getta via molte informazioni (tutti gli 00 e gli 11 casi).

Googling per "von neumann trick biased" prodotto this paper che sviluppa una soluzione migliore per il problema. L'idea è che tu prendi ancora due bit alla volta, ma se i primi due tentativi producono solo 00 e 11, tratti una coppia di 0 come un singolo 0 e una coppia di 1 come un singolo 1, e applica il trucco di von Neumann a queste coppie. E se anche questo non funziona, continua a combinare in modo simile a questo livello di coppie e così via.

Inoltre, la carta sviluppa questo in modo da generare più bit non distorti dalla sorgente polarizzata, essenzialmente utilizzando due diversi modi di generare bit dalle coppie di bit e dando uno schizzo che questo è ottimale nel senso che produce esattamente il numero di bit che la sequenza originale aveva entropia in esso.

Answer 5

La procedura a produce an unbiased coin from a biased one è stata attribuita per la prima volta a Von Neumann (un ragazzo che ha svolto un lavoro enorme in matematica e in molti campi correlati). La procedura è semplice super:

• lanciare la moneta due volte.
• Se i risultati corrispondono, ricomincia, dimenticando entrambi i risultati.
• Se i risultati sono diversi, utilizzare il primo risultato, dimenticando il secondo.

Il motivo per cui questo algoritmo funziona è perché la probabilità di ottenere HT è p(1-p), che è lo stesso di ottenere TH (1-p)p. Quindi due eventi sono ugualmente probabili.

Sto anche leggendo questo libro e si chiede il tempo di esecuzione previsto. La probabilità che due lanci non siano uguali è z = 2*p*(1-p), pertanto il tempo di esecuzione previsto è 1/z.

---

L'esempio precedente sembra incoraggiante (dopo tutto, se si dispone di una moneta sbilanciata con un bias di p=0.99, è necessario gettare la vostra moneta di circa 50 volte, che non è che molti). Quindi potresti pensare che questo sia un algoritmo ottimale. Purtroppo non lo è.

Ecco come si confronta con lo Shannon's theoretical bound (l'immagine è presa da questo answer). Mostra che l'algoritmo è buono, ma tutt'altro che ottimale.

Si può venire con un miglioramento se si considera che HHTT sarà scartato da questo algoritmo, ma in realtà ha la stessa probabilità di TTHH. Quindi puoi anche fermarti qui e restituire H. Lo stesso è con HHHTTTT e così via. L'utilizzo di questi casi migliora il tempo di esecuzione previsto, ma non lo rende teoricamente ottimale.

---

E alla fine - codice Python:

import random 

def biased(p): 
    # create a biased coin 
    return 1 if random.random() < p else 0 

def unbiased_from_biased(p): 
    n1, n2 = biased(p), biased(p) 
    while n1 == n2: 
     n1, n2 = biased(p), biased(p) 

    return n1 

p = random.random() 
print p 

tosses = [unbiased_from_biased(p) for i in xrange(1000)] 
n_1 = sum(tosses) 
n_2 = len(tosses) - n_1 
print n_1, n_2 

è abbastanza auto-esplicativo, e qui è un risultato ad esempio:

0.0973181652114 
505 495 

Come si vede, comunque abbiamo avuto una polarizzazione di 0.097, abbiamo ottenuto circa lo stesso numero di 1 e 0