严重依赖“伪随机数”，让计算机实现真正的随机有多难？

神译局是36氪旗下编译团队，关注科技、商业、职场、生活等领域，重点介绍国外的新技术、新观点、新风向。

编者按：生活当中看似到处都是随机。但真正的随机比你想象的要难得多。其实，我们接触的绝大多数都是伪随机数。即便如此，伪随机数的生成也是个很耗时间和内存的事情。但最近，MIT的研究人员找到了一种经典随机数生成算法的改进办法，令随机数的生成效率提高了很多，确定论的计算机有望将随机性植入到自己的建构块里面。Stephen Ornes对此进行了报导，原文发表在quantamagazine上，标题是：How and Why Computers Roll Loaded Dice

划重点

计算机软件和硬件运行的基础是布尔逻辑，不是概率

FLDR提出了一种将随机数集成到内置了确定性的软件和硬件里面的方法

大部分的随机数生成算法都是伪随机，是根据复杂的公式生成的

FLDR算法中时间和内存消耗上都非常高效

对于计算机来说，模拟投掷灌铅骰子一直是一个难题。

这是一个看似很简单的练习：让你想出一个随机的电话号码。选出七位数的序列，每一位都要等可能，并且选择一个数字不会影响到下一个数字。很有可能你选不出来。（不过我的话也不要全信：可以追溯到1950年代的研究表明，我们在数学上其实跟随机的关系不大，虽然我们都意识不到这一点。）

不要放在心上。计算机在生成随机性这件事情上做得也不好。本来我们也不指望它们能够做好：计算机软件和硬件运行的基础是布尔逻辑，不是概率。麻省理工学院Probabilistic Computing Project（概率计算项目）的负责人Vikash Mansinghka表示：“计算文化以确定性为中心。这一点表现在几乎每一个层面上。”

但是计算机科学家希望程序能够处理好随机性，因为有时候这就是问题的需要。多年以来，有些人开发出了新颖的算法，尽管这些算法本身不会生成随机数，但却提供了巧妙而有效的方式来利用和操纵随机性。麻省理工学院Mansinghka小组最近就取得了一项最新成果，他们提出了一种算法，叫做“快速摇灌铅骰子”（Fast Loaded Dice Roller ，FLDR）。这项成果将于今年八月份的在网上举行的国际人工智能与统计会议（Conference on Artificial Intelligence and Statistics）上进行展示。

简而言之，FLDR利用了一个随机序列来完美地模拟摇一颗灌铅骰子的情形。（或者是一枚加重的硬币，或被操纵的卡片组。新奥尔良大学的数学家Peter Bierhorst说：“算法展示了怎么把抛硬币从完全随机变成有偏向的。”Bierhorst并非研究的贡献者，但是他说FLDR成功背后的前提“很吸引人”。

FLDR不会让你在《地产大亨》游戏里面获得优势，也不会增加你去拉斯维加斯赌场掷骰子获胜的机会。但是算法的发明者说，它提出了一种将随机数集成到内置了确定性的软件和硬件里面的方法。给软硬件引入这种不确定性可以帮助机器做出像人一样的预测，并能更好地模拟依赖概率的现象，比如气候或金融市场等。

随机性是一个很棘手的概念，比乍看之下要棘手。在看不出模式的随机数序列里面，每个数字都有相同的出现概率。比方说，Pi本身并不是一个随机数，但是pi的每一位数字被认为是随机出现的（数学家称之为“正规数”）：从0到9，每个整数出现的次数相同。

是，Google搜索“随机数生成器”你是可以找到，但那些生成器生成的并不是纯粹的随机性。现在的处理器也好，搜索引擎以及密码生成器也好，它们用的都是“伪随机”的方法。当然，这些方法对于大多数用途而言都已经足够接近随机了，那是根据复杂的公式生成的，但是从理论上来讲，如果你知道那个公式的话，就可以预测序列。

科学家尝试将真正的随机性植入到机器里面至少已有80年的历史了。（在此之前，随机数来自传统的备用品，如掷骰子，从混匀的袋子里面取出编号球，或其他的机械练习。1927年，统计学家对人口普查数据进行采样，从而得到了一张有40000个随机数字的表格。）

