随机数的产生与模拟.ppt

1,第三章 随机数的产生与模拟目录,随机数的产生与模拟3.1均匀随机数的产生 线性同余法（LCG）的递推公式 反馈位移寄存器法（FSR）组合发生器3.2非均匀随机数的产生3.3 Monte Carlo方法在解确定性问题中的应用 计算定积分 随机投点法 平均值估计法 重要抽样法 分层抽样法 3.3.2 计算多重积分 3.3.2.1 随机投点法 3.3.2.2 平均值估计法 应用实例3.4 随机模拟方法在随机服务系统中的应用3.5 随机模拟方法在理论研究中的应用,返回,作业,思考题,2,随机数的产生与模拟,用随机模拟方法解决实际问题时，首先要解决的是随机数的产生方法，或称随机变量的抽样方法。,本章目录,3,随机数的产生与模拟,伪随机数：在计算机上用数学方法产生均匀随机数是指按照一定的计算方法而产生的数列，它们具有类似于均匀随机变量的独立抽样序列的性质，这些数既然是依照确定算法产生的，便不可能是真正的随机数，因此常把用数学方法产生的随机数称为伪随机数。,本章目录,4,随机数的产生与模拟,均匀分布随机数：,本章目录,5,随机数的产生与模拟,均匀分布随机数：,该定理说明了任意分布的随机数均可由均匀分布 的随机数变换得到。常简称 的随机数为均匀分布随机数。,本章目录,6,随机数的产生与模拟1 均匀随机数的产生,均匀随机数的产生：主要有线性同余法（LCG），组合同余法，反馈位移寄存器方法等,本章目录,7,均匀随机数的产生：,随机数的产生与模拟1 均匀随机数的产生,本章目录,线性同余法（LCG）的递推公式为：,8,均匀随机数的产生：,随机数的产生与模拟1 均匀随机数的产生,本章目录,当，上式称为混合同余发生器，当时，称为乘同余发生器，此时当模为素数时，称它为素数模乘同余发生器。,9,两个常用的混合式发生器：,随机数的产生与模拟1 均匀随机数的产生,本章目录,10,常用的素数模乘同余发生器：,随机数的产生与模拟1 均匀随机数的产生,本章目录,11,常用的素数模乘同余发生器：,随机数的产生与模拟1 均匀随机数的产生,本章目录,12,反馈位移寄存器法（FSR）：,对寄存器中的二进制数码 作递推运算，其中 是给定的正整数，为给定的常数。取数列 中连续的 位构成一个 位二进制整数，一直下去，一般地有 令 则 即为FSR方法产生的均匀随机数列。,随机数的产生与模拟1 均匀随机数的产生,本章目录,13,组合发生器：先用一个随机数发生器产生的随机数列为基础，再用另一个发生器对随机数列进行重新排列得到的新数列作为实际使用的随机数。这种把多个独立的发生器以某种方式组合在一起作为实际使用的随机数，希望能够比任何一个单独的随机数发生器得到周期长、统计性质更优的随机数，即组合发生器。,随机数的产生与模拟1 均匀随机数的产生,本章目录,14,组合发生器：,随机数的产生与模拟1 均匀随机数的产生,本章目录,Maclaren 和 Marsaglia在1965年提出的著名的组合发生器是组合同余发生器,该算法的具体步骤如下：,15,组合发生器：,1用第一个LCG产生 个随机数，一般取。这 个随机数被顺序地存放在矢量 中。置;,2 用第二个LCG产生一个随机整数,要求;,3 令，然后再用第一个LCG产生一个随机数,令；置;,4 重复23，得随机数列，即为组合同余发生器产生的数列。若第一个LCG的模为，令，则 为均匀随机数,随机数的产生与模拟1 均匀随机数的产生,本章目录,16,由均匀分布随机数产生非均匀分布随机数的主要方法有：逆变换法，合成法和筛选法。,随机数的产生与模拟2非均匀随机数的产生,本章目录,17,1 逆变换法：,随机数的产生与模拟2非均匀随机数的产生,对任意分布函数,要产生服从该分布的随机数，由定理知其抽样步骤为：（1）由 抽取;（2）计算,本章目录,18,1 逆变换法：,随机数的产生与模拟2非均匀随机数的产生,本章目录,例1 已知(柯西分布)，试给出其抽样方法。,19,1 逆变换法：,随机数的产生与模拟2非均匀随机数的产生,解：设,则,因此其抽样步骤如下：（1）由 抽取;（2）计算,本章目录,20,1 逆变换法：其SAS程序为（产生100个服从柯西分布的随机数）：data ex1;seed=678;do I=1 to 100;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服从,本章目录,22,2 合成法：,随机数的产生与模拟2非均匀随机数的产生,当 为离散形式时，即,其中 是密度函数，其抽样过程如下：1 产生一个正的随机整数，使得，2 产生分布为 的随机数。,本章目录,23,2 合成法：,随机数的产生与模拟2非均匀随机数的产生,本章目录,24,2 合成法：,随机数的产生与模拟2非均匀随机数的产生,解：首先将 进行分解,即，其中 其抽样框图为,本章目录,25,2 合成法：,随机数的产生与模拟2非均匀随机数的产生,本章目录,26,2 合成法：其SAS抽样程序如下（假若产生100个随机数,）：data ex2;seed=789;a=0.3;do I=1 to 100;r=ranuni(seed);r3=ranuni(seed);if r1=a then do;u=ranuni(seed);x=u;end;else do;u=ranuni(seed);v=ranuni(seed);x=max(u,v);end;output;end;run;,随机数的产生与模拟2非均匀随机数的产生,本章目录,27,3 筛选抽样法：,随机数的产生与模拟2非均匀随机数的产生,假设我们要从 抽样，如果可将 表示成，其中 是一个密度函数且易于抽样，而，是常数，,本章目录,28,3 筛选抽样法：,随机数的产生与模拟2非均匀随机数的产生,X的抽样可如下进行：1由 抽取，由 抽取2如果，则;否则，转1则X的密度函数为,本章目录,29,3 筛选抽样法：,随机数的产生与模拟2非均匀随机数的产生,本章目录,30,3 筛选抽样法：,随机数的产生与模拟2非均匀随机数的产生,解：因为：，即：则抽样框图如下：,本章目录,31,3 筛选抽样法：,随机数的产生与模拟2非均匀随机数的产生,本章目录,32,3 筛选抽样法：其SAS程序如下：data ex3;seed=789;do I=1 to 100;r1=ranuni(seed);r2=ranuni(seed);if r1=r2*3 then do;x=r2;output;end;end;run;,随机数的产生与模拟2非均匀随机数的产生,本章目录,33,蒙特卡罗（Monte Carlo）方法（即随机模拟方法）求解实际问题的基本步骤包括：1 建模：对所求的问题构造一个简单而又便于实现的概率统计模型，使所求的解恰好是所建模型的参数或有关的特征量。2 改进模型：根据概率统计模型的特点和计算实践的需要，尽量改进模型，以便减少误差和降低成本，提高计算效率。3 模拟试验4 求解：对模拟结果进行统计处理，给出所求问题的近似解。,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,本章目录,34,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,计算定积分,（1）随机投点法,赋初值:试验次数n=0,成功次数m=0;规定投点试验的总次数N;产生两个相互独立的均匀随机数 置n=n+1;判断nN是否成立,若成立转,否则停止试验,转;判断条件 是否成立,若成立置m=m+1,然后转,否则转;计算m/N,则,本章目录,35,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,计算定积分,（1）随机投点法,本章目录,36,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,计算定积分,本章目录,37,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,计算定积分,本章目录,38,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,计算定积分,(4)分层抽样法,分层抽样法的计算步骤如下：,本章目录,39,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,(1)随机投点法,多重积分随机投点法计算步骤为:,计算多重定积分,本章目录,40,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,(1)随机投点法,计算多重定积分,本章目录,41,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,(2)平均值估计法,计算多重定积分,多重积分的平均值法计算步骤为,本章目录,42,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,(2)平均值估计法,计算多重定积分,本章目录,43,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,计算多重定积分,用蒙特卡罗方法计算积分值时，误差的阶数为,它与多重积分的重数k无关，而用其他数值方法计算多重积分时，其误差与重数k是有关的，可见当k3时，使用蒙特卡罗方法计算多重积分将显现出很大的优越性,本章目录,44,应用实例,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,例4：用上述四种方法计算,(1)随机投点法,data E1;Do k=1 to 1000;m=0;Do h=1 to 1000;a=ranuni(32789);b=ranuni(32789);if b=(exp(a)-1)/(exp(1)-1)then m=m+1;end;I1=m/1000*(exp(1)-1)+1;output;E1=abs(I1-(exp(1)-1);end;run;proc means data=e1 Mean Var;var I1;run;,本章目录,45,应用实例,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,例4：用上述四种方法计算,(2)平均值估计法,data E2;Do k=1 to 1000;s=0;Do i=1 to 1000;x=ranuni(32789);fx=exp(x);s=s+fx;end;I2=s/1000;output;E2=abs(I2-(exp(1)-1);end;run;proc means data=e2 Mean Var;var I2;run;,本章目录,46,应用实例,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,例4：用上述四种方法计算,(3)重要抽样法,data E3;do k=1 to 1000;s=0;Do i=1 to 1000;r=ranuni(32789);x=(3*r+1)*(1/2)-1;s=s+exp(x)/(1+x);end;I3=3/(2*1000)*s;output;E3=abs(I3-(exp(1)-1);End;run;proc means data=e3 Mean Var;var I3;run;,本章目录,47,应用实例,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,例4：用上述四种方法计算,(4)分层抽样法,data E4;Do k=1 to 1000;s1=0;s2=0;Do i=1 to 400;ri=ranuni(32789);r1=0.5*ri;f1=exp(r1);s1=s1+f1;end;Do j=1 to 600;rj=ranuni(32789);r2=0.5+0.5*rj;f2=exp(r2);s2=s2+f2;end;I4=s1*(1/800)+s2*(1/1200);output;E4=abs(I4-(exp(1)-1);end;run;proc means data=e4 Mean Var;var I4;run;,本章目录,48,应用实例,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,例4：用上述四种方法计算,结果,49,应用实例,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,(1)随机投点法,例5：计算二重积分,Data e5;Do k=1 to 1000;m=0;h=0;Do h=1 to 1000;a1=ranuni(32789);a2=ranuni(32789);b=ranuni(32789);if b=(exp(a1+a2)-1)/(exp(2)-1)then m=m+1;end;I5=(exp(2)-1)*(m/1000)+1;output;E5=abs(I5-(exp(1)-1)*2);end;run;proc means data=e5 Mean Var;var I5;run;,本章目录,50,应用实例,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,(2)平均值估计法,例5：计算二重积分,data E6;Do k=1 to 1000;m=0;s=0;Do h=1 to 1000;a1=ranuni(32789);a2=ranuni(32789);if 0=a1=1 and 0=a2=1 then do;fx=exp(a1)*exp(a2);s=s+fx;end;end;I6=s/1000;output;E6=abs(I6-(exp(1)-1)*2);end;run;proc means data=e6 Mean Var;var I6;run;,本章目录,51,应用实例,随机数的产生与模拟3 Monte Carlo方法在解确定性问题中的应用,例5：计算二重积分,对于多元积分也有Var(I6)Var(I5),本章目录,52,随机服务系统研究的对象是服务系统，如到理发店理发，理发师与顾客构成了一个服务系统；到商店买东西，售货员与顾客就构成了一个服务系统。,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,本章目录,53,随机服务系统一般具有三要素，顾客、排队规则和窗口,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,本章目录,54,1 顾客 顾客到达排队系统的过程也称为输入过程。顾客的来源和到达排队系统的情况是多种多样的。顾客来源可能是有限的，也可能是无限的。顾客到达方式可能是连续的，也可能离散；可能是一个一个的，也可能是成批的或大量的；顾客相继到达的间隔时间可以是确定型的，也可以是随机型的；顾客的到达可以相互独立，也可以是相互关联的。如果描述顾客相继到达的间隔时间分布和所含参数（如期望值、方差等）都与时间无关，则称为平稳（Stationary）输入过程，否则称之为非平稳输入过程。,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,本章目录,55,2 排队规则 常用的规则有：损失制（Lossing System）：顾客到达时，若所有服务台均被占，该顾客就自动消失。如通常使用的损失制电话系统。等待制（Wating System）：顾客到达时，若所有服务台均被占，他们就排成队伍，等待服务。服务次序可采用以下各种规则：先到先服务：即按到达的次序接受服务。后到先服务：即后到的顾客、先接受服务。如在有的流水装配线上，后到的零件先装配；在通讯系统中，最后到达的信息一般最有价值。随机的服务：当服务机构得空时，在等待顾客中、随机地选取一名进行服务，也即每一等待的顾客被选到的概率相同。优先权服务：如医院对重患或急诊患者予以优先治疗、重要电话先接通等。多个服务台：当顾客到达时可以按如下规则在每个服务台前排成一个队：第1，n+1,2n+1,个顾客排入第一队；第2，n+2,2n+2，个顾客排入第二队等等。或者排成一个公共的队，当一个服务台得空时，队首顾客进入服务。队列数目 排队队列有单列和多列之分。顾客排队后由于等待时间过长而中途离队，但也有不允许中途离队的情况，这种情况必须坚持到服务完为止。在多队列排队情况下，各队列之间的顾客有的可以相互转移，有的不允许转移。,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,本章目录,56,3 窗口：服务台的个数可以是一个或几个，可以是单个服务，也可以是成批服务。,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,本章目录,57,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,例6 得意系统可靠性估计。设系统由顺次连接的两个元件组成。两个元件中，任何一个元件发生故障系统就停止工作。第一个元件有两个组成部分A,B（它们并联）。第二个元件有一个部件C组成。试用Monte Carlo法求:1 估计系统工作的概率，已知组成部件的工作概率分别为：2 绝对误差，其中 为系统的可靠性。可用分析的方法获得。进行50次试验。,本章目录,58,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,59,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,其输出结果为：OBS P PDIFF 1 0.58 0.002,本章目录,60,例7 某服务系统有三个服务员，输入流为泊松流，服务时间为指数分布。每个顾客服务时间等于0.5分钟。求在T=4分钟内被服务顾客的数学期望。,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,解：设 表示第 个顾客到达的时刻，表示第 个顾客到达的时间间隔。则有。其SAS程序如下：,本章目录,61,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,data ex7;s1=0;s2=0;s3=0;T=0;Do until(T4);R=ranuni(-1);P=0.2*(-log(R);T=T+p;Ss1=s1;ss2=s2;ss3=s3;If(Tss1)then do;s1=T+0.5;end;If(Tss3)then do;s3=T+0.5;end;Output;End;Run;Proc means data=ex7;Var d;Output out=result sum=dsum;Run;Proc print data=result;Run;,本章目录,62,随机数的产生与模拟4 随机模拟方法在随机服务系统中的应用,此过程共进行6次模拟，可得其平均值为=16，即在4分钟内平均服务了16个顾客。,本章目录,63,随机模拟方法不仅在求解确定性和随机性复杂系统的问题，它在理论研究方面也大为可有。比如有些问题从理论上已经得出了圆满的结论，但因没有经过实践验证比较，暂时没有被应用。这时若使用随机模拟方法先反复加以比较验证，再用于实践中就更可靠了。还有些问题，从理论上证明很困难，而科学家从其他方面的知识及经验，对所研究问题有某些猜想，这时随机模拟方法就是一个有效可行的方法。下面仅举例说明用随机模拟的方法在比较系统聚类方法上的应用,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,本章目录,64,例8,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,假设数据来自 和 的总体，用SAS来计算，比较系统聚类法的八种常用方法在分类时之间的分类效果的好坏。,本章目录,65,例8 解：基本思想为：,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,本章目录,66,例8 解：基本思想为：,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,2.用八种常用的系统聚类方法对容量为2n个样品的数据进行聚类，计算各种聚类方法的错分率(即判错个数所占的比例)(j=1,2,8);,本章目录,67,例8 解：基本思想为：,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,3.重复以上两步N次，得(j=1,8;i=1,N),计算平均错分率：(j=1,2,8)。,本章目录,68,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,其SAS程序为(以average为例)：,%macro createdata(mdata=,leixing=,mv1=,mv2=,mvar1=,mvar2=,mvar3=);data,本章目录,69,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,其SAS程序为(以average为例)：,%macro datacluster(mdata=,method=);data,本章目录,70,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,其SAS程序为(以average为例)：,%macro analyze;%do i=1%to 50;%createdata(mdata=a,leixing=1,mv1=0,mv2=0,mvar1=1,mvar2=0,mvar3=1);%createdata(mdata=b,leixing=2,mv1=3,mv2=3,mvar1=1,mvar2=0,mvar3=1);%datacluster(mdata=ab,method=average);%end;%mend analyze;%analyze;data rr;set r_result;if errorsum25 then errorsum=50-errorsum;errorratio=errorsum/50;run;/*计算错分率*/proc sort data=rr;by fenlei;run;proc means data=rr noprint;output out=r mean=err_ratio;var errorratio;by fenlei;run;/*计算平均错分率*/proc print data=r;var fenlei err_ratio;title 总错判率:;run;,本章目录,71,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,注意：在运行该SAS程序进行计算时，只需将“method=average”中的“average”用其它七种聚类方法进行替换即可得到相应聚类方法的分类结果。,本章目录,72,八种不同聚类方法下的平均错判率，结果见下表。,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,结果表明，若数据分类比较清楚，则八种聚类方法的效果都是好的。,本章目录,73,续例8,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,若假设数据来自总体 和,相应的计算结果如下：,本章目录,74,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,相应的计算结果如右：,这组数据有些混杂，从以上结果来看，除了最短距离法的分类效果好外，其余七种聚类方法的分类结果都不理想，错分率在20%左右,本章目录,75,续例8,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,再假设数据来自总体 和,本章目录,76,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,相应的计算结果如右：,这组数据介于上面两组数据之间，从结果来看，八种聚类方法都对来自第一个总体的数据的判断不好，而对第二个总体的数据判断得比较好。,本章目录,77,当然，还可进一步提出不同的刻划分类效果的统计量，再通过模拟的方法确定出哪一个统计量能更好地刻划分类效果，以后就可用此统计量作为评价标准。,随机数的产生与模拟5 随机模拟方法在理论研究中的应用,本章目录,返回,