（概率论与数理统计专业论文）树指标随机过程的若干极限定理.pdf

江苏大学硕士学位论文 摘要 马尔可夫链是描述一类实际问题的数学模型，它是一类特殊的随机过程。马 尔可夫链理论在科学研究、发展生产、改进技术、社会服务等各个方面，已经成 为强有力的数学工具，广泛地应用于物理、化学、计算机、通信、随机服务等众 多领域之中，并取得了极为丰硕的成果。随着信息论的发展，近年来树图模型已 引起物理学，概率论和信息论界的广泛兴趣。树上随机场是随机过程推广到树指 标的情形，而树上马氏链场是一类特殊的树上随机场。近几年，刘文和杨卫国及 其合作者在树上马氏链场方面做了许多工作，并取得了大量突出的成果。 本文的主要内容是研究树上马氏链随机转移概率的强极限定理和树上非对 称马氏链的强偏差定理。本文共分五章，第一章和第二章主要介绍了本文的研究 背景和所需要的基本概念，基本引理和定理；第三章和第四章是本文研究的主要 成果；第五章是结束语。其中第三章主要研究了树上马氏链随机转移概率的强极 限定理，本章通过引入渐近对数似然比的概念，将刘文的关于非齐次马氏链的随 机转移概率的几何平均的性质推广到树图上，得到了树上有限马氏链随机转移概 率的几何平均的强极限定理；第四章主要研究了树上非对称马氏链的强偏差定 理，利用叶中行给出的树上非对称马氏链的定义，通过构造鞅的方法，得到了 c a y l e y 树上非对称马氏链的强偏差定理。 关键词：树指标马氏链；随机转移概率；几何平均；强极限定理；树上非对称马 氏链；鞅；强偏差定理 江苏大学硕士学位论文 a b s t r a c t m a r k o vc h a i ni sam a t h e m a t i cm o d e ld e s c r i b i n gp r a c t i c a lp r o b l e m s i ti sa l s oa s p e c i a lr a n d o mp r o c e s s m a r k o vc h a i nt h e o r y i ns c i e n t i f i c r e s e a r c h ，d e v e l o p p r o d u c t i o n , i m p r o v et e c h n o l o g y ，s o c i a ls e r v i c e s ，a n do t h e ra r e a s , h a sb e c o m ea p o w e r f u l m a t h e m a t i c a lt o o l w i d e l y u s e di n p h y s i c s ，c h e m i s t r y ，c o m p u t e r s ， c o m m u n i c a t i o n s ，s t o c h a s t i cs e r v i c ea n dm a n yo t h e rs p h e r e s ，a n dh a sm a d eav e r y f r u i t f u lr e s u l t s w i t ht h ed e v e l o p m e n to ft h ei n f o r m a t i o nt h e o r y , t h et r e em o d e lh a s d r a w ni n c r e a s i n gi n t e r e s tf r o ms p e c i a li np h y s i c s ，p r o b a b i l i t ya n di n f o r m a t i o nt h e o r y r a n d o mf i e l d so nt r e e si st h er a n d o mp r o c e s sb ee x t e n d e dt ot h ec a s eo ft h et r e ei n d e x ， a n dm a r k o vc h a i nf i e l d si n d e x e db yt r e e si sas p e c i a lr a n d o mf i e l d so nt r e e s i nr e c e n t y e a r s ，p r o f e s s o rl i uw e na n dp r o f e s s o ry a n gw e i g u oa n dt h e i ra s s o c i a t e sd om u c h w o r ki ns t u d y i n gm a r k o vc h a i n so nt r e e sa n do b t a i nf r u i t f u lr e s u l t s t h em a i np u 印o s eo ft h i st h e s i si st os t u d yal i m i tp r o p e r t yo ft h eg e o m e t r i c a v e r a g eo fr a n d o mt r a n s i t i o np r o b a b i l i t yf o ran o n h o m o g e n o u sm a r k o vc h a i n s i n d e x e db yat r e ea n das t r o n gd e v i a t i o nt h e o r e mf o rn o n s y m m e t r i cm a r k o vc h a i n f i e l d so n at r e e t h i st h e s i si n c l u d e sf i v ec h a p t e r s i nc h a p t e r1a n dc h a p t e r2 ，w eg i v e a ni n t r o d u c t i o no ft h eb a s i sn o t i o n sm a i nr e s u l t sa n da p p r o a c h e su s e di nt h ep a p e r c h a p t e r3a n dc h a p t e r4a l et h em a i nr e s u l t s c h a p t e r5i st h ee n d i nc h a p t e r3 ，w e m a i n l yr e s e a r c hal i m i tp r o p e r t yo ft h eg e o m e t r i ca v e r a g eo fr a n d o mt r a n s i t i o n p r o b a b i l i t yf o ran o n h o m o g e n o n sm a r k o vc h a i n si n d e x e db yat r e e b yi n t r o d u c e dt h e n o t i o no fl o g l i k e l y h o o dr a t i o no fs t o c h a s t i cs e q u e n c e s ，w eo b t a i nal i m i tp r o p e r t yo f t h eg e o m e t r i ca v e r a g eo fr a n d o mt r a n s i t i o np r o b a b i l i t yf o ran o n h o m o g e n o u sm a r k o v c h a i n si n d e x e db yat r e e t h i sr e s u l ti sa ne x t e n s i o no ft h el i m i tp r o p e r t yo ft h e g e o m e t r i ca v e r a g eo fr a n d o mt r a n s i t i o np r o b a b i l i t yf o ran o n h o m o g e n o u sm a r k o v c h a i n s i nc h a p t e r4 ，w em a i n l yr e s e a r c has t r o n gd e v i a t i o nt h e o r e mf o rn o n s y m m e t r i c m a r k o vc h a i nf i e l d so n at r e e b yu s i n gt h ed e f i n i t i o no fn o n s y m m e t r i cm a r k o vc h a i n f i e l d so nat r e ea n dc o n s t r u c t i n gan o n - n e g a t i v em a r t i n g a l e ，w eo b t a i nas t r o n g d e v i a t i o nt h e o r e mf o rn o n s y m m e t r i cm a r k o vc h a i nf i e l d so n a c a y l e yt r e e 江苏大学硕士学位论文 k e yw o r d s ：n o n h o m o g e n e o u sm a r k o vc h a i n si n d e x e db ya t r e e ； r a n d o m t r a n s i t i o np r o b a b i l i t y ；g e o m e t r i ca v e r a g e ；n o n s y m m e t r i cm a r k o v c h a i nf i e l d so nt r e e s ；m a r t i n g a l e ；s t r o n gd e v i a t i o nt h e o r e m r i l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 保密口 本学位论文属于，在年我解密后适用本授权书。 不保密口 学位论文作者签名：王绎山 指导教师签名： w 扣年占月弓日如，p 年多月乡日 独创性申明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：王肇c 上f 日期： 纠p 年月? 日 江苏大学硕士学位论文 1 1 研究背景 第一章绪论 马尔可夫链( 简称马氏链) 是一种特殊的随机过程，由苏联数学家 a a m a r k o v b 于1 9 0 7 年提出这一概念并开始研究。后经世界各国几代数学家的 相继努力，特别是d o e b l i n ，d o o b 。l e v y , f e l l e r , 钟开莱，王梓坤等著名学者的代 表性工作和卓越贡献，使得马氏链目前已成为内容上十分丰富，理论上相当完整 的一个数学分支。在科学研究、发展生产、改进技术、社会服务等各个方面，马 氏链理论已经成为强有力的数学工具，被广泛的应用于物理、化学、计算机、通 信等各个领域之中，并且取得丰硕的成果。 二十世纪七十年代诞生的“随机场这一概率论与统计物理的交叉学科， 一方面为统计物理提供了一个严格的数学工具，另一方面也为概率论的研究提 供了更广阔的领域。通常我们将随机场分为格上随机场和树图上随机场，其中的 重要内容是格上和树图上m a r k o v 随机场。m a r k o v 随机场是马氏过程推广到多指 标的情形，由于它在图像分析和数据压缩理论、遗传算法、淬火算法、排队网络 理论等方面有广泛的应用，从而引起了物理学、概率论、信息论界的广泛兴趣， 成为近些年来发展起来的重要分支之一。近年来有不少数学工作者进行了这方面 的研究( 1 卜 2 ) 。树指标马氏链是马尔可夫随机场的特例，近年来国内外有许 多学者进行了这方面的研究工作，并且取得大量的研究成果。b e n j a m i n i 和 p e r e s 3 给出了树指标马氏链的定义并研究了其常返性和射线常返性。b e r g e r 和叶中行 4 研究了齐次树图上平稳随机场熵率的存在性。叶中行和b e r g e r ( 见 5 和 6 ) 利用p e m a n t l e 在 7 中的结果及组合方法，在依概率收敛意义下研究 了齐次树图上p p g 不变和遍历随机场的s h a n n o n m c m i l l a n 定理。杨卫国和刘文 8 研究了齐次树图上马氏链场( 这实际上是树指标马氏链和p p g 不变随机场的 特殊情形) 状态发生频率的强大数定律。t a k a c s 9 研究了一致有界树上有限状态 马氏链的一元函数的强大数定律。近年来，黄辉林和杨卫国 1 0 研究了一致有界 树上马氏链的强大数定律和s h a n n o n - m c m il l a n 定理。石志岩和杨卫国 11 研究 了树上二阶非齐次马氏链随机转移概率的极限性质。彭伟才，杨卫国和王蓓 1 2 江苏大学硕士学位论文 研究了齐次树上随机场的一类强偏差定理。 1 2 本文的主要研究方法和所解决的问题 在本文第三章中，我们引入了渐近似然比作为一种度量，通过运用一 些基本不等式和函数的相关知识，将刘文教授的关于非齐次马氏链的 随机转移概率的几何平均的性质推广到树图上。 在本文第四章中，通过构造鞅的方法，得到了c a y l e y 树上非对称马氏 链的强偏差定理。 2 江苏大学硕士学位论文 第二章基本理论与概念 2 1鞅的定义及基本概念 为了引进鞅的概念，首先给出条件期望的概念和性质。 2 1 1 条件期望的定义和性质 下面涉及的问题都将固定在完备的概率空间( q ，厂，p ) 上进行。 1 条件期望的定义 定义2 1 1 ( 1 3 1 ，p 1 4 5 ) 设回为尸的子仃一域，x 为( 准) 可积随机变量， y 为满足下列条件的随机变量： ( i ) y 为圆可测的； ( i i ) 对每一个b 圆，jy d p = jx d p ； jbjb 则称】，为x 关于回的条件期望，记为y - e ( x i 回。特别地，当仍= 仃( z ) 时，也 称y 关于z 的条件期望，记为e 僻i z ) 。 注：e ( xi z ) 是仃( z ) 可测的。 2 条件期望的性质： 以下咀q ，唣等都是厂的子仃一域? 命题2 1 1 ( 【1 3 】，p 1 4 6 ) ( i ) 若x ，】，为可积随机变量，口，b 为任意常数，则： e ( 必+ b y i b ) = a e ( xi b ) + b e ( y l 仍) a s ； ( 2 1 1 ) ( i i ) e ( 1 i 圆) = 1 伽； ( 2 1 2 ) ( i i i ) 若x y ，则：e ( x i b ) - e ( y i b ) a s ； ( 2 1 3 ) 特别地，当x o 时，e ( xl ) o 1 e ( xl 哂) _ _ e ( xb ) a s o 命题2 1 2 ( 1 3 1 ，p 1 4 7 ) 设】，为可积随机变量， 咒，n 1 ) 为随机变量序 3 江苏大学硕士学位论文 列，则： ( i )( 条件期望l e v i 引理) 若y x 。个x ，贝i j ： l i me ( x , ib ) _ e ( x lb ) 伽 ， 若y 邑山x ，则( 2 1 4 ) 式也成立。 ( i i )( 条件期望的f a t o u 引理) 若以y ，则： e ( 1 i n i n f x ib ) _ l i m i n f e ( x 玎ib ) 。 若x n y ，则 e f ，妇s u p i 国、l h n l s u p e ( 以i 圆) 。 玎 ，l ( i i i ) ( 条件期望的l e b e s g u e 控制收敛定理) 若i 以l y ，x 开一x a s 则： f u n n e q n 1w ) = e ( xlw ) 黜o 命题2 1 3 ( 【1 3 ，p 1 4 8 ) ( i ) 若y 为圆可测的随机变量，且x 、娜为可积随机变量，则： e ( x r i 回= y e ( xi 回 ( i i ) 吗为仍的子仃一域，x 为可积的随机变量，则： e ( e 岱i 吗) i 回= e ( x iq ) = e 但( 墨l 够) l 霸) ( i i i ) 若x 为可积的随机变量，仃( 盖) 与圆独立，则： e ( xl 哟= 尉 特别地，当x 与y 相互独立时，e ( xl y ) = 船。 4 ( 2 1 - 4 ) ( 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) 江苏大学硕士学位论文 2 1 。2 鞅的定义和性质 定义2 1 2 ( 1 3 1 ，p 1 1 6 ) 设( q ，兀p ) 是完备的概率空间，n = o ，1 2 ，) 是 非负整数全体，如果厂的子盯一域族f = 石，以) 满足下列条件： ( i ) 石包含f 中的一切可略集； ( i i ) 对每一个厅，石c 磊c f ，即巧个 则称f = 石，刀) 为仃域流。( q ，兀f ，p ) 称为带流概率空间。 以下的概念和性质都在带流概率空间( q 厂，f ，p ) 上讨论。 定义2 1 3 ( 1 3 1 ，p 1 5 8 ) 随机变量序列x = 鼍，nen ) ，若满足： ( i ) x 是f 适应的且是可积的，即对每个刀，x 办e ( 此时称 x 厅，石，万o ) 为 随机适应序列) ；且对每个n ，x n 是可积的： ( i i ) 对每个刀n ， e 僻。+ li 国= x 。口j ( 2 1 1 0 ) 则称 x 厅，石，刀o ) 为f 鞅或鞅。如果将( 2 1 1 0 ) 式中的等号换成( ) ，则称 以，石，咒o ) 为上( 下) 鞅。 命题2 1 4 ( 【1 3 1 ，p 1 5 9 ) ( i ) 对于鞅，有呱= e x o ；对于上( 下) 鞅，有瓯( ) e x o ； ( ii ) x 。，万) 为上鞅的充要条件是 ) 为下鞅； ( iii ) 以，甩) 为鞅的充要条件是 以，疗en ) 既为上鞅又为下鞅； ( i v ) 上( 下) 鞅为鞅的充要条件是脚。= e x o ，v n ，a 。 2 。1 3 鞅差序列的定义和性质 定义2 1 4 ( 1 3 1 ，p 1 0 0 )设舷，乏，咒o ) 为随机适应序列，如果 e 以+ ，i 焉) = oa s 则称 k ，焉，万o ) 为鞅差序列。 5 江苏大学硕士学位论文 引理2 1 - 5 如果 k 鼍，行o ) 为鞅差序列，则 以2 磊k ，焉，忍田为鞅；反 之，设 以鼋，以o ) 为鞅，令l = 邑一邑dn 1 ) ，y o = x o ，则 k 磊，n o ) 为鞅差 序列。 引理证明参见文( 【1 3 1 ，p 1 6 0 0 2 1 4d o o b 鞅收敛定理 命题2 1 5 ( d o o b 鞅收敛定理) 设x = 瓦，刀n ) 为带流概率空间 ( q 厂，f ，p ) 中的下鞅，s u p e x 。+ 0 ，总有 p ( x 。h = 屯hl x o = f o ，墨= ，x 。= t ) = p y 。h = “i x 。= ) ( 2 2 1 ) 成立，则称x 为离散参数的马尔科夫链。若s 为有限集，则称x 为有限马尔可 6 江苏大学硕士学位论文 夫链。 下面我们给出马氏链的等价性质( 见文 1 4 ，p 2 ) ： 引理2 2 1 设x = 弘。，n = o 工，是定义在概率空间( q ，旷，d 上的随机序 列，x 的状态空间s 是可列集或有限集，则下列陈述互相等价： ( i ) x 是离散参数的马氏链，即式( 2 2 1 ) 成立。 ( i i ) 对任何正整数刀，任何非负整数列：0 t o 毛 o ，以下均同。 ( i i i ) 对任何正整数甩，任何非负整数列：0 f o t l t 。“以及任何 毛，i l ，”i 。+ l s ，恒有 以民2 i o , 2 枷，五2 ，h2 屯h ) = p ( 民= i d ) p ( 一= 1i 民= 0 p ( x t h = i n hi k = ) ( 2 2 3 ) = p = f ) p ( x t o - i oi x 。- - i ) p ( x t h = i n hi 置= j ( 2 2 4 ) l e s ( i v ) 对任何正整数n 、m ，任何非负整数列0 t o 乙 t 一+ 1 t 。+ 。以 及任何如，f l ，i 。，钉，+ 。s ，恒有 p ( x t h = h ，盖乙+ = 乇+ 。i 盖乙= o ，叉l = i ，x t = j = p ( 盖乙h = h ，盖l + = + 。i 工l = j ( v ) 对任何正整数刀、m ，任何非负整数y d o - t o + l t n + m 以及任何i o ，f l ，”i 。，i 。“，i 叶。s ，恒有 p ( k = i d ，d2 0 ，h = “，k 。= + 。i = 屯) ( 2 2 5 ) = p 瓯2 i d ，x h = di k = i n ) p ( 置q = “，。= i n + 撙i = j ( 2 2 6 ) ( v i ) 对任何正整数纸m ，任何非负整数列o - - - t o 岛 乙+ 1 乙+ 。 7 江苏大学硕士学位论文 以及任何芘，i l ，。，h ，屯+ ，s ，恒有 p ( k = i d ，扎= 1l = ，t h = 小，t 。= 堋) = p ( 民= i o ，五 = qi = ) ( 2 2 7 ) ( v i i ) 对任何正整数聍以及任何i s ，记乒 以，0 七n - l 是由x o ，x 。- l 生成 的最小仃一代数，又记俨仁i ，k 刀+ 1 ) 是由x 。h ，x 拜+ 2 ，生成的最小仃一代 数，则对任何a 叫x t ，0 七 n - l ，b 万( 五，k 咒+ 1 ) ，恒有 尸pia ，以= f ) = p ( bix 。= f ) ( 2 2 8 ) ( v i i i ) 对任何正整数聆，任何i s 以及任何a 霉体。，0 - k n - l ， b 乒( 叉r 七，k 甩+ 1 ) 恒有 p ( a b i 以= f ) = p 似i 邑= d p ( 曰l 邑= d ( 2 2 9 ) ( i x ) 对任何正整数聍，任何f s 以及任何a 伊 邑，0 七 n - l ， b f a t ，k n + 1 ) ，恒有 p ( a l x 。= l ，曰) = p 似i 以= f ) ( 2 2 1 0 ) 注2 。2 1 由马氏链定义及等价定义的( i i ) ，( i v ) ，( v i i i ) 知，在已知x 。= i 的条件下，系统过去的历史与它的将来是独立的。 注2 2 2 由等价定义的( v i ) ，( i x ) 知，如果随机序列 x o ，x 1 ，x 。，x 。+ l ， 是马氏链，那么 ，x 。h ，x 。，x 。，x o 仍是马氏链。 注2 2 3 设 x 。，n 田是定义在s = 0 工2 ，- ，上的马氏链，记 “，j ) = p ( 邑= j i 以d = f ) ， ( 2 2 1 1 ) 只= 假o ，妫，其中屯j s , n 1 ( 2 2 1 2 ) 则称 o ，n n q 为马氏链弘。，n 田的一步转移概率，简称转移概率；若随着 刀的变化只也变化，则称弘。，n 田为非齐次马氏链，瑕，n q 为其一步转移概 8 江苏大学硕士学位论文 率矩阵列，简称转移概率矩阵列；若随着甩的变化只不变化恒为p ，则称 工矗，刀田为齐次马氏链，p 为其一步转移概率矩阵，简称转移概率矩阵。 2 3 树指标马氏链 树图g = r ，e ) 是一个没有回路的连通图。对于任意两个顶点x y r ，设 叫是连接x 与y 的唯一路径，路径拶中含有的边数记为d ( 而y ) ，称为x 到y 的 距离。 本文的树丁是指无限的，局部有限的连通图，且有一个根点，图上没有连通 的圈，且我们考虑的树都是没有叶子( 叶子是指只有一个相邻顶点的顶点) 的。 若树上的每个顶点的相邻的顶点数目是一致有界的，则我们称丁为一致有界树。 若树丁上的每个顶点都有n + 1 个相邻的顶点，则我们称之为b e t h e 树，记作 。我们首先选定一个顶点作为根顶点( 简称根) ，并记为0 。设盯，f 为树的两 个顶点，如果f 位于连接。到仃的唯一路径上，则记f 仃，且记h 为这条路径 上的顶点数。对任意的两个顶点盯，f ，记仃 f 为两者中离0 较远的顶点，满足： 仃人f 仃，且o a f f 如果仃。，设否万且l _ | = h 一1 则称_ 为仃的父代，也称仃为否的子顶点。 我们同时也讨论的另一种树叫c 缈坳树，记作乏。在乏上根顶点有 个相邻顶点，而其他顶点有n + 1 个相邻顶点，即所有c a y l e y 树的顶点都有个 子顶点。当= 1 ，即，1 = o 时即为非负整数序列。在文章允许的情况下，乙 和乏w 都记作z 。 如果h = l ，我们称仃在树z 的第n 层_ l z 。记r ( “) 为丁的子图，它包含了从 第0 层到第刀层的所有顶点，记l 为第聆层上的所有顶点的集合。记s ( 为顶点 1 7 的所有子顶点，设sc t ，记i si 表示s 中元素的个数。容易看出，如果z 是 9 江苏大学硕士学位论文 b e t h e k n ，n n o ) i = + 1 ，i s ( 盯) i = ( 口d ) ，如果z 是c 缈缈树，则j s ( 盯) i = 。 设k , les ，最( 尼，缈) ( 简记为足( 七) ) 是x 砷= 以：o - t n 中k 的个 数，瓯 ，i ，( 简记为s ( 七，z ) ) 是随机变量序偶 ( x o ，墨) ，f 厶，( 髟，t ) ，仃厶，f s ( 仃) ，1 i o 。设 删一南h ) ， ( 2 3 7 ) 则称l ( c o ) 为工一町在概率测度下的熵密度。如果。：拶z 为在概率测度p 下 的树指标马氏链，则 “妨一南1 n p 僻妒) 一南陋p ( 邑) + 茎丕，善，l n p 婵r lx 期( 2 3 8 ) 熵密度( 功) 收敛( 厶收敛，依概率收敛，a e 收敛) 到一个常数的性质在 信息论中被称为渐进均分割性( a e p ) 或者是s h a n n o n m c m i l l a n 定理。 t a k a c s 9 在研究分支马氏链的强大数定律中对树上的父代使用新的符号。 若t 为z 中的任一顶点，从根0 到顶点，的路径上存在唯一一个离顶点，最近的顶 点称为f 的父代，记为1 f ，且称f 为1 f 的子代。1 t 的父代称为t 的祖父代，记为2 。 类似地记嘎为珀勺第”辈父代。令x s = 置，tes ，sc t ，且，为x s 的实现。 令4 ( ) s ) 是s 上的k r o n e c k e r 万函数，即满足： 瓯( 石) = 茎二三竺 令n o , ke s ，d o ( 一1 ，并记 d ( 盯) _ l f j f l ：f = 仃l ， 酸似) ：= 哦( x ，) d ( ，筠似) ：= 4 ( x 厅) 4 岱口) d ( a e a口a 其中f 表示顶点f 的第n 辈父代。 类似于 3 中树指标马氏链的定义，我们可定义树指标非齐次马氏链如下： 定义2 3 3 设有限状态空间s = 1 ，2 ，册) ，x = 置，f t ) 为定义在概率 空间( g f ，p ) 上在s 中取值的变量族。设 p = ( p ( x ) ，x s ) ， = ( 只( y ix ) ) ，x , yes ，te t ( 2 3 9 ) ( 2 3 1 0 ) 江苏大学硕士学位论文 分别为s 上的概率分布和s 2 上的转移矩阵族。如果对于任何顶点 r 丁 d ) ，& ，乞r ， 尸( 五= y l x l i = x 和以满足t a o _ l t ) = p ( 置= y l x l | = x ) = ( y l x ) ，v x ，y s ( 2 3 1 1 ) 且 p ( 丘 - x ) = 尸( x ) ，v x e s ( 2 3 1 2 ) 则称x = 五，f r ) 为在概率测度p 下具有初始分布( 2 3 9 ) 和转移矩阵族( 2 3 1 0 ) 的树指标非齐次马氏链。 注：如果当f l 时有卑= ，则称x = 五，f t ) 为在概率测度p 下为层非 齐次马氏链或树指标非齐次马氏链。 2 4 关于树指标马氏链的若干已知结果 定理2 4 1 ( 见文 1 7 )设z 为齐次树， x ，：仃r ) 为定义在概率空间 ( q ，f ，p ) 上取值于s 的树z 指标马氏链，g ( 为y ) 为定义在s 2 上并取值于 o ，1 ) 的 函数。设 q ，刀1 ) 为一列正的随机变量，并且设 记 则 n - 1 只( 缈) = g ( 以，x ，) m = o 盯e i f e s ( 盯) q ( 缈) ：n - i 耳( g ( x o ，x ，) l 以) m = oo r kf 目( 盯) a = 国：溉a n = o o , 1 i m s u p l g ( c o ) ) a国名口 - p0 i i 川 3 缈 瓯 一 、l ， 缈 c 1 一吆 m 1 一 江苏大学硕士学位论文 定理2 4 2 ( 见文n 7 2 ) 设r 为齐次树， 石口：盯et ) 为定义在概率空间 ( q ，f ，p ) 上取值于s 的并具有初始分布( 2 3 1 ) 和转移矩阵( 2 3 2 ) 树r 指标马 氏链。假设转移矩阵p 为迥j 力的，则 畔斟叫p p - a e , l i ms , ( k , l i ) ( 删p - a e , l i mf ( c o ) = 一荟否万 ) p ( 小) 时啡) 纪 其中万= ( 万( 0 ) ，万( 1 ) ，万p 一1 ) ) 为由矩阵p 决定的平稳分布，( 仞) 为x f 在概率 测度p 下的熵密度。 定理2 4 3 ( 见文 1 9 ) 设z 为齐次树， 置：fet ) 为定义在概率空间 ( g f ，p ) a n n , s 的树z 指标非齐次马氏链，其初始分布为p = p ( 功，x s ) ， 转移矩阵为= ( p o ( y l 砷，x ，y e s ) ，( 晶( x ，少) ，行1 ) n g r 在s 2 上的函数族。设 ，刀1 ) 为一列j 下的随机变量，并且设 以( 国) = h ( 以，墨) q ( 缈) = e p ( g , h ( k ，墨) i 以) 记 曰= 国：溉吒= o 。，噢严丢q c 叻 1 ) 为一列正的随机变量， 并且设 以( 缈) = ( k ，五) ， t e t ( 。 口 g ( 国) = 萋e 昌( 扎，五) i 置 i e f ”、f o l 一一 记 曰= 彩：溉a = o o , l i 翟p 丢q c 功 ov x ，yeg ，tet “ o 令 包= r a i n p , ( x , l 气) ，薯，气eg ，tet ( n o ) ) 若存在常数口 0 ，使得 h 粤南，磊，岛= m q ，由于 讹) = 羞月耩州卅= 驯) 0 ，根据马尔可夫不等式有： “( i 丁扣卜i 1 l i lz 打s ) = “( 乙p i 刑忙) p 一刑忙 ( 3 2 5 ) 由( 3 2 5 ) g n 壹h ( i 丁i - 1l i l 乙s ) 主p 一矿( ) i 。 ( 3 2 6 ) 根据 一 n 引= l b o r e l c a n t e l l i 理，由( 3 2 6 ) 式及f 的任意性，g n ( 3 2 2 ) 成立。 定理3 2 1 设p 为( q ，f ) 上的概率测度，其中x = 置，f 丁) 在概率测度 p 下是非齐次马氏链，其初始分布和转移概率族分别满足： p = p ( 砷x e g ) ，( 3 2 7 ) p = 僻( ) ，i 砌x , y g ，t j f l ，( 3 2 8 ) 则随机转移概率 # = ( z ( 五l 气) ) ，丁“) 、 。) ) 的几何平均的下极限在概率测度 p 下几乎处处不小于三，即 溉砒1 恍7 仰鼻l 置) j 丢p - a e ( 3 2 9 ) 证明：设q 为( q ，f ) 上另一概率测度，且x = ，f r 在q 下是独立同分 布的，其中五在s 上的分布为均匀分布，即q ( = f ) = 三，则 q ( x 扣) = q ( x 州= x 刑) = ( 丢) 一“ c 3 2 1 0 ) 由引理3 2 1 可得 卿( 耩厂 = l i r a s u p 一 1 m 旧h 恍似e ( 删尸 l 旧w 、 d j 1 9 lp 一口幺 ( 3 2 1 1 ) 江苏大学硕士学位论文 所以 缈b 1 - k i 曲凇吖i 三p 一口幺 ( 3 2 1 2 ) 故结论成立。 定理3 2 2 设p 为( q ，) 上的概率分布，其中x = 墨，丁 在概率测度 p 下是非齐次马氏链，其初始分布和转移概率族满足( 3 2 7 ) 和( 3 2 8 ) 。设fes ， 最( 缈) 是x = 五：f 丁 ) 中f 的个数，即 s , ( , c o ) = 巧( 置) ， ( 3 2 1 3 ) 其中4 ( ) ( i s ) 是s _ e 的k r o n e c h e r - 8 函数。 ( 1 ) 如果存在一个常数，1 1 ，1 ，使得 叫掰( m ) 厂 那么就有 l i m s 叩丽1 瓯( ，缈) p p - a e , ( 3 2 1 5 ) 其中p 是方程 五五 ( 1 2 ) l ( m 1 ) r = ， ( 3 2 1 6 ) 的唯一解。 ( 2 ) 如果存在一个常数厂 去，荔与 使得( 3 2 1 4 ) 式成立，那么 憋i n f 两1 国) 9 p 一 ( 3 2 1 7 ) 其中擘是方程( 3 2 1 6 ) 在区间( 0 ，去 上的唯一解。 证明：设q 为( q ，f ) 上另一概率测度，r x = 五，t e t ) 在q 下是独立同分 布的，置的分布为 则 由引理3 2 1 有 由于 l i m s u p 一 = l i m s u p 开- - - 0 0 江苏大学硕士学位论文 q ( 五= f ) = 五 q ( 置f ) = ( 1 一五) ( 聊一1 ) ( 3 2 1 8 ) ( 3 2 1 9 ) q ( ) ：9 ( 一帕) 甜“m ，( 暑) 一1 吨。m ( 3 2 2 0 ) r， u m s u p i f p x r i - ) x r 加) p 一口。 ( 纠幢( f ， 南 哪。刖砒 卜删4 0 删rl 心( ) j 鲥上 胂。卜 卅( 划晦。 而 u h ，；砒) r ，e r 川、 o 。l ( 3 2 2 1 ) 1p 一口e i p ( x o ) h ( m ) r l f e l 、 o j ( 3 2 2 2 ) l i m s u p 【毗) 风鼻( 墨i 一) j 厂 l | r 2 1 ( 3 2 2 3 ) l 一 上一 、j 一 1 川_ 1 m o 品 名 _。l p us 即 耋l 上一 & 盟 & 力 上椭& ，j盟 墨 见 江苏大学硕士学位论文 所以 警m s u p 掣f 丽) 百r ( m - 1 ) 幺 ( 3 2 砷 l 掣1 ) 百幺 砷 熙呻渊m 掣1 妯掣h 幺。 ( 3 2 2 5 ) n 一。口 1 iz ”jl 一旯1 一允 、7 ( 1 ) 假设! 兄 1 ，由( 3 2 2 5 ) 式有 m 令 由矽( 名) = o 得 令 即渊薹l n r ( m - 1 ) h 幺 ( 旯) = r ( m - 1 ) 1 一名 2 ( m - 1 ) 1 一名 五五 ( 1 一旯) ( m 一1 ) 7 卜五= ， g ( 五) = 允丑 ( 1 一允) ( 掰一1 ) l 一 易证g (