ランダムソースを均一に分散させます

Question

$ prob（0）= prob（1）= 0.5 $でビット0と1を出力するランダムソースを構築するにはどうすればよいですか。独立した確率$ prob（a）$ $ and = 1 -1 -prob（a）$を独立した確率で出力する別のランダムソース$ s $にアクセスできます。

ジョブを実行し、予想される$の数（prob（a） cdot prob（b））^{-1} $ 2つの出力ビットと2つの出力ビットの間の$ s $のシンボルを超えないアルゴリズムをどのように述べることができますかその正しさを証明しますか？

Answer 1

これを考慮してください。2つの要素を入手してください$ x_0 $と$ x_1 $ $ s $から$ x_1 $を取得します。 $ x_0x_1 $が$ aa $または$ bb $の場合、それらを破棄して繰り返します。それ以外の場合は、同じ確率$ p_ap_b $で発生するイベント、$ ab $の$ 0 $と$ 1 $ $ 1 $を返します。

これにより、$ s $、$ n $からの$ 2n $要素が実行されます。各ステップで停止する確率は、$ p = 1-2p_ap_b $です。したがって、$ 2n $の期待値は$$ 2p sum_ {n = 1}^∞{n（1-p）^{n-1}} = frac {2p} {（1-（1-p）です。 ）^2} = frac {1} {p_ap_b} enspace。$$