题目重点：Von Neumann 将固定独立偏置源转成公平 bit，再用三位拒绝采样得到均匀 0–6，并计算期望调用次数。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练代码提供公平 bit→0–6 子程序，也提供未知固定偏置 bit→Von Neumann 去偏→0–6 的完整组合；题目未明确偏置概率与独立性。
- 若 bit 独立同分布且 P(1)=p∈(0,1) 未知，先成对采样：01→0、10→1、00/11 丢弃（Von Neumann）；若 bit 相关或 p 随时间漂移，不能保证公平。
解题路线
- 先澄清‘不平衡’是固定偏置还是相关。固定独立偏置时成对采样，01 与 10 的概率同为 p(1-p)，条件接受后各占 1/2。
- 把三个无偏 bit 按二进制组成 v∈[0,7]，v=7 时整组三位拒绝重抽，其余 v 直接返回。被接受的七个值原本各有概率 1/8，因此条件概率各为 1/7。
- 三位尝试成功率 7/8，平均尝试 8/7 次，平均用公平 bit 24/7≈3.43 次。偏置源的 Von Neumann 单个公平 bit 平均需 1/[p(1-p)] 个原始 bit，所以完整方案原始调用期望为 24/[7p(1-p)]。
- 训练代码把去偏生成器封装在三位拒绝采样外层；使用前仍要核对原题的偏置是否独立稳定。
手动走一遍
原始源 P(1)=0.8 时，01 和 10 都以 0.16 出现，分别映成公平 0/1。三个公平 bit 得 111=7 时丢弃，010=2 时返回 2。不能直接用原始偏置 bit 组成三位数，否则 0–6 不均匀。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def uniform_zero_to_six(randbit):
"""randbit() must return independent unbiased 0/1 samples."""
while True:
value = (randbit() << 2) | (randbit() << 1) | randbit()
if value < 7:
return value
def unbiased_bit_from_biased(randbit):
"""Von Neumann extractor: requires independent bits with a fixed bias."""
while True:
first, second = randbit(), randbit()
if first != second:
return first # 01 -> 0, 10 -> 1
def uniform_zero_to_six_from_biased(randbit):
return uniform_zero_to_six(lambda: unbiased_bit_from_biased(randbit))
复杂度
公平 bit 子程序期望 O(1) 时间/空间，平均调用 24/7；完整偏置源去偏期望调用量随 p→0 或 1 发散，为 24/[7p(1-p)]。随机测试对七种首轮结果与拒绝分支穷举，并对公平源/0.8 偏置源各作 70,000 次抽样频率检验；频率检验只作辅助。
易错点与追问
容易失分的边界
- 忽略题目‘不平衡’而直接三位 bit 取模 7。
- 用 v%7 让 0 的概率是 2/8。
- Von Neumann 在 bit 相关时仍宣称无偏。
- 没有拒绝 111。
- 只用统计频率代替概率证明。
继续深挖
- 未知 p 且接近 0 时效率如何？
- 偏置随时间变化但每对 bit 独立同分布吗？
- 能否回收被拒绝的随机信息提高效率？
- 如何测试随机源独立性？
