蒙特卡罗随机数.ppt

《蒙特卡罗随机数.ppt》由会员分享，可在线阅读，更多相关《蒙特卡罗随机数.ppt（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1.随机数的定义及产生方法随机数的定义及产生方法 2.伪随机数伪随机数3.产生伪随机数的乘同余方法产生伪随机数的乘同余方法4.产生伪随机数的乘加同余方法产生伪随机数的乘加同余方法5.产生伪随机数的其他方法产生伪随机数的其他方法6.伪随机数序列的均匀性和独立性伪随机数序列的均匀性和独立性2.2 MC2.2 MC随机数随机数1)随机数的定义及性质2)随机数表3)物理方法1.MC1.MC随机数的定义及产生方法随机数的定义及产生方法什么是随机数？什么是随机数？单个的数字不是随机数单个的数字不是随机数是指一个数列，其中的每一个体称为随机数，其值与数列中是指一个数列，其中的每一个体称为随机数，其值与数列中

2、的其它数无关；的其它数无关；在一个均匀分布的随机数中，每一个体出现的概率是均等的；在一个均匀分布的随机数中，每一个体出现的概率是均等的；v例如：在例如：在0,1区间上均匀分布的随机数序列中，区间上均匀分布的随机数序列中，0.00001与与0.5出现的机会均等出现的机会均等1.1 MC MC随机数随机数定义及特性定义及特性 由具有已知分布的由具有已知分布的总体中抽取简单子样总体中抽取简单子样，在蒙特卡罗方法中占有非常重要，在蒙特卡罗方法中占有非常重要的地位。总体和子样的关系，属于一般和个别的关系，或者说属于共性和个的地位。总体和子样的关系，属于一般和个别的关系，或者说属于共性和个性的关系。由具有

3、性的关系。由具有已知分布已知分布的总体中产生的总体中产生简单子样简单子样，就是由简单子样中若干，就是由简单子样中若干个性近似地反映总体的共性。个性近似地反映总体的共性。随机数随机数是实现由是实现由已知分布抽样的基本量已知分布抽样的基本量，在由已知分布的抽样过程中，将，在由已知分布的抽样过程中，将随机数作为已知量，用适当的数学方法可以由它产生具有任意已知分布的简随机数作为已知量，用适当的数学方法可以由它产生具有任意已知分布的简单子样。单子样。在连续型随机变量的分布中，最简单而且最基本的分在连续型随机变量的分布中，最简单而且最基本的分布是单位均匀分布。由该分布抽取的简单子样称，随机数布是单位均匀分

4、布。由该分布抽取的简单子样称，随机数序列，其中每一个体称为随机数。序列，其中每一个体称为随机数。单位均匀分布也称为单位均匀分布也称为0，1上的均匀分布，其分布上的均匀分布，其分布密度函数为：密度函数为：分布函数为分布函数为：1.1 MC MC随机数随机数定义及特性定义及特性 由于随机数在蒙特卡罗方法中占有极其重要的位由于随机数在蒙特卡罗方法中占有极其重要的位置，我们用专门的符号置，我们用专门的符号表示。由随机数序列的定义可表示。由随机数序列的定义可知，知，1，2，是相互独立且具有相同单位均匀分布的是相互独立且具有相同单位均匀分布的随机数序列。也就是说，随机数序列。也就是说，独立性独立性、均匀性

5、均匀性是随机数必是随机数必备的两个特点。备的两个特点。随机数具有非常重要的性质：对于任意自然数随机数具有非常重要的性质：对于任意自然数s，由由s个随机数组成的个随机数组成的s维空间上的点维空间上的点（n+1，n+2，n+s）在在s维空间的单位立方体维空间的单位立方体Gs上均匀分布，即对任意的上均匀分布，即对任意的ai，如下等式成立：如下等式成立：1.1 MC MC随机数随机数定义及特性定义及特性 其中其中P()表示事件表示事件发生的概率。反之，如果随机发生的概率。反之，如果随机变量序列变量序列1,2对于任意自然数对于任意自然数s，由，由s个元素所组成个元素所组成的的s维空间上的点（维空间上的点

