蒙特卡洛模拟方法蒙特卡洛模拟方法主讲人：李彬主讲人：李彬大连大学数学建模工作室大连大学数学建模工作室20132013年年9 9月月2 2日日蒙特卡洛模拟方法蒙特卡洛模拟方法蒙特卡罗方法概述蒙特卡罗方法概述1蒙特卡洛方法思想框图蒙特卡洛方法思想框图2相关案例分析及其软件操作相关案例分析及其软件操作3蒙特卡洛的优缺点及其适用范围蒙特卡洛的优缺点及其适用范围42013年9月2日大连大学数学建模工作室大连大学数学建模工作室Monte Carlo方法的发展历史方法的发展历史早在早在17世纪，人们就知道用事件发生的世纪，人们就知道用事件发生的“频频率率”来决定事件的来决定事件的“概率概率”。从方法特征的。从方法特征的角度来说可以一直追溯到角度来说可以一直追溯到18世纪后半叶的蒲世纪后半叶的蒲丰（丰（Buffon）随机投针试验，即著名的）随机投针试验，即著名的蒲蒲丰问题丰问题。2013年9月2日大连大学数学建模工作室大连大学数学建模工作室Monte Carlo方法的发展历史方法的发展历史 1777年，古稀之年的蒲丰在家中请来好些年，古稀之年的蒲丰在家中请来好些客人玩投针游戏（针长是线距之半），他事客人玩投针游戏（针长是线距之半），他事先没有给客人讲与先没有给客人讲与有关的事。客人们虽然有关的事。客人们虽然不知道主人的用意，但是都参加了游戏。他不知道主人的用意，但是都参加了游戏。他们共投针们共投针2212次，其中次，其中704次相交。蒲丰说，次相交。蒲丰说，2212/704=3.142，这就是，这就是值。这着实让人值。这着实让人们惊喜不已。们惊喜不已。2013年9月2日大连大学数学建模工作室大连大学数学建模工作室例例.蒲丰氏问题蒲丰氏问题 设针设针投到地面上的位置可以用一投到地面上的位置可以用一组组参数参数（x,）来描述）来描述,x为针为针中心的坐中心的坐标标,为针为针与与平行平行线线的的夹夹角角,如如图图所示。所示。 任意投任意投针针，就是意味着，就是意味着x与与都是任意取都是任意取的，的，x的范的范围围限于限于0，a/2，夹夹角角的范的范围围限于限于0，。2013年9月2日大连大学数学建模工作室大连大学数学建模工作室蒲丰氏问题数学基础蒲丰氏问题数学基础上述问题简图：上述问题简图：2013年9月2日大连大学数学建模工作室大连大学数学建模工作室分析知针与平行线相交的充要条件是：分析知针与平行线相交的充要条件是：其中：其中：建立直角坐标系建立直角坐标系 ，上述条件在坐标系下将是曲线，上述条件在坐标系下将是曲线所围成的曲边梯形区域。由几何概率知：所围成的曲边梯形区域。由几何概率知：蒲丰氏问题数学基础蒲丰氏问题数学基础2013年9月2日大连大学数学建模工作室大连大学数学建模工作室拉查里尼（Lazzarini）投计次数：3408次pi的实验值：3.1415921850185518941901历史上的实验历史上的实验历史上的实验历史上的实验斯密思（Smith）投计次数：3204次pi的实验值：3.1553福克斯（Fox）投计次数：1120次pi的实验值：3.1419沃尔弗（Wolf）投计次数：5000次pi的实验值：3.1596Monte Carlo方法的发展历史方法的发展历史2013年9月2日大连大学数学建模工作室大连大学数学建模工作室Monte Carlo方法的发展历史方法的发展历史 20世世纪纪四十年代，由于四十年代，由于电电子子计计算机的出算机的出现现，利用，利用电电子子计计算机可以算机可以实实现现大量的随机抽大量的随机抽样样的的试验试验，使得用随机，使得用随机试验试验方法解决方法解决实际问题实际问题才有了才有了可能。其中作可能。其中作为为当当时时的代表性工作便是在第二次世界大的代表性工作便是在第二次世界大战战期期间间，为为解解决原子决原子弹弹研制工作中，裂研制工作中，裂变变物物质质的中子随机的中子随机扩扩散散问题问题，美国数学家，美国数学家冯冯.诺诺伊曼和伊曼和乌乌拉姆等提出蒙特卡拉姆等提出蒙特卡罗罗模模拟拟方法方法.由于当由于当时时工作是保密的，工作是保密的，就就给这给这种方法起了一个代号叫蒙特卡种方法起了一个代号叫蒙特卡罗罗，即摩，即摩纳纳哥的一个哥的一个赌赌城的名字。城的名字。用用赌赌城的名字作城的名字作为为随机模随机模拟拟的名称，既反映了的名称，既反映了该该方法的部分内涵，又方法的部分内涵，又易易记忆记忆，因而很快就得到人，因而很快就得到人们们的普遍接受。的普遍接受。2013年9月2日大连大学数学建模工作室大连大学数学建模工作室Monte Carlo方法的基本思想方法的基本思想蒙特卡蒙特卡罗罗方法方法又称又称计计算机随机模算机随机模拟拟方法。它是以方法。它是以概概率率统计统计理理论论为为基基础础的一种方法。的一种方法。 由蒲丰实验可以知道，当所求问题的解是某个事件由蒲丰实验可以知道，当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望的概率，或者是某个随机变量的数学期望，或者是或者是与概率、数学期望有关的量时。通过某种试验的方与概率、数学期望有关的量时。通过某种试验的方法，得出该事件发生的频率，或者该随机变量若干法，得出该事件发生的频率，或者该随机变量若干个具体观察值的算术平均值，通过它得到问题的解。个具体观察值的算术平均值，通过它得到问题的解。这就是蒙特卡洛方法的基本思想。这就是蒙特卡洛方法的基本思想。2013年9月2日大连大学数学建模工作室大连大学数学建模工作室Monte Carlo方法的基本思想方法的基本思想蒙特卡蒙特卡罗罗方法方法又称又称计计算机随机模算机随机模拟拟方法。它是以方法。它是以概概率率统计统计理理论论为为基基础础的一种方法。的一种方法。 由蒲丰实验可以知道，当所求问题的解是某个事件由蒲丰实验可以知道，当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望的概率，或者是某个随机变量的数学期望，或者是或者是与概率、数学期望有关的量时。通过某种试验的方与概率、数学期望有关的量时。通过某种试验的方法，得出该事件发生的频率，或者该随机变量若干法，得出该事件发生的频率，或者该随机变量若干个具体观察值的算术平均值，通过它得到问题的解。个具体观察值的算术平均值，通过它得到问题的解。这就是蒙特卡洛方法的基本思想。这就是蒙特卡洛方法的基本思想。2013年9月2日大连大学数学建模工作室大连大学数学建模工作室Monte Carlo方法的思想框图方法的思想框图建立概率统计模型收集模型中风险变量的数据，确定风险因数的分布函数根据风险分析的精度要求，确定模拟次数N建立对随机变量的抽样方法，产生随机数N个样本值根据随机数在各风险变量的概率分布中随机抽样，代入第一步中建立的数学模型统计分析，估计均值，标准差NNN2013年9月2日大连大学数学建模工作室大连大学数学建模工作室Monte Carlo方法的框图实例方法的框图实例某投资项目每年所得盈利额某投资项目每年所得盈利额A由投资额由投资额P、劳动生产率劳动生产率L、和原料及能源价格、和原料及能源价格Q三个因三个因素。素。2013年9月2日大连大学数学建模工作室大连大学数学建模工作室Monte Carlo方法的思想框图实例方法的思想框图实例收集P,L,Q数据，确定分布函数f(P),f(L),f(Q)模拟次数N；根据分布函数，产生随机数建立对随机变量的抽样方法，产生随机数产生N个A值抽取P,L,Q一组随机数，代入模型统计分析，估计均值，标准差NNN2013年9月2日大连大学数学建模工作室大连大学数学建模工作室随机数的定义及其性质随机数的定义及其性质随机数的定义 用Monte Carlo方法模拟某过程时，需要产生各种概率分布的随机变量。最简单、最基本、最重要的随机变量是在0，1上均匀分布的随机变量。由该分布抽取的简单子样称为随机数序列，其中每一个体称为随机数。随机数属于一种特殊的由已知分布的随机抽样问题。随机数是随机抽样的基本工具。 0，1上均匀分布（单位均匀分布），其分布密度函数为： 分布函数为：2013年9月2日大连大学数学建模工作室大连大学数学建模工作室 由于随机数在蒙特卡罗方法中占有极其重要的位置，我们用专门的符号表示。由随机数序列的定义可知，1，2，是相互独立且具有相同单位均匀分布的随机数序列。也就是说，独立性、均匀性是随机数必备的两个特点。 随机数具有非常重要的性质：对于任意自然数s，由s个随机数组成的s维空间上的点（n+1，n+2，n+s）在s维空间的单位立方体Gs上均匀分布，即对任意的ai，0ai1，i=1,2,s 如下等式成立：随机数的定义及其性质随机数的定义及其性质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的收敛点2013年9月2日大连大学数学建模工作室大连大学数学建模工作室模拟是用点的密度来表示电子的几率分布密度。模拟时先产生一个随机的电子轨道半径r = r0rand(1), 显然有0 r r0, 由r计算出D(r)。再产生一个随机的概率判据D0 = Dmaxrand(1),显然有0 D0 Dmax,然后进行判断，如果D(r) D0,则舍弃它，反之就计算一个随机的角度值， = 2rand(1),最后得到的点的坐标是x = r cos ; y = r sin 。氢原子电子云模拟思路氢原子电子云模拟思路2013年9月2日大连大学数学建模工作室大连大学数学建模工作室蒲丰投蒲丰投针问题针问题2013年9月2日大连大学数学建模工作室大连大学数学建模工作室蒙特卡洛与蒙特卡洛与21点点大多数赌场使用6副牌或8副牌玩这种游戏，以防止“数牌点”，在你的模拟中使用两副牌(共104张)。只有2位参与者，你和庄家。游戏开始时每人得到两张牌，对于牌面为210的牌，点数和面数相同；对于为人脸(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日大连大学数学建模工作室大连大学数学建模工作室误差具有概率性误差具有概率性由于蒙特卡罗方法的误差是在一定置信水平下估计的，所以它的误差具有概率性，而不是一般意义下的误差。 2013年9月2日大连大学数学建模工作室大连大学数学建模工作室蒙特卡罗方法的主要应用范围蒙特卡罗方法的主要应用范围蒙特卡罗方法所特有的优点，使得它的应用范围越来越广。它的主要应用范围包括：粒子输运问题，统计物理，典型数学问题，真空技术，激光技术以及医学，生物，探矿等方面，特别适用于在计算机上对大型项目、新产品项目和其他含有大量不确定因素的复杂决策系统进行风险模拟分析。随着科学技术的发展，其应用范围将更加广泛。 2013年9月2日大连大学数学建模工作室大连大学数学建模工作室