Zufällige Quellen gleichmäßig verteilt machen

Question

Wie erstelle ich eine zufällige Quelle, die die Bits 0 und 1 mit $ prob (0) = prob (1) = 0,5 $ ausgibt. Wir haben Zugriff auf eine andere zufällige Quelle $ s $, die $ $ $ oder $ b $ mit unabhängigen Wahrscheinlichkeiten $ prob (a) $ und $ prob (b) = 1 - prob (a) $, die uns unbekannt sind, ausgibt.

Wie state ich einen Algorithmus, der den Job erledigt und der nicht mehr als eine erwartete Anzahl von $ (prob (a) cdot prob (b))^{-1} $ Symbole von $ s $ zwischen zwei Ausgangsbits und konsumiert seine Korrektheit beweisen?

Answer 1

Beachten Sie Folgendes: Holen Sie sich zwei Elemente $ x_0 $ und $ x_1 $ von $ s $. Wenn $ x_0x_1 $ $ aa $ oder $ bb $ ist, löschen Sie sie und wiederholen Sie. Ansonsten return $ 0 $ für $ AB $ und $ 1 $ $ für $ ba $, Ereignisse, die mit der gleichen Wahrscheinlichkeit $ p_ap_b $ auftreten.

Dies wird $ 2N $ Elements von $ s $, $ n $ verwendet, die Anzahl der durchgeführten Schritte. Die Wahrscheinlichkeit, bei jedem Schritt anzuhalten, beträgt $ p = 1-2p_ap_b $. Der erwartete Wert von $ 2n $ beträgt daher $$ 2p sum_ {n = 1}^∞ {n (1-p)^{n-1}} = frac {2p} {(1- (1-p)) )^2} = frac {1} {p_AP_B} Enspace. $$