《蒙特卡罗方法》PPT

2.1蒙特卡洛方法(MonteCarlosimulation)引言(introduction)MC基本思想MC收敛性及误差MC特点1完整版ppt一、两种自然现象确定性的：日月升落，四季轮回，磁石吸铁不确定的：掷骰子，炮弹落点，考试成绩二、两种研究方法

确定性问题:解析,有限元,分子动力学,Monte-Carlo

随机性问题：Monte-Carlo，布朗动力学1.引言2完整版ppt

计算机模拟：(1)随机模拟方法或统计试验方法，又称蒙特卡洛(MonteCarlo)方法。它是通过不断产生随机数序列来模拟过程。自然界中有的过程本身就是随机的过程，物理现象中如粒子的衰变过程、粒子在介质中的输运过程等。当然蒙特卡洛方法也可以借助慨率模型来解决不直接具有随机性的确定性问题。(2)确定性模拟方法。它是通过数值求解一个个的粒子运动方程来模拟整个系统的行为。在统计物理中称为分子动力学（MolecularDynamics）方法。此外,近年来还发展了神经元网络方法和原胞自动机方法。1.引言3完整版ppt

MC方法，分为三种类型：（1）直接蒙特卡洛模拟。它采用随机数序列来模拟复杂随机过程的效应。（2）蒙特卡洛积分。这是利用随机数序列计算积分的方法。积分维数越高，该方法的积分效率就越高。（3）Metropolis蒙特卡洛模拟。这种模拟是以所谓“马尔科夫”（Markov）鏈的形式产生系统的分布序列。该方法可以使我们能够研究经典和量子多粒子系统的问题。1.引言4完整版pptMonteCarlo方法：亦称统计模拟方法，statisticalsimulationmethod

利用随机数进行数值模拟的方法MonteCarlo名字的由来：是由Metropolis在二次世界大战期间提出的：Manhattan计划，研究与原子弹有关的中子输运过程；MonteCarlo是摩纳哥（monaco)的首都，该城以赌博闻名NicholasMetropolis(1915-1999)Monte-Carlo,Monaco1.引言5完整版pptMonteCarlo方法简史简单地介绍一下MonteCarlo方法的发展历史1、Buffon投针实验：1768年，法国数学家ComtedeBuffon利用投针实验估计的值dL1.引言6完整版ppt1.引言7完整版ppt1.引言8完整版ppt1.引言9完整版ppt2、1930年，EnricoFermi利用MonteCarlo方法研究中子的扩散，并设计了一个MonteCarlo机械装置，Fermiac,用于计算核反应堆的临界状态3、VonNeumann是MonteCarlo方法的正式奠基者,他与StanislawUlam合作建立了概率密度函数、反累积分布函数的数学基础，以及伪随机数产生器。在这些工作中，StanislawUlam意识到了数字计算机的重要性合作起源于Manhattan工程：利用ENIAC(ElectronicNumericalIntegratorandComputer)计算产额1.引言10完整版pptMC的统计基础-随机变量及其分布

定义随机变量X={xi}，概率分布F(x)是X的函数

离散分布：

连续分布：

f(x)为概率分布密度

数学期望：和

方差：1.引言11完整版pptMC的统计基础-大数定理设x1,x2,,xn,为一随机变量序列,相互独立,具有同样分布,且E(xi)=a存在,则对任意小量>0,有

统计含义：不论随机变量的分布如何,只要n足够大,则算术平均与数学期望值可无限接近,也就是说,算术平均以几率收敛于其数学期望值.1.引言12完整版pptMC的统计基础-中心极限定理设x1,x2,,xn,为一随机变量序列,相互独立,具有同样分布,且E(xi)=μ,D(xi)=2存在,则统计含义：如果一个随机变量X，是由大量相互独立的因素的影响形成的，其中每一个因素在总的影响中所起作用都是微小的（被稀释），这种随机变量近似地服从正态分布1.引言13完整版pptMC的基础–随机过程1定义，X＝X(x,t)随时间变化的随机变量，或时间随机变量序列2按分布函数，分类a)平稳随机过程b)Markov过程c)独立增量随机过程d)独立随机过程1.引言14完整版pptMC的基础-平稳随机过程1定义：X(t),如果它的n维（n个状态）概率密度与初始分布无关，即对任何n和t’满足fx(x1,x2,…,xn;t1,t2,..,tn)=fx(x1,x2,…,xn;t1+t’,t2+t’,..,tn+t’)含义：平稳随机过程的统计特性与所选择的时间起点无关，不随时间的推移而变化，即是“时间平稳的”。2统计特性

