蒙特卡罗算法经典算法教学课件

从Buffor投针问题谈起Buffon投针问题:平面上画很多平行线,间距为a.向此平面投掷长为l(<a)的针,求此针与任一平行线相交的概率p随机投针可以理解成针的中心点与最近的平行线的距离X是均匀地分布在区间[0,a/2]上的r.V.,针与平行线的夹角Φ是均匀地分布在区间[0,n]上的r.V.,且X与Φ相互独立,于是针与平行线相交的充要条件为X≤sin①,即相交A={o:X≤sinΦEvaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyLBuffon投针问题于是有p=P(X≤-sinΦ)q若我们独立重复地作n次投针试验,记2(A)为A发生的次数。fn(A)为A在n次中出现的频率。假如我们取f(A)作为p=P(A)的估计,即p=fn(A)。然后取亓作为丌的估计。根据大数定律,当n→>∞时,p=f(A)-“af,(a)从而有亓P>丌。这样可以用随机试验的方法求得丌的估计。历史上af(a)有如下的试验结果Evaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL试验者时间(年)针长投针次数相交次数z的估计值18500.80500025323.15956Smith18553204Fox18840.754893.15951Lazzarini19250833408118083.14159292Evaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL数值积分问题计算积分a=「f(x)dx=Ef(X)我们可以将此积分看成f(x)的数学期望。其中X~U[0,1](均匀分布)。于是可以将上式积分看作是f(X的数学期望.若{U,1≤k≤n}为iidt,u0,1则可以取an=∑f(U作为a的估计由大数定律,可以保证收敛性,即a,>awithprobabilityasn>00这表明可以用随机模拟的方法计算积分Evaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyLMontecarlo数值积分的优点与一般的数值积分方法比较,Montecarlo方法具有以下优点1.一般的数值方法很难推广到高维积分的情形,而Montecarlo方法很容易推广到高维情形2.一般的数值积分方法的收敛阶为On2),而由中心极限定理可以保证Montecarlo方法的收敛阶为O(n12)。此收敛阶与维数无关,且在维时明显优于一般的数值方法。Evaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL随杋模拟计算的基本思路1.针对实际问题建立一个简单且便于实现的概率统计模型,使所求的量(或解)恰好是该模型某个指标的概率分布或者数字特征。2对模型中的随机变量建立抽样方法,在计算机上进行模拟测试,抽取足够多的随机数,对有关事件进行统计3.对模拟试验结果加以分析,给出所求解的估计及其精度(方差)的估计4.必要时,还应改进模型以降低估计方差和减少试验费用,提高模拟计算的效率Evaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL随机数的生成1.蒙特卡罗模拟的关键是生成优良的随机数。2.在计算机实现中,我们是通过确定性的算法生成随机数,所以这样生成的序列在本质上不是随机的,只是很好的模仿了随机数的性质(如可以通过统计检验)。我们通常称之为伪随机数(pseudorandomnumbers)而大多数概率分布的随机数产生均基于均匀分布U(0,1)的随机数Evaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyLU(0,1)随机数的生成个简单的随机数生成器modml1-1=x+1/m其中x,a,m均为整数,x可以任意选取。随机数生成器的一般形式:x1=f(x1),l21=8(x1)Evaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL个简单的例子x,=6xmod11u,=x.,/11(a=6,m=11)当x=1时得到序列:,6,3,7,9,10,5,8,4,2,1,6,3.如果令a=3,x=1,得到序列:1,3,9,5,4,1,3,9.如果令a=3,x0=2,得到序列:2.6.7,10.8.2.6.Evaluadononly.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL个简单的例子(续)上面的例子中,第一个随机数生成器的周期长度是10,而后两个生成器的周期长度只有它的一半。我们自然希望生成器的周期越长越好,这样我们得到的分布就更接近于真实的均匀分布在给定m的情况下,生成器的周期与a和初值x(种子)选