走进科学
MIT提出了用随机数生成随机数的计算机算法
众所周知，计算机无法制造出随机性，它们也不应该：计算机软件和硬件运行在布尔逻辑，而非概率上。
目前，我们使用的真随机数据，一般来自系统从物理环境中采集到的“随机噪音”。
但是计算机科学家想要可以处理随机性的程序，因为那有时候是解决问题所必须的。多年来，有些公司开发出新颖的算法，尽管它们本身不会生成随机数，但却提供了巧妙而有效的方式来使用和操纵随机性。8月份，在线国际人工智能与统计会议上，麻省理工学院的Mansinghka小组公布了他们的最新成果之一：提出了被称为“快速加载的骰子滚轮”(FLDR)的算法。
简而言之，FLDR使用随机序列完美地模拟了加载模具的滚动。“它显示了如何将完全公平的抛硬币演变成有偏差的抛硬币，”新奥尔良大学的数学家彼得·比尔霍斯特说。
FLDR无助于分析金融市场的起落，也不会让您在拉斯维加斯占有优势。但是它的创造者说，它提出了一种将随机数集成到软件和硬件中的方法，这些软件和硬件本身却都遵循确定性的规则。纳入不确定性有助于机器做出人性化的预测，并更好地模拟诸如气候或金融市场等概率现象。
随机性是一个比看起来棘手的概念。在没有可识别模式的随机数序列中，每个数字都有相同的出现概率。例如，Pi本身不是一个随机数，但是Pi的各位数字则被认为是随机的(数学家称之为“正则”)：从0到9的每个整数都具有相同的出现频次。
即使您可以用Google的“随机数生成器”，也无法获得纯粹的随机性。当今的处理器，搜索引擎和密码生成器使用的“伪随机”方法对大多数用途而言都足够好用。它们来自复杂的生成公式，但是从理论上讲，如果您知道该公式，则可以预测之后的序列。
科学家将物理随机性植入机器的尝试，至少已有80年的历史。(在此之前，随机数来自掷骰子，从混匀的袋子中拾取的编号球或其他机械行为。1927年，统计学家对人口普查数据进行采样，从而得到了有40000个随机数字的工具手册。)
早期的随机数来源是物理过程。第一台产生随机数的机器是英国统计学家莫里斯·乔治·肯德尔(Maurice George Kendall)和伯纳德·巴宾顿·史密斯(Bernard Babington Smith)的发明。该机器被放置在一个黑暗的房间里，在那里，它旋转一个磁盘，将磁盘分成10个相等的楔形块(标记为0到9)。当某人以不规则的间隔轻敲按键时，短暂的霓虹灯或火花将照亮磁盘，使其看起来像定格，只有一个数字可见。后来，另一台名为Ernie的随机数机器改用氖管中的信号噪声。从1957年开始，英国彩票系统用它来开出中奖号码。
比尔霍斯特说，最近，为了得到真正的随机序列，计算机科学家必须研究自然现象，如宇宙背景辐射或量子系统的不可预测行为。他说：“自然界中存在可以利用的随机过程，这确实是不可预测的。向左或向右的电子甚至事先也不知道自己将要做什么。”
到1940年代后期，物理学家开始生成随机数以适应给定的概率分布。这样的工具可以更准确地模拟现实情况，例如交通物流或化学反应。1976年，计算机科学家高德纳(Donald Knuth)和姚期智(Andrew Yao)提出了一种算法，该算法可用一串随机数生成任何加权结果数组的随机采样。曼辛卡(Mansinghka)实验室的博士生Feras Saad说：“这是有史以来最省时的算法。”
不幸的是，萨阿德(Saad)说，不存在完美的算法，这对计算机科学家而言是众所周知的常识：许多运行速度很快的应用程序会占用大量内存，而占用内存少的应用程序则可能需要较长的运行时间。 Knuth和Yao的算法属于第一类，优雅，但在任何时候都会占用大量内存。
但是去年春天，萨阿德发现了一个聪明的解决方法。他首先意识到，当芯片上的权重加起来等于2的幂时，该算法在时间和内存上都是有效的。因此，对于六面骰子，假设将数字1到6滚动几率的加权分别为1、2、3、4、5和1。这意味着，如1的概率为1/16，滚动2的概率为2/16。由于权重的总和为16=2^4，因此针对该系统的算法在时间和内存上都很有效。
但是，假设权重取值为1、2、3、2、4、2，总和为14。由于14的乘方不是2的幂，因此Knuth-Yao算法需要更多的内存。 萨阿德意识到他可以添加一个额外的权重，这样总能令总和为2的幂次。就像是在6面骰子上，硬加上一个面，变成7面骰子。在这种情况下，如果最终“摇出”了人为添加的那一面，则返回值被丢弃，重新运行算法。
这是提高FLDR效率的关键，使之成为强大的工具：与原版需要的大量内存相比，添加额外权重所必须占用的额外内存量很小。
FLDR使Knuth-Yao算法高效，并提出了可被广泛应用的方法。气候变化建模，作物产量预测，模拟粒子行为，金融市场模型，甚至是核武器地下实验，都取决于加权概率分布中的随机数。
曼辛卡说，FLDR还可帮助研究人员找到将概率整合到计算机处理器中的方法，这是他在麻省理工学院实验室工作的重点。这将与我们过去使用的确定性布尔型计算机大相径庭。
本文译自 quantamagazine，由 majer 编辑发布。