数学家证明：这些看起来随机的数字并非随机

在现实世界中，概率很难被描述。如果我掷骰子，说它有六分之一的概率掷出 5 是什么意思？我们说结果是随机的，因为我们缺乏预测哪个面朝上的信息。但这并非真正随机。如果我们知道我如何移动我的手以及我抛掷骰子时作用在骰子上的所有力的细节，我们或许可以预测掷骰子的结果。然而，实际上，我们通常缺乏这种预测能力。数学家称这种情况为“伪随机”：虽然它看起来和感觉对我们来说是随机的，但我们知道，事实上，如果我们拥有我们想要的所有信息，掷骰子就不是随机的了。

同样，如果我向 Google 请求一个随机生成的数字，它需要一个过程来输出一个数字，但 Google 无法访问纯理论的随机数学模型。因此，它使用一个非随机的过程，产生一个对我们来说看起来是随机生成的数字，因为我们不知道该过程是什么——或者至少我们不知道一些输入是什么。Google 生成的数字也是伪随机的。

伪随机数字出现在各个领域：建模、赌场和彩票都需要伪随机数字作为输入。此外，银行和金融机构使用此类数字进行安全和欺诈检测。由于黑客对破解这些伪随机代码非常感兴趣，人们开发了复杂的生成这些数字的方法。例如，许多“随机”数生成器依赖于物理过程。例如，网络安全和互联网服务公司 Cloudflare 有一个名为 LavaRand 的系统，该系统使用熔岩灯来生成伪随机数字。

关于支持科学新闻

如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您将有助于确保未来能够看到关于当今塑造我们世界的发现和想法的具有影响力的故事。

现在假设我们有一组数字，或者更广义地说，是空间中的点。您如何判断这组点来自真正的随机过程，还是这组点是由确定性过程产生的？这个问题是许多数学领域的中心问题，数学家有各种检测随机性的方法。然而，我们想知道，“这些测试的效果到底有多好？是否存在并非随机生成的但可以满足测试的点集？” 如果是这样，我们称之为伪随机。伪随机特性和对其的搜索有各种各样的应用，从理解素数到一种叫做量子混沌的东西（我个人认为这是最适合乐队名称的数学物理学领域）。

在疫情期间，我开始研究一个与伪随机性相关的问题：在没有随机性的地方寻找随机行为。这项工作始于我发给当时在特拉维夫大学的研究员尼克拉斯·特克瑙 (Niclas Technau) 的一封电子邮件。到 2022 年年中，尽管从未面对面见过面，但我们两人已经共同撰写了三篇论文，并且找到了一些我们能够证明通过了极强伪随机测试的序列的唯一示例。

检测随机性

我们如何检测随机性？也许最粗略的方法是所谓的均匀分布。考虑两个盒子，里面有点，显然是散布在里面的——一个盒子里的点填满了整个正方形，另一个盒子里的点有一半是空的。

哪个盒子看起来更随机？希望您选择的是完全填满点的那个，因为随机过程不太可能导致一个盒子底部一半没有点。考虑均匀分布的一种方式是问，“如果我在这组点中取足够多的点，该组点所覆盖的区域的每个子区域是否会获得其公平的点数？” 如果是这样，则该组点是均匀分布的。我应该采样多少个点？理想情况下，答案是无穷多个。这样，如果这些点确实是随机生成的，那么出现奇怪行为（例如所有点都落在中线之上）的可能性就非常低——并且随着点数的增加，这种可能性会越来越接近于零。

让我们关注 0 到 1 之间的数字序列。均匀分布的随机序列是指点落在该区间任何位置的概率相等。取由方程 xn = {πn²} 创建的序列 0.142、0.566、0.274、0.265,...，其中花括号表示我们忽略该数字的整数部分。因此，第一个数字是 π x 1² = 3.141。当我们去掉 3 时，我们得到 0.141。第二个数字是 π x 2² = 12.566；去掉 12，就是 0.566。

要确定该序列是否均匀分布，我们可以问，“对于该序列中给定数量的点，有多少点填充 0 到 1 之间的任何特定子区域？” 落入子区域的公平点数是点数乘以该区域的面积，因为点落入该区域的概率等于该区域的面积。

当我们计算这个性质时，我们发现这个序列 x_n = {πn²} 是均匀分布的。但是，例如，序列 x_n = {³⁄₇n²} 不是均匀分布的，因为 0.05 和 0.1 之间的子区间是一个永远不会收到点的区域的示例。（这些结果可以追溯到 1916 年数学家赫尔曼·韦尔的开创性工作。）

其他测试

虽然均匀分布是一个有用的测试，但它衡量随机性的方法很粗略。要用另一种方法评估一组点的随机程度，请尝试在这里找出随机生成的图像

