小寒 | 提取随机：从算法基础到理论前沿

1951年，冯诺依曼在一篇论文^[1]中提到了这样一个小问题：给你一枚不均匀的硬币，允许你抛足够多次。你能否通过这些结果，来模拟出一枚均匀硬币？

这个问题有一个简单巧妙的解决方法：抛两次硬币，如果结果相同则抛弃，不同则取第一次的结果。由于“01”与“10”的概率相等，所以这个方法投掷出“0”和“1”的概率都是  。

尽管这个例子并不复杂，但它却打开了一个全新的领域：提取随机。简单来说，就是构造一个确定性算法。当我们输入任何一个满足某些条件的概率分布时，它的输出总是等于或接近于均匀分布。

这种算法有什么用？高质量的真随机数是密码学、模拟算法等领域的基础，而随机性的提取对于生成真随机数而言至关重要。我们知道，现有的计算机不能凭空生成出真正的随机数。而真随机性的来源——物理世界中发生的随机事件——又常常遵循各种不同的分布，与算法中所需要的独立、均匀的随机数大相径庭。将这些千奇百怪的分布中蕴含的随机性提取出来，使之转化为均匀分布，才能满足一般算法的需求。

然而，一般场景下的随机分布往往比一枚不均匀的硬币要复杂的多，拥有各式各样的奇特性质。在这当中，什么样的性质能表明一族分布“足够好”，从而可以为之构造算法，提取随机性？直到1990年代初，班尼·霍尔，奧德·戈德里克和大卫·祖克曼才为学界找到一个简练又好用的标准：最小熵，并在前人基础上建立起了对应的随机性提取器的理论框架^[2]。

简单介绍一下最小熵。假设一个离散概率分布用  表示，那么它的最小熵就定义为  。这个定义的直观意义是：  中的最大概率事件蕴含的信息量，也就是任一事件蕴含的信息量的最小值。它与经典的香农熵都是 Rényi 熵的特例：香农熵刻画平均情况下的信息量，而最小熵则刻画了最坏情况下的信息量。

我们想要找的随机性提取器（Randomness Extractor）就是这样一种函数  ，它能够利用任意一个最小熵足够高的分布  ，在不知道  具体分布的情况下，输出一个接近均匀分布的随机比特串。形式化地说，任意给它一个定义在  的比特上的概率分布  , 且假设  的最小熵  。再给它一个与  独立，极短的均匀分布随机种子  。那么  一定接近于一个均匀分布的随机比特串。

在这个定义下，后续的一系列研究构造了各种各样参数优秀的随机性提取器。除此之外，还有一些随机数提取器专门为某些较为特殊的分布设计。例如，有些通过电路生成的概率分布，其分布的方式往往满足某种特殊的性质，从而不用种子就能直接提取出均匀分布^[3]。感兴趣的读者可以自行查阅相关文献。

综上所言，假设采集的随机事件有足够高的最小熵。那么，不管它是大气噪声、辐射衰变还是你的鼠标移动，不管它有着怎样的独特性质，计算机都可以通过随机性提取器，将它转变为独立、均匀的随机比特串，来为密钥生成、模拟算法以及抽卡游戏提供可靠的随机性。这下，你可以放心地让计算机抛硬币了。

而随着研究的不断深入，随机数提取器的各种用途不断展露，其与理论计算机中的其他问题的关系也逐渐显现。在这里，我想简单介绍两个与随机数提取器相关的著名研究：一是将随机性提取器用于生成伪随机数。二是通过伪随机数生成器的构造，生成更好的随机性提取器。

假设有一台  个状态的有限状态自动机  ，每次转移会读取一个新的随机比特，且经过至多  步随机转移后必然停机。那么，有没有一种办法，能够不遍历求和  种可能的随机比特串，而是只遍历其中很小的一个部分，就能估计出这台机器的接受概率呢？

答案是肯定的：取一个  比特的均匀分布，记为  , 再取  个独立均匀的短种子  。利用一个输出长度是  的随机性提取器  ，构造如下分布： 

那么，上述的自动机  在  上的接受概率十分接近于在均匀分布上的接受概率。

这成立的关键就在于，  在任何一个时刻只能记忆住  比特的信息，而  含有  的信息，多于  。这样，即使我们固定了某一时刻  的状态  ，条件分布  中仍然有足够高的最小熵。  提取了这些随机性，生成了长度为  的随机比特串，使得从  出发的  根本无法分辨  和均匀分布。于是，两者对应的状态转移矩阵也几乎一样。通过对  归纳，就能说明  在  上的接受概率与在均匀分布上的接受概率相差无几了。

这一做法由诺姆·尼散和大卫·祖克曼在90年代末提出^[4]，其构造的伪随机数生成器时至今日仍在去随机化领域中被广泛应用。这里还有一个问题留给读者思考：上述的伪随机数生成器的种子长度大约是  乘以一个小量。如果我们要继续减小种子长度，又该如何改进这个做法？这个问题也可以在他们的论文原文中找到答案。

回顾小满 | 与不可区分的随机共舞，随机性，不可区分性，难函数之间往往有着密切的联系。通过一些构造^[5]，一个足够难的函数  可以被转化为一个伪随机数生成器  。具体来说，对于任何一个检验  ，如果  能够很好地区分  生成的伪随机数与均匀分布的随机数，那么我们就可以用  和一个很小的电路来计算  。反而言之，只要  不能通过小电路简单计算，那么检验  就无法区分  生成的伪随机数与均匀分布。

如果要使用  的好性质，我们首先需要一个难函数，而构造一个能难倒所有检验  的难函数却非常困难。不过，当我们把视角转向随机化算法时，只要随机抽一个函数  和一个检验  ，就会惊讶地发现  几乎总是对  而言足够难的。原因很简单：对  而言简单的函数总可以通过一个小电路计算，而这样的函数占所有函数的比例实在太小。

基于这一发现，卢卡·特雷维桑构造了一种新型的随机数提取器  ^[6]。其中，  （相当于前文中的难函数  ）代表以  为真值表的函数。由上一段所言，任意取一个检验  ，对于绝大部分的真值表  ，  都无法区分  生成的伪随机数与均匀分布。对  在  上取平均，我们发现  也无法区分  （这里  是均匀随机种子）和均匀分布。由于任意一个检验  都无法区分  和均匀分布，那么，  就是（几乎）均匀的随机比特串。在这里，我们又用到了不可区分性的哲学：均匀分布等价于任意检验无法区分的分布。

[1] John von Neumann. Various techniques used in connection with random digits. Applied Math Series, 12:36–38, 1951.

[2] Zuckerman, D. 1990. General weak random sources. In Proceedings of the 31st IEEESymposium on Foundations of Computer Science (1990), pp. 534–543.

[3] Emanuele Viola. 2011. Extractors for Circuit Sources. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS '11). IEEE Computer Society, USA, 220–229.

[4] Noam Nisan and David Zuckerman. 1996. Randomness is Linear in Space. J. Comput. Syst. Sci. 52, 1 (Feb. 1996), 43–52.

[5] Noam Nisan and Avi Wigderson. 1994. Hardness vs randomness. J. Comput. Syst. Sci. 49, 2 (Oct. 1994), 149–167.

[6] 2001. Extractors and pseudorandom generators. J. ACM 48, 4 (July 2001), 860–879.

文 | 吴睿洋