假设你有一枚不均匀的硬币。它以某个你不知道的概率 $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$ 次抛掷。 冯·诺依曼的方法是随机性提取器的鼻祖。随机性提取器把不完美的随机来源，比如电路的电噪声或鼠标的移动，变成密码学所要求的均匀比特。 硬币从来都不完全公平 2007 年，数学家佩尔西·戴康尼斯、苏珊·霍姆斯和理查德·蒙哥马利证明，用拇指以通常方式抛出的硬币，落地时与起始时同一面朝上的概率略高于一半，约为 51%。2023 年，一项超过 35 万次抛掷的实验证实了这一效应。只要每一对中的两次抛掷相互独立，冯·诺依曼的窍门就能消除这种偏差。 练习：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$ 次抛掷。