信息的本质——随机性，它不是上帝的骰子，而是我们无知的表现

自人类诞生之初，随机性就扮演着重要的角色。在人类历史的早期，随机性是由天象或者自然现象引起的，例如在天空中观察到的星星和行星的位置变化。随着时间的推移和技术的进步，随机性的应用越来越广泛，并且在不同领域中起着重要的作用。

20世纪40年代，舒尔提出了信息熵和通信信道容量等基本概念，奠定了信息论的基础。舒尔认为，随机性是信息的本质，因为它代表了信息中的不确定性和不可预测性。

20世纪50年代，随机性已经开始在计算机科学和人工智能领域得到广泛应用，而这种应用主要是基于概率和统计学的方法，通过随机选择或随机生成数据来解决一些问题。诺伊曼认为，这种方法并不是上帝的筛子，而是我们无知的表现，因为我们缺乏足够的知识和理解，无法用确定性的方法来解决某些问题，只能求助于随机性。

随机性在数论中也有着广泛的应用，包括素数分布、加密、随机数生成等方面。在素数分布方面，随机性被广泛应用于素数分布的研究和猜想中。素数分布的规律性一直是数学家们关注的问题之一，然而至今仍未找到规律。通过引入随机性，可以模拟大量随机数的分布情况，从而了解素数分布的大致规律。

假设你想确定一个给定的数是质数还是合数。你可以简单地尝试将它除以所有可能的因子，但对于大数来说，这种“暴力法”和其他因子分解算法非常缓慢。而且，如果这个数最后被证明是合数，分解算法会告诉你其除数的值，这比你所要求的信息要多。如果你只关心一个数的“素性”，有没有更高效的算法？

如果你运用随机性，确实存在更高效的方法。这个基本思想源于17世纪法国数学家皮埃尔·德·费马的一项成果，被称为他的“小定理（little theorem）”。费马考虑了两个整数，分别是N和x。他证明了，如果N是一个质数，那么

总是N的倍数，无论x的值是多少。换句话说，如果x^N - x不是N的倍数，那么N就不可能是质数。但反过来的说法并不总是成立：如果x^N - x是N的倍数，那么N通常是质数，但并非总是如此。

要将费马的小定理应用于素数检验，只需选定你感兴趣的N，随机选择x，然后将这两个数代入x^N - x。如果结果不是N的倍数，那么你就知道N肯定是合数。如果结果是N的倍数，那么N可能是质数。现在再随机挑选一个x并重试。在大多数情况下，经过几十次尝试后，你几乎可以确定N是一个质数。

基于费马小定理改进的随机算法的首个素数检验开启了一个新时代。一个又一个问题被证明使用随机性比非随机或确定性算法更容易解决。关键在于将每个问题重构为一个可以通过某个数字x的合适值快速解决的问题，然后证明几乎任何x都满足这一点。尽管研究人员不知道如何判断任何特定选择是否合适，但这种解决方案仍然有效。

然而，这些成功让研究人员不禁好奇为什么随机性会在如素数检验这类问题上有所帮助，而这类问题都是关于发现隐藏的、非随机的模式。

1994年，计算机科学家诺姆·尼桑（Noam Nisan）和阿维·维格德森（Avi Wigderson）通过证明随机性虽然有用，但可能并非必要，帮助解决了这个困惑。他们证明了以下两种情况之一必然成立：要么所有可以通过随机性高效解决的问题也具有快速的确定性算法，要么许多著名的困难问题实际上是容易的。计算机科学家认为第二种可能性非常不可能。

事实上，计算机科学家经常发现，通过从随机版本开始，然后“去随机化”它，更容易开发一个确定性算法。

在尼桑和维格德森的里程碑式证明近30年后，随机算法仍然非常受欢迎，因为去随机化可能相当棘手，并且确定性算法通常仅在理论上具有高效性。直到2002年，三位研究者才找到了一种对素数检验进行去随机化的方法，实际上他们的算法比最好的随机算法要慢得多。对于其他问题，甚至很难知道从哪里入手——最知名的算法存在一个类似于鸡和蛋的问题，只能通过随机性来解决。

这正是图论领域最近的一项突破。去年，三位计算机科学家研发了一种快速算法，用于在图中找到最短路径，即使其中一些线段使总路径长度减少而非增加。他们的算法包括通过删除某些线段将图转换为更简单的图，然后在简化后的图上解决问题，并对删除的线段进行处理。如果不存在太多的已删除线段包含图的最短路径，那么这个算法可以快速解决问题。否则，最后一步会耗费太多时间。

但首先如何决定删除哪些线段呢？确定性地找到理想的线段集合不仅困难——而且是不可能的。这个集合取决于哪些路径是最短的，这正是这三位研究者试图解决的问题。尽管他们无法找到最佳的删除线段集合，但他们可以证明大多数随机选择都相当不错，这足以打破自我指涉的循环。在极少数情况下，如果算法选择不佳，在最后一步陷入困境，他们可以停止并重新运行算法。

随机性基本上是一种在不知道最优解的情况下确保对最优解有正确了解的方法。随机性在计算机科学中找到了无数其他用途，从密码学到博弈论到机器学习。很有可能，随机性将一直存在。