1）一维概率密度与时间无关2）二维概率密度，只与两个状态对应的时间间隔Δt有关，其时间自相关仅是Δt的函数3应用：电阻的热噪声，电子信号，…1.引言15完整版pptMC的基础-Markov链1定义：在可列个离散状态x1,x2,..xN和离散时间t1,t2,..tn,若随机过程在tm+k时刻变成任一状态xi的概率，只与tm时刻的状态有关(无后效)，而与此前状态无关，称离散随机序列P{Xm+k=xi,m+k|Xm=xi,m,Xm-1=xi,m-1,..,X1=xi,1}=P{Xm+k=xi,m+k|Xm=xi,m}为Markov链.

2概率转移矩阵pij条件概率：pij(m,m+k)＝P{Xm+k=xj|Xm=xi}不依赖于m的pij称，齐次Markov链

3应用：统计物理Ising模型（固态相变，液固相变，…）1.引言16完整版pptMC的模拟方法（步骤）1.

确定统计方案(Xi,)2.确定随机变量Xi的概率分布：fi(x)3.根据fi(x)，对Xi抽样：Xi-->Ri4.编程进行计算机模拟5.获得统计量1.引言17完整版pptMC的模拟方法－1确定统计方案1确定统计模型1)现象模型随机现象Y＝Y(Xi)，Xi={X1,X2,X3,…}2)确定随机变量Xi的分布特征fi(x)平均分布，指数分布，正态分布，Γ分布…2确定统计量1.引言18完整版pptMC的模拟方法－2常见的概率分布其他还有：Γ分布，β分布，χ2分布，t分布，Poisson分布…1.引言19完整版pptMC的模拟方法－3概率抽样方法1

直接抽样法：反函数法、函数变换法

2间接抽样法：舍选法,值序抽样…设g(x,y)为X,Y的联合密度函数

如有某一分布

H(x)<M为任意函数，请对其抽样。舍选抽样示意图

1.引言20完整版pptMC的模拟方法－4随机数的产生1基本随机数，2随机数和“伪随机数”

伪随机数（序列）重演周期应足够长3产生办法

同余法、混合同余法、组合同余法等4计算机实现

a)自定义子程序，b)调用内部函数强调：伪随机数的好坏，直接影响统计结果，应予重视。

1.引言21完整版pptMonteCarlo模拟在物理研究中的作用1.引言22完整版pptMonteCarlo模拟的步骤：根据欲研究的物理系统的性质，建立能够描述该系统特性的理论模型，导出该模型的某些特征量的概率密度函数；从概率密度函数出发进行随机抽样，得到特征量的一些模拟结果；对模拟结果进行分析总结，预言物理系统的某些特性。1.引言23完整版ppt注意以下两点：MonteCarlo方法与数值解法的不同:MonteCarlo方法利用随机抽样的方法来求解物理问题;数值解法:从一个物理系统的数学模型出发,通过求解一系列的微分方程来的导出系统的未知状态;MonteCarlo方法并非只能用来解决包含随机的过程的问题:许多利用MonteCarlo方法进行求解的问题中并不包含随机过程例如:用MonteCarlo方法计算定积分.

