计算机如何以及为什么掷出装填的骰子

这里有一个看似简单的练习：想出一个随机的电话号码。一个序列中的七个数字，选择时使每个数字的可能性相等，这样您选择的一个数字不会影响下一个数字。很有可能，你做不到。(但不要相信我的话：追溯到20世纪50年代的研究表明，我们在数学上是多么的非随机，即使我们没有意识到这一点。)。

别把这件事放在心上。计算机也不能很好地产生随机性。他们不应该这样做：计算机软件和硬件运行在布尔逻辑上，而不是概率上。“计算文化以决定论为中心，”麻省理工学院(Massachusetts Institute Of Technology)概率计算项目负责人维卡什·曼辛卡(Vikash Mansinghka)说，“这几乎体现在各个层面。”

但是计算机科学家想要能够处理随机性的程序，因为有时这是问题所需要的。多年来，一些人已经开发出时髦的新算法，虽然它们本身不会产生随机数，但提供了使用和操纵随机性的聪明而有效的方法。最新的努力之一来自Mansinghka在麻省理工学院的团队，他们将在今年8月举行的在线人工智能与统计国际会议上展示一种名为快速加载掷骰子(Fast Load Dice Roller，简称FLDR)的算法。

简单地说，FLDR使用随机序列来完美地模拟加载骰子的滚动。(或者是一枚有重量的硬币，或者是一副作弊的纸牌。)。新奥尔良大学数学家彼得·比尔霍斯特(Peter Bierhorst)说：“它展示了如何将完全随机的掷硬币变成有偏见的掷硬币。”比尔霍斯特没有对这项研究做出贡献，但将FLDR成功背后的前提描述为“令人信服”。

FLDR不会给你在垄断中的优势，也不会增加你在拉斯维加斯赌桌上的赔率。但它的创建者表示，它提出了一种将随机数整合到软件和硬件中的方法，这些软件和硬件都是确定性的。纳入这种不确定性将有助于机器做出与人类相似的预测，并更好地模拟气候或金融市场等依赖概率的现象。

随机性是一个比看起来更棘手的概念。在没有可辨别模式的随机数序列中，每个数字都有相同的出现概率。例如，pi本身不是一个随机数，但是pi的数字被认为是随机的(数学家称之为“正常”)：从0到9的每个整数出现的次数大致相同。

即使你可以在谷歌上找到一个“随机数生成器”，纯粹的随机性也不是你能得到的。今天的处理器、搜索引擎和密码生成器使用的“伪随机”方法对于大多数目的来说都足够接近。它们是根据复杂的公式生成的，但从理论上讲，如果你知道公式，你很可能可以预测序列。

至少80年来，科学家们一直试图在机器中建立真正的随机性。(在此之前，随机数字来自旧的备用设备，如滚动骰子、从混合良好的袋子中挑选的编号球或其他机械练习。1927年，一位统计学家对人口普查数据进行抽样，生成了一个包含40,000个随机数字的表格。)

随机数的早期来源是物理机器。第一台随机数生成机是英国统计学家莫里斯·乔治·肯德尔和伯纳德·巴宾顿·史密斯的创意，他们在1938年对其进行了描述。这台机器被放在一个昏暗的房间里，在那里它旋转着一个圆盘，圆盘被分成10个相等的楔形碎片，标记为0到9。当有人以不稳定的间隔敲击按键时，短暂的霓虹灯闪光或火花会照亮磁盘，使其看起来冻结，只有一个数字可见。后来的一台机器名为厄尼，它使用霓虹灯管中的信号噪音代替；从1957年开始，它在英国的一次彩票中选择中奖号码。

比尔霍斯特说，最近，对于真正的随机序列，计算机科学家必须关注自然现象，如宇宙背景辐射或量子系统不可预测的行为。他说：“自然界中有一些随机过程是可以利用的，而这些过程确实是不可预测的。”“向左或向右闪避的电子甚至事先都不知道它要做什么。”

但随机性只能带你走到这一步。到了20世纪40年代末，物理学家开始产生符合给定概率分布的随机数。这类工具-理论上是滚动加载骰子的版本-可以更准确地用于模拟现实世界的情况，如交通流或化学反应。1976年，开拓性的计算机科学家唐纳德·努斯和安德鲁·姚引入了一种算法，该算法可以使用一串随机数字来产生任意加权结果数组的随机抽样。曼辛卡实验室的博士生费拉斯·萨德(Feras Saad)领导了FLDR的新工作，他说：“这是人们所能得出的最省时的算法。”

不幸的是，萨阿德说，该算法做了一个计算机科学家熟知的权衡：许多快速运行的应用程序使用大量内存，而使用很少内存的应用程序可能会有很长的运行时间。Knuth和姚的算法属于第一类，这使得它很优雅，但对于任何实际用途来说都是内存密集型的。

但去年春天，萨阿德发现了一个聪明的变通办法。他意识到，当骰子上的重量加起来是2的幂时，算法在时间和内存上都是有效的。因此，对于一个六面骰子，假设掷出数字1到6的赔率分别为1、2、3、4、5和1。这意味着例如掷出1的概率是1/16，掷出2的概率是2/16。由于权重加起来是2-16的幂是24-这个系统的算法在时间和内存上都是有效的。

但是假设权重是1、2、3、2、4、2，它们的总和是14。因为14不是2的幂，所以Knuth-姚算法需要更多的内存。萨阿德意识到，他可以加入额外的权重，这样他们的权重总和就是2的幂。在这种情况下，他只需添加另一张假想的脸-一个权重为2的脸-这样权重加起来就是16。如果算法选择了其中一张原始脸，那么这个值就会被记录下来。如果选择了额外的面，则丢弃该值，并再次运行该算法。

这是FLDR效率的关键，使其成为模拟中的强大工具：与原始卷通常需要的大容量内存相比，额外卷所需的额外内存量微乎其微。

FLDR提高了Knuth-姚算法的效率，并提出了改进广泛应用程序的方法。气候变化模拟、作物产量预测、粒子行为模拟、金融市场模型，甚至是地下核武器爆炸的探测都依赖于加权概率分布中的随机数。随机数也构成了保护通过互联网发送的数据的密码方案的主干。

Mansinghka说，FLDR还可能帮助研究人员找到将概率集成到计算机处理器中的方法-这是他在麻省理工学院实验室的工作重点。该算法可以帮助设计能够生成随机数并以有效方式使用它们的软件库和新的硬件架构。这将戏剧性地背离我们习惯的决定论布尔机器。

“我们可能处于非常有利的地位，可以将随机性整合到软件和硬件的构建块中，”他说。