下载掌阅APP，畅读海量书库
立即打开
不知你是否思考过计算机中如何产生随机数的问题？要理解这个问题，我们先考虑这样一个问题：如何鉴别一串数字是“随机数”？例如，请看如下两串数字：
000100100010010001000110001000100111100010101010101000011101011
1111000110001101000111100000100010000111110000100110100010000100
在这两串数字中，有一串是笔者“随机”在键盘上敲打出来的，另一串是用计算机的随机数生产算法产生的。你能辨别出它们吗？是不是很难判断？
稍微思考下，我们就会发现，只要给出的两个序列足够长，就能鉴别出来。因为随机数是有特征的，在课堂上学过很多这种特征，比如期望值、方差等。那对这个“0-1”的序列，当然会先考察一下0和1的数量是不是差不多。就算打字的时候非常小心，把0和1写得很均匀，还是有好多其他特征可以考察的。
在这个例子里，如果0和1的数量符合期望，那方差也肯定是符合期望的。但还可以考虑其中最长的连续的1的序列。如果10000长度的0、1二值的随机序列，其中最长的连续的数字“1”的长度只有4，那凭直觉也可以知道这个序列是有问题的。虽然从某个特定位置开始连续出现5个1的概率是1/32，但是在一万个数字里一次也没发生的概率大约只有10 -35 这个数量级。事实上，在长度1万的“0-1”随机序列里，最长的连续“1”的长度，大致是在9到15之间。
计算举例：连续掷均匀的硬币1000次，所出现的最长连续正面结果的长度记作
，求
小于等于8的概率。（计算较为烦琐，可以先跳过，稍后阅读。）
这是一个比较复杂的问题，标准方法需要用到“马尔可夫过程”，以下采用一种适合中学生理解的方法，来解释这个问题（参考来源：知乎用户“liu-yu-chen-72-92”）。不妨先考虑一个简单的例子：计算连续掷10次硬币，最长连续正面少于3次的概率。
如果用1表示正面，用0表示背面，那么连续10次投掷硬币的结果可以表示为10位的二进制序列。比如：
1101010001
所有的投掷结果共有2 10 =1024种。现在要尝试计算出，其中连续的“1”少于3个的排列数。
对以上序列的末尾补上一个“0”，并且从左到右分段，使每一段都以0结尾，且只包含1个0。以上序列分段结果是：
110，10，10，0，0，10
考察其中每一段的长度，得到“3，2，2，1，1，2”，显然长度总和等于10+1=11（因为已在序列末尾添加了一个“0”）。
我们可以确认，每次不同的投掷结果都会产生一个不同的分段结果，也会产生一个不同的长度序列。如果某次投掷结果中，最长的连续“1”序列短于3，其对应的长度序列的每一项都小于等于3。
我们考虑这样一个函数：
当
时，它就是：
将以上函数展开后，观察
项的系数。我们可以发现，这个11次幂的系数恰好是上述6个括号中各取一项，使6个括号所取各项的指数之和恰好是11的所有组合种类数。而每种组合又恰好对应之前的一种分段结果。
比如，之前的分段结果是：110，10，10，0，0，10。那么相当于在以上函数中，对每个多项式分别取
，相乘后所得项可以验证，这些项的指数之和是11。
所以，所有分为6段的投掷结果，且其中没有连续3个或以上“1”的组合数，就是
的
项的系数。
那么，投掷10次，其结果最多分为11段。所以，在所有投掷结果中，没有连续3个或以上“1”的组合数，就是
到
的
项的系数之和。
为了方便计算，可以先计算多项式：
利用等比数列求和公式，得到以上多项式求和结果，
的系数是504。所以，连续投掷10次硬币，其中连续正面不超过3次的概率是：
504÷1024≈0.49
对项数更多的情况来说，计算多项式求和非常复杂，此时可以改为使用对无穷多项等比数列进行求和，并且利用泰勒级数求得对应项系数近似值的方法。
比如，对原问题“连续掷均匀硬币1000次，所出现的最长连续正面结果的长度记作
，求
小于等于8的概率”，对符合条件的组合数，相当于求多项式：
中，
项的系数。
因为当
时，在
中，
项的系数是0，并且，当
时，多项式值为1，也不影响
项的系数。所以，可以改为“下标等于0，对无穷多项的多项式求和”：
考察上式的泰勒展开式中
的系数，借助计算机可以算得其约为
。
因此，投掷1000次硬币，其中最长连续正面次数不超过8次的概率是：
若改为计算投掷1万次硬币的情况，则计算机直接求解仍然太慢。此时可以改为计算：投掷1007次硬币，重复10轮，每轮中连续正面次数都不超过8的概率。此时，所得结果与直接计算投掷1万次的情况应该非常接近。可以算得，投掷1万次硬币，其中最长连续正面次数不超过8次的概率约为0.0056%。
以上例子就是说明，用“瞎写”的方式产生的随机数并不是很好的，甚至是不合格的随机数，有很多方法可以鉴别出这种“假”随机数。为什么需要检验随机数呢？这可太重要了，小到一个游戏程序，大到一次彩票开奖；再从信息的加密传输到目前火爆的数字货币，这些程序中都需要随机数。如果随机数不够“随机”，那就会让恶意攻击者有机可乘，产生严重的后果。
然而，究竟什么是真正的“随机”？很意外，这是一个非常微妙的，甚至哲学化的问题。比如，投掷硬币产生的序列算不算“随机”呢？看上去是随机的，但是正如很多文章里说的，如果硬币投掷出去以后，所有的物理参数都能知道，比如初速度，角度，空气阻力，湿度，硬币密度、形状等所有与硬币落下后相关的参数都可知，并且有一台计算速度极快的计算机，可以根据那些参数计算出硬币掉落桌面后哪一面向上，那么掷硬币结果还算不算随机数？对此问题，爱因斯坦有句名言叫“上帝不掷骰子”。什么是真正的随机数，自然界中有没有“真”随机现象等问题，至今仍是既有争议，也十分微妙的话题。
在数学里，给“真”随机数一个定义。比如，“真正”的符合一半对一半概率的“0-1”二项分布的随机变量的定义：
设想一个你我之间的猜随机数游戏，我给出“0-1”分布随机数，你来猜。我每次会产生一个0或1的随机数供你猜，且你有以下两个便利条件。
第一个便利条件是，我允许你在猜之前向我索要任意多的随机数。也就是说，如果你认为历史上的随机数对下一次猜测有用的话，你可以任意研究过往随机数的历史。而且你想要多少我就给你多少，这是一个便利条件。
第二个便利条件是，你有一台拥有无限计算能力的计算机，计算速度要多快有多快，你可以尽情地在猜之前利用这台计算机去分析历史随机数，直到满意为止。甚至我先将随机数写在纸上，藏进一个保险箱里，你再开始做计算分析，分析满意之后再进行猜测，并开箱检验结果。
而“真”随机数就是：经过多次之后，你能猜对的概率仍然接近二分之一，那么我产生的随机数就是“真”0-1二项均匀分布的随机数。对于这个定义，如果用数学语言重新叙述，那就是：
对任意小的
，存在一个
，当游戏次数大于
次之后，你猜中的次数
除以游戏总次数
的比值，减去1/2后的绝对值，总会小于
：
以上就是“真”随机数的定义，是不是很啰唆？但是，以上条件缺一不可。
猴子乱敲键盘产生的字符看上去很“随机”，但密码学对“真”随机数有着严格的要求，并且有办法检查随机数的“质量”
首先，你得被允许观察历史随机数，真正的随机数是与历史无关的。所以，如果能通过分析历史随机数，使猜测随机数的成功率哪怕增加万分之一，那这个随机数仍然不是“真”的。
其次，你被允许有台拥有无限计算能力的计算机，而真正的随机数是不依赖挑战者的计算速度的。其理由跟之前一样，即“真”随机数的产生是独立事件，与之前的结果无关。
最后，要注意的是，挑战者猜测的成功率与1/2取差值比较后，需要取绝对值，即猜对或者猜错的“能力”都要能“收敛”在0.5上。如果你有了明显大于一半概率的“猜错”能力，则等价于有了“猜对”的能力，这也是不行的。
我们虽然有了完美随机数的定义，但实践中这个定义没有什么用，因为以上的猜数游戏纯属理想实验。没有哪个随机数提供者可以在有限时间里给你任意长度的随机数。随机数验证者也没有拥有无限计算能力的计算机。
所以，对随机数生成者，特别是用软件产生的随机数，只能尽量去接近这个标准，而无法达到这一标准。
对检验者来说，其目标也只能是检验出随机数是否在某种场合下质量已经足够好，可以当成“真”随机数来使用。这里说的随机数的检验主要是对计算机随机数生成算法的检验。以下我们从最简单的测试类型开始说明。
第一级测试： 范围测试，它测试产生的随机数是否位于目标范围。这个测试意义比较简单，但在边界问题上还需要注意。比如，如果算法是期望产生大于0，且小于等于1的随机数，而实际算法不能产生1，或者会产生0，且概率都很小，那么测试软件可能就发现不了这些问题。这种情况很难通过软件发现，只能靠人力去分析算法来检查。
第二级测试：
均值测试，即检查期望值。比如，随机数的目标期望值是100，那就计算出1万个随机值，求平均值，看看是不是能够接近100。另外，应该有不少读者学过概率学中“置信空间”这个概念，也就是说，可以计算出这1万个随机数平均值应该在怎样的范围区间内。比如，如果平均值应该有95%的概率在
的范围内，但实际平均值是106，那就有95%的把握说这个随机数算法是有问题的。
第三级测试： 方差测试，看随机数取值的变化程度。在均值测试中，如果均值的期望值是100，但实际发现每次测试1万个随机数的平均值，恰好不多不少都是100，这种情况是好是坏？如果这种情况只有1次还好说，如果经过10次测试，平均值都正好是100，那无论如何都不能让人相信这是随机数序列。这里同样是有“置信空间”的作用，因为可以知道随机数的变化分布程度是否在预设的置信空间内。
随机变量的均值和方差是随机变量的两个基本特征。但即使符合这两个特征，也不表示随机数算法就是正确的、可用的。比如，期望值是1的指数分布，与期望值是1且方差也是1的正态分布，这两种分布的期望值和方差是相同的。
第四级测试： “桶测试”，如果你不小心在应该产生正态分布随机数的代码里用了产生指数分布的算法，那用以上3种测试都测不出区别。这时就需要用到第四级测试。教科书里都画过每种概率分布的概率密度函数，正态分布像一口倒扣的钟，也叫“钟形曲线”，指数分布是从左上到右下下降的曲线。
要区分这两种情况，我们就可以在
坐标轴上等距离取若干个点，然后画垂线，每两条垂线之间就是一个个“桶”，然后考察随机变量落到不同的桶中的数量。比如，对于正态分布，我们知道在期望值两边对称的桶里的变量数量应该是差不多的，但对于指数分布，左边的桶就比右边的桶里的变量数量要多。这样，我们就能区分出这两种分布。
上图为正态分布的概率密度曲线，下图为指数分布的概率密度曲线。通过考察样本随机数落在纵向的每个“桶”形柱状区域内的数量，可以区分这两种随机分布
桶测试已经是非常细致的测试了，但它的精度跟桶划分的密度有关。不管怎么划分，都只能划分有限多的桶，还是存在很小的可能性，使你的算法在某个桶的狭小范围内失真。所以，还有一个关于随机数的终极测试：柯尔莫哥罗夫—斯米尔诺夫检验，简称“KS测试”。
这个测试的基本理念就是画出（准确来讲是拟合）测试样本的概率累积函数图像，然后与理论上的经验累积函数图像比较。有时是取两组测试样本画出两条概率累积函数图像互相比较。
“概率累积函数”在概率课本上应该出现过，就是函数值从0变化到1的一条曲线，其实就是概率密度函数的积分函数图像。不管函数具体是怎样定义的，我们可以想象，如果算法是对的，那样本拟合出来的累积函数图像应该是比较接近经验概率累积函数图像的，虽然总会有些小的误差。
KS测试就是取实验结果的函数图像与理论图像在某个垂直线上的最大差值。如果这个差值大到事先设定的某个“阈值”，或者说这个差值足够“显著”，那就要考虑随机数算法是否有问题了。当然，虽然我说得如此简单，但实际这个测试是有相当复杂的数学依据的。它可以定量地告诉你，这个最大误差发生的概率是多少，或者在一定执行空间内，这个误差应该在什么范围。
KS测试已经相当优秀，它还有一些变体测试，比如“夏皮罗-威尔克检验”和安德森-达令检验。每种测试各有利弊，这里就不一一细数了。
上图是KS测试示意图，红线是理论概率累积曲线，蓝色是实际被测试的随机数的累积曲线。考察两者之间的最大差距，即黑色箭头位置，可以用来检查随机数生成器的可靠性
关于随机数的测试，基本就是以上这些手段了。有意思的是，能够通过以上这些测试的随机数算法，并不一定是“安全”的算法，不一定能用在需要严格加密领域中的随机数生成。而有些被证明是非常安全的随机数算法，也并不能保证每次都能通过以上测试，尤其是桶测试和KS测试。这也是可以理解的，因为随机数本身就需要有不确定性。如果它能100%通过测试，那也就不随机了。这就是随机数的微妙和有趣之处。