对这样的问题可将其转换成相关的随机过程,然后用MonteCarlo方法进行求解1.引言24完整版pptMonteCarlo算法的主要组成部分概率密度函数(pdf)—必须给出描述一个物理系统的一组概率密度函数;随机数产生器—能够产生在区间[0,1]上均匀分布的随机数抽样规则—如何从在区间[0,1]上均匀分布的随机数出发,随机抽取服从给定的pdf的随机变量;模拟结果记录—记录一些感兴趣的量的模拟结果误差估计—必须确定统计误差（或方差）随模拟次数以及其它一些量的变化；减少方差的技术—利用该技术可减少模拟过程中计算的次数；并行和矢量化—可以在先进的并行计算机上运行的有效算法1.引言25完整版pptMonteCarlo模拟的应用：自然现象的模拟：宇宙射线在地球大气中的传输过程；高能物理实验中的核相互作用过程；实验探测器的模拟数值分析：利用MonteCarlo方法求积分1.引言26完整版ppt271.针对实际问题建立一个简单且便于实现的概率统计模型，使所求的量（或解）恰好是该模型某个指标的概率分布或者数字特征。2.对模型中的随机变量建立抽样方法，在计算机上进行模拟测试，抽取足够多的随机数，对有关事件进行统计3.对模拟试验结果加以分析，给出所求解的估计及其精度(方差)的估计4.必要时，还应改进模型以降低估计方差和减少试验费用，提高模拟计算的效率2.MC基本思路27完整版ppt

当问题可以抽象为某个确定的数学问题时，应当首先建立一个恰当的概率模型，即确定某个随机事件A或随机变量X，使得待求的解等于随机事件出现的概率或随机变量的数学期望值。然后进行模拟实验，即重复多次地模拟随机事件A或随机变量X。最后对随机实验结果进行统计平均，求出A出现的频数或X的平均值作为问题的近似解。2.MC基本思想28完整版ppt二十世纪四十年代中期，由于科学技术的发展和电子计算机的发明，蒙特卡罗方法作为一种独立的方法被提出来，并首先在核武器的试验与研制中得到了应用。但其基本思想并非新颖，人们在生产实践和科学试验中就已发现，并加以利用。两个例子

例1.蒲丰氏问题

例2.射击问题（打靶游戏）计算机模拟试验过程2.MC基本思想29完整版ppt例1.蒲丰氏问题为了求得圆周率π值，在十九世纪后期，有很多人作了这样的试验：将长为2l的一根针任意投到地面上，用针与一组相间距离为2a（l＜a）的平行线相交的频率代替概率P，再利用准确的关系式：求出π值其中Ｎ为投计次数，n为针与平行线相交次数。这就是古典概率论中著名的蒲丰氏问题。2.MC基本思想30完整版ppt

一些人进行了实验，其结果列于下表：实验者年份投计次数π的实验值沃尔弗(Wolf)185050003.1596斯密思(Smith)185532043.1553福克斯(Fox)189411203.1419拉查里尼(Lazzarini)190134083.14159292.MC基本思想31完整版ppt例2.射击问题（打靶游戏）

设r表示射击运动员的弹着点到靶心的距离，ｇ(r)表示击中r处相应的得分数（环数），f(r)为该运动员的弹着点的分布密度函数，它反映运动员的射击水平。该运动员的射击成绩为

用概率语言来说，<g>是随机变量ｇ(r)的数学期望，即

2.MC基本思想32完整版ppt现假设该运动员进行了Ｎ次射击，每次射击的弹着点依次为r1，r2，…，rN，则Ｎ次得分g(r1)，g(r2)，…，g(rN)的算术平均值代表了该运动员的成绩。换言之，为积分<g>的估计值，或近似值。在该例中，用Ｎ次试验所得成绩的算术平均值作为数学期望<g>的估计值（积分近似值）。

2.MC基本思想33完整版ppt2.MC基本思想——数值积分34完整版ppt与一般的数值积分方法比较，MonteCarlo方法具有以下优点：2.MC基本思想——数值积分35完整版ppt由以上例子可以看出，当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望，或者是与概率、数学期望有关的量时，通过某种试验的方法，得出该事件发生的频率，或者该随机变量若干个具体观察值的算术平均值，通过它得到问题的解。这就是蒙特卡罗方法的基本思想。当随机变量的取值仅为1或0时，它的数学期望就是某个事件的概率。或者说，某种事件的概率也是随机变量（仅取值为1或0）的数学期望。

