一元连续型随机数的生成与检验

课程设计（综合实验）报告（2011--2011年度第1学期）名称：数学建模课程设计题日：一元连续型随机数生成及检验院系：数理系班级：学号：学生姓名：指导教师：设计周数：2周成绩：日期：2012年1月12日摘要：本文具体阐述了线性混合同余法生成随机数的过程，并对生成的随机数进行了参数检验、均匀性检验和独立性检验，验证了线性混合同余法生成随机数的正确性。关键字：随机数均匀分布伪随机数2检验1、问题重述：（1）背景人类研究产生随机数已有一段漫长的历史，最早的随机数产生基本上是手工实现的，如抽签、掷骰子、发纸牌以及从箱子里摸编号球等都属此类；20世纪初，统计学家和赌博者对随机数发生兴趣，制造出了很多能更快产生随机数的机械装置；随着计算机的广泛应用，随机数的产生更加得到重视，40〜50年代，人们转向用数学方法来产生随机数。（2）问题设随机变量X（总体）服从某种随机分布，对其进行了n次独立观察，得到一组简单随机样本气,x2，...,X.，满足：1）X],X2,...,X相互独立；2）每一个X],X2,...,X都与总体X同分布.利用某种方法得到一串数列r,r，…,r，在一定的统计意义下可作12n为随机样本X,X，…,X的一组样本值，称r,r,...,r一组具有与X相同12n12n分布的随机数.现在需要寻求一种简便、经济、可靠并能在计算机上实现的产生随机数的方法.而最常用、最基础的随机数是在(0,1)区间内均匀分布的随机数。在得到一系列随机数后，我们又面临如何检验所得的随机数是否满足使用要求的问题。2、问题分析直接抽样法时，利用均匀随机数r通过给定分布函数的逆F一i(r)来得到给定分布随机数的抽样法，其主要依据为下列统计中的结果。定理：设F(x)为一连续的分布函数，则若X〜F(x)，则R=F(X)〜U(0,1)；若R〜U(0,1)，则X=F-i(R)〜F(x)；其中F-1(y)=inf{x:F(x)>】0<y<1)称为F(x)的逆。据此定理，生成均匀随机数r后，由r=F(x)所能解出的x=F-1(r)即为给定分布F(x)的随机数x的直接抽样公式。例：用直接抽样法产生指数分布f(x)二人e-人x，(x>0)的随机数，其中人〉0为参数。解：指数分布的分布函数F(x)=1-e&，(x>0)，则对均匀随机数r，由r=1-e九解得x=-ln(1-r)。又因r和1-r均服从(0,1)上的均匀分布，故x=-llnr，即为指数分布的直接抽样力公式，在产生均匀随机数r后，由该公式即得指数分布的随机数x。而我们所真正需要的随机数应该不是真正的随机数，而是统计上满足使用需求的随机数，产生方便，使用方便，易于产生。并满足一下特性：分布均匀，尽可能接近U(0,1)；统计上独立；产生速度足够快；可以重现；有足够长的周期；用内存尽可能的少。严格意义上来说，现在所有的随机数发生器都不是在概率论意义下的真正随机数，而只能是称为伪随机数，因为无论哪一种随机数发生器都是采用递推算法一一即有一定规律可言，这已经违反了概率论意义下随机的含义。但是，如果算法选择合适，则通过该算法得到的数据，可以在一定程度下满足统计检验的要求，具有较好的统计特性，也就可以用于模拟。由于“伪”随机数应该是随机数，又具有均匀、独立的特点，因此要进行以下三个方面的检验：参数检验；均匀性检验；独立性检验。3、模型假设把伪随机数近似看成随机数。4、模型建立与求解分析历史上常用的随机数的生成方法有平方取中法、乘法取中法、常数取中法和菲波那契法。这些方法虽然简单、百观、易于实现，但同时也存在数据内部特性难以控制，容易出现退化等问题。此处我们使用混合线性同余法。通式：X=[aX+c]modmU:=X，m其中:a表示乘子；c表示增量；X0表示初值；m表示模；通常4个参数都取整数。因为参数的选择不同对产生的随机序列和统计特性有极大的影响，所以问题的关键在于如何选择参数以得到好的结果。显然，根据通式X.广[aX+c]modm，可得：0<X<m—1；由于X为整数，因此由此所得到的随机数肯定是有限个数;I通式：X.1=[aX+c]modm=(aX+c)—[(aX+c)/m]*mlI令N=axX.+c贝U：X.1=N—[N/m]xmX.的范围0<X<m；U]=X"m<1；X.为整数，所以max(X.])=m—1，0<X.1<m—1而且，其数据周期的重复出现;进一步讨论因为x.取值有限，因此肯定会在m次迭代内出现重复值；又因为X.+1取值，只与X.相关，则一旦乂重复出现，后续X.+1都会完全重复。X.+1为整数，所以只能为｛0,1,2,...师-1｝中的一个，则*也为有限长，为｛0，1/m，2/m，…，m-1/m｝之一。由此带来的问题：可能会不均匀，即最大的周期长度可能是m，但是并不一定。m越大，X.+1的选择范围越大，数字出现的频率越均匀气的可选择范围也越大。反之如果m取的小，则U+1很难为均匀分布。通常，取m尽可能的大，如：取m=2b其中b为计算机最大位长，如果取b=31，m=2x109，即该随机数发生器能够产生21亿以上个不重复随机数。Um为周期式的重复，在每个m段中，计算公式是相同的。且X..肯定是不随机的，因为可以根据递归调用发现，只要m，a，C，X0一旦确定，则X是函数可得的，本质上不存在任何随机性。i5、模型检验分析：由于在实际应用中，我们并不真正需要“真”的随机数，只要满足“某些条件”的“伪”随机数已经足够了。所以我们现在面临的问题是如何验证由混合线性同余法所得的随机数是否满足使用要求。由于“伪”随机数应该是随机数，又具有均匀、独立的特点，因此要进行以下三个方面的检验：参数检验；均匀性检验；独立性检验。检验过程：1、参数检验对于随机数u,u，…,u(N为数据长度)，一些常见的进行检验的参12N数包括：均值的估计值：u=£u/n；方差的估计值：S2=上Z(u-u)2；n一1均值估计值的期望：E面=1；2均值估计值的方差：见u)=上；12n方差估计值的期望：E(s2)二1；12方差估计值的方差：D(s2)^1；180n可构造如下统计量：x广^一^=、：顽(u一2)，X2=S2-ES°=\E(s2-£)；注意到当N足够大时，X,X近似服从n(0,1)分布，对给定的显著水平a(假定为0.05)，查表可得临界值为1.96。当1yI>1.96时，拒绝eu)=1和D(访=1的假设；1212n当|匕|>1.96时，拒绝E(s2)二£和D(s2)=-8-假设，否则接受这两个假设。这样，我们就把参数检验转化为标准正态分布的检验。卜面用混合线性同余法生成了400个随机数(具体随机数见附录1)，我们先假设这些数服从u(0,1)分布，则有：TOC\o"1-5"\h\zU=-£u=0.4979，s2=-^£(u-u)2=0.0875；nin-1^^且有：E(u)=，D(u)=，E(s2)=，D(s2)=；212n12180n我们知道服从u(0,1)分布的均值u=1，方差82=.1。212我们取统计量X,X，u—E(u)—厂】、X=—_=%.12n(u-—)，1项2X2=S2D；)=、E(s2-£)；当n充分大时，则应有X,X都近似服从n(0,1)。取以=0.05，查止态分布表Z=1.96；2由于|X]|=0.1441<1.96，叩=1.1117<1.96；所以在显著性水平a=0.05条件下，可以接受总体均值u=1，方差82=1的假设。212另外，用matlab拟合出了正态分布函数及正态随机数的经验分布函数和u(0,1)分布函数及u(0,1)的经验分布函数，分别取产生的随机数个数n=20,50,200,2000正态分布函数及正态随机数的经验分布函数:n=20n=50n=2000u(0,1)分布函数及u(0,1)的经验分布函数:n=20EmpiricalCDF°-91—°-8-----…-…十——°-7-—:。…一一---一一--■-X-一一....i-.....一一........；0-3"-一一…/…一十一一…一一…一一……°；i01-tX---…--…十一一…一十…一。iin=2000'：...'2、均匀性检验对于给定的随机数，其均匀性检验主要是采用频率检验法，手段是检验所产生的随机数落在各子区间的频率和理论频率之间的差异是否显著。常用的频率检验法有两种：K-S检验(Kolmogorov-Smirnov)和/2检验；在这里，我们使用Z2检验。思路:将(0,1)区间分成k个相等的子区间，检查总数为N的随机数落在各子区间的实际频数n与理论频数的差异是否显著。设落在第/个子区间的随机数的实际频数为n，落在第/个子区间的理论频数为m，m=N/k；建立x2统计量:木2=8上冬=kE(n—N)2i=1'i=1当样本量足够大时，该统计量近似服从自由度为k-1的X2分布，显著水平a一般取0.01〜0.05。x2当统计量>临界值(k—1),(1—a)时，则在该显著水平上拒绝该批样本为均匀的假设。X2检验步骤：分区间k；统计n和计算m；计算统计量x2；根据显著水平及自由度k-1从x2表查临界值；比较x2和临界值，确定是否接受。下面用x2拟合优度检验法对上面得到的随机数做分布均匀性检验，我们将样本的取值范围分布在10个等宽区间，即分成0〜0.1，0,1〜0.2，…，0.9〜1，10个区间。统计实际落在每个区间内的样本个数n.如下：i12345678910ni32603040304052343840如对均匀分布，则这些数落在第"区间内的概率1。按X2拟合法，取统计量V=—£〃2/p-n=—£n2-n=13.240i取以=0.05，查自由度k-1=10-1=9的X2分布表X2059=16.92>|V|=13.2故应接受显著水平为的a=0.05均匀性假设。3、独立性检验检查随机数样本间是否存在相关性，常用的有下列三种方法:(1)相关性检验’Zuu—u2'ii+k"N—k)设给定随机数列U1,u2，..,un，前后相距为k的样本的相关系数的估计值为pk，则若k阶自相关系数为0，即p广0。建立统计量：Vk=pkJN-k当N充分大时，该统计量近似服从N(0,1)分布；给定显著水平a=0.05,计算出k=1,2,…,k...时各阶自相关系数的估计值；若I匕I>1.96，则拒绝相关系数pk=0的假设。（2）组合规律性检验-Poker检验用于检查随机数样本中重复数字出现的频率，从而检查该组样本的组合规律性。如，三位数：三个数字相同出现的概率为：P三个数字相同）=0.10.1=0.01三个数字不同出现的概率为：P三个数字不同）=0.90.8=0.72有两个数字同时出现的概率为：p两个数字相同）二C（3,2）（0.0.9）=1-0.01-0.72=0.27以此作为理论频率与实际频数作比较，然后对其进行2检验。在给定的显著水平下，找出临界值，根据临界值确定差距是否显著。（3）连贯性检验根据给定样本中是否存在每隔一些数字就连续出现增大或减少的趋势，或连续在均值之上或在均值之下的现象来判断给定的样本是否相互独立。可以采用一种符号来表示一种事件的出现，连续出现的相同（或单个）事件的符号连就称为一个“连”，这样容易看到相同事件出现的规律性。如两种类型的10个事件的符号+--+++-就构成了6个连（相同状态的事件构成一个连）。常用的连贯性检验方法有：升降连检验和正负连检验。在此，我们使用正负连检验。判定给定样本中是否每隔一些数字就出现连续在均值之上或在均值之下的趋势。大于均值的样本用+号表示，其总数为n「小于均值的样本用-号表示，其总数为〃;2用这些+、-号组成的符号串中最大可能的连数为N=气+七(N为样本个数)，最小连数为1；设》为一个样本序列的连的总数(连续发生的+或-事件构成一个连)则其均值和方差分别为：2nn1广N22nn(2nn—N)bbN2(N—1)当数字总数N>20时，连的总数a近似服从正态分布N(u,a2)；建立统计量：7_b—(2nnJN)—1/2o2nn(2nn—N)1N，(N—y1/2据显著性水平确定临界值(正态)，以确定是否显著。现在我们将上面随机数分别与均值u_0.5相减，取其符号得到一个正负号序列，统计其中的正号个数n_208，负号个数n=192，b=188；假设这些数式独立分布的，取统计量b则应有：u=丑2+-=200.18bN2^2=2nin2(2nin2—N)=99.4296bN2(N—1)b近似于正态分布。由于Z0=；「(2罟：N—N；/2=(188—200.18)/、99.4296=—1.2215[1212“1/2N2(N—1)取a=0.05，查正态分布表Z=1.96>|ZJ=1.22152故应该接受这一假设。6、模型评价通过对线性混合同余法产生的随机数进行参数检验、均匀性检验和独立性检验，验证了线性混合同余法的优越性，这种方法也不失为一种好的随机数生成法。7、参考文献邓集贤等.概率论及数理统计(上、下册).北京：高等教育出版社.第4版.2009.石博强等.MATLAB数学计算范例教程.北京：中国铁道出版社.2004.高祖新等.统计计算与软件实用统计计算.南京：南京大学出版社.1996.附录：附录1产生400个随机数：u=rand(1,400)m=mean(u)v=var(u)x1=sqrt(12.*400).*(m-1./2)x2=sqrt(180.*400).*(v-1./12)0.01490.28820.81670.98550.01740.81940.62110.56020.24400.82200.26320.75360.65960.21410.60210.60490.65950.18340.63650.17030.53960.62340.68590.67730.87680.01290.31040.77910.30730.92670.67870.07430.07070.01190.22720.51630.45820.70320.58250.50920.07430.19320.37960.2764

