第4章 随机数的产生优秀PPT.ppt

《第4章 随机数的产生优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第4章 随机数的产生优秀PPT.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章 随机数的产生现在学习的是第1页，共39页 在几乎所有的离散系统仿真中，随机在几乎所有的离散系统仿真中，随机数是一个必不可少的基本元素。数是一个必不可少的基本元素。大多数计算机语言都提供能够产生随机大多数计算机语言都提供能够产生随机数的子程序、对象或函数。同样，仿真语言数的子程序、对象或函数。同样，仿真语言也能产生用于事件发生时间和其他随机变量也能产生用于事件发生时间和其他随机变量的随机数。的随机数。现在学习的是第2页，共39页4.1.14.1.1随机数的定义随机数的定义 随机数是指从每一数出现几率相等的一系列随机数是指从每一数出现几率相等的一系列数中，靠随机的方法抽取出来的数。数中，靠

2、随机的方法抽取出来的数。4.1.24.1.2随机数的性质随机数的性质 一个随机数序列一个随机数序列R1，R2，必须满足两必须满足两个重要的统计性质：个重要的统计性质：均匀性和独立性均匀性和独立性。0,1 0,1均匀分布的随机数可以用来生成其它分布的均匀分布的随机数可以用来生成其它分布的随机数。随机数。4.1 4.1 随机数概述随机数概述现在学习的是第3页，共39页0,10,1均匀分布概率密度函数均匀分布概率密度函数 其他其他f(x)101x现在学习的是第4页，共39页关于均匀性和独立性的两个结论：关于均匀性和独立性的两个结论：1 1、如果将区间、如果将区间0,10,1分为分为n n类或等长的子

3、区类或等长的子区间，那么在每个区间的期望观测次数为间，那么在每个区间的期望观测次数为N/nN/n，其中其中N N为观测的总次数。为观测的总次数。2 2、观测值落在某个特定区间的概率与、观测值落在某个特定区间的概率与以前的观测值无关。以前的观测值无关。现在学习的是第5页，共39页4.1.34.1.3随机数的分类随机数的分类随随机机数数真随机数真随机数准随机数准随机数伪随机数伪随机数现在学习的是第6页，共39页真随机数：真随机数：真随机数数列是不可预计的，因而也不可能重真随机数数列是不可预计的，因而也不可能重复产生两个相同的真随机数数列。复产生两个相同的真随机数数列。真随机数只能用某些随机物理过程

4、真随机数只能用某些随机物理过程来产生。来产生。如果采用随机物理过程来产生真随机数，理论如果采用随机物理过程来产生真随机数，理论上不存在什么问题。但在实际应用时，要做出速度上不存在什么问题。但在实际应用时，要做出速度很快，而又准确的随机数物理过程产生器是非常困很快，而又准确的随机数物理过程产生器是非常困难的。难的。现在学习的是第7页，共39页准随机数：准随机数：准随机数概念是来自如下的事实：要实准随机数概念是来自如下的事实：要实现严格数学意义上的随机数，在理论上虽然现严格数学意义上的随机数，在理论上虽然可行，但在实际中却是不可行的，也没有这可行，但在实际中却是不可行的，也没有这个必要。关键是要保

5、证个必要。关键是要保证“随机随机”数数列具有数数列具有能产生出所需要的结果的必要特性。能产生出所需要的结果的必要特性。现在学习的是第8页，共39页 例如，在大多数模拟研究中，模拟事例例如，在大多数模拟研究中，模拟事例被认为是相互独立的，而这些事例的顺序则被认为是相互独立的，而这些事例的顺序则似乎并不重要。因而我们可以在大多数运算似乎并不重要。因而我们可以在大多数运算中，放心地置随机性的概念于不顾。同样，中，放心地置随机性的概念于不顾。同样，我们也可以不考虑对某些分布均匀性的涨落我们也可以不考虑对某些分布均匀性的涨落程度。程度。事实上在许多情况下，超均匀的分布事实上在许多情况下，超均匀的分布比真

