蒙卡特罗方法课件3.ppt

第二章 随机数;第二章 随机数;随机数的定义及产生方法;随机数的定义及性质 ; 由于随机数在蒙特卡罗方法中占有极其重要的位置，我们用专门的符号ξ表示。由随机数序列的定义可知，ξ1，ξ2，…是相互独立且具有相同单位均匀分布的随机数序列。也就是说，独立性、均匀性是随机数必备的两个特点。 随机数具有非常重要的性质：对于任意自然数s，由s个随机数组成的s维空间上的点（ξn+1，ξn+2，…ξn+s）在s维空间的单位立方体Gs上均匀分布，即对任意的ai， 如下等式成立：; 其中P(·)表示事件·发生的概率。反之，如果随机变量序列ξ1, ξ2…对于任意自然数s，由s个元素所组成的s维空间上的点（ξn+1，…ξn+s）在Gs上均匀分布，则它们是随机数序列。 由于随机数在蒙特卡罗方法中所处的特殊地位，它们虽然也属于由具有已知分布的总体中产生简单子样的问题，但就产生方法而言，却有着本质上的差别。 ;随机数表;物理方法; 因此，利用物理方法在计算机上产生随机数，就是要产生只取0或1的随机数字序列，数字之间相互独立，每个数字取0或1的概率均为0.5。 用物理方法产生的随机数序列无法重复实现，不能进行程序复算，给验证结果带来很大困难。而且，需要增加随机数发生器和电路联系等附加设备，费用昂贵。因此，该方法也不适合在计算机上使用。;伪随机数;伪随机数;伪随机数存在的两个问题; 由于这两个问题的存在，常称用数学方法产生的随机数为伪随机数。对于以上存在的两个问题，作如下具体分析。 关于第一个问题，不能从本质上加以改变，但只要递推公式选得比较好，随机数间的相互独立性是可以近似满足的。至于第二个问题，则不是本质的。因为用蒙特卡罗方法解任何具体问题时，所使用的随机数的个数总是有限的，只要所用随机数的个数不超过伪随机数序列出现循环现象时的长度就可以了。 用数学方法产生的伪随机数容易在计算机上得到，可以进行复算，而且不受计算机型号的限制。因此，这种方法虽然存在着一些问题，但仍然被广泛地在计算机上使用，是在计算机上产生伪随机数的主要方法。 ;伪随机数的周期和最大容量 ;产生伪随机数的乘同余方法;乘同余方法的最大容量的上界;关于a与x1的取值;乘同余方法在计算机上的使用;产生伪随机数的乘加同余方法;乘加同余方法的最大容量; M，x1，a，c的取值;产生伪随机数的其他方法;伪随机数序列的均匀性和独立性;伪随机数的均匀性 ; 将伪随机数序列ξ1,ξ2…，ξn从小至大重新排列 并令 ，则由δ(n)的定义，容易证明 很明显，对于固定的ｎ，δ(n)的值越小越好。它是描述伪随机数序列均匀程度的基本量。对于任意随机数序列，均有如下不等式成立： 当 时，所对应的伪随机数序列为最佳分布。; 可以证明，伪随机数序列为最佳分布的充要条件是它取遍序列 的所有值。 对于计算机上使用的乘同余方法，按照前面介绍的方法选取a、x1时，所产生的伪随机数序列的均匀偏度 对于乘加同余方法 对于部分伪随机数的均匀性问题通常用统计检验方法检验。 ;伪随机数的独立性 ; 对于乘同余方法， 对于乘加同余方法， 因此，这两种方法的独立性都是很好的。 同伪随机数的均匀性问题一样，伪随机数序列的独立性问题也是对它的全体讨论的。若只考虑伪随机数的一部分，在通常情况下给出ε(i)是相当因难的。因此，伪随机数序列的独立性问题的统计检验方法同样是非常重要的。 ;作 业