2.MC基本思想36完整版ppt因此，可以通俗地说，蒙特卡罗方法是用随机试验的方法计算积分，即将所要计算的积分看作服从某种分布密度函数f(r)的随机变量ｇ(r)的数学期望

通过某种试验，得到Ｎ个观察值r1，r2，…，rN（用概率语言来说，从分布密度函数f(r)中抽取Ｎ个子样r1，r2，…，rN，），将相应的Ｎ个随机变量的值g(r1)，g(r2)，…，g(rN)的算术平均值作为积分的估计值（近似值）。

2.MC基本思想37完整版ppt为了得到具有一定精确度的近似解，所需试验的次数是很多的，通过人工方法作大量的试验相当困难，甚至是不可能的。因此，蒙特卡罗方法的基本思想虽然早已被人们提出，却很少被使用。本世纪四十年代以来，由于电子计算机的出现，使得人们可以通过电子计算机来模拟随机试验过程，把巨大数目的随机试验交由计算机完成，使得蒙特卡罗方法得以广泛地应用，在现代化的科学技术中发挥应有的作用。

2.MC基本思想38完整版ppt计算机模拟试验过程

计算机模拟试验过程，就是将试验过程（如投针，射击）化为数学问题，在计算机上实现。以上述两个问题为例，分别加以说明。例1.蒲丰氏问题例2.射击问题（打靶游戏）由上面两个例题看出，蒙特卡罗方法常以一个“概率模型”为基础，按照它所描述的过程，使用由已知分布抽样的方法，得到部分试验结果的观察值，求得问题的近似解。2.MC基本思想39完整版ppt例１．蒲丰氏问题设针投到地面上的位置可以用一组参数（x,θ）来描述，x为针中心的坐标，θ为针与平行线的夹角，如图所示。任意投针，就是意味着x与θ都是任意取的，但x的范围限于［0，a］，夹角θ的范围限于［0，π］。在此情况下，针与平行线相交的数学条件是针在平行线间的位置2.MC基本思想40完整版ppt如何产生任意的（x,θ）？x在［0，a］上任意取值，表示x在［0，a］上是均匀分布的，其分布密度函数为：类似地，θ的分布密度函数为：因此，产生任意的（x,θ）的过程就变成了由f1(x)抽样x及由f2(θ)抽样θ的过程了。由此得到：其中ξ1，ξ2均为（0,1）上均匀分布的随机变量。2.MC基本思想41完整版ppt每次投针试验，实际上变成在计算机上从两个均匀分布的随机变量中抽样得到（x,θ），然后定义描述针与平行线相交状况的随机变量s(x,θ)，为如果投针Ｎ次，则是针与平行线相交概率Ｐ的估计值。事实上，于是有2.MC基本思想42完整版ppt例２．射击问题

设射击运动员的弹着点分布为用计算机作随机试验（射击）的方法为，选取一个随机数ξ，按右边所列方法判断得到成绩。这样，就进行了一次随机试验（射击），得到了一次成绩ｇ(r)，作Ｎ次试验后，得到该运动员射击成绩的近似值环数78910概率0.10.10.30.52.MC基本思想43完整版ppt蒙特卡罗方法作为一种计算方法，其收敛性与误差是普遍关心的一个重要问题。收敛性误差减小方差的各种技巧效率3.MC收敛性及误差44完整版ppt收敛性