0.77090.31390.63820.98660.50290.94770.82800.91760.11310.81210.90830.15640.12210.76270.72180.65160.75400.66320.88350.27220.41940.21300.03560.08120.85060.34020.46620.91380.22860.86200.65660.89120.48810.99260.37330.53140.18130.50190.42220.66040.67370.95730.19190.11120.56510.96920.02370.87020.02690.51950.19230.71570.25070.93390.13720.52160.89520.94240.33510.43740.47120.14930.13590.53250.72580.39870.35840.28530.86860.62640.24120.97810.64050.22980.68130.66580.13470.02250.26220.11650.06930.85290.18030.03240.73390.53650.27600.36850.01290.88920.86600.25420.56950.15930.59440.33110.65860.86360.56760.98050.79180.15260.83300.19190.63900.66900.77210.37980.44160.48310.60810.17600.00200.79020.51360.21320.10340.15730.40750.40780.05270.94180.15000.38440.31110.16850.89660.32270.73400.41090.39980.50550.16930.52470.64120.01620.83690.80350.69780.46190.08260.82070.19300.44540.01300.30870.87540.83530.33310.88070.47970.56080.61590.66190.61660.68510.51020.71400.51520.60590.96670.82210.31780.58770.13020.25440.80300.66780.01360.56160.45460.90490.28220.06500.47660.98370.92230.56120.65230.77270.10620.00110.54180.00690.45130.19570.78710.61860.01550.89090.76170.90700.75860.38070.33110.50410.56460.76720.77990.48410.80220.47100.20280.57960.66650.67680.94250.77010.73740.86630.99090.50390.62910.79260.44860.52440.17150.13070.21880.10550.14140.45700.78810.28110.22480.90890.00730.58870.54210.65350.31340.23120.41610.29880.67240.93830.34310.56300.11890.16900.27890.55680.48560.95220.23190.47870.52650.79270.19300.90960.92220.01330.76750.94730.81330.92380.19900.67430.92710.34380.594