蒙特卡罗随机数.ppt
《蒙特卡罗随机数.ppt》由会员分享,可在线阅读,更多相关《蒙特卡罗随机数.ppt(41页珍藏版)》请在三一文库上搜索。
1、随机数的定义及产生方法 伪随机数 产生伪随机数的乘同余方法 产生伪随机数的乘加同余方法 产生伪随机数的其他方法 伪随机数序列的均匀性和独立性,2.2 MC随机数,随机数的定义及性质 随机数表 物理方法,1.MC随机数的定义及产生方法,什么是随机数?,单个的数字不是随机数,是指一个数列,其中的每一个体称为随机数,其值与数列中的其它数无关;,在一个均匀分布的随机数中,每一个体出现的概率是均等的;,例如:在0,1区间上均匀分布的随机数序列中,0.00001与0.5出现的机会均等,1.1 MC随机数定义及特性,由具有已知分布的总体中抽取简单子样,在蒙特卡罗方法中占有非常重要的地位。总体和子样的关系,属
2、于一般和个别的关系,或者说属于共性和个性的关系。由具有已知分布的总体中产生简单子样,就是由简单子样中若干个性近似地反映总体的共性。 随机数是实现由已知分布抽样的基本量,在由已知分布的抽样过程中,将随机数作为已知量,用适当的数学方法可以由它产生具有任意已知分布的简单子样。,在连续型随机变量的分布中,最简单而且最基本的分布是单位均匀分布。由该分布抽取的简单子样称,随机数序列,其中每一个体称为随机数。 单位均匀分布也称为0,1上的均匀分布,其分布密度函数为: 分布函数为 :,1.1 MC随机数定义及特性,由于随机数在蒙特卡罗方法中占有极其重要的位置,我们用专门的符号表示。由随机数序列的定义可知,1,
3、2,是相互独立且具有相同单位均匀分布的随机数序列。也就是说,独立性、均匀性是随机数必备的两个特点。 随机数具有非常重要的性质:对于任意自然数s,由s个随机数组成的s维空间上的点(n+1,n+2,n+s)在s维空间的单位立方体Gs上均匀分布,即对任意的ai, 如下等式成立:,1.1 MC随机数定义及特性,其中P()表示事件发生的概率。反之,如果随机变量序列1, 2对于任意自然数s,由s个元素所组成的s维空间上的点(n+1,n+s)在Gs上均匀分布,则它们是随机数序列。 由于随机数在蒙特卡罗方法中所处的特殊地位,它们虽然也属于由具有已知分布的总体中产生简单子样的问题,但就产生方法而言,却有着本质上
4、的差别。,1.1 MC随机数定义及特性,为了产生随机数,可以使用随机数表。随机数表是由0,1,9十个数字组成,每个数字以0.1的等概率出现,数字之间相互独立。这些数字序列叫作随机数字序列。如果要得到n位有效数字的随机数,只需将表中每n个相邻的随机数字合并在一起,且在最高位的前边加上小数点即可。例如,某随机数表的第一行数字为7634258910,要想得到三位有效数字的随机数依次为0.763,0.425,0.891。 因为随机数表需在计算机中占有很大内存,而且也难以满足蒙特卡罗方法对随机数需要量非常大的要求,因此,该方法不适于在计算机上使用。,1.2 MC随机数表,用物理方法产生随机数的基本原理是
5、:利用某些物理现象,在计算机上增加些特殊设备,可以在计算机上直接产生随机数。这些特殊设备称为随机数发生器。用来作为随机数发生器的物理源主要有两种:一种是根据放射性物质的放射性,另一种是利用计算机的固有噪声。 一般情况下,任意一个随机数在计算机内总是用二进制的数表示的: 其中i(i=1,2,m)或者为0,或者为1。,1.3 MC随机数物理方法,因此,利用物理方法在计算机上产生随机数,就是要产生只取0或1的随机数字序列,数字之间相互独立,每个数字取0或1的概率均为0.5。 用物理方法产生的随机数序列无法重复实现,不能进行程序复算,给验证结果带来很大困难。而且,需要增加随机数发生器和电路联系等附加设
6、备,费用昂贵。因此,该方法也不适合在计算机上使用。,1.3 MC随机数物理方法,0,1区间上均匀分布的随机数是Monte Carlo模拟的基础:,0,1均匀分布的随机数的产生方法:,利用一些具有内在的随机性的过程,缺点:模拟的结果不可再现,使得模拟程序的找错困难,利用事先制订好的随机数表,缺点:表的容量有限,不适合需要大量随机数的应用,服从任意分布的随机数序列可以用0,1区间均匀分布的随机数序列作适当的变换或舍选后求得,1.3 MC随机数小结,伪随机数 伪随机数存在的两个问题 伪随机数的周期和最大容量,2 伪随机数,在计算机上产生随机数最实用、最常见的方法是数学方法,即用如下递推公式: 产生随
7、机数序列。对于给定的初始值1,2,k,确定n+k,=1,2,。经常使用的是k=1的情况,其递推公式为: 对于给定的初始值1,确定n+1,=,2 伪随机数,用数学方法产生的随机数,存在两个问题: 递推公式和初始值1,2,k确定后,整个随机数序列便被唯一确定。不满足随机数相互独立的要求。 由于随机数序列是由递推公式确定的,而在计算机上所能表示的0,1上的数又是有限的,因此,这种方法产生的随机数序列就不可能不出现无限重复。一旦出现这样的n,n (n n ),使得下面等式成立: 随机数序列便出现了周期性的循环现象。对于k=1的情况,只要有一个随机数重复,其后面的随机数全部重复,这与随机数的要求是不相符
8、的。,2 伪随机数两个问题,由于这两个问题的存在,常称用数学方法产生的随机数为伪随机数。对于以上存在的两个问题,作如下具体分析。 关于第一个问题,不能从本质上加以改变,但只要递推公式选得比较好,随机数间的相互独立性是可以近似满足的。至于第二个问题,则不是本质的。因为用蒙特卡罗方法解任何具体问题时,所使用的随机数的个数总是有限的,只要所用随机数的个数不超过伪随机数序列出现循环现象时的长度就可以了。 用数学方法产生的伪随机数容易在计算机上得到,可以进行复算,而且不受计算机型号的限制。因此,这种方法虽然存在着一些问题,但仍然被广泛地在计算机上使用,是在计算机上产生伪随机数的主要方法。,2 伪随机数两
9、个问题,发生周期性循环现象的伪随机数的个数称为伪随机数的周期。对于前面介绍的情况,伪随机数的周期为nn。 从伪随机数序列的初始值开始,到出现循环现象为止,所产生的伪随机数的个数称为伪随机数的最大容量。前面的例子中,伪随机数的最大容量为n 。,2 伪随机数周期和最大容量,乘同余方法是由Lehmer在1951年提出来的,它的一般形式是:对于任一初始值x1,伪随机数序列由下面递推公式确定: 其中a为常数。,2 伪随机数乘同余方法,对于任意正整数M,根据数论中的标准分解定理,总可以分解成如下形式: 其中P0=2,P1, Pr表示不同的奇素数,0表示非负整数,1,r表示正整数。a无论取什么值,乘同余方法
10、的最大容量的上界为: 的最小公倍数。其中:,2 伪随机数乘同余方法(上限),关于a与x1的取值,如果a与x1满足如下条件: 对于 , x1与M互素,则乘同余方法产生的伪随机数序列的最大容量达到最大可能值(M)。,2 伪随机数乘同余方法,乘同余方法在计算机上的使用,为了便于在计算机上使用,通常取 : =2s 其中s为计算机中二进制数的最大可能有效位数 x1= 奇数 a = 52k+1 其中k为使52k+1在计算机上所能容纳的最大整数,即a为计算机上所能容纳的5的最大奇次幂。一般地,s=32时,a=513;s=48,a=515等。伪随机数序列的最大容量(M)=2s-2 。 乘同余方法是使用的最多、
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 蒙特卡罗 随机数
链接地址:https://www.31doc.com/p-2653208.html