（概率论与数理统计专业论文）马尔可夫链蒙特卡罗算法.pdf

摘要 本文在对m c m c 算法的起源，应用以及其相关的基本问题( 随机样本生 成法。静态m o n t ec a r l o 算法) 做了介绍后。一方面讨论了m c m c 算法的构造 方法，另方面讨论了m a r k o v 链的定性收敛和定量收敛，并用耦合构造的方 法证明了其中的一些结论，得到了若干有意义的的结果 本文第部分介绍了m c m c 算法的起源及应用范围，讨论了若干种随机 样本生成法和静态m o n t ec a r l o 算法，第二部分介绍了m c m c 算法的构造方 法，专门i - t 论了m e t r o p o l i s - h a s t i n g 采样法，第三部分讨论了m a r k o v 链收敛性 几种方法，包括定量收敛和定性收敛第四部分着重讨论了m a r k o v 链定量收 敛的个推广的结论及证明，得出了若干结果，具有较好的理论及现实指导意 义 关键词；m c m c ，蒙特卡罗，马尔可夫链，m e t r o p o l i s - h a s t i n g 采样法，定量 收敛，耦合构造 a b s t r a c t t h i sp a p e rs u r v e y sv a r i o u sr e s u l t sa b o u tm a r k o vc h a i n sm o n t ec a r l ou l g o - r i t h m s i tb c g i n e dw i t ha ni n t r o d u c t i o nt om a r k o vc h a i nm o n t ec a r l o ( m c m c la l - g o r i t h m s ，w h i c hp r o v i d e dt h em o t i v a t i o na n dc o n t e x t f o rt h ef o l l o w i n gt h e o r y t h e n ， t h em f l f i c i e n tc o n d i t i o n sf o rg e o m e t r i ca n du n i f o r me r g o d i c i t yw e r ep r e s e n t e d ，a l o n g e d w i t hq u a n t i t a t i v eb o u n d so nt h er a t eo fc o n v e r g e n c et os t a t i o n a r i t y , w eo b t a i n e d s o m ei m p o r t a n tr e s u l t s t h ef i r s tp a r to ft h i sp a p e ri n t r o d u c t e dt h em o t i v a t i o na n dc o n t e x to fm c m c ， d i s c u s s e ds o m es a m p l ea l g o r i t h m sa n dc l a s s i c a lm o n t ec a r l oa l g o r i t h m s t h e8 e o o n dp a r ti n t r o d u c t e dt h ec o n s t r u c t i n go fm c m ca l g o r i t h m s t h et h i r dp a r td i s - c u s s e ds o m em e t h o r da b o u tm a r k o vc h a i nc o n v e r g e n c et i m e s t h el a s tp a r td i s c u s s e d t h eq u a n t i t a t i v ec o n v e r g e n c er a t e s ，p r o v e dt h ec o n v e r g e n c eu s i n gc o u p l i n gc o n s t r u e - t i o n s ，a n do b t a i n e ds o m ei m p o r t a n tr e s u l t s k e yw o r d s ：m c m c ， m o n t ec a r l o ，m a r k o vc h a i n ， m e t r o p o l i s - h a s t i n g a l g o r i t h m ，q u a n t i t a t i v ec o n v e r g e n c e ，c o u p l i n gc o n s t r u c t i o n s u 湖北大学学位论文原创性声明和使用授权 说明 原创性声明 本人郑重声明；所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个 人或集体已经发表或撰写过的作品或成果对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明本声明的法律后果由本人承担 论文作者签名“习菲 签名日期；2 0 0 7 年5 月2 9 日 学位论文使用授权说明 本人完全了解湖北大学关于收集，保存，使用学位论文的规定，即；按照 学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷 本和电子版，并提供目录检索与阅览服务；学校可以采用影印，缩印，数字化 或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部 分或全部内容( 保密论文在解密后遵守此规定) 论文作者签名，、司菲 签名日期t 2 口四年歹月砧日 导师签名：；丧拶r 签名日期y 7 年j 月话喟 第一章序言 第一章序言 1 8 9 9 年，瑞利等人最早提出基于统计概念的计算方法一蒙特卡诺方法的 思想，二十世纪二十年代柯朗( 德) 冯诺伊曼( 美) 等人发展了这个方法， 后在电子计算机上获得广泛应用1 9 0 6 年俄国数学家马尔可夫，首次提出了 “马尔可夫链”的数学模型 本世纪9 0 年代以来，对。复杂性。的研究较为瞩目。很多应用问题都存在 着分析对象比较复杂与正确识别模型结构的困难，这时用m a r k o v 链的样本， 来对不变分布，g i b b s 分布，g i b b s 场，高维分布或样本空间非常大的离散分 布等做采样。并用以做隧机模拟的方法，即m c m c 方法的问世对建立可实际 应用的统计模型开辟了广阔的前景根据m c m c 理论，通过使用专用统计软 件进行m c m c 模拟，可解决许多复杂性问题，它相对于决定性算法，显示出 了其巨大的优越性此外，得益于m c m c 理论的运用，使得贝叶斯( b a y e s ) 统 计得到了再度复兴，以往被认为不可能实施计算的统计方法变得是很轻而易 举了 在许多很复杂的统计问题中，有时很难对各种统计方法进行理论分析， 为了评估它们的优劣，常见的实用方法是做随机模拟z 即设法按问题的要求和 条件去构造出一系列的模拟样本，用它们的样本频率代替相应的概率作统计 分析和推断，观察由这些模拟样品所作出的推断的正确率因为在概率论初期 发展时，随机模拟的原型常常来自博采，于是人们就以博采之都m o n t ec a r l o 作为随机模拟方法的别称久而久之，m o n t ec a r l o 方法作为名称饲比随机模 拟方法更为广泛的常用了 用m a r k o v 链的样本。来对不变分布，g i b b s 分布，g i b b s 场，高维分布 或样本空间非常大的离散分布等作采样，并用以作随机模拟的方法，统称为 m a r k o vc h a i nm o n t ec a r l o ( m c m c ) 方法这是动态的m o n t ec a r l o 方法由于 这种方法的问世，使随机模拟在很多领域的计算中，相对于决定性算法，显示 出它的巨大优越性而有时随机模拟与决定性算法的结合使用，会显示出更多 的长处 1 湖北大学硕士学位论文 m c m c 至少可以用在以下几个层面， ( 1 ) 用于生成较复杂的随机数t 实现对高维分布( 或高维格点分布) ”的取样，得到”随机数 o 是实现重要度采样的一种方法对i ，( z ) i 的重要度采样，就是取得随机数 = 揣 对于，( z ) 20 ，作以”= w ( z ) = 了￥等岛为极限分布的m a r k o v 链j o ，利用遍历 定理可以由这个m a r k o v 链的一条轨道，得到分布密度”( 。) 的估计 ( 2 ) 实现高维积分( 或项数极多的求和) 的数值计算( 典例是g i b l 分布的各 种泛函的平均值的计算) ( 3 ) 用模拟方法估计最可几轨道例如，如果模拟了1 0 0 条轨道。那么就能以 大概率推断，最可几轨道就在这些轨道的附近当统计的分布未知时，可以用 模拟方法从频率估计置信限 ( 4 ) 用被估计参数的b a y e s 分布的取样，来估计参数 ( 5 ) 求复杂样本空间上函数的极值( 模拟退火) 鉴于以上情况，本文第一部分介绍了m c m c 算法的起源及应用范围，讨论 了若干种随机样本生成法和静态m o n t ec a r l o 算法，第二部分介绍了m c m c 算 法的构造方法，专门讨论了m e t r o p o l i s - h a s t i n g 采样法，第三部分讨论了m a r k o v 链收敛性几种方法，包括定量收敛和定性收敛第四部分着重讨论了m a r k o v 链定量收敛的一个推广的结论及证明 2 第二章随机样本生成法 第二章随机样本生成法 随机变量( 或随机向量) 的样本简称为随机数由于在统计中常用的是独 立样本列，不妨假设随机数之间都是独立的，生成随机数的方法，也称为随机 数的取样法 2 1 随机数的生成方法 2 1 1 均匀随机变量的计算机模拟 在i o ，1 】上均匀分布的随机变量的独立样本称为均匀随机数( u ( 0 ，1 ) 随机 数) 在计算机上产生的称之为。伪随机数。的数列，是一种具有非常长周期 的。且能通过数理统计中的独立性与均匀性假设检验的数列实践证明，伪 随机数是均匀随机数的一种可行的近似这种伪随机数虽然不是独立同分布 的u ( o ，1 ) 随机变量的样本。而是在【0 ，1 l 中取值的周期数列。但是由于它可以 像均匀随机数一样地通过数理统计中的独立性与均匀性假设检验，而且它的 周期非常长，以至在计算机实际运算过程中不会出现重复，所以在实际计算中 它能很好的替代均匀随机数最普遍用以产生伪随机数的方法是同余法典 型的饲子如下。 + 1 = 5 1 3 ( 斌2 3 6 ) ，! o = l ，= 2 - ( 周期约为2 1 0 ”) 2 1 2 分布函数f ( x ) 的随机数 ( 反函数法) 分布函数为f ( x ) 的独立随机变量列的样本，称为f ( x ) 随机 数若f ( x ) 严格单调增加，是均匀随机数，则f - 1 ( f ) 是f ( z ) 随机数，其 中f o 为f 的反函数 2 1 3 正态随机数 l v ( o ，1 ) 随机数称为标准正态随机数生成标准正态随机数有个比反函数 的方法更为简单的实践方法，就是利用中心极限定理设】1 ，7 1 2 为均匀随机 3 湖北大学硕士学位论文 数，且它们是独立的，由中心极限定理，可以认为f = 目l + + r 1 2 - 6 n ( 0 ，1 ) ，即 用f = 】1 + + t _ 1 2 6 近似的作为标准正态随机数在实际计算中琅( 1 i 兰1 2 ) 还应该甩伪随机数代替 命题2 1 ( 生成标准正态随机数的b o x - m u l l e r 方法) ，取两个独立的均匀随 机数啦，啦。令 l = - 2 i n7 1 c ( 2 啦) 如= - 2 i n q ls i n ( 2 口m ) 则l ，巳为相互独立的标准正态随机数 2 1 4 v o n n e u m a n 取舍原则 假定我们要生成密度为p ( 功的随机数为此取一个参考分布密度p o ( z ) ， 使它满足t ( 1 肺( z ) 随机数容易生成，例如砌( z ) 为正态密度，均匀密度，指数密度， 及它们的混合密度等； ( 2 瑜( 。) 与p ( z ) 的取值范围差不多，且存在c ，使p p ) c ( 。) 则有以下命题t 命题2 2 设随机变量q 具有密度p o ( z ) ，而随机变量u v 0 ，1 1 且与口独 立。则 确纠蒜猢= p ) d r 证明对q 的取值用推广了的全概率公式( p ( a ) = f p c a 目= ”伽( ) 西) ， 得到 左勉=p ( 目s l 龋2 矿) p ( 龋t r ) 一j ：e ( t r d 案) p 0 ( ) 妇 = 。- 。_ - _ _ _ _ _ _ _ _ _ _ _ _ - - _ _ _ - - - - - - - - - - - 。_ _ _ _ - _ _ _ _ - - - 一 j ：e ( u 龋) p o ( y ) d y = 墨y y o o 逊b , c y 堕) d = 右边 2 2 硇愿 4 第二章随机样本生成法 取舍原则的具体作法是 ( 1 ) 独立的生成n 个独立的瑚( z ) 随机数m ，与n 个与之独立的u o ，1 】 随机数矾，巩 ( 2 ) 对于i _ l 2 一如果有毒仉，就保留否则舍弃依 由命题2 2 ，所有这样保留下来的啦就成为一系列独立的p ( z ) 随机数( 当 然个数比n 小很多) 这种取舍方法称为v o nn e u m s n 取舍原则 取舍原则可以改良为以下叙述- 如果p ( z ) = 1 ( ) ，只要存在c ，使 ( 习c 如( z ) ，那么我们可以在取舍 原则中用 ( z ) 代替p ( z ) ，得到p ( z ) 随机数具体为：独立的生成n 个独立的 p o ( 。) 随机数m ，与n 个与之独立的独立u o ，1 】随机数u l ，如果 盟c p o ( , h ) 矾 。 就保留， ，否则舍弃哺，那么所有保留的是相互独立的p ( z ) 随机数 2 1 5 多维随机数 对于已知的分布密度，可以利用条件密度，把生成多维随机数归结为生 成一系列一维随机数；设随机向量( 局，施) 的密度为，( # l ，z 2 ，z d ) ，则有 表达式 ，( z l ，x 2 ，x d ) = x l ( z 1 ) ，( z 2 i z l ) ( * d l * 1 ，d 1 ) 其中厶。( z 1 ) 为x l 的边缘密度，i z l ，一1 ) 为在已知墨= z 1 ，x k l 一 $ i l 条件下凰的条件密度于是可以先取一个及。随机数z l ；然后，在z l 固定的情形下，生成一个，( ，z 1 ) ，随机数x 2 ；再在z l 一2 固定的情形下，生成 个，( ，z 1 ，x 2 ) 随机数。3 ；最后，在z l ，。2 ，黝一l 固定的情形下。生成一 个，( ，钆，跏一1 ) 随机数黝这样得到的( z l ，3 ：d ) 就是向量( x l ，施) 的 一个随机数 2 2 静态的m o n t ec a r l o 方法 通过构造独立同分布随机数，计算积分的m o n t ec a r l o 方法，称为静态 m o n t ec a r l o 方法其思想可以在本节中，通过估计最简单的积分c ，( z ) 如得 到阐明对于高维积分，其思路与一维积分是一样的 5 湖北大学硕士学位论文 2 2 1 用频率估计概率来计算积分的m o n t ec a r l o 方法 假定0sf ( x ) sm ，那么由积分的面积含义有 j ：，( z ) 出= i s l ( 其中j s i 为s = ( 霸y ) ：8 曼z 曼6 ，0 y ，( z ) 的面积) 考虑平面区域n = i o ，6 】【0 ，m 上的均匀随机变量6 则 1一 p 2 p ( f s ) 。商j cm ) 缸 对于n 个独立的m 均匀随机数矗“) ，记 虬= 6 ，臼中落在s 中的频数 于是。利用大数定理便知 嘲6 _ n ) m 等 是积分i = f ：f ( x ) d x 的相合估计，即对于任意的e 0 ，当n o o 时，有 p ( 1 ( b - a ) m - 等一f m 川 扣。 又由于虬服从参数为( p , n ) 的二项分布，所以有 e i = 学p = 厶牡 即j 是积分e ，( z ) 如的无偏估计此估计的方差为 j = ( 6 一。) 2 m 2 p ( n n ) ：( 6 一。) 。m ：壶竺n 二盘1 2 爿( 6 一a ) m 一日 = o ( 亩) 又由于方差代表平均平方误差，故有积分的估计j 的误差为o ( 斋) 2 2 2 用样本函数的平均值估计的期望来计算积分的m o n t ec a r l o 方法 一一期望法 期望法的核心思想是把积分看成某个随机变量的期望最常见的是看成 f a ，b l 上均匀随机变量的期望设口一c ，【o ，6 】( k b l 上的均匀分裥 ，= r m 肛( b 刊啪) 第二章随机样本生成法 于是对n 个独立的i a ，b 1 上的均匀随机数，可以用矩估计 j 邓刊趔专芦盟 作为j = f b f ( x ) d x 的估计，由于 e ，= 坠掣- ( 6 _ 0 ) 啪h 故j 是无偏估计而且 ( ；) - ( 6 叫2 号掣 = ( b - a ) 2 寺e m ) 2 一m 目) 1 2 = ( b - a ) 2 斋f m ) 2 而d z _ - j 1 2 毒【( 6 一n ) m z 一确 = m r ( j ) 可见频率法比期望法更有效 2 2 3 减少方差的技术一一重要度采样法 用m o n t ec a r l o 方法计算积分f bf ( x ) d x 时，未必一定要使用均匀随机数 事实上，从i a ，b 】上取值的任意一种随机数出发，都可以得到f b f ( z ) d a c 的估计 量而且在，( 功20 ，显见值f ( x ) 大的x 对于积分s b f ( z ) d x 有更大的贡献，由 此得到启发。所用的随机数的分布密度的形状越像“x ) ，则越合理这个思想 就是重要度采样法 1 g - 采样法 假定分布密度g ( x ) 在f ( x ) 非零处恒正，则积分 ，；r m 肛f 赫靛 对于密度为g ( x ) 的。g - 随机数f ，有 ，叫等】 于是对于n 个独立的g - 随机数f l ，臼，关于积分，= f b f ( w ) d t 可取估计 删= 扣器h 邶r 裂】 7 湖北大学硕士学位论文 显见它也是无偏的相合估计利用s c h w a r t z 不等式得到 f 【器】2 9 出 = f 出，如z 6 【器如 r 揣厕，2 = 【，( z ) 出】2 而且上式当且仅当在v 俪两= c 孑黯时( 即g ( x ) 2 0 f ( x ) 时) 达到极小值噼，( z ) 如】2 这说明v a t ( 1 0 ) ) = 1 b l 籍fw 】2 9 ( z ) 如一r 】的最小值在蛐( z ) = c ，( z ) 时取到 又因为卯( z ) 为密度故c 。7 1 壳函是无估计误差的精确值 综上讨论可知，要使方差达到最小，就应该用9 0 ( z ) = c ，( z ) 作为参考密 度由此我们可以得到下面的认识，即只要密度g ( x ) 的形状与被积分的函数 近似，用，( 。) 作为e ，( z ) 出的估计，就会降低方差这就是下面的概念 定义2 - 1 分布密度为9 ( z ) = z 惯犯的g - 采样，称为关于f ( x ) 的重要 度采样 重要度采样不能直接通过取舍原则实现近似的实现重要度采样可以采 用m a r k o v 链m o n t ec a r l o 方法 在实践中人们也往往按照重要度采样的思路，灵活的寻找常用的已知类 型的密度g ，使它在峰值附近与f ，( 硎较接近，以便达到降低估计的方差的目 的 2 修正的重要度采样法 对于g - 采样假定存在非负函数h ( x ) ，满足 n = f ) 9 ( 挑 o 而且n 已知。那么我们可以采用h ( x ) 作为修正乘积因子显见对于g - 随机数 f 有 ，：肛肛案 如果先放弃对于估计的无偏性要求，而只要求估计的相合性，则对于n 个独 立的g - 随机数l ，臼，我们可以通过比值，构造j = e ，( z ) 如的如下的估 第二章随机样本生成法 计量 l 瓣+ + 渊 k n 怒若怒 显见它是j = e ，( z ) 如的相合估计在某些假定下，它是渐进无偏的，即 艘e ( ，) 2 0 而且j 保留了重要度采样的特性，即当 ( z ) = c 粥时，j 就是j = e ，( z ) 出 于是，只要当h ( x ) 与描近似，就会降低方差注意对于给定的分布密度 g ( x ) h ( x ) 应选取的尽量与籍近似这个修正乘积因子h ( x ) 是用来再一次降 低由于密度g ( x ) 与被积函数“x ) 的倍数不够像所带来的失误而设置的而当 h ( z ) i 1 时，就退化为g - 采样，这相当于对g - 采样不再做修正 9 湖北大学硕士学位论文 第三章m c m c 算法的构造 m c m c ( m a r k o vc h a i nm o n t ec a r l o 算法) 是一种简单有效的计算方法，在 统计物理，b a y e s 统计计算，显著性检验，极大似然估计等领域有着广泛的应 用m c m c 的基本思路是：通过建立个平稳分布为”( z ) 的m a r k o v 链来得 到”( z ) 的样本，基于这样就可以做各种统计推断 3 1 问题的提出 对一给定的状态空间x ，给定的密度函数瓢，满足0 丘和 o o ( 一般情 况下x 是r d 上的一个开子集，和是l e b e s g u e 测度) ，由密度函数唧，可给出 x 上的一概率测度”( ) ，即 ”( a ) = 瓣f a ”( x ) d x ( 3 1 ) 又定义函数i ：x r 关于z ( - ) 的期望为。 砌m = 借 ( 3 - 2 ) 但若x 是高维的，且是一复合函数。则( 3 2 ) 式的直接积分法是不可行的 对高维积分问题，经典的m o n t e c l o 算法是去模拟i i d 的随机变量z l ，z 2 ，z 一 口，用 亓= ( 丙i ，。i - nl ，( 磊) ( 3 3 ) 来估计”( ，) 由于 e 【膏( ，) 】2 亩e 【，扛) j = 蜀r 【，( x ) 】。一( ，) 故女( ，) 是无偏估计又 ”。r 女( ，) = 击【”。r ，( z ) j = 嘉【丌( ，2 ) 一防( ，) 】2 】一d ( 寺) 若”( ，2 ) 0 0 ，则由经典的中心极限定理，女( ，) 一一( ，) 的误差为平凡的极限分 布但问题是，若轧是复合的，将非常难去估计”( ) 的i i d 的随机变量 第三章m c m c 算法的构造 m c m c 解决这一问题的方法是构造x 上个以”( ) 为平稳分布的m a r k o v 链为此，首先定义一个m a r k o v 链以p ( x ，由) ( ( z ，y ) x ) 为转移概率的平稳 分布 定义3 1平稳分布一个链的若满足性质一对任意的n20 ，任意的k ， 有 ，做) 与 ，如+ - ) 的分布相同，则称该链的分布为平稳分布。 注x 上一一有限测度”若满足 ， p ( d y ) = f f ( 如) p ( z ，d u ) = ”( d u ) ( 3 4 ) j x e x 则称，r 为不变测度一个以”( ) 为平稳分布的m a r k o v 链一定含有不变测度 丌( ) 这样，如果我们对m a r k o v 链运行足够长的时间( 以任意点为起点) ，对足 够大的n ，j 的分布将会近似的趋向平稳tl ( j ，n ) * r ( ) ，此时可令z l ；， 再重新运行m a r k o v 链，可依次得到历，z 3 ，即可由( 3 3 ) 式得到”( ，) 的估 计女( ，) 表面看起来似乎很难找到这样的m a x k o v 链，然后直接得出”( ，) 的估计 但在事实上，在后面的介绍中我们可以看到m a r k o v 链的构造通常是出乎意料 的容易的 3 2 m e t r o p o l i s - h a s t i n g 采样法 构造m c m c 的方法有许多，这里我主要介绍m e t r o p o l i s - h a s t i n g 采样法 基本思路， 任意选择一个不可约的转移概率q ( x ，) 以及个转移概率n ( ，) ( 0 a ( x ， 1 ) ，对任一组合扛，一) ，定义， p ( x ，一) = q 扛，一) a 扛，一) z 一 p ( x ，一) = 1 一口( 而一) 口扛，z ) d z = 一 j 。一 易见p ( z ，一) 构成一个概率转移核 此方法的实施比较直观，如果链在时刻处于状态z ，即置= z ，则首先 由q ( 恤) 产生一个潜在的转移z 一一，然后以概率a ( z ，一) 接受一作为链下一 时刻的状态值，而以概率1 一a ( z ，一) 拒绝转移到一，从而链在下一时刻仍然处 于状态n 1 1 湖北大学硕士学位论文 我们的目标是使”( z ) 成为马氏链的平稳分布，下面就介绍在给定q ( x ，y ) 后，如何选择a ( x ，) 一个常用的选择， 出，胡= m i n l 描 ( 一) 口( 一，z ) 口( 。) q 仁，一) 丌( 一) 口( 茁7 ，z ) 7 r ( ) 口( z ，z 7 ) 定理3 1 由上述过程产生的m a r k o v 链是可逆的，即 ( 一) p ( z ，。) = 7 r ( z ) p ( z ，一) ( 3 5 ) 且”( 。) 是m a r l m v 链的平稳分布 证明若z = 一，则上式显然成立下面设z z - ，则 霄( z ) p ( z ，一) = 小m x ) m i n l ，甍珊智) = m i n r ( ) 口( z ，z ) ，r ( 一) 口( 一，z ) = 删，z ) r a m 署鬻舞1 ) = 霄( z 7 ) p ( z ，z ) 所以( 3 5 ) 成立 因为( 3 5 ) 式成立，所以有t m ) p ( 那，) 如= 彬) = 删) p ( 一z ) = 删) ( 最后一个等号成立是因为p ( 一，z ) 是个概率核) 所以，”( z ) 是m a r l l 【a v 链的平稳分布，证毕 m e t r o p o l i s - h a s t i n g 采样法的具体步骤； 1 任意选取m a r k o v 链的一个初始状态x 0 = z 2 由转移核q ( ，z ) 产生一个尝试移动一 1 2 籍 妒 铲 矗 氙 g g ，_-l_【 = fr 0 有 p 1此 第三章m c m c 算法的构造 3 生成u ( o ，1 ) 随机数“，如果u o ，当n 至少为多大时有 i i p ”( 戤a ) 一口( a ) i i 0 即使是咖不可约链也不一定收敛到平稳分布，比如说在周期情形下，如 下面的一个简单例子 设x = 1 ，2 ，3 ，f 1 】= , q 2 1 = 口【3 】= ，令e ( 1 ，2 ) = p ( 2 ，3 ) = p ( z ，1 ) = 1 则 ”( ) 为平稳分布，且该链为乒不可约链【如( - ) = 6 t ( ) 】但是，如果令x o = 1 ， 且只要是3 的倍数就有j l = 1 ，则p ( 五。) = 1 的取值在0 和1 之间震荡，故 p ( j k = 1 ) 一z 【3 】，即乒不可约链没有收敛到平稳分布 为了避免上述问题，现引入非周期性的概念 定义4 3 个有平稳分布”( ) 的m a r k o v 链是非周期的，如果这里不存在 d 2 以及不相交的子集x 1 ，x 2 ，x d x ，使得对所有的z 躲( 1 s i d - 1 ) 1 5 湖北大学硕士学位论文 有p ( z ，x i 一1 ) = 1 ，并且p ( 。，x 1 ) = 1 对所有z x d ，使得( x 1 ) o ( 因此对所有 i 有”( x i ) o ) ( 否则，链称为周期的，有周期d ，周期分解为x l ，x 2 ，) 综上述定义。可得到如下定理。 定理4 1 在个有可数生成一域的状态空间上，若m a r k o v 链是仁不可 约的，非周期的，且有平稳分布”( ) ，则对”一n e ，z x ，有 ，熙l l p ( x ，) 一”( ) l i = 0 特别的，对所有测度a 骼有u m 一。p ( z ，a ) = r ( a ) 引理4 1 在定理4 1 的条件下，如果h ：x r 且 r ( i h l ) o o ，则强大数 定理也是成立的，如下t 1 ，墨( i ) 冬l h ( x d2 7 r ( ) w p ( 4 1 ) 由于对m c m c 算法，通常建立的要求是”( ) 是甲稳分布，且一般会直接明确 链是咖不可约的( 如一定区域上的l e b e g u e 测度) ，非周期性也一般成立( 如对 m e t r o p o l i s 算法或g i b b s 算法) ，故定理1 被广泛的应用于m c m c 算法中 引理4 2 ( 在周期的情形f ) 如果一个m a r k o v 链是争不可约的，有周期 d 2 ，且有平稳分布 ( ) ，则对7 r d e ，z x ，有 桌恐i i 嵩。p ( ”) 一”( 。) 1 1 = 0 ( 4 ，2 ) 并且强大数定理( 4 1 ) 也是同样成立的 4 3 一致遍历 定理4 1 给出了定性收敛到平稳分布的条件，但是并没有指出以多大的速 率定量收敛，和定量收敛有关的一个性质就是一致遍历 定义4 4 个有平稳分布”( ) 的m a r k o v 链是一致遍历的，如果存在 p 1 ，m o o ，使得 0 p ”( ，) 一( ) 0 m p n ，n = 1 ，2 ，3 关于一致收敛有下列命题成立t 命题4 2 个有平稳分布7 r ( ) 的m a r k o v 链是一致遍历的的，当且仅当 存在n n ，使得下式成立： 1 s u p i i p “( x ，) 一口( ) | | 妄 z e x 1 6 第四章m a r k o v 链的收敛性 证明；。辛若链是一致遍历的，则 l i r as u p i 忙”( z ，) 一f ( ) l i 曼u mm ，= 0 一。z e x一 故对足够大的n ，有s u p z x0 尸”( ”) 一，r ( ) 0 幸若存在n n ，使得s u x0p ，l ( z ，) 一 ( ) 0 0 ，概率测度一( ) 使得最 小化条件( 4 3 ) 成立则该m a r k o v 链是一致遍历的，并且对所有的z x 有 0 p ，l ( q ) 一一( 训( 1 一) 。嚣。，这里。r 一是不超过r 的最大整数 定理4 2 给出了0 p ( 即) 一”( - ) 0 定量收敛到一有界值的条件，注意它必须 是( 1 一s ) 嚣。因此，一旦n o 和已知，就可以找到n 。，使得0 p m 扛，) 一- ( ) l l o 0 1 这些在m c m c 中有着非常重要广泛的应用 对离散状态空间的情形，令 g n o2 蛾鉴扩( 删) o 贝0 同样有0 p n ( z ，) 一* ( ) 1 1 ( 1 一) 。盖。 1 7 湖北大学硕士学位论文 4 4 几何遍历 比一致遍历条件稍弱的是几何遍历 定义4 6 个有平稳分布 ( ) 的m a r k o v 链是几何遍历的，如果当m c x ) o o 时，对口一a e ，z x ，存在p 1 满足 i i 尸”( z ，) 一口( | ) | | s f ( z ) p n ， n = 1 ，2 ，3 定义4 7 ，称一个m a r k o v 链满足转移条件，如果存在常数0 1 ，b 0 ，以及概率测度”( ) 使得最小化条件( 4 3 ) 成立又进一步 设存在常量0 a 1 ，b 1 , n 0 n 9 0 ，使得( 4 3 ) ，( 5 1 ) 成立，定 义b 如( 5 2 ) 则对任意联合初始分布l ( x o ) ，工( 弼) 任意整数1 j k ，如果 ) ， 霸) 是l ( x o ) ，工( 弼) 上的两个m a r k o v 链，则 i i l ( x k ) 一工( x k ) t ls ( 1 一e p + a 一b ，一1 e h ( x o ，弼) 】 定理5 1 的证明将在后面用耦合构造的方法给出这个定理的各种变型和 推广已经广泛的应用于m c m c 算法中，虽然很难直接将定理5 1 直接应用于 实际的m c m c 算法，但是它确实建立了严格的，精确的，可行的公理去确保 m a r k o v 链的定量收敛，因此具有很好的理论指导意义 5 2 用耦合的方法证明定理 5 2 1 耦合不等式 1 9 湖北大学硕士学位论文 关于耦合最基本的思想即为下式，设在空问x 上有两个联合定义的随机 变量x ，y ，如果令工( x ) ，l ( y ) 为它们分别的概率分布，则有 i i l ( x 一( x ：) 0 = s u p i p ( 戤a ) 一p ( x ；a ) f a = s u p i p ( x k a ，x k = 墨) + p ( x k a ，x k 墨) a p ( 磁a ，凰= 嬲) 一p ( 磁a ，讯氍) i = s u p i p ( x k a ，x k 磁) 一p ( 磁a ，x k 氍) i a 冬p ( x k x k ) ( 5 3 ) 5 2 2 耦合的构造 设c 是小集，从x o = 易弼一”( ) ，n = 0 开始，一直重复下列步骤 对给定的，弼 1 若= 嬲，则令+ l = 墨+ 1 一p ( ，) ，用n + 1 代替n 2 若弼且( ，碟) c c 则 ( a ) w p 选择矗+ t l o = 磙+ m 一 ( - ) ( b ) w p 1 一条件独立的选择 + n o r 乏1 p ，) 一”( ) 磁+ t i o 一壬i f p ( 弼，) 一e ”( ) 】 若霹且( j 0 ，嬲) 聋c c 则独立的选择 + 1 一p ( ，) ，磁+ 1 一p ( 霸，) ， 用n + l 代替1 1 由此构造得到的 ， 磁 n = 1 ，2 ，3 即是l ( x o ) ，l ( 弼) 上的两个 m a r k o v 链 5 2 3 定理5 1 的证明 ( i ) 令n k = # m ：0 m s ，( x m ，霸。) c g ) ，令( j ，磁) 到达c c 的 时刻为n ，见，对任意整数j ( o sj k ) 有 p x k 磁】= p x k 磁，n k 1 2 卅+ p x k 氍，帆一l j 】( 5 4 ) 2 0 第五章m a r k o v 链的定量收敛 由于事件 凰磁，n k 一12 办2 噩墨，( x t ，墨) c c , t = 1 ，j ) 面由耦合的构造知 p 五= 墨，( 而，雹) g c ) = e 净p p “魁，肌一1 翊( 1 一y ( 5 5 ) 为证明( 5 5 ) 式第2 部分的有界性，令 m k = 舻口一肌一- ( 溉，氍) t ( x k 磁) ，k = 0 ，1 2 其中_ l = 0 ( i i ) 引理te 【慨+ li 弱，瓤，弼，氍】m k e 即 m d 是上鞅 证明，若( 汛，冠) e a 则由帆的定义帆= n k “故 e m k + 1l ，尥，粥，氍】 = 扩+ 1 b 一心一e h ( x k + l , 磁+ 1 ) j ( 拖+ l 冠+ 1 ) l 瓢，氍1 舻+ 1 b 一帆一1 e h ( x k + l ，x 。i + 1 ) i 戤，x k i ( x k x k ) = m k a e h ( x k + 1 ，墨+ 1 ) l 溉，墨 h ( x k ，墨) = m k a - p h ( x k ，磁) h ( x k ，磁) sm k 同样，若( 溉，磁) c c ，则n k = 肌一1 + 1 ，不妨设x k 磁( 若溉= 磁则 m k + l ； 靠= 0 ) 则有 e f 螈+ 1i 硒，弼，戤】 = a k + l b 一肌r 1 e h ( x j , + 1 ，磁+ 1 ) i ( x k + 1 磁+ 1 ) i 甄，磁】 = = 矿+ 1 b 一一l 一1 ( 1 一) ( 西h ) ( x t ，x ：) = 地口b l ( 卜) ( 面 ) m ，砭) 肪，磁) 地 综上有m k 是上鞅 ( 谢) 由定义知b 1 ， p 陬冠，机一1 刃= p 陬氍，肌一1sj 一1 】 p 【j 氍，b 一- 一1 b o 一1 ) l = p f ( x 七群) b 一t2b o 一1 l b j 一1 e 【( 凰冠) 】b 一帆一- ( c am a r k o v 不等式) 一1 e 【j ( 凰磁) 】b 一帆一t ( 凰，磁) 1 ) = o z - k b j 一1 e m k 】o 一b j 一1 e m o 】 ( 由 缸是上鞅) = a 一伊e h ( x o ，弼1 ( 由的定义) ( 5 6 ) 2 1 湖北大学硕士学位论文 联合( 5 3 ) ( 5 ，4 ) ( 5 5 ) ( 5 6 ) 可得 i i l ( x k ) 一| l ( 磁) 0 ( 1 一p + a 一一1 e h ( x o ，弼) l 定理证毕 参考文献 参考文献 【1 】a n d r i e nc ，f o r tg e x p l i c i tc o n t r o lo fs u b g e o m e t r i ce r g o d i c i t y 吲r a p p o r td e r e c h e r c h e , 2 0 0 5 ，0 5 ：1 7 f 2 】b a x e n d a l eph r e n e w a lt h e o r ya n dc o m p u t a b l ec o n v e r g e n