第4章随机数与随机变量的生成.ppt

生产系统建模与仿真,ModelingandSimulationofProductionSystem,第4章随机数与随机变量的生成,第4章随机数与随机变量的生成,4.1随机数的生成和性质4.2常用的随机数发生器4.3随机数发生器的性能检验4.4随机变量的生成,基本要求,理解几种常用随机数发生器的基本思想和原理理解随机变量的生成方法了解随机数的基本性质了解随机数发生器的性能检验,随机数的生成及其性质,随机数是包括生产系统在内的所有离散事件系统仿真中一个必不可少的基本元素，是整个仿真过程得以运行的基础。对于包括生产系统在内的几乎所有离散事件系统来说，其仿真程序或模型都要求必须具备比较完善的能够产生指定分布的随机变量生成模块或子程序。大多数计算机语言都提供能够产生随机数的子程序、对象或函数。同样，仿真语言也能产生用于事件发生时间和其他随机变量的随机数。,随机数的生成及其性质,随机数定义：指从每一数出现几率相等的一系列数中，靠随机的方法抽取出来的数。随机数生成方法关于随机数生成方法的研究已有很长的历史。最早的随机数是用手工实现的，如抽签、发纸牌、从罐子中摸取带数字的球等方法。其中，有些方法至今仍然还采用。,随机数的生成及其性质,随机数生成方法随着Monte-Carlo方法的出现，20世纪初出现了生成随机数的机械装置和电子装置，如抽奖机等。但是机械装置和电子装置不能重复生成与原来完全相同的随机数，对计算结果无法进行检查，并且生成过程比较复杂。因此，它们未能得到进一步推广。目前，在用计算机生成随机数的方法中，一类使用最广、发展较快的方法是数学方法，其特点是占用内存少、速度快并且便于检查。,随机数的生成及其性质,用数学方法生成随机数是指按照一定的算法（递推公式），来生成“随机”数列（也称随机数流）。这种用算法生成的随机数，只要给定初始的种子值，则以后所生成的“随机”数都是确定的数值，从本质上说这并不具有真正的随机性，因此称这种方法为伪随机数PRN（PseudoRandomNumber）。,随机数的生成及其性质,用数学方法生成随机数所依赖的算法和程序就称为随机数发生器。仿真模拟钟所用到各类随机变量都是以随机数发生器产生的0,1)间均匀分布随机数为基础而得来的。如果精心设计算法，就可以生成具有真正随机数的统计性质的伪随机数。通常，只要所生成的伪随机数能通过一系列统计检验（如独立性、均匀性）就可以把它们作为真正的随机数使用。,随机数的生成及其性质,优良的随机数发生器具有特征1.生成的随机数序列要尽可能地逼近理想的均匀总体随机样本所具有的随机性、均匀性和独立性等统计性质。2.生成的随机数序列必须要有足够长的周期，以满足仿真计算的需要。3.产生随机数的速度快4.所生成的随机数序列必须是完全可重复的5.占有内存小,关于均匀性和独立性：1、如果将区间0,1分为n类或等长的子区间，那么在每个区间的期望观测次数为N/n，其中N为观测的总次数。2、观测值落在某个特定区间的概率与以前的观测值无关。,随机数的生成及其性质,常用的随机数发生器,生成随机数的方法经历了一段漫长的发展过程，下面介绍几种有代表性的算法，主要有：（1）早期的随机数发生器：平方取中随机数发生器、乘积取中随机数发生器、常数乘子法、斐波那契法（Fibonacci）等；（2）线性同余随机数发生器：混合同余随机数发生器、乘同余随机数发生器；,常用的随机数发生器,1.平方取中随机数发生器由冯诺依曼于1940年提出的，基本原理是：将一个N位数平方后，取中间N位数为第一个随机数，然后再平方取中间N位数为第二个随机数，递推公式如下：,常用的随机数发生器,1.平方取中随机数发生器,常用的随机数发生器,1.平方取中随机数发生器,常用的随机数发生器,常用的随机数发生器,例4.1取k=1，x0=76，求由“平方取中法”可以得到如下随机数。解：,（或者直接从5776取中取中间的两个数得77),常用的随机数发生器,常用的随机数发生器,由上例可以看出，由于k取值较小，很快进入退化状态；当k取值较大时，将使退化现象延迟。平方取中法易退化且均匀性差异显著,2.乘积取中法随机数发生器,乘积取中法随机数发生器的其递推公式为：,乘积取中法随机数发生器中要有两个种子值为x0、x1，x0、x1为2k位非负整数，k一般最小取2；,常用的随机数发生器,例4.2取k=2，x0=5167，x1=3729，求由“乘积取中法”可以得到不同的随机数。,解：由于,取,则,取,则,同理,依次取下去，我们可以得到如下表：,常用的随机数发生器,“乘积取中法”的周期比“平方取中法”长，均匀性也有所改善，但主要缺点是最后仍要进入退化状态。,常用的随机数发生器,3.常数乘子发生器,常数乘子发生器是乘积取中法随机数发生器的一种变形，这种方法需要选取一个2k位的非负整数M为常数因子，其递推公式为：,常数乘子发生器中的x0为2k位非负整数，k一般最少取2。,3.常数乘子发生器,常用的随机数发生器,例4.3取k=2，M=3987，x0=7223，求由常数乘子法可以得到不同的随机数。,解,常用的随机数发生器,同理,常用的随机数发生器,同乘积取中法一样，常数乘子法的周期比平方取中法长，均匀性也有所改善，但主要缺点是最后仍要进入退化状态。,依次取下去，我们可以得到如下表：,常用的随机数发生器,4.斐波那契发生器,斐波那契（Fibonacci）法基于Fibonacci序列，其递推公式为：,其中，x0、x1、m为非负整数。,常用的随机数发生器,例4.4取x0=0，x1=1，m=8，求由上述递推公式可以得到不同的随机数。,则,解：,常用的随机数发生器,同理,则,常用的随机数发生器,若继续计算可得，u1=u13=0.125，且从n=13开始，un循环取u1从到u13的值，周期T=12m。此法的优点是计算方便，周期长，缺点是序列中的数重复出现。,依次取下去，我们可以得到如下表：,常用的随机数发生器,（以上四法）历史上常用方法的特点简单、直观、易于实现；数据内部特性难以控制，容易出现退化等问题。,常用的随机数发生器,其中:a,c-常数ui为0，1)间随机数Zi-任意数,Z0为随机数种子m-发生器的模,近似于发生器的周期,因此越大越好.参数m为模数;a为乘子(乘数);c为增量(加数);并且m,a和c均为非负整数。设Z0为给定的种子值，为非负整数,5.目前常用方法线性同余随机数发生器此方法是由莱默尔于1948年提出的，是目前在离散系统仿真中应用最广泛的随机数发生器，基本公式如下：,常用的随机数发生器,线性同余随机数发生器的讨论例Z=A(MODM)则,当A=0A(modM)=0A=1A(modM)=1A=2A(modM)=2:A=M-1A(modM)=M-1A=MA(modM)=0A=M+1A(modM)=1:A=2MA(modM)=0,可见,数列是循环的,有周期,常用的随机数发生器,由上述递推公式得到的xn满足：，从而至多能取m个不同的整数。,称数列xn重复值之间的最短长度为xn的周期，记为T。若T=m，则称为满周期的。下面举例说明线性同余随机数发生器的应用。,例4.5取a=3，c=1，m=8，x0=1，求线性同余法产生随机数。,解：,常用的随机数发生器,同理,常用的随机数发生器,从n=5开始，un循环取u1从到u4的值，周期T=421亿。m可取一个足够大的质数。a和c的选取c与m互质，一般为奇数；a-1可为4整除；则a一定为4的倍数+1。x0的选取因为xi可以是0m之间的任一数，所以x0的选取不是很重要，但是如果取x0=0有时确实会使通式的结果退化。,常用的随机数发生器,常用同余式随机数发生器,计算机随机数发生器产生的随机数是一个具有一定周期的循环数列,从这个意义上说,计算机产生的随机数是一个伪随机数.它必须经过检验才能使用.一般要经过独立性和均匀性检验。,常用的随机数发生器,组合发生器把两个或者更多个独立的随机数发生器(通常是两个不同的线性同余发器)以某种方式组合起来，使得新组合的随机数发生器具有更长的周期和良好的统计性质。最著名的是麦克拉伦(M.D.Maclaren)和马尔萨利亚(G.Marsaglia)于1965年提出的组合同余法,常用的随机数发生器,组合发生器把两个或者更多个独立的随机数发生器(通常是两个不同的线性同余发器)以某种方式组合起来，使得新组合的随机数发生器具有更长的周期和良好的统计性质。最著名的是麦克拉伦(M.D.Maclaren)和马尔萨利亚(G.Marsaglia)于1965年提出的组合同余法,常用的随机数发生器,组合发生器组合同余法采用第一个线性同余发生器LCGl生成k个随机数，一般取k=128，把这k个数按序依次存放在某一向量T中，T=(t1，t2,，tk);并置n=1。采用第二个线性同余发生器LCG2生成一个随机的整数j，满足1jk。令xn=tj，然后再采用第一个发生器LCGI生成一个新的随机数y来替代tj，亦即令tj=y；并置n=n+1。重复一，得到随机数序列xn，此即组合同余发生器生成的数列。若第一个发生器LCG1的模为m，令un=xn/m，则un即为由该组合发生器生成的均匀随机数序列。,常用的随机数发生器,随机数生成特点：有周期性，伪随机应用中，我们并不真正需要“真”的随机数；满足“某些条件”的“伪”随机数已经足够了面临的问题如何验证所得的随机数是否满足使用要求。由于“伪”随机数应该是随机数，又具有均匀、独立的特点，因此要进行以下三个方面的检验：参数检验;均匀性检验;独立性检验。,随机数发生器的性能检验,在实际应用中，随机数发生器的性能检验方法，主要包括有两大类:一类是经验检验方法;另一类是理论检验方法。,随机数发生器的性能检验,45,随机数发生器的性能检验,参数检验,参数检验,随机数发生器的性能检验,参数检验例：给定显著性水平a=0.05，对P54例4-5中得到的随机数序列un的前100项数据(见表4一5)进行参数检验。解:计算样本均值和样本方差分别为,随机数发生器的性能检验,对给定的显著性水平a=0.05,z0.025=1.96。而由式计算可得,随机数发生器的性能检验,所以，在显著性水平a=0.05时，该随机数序列un总体的均值和方差与均匀分布U(0,1)的均值和方差没有显著的差异。,随机数发生器的性能检验,均匀性检验均匀性检验是校验所产生的随机数落在各子区间的频率和理论频率之间的差异是否显著。,随机数发生器的性能检验,均匀性检验,随机数发生器的性能检验,例：给定显著性水平a=0.05,用检验对P54例4-5中得到的随机数序列un的前100项数据(见表4-5)进行均匀性检验。将0，1区间等分成10个子区间(即m=10),显然易见，其相应的理论频数为=n/m=10。对该随机数序列un落在各子区间中的个数(经验频数)进行统计，得到ni(i=1，2,10)分别为13,14,10,7,7、9、9、6,14、5，由此可计算得,随机数发生器的性能检验,随机数发生器的性能检验,练习：使用2检验判断下列数据是否具有均匀分布，取0.05。,使用n=10个等长区间，查表得,均匀性检验,随机数发生器的性能检验,（二）K-S检验例：给定显著性水平a=0.05，用K-S检验方法对P54例4-5中得到的随机数序un的前10项数据(见表4一5)进行均匀性检验。把随机数按照由小到大的顺序进行重新排列，相关的计算数据及结果如表,随机数发生器的性能检验,（二）K-S检验,随机数发生器的性能检验,因此，可认为该随机数序列un的总体分布与均匀分布U(0,1)之间无显著的差异。,独立性检验独立性检验是检查一个序列的随机数是否存在相关性。,随机数发生器的性能检验,随机变量的产生方法,给定了随机数的生成方法，只是构建随机变量的第一步。理论上说，可以通过函数映射关系，即构造函数关系来从0,1)上的均匀分布随机数来构造任意分布的随机变量。因此，如何来构造适当的函数关系就成为了关键。对于不同分布随机变量的要求，有多种生成方法，如逆转换法，结合法等等。,61,随机变量生成的特点,需要:快速生成满足精度要求的随机变量。评价标准:精度：比较确切符合的给定分布省时：快速省内存：常用生成方法逆变换法；合成法；结合法；经验分布随机变量。随机变量生成的基础U(0,1)。,62,随机变量的生成的基本定理,定理：若F(x)是任意随机变量X的CDF(累积分布函数)，则:Y=F(x)IIDU(0,1)，且与X的分布特性无关说明性证明：令Y=F(x)，F(x)是X的CDF；Y也是一个随机变量，令G(y)为Y的CDF。G(y)=P(Y=y)=P(F(x)=y)=P(x=F-1(y)=F(F-1(y)=y(F(x)的单调非降特性)即：G(y)=y；Y为具有均匀分布随机变量的CDF，并在0,1区间，所以Y=F(x)IIDU(0,1)；显然G(y)=y与X的分布特性无关。该定理为利用随机数生成所需随机变量的基础。,生成随机变量有许多种不同的方法，一般采用的具体算法与所要生成的随机变量有关。通常在仿真中要用到各种分布的随机变量，它们一般都是以U0,1）随机数为基础，通过适当的变换生成。这里介绍几种有效的、常用的抽样方法以及相应分布的随机变量的生成。常用的方法主要有：,逆转换法、函数变换法、近似法、合成法、结合法。,随机变量的产生方法,逆转换法是利用拟合分布的分布函数的反函数来产生随机变量.如果已知分布的分布函数，并可以从分布函数求出它的反函数，就可以利用它的反函数来产生已知分布的随机变量。,1.逆转换法（逆变法）,随机变量的产生方法,原理纵坐标表示累计分布值，范围0,1)。利用随机数发生器产生0,1)间均匀分布的随机数，相当于在纵坐标上随机地找到一个点Ui，从这一点利用反函数就可以求得该分布在这一点上的随机变量Xi。,随机变量的产生方法,其步骤如下:1.确定随机过程中该随机变量的拟合分布.2.确定拟合分布的参数及分布函数F(X).3.求出分布函数的反函数Xi=G(Ui)=F-1(Ui).4.用随机数发生器产生0,1)间均匀分布的随机数Ui5.用Xi=G(U)=F-1(Ui)来计算,求得该分布的随机变量Xi.6.返回步骤4，产生下一个随机变量。,随机变量的产生方法,则,这说明对于分布函数是F(x)的随机变量，若要生成其随机数，我们最关心的是下列表达式：,在仿真过程中，要生成规定分布的随机数，通常先要生成0,1)区间上均匀分布的随机数，然后才能按上述方法从所需要的分布函数中生成相应的随机数，因此，0,1)区间上均匀分布的随机数是生成其它分布随机数的基础。,随机变量的产生方法,A连续型随机变量(1)均匀分布Ua,b随机数的生成,均匀分布Ua,b的概率密度函数为,对应的分布函数为,即,由,得,随机变量的产生方法,其算法的步骤为：,（1）产生独立的U0,1)随机数u1,u2,un；（2）令xi=(b-a)ui+a(i=1,2,n)，则x1,x2,xn即为Ua,b随机数。,则由逆变法的生成原理知为一随机变量，其分布函数是F(x)。,令,若随机变量,故F(x)的反函数为:,随机变量的产生方法,(2)指数分布随机数的生成,指数分布的概率密度函数为:,当时，对应的分布函数为：,随机变量的产生方法,令,则由逆变法的生成原理知为一随机变量，其分布函数是F(x)。,若随机变量,故F(x)的反函数为:,即,由,得,随机变量的产生方法,72,指数分布随机数的生成步骤为：,（1）产生独立的U0,1)随机数u1,u2,un；（2）令则x1,x2,xn就是所要求指数分布的随机数。,由于U与1-U均为0,1)区间上的均匀分布的随机变量，因此抽样公式取为:,随机变量的产生方法,随机变量的产生方法,B离散型随机变量,离散分布的反变换法,随机变量的产生方法,B离散型随机变量,随机变量的产生方法,B离散型随机变量例设离散随机变量x的质量函数及累积分布函数如下表所示：,在概率论中，概率质量函数(probabilitymassfunction，简写为pmf)是离散随机变量在各特定取值上的概率。概率质量函数和概率密度函数不同之处在于：概率密度函数是对连续随机变量定义的，本身不是概率，只有对连续随机变量的取值进行积分后才是概率。,随机变量的产生方法,B离散型随机变量解：,随机变量的产生方法,B离散型随机变量,练习,某均匀分布的概率密度函数为：,其中a=2，b=5。用逆转换法生成符合该分布的随机数。,随机变量的产生方法,卷积法,随机变量的产生方法,卷积法例4-12埃尔朗分布。设X的概率密度函数为若Y1，Y2，Ym独立且同服从指数分布E()，令X=Y1+Y2+Ym，则X服从n阶埃尔朗分布。,随机变量的产生方法,卷积法生成随机变量算法：生成独立的均匀分布U(0,1)随机数u1，u2，um。计算u=u1u2.um。令x=-(1/)ln(u)，则x即为服从n阶埃尔朗分布的随机变量。,随机变量的产生方法,组合法,随机变量的产生方法,组合法,重复步骤(1)一(2)，就可以得到所求的分布函数为F(x)的随机变量数列。,随机变量的产生方法,组合法例双指数分布。设随机变量X的概率密度函数为,随机变量的产生方法,组合法可用两个密度函数f1(x)和f2(x)的组合来产生服从密度函数f(x)的随机变量X。,随机变量的产生方法,组合法随机变量生成步骤如下:产生均匀分布U(0,1)的随机数u1及u2。如果u10.5，则生成服从与密度函数f1(x)相应的分布函数的随机变量，根据反变换法，可得X=lnu2。如果u10.5，则生成服从与密度函数f2(x)相应的分布函数的随机变量，同样，有X=lnu2。,随机变量的产生方法,以上方法都有一个共同的特点，即以反变换法为基础，直接面向分布函数，因而又称为直接法。当反变换法难于使用(例如随机变量的分布函数不存在封闭形式等)或者效率不高时，有时就需要使用非直接