Fare fonti casuali uniformemente distribuito

Question

Come faccio a costruire una fonte casuale che emette i bit 0 e 1 con $ prob (0) = prob (1) = 0,5 $. Abbiamo accesso a un'altra fonte casuale $ s $ che le uscite $ a oppure $ b $ con probabilità indipendenti $ prob $ (a) $ e $ prob (b) = 1 -. Prob (a) $ che sono a noi sconosciute

Come faccio Premetto un algoritmo che fa il lavoro e che non consuma più di un numero previsto di $ (Prob (a) \ cdot prob (b)) ^? {- 1} $ simboli di $ S $ tra due bit di uscita e di dimostrare la sua correcteness

Answer 1

Considerate questo: ottenere due elementi $ x_0 $ e $ x_1 $ da $ S $. Se $ x_0x_1 $ è $ aa $ o $ bb $ poi li scarta e ripetere. In caso contrario, tornare $ 0 $ a $ AB $ e $ 1 $ per $ ba $, gli eventi che si verificano con la stessa probabilità $ p_ap_b $.

Questa userà $ 2n $ elementi da $ S $, $ n $ il numero di passi effettuati. La probabilità di fermarsi ad ogni passo è di $ p = 1-2p_ap_b $. Il valore atteso di $ 2n $ è quindi $$ 2p \ sum_ {n = 1} ^ 8 {n ??(1-p) ^ {n-1}} = \ frac {} {2p (1- (1-p) ) ^ 2} = \ frac {1} {p_ap_b} \ enspace. $$