伪均匀随机数的计算机检验

1、 伪均匀随机数的计算机检验摘要现代社会中，计算机能力的提高使得随机数发生器在众多领域中有了较为广泛的应用，如蒙特卡罗方法，统计抽样技术和密码学等。同时关于随机数发生器也产生了很多的理论和方法，本文将简单介绍一些常见的伪均匀随机数发生器：线性同余发生器（LCG方法）和反馈位移寄存器法（FSR方法）。然后对伪均匀随机数序列进行统计检验。主要检验方法有参数检验（包括均值、方差或各阶距）、均匀性检验（包括卡方、柯氏和序列检验）、独立性检验（包括相关系数、列联表和游程检验）。最后，本文将利用Matlab生成一列随机数，并运用SPSS统计软件对此列随机数的统计特性择其适合的方法进行检验。关键词：伪随机数；

2、随机数发生器；统计检验；SPSS统计分析AbstractIn modern society, the improvement of computer capabilities make random number generator widely used in many areas, such as the Monte Carlo method, statistical sampling techniques and cryptography. At the same time there are a lot of theories and methods on the random num

3、ber generator, I will introduce some of the common random number generators briefly in this article: linear congruential generator (LCG method) and feedback shift register method (FSR method) . Then I will do statistical tests with the sequence of random numbers . Main methods are: parameter test (i

4、nvolving the mean, variance, or the order from) ,the test of homogeneity (involving Chi-square, Coriolis and sequence test), test for independence (involving the correlation coefficient, contingency table and the runs test. Finally ,this paper will use the Matlab generate a sequence of random number

5、s, use SPSS and select the appropriate test methods to test statistical properties of the sequence of random numbers.Key words: random number, random number generator, statistical test,SPSS statistical analysis目录摘要IAbstractII一、引言11基本概念和定理12 伪随机数2二、产生随机数的一般方法32.1 取中法32.1.1 平方取中法3乘积取中法32.2 同余发生器3混合同余法

6、4乘同余法4加同余法42.3反馈位移寄存器法4三、伪均匀随机数的统计检验63.1 检验步骤63.2 检验统计量63.3 统计检验方法7参数检验7均匀性检验8独立性检验10其他经验检验12四、实例分析134.1 数据产生及录入134.2 参数检验-单样本t检验134.3均匀性检验-卡方检验144.4独立性检验164.5本章小结18五、结论19参考文献20附录21一、引言在科学研究和工程设计中广泛应用到计算机模拟方法，从而常常需要产生大量的具有特定统计性质的随机数。这种随机数通常是由计算机以某种数学方法产生，他们实质上是完全确定的，但可以满足一定的统计特征，故也称为伪随机数。而如何产生达到统计要求

7、的随机数，则有不同的方法：硬件方法和软件方法。硬件方法可以在计算机上附上一个硬件设备或者采用移位寄存器来产生伪随机数；软件方法一般都采用数学公式法。至今关于随机数发生器有很多的理论和方法，其中除了传统的Fibonacci法、平方取中法、线性同余法、位移寄存器法和组合方法外，最近还有非线性同余法、取小数法、进位加和错位减法、广义反馈位移寄存器法等等。尽管这个领域己经有很多的理论研究，但是仍存在很多的实际问题，甚至最近提出的随机数发生器也有一些缺点。近年来在计算机中，比较广泛使用的方法就是同余法，而在高级程序设计语言中常采用线性同余法。每次生成的伪随机数需要满足独立的条件及给定分布函数的要求，但高

8、级程序设计语言中提供的库函数产生的伪随机数都是满足一定条件的均匀分布随机数，且在同一次程序运行中，每次产生的伪随机数是完全相同的。通过在微机上对用乘同余法和混合同余法产生的随机数进行大量的试验， 发现通过适当选择算法中的各常量， 用这两种方法产生的随机数，其分布特性一般容易通过统计捡验。用随机模拟方法解决实际问题时，首先要清楚随机数的产生方法，或者说是随机变量的抽样方法。1基本概念和定理 定义1: 设随机变量，则称随机变量随机抽样序列为分布的随机数。 若，则称来自的随机抽样序列为正态分布随机数；若服从指数分布，则称为指数分布的随机数；若区间均匀分布，则称为区间上的均匀分布随机数。 定理1 设是

9、连续且严格单调上升的分布函数，它的反函数存在，且记为即。若随机变量的分布函数为，则。若随机变量，则的分布函数为。推论 已知，设是一个分布函数，且反函数存在，则。 定理2：设服从二点分布相互独立，且令 =+（用二进制表示） 则定义2：(准均匀分布) 设离散随机变量的概率密度为： 则称为准均匀分布，且。2 伪随机数显然，用计算机只能产生准均匀随机分布数，但是当很大时，和均匀随机变量的统计性质差异很小，可以把准均匀随机数做伪均匀随机数。二、产生随机数的一般方法2.1 取中法 平方取中法平方取中法又称自然取中法，首先由Von Neuman于1940年提出， 此法开始取一个 2 位十进制整数作为种子，将

10、其平方得到的一个4位数（不足4位的高位补0），然后取该4位中间 2位作为下一种子数，并对此数进行规格化（化成小于1的2位的实数值），依上述过程类推便得到一维随机数列。其一般的递推公式是：的中间2位数字；按此公式依次得到一列数据，然后把这列数据的每一个元素都除以 ，可得到0,1区间上均匀分布的随机数列。乘积取中法乘积取中法是通过平方取中法改进得到的一种产生随机数的方法，其一般递推公式为：式中：第 n+1 个十进制的正整数；第 n+1 个伪随机数。 此方法虽然简单，但均匀性不好，且序列很快趋于零，其长度难以确定，故目前已很少使用。2.2 同余发生器该发生方法是目前应用最广泛的方法之一，通常我们把它

11、简称为LCG（Linear Congruence Generator）方法，它是由 Lehmer 在1951年提出的。此方法是利用数论中的同余运算来产生随机数的，故称之为同余发生器。LCG 方法的一般递推公式为： 其中初值为，为模数，为乘子（乘数），为增量（加数），且，均为非负整数。显然由上式得到的（=1,2,）满足：。从而。当然，递推公式中的参数，的选择十分关键。否则，进行了一定次数的迭代之后会出现短周期的重复现象，因而我们应慎重选取。当参数，选择不同时，对应的方法会有稍稍的不同，具体的讨论如下：混合同余法当上面的式中参数0，1时，则称之为混合同余法，或者称为混合式LCG。乘同余法 当式中=

12、0时的LCG方法称为乘同余法，或是积式发生器。具体表示式如下： ，初值为。加同余法当式中时，称之为加同余法。具体表示式为：，初值为虽说此方法可于以达到最大的周期，而且计算机实现比较方便。但是和上面的混合同余法、乘同余法对比，验证得出：该方法得到的随机数列性质相对较差。所以，一般常用的是混合同余法和乘同余法。2.3反馈位移寄存器法随着 LCG 方法的应用，人们渐渐发现其缺陷并开始寻找新的随机数发生方法。因此，通过大家的努力，在1965年以 Tausworthe 的相关论文为基础，出现了几种比较好的随机数发生器。它的主要原理是通过对寄存器进行位移，直接在存储单元中形成随机数。我们称这种方法为反馈位

13、移寄存器法（Feedback Shift Register Methods）,简称之为 FSR 方法。其线性递推公式为： 其中为给定正整数，或为给定的常数。1971年，Toot hill、Robinson 和 Adams 又给出了 FSR 的另一递推公式： 其中是次数小于的且系数为0或1的多项式。而且0为正整数。三、伪均匀随机数的统计检验伪均匀随机数的有效性在于它们与真正的区间上均匀随机数的性质是否有显著差异。这是一个重要的问题。因为二者若有显著差异，这时以这种随机数发生器产生的随机数为基础的随机变量所得到的样本就不能够反映该随机变量的性质，从而无法得到可靠的随机模拟结果。因此随机数发生器的检

14、验是一项很重要的工作。一般情况下，会有两种不同的检验方法：经验检验和理论检验。经验检验是一种统计检验，它是以发生器产生的均匀随机数序列为基础的，根据区间上均匀总体简单随机样本的性质，如特征向量、均匀性、随机性等，研究我们产生的随机序列的相应性质，进行比较、借鉴、视其差异是否显著决定取舍。理论检验从统计意义上说并不是一种检验，它用一种综合的方法来评估发生器的参数值，而根本不必产生任何随机数序列，即它只是一种理论上的研究。由于理论检验方法需要专门学科的知识，数学上又相当难，我们这里只讨论经验检验的几种方法，通常称为统计检验。3.1 检验步骤首先假设总体具有某种统计特性，然后由样本值检验这个假设是否

15、可信，此法又称假设检验，具体步骤如下：提出假设：总体分布为；选取适当的统计量，其中是样本，并求出在成立时的分布；给定显著水平，确定检验方法，即给出否定域:使得 由观测值（样本值）计算值；做统计判断，当时否定；当时，相容。3.2 检验统计量 根据中心极限定理得到近似正态分布统计量设是相互独立同分布，且，记=，则以为极限分布。统计量将总体的简单子样按一定规则分为互不相交的个组，记第组的观测频数为，若随机变量属于第组的概率为，记理论频数，由构造统计量渐进服从，其中是附加在概率分布上独立约束条件的个数即确定概率时利用样本估计总体参数的个数，当时，。3.3 统计检验方法参数检验均匀随机数的参数检验是检验

16、由某个发生器产生的随机数序列的均值、方差和各阶矩阵等与均匀分布的理论值是否有显著差异。若随机变量，则若是均匀总体的简单随机样本，即相互独立同分布，记，。则有： ；。设是某个发生器产生的随机数，首先对特征量作统计检验。在是均匀总体的简单随机样本的假设下，统计量 渐进服从。给定显著性水平后，查标准正态数值表得：()，否定域。由随机数序列计算的值，若，则认为产生的随机数序列的特征向量与均匀总体的特征量没有显著差异；否则，由于的特征量与均匀总体的特征量有显著差异，故不能认为是均匀总体的简单样本。我们用SPSS做参数检验时用单样本t检验。单样本t检验的目的是利用来自某总体的样本数据，推断该样本的均值是否

17、与指定的检验值之间存在显著差异。它是对总体均值的假设检验。单样本t检验的原假设为：总体均值与检验值之间不存在显著差异，表述为：，为总体均值，为检验值。对单个总体均值的推断是建立在单个样本均值基础上的，也就是希望利用样本均值去估计总体均值。构造t检验统计量为：，其中为样本方差。式中，t统计量服从n-1个自由度的t分布。SPSS将自动计算出t统计量的观测值和对应的概率P-值。给定显著性水平，与检验统计量的概率P-值比较。若概率P-值小于显著性水平，则应拒绝原假设，认为总体均值与检验值之间存在显著差异；反之，则不应拒绝原假设，认为总体均值与检验值之间无显著差异。均匀性检验 随机数的均匀检验又称为频率

18、检验，它用来检验由某个发生器产生的随机数序列是否均匀的分布在区间上。也就是检验经验频率与理论频率的差异是否显著。 检验 卡方检验基本思想的理论依据是：如果从一个随机变量中随机抽取若干个观察样本，这些观察样本落在的个互不相交的子集中的观察频数服从一个多项分布，这个多项分布在趋向于无穷时近似服从卡方分布。设使待检验的一组随机数，假设：为均匀总体的简单样本。 将区间分为个小区间，以表示第个小区间，设落入第个小区间的数目为。 根据均匀性假设，落入每个小区间的概率为，第个小区间的理论频数，统计量渐进服从，给定显著性水平，查分布表得临界值后，即可对经验频率与理论频率的差异作显著性检验。若的概率P-值小于显

19、著性水平，则应拒绝原假设，认为样本来自的总体分布与期望分布或某一理论分布存在显著差异；反之，则不能拒绝原假设，可以认为样本来自的总体分布与期望分布或某一理论分布不存在显著差异。K-S检验（柯氏检验）K-S（柯尔莫哥洛夫-斯米尔诺夫）检验的原假设是：样本来自的总体与指定的理论分布无显著差异。其基本思路是：首先，在原假设成立的前提下，计算各样本观测值在理论分布中出现的累计概率值；其次，计算各样本观测值的实际累计概率值；计算实际累计概率值与理论累计概率值的差；最后，计算差值序列中最大绝对差值，即。统计量也称为K-S统计量。在小样本下，原假设成立时，统计量服从柯氏分布。在大样本下，原假设成立时，近似服

20、从分布：当小于0时，为0；当大于0时，=若统计量的概率P-值小于显著性水平，则应拒绝原假设，认为样本来自的总体分布与给定的分布存在显著差异；反之，则不能拒绝原假设，可以认为样本来自的总体分布与给定的分布不存在显著差异。 序列检验（Serial test）序列检验实际上是用于多维分布的均匀性检验，它也间接地检验序列的独立性。已知随机数序列，将容量为的随机数一次配对为： 如果是均匀随机数序列，那么他们应该构成平面上正方形内的二维均匀随机向量的样本。将单位正方形分成个等面积的小正方形，表示落入第个小正方形的频数；理论频数。则检验统计量在为均匀分布的独立抽样序列成历史渐进的服从。以上二维的序列检验可以

21、推广到三维、四维直至一般的维。即对依次用不相交的阶组合：，它们应该是在单位维超立方体中均匀分布的独立随机样本。把区间分为个相等的小区间，相应地把单位维超立方体分成个小立方体，用表示落入第个超立方体的个数。统计量渐进服从。这种维均匀分布的检验（序列检验）间接地检验了的独立性。独立性检验 独立性检验主要检验随机数序列之间的统计相关性是否显著。它通常包括以下几种检验方法： 相关系数检验 两个随机变量的相关系数反映它们之间线性相关程度，若两个随机变量独立，则它们的相关系数必为零（反之不一定），故可以利用相关系数检验随机数的独立性。设是待检验的一组随机数，原假设：相关系数。考虑样本的阶自相关系数 相关系

22、数范围为：，当时，表示变量的线性相关性较弱。SPSS将自动计算自相关系数及标准误差，概率P-值，若检验统计量的概率P-值小于给定的显著性水平，应拒绝原假设，认为变量存在线性相关性；若相反，则不应拒绝原假设，认为变量间不存在线性相关性。当充分大，且成立时，渐进服从分布。利用统计量可以进行相关性检验。 相关系数检验 另外，的阶自相关系数还可以定义为： 其中，。 记，则可以证明：，这时检验假设可以用检验假设来代替。统计检验量为：利用统计量可进行相关性检验。 列联表检验在平面上，将单位正方形分成个相等的小正方形，把个随机数按先后顺序两两分组，例如取：，其中，为大于1的正数。记这些数对落入第个小正方形内

23、的数目为令：， 用表示落入第个小正方形内的概率。当独立性假设成立时， 其中，表示随机数落入第列的概率，表示落入第行的概率。用最大似然法可得： 检验统计量：渐进服从，其中是用样本来估计的个数，故，所以。其他经验检验如最值检验，最值检验主要是检验伪均匀随机数序列的最大值和最小值。四、实例分析 本文利用Matlab中的Rand函数来产生随机数序列并运用作者学过的SPSS统计软件对随机数序列做统计检验。4.1 数据产生及录入打开Matlab，在工作窗口输入指令：shuju=1*rand（1000,1）+0，点击“Enter”即得到1000个数据。而由于SPSS无法直接读取MATLAB data fil

24、e格式的数据，因此我们先将产生的随机数导入一个电子表格中，命名为“shuju”这样，SPSS就可以直接读取了，步骤为：选择菜单【File】-【Open】-【Data】，选择数据文件的类型“.xls”，并输入文件名“shuju”，出现下图： 我们默认将Excel工作表中的全部数据读入，直接点击“ok”。得到界面如下： 4.2 参数检验-单样本t检验单样本t检验在本例中的原假设可以表述为：=0.5。操作步骤：选择菜单【Analyze】-【Compare Means】-【One-samples T Test】出现如下图所示的窗口：将数据选择到【Test Variable（s）】，并将【Test Va

25、lue】中的0改为0.5，点击“ok”，得到以下结果：由第一张表可知：Matlab产生的1000个01之间的随机数的均值是0.51723，标准差是0.28536，均值标准误差是0.09024。从第二张表我们看到这组数的t统计量的观测值是1.909，自由度为999，t统计量的双尾概率P值是0.057，显然P> (=0.05)，则不应拒绝原假设，即认为总体均值与检验值之间无显著差异：样本均值与检验值的差是0.01723（它除以均值标准误差0.09024后得到t统计量的观测值），最后两列是总体均值与原假设值差的95%的置信区间为（-0.00048，0.03494），由此计算出总体均值的95%的

26、置信区间为（0.49952，0.53494），这表示我们有95%的把握认为总体均值在0.499520.53494之间，0.5包含在这个区间内，这也证明了总体均值与检验值之间无显著差异。4.3均匀性检验-卡方检验本例中卡方检验的原假设可以表述为：样本数据的分布与（0,1）上的均匀分布无显著差异。但在做卡方检验之前，需要将数据分组。我们将这1000个数据分为十组，即各组为：00.10000、0.100010.20000、0.200010.30000、0.900011。操作步骤如下：选择菜单【Tansform】-【Recode】-【Into Different Variables】，选择分组变量到【

27、Numeric Variable->Output】框中，在【Output Variable】框中的【Name】后输入存放分组结果的变量名，并按“change”确认。也可在【Lable】后输入相应的变量名标签，再按“Old and New values”按钮进行分组区间的定义。如下图：然后进行卡方检验。操作步骤如下：选择菜单【Analyze】-【Nonparametric Tests】-【Chi-Square】，出现如下窗口：选择待检验的变量到【Test Variable List】框中。在【Expected Values】框中给出理论值，我们默认为“All categories equal”(即表示所有子集的频数都相等)。得到下表：第一个表的第二列是指每组的频数，第三列是理论频数，第四列是实际频数与理论频数的差；第二个表是计算的卡方统计量以及对应的概率P-值，若选择的显著