首页 > 程序员的自我修养 > 随机数之谜
2015
01-15

随机数之谜

自我学习编程以来,生成随机数的random函数曾经令我困惑,又令我异常着迷。这个random函数几乎是任何一种编程语言必备的工具函数,其生成随机数可以应用到从游戏抽奖环节到蒙特卡洛模拟法的诸多领域,可谓是个异常重要的算法。故而我对这个算法产生了极大兴趣,我扪心自问:(1)一个算法如何才能生成随机数呢?(2)它如何证明自己生成的数字是随机的呢?

随着学习的深入,很快第一个问题有了答案:大多数random函数都是通过参照CPU时钟生成随机数的,虽然这些算法中有些比较复杂以令生成的结果集符合均匀分布或是其他概率分布——但不论如何,这样生成的随机数其实100%可以推算出来,所以算不得是真正的随机数。故而这些random函数被称作“伪随机数生成器”,它们生成的随机数也被称作“伪随机数”,用以和“真正的随机数”相区别。这样的结果无疑令我非常失望。那么什么数算是真随机数?

给定一个数,例如3214,可以说这个数是随机数吗?显然不能,因为不存在一个“特定的随机数”——特定这个概念本身就与随机相违背。那么随机数是什么?回忆一下第一次接触随机数这个概念的时候的所用引子吧——毫无疑问是抛硬币——每抛下一次硬币,你都无法预测结果是正是反,哪怕已经抛下10万次,你也不能100%确定下一次是正还是反。这就是随机数最重要的特性:它所产生的后面的那个数与前面的那个数毫无关系,你不能通过之前的随机实验结果去推测下一个随机数是多少。如同很多其他人类所创造的概念一样,人类也必须为这些概念所生成的复杂性负责。经济学家凯恩斯用随机的对立面来定义随机性:任何事先知道的、由于某种特定原因决定的或根据某种计划实施的,都不是随机的。从这个概念上看所谓随机数,就是人类无法掌握其规律的,不可预见的对象。法国著名数学家庞加莱则直言:或然性(随机性)不过是我们无知的一种量度。

1920-1950年是信息科学大发展的年代。有趣的是这个时代的三位计算机领军人物,香农,冯诺依曼,图灵都研究过随机数这个问题。

计算机开山祖师爷冯诺伊曼曾表示,由于其决定论算法和有限的存储容量,其计算机不可能生成真随机数。他说“任何考虑用算数方法来生成随机数的人都犯下了僭越之罪……因为,正如已经被指出的,并不存在一个随机数这样的东西,有的只是生成随机数的方法(例如掷骰子等物理方法),但一个严格的算术方法显然不属于其中之一”。从逻辑学角度也很容易理解上述内容,因为冯诺依曼的计算机体系架构和算法完全是基于决定论的——你给一个确定的输入,就有一个确定的结果。所谓决定论无非就是你现在在看这段文字,也是N万年前的原因决定好的结果而已。想在这样的体系下做一个算法,输入确定的值却返回无法预测的混沌,这与决定论体系本身就是自相矛盾的。除非你是超脱出这个体系的无所不能的“上帝”——这就是为什么冯诺伊曼说企图用算数方法来生成随机数的人犯下了“僭越之罪”。用纯数学算法生成不可预测的的混沌本身,就跟上帝创造这个混沌世界的故事没什么两样。

信息论鼻祖香农则证明,如果有一个纯数学算法可以生成100个随机数,那么就要输入100个随机数。换言之,只有用随机才能生成随机。现阶段所有能生成“真随机数的生成器”(True Random Number Generator, TRNG),无不是通过一些无法预测结果的物理过程来生成随机数的,例如热力学噪声、光电效应量子现象,这些物理过程在理论上是完全不可预测的,并且已经得到了实验的证实。硬件随机数生成器通常由换能器放大器模拟数字转换器组成。其中换能器用来将物理过程中的某些效果转换为电信号,放大器及其电路用来将随机扰动的振幅放大到宏观级别,而模拟数字转换器则用来将输出变成数字,通常是二进制的零和一。通过重复采样这些随机的信号,一系列的随机数得以生成。

图灵,停机问题

哥德尔不完备性定理

格里高利 蔡珽的数学理论:上帝不仅在量子力学和非线性动力学额中掷骰子,而且在基础数论中也如此。

这个问题最终会上升到形而上学的讨论:到底有没有自由意志?因为随机数代表着不可预测性,同时也代表着有着不可计划的自由意志。


留下一个回复

你的email不会被公开。