龚光鲁,钱敏平著应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第8章 Monte Carlo与 Markov chain monte carlo(MCMC)方法 在许多很复杂的统计问题中,有时很难直接对各种统计方法进行理论分析.为了评估它 们的优劣,常见的实用办法是做随机模拟:即设法按问题的要求与条件去构造出一系列的模 拟样本,用它们的样本频率代替对应的概率作统计分析与推断,观察由这些摸拟样品所作出 的推断的正确率.因为在概率论初期发展时,随机模拟的原型常常来自博采,于是人们就以 博采之都 Monte carlo作为随机模拟方法的别称.久而久之, Monte carlo方法作为名称 倒比随机模拟方法更为广泛地被常用了.相仿地,人们还把组合计算中的某些随机模拟方法, 称为 Las vegas方法,这是以美国的博采城 Las vegas命名的 般随机模拟方法的长处是,计算的复杂度不依赖于计算空间的维数因此,在计算非 常高维数的积分(或多指标的求和)时, Monte Carlo方法比通常的计算方法有明显的优越 性.而很多的 Monte carlo计算问题,可归结为计算积分或庞大和数的问题 1.计算积分的 Monte carlo方法与采样量估计 通过构造独立同分布随机数,计算积分的 Monte carlo方法,也称为静态 Monte Carlo 方法,其思想可以在本节中,通过估计最简单的积分f(x)dx得到阐明.对于高维积分, 其思路与一维积分是一样的.另一方面,在甚高维情形,因为计算量太大,用静态 Monte Carlo方法处理速度太慢.我们在第2节中通过构造 Markov链的极限不变分布,来模拟 计算积分的方法(称为动态 Monte Carlo方法, Markov链 Monte carlo方法,MCMC),将 更为适用 1.1用频率估计概率来计算积分的 Monte Carlo方法 假定0≤f(x)≤M.那么由积分的面积含义有 f(x)ax=S|,(其中S|为S={(x,y):a≤x≤b,f(x)≥y}的面积) 考虑平面区域Ω=如,b×[0,M上的均匀随机变量5,则 p=P(∈S) 「/(x)k 对于N个独立的-均匀随机数;,(≤N),记 Ns={1,…5x}中落在S中的频数 于是,利用大数定律便知 (b-a)202 龚光鲁，钱敏平著 应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第 8 章 Monte Carlo 与 Markov Chain Monte Carlo (MCMC) 方法 在许多很复杂的统计问题中,有时很难直接对各种统计方法进行理论分析．为了评估它 们的优劣,常见的实用办法是做随机模拟：即设法按问题的要求与条件去构造出一系列的模 拟样本,用它们的样本频率代替对应的概率作统计分析与推断, 观察由这些摸拟样品所作出 的推断的正确率．因为在概率论初期发展时, 随机模拟的原型常常来自博采, 于是人们就以 博采之都 Monte Carlo 作为随机模拟方法的别称. 久而久之, Monte Carlo 方法作为名称 倒比随机模拟方法更为广泛地被常用了. 相仿地, 人们还把组合计算中的某些随机模拟方法, 称为 Las Vegas 方法, 这是以美国的博采城 Las Vegas 命名的. 一般随机模拟方法的长处是，计算的复杂度不依赖于计算空间的维数. 因此, 在计算非 常高维数的积分（或多指标的求和）时, Monte Carlo 方法比通常的计算方法有明显的优越 性. 而很多的 Monte Carlo 计算问题, 可归结为计算积分或庞大和数的问题. 1. 计算积分的 Monte Carlo 方法与采样量估计 通过构造独立同分布随机数, 计算积分的 Monte Carlo 方法, 也称为静态 Monte Carlo 方法, 其思想可以在本节中,通过估计最简单的积分 ò b a f (x)dx 得到阐明. 对于高维积分, 其思路与一维积分是一样的. 另一方面，在甚高维情形, 因为计算量太大, 用静态 Monte Carlo 方法处理速度太慢. 我们在第 2 节中通过构造 Markov 链的极限不变分布，来模拟 计算积分的方法（称为动态 Monte Carlo 方法， Markov 链 Monte Carlo 方法, MCMC), 将 更为适用. 1. 1 用频率估计概率来计算积分的 Monte Carlo 方法 假定 0 £ f ( x) £ M . 那么由积分的面积含义有 f (x)dx | S | b a = ò , (其中| S | 为 S ={(x, y) : a £ x £ b, f (x) ³ y} D 的面积 ). 考虑平面区域W =[a,b]´[0,M ] D 上的均匀随机变量x , 则 b a M p P S ( ) 1 ( ) - = Î = D x ò b a f (x)dx . 对于 N 个独立的W -均匀随机数 ,(i N) xi £ , 记 { , , } NS 1 N = x L x 中落在 S 中的频数， 于是，利用大数定律便知 D = ^ I N N b a M S ( - ) （８．１）