麻省理工学院的Vikash Mansinghka表示，新的FLDR算法可以帮助科学家把概率植入到确定性计算机当中。

早期的随机数的来源是物理机器。第一台产生随机数的机器是英国统计学家莫里斯·乔治·肯德尔（Maurice George Kendall）和伯纳德·巴宾顿·史密斯（Bernard Babington Smith）的发明。1938年，他们对此进行了描述。机器被放进一间黑屋里面，然后旋转一个分成10等分的圆盘，每一份分别用0到9的数字标记。当某人用不规则的间隔敲击按键时，一道霓虹灯或火花就会照亮圆盘，让它看起来好像被定格了一样，但只有一个数字可见。后来又发明了另一台机器，叫做Ernie，这次则是在氖管中用了信号噪声。从1957年开始，英国的某个彩票就是用它来选出中奖号码的。

Bierhorst 说，最近以来，为了得到真正的随机序列，计算机科学家必须研究自然现象，比如宇宙背景辐射或量子系统的不可预测行为才行。他说：“自然界中存在可以利用的随机过程，这确实是不可预测的。那些忽左忽右躲闪腾挪的电子甚至事先都不知道自己要做什么。”

但是随机性只能带你走那么远了。到1940年代后期，物理学家开始生成随机数来拟合给定的概率分布。这样的工具（滚灌铅骰子的理论版）可以更准确地用于模拟现实情况，比方说交通流量或者化学反应。1976年，计算机科学家先驱Donald Knuth和Andrew Yao提出了一种算法，这种算法可以用一串随机数生成任意加权结果数组的随机样本。Mansinghka实验室的博士生Feras Saad 说：“这是有史以来最省时的算法。”

但不幸的是，Saad 说，这种算法要进行一定的折衷，那种计算机科学家都很熟悉的取舍权衡：很多跑得快的应用使用了大量内存，而使用内存较少的应用则可能需要很长的运行时间。Knuth和Yao的算法属于第一类，所以算法是很优雅，但是实际使用要占用大量内存。

但是去年春天时，Saad找到了一种聪明的解决方法。他意识到，当骰子的权重加起来等于2的幂次时，这一算法在时间和内存消耗上都非常高效。因此，对于一个六面骰子，假设滚出数字1到6的几率分别赋予1、2、3、4、5和1的加权。这意味着比方说滚出1的概率为1/16，滚出2的概率为2/16。由于权重的总和是2的幂次（16是2的4次方），所以这套系统的算法在时间和内存消耗上都很高效。

麻省理工学院博士生Feras Saad 帮助设计了一种新的算法，这种算法可以高效、准确地模拟摇灌铅骰子。

但是，假设权重取值改为1、2、3、2、4、2，总和为14的情况。由于14不是2的幂次方，所以Knuth-Yao算法需要占用更多的内存。Saad 意识到他可以增加一个权重，从而使得它们的总和总是2的幂次。在这种情况下，他只需给骰子增加一面——让假设的这一面权重为2，这样权重加起来就是16了。如果算法选到了原先的6面之一，就记录下相应的数值。如果选到了莫须有的那一面，就丢弃掉，然后再次运行算法。

这就是FLDR算法效率的关键，使得它成为了仿真的一个强大的工具：与原先一般需要占用大量内存的算法相比，多余的滚骰子所需占用的额外内存很小。

FLDR提高了Knuth-Yao算法的效率，并为改善一系列应用指明了方向。气候变化模拟，作物产量预测，粒子行为模拟，金融市场模型，甚至核武器地下爆炸的探测都取决于按照加权概率分布的随机数。随机数是用来保护通过互联网发送的数据的加密机制的支柱。

Mansinghka说，FLDR还可以帮助研究人员找到将概率整合到计算机处理器里面的方法，这是他在麻省理工学院实验室工作的重点。有了这一算法，软件库和新的硬件体系结构的设计就可以生成随机数并以有效的方式去利用这些随机数。这跟我们过去使用的确定性布尔机器将大相径庭。

他说：“ 我们很可能即将把随机性集成到软件和硬件的构建块当中。”

译者：boxi。