即使所有三个盒子中的点看起来都是均匀分布的，但它们看起来并不都是随机的。左边的盒子中的所有点之间的间隔非常规则，并且在中间的图像中，这些点似乎聚集在一起。只有右侧框中的点看起来是随机的。这种类型的例子促使数学家开发出更复杂的测试，称为间隙分布和配对相关性。前者测量点之间的间隙大小，后者测量点的聚类——它们聚集或分开的程度。在这些测试中，当我们考虑越来越多的点时，我们会分别计算点之间的间隙数量或彼此接近的配对数量。如果这些与我们从随机数据中期望的结果一致，我们就说间隙分布或配对相关性是“泊松式的”（以法国概率学家西蒙-德尼·泊松的名字命名）。

这些测试很有用，但要实际证明一个序列满足这些测试仍然很困难。本质上，证明一组点具有某种模式比证明它没有任何模式更容易。但作为数学家，我们想要一个逻辑证明，而不会仅仅满足于测试大量点。

一组示例

我上面使用的是一组流行的示例的一部分，它们都可以写成 x_n = {αn^θ}，其中 α 和 θ 各自代表一个数字（例如，α = π 和 θ = 2）。这些序列在历史上很有趣，因为它们是韦尔用来理解均匀分布的第一个例子之一。最近，由于它们与量子混沌相关的某些深刻思想的联系，它们再次流行起来。奇怪的是，我们知道几乎所有 α 和 θ 的选择都会给出一个具有泊松配对相关性的序列。然而，直到最近，我们还没有一个 α 和 θ 的确切选择能给出泊松配对相关性的例子。这是数学中一个常见的问题，我们可以证明大多数选择会导致特定结果，但却找不到一个具体的例子。（我们说这就像在干草堆里找干草。）在寻找间隙分布方面，我们真的束手无策。

这就是特克瑙和我决定解决的问题。在我们早期的在线讨论之后，我们首先研究 θ = 1/2，由于复杂的原因，这是一个重要的例子。我们试图绕过通常用于解决此问题的大量数学机制（主要是因为我不理解它），并回到韦尔用于均匀分布的 1916 年技术。问题的关键在于证明某个特定的总和很小。最初，我们可以证明该总和不是无限大，但我们无法充分限制它。

经过大量的挠头苦思，当我们意识到如果 θ 很小，这些技术会更好地工作时，突破就来了，因此我们改变了问题。与独立研究同一问题的数学家 Athanasios Sourmelidis 一起，我们能够证明，如果 θ 小于或等于 1/3，则该序列具有泊松配对相关性（对于任何 α）。这给了我们一个完整的序列族，我们可以证明它们具有泊松配对相关性。然后，特克瑙和我能够扩展这些技术，使指数更小，并表明所得序列满足一个更强的伪随机测试，称为三相关性。通过使 θ 越来越小，我们能够证明越来越强的伪随机特性。

这些技术之所以有效，是因为随着我们使指数变小，序列 n^θ 增长得越来越慢，这有助于限制所得的总和（我们在 θ = 1/2 的情况下找不到其上限）。有些序列的增长速度比 n^θ 慢，无论指数是多少，例如序列 (log n)^A，其中 log 是自然对数（尽管任何对数都适用），而 A 是任何大于 0 的指数。对数和对数的幂增长非常非常缓慢。有了这个见解，我们可以证明，如果 θ > 1，则序列 x_n = {α(log n)^θ} 具有泊松式的所有相关性和泊松间隙分布。

从某种意义上说，这种组合是可能的最强的伪随机测试。这也是我们所知的唯一显示此行为的示例族。换句话说，我们的数学机制无法检测出此序列是确定性的还是随机的垃圾（即使在无限次采样之后）。这意味着目前没有办法判断这个序列是随机的还是伪随机的。奇怪的是，如果我们取 θ = 1，则该序列甚至不是均匀分布的。因此，对于序列 x_n = {αlog n}，这些点似乎聚集在 0 到 1 之间的区间的左侧。这种模式甚至可以用肉眼看到，并且与称为本福德定律的东西有关，这意味着很明显这个序列不是随机的。

伪随机数的世界既奇特又充满了未解之谜。数学家们认为各种有趣的序列都是伪随机的，但却无法证明这一点。尽管与数学的其他领域存在着深刻的联系，但由于我们对伪随机序列的许多猜想缺乏证明，这阻碍了我们的进展。Technau、Sourmelidis 和我终于提供了一组例子，我们可以证明它们表现出强大的伪随机特性，但这些技术似乎只适用于缓慢增长的序列。在数学领域，很难预料进步会出现在哪里。也许将一些更复杂的现有机制与我们开发的方法相结合，可能会提供更深入的见解。又或者，有人会开发出一整套新的工具来判断什么是随机的，什么不是随机的。