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

1、别志松 随机变量的产生2主要内容随机变量（过程）产生在蒙特卡洛仿真中的重要性均匀分布随机变量的产生其他分布随机变量产生的一般方法高斯分布随机变量的产生蒙特卡洛仿真的三个过程构造或描述概率过程从已知分布进行采样，即随机试验建立估计量3蒙特卡洛仿真精度的决定性因素仿真试验次数高斯近似、泊松近似从已知分布采样的准确性！可能造成有偏估计；严重影响仿真精度。4计算机仿真中的随机采样计算机仿真中的蒙特卡洛方法要求在计算机上产生满足一定概率分布的随机数。计算机只能按人的意志按照一定的程序产生数据，因此必然不可能是纯随机的。只可能是伪随机的。满足一定条件的伪随机采样能够完成仿真评估目标。5早期的随机数产生器在

2、发展过程的早期，随机数是通过人为技术产生的，如抛硬币，掷骰子，玩纸牌和赌盘等。后来出现了一些物理设备，如噪音二极管，盖格计数器，这些设备与电脑相连来产生随机数。当时普遍认为只有机械或电子设备才能产生真正的随机序列。机械设备仍然广泛运用于赌博和与其类似的活动中。传统随机数产生方法的问题对于普遍应用来说，机械学方法太慢；产生的序列不能重现；机械学方法产生的数据具有主观性和非独立性。尽管一些先进的物理方法能很快产生随机数并能通过绝大多数的统计测试，（例如基于热噪声的设备），但它们主要的缺陷是缺乏可重复性。现代随机数产生方法现在多数的随机数据发生器都不基于物理设备，而是在计算机上通过对数的操作实现。它

3、们运行快，要求的存储空间小；能很容易的重现给定的随机数。一个好的随机数产生器几乎拥有着真实随机序列的所有重要的统计特性但这些序列是由确定性算法产生的。由于这个原因，这类发生器所产生的序列的随机性常常称为伪随机。计算机工具中的伪随机变量产生C语言库函数中提供了rand函数产生从0到RAND_MAX中的任意整数；在此基础上可以产生服从其他分布的随机变量。但是在一些情况下，该随机数生成函数不能满足仿真要求。Matlab提供了rand、randn、random等一系列随机数生成函数。大部分高级语言都提供了随机数生成的有关函数。但是仍有必要初步了解一些随机变量产生的知识。910主要内容随机变量（过程）产

4、生在蒙特卡洛仿真中的重要性均匀分布随机变量的产生由均匀分布产生其他分布随机变量的方法通信系统仿真中的常用随机变量的产生均匀分布随机数产生的重要性均匀分布的随机数在蒙特卡洛仿真中具有非常重要的地位，是从已知随机分布采样的基础。其他分布随机数的产生以均匀分布随机数为基础。均匀分布随机数产生方法的优劣决定了蒙特卡洛仿真从已知分布采样的可信度，其中产生0,1区间上均匀分布的随机变量是生成其他随机变量的前提。在不少文献中所说的随机数发生器（RNG）就特指产生0,1区间上均匀分布随机变量的算法。11均匀分布随机数产生方法种类线性同余方法及其变种乘同余混合同余组合移位寄存器法及其变种单变量平方移位法加法-进

5、位法和减法-借位法Mersenne Twister法1213线性同余发生器采用下述公式产生随机数：其中 是第i个随机数，a为乘子，b为增量，m为模数， 为随机数源或种子，均为非负整数令 ，则可得到0,1)区间上的随机数线性同余发生器若a!=0, b!=0，称为混合同余法若a=1，b!=0，称为加同余法若a!=0, b=0，称为乘同余法研究表明，乘同余法优于加同余法，而混合同余法与简单的乘同余法相比并无显著优点。因此，乘同余法更常用线性同余法的周期性这种方法产生的随机数实际上是伪随机数：采用递推算法，后面产生的数会重复前面的数，即实际上是有限的周期数列。无论Zi取何值，其循环顺序相同。随机数循环

