第3章随机数的产生与模拟

1第三章随机数的产生与模拟目录随机数的产生与模拟§3.1均匀随机数的产生3.1.1线性同余法（LCG）的递推公式3.1.2反馈位移寄存器法（FSR）3.1.3组合发生器§3.2非均匀随机数的产生§3.3MonteCarlo方法在解确定性问题中的应用3.3.1计算定积分3.3.1.1随机投点法3.3.1.2平均值估计法3.3.1.3重要抽样法3.3.1.4分层抽样法3.3.2计算多重积分3.3.2.1随机投点法3.3.2.2平均值估计法3.3.3应用实例§3.4随机模拟方法在随机服务系统中的应用§3.5随机模拟方法在理论研究中的应用返回2随机数的产生与模拟用随机模拟方法解决实际问题时，首先要解决的是随机数的产生方法，或称随机变量的抽样方法。本章目录3随机数的产生与模拟伪随机数：在计算机上用数学方法产生均匀随机数是指按照一定的计算方法而产生的数列，它们具有类似于均匀随机变量的独立抽样序列的性质，这些数既然是依照确定算法产生的，便不可能是真正的随机数，因此常把用数学方法产生的随机数称为伪随机数。本章目录4随机数的产生与模拟均匀分布随机数：定理：设)(xF是连续且严格单调上升的分布函数，它的反函数存在，且记为)(1xF，1、若随机变量的分布函数为)(xF，则)1,0(~)(UF;2、若随机变量)1,0(~UR,则)(1RF的分布函数为)(xF本章目录5随机数的产生与模拟均匀分布随机数：该定理说明了任意分布的随机数均可由均匀分布的随机数变换得到。常简称的随机数为均匀分布随机数。)1,0(U)1,0(U本章目录6随机数的产生与模拟1均匀随机数的产生均匀随机数的产生：主要有线性同余法（LCG），组合同余法，反馈位移寄存器方法等本章目录7均匀随机数的产生：01))(mod(值xMxrMcaxxnnnn初,...2,1n随机数的产生与模拟1均匀随机数的产生本章目录线性同余法（LCG）的递推公式为：8均匀随机数的产生：随机数的产生与模拟1均匀随机数的产生本章目录0c0c当，上式称为混合同余发生器，当时，称为乘同余发生器，此时当模为素数时，称它为素数模乘同余发生器。9两个常用的混合式发生器：350353511522)2)(mod15(xxrxxnnnn3103131122)2)(mod453806245314159269(xxrxxnnnn,...2,1n随机数的产生与模拟1均匀随机数的产生本章目录10常用的素数模乘同余发生器：312)312()312(mod312535035351xxrxxnnnn,...2,1n随机数的产生与模拟1均匀随机数的产生本章目录11常用的素数模乘同余发生器：,...2,1n12)12()12(mod31031311xxrxaxnnnin)4,3,2,1(i168071a3972040942a7642611233a6303600164a随机数的产生与模拟1均匀随机数的产生本章目录12反馈位移寄存器法（FSR）：对寄存器中的二进制数码作递推运算，其中是给定的正整数，为给定的常数。取数列中连续的位构成一个位二进制整数，一直下去，一般地有令则即为FSR方法产生的均匀随机数列。)2)(mod(1111kpkppkpkccckp)1,...,2,1(10,1piorccipnL22)1(1)1(),,,(nLLnLnnx,...2,1nLnnxr2,...2,1nnrL随机数的产生与模拟1均匀随机数的产生本章目录13组合发生器：先用一个随机数发生器产生的随机数列为基础，再用另一个发生器对随机数列进行重新排列得到的新数列作为实际使用的随机数。这种把多个独立的发生器以某种方式组合在一起作为实际使用的随机数，希望能够比任何一个单独的随机数发生器得到周期长、统计性质更优的随机数，即组合发生器。随机数的产生与模拟1均匀随机数的产生本章目录14组合发生器：随机数的产生与模拟1均匀随机数的产生本章目录Maclaren和Marsaglia在1965年提出的著名的组合发生器是组合同余发生器,该算法的具体步骤如下：15组合发生器：1用第一个LCG产生个随机数，一般取。这个随机数被顺序地存放在矢量中。置;128kk),,,(21ktttT1nk2用第二个LCG产生一个随机整数,要求;jkj13令，然后再用第一个LCG产生一个随机数,令；置;jntxyytj1nn4重复2~3，得随机数列，即为组合同余发生器产生的数列。若第一个LCG的模为，令，则为均匀随机数nxMMxrnnnr随机数的产生与模拟1均匀随机数的产生本章目录16由均匀分布随机数产生非均匀分布随机数的主要方法有：逆变换法，合成法和筛选法。随机数的产生与模拟2非均匀随机数的产生本章目录171逆变换法：随机数的产生与模拟2非均匀随机数的产生对任意分布函数,要产生服从该分布的随机数，由定理知其抽样步骤为：（1）由抽取;（2）计算)(xF)1,0(UR)(1RF本章目录181逆变换法：随机数的产生与模拟2非均匀随机数的产生本章目录)1(1)(~2xxp例1已知(柯西分布)，试给出其抽样方法。191逆变换法：随机数的产生与模拟2非均匀随机数的产生解：设,则,因此其抽样步骤如下：（1）由抽取;（2）计算)1,0(~UR)(~)(tan21xpR)1,0(UR)(tan21R本章目录201逆变换法：其SAS程序为（产生100个服从柯西分布的随机数）：dataex1;seed=678;doI=1to100;r=ranuni(seed);x=tan(3.14159*(r-0.5));output;end;run;随机数的产生与模拟2非均匀随机数的产生本章目录212合成法：随机数的产生与模拟2非均匀随机数的产生其想法是：如果X的密度难于抽样，而X关于Y的条件密度以及Y的密度函数均易于抽样，则X的随机数可如下产生：由Y的密度抽取y由条件密度抽取x则X服从)(yg)|(yxp)(xp)(yg)|(yxp)(xp本章目录222合成法：随机数的产生与模拟2非均匀随机数的产生当为离散形式时，即,其中是密度函数，其抽样过程如下：1产生一个正的随机整数，使得，2产生分布为的随机数。)(ygniiixpxp1)()(1,01niii)(xpiJjpjJP}{nj,...,2,1)(xpj本章目录232合成法：随机数的产生与模拟2非均匀随机数的产生本章目录设时梯形分布的密度函数为，试用合成法产生其随机数。10a其他,0]1,0[,)1(2)(xxaaxp例2242合成法：随机数的产生与模拟2非均匀随机数的产生解：首先将进行分解,即，其中其抽样框图为)(xp)()1()()(21xpaxapxp其他0]1,0[,1)(1xxp其他,0]1,0[,2)(2xxxp本章目录252合成法：随机数的产生与模拟2非均匀随机数的产生产生产生令产生令输出YN)1,0(~URaR)1,0(~UUU)1,0(~,UVU),max(VU本章目录262合成法：其SAS抽样程序如下（假若产生100个随机数,）：dataex2;seed=789;a=0.3;doI=1to100;r=ranuni(seed);r3=ranuni(seed);ifr1=athendo;u=ranuni(seed);x=u;end;elsedo;u=ranuni(seed);v=ranuni(seed);x=max(u,v);end;output;end;run;随机数的产生与模拟2非均匀随机数的产生本章目录273筛选抽样法：随机数的产生与模拟2非均匀随机数的产生假设我们要从抽样，如果可将表示成，其中是一个密度函数且易于抽样，而，是常数，)(xp)()()(xgxhcxp)(h1)(0xg1c)(xp本章目录283筛选抽样法：随机数的产生与模拟2非均匀随机数的产生X的抽样可如下进行：1由抽取，由抽取2如果，则;否则，转1则X的密度函数为)1,0(UR)(yhy)(ygRyx)(xp本章目录293筛选抽样法：随机数的产生与模拟2非均匀随机数的产生本章目录设，试用筛选法抽取其随机数。34)(xxp10x例3303筛选抽样法：随机数的产生与模拟2非均匀随机数的产生解：因为：，即：则抽样框图如下：314)(xxp3)(,1)(,4xxgxhc本章目录313筛选抽样法：随机数的产生与模拟2非均匀随机数的产生独立产生令NY)1,0(~,21Urr321rr2rx本章目录323筛选抽样法：其SAS程序如下：dataex3;seed=789;doI=1to100;r1=ranuni(seed);r2=ranuni(seed);ifr1=r2**3thendo;x=r2;output;end;end;run;随机数的产生与模拟2非均匀随机数的产生本章目录33蒙特卡罗（MonteCarlo）方法（即随机模拟方法）求解实际问题的基本步骤包括：1建模：对所求的问题构造一个简单而又便于实现的概率统计模型，使所求的解恰好是所建模型的参数或有关的特征量。2改进模型：根据概率统计模型的特点和计算实践的需要，尽量改进模型，以便减少误差和降低成本，提高计算效率。3模拟试验4求解：对模拟结果进行统计处理，给出所求问题的近似解。随机数的产生与模拟3MonteCarlo方法在解确定性问题中的应用本章目录34随机数的产生与模拟3MonteCarlo方法在解确定性问题中的应用10)(dxxfI计算定积分（1）随机投点法①赋初值:试验次数n=0,成功次数m=0;规定投点试验的总次数N;②产生两个相互独立的均匀随机数置n=n+1;③判断n≤N是否成立,若成立转④,否则停止试验,转⑤;④判断条件是否成立,若成立置m=m+1,然后转②,否则转②;⑤计算m/N,则)1,0(~,U)(fNm/1本章目录35随机数的产生与模拟3MonteCarlo方法在解确定性问题中的应用10)(dxxfI计算定积分（1）随机投点法对一般区间[a,b]上定积分I=badxxf)(的计算,只需做线性变换,即可化成[0,1]上的定积分。设)(xf在],[ba上有界:dxfc)(,为了化一般区间上的积分为[0,1]区间上的积分,且被积函数值在[0,1]之间,令auabx)(,则有：100)()()(abcduuSdxxfba其中cdcuabafu]))(([)(,))((0cdabS.本章目录36随机数的产生与模拟3MonteCarlo方法在解确定性问题中的应用10)(dxxfI计算定积分(2)平均值估计法平均值估计法的计算步骤：①产生[0,1]区间的均匀随机数②计算③令=,则为积分值的近似解.Nrrr,,,21)(irf),...2,1(Ni2NiirfN1)(12I本章目录37随机数的产生与模拟3MonteCarlo方法在解确定性问题中的应用10)(dxxfI计算定积分(3)重要抽样法重要抽样法的计算步骤为：①产生均匀随机数②用直接抽样法产生随机数,即由计算则③计算=,则是的估计量.ir),...2,1(Ni)(xgix)(~xgxiNiiiNiixgxfNzN11)()(113Iir3本章目录38随机数的产生与模拟3MonteCarlo方法在解确定性问题中的应用10)(dxxfI计算定积分(4)分层抽样法分层抽样法的计算步骤如下：①将积分区间[0,1]用分点ai(i=0,1,……,m)分成m个互不相交的子区间，其长度分别为：1iiiaa