1951年，冯诺依曼在一篇论文
[1]
中提到了这样一个小问题：给你一枚不均匀的硬币，允许你抛足够多次。你能否通过这些结果，来模拟出一枚均匀硬币？
这个问题有一个简单巧妙的解决方法：抛两次硬币，如果结果相同则抛弃，不同则取第一次的结果。由于“01”与“10”的概率相等，所以这个方法投掷出“0”和“1”的概率都是
。
尽管这个例子并不复杂，但它却打开了一个全新的领域：
提取随机
。简单来说，就是构造一个确定性算法。当我们输入任何一个满足某些条件的概率分布时，它的输出总是等于或接近于均匀分布。
这种算法有什么用？高质量的真随机数是密码学、模拟算法等领域的基础，而随机性的提取对于生成真随机数而言至关重要。我们知道，现有的计算机不能凭空生成出真正的随机数。而真随机性的来源——物理世界中发生的随机事件——又常常遵循各种不同的分布，与算法中所需要的独立、均匀的随机数大相径庭。将这些千奇百怪的分布中蕴含的随机性提取出来，使之转化为均匀分布，才能满足一般算法的需求。
然而，一般场景下的随机分布往往比一枚不均匀的硬币要复杂的多，拥有各式各样的奇特性质。在这当中，什么样的性质能表明一族分布“足够好”，从而可以为之构造算法，提取随机性？直到1990年代初，班尼·霍尔，奧德·戈德里克和大卫·祖克曼才为学界找到一个简练又好用的标准：最小熵，并在前人基础上建立起了对应的随机性提取器的理论框架
[2]
。
简单介绍一下最小熵。假设一个离散概率分布用
表示，那么它的最小熵就定义为
。这个定义的直观意义是：
中的最大概率事件蕴含的信息量，也就是任一事件蕴含的信息量的最小值。它与经典的香农熵都是 Rényi 熵的特例：香农熵刻画平均情况下的信息量，而最小熵则刻画了最坏情况下的信息量。
我们想要找的随机性提取器
（Randomness Extractor）
就是这样一种函数
，它能够利用任意一个最小熵足够高的分布
，在不知道
具体分布的情况下，输出一个接近均匀分布的随机比特串。形式化地说，任意给它一个定义在
的比特上的概率分布
, 且假设
的最小熵
。再给它一个与
独立，极短的均匀分布随机种子
。那么
一定接近于一个均匀分布的随机比特串。
在这个定义下，后续的一系列研究构造了各种各样参数优秀的随机性提取器。除此之外，还有一些随机数提取器专门为某些较为特殊的分布设计。例如，有些通过电路生成的概率分布，其分布的方式往往满足某种特殊的性质，从而不用种子就能直接提取出均匀分布
[3]
。感兴趣的读者可以自行查阅相关文献。
综上所言，假设采集的随机事件有足够高的最小熵。那么，不管它是大气噪声、辐射衰变还是你的鼠标移动，不管它有着怎样的独特性质，计算机都可以通过随机性提取器，将它转变为独立、均匀的随机比特串，来为密钥生成、模拟算法以及抽卡游戏提供可靠的随机性。这下，你可以放心地让计算机抛硬币了。
而随着研究的不断深入，随机数提取器的各种用途不断展露，其与理论计算机中的其他问题的关系也逐渐显现。在这里，我想简单介绍两个与随机数提取器相关的著名研究：一是
将随机性提取器用于生成伪随机数
。二是
通过伪随机数生成器的构造，生成更好的随机性提取器
。
假设有一台
个状态的有限状态自动机
，每次转移会读取一个新的随机比特，且经过至多
步随机转移后必然停机。那么，有没有一种办法，能够不遍历求和
种可能的随机比特串，而是只遍历其中很小的一个部分，就能估计出这台机器的接受概率呢？
答案是肯定的：取一个
比特的均匀分布，记为
, 再取
个独立均匀的短种子
。利用一个输出长度是
的随机性提取器
，构造如下分布：
那么，上述的自动机
在
上的接受概率十分接近于在均匀分布上的接受概率。
这成立的关键就在于，
在任何一个时刻只能记忆住
比特的信息，而
含有
的信息，多于
。这样，即使我们固定了某一时刻
的状态
，条件分布
中仍然有足够高的最小熵。
提取了这些随机性，生成了长度为
的随机比特串，使得从
出发的
根本无法分辨
和均匀分布。于是，两者对应的状态转移矩阵也几乎一样。通过对
归纳，就能说明
在
上的接受概率与在均匀分布上的接受概率相差无几了。
这一做法由诺姆·尼散和大卫·祖克曼在90年代末提出
[4]
，其构造的伪随机数生成器时至今日仍在去随机化领域中被广泛应用。这里还有一个问题留给读者思考：上述的伪随机数生成器的种子长度大约是
乘以一个小量。如果我们要继续减小种子长度，又该如何改进这个做法？这个问题也可以在他们的论文原文中找到答案。
