Faire des sources aléatoires réparties uniformément

Question

Comment puis-je construire une source aléatoire qui délivre les bits 0 et 1 $ prob (0) = prob (1) = 0,5 $. Nous avons accès à un autre $ source aléatoire S $ que les sorties $ a $ ou $ b $ avec des probabilités indépendantes $ prob (a) $ et $ prob (b) = 1 -. Prob (a) $ qui nous sont inconnus

Comment puis-je affirmer un algorithme qui fait le travail et qui ne consomme pas plus qu'un nombre prévu de $ (Prob (a) \ cdot prob (b)) ^ {- 1} $ de symboles $ S $ entre deux bits de sortie et prouver son correcteness

Answer 1

Considérez ceci: obtenir deux éléments x_0 $ $ $ $ et x 1 $ de S $. Si x_0x_1 $ est $ aa $ ou $ bb $, alors jetez-les et répétez. retour Sinon $ 0 $ pour $ ab $ et 1 $ pour $ $ ba, les événements qui se produisent avec la même probabilité $ p_ap_b $.

utilisera 2n $ éléments de $ de $ S $, $ n $ le nombre d'étapes effectuées. La probabilité d'arrêt à chaque étape est $ p = 1-2p_ap_b $. La valeur attendue de $ 2n $ est donc $$ 2p \ sum_ {n = 1} ^ 8 {n ??(1-p) ^ {n-1}} = \ frac {} {2p (1- (1-p) ) ^ 2} = \ frac {1} {p_ap_b} \ enspace. $$