Monte Carlo Simulation Methods.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,蒙特卡罗模拟方法,Monte Carlo Simulation Methods,2,主要内容,1.,各种随机数的生成方法,.,2.MCMC,方法,.,3,蒙特卡罗模拟是一种随机模拟方法。以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系，用电子计算机实现统计模拟或抽样，以获得问题的近似解。为象征性地表明这一方法的概率统计特征，故借用赌城蒙特卡罗命名。又称统计模拟法、随机抽样技术。由,S.M.,乌拉姆和,J.,冯,诺伊曼在,20,世纪,40,年代为研制核武器而首先提出。在这之前，蒙特卡罗方法就已经存在。,1777,年，法国,Buffon,提出用投针实验的方法求圆周率。这被认为是蒙特卡罗方法的起源。,4,从,Buffon,投针问题谈起,5,Buffon,投针问题,6,试验者,时间,(,年,),针长,投针次数,相交次数,的估计值,Wolf,1850,0.80,5000,2532,3.15956,Smith,1855,0.60,3204,1218,3.15665,Fox,1884,0.75,1030,489,3.15951,Lazzarini,1925,0.83,3408,1808,3.14159292,7,数值积分问题,8,Monte Carlo,数值积分的优点,与一般的数值积分方法比较，,Monte Carlo,方法,具有以下优点：,9,随机模拟计算的基本思路,1.,针对实际问题建立一个简单且便于实现的概率统计模,型，使所求的量（或解）恰好是该模型某个指标的概率分布或者数字特征。,2.,对模型中的随机变量建立抽样方法，在计算机上进行,模拟测试，抽取足够多的随机数，对有关事件进行统计,3.,对模拟试验结果加以分析，给出所求解的估计及其精,度,(,方差,),的估计,4.,必要时，还应改进模型以降低估计方差和减少试验费,用，提高模拟计算的效率,10,随机数的生成,1.,蒙特卡罗模拟的关键是生成优良的随机数。,2.,在计算机实现中,我们是通过确定性的算法生成,随机数,所以这样生成的序列在本质上不是随机,的,只是很好的模仿了随机数的性质,(,如可以通过,统计检验,),。我们通常称之为伪随机数,(pseudo-random numbers),。,3.,在模拟中，我们需要产生各种概率分布的随机数，而大多数概率分布的随机数产生均基于均匀分布,U(0,1),的随机数。,11,U(0,1),随机数的生成,一个简单的随机数生成器：,12,一个简单的例子,13,一个简单的例子,(,续,),上面的例子中，第一个随机数生成器的周期长度是,10,，而后两个生成器的周期长度只有它的一半。我们自然希望生成器的周期越长越好，这样我们得到的分布就更接近于真实的均匀分布。,14,线性同余生成器,(Linear Congruential Generator),15,常用的线性同余生成器,Modulus m,Multiplier a,Reference,231-1,=2147483647,16807,Lewis,Goodman,and Miller,2147483647,39373,LEcuyer,2147483647,742938285,Fishman and Moore,2147483647,950706376,Fishman and Moore,2147483647,1226874159,Fishman and Moore,2147483399,40692,LEcuyer,2147483563,40014,LEcuyer,16,复杂一些的生成器（一）,1.Combining Generators:,17,复杂一些的生成器（二）,2.Multiple recursive generator,18,算法实现,许多程序语言中都自带生成随机数的方法，如,c,中的,random(),函数，,Matlab,中的,rand(),函数等。,但这些生成器生成的随机数效果很不一样，比如,c,中的函数生成的随机数性质就比较差，如果用,c,，最好自己再编一个程序。,Matlab,中的,rand(),函数，经过了很多优化。可以产生性质很好的随,机数，可以直接利用。,19,由,rand(),函数生成的,U0,1,随机数,20,由,rand,函数生成的,2,维随机点,21,从,U(0,1),到其它概率分布的随机数,U(0,1),的均匀分布的随机数，是生成其他概率,分布随机数的基础，下面我们主要介绍两种将,U(0,1),随机数转换为其他分布的随机数的方法。,1.,逆变换方法,(Inverse Transform Method),2.,舍取方法,(Acceptance-Rejection Method),22,Inverse Transform Method,23,Inverse Transform Method,24,几个具体例子（一）,25,几个具体例子（二）,26,几个具体例子（三）,27,标准正态分布随机数的生成,正态分布是概率统计中最重要的分布，在此,我们着重讨论如何生成标准正态分布随机数。,引理：,28,Box-Muller,算法,29,逆变换方法（一）,我们无法通过具体的数学表达式计算正态分布函数,的逆函数，我们必须通过数值的方法逼近正态函数,下面我们介绍,Beasley-Springer-Moro,方法。,30,逆变换方法（二）,31,逆变换方法（三）,a0=2.50662823884,b0=-8.47351093090,a1=-18.61500062529,b1=23.08336743743,a2=41.39119773534,b2=-21.06224101826,a3=-25.44106049637,b3=3.13082909833,c0=0.3374754822726147,c5=0.0003951896511919,c1=0.9761690190917186,c6=0.0000321767881768,c2=0.1607979714918209,c7=0.0000002888167364,c3=0.0276438810333863,c8=0.0000003960315187,c4=0.0038405729373609,在,matlab,中可以直接通过,norminv(),函数直接,计算标准正态分布函数的逆。,32,Matlab,生成的正态随机数,33,Acceptance-Rejection Method,（一）,Acceptance-Rejection,方法最早由,Von Neumann,提出，现在已经广泛应用于各种随机数的生成。,基本思路：,通过一个容易生成的概率分布,g,和一个取舍,准则生成另一个与,g,相近的概率分布,f,。,34,Acceptance-Rejection Method,（二）,具体步骤：,35,Acceptance-Rejection Method,（三）,下面我们验证由上述步骤生成的随机数,Y,确实,具有密度函数,f(x),36,Acceptance-Rejection Method,（四）,所以为了提高舍取法的效率，我们应该使,c,的取值尽,可能的小，也就是使,f,和,g,的分布更为相近。,37,几个具体例子（一）,38,几个具体例子（一）,39,几个具体例子（二）,40,几个具体例子（二）,41,随机向量的抽样方法（一）,42,随机向量的抽样方法（二）,43,生成多维正态随机数的方法（一）,44,生成多维正态随机数的方法（二）,生成多维正态随机数的具体步骤：,45,参考数学建模书了解,monte carlo,的应用,搜索,bayesian,了解基于,monte carlo,的,bayesian,应用,46,马氏链在,Monte Carlo,随机模拟中的应用,定义,为要模拟服从给定分布的随机变量,用生成一个易于,实现的不可约遍历链 作为随机样本,使其平稳分布为,的方法，称为,马氏链蒙特卡罗方法,.,蒙特卡罗方法的一个首要步骤是产生服从给定的概率分布函数,的随机变量,(,或称为随机样本,),由概率论知识,熟知下面的结论,.,47,引理,生成随机变量,U,使其分布满足,U,0,1,记为,U,U,0,1,F,(,x,),是给定的一个分布函数,记,为,F,(,x,),的反函数,则,X,=,F,-1,(,U,),分布函数为,F,(,x,).,48,49,50,米特罗波利斯,(Metropolis),等人在,1953,年最早,给出了通过生成一马氏链实现从分布 中采,样,(,生成相关的样本,),这一重要基本思想,.,随后,哈斯汀,(Hastings),将其推广到更一般的形式,.,下面仅叙述状态空间,S,为至多可数的情形,:,51,52,53,Markov chain Monte Carlo(MCMC),问题提出：,54,MCMC,方法的基本思路,MCMC,是一种简单有效的计算方法，在统计物理，,Bayes,统计计算，显著性检验，极大似然估计等领,域都有着广泛的应用。,基本思路：,55,概率转移核的构造（一）,MCMC,的方法有很多，在此我们只介绍,Metropolis-Hastings,方法。,基本思路：,56,概率转移核的构造（二）,57,概率转移核的构造（三）,Metropolis-Hastings,算法：,58,59,（续上页证明）,60,Metropolis-Hastings,算法的具体步骤,61,几种常用的,q(x,x),（一）,1.Metropolis,选择：,62,几种常用的,q(x,x),（二）,2.,独立抽样：,63,拟蒙特卡罗方法,另一类形式与,Monte Carlo,方法相似，但理论基础不同的方法,“,拟蒙特卡罗方法”,(Quasi-Monte Carlo,方法,),近年来也获得迅速发展。我国数学家华罗庚、王元提出的“华,王”方法即是其中的一例。这种方法的基本思想是“用确定性的超均匀分布序列,(,数学上称为,Low Discrepancy Sequences),代替,Monte Carlo,方法中的随机数序列。对某些问题该方法的实际速度一般可比,Monte Carlo,方法高数百倍，并可计算精确度。,