6、随机数的均匀分布更合乎实际需要。比真随机数的均匀分布更合乎实际需要。现在学习的是第9页，共39页伪随机数：伪随机数：“伪伪”的意思是假，这里产生的是假的意思是假，这里产生的是假的随机数！的随机数！“伪伪”意味着使用某种已知的方法产生意味着使用某种已知的方法产生随机数的特别做法去除了真正随机性的可能。随机数的特别做法去除了真正随机性的可能。如果该方法已知，则随机数构成的集合如果该方法已知，则随机数构成的集合就会重复。就会重复。现在学习的是第10页，共39页 在伪随机数的产生过程中，一定会出现一在伪随机数的产生过程中，一定会出现一些与理想随机数的背离：些与理想随机数的背离：1.1.可能并不是均匀分

7、布的。可能并不是均匀分布的。2.2.可能是离散的，而不是连续的。可能是离散的，而不是连续的。3.3.平均值可能太大或太小。平均值可能太大或太小。4.4.方差可能太大或太小。方差可能太大或太小。5.5.数字之间可能不是相互独立的，如：数字之间可能不是相互独立的，如：(a)(a)数字之间自相关；数字之间自相关；(b)(b)数字接连大于或小于相邻的数字；数字接连大于或小于相邻的数字；(c)(c)若干大于均值的数跟着若干小于均值的数。若干大于均值的数跟着若干小于均值的数。现在学习的是第11页，共39页4.1.44.1.4仿真中伪随机数的特性仿真中伪随机数的特性 随机数作为仿真的一部分，通常由计随机数作

8、为仿真的一部分，通常由计算机产生。方法有很多，但必须具备以下算机产生。方法有很多，但必须具备以下特性：特性：程序的速度必须快。程序的速度必须快。程序的可移植性要强。程序的可移植性要强。程序必须有足够长的周期。程序必须有足够长的周期。随机数必须是可重复的。随机数必须是可重复的。尽可能逼近理想的均匀性和独立性统尽可能逼近理想的均匀性和独立性统 计性质。计性质。现在学习的是第12页，共39页4.2.14.2.1平方取中法平方取中法 一个二进制一个二进制n n位数位数X X自乘后一般得到一个自乘后一般得到一个2n2n位数位数X X2 2。设设X X0 0=b=b1 1b b2 2bbn n 则则X X

9、0 02 2=c=c1 1c c2 2ccn ncc2n2n取取X X0 02 2中间的中间的n n位数位数(设设n n为偶数为偶数)X X1 1=c=cn/2+1n/2+1c cn/2+2n/2+2ccn/2+nn/2+n重复上述步骤，可得重复上述步骤，可得X X0 0,X,X1 1,X,X2 2,。令令y yn n=X=Xi i2 2-n-n，则，则y y0 0,y,y1 1,y,y2 2,就是就是(0,1)(0,1)均匀分布的均匀分布的随机数样本。随机数样本。4.2 4.2 产生随机数的方法产生随机数的方法现在学习的是第13页，共39页十进制数的平方取中法：十进制数的平方取中法：设设X

10、X0 0=675248=675248 则则X X0 02 2=455 959861 504=455 959861 504 X X1 1=959861=959861 X X1 12 2=921 333139 321=921 333139 321 X X2 2=333139=333139 将将X X0 0,X,X1 1,X,X2 2,乘以乘以1010-6-6可得到可得到y y0 0=0.675248=0.675248，y y1 1=0.959861=0.959861，y y2 2=0.333139 =0.333139 现在学习的是第14页，共39页 应用平方取中法时，产生的数列具有应用平方取中法时

11、，产生的数列具有周期性，且可能遇到周期性，且可能遇到“退化退化”的危险，即出的危险，即出现中间所取得值都为现中间所取得值都为0 0，或形成重复循环样，或形成重复循环样本的现象。本的现象。现在学习的是第15页，共39页4.2.24.2.2线性同余法线性同余法 利用如下关系递推产生利用如下关系递推产生0 0到到m-1m-1之间的整数序之间的整数序列列X X1 1,X,X2 2,Xi+1=(aXi+c)mod m,i=1,2,初始值初始值X0种子种子 a乘子乘子 c增量增量 m模数模数 当当a=1a=1，上式为加同余法；，上式为加同余法；当当c=0c=0，则称为乘同余法；，则称为乘同余法；当当a1a