6、（n+1，n+s）在）在Gs上均匀分布，上均匀分布，则它们是随机数序列。则它们是随机数序列。由于随机数在蒙特卡罗方法中所处的特殊地位，由于随机数在蒙特卡罗方法中所处的特殊地位，它们虽然也属于由具有已知分布的总体中产生简单子它们虽然也属于由具有已知分布的总体中产生简单子样的问题，但就产生方法而言，却有着本质上的差别。样的问题，但就产生方法而言，却有着本质上的差别。1.1 MC MC随机数随机数定义及特性定义及特性 为了产生随机数，可以使用随机数表。随机数表为了产生随机数，可以使用随机数表。随机数表是由是由0，1，9十个数字组成，每个数字以十个数字组成，每个数字以0.1的等概的等概率出现，数字之间

7、相互独立。这些数字序列叫作随机率出现，数字之间相互独立。这些数字序列叫作随机数字序列。如果要得到数字序列。如果要得到n位有效数字的随机数，只需将位有效数字的随机数，只需将表中每表中每n个相邻的随机数字合并在一起，且在最高位的个相邻的随机数字合并在一起，且在最高位的前边加上小数点即可。例如，某随机数表的第一行数前边加上小数点即可。例如，某随机数表的第一行数字为字为7634258910，要想得到三位有效数字的随机数，要想得到三位有效数字的随机数依次为依次为0.763，0.425，0.891。因为随机数表需在计算机中占有很大内存，而且因为随机数表需在计算机中占有很大内存，而且也难以满足蒙特卡罗方法对

8、随机数需要量非常大的要也难以满足蒙特卡罗方法对随机数需要量非常大的要求，因此，该方法不适于在计算机上使用。求，因此，该方法不适于在计算机上使用。1.2 MC MC随机数表随机数表 用物理方法产生随机数的基本原理是：利用某些用物理方法产生随机数的基本原理是：利用某些物理现象，在计算机上增加些特殊设备，可以在计算物理现象，在计算机上增加些特殊设备，可以在计算机上直接产生随机数。这些特殊设备称为随机数发生机上直接产生随机数。这些特殊设备称为随机数发生器。用来作为随机数发生器的物理源主要有两种：一器。用来作为随机数发生器的物理源主要有两种：一种是根据放射性物质的放射性，另一种是利用计算机种是根据放射性

9、物质的放射性，另一种是利用计算机的固有噪声。的固有噪声。一般情况下，任意一个随机数在计算机内总是用一般情况下，任意一个随机数在计算机内总是用二进制的数表示的：二进制的数表示的：其中其中i（i=1，2，m）或者为）或者为0，或者为，或者为1。1.3 MC MC随机数随机数物理方法物理方法 因此，利用物理方法在计算机上产生随机数，就是因此，利用物理方法在计算机上产生随机数，就是要产生只取要产生只取0或或1的随机数字序列，数字之间相互独立，的随机数字序列，数字之间相互独立，每个数字取每个数字取0或或1的概率均为的概率均为0.5。用物理方法产生的随机数序列无法重复实现，不能用物理方法产生的随机数序列无

10、法重复实现，不能进行程序复算，给验证结果带来很大困难。而且，需要进行程序复算，给验证结果带来很大困难。而且，需要增加随机数发生器和电路联系等附加设备，费用昂贵。增加随机数发生器和电路联系等附加设备，费用昂贵。因此，该方法也不适合在计算机上使用。因此，该方法也不适合在计算机上使用。1.3 MC MC随机数随机数物理方法物理方法l0,10,1区间上均匀分布的随机数是区间上均匀分布的随机数是Monte CarloMonte Carlo模拟的基础模拟的基础:0,10,1均匀分布的随机数的产生方法：均匀分布的随机数的产生方法：利用一些具有内在的随机性的过程利用一些具有内在的随机性的过程放射性衰变过程（放

11、射性衰变过程（radioactive decay)radioactive decay)；热噪声热噪声(thermal noise);(thermal noise);宇宙线的到达时间（宇宙线的到达时间（cosmic ray arrival);cosmic ray arrival);缺点：模拟的结果不可再现，使得模拟程序的找错困难缺点：模拟的结果不可再现，使得模拟程序的找错困难利用事先制订好的随机数表利用事先制订好的随机数表缺点：表的容量有限，不适合需要大量随机数的应用缺点：表的容量有限，不适合需要大量随机数的应用服从任意分布的随机数序列可以用服从任意分布的随机数序列可以用0,10,1区间均匀分布

