假设你有一枚不均匀的硬币。它以某个你不知道的概率 $p$ 正面朝上，也许是 $0.7$，也许是 $0.55$。能用它来做一次完全公平、各占一半的抽签吗？

在谈到制造随机数的人的“罪孽状态”的那篇 1951 年的论文里，冯·诺依曼给出了一个简短而出人意料的回答。

窍门

把硬币抛两次：

  • 如果是正、反，就算“正面”；
  • 如果是反、正，就算“反面”；
  • 如果是正、正或反、反，就作废，再抛两次。

为什么是公平的？两次抛掷相互独立，所以

$$P(\text{正、反}) = p\,(1-p), \qquad P(\text{反、正}) = (1-p)\,p.$$

无论 $p$ 是多少，它们都是同一个数。相同的结果被丢掉了，在剩下的结果中，正面和反面的机会完全相等。不需要知道硬币偏得多厉害，只需要各次抛掷互不影响。

代价

代价是要丢掉一些对。一对可用的概率是 $2p(1-p)$。对于公平的硬币 $p = \frac12$，一对可用的概率是 $\frac12$：平均每个结果需要 $2$ 对，也就是 $4$ 次抛掷。对于偏得很厉害的硬币，代价急剧上升：如果 $p = 0.9$，一对可用的概率只有 $2 \times 0.9 \times 0.1 = 0.18$，平均每个结果需要大约 $11$ 次抛掷。

冯·诺依曼的方法是随机性提取器的鼻祖。随机性提取器把不完美的随机来源，比如电路的电噪声或鼠标的移动，变成密码学所要求的均匀比特。

练习：70% 的硬币

取 $p = 0.7$，计算每种对出现的概率，以及每个结果平均需要的抛掷次数。

$P(\text{正、正}) = 0.49$，$P(\text{反、反}) = 0.09$，$P(\text{正、反}) = P(\text{反、正}) = 0.21$。一对可用的概率是 $0.42$。到第一个可用的对为止所需对数的平均值是 $\frac{1}{0.42} \approx 2.4$，即每个结果大约 $4.8$ 次抛掷。

练习：为什么不能只抛一次？

有人提议：“抛一次；如果是正面，就再抛一次，用第二次的结果。”这公平吗？

不公平。第二次抛掷仍然有偏差：无论第一次是什么，它都以概率 $p$ 出现正面。任何一次只看一次抛掷的规则，在不知道 $p$ 的情况下都无法纠正偏差。冯·诺依曼的窍门之所以有效，是因为它比较两次抛掷，并利用了“正、反”和“反、正”这两种顺序之间的对称性。

来源： John von Neumann, “Various techniques used in connection with random digits”, National Bureau of Standards Applied Mathematics Series 12（1951）· Persi Diaconis、Susan Holmes 与 Richard Montgomery, “Dynamical bias in the coin toss”, SIAM Review（2007）。

约翰·冯·诺依曼的全部主题 · ← 蒙特卡洛方法：掷骰子来计算 · 自我复制的自动机 →

图片来源.