12、1，c0c0，称上式为混合线性同余法。，称上式为混合线性同余法。现在学习的是第16页，共39页例：取模计算 当当m=100m=100时，对以下各数进行取模。时，对以下各数进行取模。1197 1197 56821 56821 258 258 66 66 当当m m为为1010的幂的幂(即即m=10m=10b b)时，保留最右面的时，保留最右面的b b位位(十进制十进制)数数字，就可以完成取模运算。字，就可以完成取模运算。对于二进制计算机，当对于二进制计算机，当m=2m=2b b时，取模效率最高。时，取模效率最高。mod100=97mod100=97mod100=21mod100=21mod100

13、=58mod100=58mod100=66mod100=66现在学习的是第17页，共39页例：混合线性同余法例：混合线性同余法 产生随机数序列，其中产生随机数序列，其中X X0 0=27,a=17,=27,a=17,c=43,m=100c=43,m=100。X X1 1=(1727+43)mod100=502mod100=2=(1727+43)mod100=502mod100=2 X X2 2=(172+43)mod100=77mod100=77=(172+43)mod100=77mod100=77 X X3 3=(1777+43)mod100=1352mod100=52=(1777+43)m

14、od100=1352mod100=52 X X4 4=如何得到如何得到0 0到到1 1之间的随机数？之间的随机数？现在学习的是第18页，共39页 线性同余法产生的随机数除了要接近线性同余法产生的随机数除了要接近均匀性和独立性统计特性外，还有其他一均匀性和独立性统计特性外，还有其他一些重要性质需要考虑：些重要性质需要考虑：最大密度最大密度上例中可否产生上例中可否产生0.0070.007这样一个样本？这样一个样本？所产生两个大小相邻样本的最小间隔是多少？所产生两个大小相邻样本的最小间隔是多少？其产生的随机数的最大密度为多少？其产生的随机数的最大密度为多少？是什么在决定着最大密度？是什么在决定着最大