12、的区间均匀分布的随机数序列作适当的变换或舍选后求得随机数序列作适当的变换或舍选后求得1.3 MC MC随机数随机数小结小结1)伪随机数伪随机数2)伪随机数存在的两个问题伪随机数存在的两个问题3)伪随机数的周期和最大容量伪随机数的周期和最大容量 2 伪随机数伪随机数 在计算机上产生随机数最实用、最常见的方法是数学方法，即用如在计算机上产生随机数最实用、最常见的方法是数学方法，即用如下递推公式：下递推公式：产生随机数序列。对于给定的初始值产生随机数序列。对于给定的初始值1,2，k，确定，确定n+k，=1，2，。经常使用的是。经常使用的是k=1的情况，其递推公式为：的情况，其递推公式为：对于给定的初

13、始值对于给定的初始值1，确定，确定n+1，=,2 伪随机数伪随机数 用数学方法产生的随机数，存在两个问题：用数学方法产生的随机数，存在两个问题：a)递推公式和初始值递推公式和初始值1,2，k确定后，整个随机数序列确定后，整个随机数序列便被唯一确定。不满足随机数相互独立的要求。便被唯一确定。不满足随机数相互独立的要求。b)由于随机数序列是由递推公式确定的，而在计算机上所能由于随机数序列是由递推公式确定的，而在计算机上所能表示的表示的0，1上的数又是有限的，因此，这种方法产生的上的数又是有限的，因此，这种方法产生的随机数序列就不可能不出现无限重复。一旦出现这样的随机数序列就不可能不出现无限重复。一

