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

伪均匀随机数的计算机检验摘要现代社会中，计算机能力的提高使得随机数发生器在众多领域中有了较为广泛的应用，如蒙特卡罗方法，统计抽样技术和密码学等。同时关于随机数发生器也产生了很多的理论和方法，本文将简单介绍一些常见的伪均匀随机数发生器：线性同余发生器（LCG方法）和反馈位移寄存器法（FSR方法）。然后对伪均匀随机数序列进行统计检验。主要检验方法有参数检验（包括均值、方差或各阶距）、均匀性检验（包括卡方、柯氏和序列检验）、独立性检验（包括相关系数、列联表和游程检验）。最后，本文将利用Matlab生成一列随机数，并运用SPSS统计软件对此列随机数的统计特性择其适合的方法进行检验。关键词：伪随机数；随机数发生器；统计检验；SPSS统计分析AbstractInmodernsociety,theimprovementofcomputercapabilitiesmakerandomnumbergeneratorwidelyusedinmanyareas,suchastheMonteCarlomethod,statisticalsamplingtechniquesandcryptography.Atthesametimetherearealotoftheoriesandmethodsontherandomnumbergenerator,Iwillintroducesomeofthecommonrandomnumbergeneratorsbrieflyinthisarticle:linearcongruentialgenerator(LCGmethod)andfeedbackshiftregistermethod(FSRmethod).ThenIwilldostatisticaltestswiththesequenceofrandomnumbers.Mainmethodsare:parametertest(involvingthemean,variance,ortheorderfrom),thetestofhomogeneity(involvingChi-square,Coriolisandsequencetest),testforindependence(involvingthecorrelationcoefficient,contingencytableandtherunstest.Finally,thispaperwillusetheMatlabgenerateasequenceofrandomnumbers,useSPSSandselecttheappropriatetestmethodstoteststatisticalpropertiesofthesequenceofrandomnumbers.Keywords:randomnumber,randomnumbergenerator,statisticaltest,SPSSstatisticalanalysis目录摘要................................................................IAbstract...........................................................II一、引言............................................................11基本概念和定理.................................................32伪随机数......................................................4二、产生随机数的一般方法............................................32.1取中法......................................................32.1.1平方取中法.............................................32.1.2乘积取中法.............................................52.2同余发生器..................................................62.2.1混合同余法.............................................42.2.2乘同余法...............................................62.2.3加同余法...............................................62.3反馈位移寄存器法.............................................7三、伪均匀随机数的统计检验..........................................63.1检验步骤....................................................63.2检验统计量..................................................63.3统计检验方法................................................73.3.1参数检验...............................................73.3.2均匀性检验.............................................83.3.3独立性检验............................................103.3.4其他经验检验..........................................12四、实例分析.......................................................134.1数据产生及录入.............................................134.2参数检验-单样本t检验......................................134.3均匀性检验-卡方检验.........................................144.4独立性检验..................................................164.5本章小结....................................................18五、结论...........................................................19参考文献...........................................................20附录...............................................................21一、引言在科学研究和工程设计中广泛应用到计算机模拟方法，从而常常需要产生大量的具有特定统计性质的随机数。这种随机数通常是由计算机以某种数学方法产生，他们实质上是完全确定的，但可以满足一定的统计特征，故也称为伪随机数。而如何产生达到统计要求的随机数，则有不同的方法：硬件方法和软件方法。硬件方法可以在计算机上附上一个硬件设备或者采用移位寄存器来产生伪随机数；软件方法一般都采用数学公式法。至今关于随机数发生器有很多的理论和方法，其中除了传统的Fibonacci法、平方取中法、线性同余法、位移寄存器法和组合方法外，最近还有非线性同余法、取小数法、进位加和错位减法、广义反馈位移寄存器法等等。尽管这个领域己经有很多的理论研究，但是仍存在很多的实际问题，甚至最近提出的随机数发生器也有一些缺点。近年来在计算机中，比较广泛使用的方法就是同余法，而在高级程序设计语言中常采用线性同余法。每次生成的伪随机数需要满足独立的条件及给定分布函数的要求，但高级程序设计语言中提供的库函数产生的伪随机数都是满足一定条件的均匀分布随机数，且在同一次程序运行中，每次产生的伪随机数是完全相同的。通过在微机上对用乘同余法和混合同余法产生的随机数进行大量的试验，发现通过适当选择算法中的各常量，用这两种方法产生的随机数，其分布特性一般容易通过统计捡验。用随机模拟方法解决实际问题时，首先要清楚随机数的产生方法，或者说是随机变量的抽样方法。1基本概念和定理定义1:设随机变量~)(xF，则称随机变量随机抽样序列i为分布)(xF的随机数。若~N2,，则称来自的随机抽样序列，，21为正态分布随机数；若服从指数分布，则称，，21为指数分布的随机数；若ba~，区间均匀分布，则称，，21为ba，区间上的均匀分布随机数。定理1设)(xF是连续且严格单调上升的分布函数，它的反函数存在，且记为)(1xF即xxFF)]([1。若随机变量的分布函数为)(xF，则F~)1,0(U。若随机变量R~)1,0(U，则)(1RF的分布函数为)(xF。推论已知)(~xG，设)(xF是一个分布函数，且反函数)(1xF存在，则)(~))((1xFGF。定理2：设iX服从二点分布，，，21i相互独立，且0}1{}0{iiXPXP令=21X+22X+…+2kX…kXXX21.0（用二进制表示）则~)1,0(U定义2：(准均匀分布)设离散随机变量*的概率密度为：kkiPP21121)12210(ki，，，，则称*为准均匀分布，且121212121kkVarE，。2伪随机数显然，用计算机只能产生准均匀随机分布数，但是当k很大时，*和均匀随机变量的统计性质差异很小，可以把准均匀随机数做伪均匀随机数。二、产生随机数的一般方法2.1取中法2.1.1平方取中法平方取中法又称自然取中法，首先由VonNeuman于1940年提出，此法开始取一个2s位十进制整数作为种子，将其平方得到的一个4s位数（不足4s位的高位补0），然后取该4s位中间2s位作为下一种子数，并对此数进行规格化（化成小于1的2s位的实数值），依上述过程类推便得到一维随机数列。其一般的递推公式是：21{nnww的中间2s位数字}；按此公式依次得到一列数据，然后把这列数据的每一个元素都除以210s，可得到[0,1]区间上均匀分布的随机数列nuuu，，，21。2.1.2乘积取中法乘积取中法是通过平方取中法改进得到的一种产生随机数的方法，其一般递推公式为：snnssnnnxRxxx21121110)10(mod10式中：1nx——第n+1个十进制的正整数；1nR——第n+1个伪随机数。此方法虽然简单，但均匀性不好，且序列很快趋于零，其长度难以确定，故目前已很少使用。2.2同余发生器该发生方法是目前应用最广泛的方法之一，通常我们把它简称为LCG（LinearCongruenceGenerator）方法，它是由Lehmer在1951年提出的。此方法是利用数论中的同余运算来产生随机数的，故称之为同余发生器。LCG方法的一般递推公式为：，，，21mod1nMxrMcaxxnnnn其中初值为0x，M为模数，a为乘子（乘数），c为增量（加数），且nx，M，a，c均为非负整数。显然由上式得到的nx（n=1,2,…）满足：Mxn0。从而10，nr。当然，递