由前面介绍可知，蒙特卡罗方法是由随机变量X的简单子样X1，X2，…，XN的算术平均值：作为所求解的近似值。由大数定律可知，如X1，X2，…，XN独立同分布，且具有有限期望值（E(X)<∞），则即随机变量X的简单子样的算术平均值，当子样数Ｎ充分大时，以概率1收敛于它的期望值E(X)。3.MC收敛性及误差45完整版ppt误差蒙特卡罗方法的近似值与真值的误差问题，概率论的中心极限定理给出了答案。该定理指出，如果随机变量序列X1，X2，…，XN独立同分布，且具有有限非零的方差σ2，即f(X)是X的分布密度函数。则3.MC收敛性及误差46完整版ppt当N充分大时，有如下的近似式其中α称为置信度，1－α称为置信水平。这表明，不等式近似地以概率1－α成立，且误差收敛速度的阶为。通常，蒙特卡罗方法的误差ε定义为上式中与置信度α是一一对应的，根据问题的要求确定出置信水平后，查标准正态分布表，就可以确定出。3.MC收敛性及误差47完整版ppt下面给出几个常用的α与的数值：

关于蒙特卡罗方法的误差需说明两点：第一，蒙特卡罗方法的误差为概率误差，这与其他数值计算方法是有区别的。第二，误差中的均方差σ是未知的，必须使用其估计值来代替，在计算所求量的同时，可计算出。α0.50.050.003

0.67451.9633.MC收敛性及误差48完整版ppt减小方差的各种技巧

显然，当给定置信度α后，误差ε由σ和N决定。要减小ε，或者是增大N，或者是减小方差σ2。在σ固定的情况下，要把精度提高一个数量级，试验次数N需增加两个数量级。因此，单纯增大N不是一个有效的办法。另一方面，如能减小估计的均方差σ，比如降低一半，那误差就减小一半，这相当于N增大四倍的效果。因此降低方差的各种技巧，引起了人们的普遍注意。后面课程将会介绍一些降低方差的技巧。3.MC收敛性及误差49完整版ppt效率一般来说，降低方差的技巧，往往会使观察一个子样的时间增加。在固定时间内，使观察的样本数减少。所以，一种方法的优劣，需要由方差和观察一个子样的费用（使用计算机的时间）两者来衡量。这就是蒙特卡罗方法中效率的概念。它定义为，其中c

是观察一个子样的平均费用。显然越小，方法越有效。3.MC收敛性及误差50完整版ppt优点能够比较逼真地描述具有随机性质的事物的特点及物理实验过程。受几何条件限制小。收敛速度与问题的维数无关。具有同时计算多个方案与多个未知量的能力。误差容易确定。程序结构简单，易于实现。缺点收敛速度慢。误差具有概率性。在粒子输运问题中，计算结果与系统大小有关。4.MC特点51完整版ppt能够比较逼真地描述具有随机性质的事物的特点及物理实验过程从这个意义上讲，蒙特卡罗方法可以部分代替物理实验，甚至可以得到物理实验难以得到的结果。用蒙特卡罗方法解决实际问题，可以直接从实际问题本身出发，而不从方程或数学表达式出发。它有直观、形象的特点。4.MC特点52完整版ppt受几何条件限制小在计算s维空间中的任一区域Ds上的积分时，无论区域Ds的形状多么特殊，只要能给出描述Ds的几何特征的条件，就可以从Ds中均匀产生N个点，得到积分的近似值。其中Ds为区域Ds的体积。这是数值方法难以作到的。另外，在具有随机性质的问题中，如考虑的系统形状很复杂，难以用一般数值方法求解，而使用蒙特卡罗方法，不会有原则上的困难。4.MC特点53完整版ppt收敛速度与问题的维数无关由误差定义可知，在给定置信水平情况下，蒙特卡罗方法的收敛速度为，与问题本身的维数无关。维数的变化，只引起抽样时间及估计量计算时间的变化，不影响误差。也就是说，使用蒙特卡罗方法时，抽取的子样总数N与维数s无关。维数的增加，除了增加相应的计算量外，不影响问题的误差。这一特点，决定了蒙特卡罗方法对多维问题的适应性。而一般数值方法，比如计算定积分时，计算时间随维数的幂次方而增加，而且，由于分点数与维数的幂次方成正比，需占用相当数量