6、一次称为发生器的一个周期(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的混合同余发生

7、器。下面简单介绍如何根据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

8、*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最小标准随机数发生器测试比

9、较复杂，不可能任意设计并测试。因此有人提出多种最小标准，最小标准要求：满周期通过一组随机性统计测试易于从一台计算机移植到另一台计算机 23Lewis，Goosman和Miller最小标准m=231-124复合线性同余法25在希望获得一些更长周期（并不一定是满周期）的随机数发生器时，一个行之有效的思想就是把具有较短周期的不同随机数发生器的输出线性合并。两个周期分别为N1和N2的随机数发生器合并之后的输出随机数周期为：当N1和N2互素时，N=N1*N2一种复合线性同余发生器周期线性同余法的问题线性同余法虽然计算起来比较简单，而且参数选取适当的线性同余随机数发生器能够通过大多数随机数测试方法。但是，

10、受到字长和模数的限制，线性同余法的周期一般不可能很长，对于某些仿真量特别大的需求而言可能无法满足要求。线性同余法产生伪随机数的另一个重要问题在于它的结构性，无论怎样选择参数总会带来n元组之间的相关性，这种相关性在有的仿真场景下会造成仿真结果偏差。其他随机数产生方法为了克服线性同余法的缺点，研究人员提出了多种多样的随机数产生方法，这些方法大体上可以分为两大类。第一类是线性同余法的变种，包括非线性同余法、矩阵同余法、多递归同余法、加法-进位法/减法-借位法/乘法-进位法等；第二类是移位寄存器法的变种，包括广义反馈移位寄存器(GFSR)和Mersenne Twister算法等。Mersenne Tw

11、isterMersenne 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.上的所有数，周期21492 7.4以后的默认算法：Mersenne

12、 Twister 算法2-53, 1-2-53.上的所有数，周期 (219937-1)/2.目前的Matlab版本可以选择多种算法中的一种，除了上述三种外还包括组合成递归生成器、延迟斐波那契生成器和移位寄-线性同余求和生成器，可以通过RandStream函数设置所需要的随机数发生器。3031主要内容随机变量（过程）产生在蒙特卡洛仿真中的重要性均匀分布随机变量的产生由均匀分布产生其他分布随机变量的方法通信系统仿真中的常用随机变量的产生其他随机变量的产生在蒙特卡洛仿真中，我们所需要的不仅仅是(0,1)区间上的均匀分布随机变量，往往需要同时产生具有各种不同分布的随机变量，因此，我们必须在(0,1)区

13、间上均匀分布随机变量的基础上产生其他分布的随机变量。常用的方法有反变换法、舍选法和复合法。33反变换法反变换法是一种最常用、最直观的随机变量产生方法，是将累计分布函数的反函数作用于均匀分布随机变量产生目标随机变量的方法。由概率论可知，累计分布函数具有以下特点：单调不减函数；右连续函数；值域为0,1。如果目标随机变量的累积分布函数具有闭式表达式，都可以得到其反函数，其反函数的定义域为0,1区间。34反变换法容易证明，如果连续分布随机变量X的累积分布函数为 ，则变量 服从0,1区间上的均匀分布。因此，由均匀分布的不相关随机序列U经过如下变换即可获得具有概率分布函数 的不相关序列 。指数分布的产生累

14、积分布函数可以得到其累计分布函数的反函数为：指数分布随机变量的产生方法：产生(0,1)区间上均匀分布的随机变量U；产生服从参数为的指数分布的随机变量 。说明用反变换法产生随机变量时首先必须用随机数发生器产生在0,1区间上均匀分布的、独立的随机变量u。选择一个均匀性和独立性较好的随机数发生器对于随机变量的产生非常重要上述方法要求所需分布的累积分布函数及其反函数能用解析式表达出来，已知概率分布的离散随机变量累积分布函数可以表示出来，适合采用反变换法。反变换法。离散随机变量x分别以概率p(x1), p(x2), p(xn)取值x1, x2, , xn，其中0p(xi)1且 ，其分布函数如图离散随机变

15、量的反变换法38离散随机变量的反变换法产生离散随机变量反变换法的速度取决于区间搜索的速度可采用多种方法，因此有各种形式的反变换法先将xi按照从小到大的顺序排序，得到分布函数子区间的分界点。若由随机数发生器产生的u=p(x1，则x=x1，若p(x1)u=p(x1)+p(x2)，则x=x239分布分解法（组合法）反变换法是最直观的方法，但是不一定在任何情况下都是最有效的方法。当目标随机变量的累积分布函数可以表示为多个其它累计分布函数加权和的形式，而这些分布函数比目标变量分布函数更容易采样时，适合采用分布分解法，或称为组合法。设随机变量x的分布函数F(x)可写成下面形式：Fj(x)是其他类型的分布函

16、数，组合法步骤则组合法产生随机变量的步骤如下：（1）产生随机整数J，使pJ=j=pj 确定采用哪一个分布函数来取样，可采用离散反变换法来实现（2）产生具有分布函数Fj(x)的随机变量xj 以该分布函数产生随机变量，可采用反变换法（3）令x=xj显然，第一步可以用离散反变换法产生，确定所选择的分布函数；第二步则直接对所选择的分布函数进行采样，可以通过反变换法等方法实现。例产生概率密度函数为 的随机变量X 舍选法有的情况下，目标分布的概率分布函数难以写成闭式表达式，但是其概率密度函数可以写成闭式表达式形式，这种情况下舍选法可以作为一种通用方法来使用。(1)产生(a,b)区间内均匀分布的随机变量u1

17、；(2)产生(0,c)区间内均匀分布的随机变量u2；（3）如果 则 ，否则，回到第(1)步。舍选法可以看出，这一步骤非常类似于上一章蒙特卡洛方法计算值的过程，当撒点区域的面积远大于 所围成的面积时，舍选法效率很低。为了提高舍选法的效率，撒点区域往往不设置成上例中的矩形区域，而是根据 的 特征选择一个函数 来代替常数c， 应满足以下条件：易于进行反变换。舍选法步骤令 ，则 ，则 可以看做一个概率密度函数。由此，一般的舍选法步骤变为：产生(0,1)区间上的均匀分布随机变量U1；根据r(x) 产生随机变量 ；检验不等式 ，如果不等式成立，则 ，否则返回第(1）步。舍选法效率的高低与 的选择密切相关。

18、45主要内容随机变量（过程）产生在蒙特卡洛仿真中的重要性均匀分布随机变量的产生其他分布随机变量产生的一般方法高斯分布随机变量的产生高斯分布随机变量的产生在通信系统中会常常碰到高斯随机变量。在很多仿真中，高斯噪声发生器都是一个最基本的模块。非闭合形式，反变换法不适用。概率密度函数具有闭合形式，舍选法可用，但效率非常低中心极限定理法中心极限定理指出，当 时， N个独立随机变量之和的分布趋近于高斯分布。一般，取：中心极限定理法的截尾现象按上述参数得到的随机变量 只能在区间(-6,6)区间上取值。也就是说，利用中心极限定理方法产生高斯分布随机变量时，实际产生变量的范围总是无法达到高斯分布的尾部，这种现

19、象称为截尾。增大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方法需要计算三角函数