（概率论与数理统计专业论文）mcmc算法中的metropolis算法的相关理论问题.pdf

中文摘要 捅要 本文主要介绍m a r k o v 链m o n t ec a r l o 算法中i 拘m e t r o p o l i s 算法的基本思想以及该算 法所涉及的一些基本理论知识。其中，在使用m e t r o p o l i s 算法时，我们主要关注算法 中预选矩阵p 的选取和该算法收敛速度的问题，由此产生了该算法满足一致遍历性， 几何遍历性以及算法定量收敛到平稳分布的条件。在这些条件的证明巾，我们摒弃了 冗长的分析方法的证明，而是选择了耦合构造的证明方法。特别，在算法定量收敛到 平稳分布( 定理4 5 1 ) 的证明中，我们主要给出了当n o 2 情形的详细证明。 关键词：预选矩阵；一致遍历性；几何遍历性：平稳分布；耦合构造 湖北大学硕上学位论文 a b s t r a c t i nt h i sp a p e r , w ei n t r o d u c et h em a i ni d e aa n dt h eb a s i ct h e o r e t i c a lk o n w l e d g eo ft h e m e t r o p o l i sa l g o r i t h mi nt h em a r k o vc h a i nm o n t ec a r l oa l g o r i t h m i nt h eu s eo fm e t r o p o - l i sa l g o r i t h m ，w ec o n c e r ni nh o wt os e l e c tt h ep r o p o s a lm a t r i xpa n dh o wq u i c k l yd o e st h i s c o n v e r g e n c et a k ep l a c e t h e nw eg i v et h e c o n d i t i o n st h a tw h e nt h i sa l g o r i t h mi su n i f o r m l ye r o g o d i co rg e o m e t r i ce r g o d i co rq u a n t i t a t i v ec o n v e r g e n c e i nt h ep r o o fo ft h i st h e o r e m s ，w ea v o i d m a n yl o n ga n a l y t i ct e c h n i c a l i t i e sb u ts e l e c tu s i n gd i r e c tc o u p l i n gc o n s t r u c t i o n st og i v et h e p r o o f s e s p e c i a l l yi np r o o f i n go f t h ea l g o r i t h mq u a n t i t a t i v ec o n v e r g e n c et os t a t i o n a r y ( t h e o r e m 4 5 1 ) ，w eg i v et h ep r o o f sw h e nt h ec a s eo fn o 2 k e yw o r d s ：p r o p o s a lm a t r i x ；u n i f o r m l ye r g o d i c ；g e o m e t r i ce r g o d i c ；s t a t i o n a r yd i s t r i b u t i o n ；c o u p l i n gc o n s t r u c t i o n 玎 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究 成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本人完全意识到本声明的法律后果由本人承担。 学位论文使用授权说明 作者签名：姜瑾 签名日期：训年；月牛e l 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本：学校有权保存并向国家有关部 门或机构送交论文的复印件和电子版，并提供日录检索与阅览服务；学校可以允许采 用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的的前提下， 学校可以公开学位论文的部分或全部内容。( 保密论文在解密后遵守此规定) 日期：- 暑年6 月卑日 日期：知h 陴月乒日 第一章引言 第一章引言 蒙特卡罗方法的基本思想 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 方法得到广泛的发展和应用特别是随着科学技术的发展，出现了许多复 杂难解的问题例如核物理中描述质点运动的迁移运动方程 1 1 , 2 3 , 3 8 ；大型系统的可靠性 分析 2 7 3 5 1 ；地震波的模拟实验；高维数学问题求解【9 2 5 3 7 1 ；多元统计分析；医学，技术中 的诊断，识别；大型生产过程中的运筹规划等等【3 9 1 ，用传统的物理实验或数学方法进行处 理十分困难，这时进行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 i nm o n t e c a r l o ( m c m c ) 方法这足动态的蒙特卡罗方法由于这种方法的问世，使随机模拟在很多 领域的计算中，相对于决定性算法，显示出它的巨大的优越性 m c m c 方法至少可以用在以下几个方面【4 1 1 ： ( 1 ) 用于生成较复杂的随机数 ( 2 ) 实现高维积分( 或项数极多的求和) 的数值计算( 例如计算g i b b s 分布的各种泛函 的平均值) ( 3 ) 用模拟方法估计最口1 几轨道 ( 4 ) 用被估参数的b a y e s 分布的取样，来估计参数 ( 5 ) 求复杂样本空间上函数的极值( 模拟退火) 湖北大学硕士学位论文 第二章随机数及伪随机数 一般地说，利用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 方法的关键 2 1 一维随机数 均匀随机变量的计算机模拟 最常用的随机数是在区间【o ，l 】内的均匀分布的随机数( 简称均匀随机数，记 为u o ，l 】随机数) ，其它任意分布律的随机数可以利用均匀分布的随机数来产生事实 上现在已经有一些制备好的随机数表可供我们计算使用这些表除了可供手算使用 外，原则上也可在电子计算机上使用( 把随机数表输入计算机存储起来备用) 但是由于计 算时常常需要大量的随机数而电子计算机的存储容量又有限故实用中一般采用伪随 机数来代替随机数使用实践证明，伪随机数是均匀随机数的一种可行的近似这种伪随 机数虽然不是独立同分布的u o ，l 】随机变量的样本，而是在【0 ，1 】中取值的周期数列，但是 由于它可以像均匀随机数一样地通过数理统计中的独立性与均匀性假设检验，而且它 的周期非常长，以至在计算机实际运算过程中不会出现重复，所以在实际计算中它能很 好地替代均匀随机数 最普遍用以产生伪随机数的方法是同余法典型的例子如下： y n + 1 = 5 1 3 y n ( m o d 2 3 6 ) ，y o = 1 ，z n = 2 - 3 6 蜘( 周期约为2 1 0 1 0 ) y n + 1 = 5 1 7 y n ( m o d 2 4 2 ) ，y o = 1 ，z n = 2 - 4 2 蜘( 周期约为2 1 0 1 2 ) + 2 = + l4 - y n ( m o d 2 4 4 ) ，y o = 1 ，y l = 1 ，z n = 2 4 4 鲰( 周期约为；1 0 1 4 ) 分布函数为f ( x ) 的随机数 分布函数为f ( z ) 的独立随机变量列的样本，称为f ( z ) 随机数 命题2 1 1 4 u 若f ( z ) 严格单调增加，是均匀随机数，则f _ 1 ( f ) 是f ( z ) 随机数，其 中f 一1 为f 的反函数 命题2 1 2 【4 i 】设随机变量只取有限个值，其分布为一i 山1 h l ，把【o ，l 】分 jf fl 朋m 2 第二章随机数及伪随机数 为n 个不交的予区间，使第i 个区间五的长度为p i 任取均匀随机数u ，则 t i 甄“( u ) i = 1 就是一个随机数( 它的意思是：如果u 落入了止，就取= 钆) 正态随机数 n ( o ，1 ) 随机数称为标准正态随机数生成标准生态随机数有一个比反函数的方法更 为简单的实践方法，就是利用中心极限定理设7 7 l ，研1 2 ) 为均匀随机数，且它们是独 立的，由中心极限定理，可以认为= 叩1 + + r h 2 - 6 n ( 0 ，1 ) ，即用f = r h + - - r 1 2 - - 6 近 似地作为标准正态随机数，在实际计算中碾( 1 i 1 2 ) j 丕应该用伪随机数代替 命题2 1 3 1 4 1 1 ( 生成标准正态随机数的b o x m u l l e r 方法) 取两个独立的均匀随机 数7 7 1 ，7 2 ，令 1 = 、一2i n7 7 1c o s ( 2 7 r r 2 ) ， 已= 、一2 i nr 1s i n ( 2 丌啦) 则f l ，已为相互独立的标准正态随机数 命题2 1 4 1 4 1 1 ( 生成标准生态随机数的m a r s a g l i a 方法) 设( x ，y ) 为单位园上的均匀 随机数，则 ( r ) 全、- 2 1 n ( x 2 + y 2 ) ( x ) 一( ( ：) ，1 l ：) ) 一般正态随机数的生成：若为标准正态随机数，则仃+ p 为( p ，口2 ) 随机数 p o i s s o n 随机数 设巩，是相互独立的【o ，l 】均匀随机数若 则定义n = n ，那么满足参数为a 的泊松分布 混合分布随机数 对于权重为p l ，陬( 和为l 的n 个正数) 的混合分布随机数，有命题 命题2 1 5 4 1 1 设u v o ，1 】，0 = t o t n = 1 ，t i t i _ 1 = p i ( i n ) ，只( z ) ( i 3 巩 。随 一 入 一e 巩 州腻 湖北大学硕- 上学位论文 n ) 为分布函数，那么 壹f ( 旦三粤) 厶。 ) ( ) 。分布函数为妻a r 的混合分布 i = 1 ，l i = 1 v o nn e u m a n 取舍原则 假定我们要生成密度为p ( z ) 的随机数为此取一个参考分布密度m ( z ) ，使它满足： ( 1 ) 如( z ) 随机数容易生成，例如伽( z ) 为正态密度、均匀密度、指数密度，及它们的 混合密度等： ( 2 ) 伽( z ) 与p ( z ) 的取值范围差不多，且存在c ，使p ( z ) c p o p ) 则有以下命题： 命题2 1 6t 4 1 1 设随机变量7 7 具有密度伽( z ) 而随机变量u v o ，1 】且与7 7 独立，则 确纠龋猢= 仁咖川 取舍原则的具体作法是： ( 1 ) 独立地生成n 个独立的p o ( z ) 随机数叩l 一，与n 个与之独立的v o ，1 】随机 数仉，“ ( 2 ) 对于i = 1 ，2 ，如果有焉阢，就保留仇，否则舍弃侬 这样，所有这样保留下来的吼就成为一系列独立的p ( z ) 随机数( 当然个数会比n 小很 多) 这种取舍方法称为v o nn e u m a n 取舍原则 2 2 多维随机数 连续型多维随机数 对于已知的分布密度，可以利用条件密度，把生成多维随机数归结为生成一系列一 维随机数：设随机向f l ( x 1 ，) 的密度茭3 f ( x l ，x 2 ，黝) ，则有表达式 f ( x 1 ，x 2 ，x d ) = 厶( x 1 ) f ( x 2 l x l ) ，( 黝i z l 一，x d 1 ) ， 其中厶。( x 1 ) 为x 1 的边缘密度，f ( x k l x l ，瓢一1 ) 为在已知x 1 = x l ，虬一1 = 巩一1 条 件下，磁的条件密度于是可以先取一个厶。随机数z l ；然后，在固定x l 的情形下生 成一个，( i z l ) 随机数；再在z 1 ，z 2 固定的情形下，生成一个，( i z l ，z 2 ) 随机数；最后，在同 定z 1 7 一，x d - 1 的情形下，生成一个，( l z l 一，x d 1 ) 随机数黝，这样得到的就是随机向 量( x l 一，) 的一个随机数 4 第二章随机数及伪随机数 离散型多维随机应数 只要用概率函数p ( z l ，z 2 ，z d ) d = e fp ( x 1 = z l ，托= 黝) 代替密度函数，上面 方法自然适用 多维正态随机数 设( x 1 ，) 服从似，) ，其密度函数为p ( z ) = 历予枷e - 1 1 2 ( z - p ) r - 1 霉一川，其 中= ( ) i j s d 为对称正定矩阵由线性代数知，可以找到下三角形矩阵c ，( = 0 ，v i 歹) ，使= c 伊作独立( o ，1 ) 随机数l ，白令全( l ，白) t ，则c + p 一 ( p ，) 可见伏+ p 为( p ，) 随机数于是求多维正态随机数的快速生成问题，就归结 为快速计算下三角形矩阵c 的问题 5 一 湖北大学硕上学位论文 第三章m a r k o v 链m o n t ec a r l o 算法中的m e t r o p o l i s 算法 前面我们讨论t m o n t ec a r l o 算法的基本思想以及一些随机数与伪随机数的取法问 题，下面我们通过一个问题来引出什么是m c m c 算法 3 1 问题 问题：给定某状态空间x 上的密度函数和，它满足o 厶和 0 , r t 取 多大时有l l p n ( z ，) 一7 r ( ) l l 0 例子4 2 1 假设7 r ( ) 为概率测度，密度函数礼为d 一维勒贝格测度考虑m e t r o p o l i s 算 法此时令预选密度p ( x ，) 也为d 一维勒贝格测度如果p ( ，) 是尉x 上正连续函数，靠处 处为正，则该算法是7 1 - - 不可约的事实上，令丌( a ) 0 ，则存在r o 使得7 r ( a 凡) 0 ， 其中a r = anb r ( 0 ) b n ( 0 ) 是以0 为原点半径为尉拘圆球，则由连续性，对任意z ，对 某e o 有i i l f 可 凡m i np ( z ，秒) ，p ( v ，z ) e ，贝u p ( z ，a ) p ( z ，a r ) = 上r p ( z ，可) m i n 【l ，糍】咖 e l e b ( 【yea r ( ) 和( z ) ) ) + 乏高丌( yea n ：( 可) o ，因为7 r ( ) 对勒贝格测度绝对连续，且l e b ( a n ) o ，则( 4 1 ) 式的 后两项不可能同时为0 ，故有p ( x ，a ) o ，因此该m a r k o v 链是7 r 一不可约的 然而即使m a r k o v 链是西一不可约的也不一定收敛到平稳分布，还需要m a r k o v 链是非 周期的 例如：假设x = 1 ，2 ，3 】7 r ( 1 ) = 7 r ( 2 ) = 7 r ( 3 ) = ；令p ( 1 ， 2 ) ) = p ( 2 ， 3 ) ) = p ( 3 ，_ 【1 ) ) = 1 则7 r ( ) 是平稳分布hm a r k o v 链是一不可约的然而如果x o = 1 ，当n 是3 的 倍数时总有x n = 1 ，因此p ( = 1 ) 在0 与l 之间振荡跳跃，即p ( = 1 ) 唧7 r ( 1 ) ，因 l l 扫d a r k o v 链也不收敛到平稳分布7 r ( ) 这样我们还需要非周期的定义。 定义4 2 21 2 0 1 拥有平稳分布7 r ( ) 的m a r k o v 链是非周期的，如果不存在d 2 和不交子 集x 1 ，恐，x a x 满足p ( x ，x i + 1 ) = 1z x i ( 1 i d 一1 ) 且p ( x ，x 1 ) = 1z ，使得丌( x 1 ) 0 考虑例子4 2 1 的情形，假设x 1 和托为x 的不相交子集且都为7 r 正测度，并且 有p ( x ，配) = 1 ，z x 1 任取z x 1 ，因为x 1 有勒贝格正测度，故 e ( z ，x 1 ) p ( z ，可) q ( z ，可) d y 0 j y e x x 1 0 第四章相关定理及其证明 矛盾因此例子4 2 1 的非周期性成立对于其他的m c m c 算法也有相似的结论，例 如g i b b s 样本也有满足非周期的结论【3 7 1 现在我们可得出下面收敛定理 定理4 2 1 【2 0 lm a r k o v 链在盯一代数可数生成状态空间上是西一不可约，非周期，且有平 稳分布7 r ( ) ，则对7 r a e z x ，有 l i m0 p ( z ，- ) 一7 r ( 训= 0 n + 特别，对所有可测a x ，l i k 。p r ( z ，a ) = 丌( a ) 事实上，在定理4 2 1 的条件下，如果 ：x r r 有丌( i h l ) 0 和所 有z x ，m a r k o v 链从z 出发以概率1 最终到达b 例如p 【| 礼：墨b i x 0 = z 】= 1 该条 件要强于7 r 一不可约性关于h a r r i s 常返的讨论可参考文献【3 7 定理4 2 1 已经说明m a r k o v 链渐近收敛到平稳分布，但并没有说明收敛的速度有多 快一致遍历性即是一个关于m a r k o v 链收敛速度的性质 湖北大学硕上学位论文 4 3 一致遍历性 定义4 3 1 拥有平稳分你的m a r k o v 链是一致遍历的，如果对某p 1 和m o o ，有 p n ( z ，- ) 一7 r ( ) l i m p - ，n = 1 ，2 ，3 ，zc x 一致遍历性一个等价的命题为： 命题4 3 1 拥有平稳分布的m a r k o v 链是一致遍历的当且仅当对某佗 n ，s u p z _ c x | i p ( z ，。) 一7 r ( ) l i 1 2 证明如果m a r k o v 链是一。致遍历的，则 l i ms u pi i p ( z ，) 一7 r ( ) l l l i mm p n = 0 n + z c _ x ”+ 故对充分大的凡，：i 肓s u p 。xi lp ，l ( z ，) 一7 r ( 训 1 2 反之，如果对某n n ，有s u p 。xl lp l ( z ，) 一7 r ( ) 1 1 0 和概率测 度( ) ，最小化条件成立特别若c = x ( 即整个窄问为- - , b 集) ，则该m a r k o v 链是一致遍历 的且事实上，对所有z x ，有i i p ( x ，) 一7 r ( 训( 1 一e ) b o a 其中l r j 是不超过7 的最大 整数 关于一致遍历性可参考文献【1 4 1 2 第四章相关定理及其证明 如果m a r k o v 链不是一致遍历，则定理4 3 1 不能适用但我们还有下面较弱形式的遍 历定理 4 4 几何遍历性 定义4 4 1 拥有平稳分布7 r ( ) 的m 矧k 0 v 链是几何遍历的，如果对某j d l ，有 i i p 祝( z ，) 一7 r ( ) 0 m ( z ) 矿，n = l ，2 ，3 ， 其中m ( z ) o o 对丌一a e z x 几何遍历性与一致遍历性的不同之处是现在m 依赖于初始状态z 关于几何遍历性的背景可参考文献【2 0 ，2 2 定义4 4 2 给定x 上m a r k o v 链的转移概率函数p 和可测函数，：x _ r ，定 义p ，：x 只使得( p ，) ( z ) 是给定k = z 下，( 瓦+ 1 ) 的条件数学期望，记为( p ，) ( z ) = 止x ，( 可) p ( z ，咖) 定义4 4 3m a r k o v 链满足漂移条件，如果存在常数0 a 1 ，b o ，概 率测度( ) 满足最小化条件，并且对o a 1 ，b 1 ，有 p h ( x ，y ) h ( x ，y ) q ，( z ，y ) 隹c c( 4 4 ) 其中鼽( z ，y ) 三f x 厶h ( z ，w ) p ( x ，d z ) p ( y ，d w ) 命题4 5 1 假设对函数矿：x 一【1 ，c o ，c x ，a o ，使得( 4 2 ) 式和( 4 4 ) 式成立如( 4 5 ) 式定 义鼠。，则对任意的初始联合分布z ( ，蜀) ，任意整数1 j 后，如果和k 为从联合 初始分布z ( ，墨) 出发的两条独立的与原链具有相同转移概率的m 蝴链，则有 z ( 托) 一z ( ) i j ( 1 一e ) + q 一七( 最。) e h ( x o ，) 】 下面我们就来证明定理4 5 1 。在证明该定理之前，我们首先介绍耦合构造 耦合不等式： 假设知道随机变量x ，y 的联合分布，z ( x ) ，z ( y ) 分别表示x ，y 的概率分布，则 z ( x ) 一z ( y ) i i = s u pi p ( x a ) 一p ( y a ) i = s u pl p ( x a ，x = y ) + p ( x a ，x y ) a p ( y a ，y = x ) 一p ( y a ，y x ) i = s u pi p ( x a ，x y ) 一p ( y a ，y x ) 1 5 湖北大学硕上学位论文 p ( x y ) 即 l i c ( x ) 一z ( y ) l i p ( x y ) 即两随机变量全变差范数由它们不相等的概率来控制 1 5 , 2 4 , 3 6 小集与耦合构造： 设c 为小集， k 与 k ) 为两条m a u r k 0 v 链，下面进行耦合构造： 当n = o 时，x o = z ，矗一7 r ( ) 当给定k ，k ，则 1 ) 如果= k ，取+ l = k + 1 一尸( k ，) ； 2 ) 如果k ，但( ，k ) c c ，则： ( a ) 以概率e 取+ 伽= k + 帅一( ) ； ( b ) 以概率l e 取 1 慨“亡【p ( ，) 一e ( 。) 】 k + 伽一五1 【p ，l o ( k ，) 一e ( ) 】 其中k + 伽与k + 。相互独立 当n o 1 时， + l 一尸( 以，) ，+ n o 一1 一p ( + 伽一2 ，) k + 。一p ( k ，) ，k 慨一。一p ( k 慨却) 其中+ l 与k + 1 相互独立，k + 2 与k + 2 相互独立， 3 ) 如果k ，且( k ，k ) 聋c c ，则+ 。一p ( 凡，) ，k + 。一p ( k ，) ，其 中k + 1 与瓦+ 1 相互独立 在这样的构造下，有p ( a ) = p ( z ，a ) ，p ( k a ) = 丌( 以) ，n n 证明定理4 5 1 假设n o = 1 ，记鼠。为b ，令 肌= # m ：0 m k ，( x m ，矗) c c ) 丁l = i n f n 0 ，( ，) c c ) 1 6 第四章相关定理及其证明 对任意1sj 七，则 死= i n f n 丁1 + 1 ，( k ，k ) c c ) p ( x k ) = p ( x k ，n k l j ) + p ( x k 瓦，肌一1 ) 而 札一l j ) = 【勺sk 1 ) ，且 五瓦，勺k 一1 ) c 再令 ：。【k + t 疋+ 。) ，则 p ( x k ，n k l 歹) = e 【x 。x ：) 厶勺七一l 】 歹 e 【h + t = 1 j = e t e hi 【x t = 1 j i = e l h i 。婚 = 1 j i = e l h i l x t 一 。矗+ 。 1 q + 。矗+ 。) l 。矗+ 。，e 陬h 十，x 0 + 。i 】 。矗+ 。) 置h ，x 乞) 。x ：) 】 j i = ( 1 一e ) e 【 = ( 1 一e 尸 i = 1如+ 。x 乏+ ) 】 尥= a k b - n k - 1 h ( x k ，x ：) 以哟，k = 0 ，1 川2 我们需要证e 【慨+ ll x o ，凰，矗，墨】慨，即需要证 慨) 为上鞔 证明：如果( 溉，) 岳c c ，则m = m _ 卜 吲慨+ - i ，风，矗，x ：】 = e 【。m b 一肌h ( x k + l k + 1 ) ， 以+ 。x ：+ 。 i 虬，】 = e 【q m b - n i - , h ( x k + l + 1 ) j i x 川x ：+ 。) i 拖，】 = q 川b - n k - , e h ( x k + 1 ，+ ) 溉+ 。x ：+ 。) l 托，】 1 7 一 q mb 一肌e h ( x k + 1 + 1 ) l x k ，确k 。x ：) ：m k o e h ( x k + 。，+ 1 ) i x k ，x ：】h ( x 七，x ：) 慨 如果( 托，) c c , 贝j l g k = 肌一l + 1 假定虬k ( 因为在凰= 情况下，结论显 然成立) ，则 e 【尥+ l i ，虬，矗，硝 = e 陋七+ 1 b 一肌h ( x k + l ，x 0 1 ) ， 地+ 。x ：+ 。) i x 七，1 = q m b - n k _ , - a e h ( x k + l ，x 0 1 ) 札，x o i 甄，】 ：o l k + 1 b n k _ , - - i ( 1 一e ) ( - r h ) ( x k ，) = 地q b _ 1 ( 1 一) ( 页1 ) ( 虬，x ：) 危( x 七，x ：) 尥 故 慨) 为上鞅则 p ( x 七x ：，n k l 1 时，令 n ：i n f n 0 ，( ，k ) c c ) 1 8 第四章相关定理及其证明 则 吃= i n f n 7 1 + n o ，( k ，x ：) c c ) 肌= m a x j ：0 吩k ) p ( x k k ) = p ( 虬，帆一伽j ) + p ( x k ，肌一咖 j ) 由于 肌一伽歹) = 弓k n o ，且 兄k ，弓七一伽) c 厂瞧l x t + 伽 瓦+ 伽) ，则 p ( x k ，帆嘲歹) = e l i 托x d i ( 勺垡一伽) 】 j e 【 t = 1 = e 【e 【h + ，。x ) l & l l i = 1 j 一1 = e 【 i = 1 j - 1 h + x ：t + 引_ 伽x 乞伽 l 岛】 = e 【k 伽x ”i 。，& h ，_ i = 1 j - 1 = ( 1 一e ) e 1 - 1 i x l + ，。x ：t + ，。 】 t = 1 = ( 1 一e 尸 假设乃k n o 【k ， k 【勺+ n o + 1 ，乃+ 1 ) ，其中若勺+ 7 , 0 + 1 勺+ 1 ，则约定【巧+ n o + 1 ，巧+ 1 ) 为空 令 地= 口七础咖h ( x k ，) x 。x ： ，k = o ，1 川2 我们需要证明是否有e 尬( 七+ 1 ) i ，五( 七) ，碥，( 知) 】 尬( k ) ，即需要 证 尬( 七) ) 是否为上鞅 1 9 0 o n+ ，q x o n 卜 1 x l 1 ， 湖北大学硕：l 学位论文 证明：若七= 乃，乃一勺一1 = n o ，则七+ 1 ( 勺，乃+ n o ，i 救t ( k ) = 口一1 ，t ( k + 1 ) = 乃，这 时有一伽= 一。一加+ 1 ，则 e 【舰( 七+ , ) l x o ，x t ( k ) ，k ，( 奄) 】 = e 【蚝i x o ，x t ，- i , k ，x 乏一。】 。 = e 妒。勺咖j l ( ，瓦) j m ，x 纠h 刈一。】 = e l q 伽+ 耐一r j 一“。危( k ，瓦) x ，x 纠k ”瓦一。】 , = - o l 伽聒蚝一，引 ( ，墨) j m ，i 刈瓦一。 h ( x r j 毛一。) q 咖b = 朋r r j 一，( 1 一e ) ( r ) ( 如一。，一。) m r ( 柚 若k h ，乃+ 伽】，k + 1 【勺，勺+ n o ，则( 七) = 乃，t ( k + 1 ) = 乃，则 e 【尬( m ) l x o ，：，x t ( k ) ，矗，( 七) 】 = e 【蚝i x o ， = i t ( 七) ，如，矗，毛】 若后= 乃+ 伽，七+ 1 = 乃+ 佗o + 1 ，则t ( 后) = 乃，t ( 七+ 1 ) = 七+ 1 ，且肮+ 1 一f l o = 1 + 下j 一伽，则 e m t ( , + i ) i x o ，x t ( k ) ，x o ，x 晶】 = e i k + i ，k ，瓦】 = e 【口m 耐怯+ 1 一。 ( 托扎+ - ) k x o i ，砭】 = e 【q q 慨+ 1 一一。 ( h + 伽扎瓦+ 加+ 。) h 机“x _ 。+ 。) i ，瓦】 = q 州吲蚝引 ( 如+ n o + l 瓦慨+ ，) h 饥+ l x + 。) l b ，墨m 如，墨) q 时1 b = m t ( a ) ( 1 一e ) ( 葡 ) ( 如，瓦) ( 如，矗) s 舰 若七【勺+ n o + 1 ，弓+ 1 ) ，k + 1 【乃+ n o + 1 ，t j + i ) ，则t ( 七) = 尼，t ( k + 1 ) = k + 1 ， 且肌+ h 。：肌咖，则 e 【m ( 川) i = e 【慨+ 1 ，五( 七) ，矗， ，虬，矗， 2 0 y 1 ( k ) j 第四章相关定理及其证明 = e 【口川碟k + l - n o h ( x k + 1 + 。) + 。x ：+ 。 l 兄，】 e 时+ 1 耐- n i c _ r t 0 ( 甄+ 1 + 1 ) j x ： l 虬，x ：】 = a m k e h ( x 岛+ l + 。) i 托，瓦】危( 凰，) 舰( 七) 即 尬( 七) ) 为j 二鞅那么 p ( x k 砭，n k 一加 l 时，有 i z ( 儿) 一z ( ) | isp ( k ) ( 1 一e ) j + o t r t 。o l 一七磁i 1 e h ( x o ，墨) 】 2 1 湖北大学硕上学位论文 参考文献 【l 】a s m u s s e ns a p p l i e dp r o b a b i l i t ya n dq u e u e s m j o h nw i l e ya n ds o n s ，1 9 8 7 1 2 a t h r e y ak b d o s sh a n ds e t h u r a m a nj o nt h ec o n v e r g e n c e o ft h em a r k o vc h a i ns i m u l a t i o nm e t h o d j 1 9 9 6 ，2 4 ：6 9 1 0 0 【3 】a t h r e y ak b a n dn e yp an e wa p p r o a c ht ot h el i m i tt h e o r yo fr e c u r r e n tm a r k o v c h a i n j t r a n s a m e r m a t h s o c ，1 9 7 8 ，2 4 5 ：4 9 3 5 0 1 【4 】b a x e n d a l ep h 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 c er a t e sf o rg e o m e t r i c a l l ye 卜 g o d i cm a r k o vc h a i n s m u n i v e r s i t yo fs o u t h e r nc a l i f o r n i a ，2 0 0 3 【5 】b e r e n h a n tk a n dl u n dr b g e o m e t r i c r e n e w a lc o n v e r g e n c er a t e sf r o mh a z a r d r a t e s i j j a p p l p r o b ，2 0 0 1 ，3 8 ：1 8 0 1 9 4 【6 】c o w l e sm k a n dr o s e n t h a lj s as i m u l a t i o na p p r o a c ht 0c o n v e r g e n c e r a t e sf o rm a r k o v c h a i nm o n t ec a r l oa l g o r i t h m s j s t a t i s t i c sa n dc o m p u t i n g ，19 9 8 ，8 ：l15 12 4 【7 】d o o bj i s t o c h a s t i cp r o c e s s e s m w i l e y , 19 5 3 1 8 f o r tg c o m p u t a b l eb o u n d sf o rv - g e o m e t r i ce r g o d i c i t yo fm a r k o vt r a n s i t i o n k e r - n e l s m u n i v e r s i t yj o s e p hf o u r i e r , g r e n o b l e ，f r a n c e ，2 0 0 3 【9 】g i l k sw r ，r i c h a r d s o ns a n ds p i e g e l h a l t e rd je t a l m a r k o vc h a i nm o n t ec a r l oi np r a c - t i c e m c h a p m a na n dh a l l ，l o n d o n ，1 9 9 6 【10 】h a s t i n g s w k m o n t ec a r l os a m p l i n gm e t h o d su s i n gm a r k o vc h a i na n dt h e i r a p p l i c a t i o n j b i o m e t r i k a ，1 9 7 0 ，5 7 ：9 7 1 0 9 【l l