《信息与通信系统仿真》课件9 随机变量的产生

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,别志松,随机变量的产生,2,主要内容,随机变量（过程）产生在蒙特卡洛仿真中的重要性,均匀分布随机变量的产生,其他分布随机变量产生的一般方法,高斯分布随机变量的产生,蒙特卡洛仿真的三个过程,构造或描述概率过程,从已知分布进行采样，即随机试验,建立估计量,3,蒙特卡洛仿真精度的决定性因素,仿真试验次数,高斯近似、泊松近似,从已知分布采样的准确性！,可能造成有偏估计；,严重影响仿真精度。,4,计算机仿真中的随机采样,计算机仿真中的蒙特卡洛方法要求在计算机上产生满足一定概率分布的随机数。,计算机只能按人的意志按照一定的程序产生数据，因此必然不可能是纯随机的。,只可能是伪随机的。,满足一定条件的伪随机采样能够完成仿真评估目标。,5,早期的随机数产生器,在,发展,过程的早期，随机数是通过人为技术产生的，如抛硬币，掷骰子，玩纸牌和赌盘等。,后来出现了一些物理设备，如噪音二极管，盖格计数器，这些设备与电脑相连来产生随机数。当时普遍认为只有机械或电子设备才能产生真正的随机序列。,机械设备仍然广泛运用于赌博和与其类似的活动中,。,传统随机数产生方法的问题,对于普遍应用来说，机械学方法太慢；,产生的序列不能重现；,机械学方法产生的数据具有主观性和非独立性。,尽管一些先进的物理方法能很快产生随机数并能通过绝大多数的统计测试，（例如基于热噪声的设备），但它们主要的缺陷是缺乏可重复性。,现代随机数产生方法,现在多数的随机数据发生器都不基于物理设备,，而是,在计算机上,通过对数的操作实现,。,它,们运行快，要求的存储空间小,；,能很容易的重现给定的随机数。,一个好的随机数产生器,几乎,拥有着真实随机序列的所有重要的统计特性,但,这些序列是由确定性算法产生的。,由于这个原因，这类发生器所产生的序列的随机性常常称为伪随机。,计算机工具中的伪随机变量产生,C,语言库函数中提供了,rand,函数产生从,0,到,RAND_MAX,中的任意整数；,在此基础上可以产生服从其他分布的随机变量。,但是在一些情况下，该随机数生成函数不能满足仿真要求。,Matlab,提供了,rand,、,randn,、,random,等一系列随机数生成函数。,大部分高级语言都提供了随机数生成的有关函数。,但是仍有必要初步了解一些随机变量产生的知识。,9,10,主要内容,随机变量（过程）产生在蒙特卡洛仿真中的重要性,均匀分布随机变量的产生,由均匀分布产生其他分布随机变量的方法,通信系统仿真中的常用随机变量的产生,均匀分布随机数产生的重要性,均匀分布的随机数在蒙特卡洛仿真中具有非常重要的地位，是从已知随机分布采样的基础。,其他分布随机数的产生以均匀分布随机数为基础。,均匀分布随机数产生方法的优劣决定了蒙特卡洛仿真从已知分布采样的可信度，其中产生,0,1,区间上均匀分布的随机变量是生成其他随机变量的前提。,在不少文献中所说的随机数发生器（,RNG,）就特指产生,0,1,区间上均匀分布随机变量的算法。,11,均匀分布随机数产生方法种类,线性同余方法及其变种,乘同余,混合同余,组合,移位寄存器法及其变种,单变量平方移位法,加法,-,进位法和减法,-,借位法,Mersenne Twister,法,12,13,线性同余发生器,采用下述公式产生随机数：,其中 是第,i,个随机数，,a,为乘子，,b,为增量，,m,为模数， 为随机数源或种子，均为非负整数,令 ，则可得到,0,1),区间上的随机数,线性同余发生器,若,a!=0, b!=0,，称为混合同余法,若,a=1,，,b!=0,，称为加同余法,若,a!=0, b=0,，称为乘同余法,研究表明，乘同余法优于加同余法，而混合同余法与简单的乘同余法相比并无显著优点。因此，乘同余法更常用,线性同余法的周期性,这种方法产生的随机数实际上是伪随机数：采用递推算法，后面产生的数会重复前面的数，即实际上是有限的周期数列。无论,Zi,取何值，其循环顺序相同。,随机数循环一次称为发生器的一个周期,(P),。,对混合同余法，若,P=m,，则该发生器具有满周期,对乘同余法，由于,xi,不能取,0,，因此满周期为,m-1.,由于蒙特卡洛仿真通常需要较大的仿真量，如果随机数发生器在仿真时长内发生重复，则会对仿真结果的可信度造成较大影响，因此设计乘同余或混合同余发生器时总希望是满周期的,。,混合同余法满周期条件,发生器的周期是受,a,b,m,共同控制的。,当且仅当以下特性满足时，混合同余发生器达到最大周期,：,(1)b,和,m,互素,(2)a-1,可以被,m,的任意素因子整除,(3),如果,m,是,4,的倍数，则,a-1,也必须是,4,的倍数,例：一个周期为,m=5000,的满周期混合同余发生器,我们可以设计一个周期为,m=5000,的混合同余发生器。下面简单介绍如何根据,m,选取,C,和,D,的值。,选取,D,值要求与,m,互素，可以选择除了,2,和,5,之外其他素数的乘积。比如：,17,例：一个周期为,m=5000,的满周期混合同余发生器,为了让该发生器满周期，,C-1,应当可以被,m,的任意素因子整除，并且应当能被,4,整除，可取,递推公式：,18,例：一个周期为,m=5000,的满周期混合同余发生器,19,%full period LCG,a=input(enter multiplier a: );,b=input(enter increment b: );,m=input(enter modulus m: );,seed=input(enter seed: );,n=1;,ix=rem(seed*a+b),m);,while (ix=seed)&(nm,disp(caught in a loop);,else,text=the period is ,num2str(n,15),.;,end,乘同余满周期条件,乘同余法满周期的条件,m是素数,C,是,mod(m),的本原元,20,乘同余法满周期条件,其中,C,是,mod(m),的本原元当且仅当满足以下条件成立：,且,k,为任意整数,21,线性同余法,并不是所有具有满周期的线性同余发生器都是好的随机数发生器,；,良好的随机数发生器必须通过各种随机数测试以满足均匀性、独立性、快速性、计算机字长效应的要求,；,因此，线性同余发生器中的常数选择是一个十分复杂的问题。,22,最小标准,随机数发生器测试比较复杂，不可能任意设计并测试。,因此有人提出多种最小标准，最小标准要求：,满周期,通过一组随机性统计测试,易于从一台计算机移植到另一台计算机,23,Lewis,，,Goosman,和,Miller,最小标准,m=2,31,-1,24,复合线性同余法,25,在希望获得一些更长周期（并不一定是满周期）的随机数发生器时，一个行之有效的思想就是把具有较短周期的不同随机数发生器的输出线性合并。两个周期分别为,N1,和,N2,的随机数发生器合并之后的输出随机数周期为,：,当,N1,和,N2,互素时，,N=N1*N2,一种复合线性同余发生器,周期,线性同余法的问题,线性同余法虽然计算起来比较简单，而且参数选取适当的线性同余随机数发生器能够通过大多数随机数测试方法,。,但是，受到字长和模数的限制，线性同余法的周期一般不可能很长，对于某些仿真量特别大的需求而言可能无法满足要求。,线性同余法产生伪随机数的另一个重要问题在于它的结构性，无论怎样选择参数总会带来,n,元组之间的相关性，这种相关性在有的仿真场景下会造成仿真结果偏差。,其他随机数产生方法,为了克服线性同余法的缺点，研究人员提出了多种多样的随机数产生方法，这些方法大体上可以分为两大类。第一类是线性同余法的变种，包括非线性同余法、矩阵同余法、多递归同余法、加法,-,进位法,/,减法,-,借位法,/,乘法,-,进位法等；,第二类是移位寄存器法的变种，包括广义反馈移位寄存器,(GFSR),和,Mersenne Twister,算法等。,Mersenne Twister,Mersenne Twister,有以下优点：,随机性好；,易于在计算机上容易实现；,占用内存较少,(mt19937,的,C,程序码执行仅需,624,个字的工作区域,),；,与其它已使用的伪随机数发生器相比，产生随机数的速度快、周期长，可达到,219937-1,，且具有,623,维均匀分布的性质，对于一般的应用来说足够大，序列相关性比较小，能通过很多随机性测试。,Matlab,中的随机数产生算法,4,以前版本的默认算法：,乘同余算法,1/(231-1), 1-1/(231-1),周期,231-2.,47.3,以前的默认算法：,修正的,SWB,算法,2,-53, 1-2,-53,.,上的所有数，周期,2,1492,7.4,以后的默认算法：,Mersenne Twister,算法,2,-53, 1-2,-53,.,上的所有数，周期,(2,19937,-1)/2.,目前的,Matlab,版本可以选择多种算法中的一种，除了上述三种外还包括组合成递归生成器、延迟斐波那契生成器和移位寄,-,线性同余求和生成器，可以通过,RandStream,函数设置所需要的随机数发生器,。,30,31,主要内容,随机变量（过程）产生在蒙特卡洛仿真中的重要性,均匀分布随机变量的产生,由均匀分布产生其他分布随机变量的方法,通信系统仿真中的常用随机变量的产生,其他随机变量的产生,在蒙特卡洛仿真中，我们所需要的不仅仅是,(0,1),区间上的均匀分布随机变量，往往需要同时产生具有各种不同分布的随机变量，因此，我们必须在,(0,1),区间上均匀分布随机变量的基础上产生其他分布的随机变量,。,常用的方法有反变换法、舍选法和复合法。,33,反变换法,反变换法是一种最常用、最直观的随机变量产生方法，是将累计分布函数的反函数作用于均匀分布随机变量产生目标随机变量的方法。,由概率论可知，累计分布函数具有以下特点：,单调,不减,函数；,右连续函数；,值域为,0,1,。,如果目标随机变量的累积分布函数具有闭式表达式，都可以得到其反函数，其反函数的定义域为,0,1,区间。,34,反变换法,容易证明，如果连续分布随机变量,X,的累积分布函数为,，则变量,服从,0,1,区间上的均匀分布。因此，由均匀分布的不相关随机序列,U,经过如下变换即可获得具有概率分布函数,的不相关序列,。,指数分布的产生,累积分布函数,可以得到其累计分布函数的反函数为：,指数分布随机变量的产生方法：,产生,(0,1),区间上均匀分布的随机变量,U,；,产生服从参数为的指数分布的随机变量,。,说明,用反变换法产生随机变量时首先必须用随机数发生器产生在,0,1,区间上均匀分布的、独立的随机变量,u,。,选择一个均匀性和独立性较好的随机数发生器对于随机变量的产生非常重要,上述方法要求所需分布的累积分布函数及其反函数能用解析式表达出来，,已知概率分布的离散随机变量累积分布函数可以表示出来，适合采用反变换法。反变换法。,离散随机变量,x,分别以概率,p(x1), p(x2), p(xn),取值,x1, x2, , xn,，其中,0p(x,i,)1,且 ，其分布函数如图,离散随机变量的反变换法,38,离散随机变量的反变换法,产生离散随机变量反变换法的速度取决于区间搜索的速度,可采用多种方法，因此有各种形式的反变换法,先将,xi,按照从小到大的顺序排序，得到分布函数子区间的分界点。若由随机数发生器产生的,u=p(x1,，则,x=x1,，若,p(x1)u=p(x1)+p(x2),，则,x=x2,39,分布分解法（组合法）,反变换法是最直观的方法，但是不一定在任何情况下都是最有效的方法。当目标随机变量的累积分布函数可以表示为多个其它累计分布函数加权和的形式，而这些分布函数比目标变量分布函数更容易采样时，适合采用分布分解法，或称为组合法。,设随机变量,x,的分布函数,F(x),可写成下面形式：,F,j,(x),是其他类型的分布函数，,组合法步骤,则组合法产生随机变量的步骤如下：,（,1,）产生随机整数,J,，使,pJ=j=p,j,确定采用哪一个分布函数来取样，可采用离散反变换法来实现,（,2,）产生具有分布函数,F,j,(x),的随机变量,x,j,以该分布函数产生随机变量，可采用反变换法,（,3,）令,x=,x,j,显然，第一步可以用离散反变换法产生，确定所选择的分布函数；第二步则直接对所选择的分布函数进行采样，可以通过反变换法等方法实现。,例,产生概率密度函数为,的随机变量,X,舍选法,有的情况下，目标分布的概率分布函数难以写成闭式表达式，但是其概率密度函数可以写成闭式表达式形式，这种情况下舍选法可以作为一种通用方法来使用。,(1),产生,(a,b),区间内均匀分布的随机变量,u,1,；,(2),产生,(0,c),区间内均匀分布的随机变量,u,2,；,（,3,）,如果,则,，否则，回到第,(1),步。,舍选法,可以看出，这一步骤非常类似于上一章蒙特卡洛方法计算,值的过程，当撒点区域的面积远大于,所围成的面积时，舍选法效率很低。,为了提高舍选法的效率，撒点区域往往不设置成上例中的矩形区域，而是根据,的 特征选择一个函数,来代替常数,c,，,应满足以下条件：,易于进行反变换。,舍选法步骤,令,，则,，则,可以看做一个概率密度函数。由此，一般的舍选法步骤变为：,产生,(0,1),区间上的均匀分布随机变量,U1,；,根据,r(x),产生随机变量,；,检验不等式,，如果不等式成立，则,，否则返回第,(1,）步。,舍选法效率的高低与,的选择密切相关。,45,主要内容,随机变量（过程）产生在蒙特卡洛仿真中的重要性,均匀分布随机变量的产生,其他分布随机变量产生的一般方法,高斯分布随机变量的产生,高斯分布随机变量的产生,在通信系统中会常常碰到高斯随机变量。在很多仿真中，高斯噪声发生器都是一个最基本的模块。,非闭合形式，反变换法不适用。,概率密度函数具有闭合形式，舍选法可用，但效率非常低,中心极限定理法,中心极限定理指出，当,时，,N,个独立随机变量之和的分布趋近于高斯分布。,一般，取：,中心极限定理法的截尾现象,按上述参数得到的随机变量,只能在区间,(-6,6),区间上取值。也就是说，利用中心极限定理方法产生高斯分布随机变量时，实际产生变量的范围总是无法达到高斯分布的尾部，这种现象称为截尾。增大,N,值，可以减小这种影响，却会增大计算量计算。,因此，如果采用中心极限定理方法产生高斯分布，需要合理选取,N,值，以在仿真速度和精度之间作出折中。,Box-Muller,方法,瑞利分布和高斯分布之间的有密切关系,如果,X,和,Y,为均值为,0,、方差为,的独立高斯随机变量，那么,服从参数为,的瑞利分布,服从 上的均匀分布。,将该关系反过来，就是,Box-Muller,方法,的原理,由,George Box,和,Mervin Muller,在,1958,年提出,。,瑞利分布的产生,瑞,利分布的累积分布函数具有闭式表达式，可以采用反变换法产生瑞利分布随机变量。,Box-Muller,方法的产生标准高斯分布随机变量的步骤,产生两个独立的,(0,1),区间上均匀分布随机变量,U1,和,U2,；,可以产生两个独立的、均值为,0,方差为,1,的高斯分布随机变量。,舍选法与,Box-Muller,算法的组合,标准的,Box-Muller,方法需要计算三角函数，计算复杂度较高，有人研究了另一种形式的,Box-Muller,方法,。,(1),产生两个独立的在,-1,1,上均匀分布的随机变量,U1,和,U2,；,(2),令,。如果,，舍弃,的值并返回上一步；否则，进入下一步,；,(3),则,X,、,Y,即为标准高斯分布的随机变量。,优缺点,从运算上，这种方法方法与标准的,Box-Muller,方法相比，避免了三角函数运算，这样使运算速度加快。但是它采用了舍选法，效率有所下降。同时，,次调用极坐标算法产生的高斯随机变量对的个数也是随机变量，这会使得仿真程序更加复杂。,有色高斯随机过程的产生,在通信系统仿真中，有时需要用到有色高斯随机过程。,产生具有相关性的非分布是一件比较困难的事情，但是由于高斯分布具有一些非常特殊的性质，使得有色高斯随机过程相比比较简单。,产生具有给定相关系数的高斯分布随机变量,首先生成两个零均值、方差相等的独立高斯分布随机变量,X,和,Y,，引入另一个随机变量,Z,，定义为,X,和,Z,的相关系数为,。,Z,的均值为,0,，方差与,X,和,Y,相等。,生成具有给定功率谱密度的高斯随机过程,独立高斯通过给定的滤波器,参阅书上例子,已知协方差矩阵的高斯随机过程,如果已知两个零均值高斯随机过程的相关矩阵，可以通过以下方法实现具有相关性的高斯随机过程；,相关矩阵进行,Cholesky,分解,mu = 1 2;,Sigma = 1 .5; .5 2;,R = chol(Sigma);,z = repmat(mu,100,1) + randn(100,2)*R;,Matlab,中的随机变量产生,rand,randn,random,