14、旦出现这样的n，n(nDraw();pad2-Draw();pad3-Draw();TH1F*h1=new TH1F(h1,h1,100,0.0,1.0);TH2F*h2=new TH2F(h2,h2,100,0.0,1.0,100,0.0,1.0);TH3F*h3=new TH3F(h3,h3,100,0.0,1.0,100,0.0,1.0,100,0.0,1.0);2 伪随机数伪随机数 for(int i=0;i Fill(x);h2-Fill(x,y);h3-Fill(x,y,z);pad1-cd();h1-Draw();pad2-cd();h2-Draw();pad3-cd();h3-

15、Draw();2 伪随机数伪随机数2 伪随机数伪随机数如果取如果取a=69069,a=69069,将极大地改善结果将极大地改善结果2 伪随机数伪随机数1968年，年，Marsaglia对这一问题进行了研究，认为：对这一问题进行了研究，认为：任何的乘同余产生器都存在这一问题：在三维和三维以任何的乘同余产生器都存在这一问题：在三维和三维以上的空间中，所产生的随机数总是集聚在一些超平面上上的空间中，所产生的随机数总是集聚在一些超平面上随机数序列是关联的随机数序列是关联的对于对于32位的计算机，在位的计算机，在d-维空间中超平面的最大数目为维空间中超平面的最大数目为d=3 2953d=4 566d=6

16、 120d=10 41改进措施：将递推公式修改为改进措施：将递推公式修改为特点：特点：1）需要两个初始值（种子）；）需要两个初始值（种子）；2）周期可大于）周期可大于m;2 伪随机数伪随机数#include unsigned long seed0=9;unsigned long seed1=11;float randac()const unsigned long a=65539;const unsigned long b=65539;unsigned long i2;unsigned long m=pow(2,31);i2=(a*seed1+b*seed0)%m;seed0=seed1;see

17、d1=i2;return(float)i1/float(m);void SetSeed(unsigned long i0,unsigned long i1)seed0=i0;seed1=i1;2 伪随机数伪随机数a=b=65539,seed0=9,seed1=112 伪随机数伪随机数如何获取如何获取0,1区间均匀分布的随机数产生器：区间均匀分布的随机数产生器：1.每一个每一个Monte Carlo模拟程序软件包都有自带的产生器：模拟程序软件包都有自带的产生器：Jetset(LUND Monte Carlo模拟系列）：利用模拟系列）：利用Marsaglia等等所提出的算法，周期可达所提出的算法，

18、周期可达1043函数用法：函数用法：r=rlu(idummy)Geant3(探测器模拟程序，探测器模拟程序，FORTRAN):周期周期=1018Call grndm(vec*,len).2.利用利用CERN程序库：程序库：Y=rndm(x):周期：周期：5x108Y=rn32(dummy):乘同余法，乘同余法，a=69069,i0=65539Call ranmar(vec,len):周期：周期：1043Call ranecu(vec,len,isq)2 伪随机数伪随机数CLHEP(Class Library for High Energy Physics)中的随机数产中的随机数产生器生器3.利

19、用利用CLHEP中的随机数产生器软件包：中的随机数产生器软件包：http:/ 伪随机数伪随机数FORTRAN中使用随机数产生器应注意的问题：中使用随机数产生器应注意的问题：在在FORTRAN中，如果随机数产生器是带中，如果随机数产生器是带dummy变量的函数：变量的函数：其中变量其中变量idum在函数中不使用，应注意以下问题：在函数中不使用，应注意以下问题：X=RAND(idum)FORTRAN编译器在对程序进行优化时：编译器在对程序进行优化时：X=RAND(IDUM)+RAND(IDUM)X=2.0*RAND(IDUM)DO I=1,10 X=RAND(IDUM)END DOX=RAND(I

20、DUM)DO I=1,10 .END DO解决办法：解决办法：DO I=1,10 IDUM=IDUM+1 X=RAND(IDUM)END DO2 伪随机数伪随机数 判断伪随机数序列是否满足均匀和相互独立的要求，判断伪随机数序列是否满足均匀和相互独立的要求，要靠统计检验的方法实现。对于伪随机数的统计检验，一要靠统计检验的方法实现。对于伪随机数的统计检验，一般包括两大类：均匀性检验和独立性检验。般包括两大类：均匀性检验和独立性检验。六十年代初，人们开始用定性的方法研究伪随机数序六十年代初，人们开始用定性的方法研究伪随机数序列的均匀性和独立性问题，简要叙述如下。列的均匀性和独立性问题，简要叙述如下。

21、2 伪随机数伪随机数均匀性和独立性均匀性和独立性1)伪随机数的均匀性伪随机数的均匀性 这里只考虑伪随机数序列1,2，n全体作为子样时的均匀性问题。其中n为伪随机数序列的最大容量。对 于 任 意 的 0 x1，令 Nn(x)表 示 伪 随 机 数 序 列1,2，n中适合不等式i x i=1，2，n 的个数，则 标志伪随机数序列1,2，n的均匀程度，称为均匀偏度。2 伪随机数伪随机数均匀性和独立性均匀性和独立性 将伪随机数序列1,2，n从小至大重新排列 并令 ，则由(n)的定义，容易证明 很明显，对于固定的，(n)的值越小越好。它是描述伪随机数序列均匀程度的基本量。对于任意随机数序列，均有如下不等

22、式成立：当 时，所对应的伪随机数序列为最佳分布。2 伪随机数伪随机数均匀性和独立性均匀性和独立性 可以证明，伪随机数序列为最佳分布的充要条件是它取遍序列 的所有值。对于计算机上使用的乘同余方法，按照前面介绍的方法选取a、x1时，所产生的伪随机数序列的均匀偏度 对于乘加同余方法 对于部分伪随机数的均匀性问题通常用统计检验方法检验。2 伪随机数伪随机数均匀性和独立性均匀性和独立性2)伪随机数的独立性伪随机数的独立性 对于任意 ，令 表示(1,2)，(2,3)，(n,n+1)中适合不等式 的个数，根据随机变量间相互独立的定义和频率近似概率的方法，令 则(n)标志伪随机数序列1,2，n的独立程度，简称为独立偏度。对于固定的n,(n)的值越接近于零，伪随机数序列的独立性越好。2 伪随机数伪随机数均匀性和独立性均匀性和独立性 对于乘同余方法，对于乘加同余方法，因此，这两种方法的独立性都是很好的。同伪随机数的均匀性问题一样，伪随机数序列的独立性问题也是对它的全体讨论的。若只考虑伪随机数的一部分，在通常情况下给出(i)是相当因难的。因此，伪随机数序列的独立性问题的统计检验方法同样是非常重要的。2 伪随机数伪随机数均匀性和独立性均匀性和独立性40例子例子41例子例子