使随机来源均匀分布

Question

如何构建一个随机源，该源以$ prob（0）= prob（1）= 0.5 $输出位0和1。我们可以访问另一个随机源$ s $，该$ s $输出$ a $ a $ a $ a $ b $具有独立概率$ prob（a）$（a）$（b）= 1 -prob（a）$，我们未知。

我如何陈述一种完成该作业的算法，并且不超过预期数量的$（prob（a） cdot prob（b））^{ - 1} $符号在两个输出位和两个输出位之间的$ s $证明其正确性？

Answer 1

考虑一下：从$ s $中获取两个元素$ x_0 $和$ x_1 $。如果$ x_0x_1 $是$ aa $或$ bb $，则丢弃它们并重复。否则，$ ab $的返回$ 0 $和$ ba $的$ 1 $，同一概率$ p_ap_b $发生的事件。

这将使用$ s $，$ n $执行步骤的$ 2N $元素。在每个步骤中停止的概率是$ p = 1-2p_ap_b $。 $ 2n $的预期值为$$ 2p sum_ {n = 1}^∞{n（1-p）^{n-1}} = frac {2p} {（1-（1-（1-P）） ）^2} = frac {1} {p_ap_b} enspace。$$