15、密度？现在学习的是第19页，共39页最大周期最大周期 在实际应用中，为了避免出现循环，得在实际应用中，为了避免出现循环，得到最大可能的周期，可以通过选择适当的到最大可能的周期，可以通过选择适当的a,c,ma,c,m和和X X0 0来获得最大周期的值。来获得最大周期的值。如果如果m=2m=2b b且且c0c0，当，当c c是相对于是相对于m m的素数，的素数，且且a=1+4k(ka=1+4k(k为正整数为正整数)时，最大可能周期时，最大可能周期P=m=2P=m=2b b。现在学习的是第20页，共39页 如果如果m=2m=2b b且且c=0c=0，当，当X X0 0为奇数，且为奇数，且a=3+8k

16、a=3+8k或或a=5+8ka=5+8k(k(k为正整数为正整数)时，最大可能周期时，最大可能周期P=m/4=2P=m/4=2b-2b-2。如果如果m m为素数且为素数且c=0,c=0,当当a ak k-1-1能被能被m m整除的最整除的最小小k k为为k=m-1,k=m-1,最大可能周期最大可能周期P=m-1P=m-1。例：例：令令a=7a=75 5=16807,m=2=16807,m=23131-1=2147483647,-1=2147483647,c=0,Xc=0,X0 0=123457,=123457,这些选择满足周期这些选择满足周期P=m-1P=m-1的的条件条件(超过超过2020亿

17、亿).).现在学习的是第21页，共39页4.2.34.2.3组合线性同余发生器组合线性同余发生器 随着仿真系统的复杂性大大增加，上例中随着仿真系统的复杂性大大增加，上例中的周期已经不能满足所有的应用要求了。我们的周期已经不能满足所有的应用要求了。我们需要得到周期足够长的发生器。需要得到周期足够长的发生器。一个卓有成效的方法是将两个或更多的乘同一个卓有成效的方法是将两个或更多的乘同余法结合起来，得到具有良好的统计性质以及更余法结合起来，得到具有良好的统计性质以及更长的周期性的发生器。长的周期性的发生器。现在学习的是第22页，共39页 如果如果W Wi,1i,1,W,Wi,2i,2,W,Wi,ki

18、,k为任意独立、离散为任意独立、离散取值的随机变量，但其中的一个取值的随机变量，但其中的一个(比如比如W Wi,1i,1)服从服从m m1 1-2-2上的整数均匀分布，则上的整数均匀分布，则服从服从0 0到到m m1 1-2-2上的整数均匀分布。上的整数均匀分布。现在学习的是第23页，共39页设设X Xi,ki,k为为k k个不同的乘同余发生器第个不同的乘同余发生器第i i次的输出次的输出值，其中第值，其中第j j个发生器的周期为个发生器的周期为m mj j-1.-1.现在学习的是第24页，共39页系数系数“(-1)(-1)j-1j-1”意味着执行减去意味着执行减去X Xi,ji,j-1-1此

19、发生器最大可能周期为此发生器最大可能周期为现在学习的是第25页，共39页4.2.44.2.4随机数流随机数流 线性同余随机数发生器所产生的每一个线性同余随机数发生器所产生的每一个X X都可以作为都可以作为“种子种子”继续产生随机数。继续产生随机数。对于一个线性同余随机数发生器来说，随对于一个线性同余随机数发生器来说，随机数流只不过是一种方便地从序列中挑选一个机数流只不过是一种方便地从序列中挑选一个初始种子的方法。初始种子的方法。S Si i=X=Xb(i-1)b(i-1)现在学习的是第26页，共39页 为了验证所产生的随机数是否达到了均匀性为了验证所产生的随机数是否达到了均匀性和独立性这两个期

20、望的性质，必须进行检验。和独立性这两个期望的性质，必须进行检验。1 1、频率检验、频率检验 H H0 0:R:Ri iU0,1U0,1 H H1 1:R:Ri iU0,1U0,1 2 2、自相关性检验、自相关性检验 H H0 0:R:Ri i独立独立 H H1 1:R:Ri i独立独立 拒绝虚假设拒绝虚假设H H0 0的失败意味着该检验接受此的失败意味着该检验接受此虚假设。但必须考虑显著性程度虚假设。但必须考虑显著性程度。4.3 4.3 随机数的检验随机数的检验现在学习的是第27页，共39页4.3.14.3.1频率检验频率检验科尔莫戈罗夫科尔莫戈罗夫斯米尔诺夫检验斯米尔诺夫检验 该检验将均匀分

21、布的连续累积分布函数该检验将均匀分布的连续累积分布函数F(x)F(x)与与N N个观测样本的经验累积分布函数个观测样本的经验累积分布函数S SN N(x)(x)相比较。相比较。F(x)=x,0 x1 F(x)=x,0 x1样本样本R R1 1,R,R2 2,R,RN N的的S SN N(x)(x)定义如下：定义如下：现在学习的是第28页，共39页基于如下统计：基于如下统计：D=max|F(x)-S D=max|F(x)-SN N(x)|(x)|D D的样本分布已知，它与的样本分布已知，它与N N的函数关系可查表的函数关系可查表得到。得到。步骤步骤1 1 将所有数据按照从小到大顺序排列将所有数据

22、按照从小到大顺序排列 R R(1)(1)RR(2)(2)RR(N)(N)步骤步骤2 2 计算计算 现在学习的是第29页，共39页步骤步骤3 3 计算计算D=max(DD=max(D+,D,D-)步骤步骤4 4 对给定的显著水平对给定的显著水平和样本大小和样本大小 N N，查表确定临界值查表确定临界值D D步骤步骤5 5 若样本的统计量若样本的统计量D D大于临界值大于临界值D D，则，则虚假设被拒绝。若虚假设被拒绝。若D DD D，则推断实际分布与，则推断实际分布与均分布之间未检测到差异。均分布之间未检测到差异。现在学习的是第30页，共39页例：例：假设产生了假设产生了5 5个随机数：个随机数

23、：0.44,0.81,0.44,0.81,0.14,0.05,0.93,0.14,0.05,0.93,使用科尔莫戈罗夫使用科尔莫戈罗夫斯米斯米尔诺夫检验其均匀性尔诺夫检验其均匀性,=0.05.0.05.0.050.140.810.440.930.200.400.800.601.000.150.260.160.070.050.210.040.13D+D-当当=0.05=0.05，N=5N=5时，查表时，查表D=0.565D=0.565，故不拒绝均匀性假设！故不拒绝均匀性假设！现在学习的是第31页，共39页2 2检验检验 O Oi i为第为第i i 组中数据的观测值个数组中数据的观测值个数 E E

24、i i为第为第i i 组中数据的期望个数组中数据的期望个数 n n为组数为组数 对于均匀分布对于均匀分布,如果各组间隔相等如果各组间隔相等,且且观测值的总数为观测值的总数为N,N,则则 的采样分布近似等于的采样分布近似等于有有n-1n-1个自由度的个自由度的 分布。分布。现在学习的是第32页，共39页例：例：使用使用2 2检验判断下列数据是否具有均检验判断下列数据是否具有均匀分布，匀分布，取取0.050.05。0.340.900.250.890.870.440.120.210.460.670.830.760.790.640.700.810.940.740.220.740.960.990.770

25、.670.560.410.520.730.990.020.470.300.170.820.560.050.450.310.780.050.790.710.230.190.820.930.650.370.390.420.990.170.990.460.050.660.100.420.180.490.370.510.540.010.810.280.690.340.750.490.720.430.560.970.300.940.960.580.730.050.060.390.840.240.400.640.400.190.790.620.180.260.970.880.640.470.600.110

26、.290.78现在学习的是第33页，共39页使用使用n=10n=10个等长区间，查表得个等长区间，查表得区间区间OiEiOi-Ei(Oi-Ei)21810-240.42810-240.4310100004910-110.151210240.46810-240.471010000814104161.691010000101110110.1总计总计10010003.4现在学习的是第34页，共39页 若样本数足够多，对测试数据样本的若样本数足够多，对测试数据样本的均匀性来说，科尔莫戈罗夫均匀性来说，科尔莫戈罗夫斯米尔诺夫斯米尔诺夫检验和检验和2 2检验都是可接受的。但科尔莫戈罗检验都是可接受的。但科

27、尔莫戈罗夫夫斯米尔诺夫检验是两者较强的，推荐使斯米尔诺夫检验是两者较强的，推荐使用。而且科尔莫戈罗夫用。而且科尔莫戈罗夫斯米尔诺夫检验可斯米尔诺夫检验可以应用到小样本场合，而以应用到小样本场合，而2 2检验只能在大样检验只能在大样本本(如如N50)N50)时才有效。时才有效。现在学习的是第35页，共39页4.3.24.3.2自相关性检验自相关性检验0.120.010.230.280.310.640.280.830.990.150.330.350.410.600.270.750.680.490.050.430.580.190.360.690.890.910.950.930.880.87 计算从第

28、计算从第i i个数开始，每个数开始，每m m个数之间的个数之间的自相关系数，即自相关系数，即R Ri i,R,Ri+mi+m,R,Ri+2mi+2m,R,Ri+(M+1)mi+(M+1)m的的自相关系数自相关系数imim。MM是使得是使得i+(M+1)mNi+(M+1)mN成立的最大整数。成立的最大整数。现在学习的是第36页，共39页 当当MM值很大的情况下，值很大的情况下，Z Z0 0应该应该服从均值为服从均值为0 0，方差为，方差为1 1的正态分布。的正态分布。现在学习的是第37页，共39页例：例：检查本小节开始提到的序列中的第检查本小节开始提到的序列中的第3 3、8 8、1313、个数是

29、否自相关，取个数是否自相关，取=0.05=0.05。N=30m=5M=4i=3 查表得查表得 ，不能拒绝独立性的虚假设。，不能拒绝独立性的虚假设。当当M M值小时，特别是被检验的数偏小时，这种值小时，特别是被检验的数偏小时，这种检验不太灵敏。检验不太灵敏。现在学习的是第38页，共39页 用一个用一个粒子放射源和一个高分辨率的计粒子放射源和一个高分辨率的计数器做成的装置，在数器做成的装置，在20 20 毫秒时间内平均记录毫秒时间内平均记录了了24.31524.315个个粒子。当计数为偶数时，便在磁粒子。当计数为偶数时，便在磁带上记录二进制的带上记录二进制的“1 1”。这个装置每小时可以产生大约这个装置每小时可以产生大约60006000个个3131比特比特(bits)(bits)的真随机数。的真随机数。现在学习的是第39页，共39页