在复杂网络分析领域，经常需要研究随机性。很多复杂网络的配置模型（例如ER图和无标度网络）在生成网络实例的时候，都需要通过计算机产生随机数。我们大多数时间不需要知道计算机产生随机数的具体细节，不过这里还是整理一下相关的知识，其中包含了一些很有意思的思想和方法。
本文介绍了伪随机数的定义、生成和检验，主要回答以下两个问题：（1）为什么计算机生成的随机数叫“伪”随机数？（2）为什么我们将确定性的伪随机数视为“随机”的？
真随机与伪随机
伪随机数的检验
上面说到，伪随机数是完全可以预测的。那么，就有一个问题：它的“随机性”又是怎么一回事呢？
伪随机数生成器的“随机性”指的是它生成的序列看起来像一组随机数：
假设我们有一个(0,1)均匀分布的伪随机数生成器，它生成了一组样本A。
假设我们有一个“真正的”(0,1)均匀分布的随机事件，它生成了一组样本B。
那么，A和B具有完全相同的统计规律。
换句话说，如果如果只给了一串样本，几乎没有办法区分它是由真正的随机事件产生的，还是通过伪随机数生成器生成的。
换句话说，如果一个伪随机数生成器生成的一串样本能够通过：（1-1）均匀分布的检验，（1-2）独立性的检验；我们就认为这个伪随机数生成器生成了独立同均匀分布的随机数。
伪随机数生成器的检验通常有以下两种：（1）实证检验（Empirical test）；（2）理论检验（Theoretical test）。
其中，实证检验的全部方法的总结如下图所示：
（1）实证检验（Empirical test）
（1-1）均匀分布的检验
实证检验采用的是假设检验的思路，主要看的是生成的样本的分布（Empirical）和均匀分布（Theoritical）的相似程度。
假设检验的Null Hypothesis是：
生成的样本的分布和均匀分布没有显著差别。
对于均匀分布的检验主要有两种：Kolmogorov-Smirnov test和Chi-square test。（其实不一定要是均匀分布，这两种检验可以检验任意分布）。
（1-1-1）Kolmogorov-Smirnov test
基本思想是看理论分布F(x)和样本频数之间的最大差值。
具体步骤：
关于KS检验的D统计量，有如下图形化的解释：
本文地址：百科问答频道 https://www.neebe.cn/wenda/903273.html，易企推百科一个免费的知识分享平台，本站部分文章来网络分享，本着互联网分享的精神，如有涉及到您的权益，请联系我们删除，谢谢！
相关阅读
