第5章_随机数的产生与模拟

1第五章随机数的产生与模拟目录随机数的产生与模拟§5.1均匀随机数的产生5.1.1线性同余法（LCG）的递推公式5.1.2反馈位移寄存器法（FSR）5.1.3组合发生器§5.2非均匀随机数的产生5.2.1逆变换法5.2.2值序抽样法5.2.3复合抽样法5.2.4直接抽样法5.2.5舍选抽样法返回作业思考题2随机数的产生与模拟用随机模拟方法解决实际问题时，首先要解决的是随机数的产生方法，或称随机变量的抽样(sampling)方法。随机数的概念：本章重点介绍[0，1]区间上均匀分布随机数的产生和检验。本章目录3随机数的产生与模拟均匀分布随机数：本章目录定理1.1：设是连续且严格单调上升的分布函数，它的反函数存在，且记为，即)(xF)(1xFxxFF)]([11、若随机变量的分布函数为，则)(xF)1,0(~)(UF)(1RF2、若随机变量，则的分布函数为)1,0(~UR)(xF4随机数的产生与模拟uuFFuFPuFPuF)]([)}({})({)(111设随机变量的分布函数为，当时，)(F)(1uF]1,0[u证明：当时，；当时，0u0)(1uF1u1)(1uF所以)1,0(~)(UF设的分布函数为，则)(1RF)(2xF)()]([)}({})({)(12xFxFFxFRPxRFPxFR因为，对任意有。所以的分布函数为)1,0(~UR)())((xFxFFR]1,0[)(xF)(1RF)(xF5随机数的产生与模拟定理1.1说明了任意分布的随机数均可由均匀分布的随机数变换得到。常简称的随机数为均匀分布随机数。)1,0(U)1,0(U本章目录6随机数的产生与模拟本章目录产生随机数的一般方法：手工方法：抽签、掷骰子、摇号等；随机数表法：占用内存大，目前已很少使用；物理方法：不能重复计算；数学方法：使用最广。7随机数的产生与模拟伪随机数：在计算机上用数学方法产生均匀随机数是指按照一定的计算方法而产生的数列，它们具有类似于均匀随机变量的独立抽样序列的性质，这些数既然是依照确定算法产生的，便不可能是真正的随机数，因此常把用数学方法产生的随机数称为伪随机数。伪随机数不可能真随机；需要对产生的伪随机数进行各种检验保证其符合独立性条件且分布为要求的分布；本章目录8随机数的产生与模拟本章目录9随机数的产生与模拟1均匀随机数的产生均匀随机数的产生：主要有线性同余法（LCG），组合同余法，反馈位移寄存器方法等本章目录10随机数的产生与模拟1均匀随机数的产生同余定义：性质：①对称性：a≡b(modM)，则b≡a(modM).②传递性：若a≡b(modM)，b≡c(modM)，则a≡c(modM).11随机数的产生与模拟1均匀随机数的产生性质：例如：已知12≡60(mod16)，M=16，取C=6，因为(M,C)=2，则有2≡10(mod8)，其中M/(M,C)=16/2=8。或者，取C=12，M=16，因为(M,C)=4，则有1≡5(mod4)，其中M/(M,C)=16/4=4。12随机数的产生与模拟1均匀随机数的产生求余运算的式子A(modM)定义为：MwhenAMMAAMwhenAAMMAAMA)(mod其中表示求的整数部分。MAMA13均匀随机数的产生：01))(mod(值xMxrMcaxxnnnn初,...2,1n随机数的产生与模拟1均匀随机数的产生本章目录线性同余法（LinearCongruenceGenerator，LCG）的递推公式为：14均匀随机数的产生：随机数的产生与模拟1均匀随机数的产生本章目录线性同余法的周期：15均匀随机数的产生：随机数的产生与模拟1均匀随机数的产生本章目录线性同余法产生的序列一定会重复，因为一共只有M个可能取值。,,,210xxx16均匀随机数的产生：随机数的产生与模拟1均匀随机数的产生本章目录说明：满周期是T=M时。17均匀随机数的产生：随机数的产生与模拟1均匀随机数的产生本章目录当c≠0时，上式称为混合同余发生器，当c=0时，称为乘同余发生器，此时当模为素数时，称它为素数模乘同余发生器。18两个常用的混合式发生器：350353511522)2)(mod15(xxrxxnnnn3103131122)2)(mod453806245314159269(xxrxxnnnn,...2,1n随机数的产生与模拟1均匀随机数的产生本章目录19常用的素数模乘同余发生器：312)312()312(mod312535035351xxrxxnnnn,...2,1n随机数的产生与模拟1均匀随机数的产生本章目录20常用的素数模乘同余发生器：,...2,1n12)12()12(mod31031311xxrxaxnnnin)4,3,2,1(i168071a3972040942a7642611233a6303600164a随机数的产生与模拟1均匀随机数的产生本章目录21组合发生器：先用一个随机数发生器产生的随机数列为基础，再用另一个发生器对随机数列进行重新排列得到的新数列作为实际使用的随机数。这种把多个独立的发生器以某种方式组合在一起作为实际使用的随机数，希望能够比任何一个单独的随机数发生器得到周期长、统计性质更优的随机数，即组合发生器。随机数的产生与模拟1均匀随机数的产生本章目录22组合发生器：随机数的产生与模拟1均匀随机数的产生本章目录Maclaren和Marsaglia在1965年提出的著名的组合发生器是组合同余发生器,该算法的具体步骤如下：23组合发生器：2用第二个LCG产生一个随机整数,要求;jkj13令，然后再用第一个LCG产生一个随机数,令；置;jntxyytj1nn4重复2~3，得随机数列，即为组合同余发生器产生的数列。若第一个LCG的模为，令，则为均匀随机数nxMMxrnnnr随机数的产生与模拟1均匀随机数的产生本章目录1用第一个LCG产生个随机数，一般取。这个随机数被顺序地存放在矢量中。置;k),,,(21ktttT1nk218k24检验目的：检验均匀伪随机数符合独立同均匀分布；两种检验方法统计检验：对生成的伪随机数进行假设检验理论检验：从理论上讨论随机数发生器性质统计检验常用近似正态统计量和ⅹ2统计量以下检验方法一般假设用某发生器生成了均匀分布伪随机数r1，r2，...，rn，来检验这些生成的随机数的各种统计量。随机数的产生与模拟1均匀随机数的检验本章目录251、特征量检验随机数的产生与模拟1均匀随机数的检验本章目录262、均匀性检验随机数的产生与模拟1均匀随机数的检验本章目录272、均匀性检验：K-S检验随机数的产生与模拟1均匀随机数的检验本章目录283、独立性检验：自相关系数的检验随机数的产生与模拟1均匀随机数的检验本章目录29均匀随机数检验的SAS程序DATARAN;doj=1to2;DOI=1TO50;X=UNIFORM(0);OUTPUT;END;end;procfreqdata=ran;/*均匀性检验*/tablesi*j/chisq;weightx;run;procnpar1waydata=ranedf;/*k-s检验*/varx;classj;run;Dataran1;doi=1to50;X=UNIFORM(0);y=UNIFORM(0);output;end;proccorr;/*自相关系数检验*/varxy;run;30均匀随机数检验的SAS程序SAS结果输出：1、均匀性检验结果：卡方检验由于Chi-square的P值等于1.0000，大于0.05，所以接受原假设，即随机数在(0,1)这个区间出现的机会均等。31均匀随机数检验的SAS程序SAS结果输出：2、均匀性检验结果：K-S检验由于K-S检验的P值等于0.24，大于0.05，所以接受原假设，即随机数在(0,1)这个区间出现的机会均等。32均匀随机数检验的SAS程序3、独立性检验结果：自相关系数检验由于自相关系数检验的P值等于0.8646，大于0.05，所以接受原假设，即随机数之间是相互独立的。P值原假设33由均匀分布随机数产生非均匀分布随机数的主要方法有：直接抽样法，逆变换法，值序抽样法，合成法和筛选法。随机数的产生与模拟2非均匀随机数的产生本章目录341直接抽样法（反函数法）1）连续分布的直接抽样法随机数的产生与模拟2非均匀随机数的产生本章目录如果随机变量是分布函数的反函数，则)(),1,0(~1FUR)(xF)(~)(1xFRF如果分布有概率密度函数，则)(xF)(xfdxxfFR)()(由均匀随机数直接产生分布随机数的方法称为直接抽样法。}{ir)(xF351直接抽样法（反函数法）1）连续分布的直接抽样法随机数的产生与模拟2非均匀随机数的产生本章目录abadxabdxxfFRa1)()(则其他，，已知,0],[,1)(baxabxfaRab)(即得抽样公式为例：产生上均匀分布的随机数。],[ba解：361直接抽样法（反函数法）1）连续分布的直接抽样法随机数的产生与模拟2非均匀随机数的产生本章目录edxeFRx1)(0因为，，0,0)0(0,)(xxexfx);1ln(1R即得抽样公式为例：产生密度函数为的随机数，其中)(xfRln1为实际应用中抽样公式常解：371直接抽样法（反函数法）2）离散分布的直接抽样法随机数的产生与模拟2非均匀随机数的产生本章目录381直接抽样法的局限性：连续型分布函数反函数没有解析表达式时；另一方面可能有效率更高的产生随机数的方法。随机数的产生与模拟2非均匀随机数的产生本章目录