蒙特卡洛方法

蒙特卡洛模拟方法主讲人：李彬大连大学数学建模工作室2013年9月2日2013年9月2日大连大学数学建模工作室蒙特卡洛模拟方法蒙特卡罗方法概述1蒙特卡洛方法思想框图2相关案例分析及其软件操作3蒙特卡洛的优缺点及其适用范围42013年9月2日大连大学数学建模工作室MonteCarlo方法的发展历史早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。从方法特征的角度来说可以一直追溯到18世纪后半叶的蒲丰（Buffon）随机投针试验，即著名的蒲丰问题。2013年9月2日大连大学数学建模工作室MonteCarlo方法的发展历史1777年，古稀之年的蒲丰在家中请来好些客人玩投针游戏（针长是线距之半），他事先没有给客人讲与π有关的事。客人们虽然不知道主人的用意，但是都参加了游戏。他们共投针2212次，其中704次相交。蒲丰说，2212/704=3.142，这就是π值。这着实让人们惊喜不已。2013年9月2日大连大学数学建模工作室例.蒲丰氏问题设针投到地面上的位置可以用一组参数（x,θ）来描述,x为针中心的坐标,θ为针与平行线的夹角,如图所示。任意投针，就是意味着x与θ都是任意取的，x的范围限于［0，a/2］，夹角θ的范围限于［0，π］。2013年9月2日大连大学数学建模工作室蒲丰氏问题数学基础上述问题简图：2013年9月2日大连大学数学建模工作室分析知针与平行线相交的充要条件是：其中：建立直角坐标系，上述条件在坐标系下将是曲线所围成的曲边梯形区域。由几何概率知：sin21x020，axx，aladGgP22sin210的面积的面积蒲丰氏问题数学基础2013年9月2日大连大学数学建模工作室拉查里尼（Lazzarini）投计次数：3408次pi的实验值：3.1415921850185518941901历史上的实验斯密思（Smith）投计次数：3204次pi的实验值：3.1553福克斯（Fox）投计次数：1120次pi的实验值：3.1419沃尔弗（Wolf）投计次数：5000次pi的实验值：3.1596MonteCarlo方法的发展历史2013年9月2日大连大学数学建模工作室MonteCarlo方法的发展历史20世纪四十年代，由于电子计算机的出现，利用电子计算机可以实现大量的随机抽样的试验，使得用随机试验方法解决实际问题才有了可能。其中作为当时的代表性工作便是在第二次世界大战期间，为解决原子弹研制工作中，裂变物质的中子随机扩散问题，美国数学家冯.诺伊曼和乌拉姆等提出蒙特卡罗模拟方法.由于当时工作是保密的，就给这种方法起了一个代号叫蒙特卡罗，即摩纳哥的一个赌城的名字。用赌城的名字作为随机模拟的名称，既反映了该方法的部分内涵，又易记忆，因而很快就得到人们的普遍接受。2013年9月2日大连大学数学建模工作室MonteCarlo方法的基本思想蒙特卡罗方法又称计算机随机模拟方法。它是以概率统计理论为基础的一种方法。由蒲丰实验可以知道，当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望，或者是与概率、数学期望有关的量时。通过某种试验的方法，得出该事件发生的频率，或者该随机变量若干个具体观察值的算术平均值，通过它得到问题的解。这就是蒙特卡洛方法的基本思想。2013年9月2日大连大学数学建模工作室MonteCarlo方法的基本思想蒙特卡罗方法又称计算机随机模拟方法。它是以概率统计理论为基础的一种方法。由蒲丰实验可以知道，当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望，或者是与概率、数学期望有关的量时。通过某种试验的方法，得出该事件发生的频率，或者该随机变量若干个具体观察值的算术平均值，通过它得到问题的解。这就是蒙特卡洛方法的基本思想。2013年9月2日大连大学数学建模工作室MonteCarlo方法的思想框图建立概率统计模型收集模型中风险变量的数据，确定风险因数的分布函数根据风险分析的精度要求，确定模拟次数N建立对随机变量的抽样方法，产生随机数N个样本值根据随机数在各风险变量的概率分布中随机抽样，代入第一步中建立的数学模型统计分析，估计均值，标准差NNN2013年9月2日大连大学数学建模工作室MonteCarlo方法的框图实例某投资项目每年所得盈利额A由投资额P、劳动生产率L、和原料及能源价格Q三个因素。dcQbLaPA2122013年9月2日大连大学数学建模工作室MonteCarlo方法的思想框图实例收集P,L,Q数据，确定分布函数f(P),f(L),f(Q)模拟次数N；根据分布函数，产生随机数建立对随机变量的抽样方法，产生随机数产生N个A值抽取P,L,Q一组随机数，代入模型统计分析，估计均值，标准差NNNdcQbLaPA2122013年9月2日大连大学数学建模工作室随机数的定义及其性质随机数的定义用MonteCarlo方法模拟某过程时，需要产生各种概率分布的随机变量。最简单、最基本、最重要的随机变量是在［0，1］上均匀分布的随机变量。由该分布抽取的简单子样称为随机数序列，其中每一个体称为随机数。随机数属于一种特殊的由已知分布的随机抽样问题。随机数是随机抽样的基本工具。［0，1］上均匀分布（单位均匀分布），其分布密度函数为：分布函数为：其他,010,1)(xxf1,110,0,0)(xxxxxF2013年9月2日大连大学数学建模工作室由于随机数在蒙特卡罗方法中占有极其重要的位置，我们用专门的符号ξ表示。由随机数序列的定义可知，ξ1，ξ2，…是相互独立且具有相同单位均匀分布的随机数序列。也就是说，独立性、均匀性是随机数必备的两个特点。随机数具有非常重要的性质：对于任意自然数s，由s个随机数组成的s维空间上的点（ξn+1，ξn+2，…ξn+s）在s维空间的单位立方体Gs上均匀分布，即对任意的ai，0≤ai≤1，i=1,2,…,s如下等式成立：siiinsiaaP11,...,1)(随机数的定义及其性质2013年9月2日大连大学数学建模工作室其中P(M)表示事件M发生的概率。反之，如果随机变量序列ξ1,ξ2…对于任意自然数s，由s个元素所组成的s维空间上的点（ξn+1，…ξn+s）在Gs上均匀分布，则它们是随机数序列。由于随机数在蒙特卡罗方法中所处的特殊地位，它们虽然也属于由具有已知分布的总体中产生简单子样的问题，但就产生方法而言，却有着本质上的差别。随机数的定义及其性质2013年9月2日大连大学数学建模工作室产生随机数的方法随机数表物理方法计算机方法2013年9月2日大连大学数学建模工作室随机数表随机数表是由0,1,2,…,9十个数字组成，每个数字以0.1的概率出现，数字之间相互独立。方法：如果要得到n位有效数字的随机数，只需将表中每n个相邻的随机数字合并在一起，且在最高位的前边加上小数点即可。例如：某随机数表第一行数字为7634258910…，要想得到三位有效数字的随机数依次为：0.763，0.425，0.8912013年9月2日大连大学数学建模工作室物理方法基本原理：利用某些物理现象，在计算机上增加些特殊设备，可以在计算机上直接产生随机数。缺点：无法重复实现费用昂贵2013年9月2日大连大学数学建模工作室计算机产生随机数由于在计算机上产生随机数最实用、最常见的方法是数学法，即采用递推的公式产生随机数。但随之也带来问题：1，不满足相互独立的要求2，不可避免的出现重复问题因此，我们将计算机产生的随机数称为伪随机数2013年9月2日大连大学数学建模工作室产生伪随机数的方法乘同余方法乘加同余方法取中方法加同余方法2013年9月2日大连大学数学建模工作室Matlab中生成随机数的函数2013年9月2日大连大学数学建模工作室Matlab中生成随机数的函数2013年9月2日大连大学数学建模工作室exprnd指数分布的随机数生成器geornd几何分布的随机数生成器poissrnd泊松分布的随机数生成器unidrnd离散均匀分布的随机数生成器unifrnd连续均匀分布的随机数生成器betarnd贝塔分布的随机数生成器binornd二项分布的随机数生成器Matlab中生成随机数的函数2013年9月2日大连大学数学建模工作室其它函数2013年9月2日大连大学数学建模工作室蒙特卡洛方法的实例讲解计算圆周率在平面上画一个半径r的圆和边长为2r的正方形，让他们的中心重合。随机的向正方形内投点N次，观察投在圆内的点的数目m。计算点投在圆内的概率。2013年9月2日大连大学数学建模工作室氢原子电子云模拟氢原子的基态（n=0,l=0,m=0）的电子分布几率密度函数是：其中a1=5.29*10-2nm,D的最大值Dmax=1.1,r0=0.25nm是D的收敛点123124arearD2013年9月2日大连大学数学建模工作室模拟是用点的密度来表示电子的几率分布密度。模拟时先产生一个随机的电子轨道半径r=r0rand(1),显然有0≤r≤r0,由r计算出D(r)。再产生一个随机的概率判据D0=Dmaxrand(1),显然有0≤D0≤Dmax,然后进行判断，如果D(r)D0,则舍弃它，反之就计算一个随机的角度值，θ=2πrand(1),最后得到的点的坐标是x=rcosθ;y=rsinθ。氢原子电子云模拟思路2013年9月2日大连大学数学建模工作室蒲丰投针问题2013年9月2日大连大学数学建模工作室蒙特卡洛与21点大多数赌场使用6副牌或8副牌玩这种游戏，以防止“数牌点”，在你的模拟中使用两副牌(共104张)。只有2位参与者，你和庄家。游戏开始时每人得到两张牌，对于牌面为2~10的牌，点数和面数相同；对于为人脸(J、Q、K)的牌，点数为10；牌面为A的牌，点数为1或者11.游戏的目的是得到总数尽量接近21点的牌，不得超过(超过称“爆了”)，并使你得到的总点数多于庄家。2013年9月2日大连大学数学建模工作室与蒙特卡洛相关的赛题2010年全国赛A题2013年9月2日大连大学数学建模工作室优点1.能够比较逼真地描述具有随机性质的事物的特点及物理实验过程。2.受几何条件限制小。3.收敛速度与问题的维数无关。4.误差容易确定。5.程序结构简单，易于实现。蒙特卡洛的优缺点及其适用范围2013年9月2日大连大学数学建模工作室缺点1.收敛速度慢。2.误差具有概率性。3.进行模拟的前提是各输入变量是相互独立的。蒙特卡洛的优缺点及其适用范围2013年9月2日大连大学数学建模工作室能够比较逼真地描述具有随机性质的事物的特点及物理实验过程从这个意义上讲，蒙特卡罗方法可以部分代替物理实验，甚至可以得到物理实验难以得到的结果。用蒙特卡罗方法解决实际问题，可以直接从实际问题本身出发，而不从方程或数学表达式出发。它有直观、形象的特点。2013年9月2日大连大学数学建模工作室受几何条件限制小在计算s维空间中的任一区域Ds上的积分，无论区域Ds的形状多么特殊，只要能给出描述Ds的几何特征的条件，就可以从Ds中均匀产生N个点2013年9月2日大连大学数学建模工作室收敛速度与问题的维数无关由误差定义可知，在给定置信水平情况下，蒙特卡罗方法的收敛速度为o（N-1/2），与问题本身的维数无关。维数的变化，只引起抽样时间及估计量计算时间的变化，不影响误差。也就是说，使用蒙特卡罗方法时，抽取的子样总数N与维数s无关。维数的增加，除了增加相应的计算量外，不影响问题的误差。这一特点，决定了蒙特卡罗方法对多维问题的适应性。2013年9月2日大连大学数学建模工作室程序结构简单，易于实现在计算机上进行蒙特卡罗方法计算时，程序结构简单，分块性强，易于实现。2013年9月2日大连大学数学建模工作室收敛速度慢如前所述，蒙特卡罗方法的收敛为o（N-1/2），一般不容易得到精确度较高的近似结果。对于维数少（三维以下）的问题，不如其他方法好。2013年9月2日大连大学数学建模工作室误差具有概率性由于