随机数的可信性：事前理论论证，事中算法流程，事后统计验证

摘要: 随机数的可信性。参考：计算机程序设计艺术 第三章

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

大老板面临的随机公平性问题

最近新晋网红周鸿祎在各短视频平台上高调卖他9年的迈巴赫s600，要换国产新能源智能汽车，360 楼下已经成了车展。很多人都想买他的迈巴赫，而且都很有诚意。周鸿祎在视频里明确说了，不会是先到先得，也不会是价高者得，他要想一个公平的方式，哪怕是通过随机的方式来选择，最后谁也不得罪，最后卖给谁就靠缘分了。我们可以看一下大老板是如何解决他随机选择的公平性问题的。

随机系统的拆解

说回到随机抽样的可信性问题。对于一个抽样系统，可以理解为一个算法流程，其中的某些步骤引入了随机数，算法输出的结果也因为随机数的不同取值而不同，另一方面，算法输出的随机性也仅取决于这些随机数，这些随机数取相同值时，算法的输出是确定性的相同值。

在算法的层面需要保证：只要随机数是充分随机的，那么算法输出就是我们想要的分布，这样算法系统的随机性是否可信就完全转化为了随机数的随机性是否可信。

公平性中的主观性

对于一个随机数发生源产生的一个随机序列，要谈它的公平性非常难，因为这里面有很多主观性。

比如给一个人纸和笔，让他写下 100 个随机的 0~9 数字，写出令人满意的结果的机会是很微小的。人们倾向于避免似乎是非随机的一些事情，比如两个相等的相邻数字，但是事实上两个相邻数字出现的机会还挺大的（在毕业论文中，伪造一份看上去真实，后续也能经得起随机性检验的数据，比自己把实验做出来可能还难。你伪造了数据最后没事儿，仅仅是没查你而已）。

即使给一个人发一份经过检验的真正随机数字的表，他也可能会怀疑，因为他也许能看出某些奇怪的规律性，也许序列的某一段跟他的电话号码的模式重合，等等。

可以做的工作

也就是说，一个再好的随机数系统，仍然很难让所有人都觉得可信。但即使如此，我们还是可以从几个方面做出努力，给出尽可能让人信服的结论。

事前：理论推导

第一是事前的理论推导，在实际生成随机数之前，就告诉人们后续生成的序列不存在周期性，或者存在周期但是非常大。

这里会涉及到比较深的数学知识，比如线性同余法产生的序列的周期性，涉及到很多数论的知识。

事中：算法流程

第二是事中的算法流程，这一步主要是要展示随机数算法本身，以及随机数产生之后的算法流程没有接受多余参数的地方。告诉人们，只要随机数本身没问题，那么算法的输出结果就没问题。

事后：统计检验

第三是事后的统计检验，也就是实际生成一串序列之后，如何判定他是否随机。这也是相关的理论和实践最丰富的地方。检验方法不多，常见的有卡方检验、Kolmogorov-Simirnov 检验等。

但是检验的指标非常多，因为有很多特点让一串序列看起来好像不随机。比如是不是存在某个经常出现的数对，比如相同数字出现的间隔长度是不是过长，比如连续出现同一数字的次数是不是跟理论计算的平均值差太远，比如上升子序列的最长的长度是不是太短了，等等等等，这些都可以作为怀疑的依据。

在实践当中，应该用多个指标去检验，每通过一个检验，就让人们对随机性的信心提升一些。但这里注意，即使我们已经连续通过了很多指标的检验，也无法保证下一个检验一定通过。这也给了制度上的设计空间，可以让第三方提交他的检验程序和判断依据，如果没有人能设计某种检验使得程序生成的序列通不过，那就只好暂时相信它就是个随机序列。

参考书

这里推荐《计算机程序设计艺术》第2卷第3章的内容，本章讨论了关于随机数的大量课题：怎样生成随机数，怎样检验它们，怎样在应用中修正它们，怎样推导理论等。最终给出了如何在程序中给出一个可靠的随机数来源的算法。上面讨论的三个方面都有丰富的论证和推导，其中有大量习题，比如计算一个程序生成的序列的周期，比如证明某些数论或者概率的命题等等，作者在后面给出了详细答案，有时间的时候可以浅读一下，会发现我们调用了无数次的 rand() 背后有这么多事情。

---