（应用数学专业论文）两类非齐次树图上马氏链场的强极限性质.pdf

江苏大学硕士学位论文 摘要 三十几年前，诞生了“随机场”这一概率论与统计物理的交叉学 科，它与其他概率物理分支，代表着当今数学与物理互相渗透的大潮 流的一个侧面。马氏链场即是一种特殊的随机场。随着信息论的发展， 树模型近年来引起物理学、概率论及信息论界的广泛兴趣，信息论中 的s h a n n o n m c m i l l a n 定理的研究也一度成为学者们研究的一个热 点。树图上马氏链场的强大数定律与熵定理在图像分析与数据压缩理 论、遗传算法、淬火算法、排队网络理论方面有广泛的应用。刘文教 授和杨卫国教授在树图上马氏链场的强大数定律方面做了许多工作， 也取得了丰硕的成果。本文主要利用杨卫国教授独创的鞅方法与纯分 析法结合的方法继续这方面的工作。 全文共分为五章。第一章是绪论部分，介绍了本论文的选题背景， 并对已有的工作作了扼要的介绍；第二章回顾一下概率论中随机变量 序列的基本收敛性和鞅的概念性质；第三章至第四章为主要内容，第 三章给出了树及树上马氏链场的概念，并证明了广义b e t h e 树上马氏 链场的几个关于状态与状态序偶出现频率的强极限定理；第四章是强 大数定律，首先给出了一类特殊非齐次树k 。：概念，其次证明了关 于状态与状态序偶出现频率的强大数定律，最后给出了几乎处处收敛 的s h a n n o n - m c m i l l a n 定理。第五章是结束语。 关键词：随机场：马氏链场：强大数定律：s h a n n o n m c m i l l a n 定理：广 义b e t h e 树 江苏大学硕士学位论文 a b s t r a c t t h i r t yy e a r sa g o ，r a n d o mf i e l d sc a m ei n t ob e i n g i ti sas u b j e c to f i n t e r s e c t i o no fp r o b a b i l i t ya n ds t a t i s t i c a lp h y s i c s r a n d o mf i e l d s ，t o g e t h e r w i t ho t h e rb r a n c h e so fp r o b a b i l i t i cp h y s i c s ，s t a n d sf o ra ni m p o r t a n t a s p e c t at r e n d ，w h i c hi st h ei n t e r p e r m e a t i n go fm a t h a n dp h y s t h em a r k o v c h a i nf i e l di sas p e c i a lr a n d o mf i e l d w i t ht h ed e v e l o p m e n to ft h e i 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 sd r a w ni n c r e a s i n gi n t e r e s tf r o m s p e c i a l i s ti 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 t h es h a n n o n m c m i l l a nt h e o r e mi ni n f o r m a t i o nt h e o r yi se v e rb e c o m i n gaf o c u sa m o n g m a n ys c h o l a r s s t r o n gl a w s o fl a r g en u m b e r sa n ds h a n n o n - - m c m i l l a n t h e o r e mo nm a r k o vc h a i nf i e l d si n d e x e db yt r e e sh a v eb e e ne x t e n s i v e l y a p p l i e di nm a n ya s p e c t s ，s u c h a s p i c t u r ea n a l y s i sa n dd a t a c o n s t r a c t i o n t h e o r y , g e n e t i ca l g o r i t h m s ，q u e n c h i n ga l g o r i t h m s ，q u e u en e t w o r k st h e o r y a n ds oo n p r o 1 i uw e na n dp r o y a n gw e i g u oh a v eb e e nd o i n gw e l li n s t r o n gl a wo fl a r g en u m b e r sf o rm a r k o vc h a i nf i e l d so nt r e e s m a r t i n g a l e m e t h o d st o g e t h e rw i t hp u r ea n a l y s i sm e t h o d sw h i c hc r e a t e db yp r o y a n g i se m p l o y e dt oi n v e s t v i g a t es t r o n gl i m i tt h e o r e m sf o rm a r k o vc h a i nf i e l d s o nt r e e s i nt h i sp a p e rw ec o n t i n u et h i sr e s e a r c h t h i sp a p e ri s c o m p o s e do ff i v ec h a p t e r s i nt h ef i r s tc h a p t e rw e i n t r o d u c et h er e l a t i v eb a c k g r o u n do nt h i s p a p e ra n dg i v es o m es i m p l e e x p r e s s i o n so ft h ew o r kw h i c hh a v eb e e ns t u d i e d i nt h es e c o n dc h a p t e r w eg i v es o m es p e c u l a t i v ek n o w l e d g ea b o u tc o n v e r g e n c ef o rr a n d o m i i 江苏大学硕士学位论文 v a r i a b l e s i nt h et h i r dc h a p t e rw ep r o v es o m es t r o n gl i m i tt h e o r e m sf o rt h e f r e q u e n c i e so fo c c u r r e n c eo fs t a t e s a n do r d e r e dc o u p l e so fs t a t e sf o r m a r k o vc h a i nf i e l d si n d e x e db yt h eg e n e r a l i z e db e t h et r e e s t r o n gl a w so f l a r g en u m b e r sa n ds h a n n o n m c m i l l a nt h e o r e mf o rm a r k o vc h a i nf i e l d s i n d e x e db yas p e c i a ln o n h o m o g e n o u st r e ea r eo b t a i n e di nt h ef o u r t h c h a p t e r w eg i v et h es i m p l es u m - u pa b o u t t h i sp a p e ri nt h el a s tc h a p t e r k e y w o r d s ：r a n d o mf i e l d s ；m a r k o v c h a i n f i e l d s ；s t r o n g l a wo fl a r g e n u m b e r s ；s t a t e sa n dc o u p l e s o fs t a t e s ；s h a n n o n m c m i l l a n t h e o r e m ；t h eg e n e r a l i z e db e t h et r e e i i i 学位论文版权使用授权书 y9 3 8 0 5 7 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部内容或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密西 学位论文作者签名：为越 卅年z 月5 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已注明引用的内容以外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者签名i 与越 日期：加年石月，5 日 江苏大学硕士学位论文 第一章绪论 在概率论的发展史上，极限理论的研究一直占有重要地位，刘文教授和杨 卫国教授利用纯分析方法在极限理论的研究方面作了许多工作，得到了一些广泛 而深刻的结果。本论文是在杨卫国教授研究工作的基础上对树图上马氏链场的强 极限性质加以推广。 二十世纪七十年代诞生的“随机场”这一概率论与统计物理的交叉学科，它 一方面大大扩充了概率论的研究领域，另一方面也为统计物理提供了一个严格的 数学工具。这个学科及其他概率物理分支，代表着当今数学与物理相互渗透的大 潮流的一个重要侧面。新近超导研究的突破，为随机场提出了许多迷人的新课题， 带来了巨大推动力。马氏链场即是一种特殊的随机场。近年来有不少数学工作者 进行了这方面的研究见 1 _ “ 树模型近年来引起物理学、概率论及信息论界的广泛兴趣，信息论中 s h a n n o n m c m ilf a n 定理的研究【7 1 ，也一度成为学者们研究的一个热点。树图 上马氏链场的强大数定律与熵定理在图像分析与数据压缩理论、遗传算法、淬火 算法、排队网络理论等方面有广泛的应用嘲- 【i ”。关于树上马氏链场的早期研究 见s p i t z e r “1 和k e m e n y ”1 的文献。p e m a n t l e 根据随机游动的理论证明了树上p p g 不变随机场单边尾域的平凡性，由此得到树上p p g 不变和遍历随机场的弱大数 定律m l 。1 9 9 0 年，b e r g e r 和叶中行研究了树上p p g 不变随机场中熵率的存在性， 之后他们又研究了树上p p g 不变随机场的遍历性及s h a n n o n - m c m i l l a n 定理 1 4 1 15 1 ，但他们的主要工作限于b e t h e 树和c a y l e y 树上，而且其中的收敛是以概 率收敛。1 9 9 4 年，b e n j a m i n i 与p e r e s 提出了树指标马氏链的概念，并研究了它 们的常返性和射线常返性 1 6 1 。近几年，刘文教授和杨卫国教授及合作者在树上 马氏链场方面做了许多工作，也取得了丰硕的成果，得出了一些树上马氏链场关 于状态与状态序偶出现频率的强极限性质和强偏差定理，齐次树图上马氏链场的 强大数定律和几乎处处收敛的s h a n n o n m o m i l l a n 定理 1 7 1 - f 2 8 1 。本文是在杨卫国教 授研究的基础上加以推广，得到了广义b e t h e 树图上马氏链场的若干强极限性质 江苏大学硕士学位论文 及一类特殊非齐次树图上马氏链场的强大数定律和几乎处处收敛的 s h a n n o n - f 【c h i l l a n 定理。 全文共分为五章。第一章是绪论部分，介绍了本论文的选题背景，并对已 有的工作做了扼要的介绍；第二章回顾一下概率论中随机变量序列的基本收敛性 和鞅的概念性质；第三章至第四章为主要内容，第三章给出了树及树上马氏链场 的概念，并证明了广义b e t h e 树上马氏链场的几个关于状态与状态序偶出现频率 的强极限定理；第四章是强大数定律，首先给出了一类特殊非齐次树。概念， 其次证明了关于状态与状态序偶出现频率的强大数定律，最后给出了几乎处处收 敛的s h a n n o n m c m i l l a n 定理。第五章是结束语。 江苏大学硕士学位论文 第二章基本理论与概念 2 1 随机变量序列的基本收敛 2 1 1 以分布收敛 定义2 1 1 设 x ，瓦，n 1 ) 是概率空间( q ，乎，p ) 上的随机变量序列，如果 五) 的分布函数列 e ( z ) ) 弱收敛于随机变量五的分布函数f ( x ) ，则称瓦以分 布收敛于互，记作以与工。 2 1 2 几乎必然收敛( a s ) 定义21 2 设 ，鼻，九1 是概率空间( q ，乎，p ) 上的随机变量序列，如果存 在a 乎，并且p ( a ) = 0 ，使得当由a 。时，有1 i m 瓦( ) = x ) ，则称 瓦，n 1 ) 几 n 乎必然收敛于x ，或简称 五) a s 收敛于x ，记为瓦叫x a s 如果存在集合a 擘，p ( a ) = 0 使得当国a 。时，有 孵l 瓦( 国) 一以( 出) l = 0 ( 2 1 1 ) 则称 五，竹1 ) 是c a u c h ya s 收敛的。 引理2 1 1 设 x ，五，n 1 ) 是概率空间( q ，乎，p ) 上的随机变量序列，则 置) a - s 收敛于x 的充要条件是 瓦，咒1 ) 是c a u c h y a s 收敛的。 引理证明见 2 9 引理21 2 瓦 a s 收敛于工的充要条件是v s 0 l i m p u ( 1 l x | s ) ) = 0 引理证明见 2 9 1 推论2 1 1 如果v 占 0 ，有 刊瓦一x l f ) - 砖= 0 ( 2 1 ，4 ) 则称 瓦，”1 ) 以概率收敛于于x 。简记为五与z 注2 1 1 ： 如果置旦斗爿，那么极限随机变量z 是a s 唯一的，即如果有 以o x 同时有五o y ，则有x = y a s 引理2 1 3 如果五一z a s ，那么有置与 该引理是引理2 1 ，2 的一个推论。 注2 1 2 ：定理2 1 3 的逆命题一般不成立，但在特殊情况下成立。设( q ，擘，p ) 是一概率空间，是定义在其上的满足如下条件的随机变量的集合，即若z ，y 是 中两个不同的随机变量，则p ( x 】，0 ，那么中任一随机变量序列的以概 率收敛性蕴含着a s - 收敛性的充要条件是q 为可列多个互不相交的原子之并。 引理214 ( i ) 设置与z ，则有子列，五 叫a | s ( i i ) 设置与，则有五 z ( i i i ) x 与c 等价于z 与c ，其中c 为常数， 引理证明见 2 9 4 江苏大学硕士学位论文 2 1 。4 l p 收敛( 平均收敛) 对o p 。，令l p = z ：工是随机变量且e f r o ，存在简单随机变量y = 莩咏丘，使得 e i x r 1 9 占这就是说，对任一p 次可积的简单随机变量序列 k ) p 阶平均收敛 千x 引理2 1 5 若以与，n n x o 爿 引理证明见 2 9 1 应用测度论中关于极限号与积分号交换的有关定理，可得下面的三个重要 l e b e s g u e 控制收敛定理i r x 。与z ，随机变量y e 厶使得i 曩i m a s ( n 1 ) ，那么咒，厶且山爿这时有甄一麟 单调收敛定理设瓦厶，瓦o k x1 、_ a s ( 1 ) 我们有1 挚e k = e x 因此如果1 譬 c o ，n n x e 厶 ( i i ) 反之，若z 厶，则每一以。且l i m e x = e x f a t o u 引理设也厶0 1 ) 是非负随机变量，使得l i m i n f e x , , 。，则 l i m i n f x l ，且 e ( 1 i m i n f x ) l i m i n f e x , 证明见 2 9 1 2 2 鞅的定义及基本概念 为了引进鞅的概念，首先给出条件期望的概念和性质。 江苏大学硕士学位论文 2 2 1 条件期望的定义和性质 涉及的问题都将固定在完备的概率空间( q ，多，p ) 上进行。 1 ，条件期望的定义 定义221 设廊为g 的子盯一域，j 为( 准) 可积随机变量，y 为满足下 列条件的随机变量： ( i ) y 为国可测的 ( i i ) 对每一个b 国，p 卯= p 卯 则称y 为关于国的条件期望，记为y = e ( _ i 国) 。特别地，当国= 盯( z ) 时，也 称y 关于z 的条件期望，记为e ( x i z ) 注2 2 1 ：e ( i z ) 是盯( z ) 可测的。 2 条件期望的性质： 以下国，墨，雹等都是擘的子盯一域。 引理2 2 1 ( i ) 若工，y 为可积随机变量，口，卢为任意常数，则： e ( a x + 卢】，i 国) = a e ( x j 国) + f l e ( y i a l ) a s ( 2 2 1 ) ( i i ) e ( 1 l 国) = 1 a s ( i i i ) 若y ，则：e ( x i 国) e ( r l 国) a s 特别地，当x 0 时，e ( x l 国) 0 i e ( x l 国) l e ( i x0 国) a s ( 2 2 2 ) ( 2 2 - 3 ) 引理222 设y 为可积随机变量， 咒， 1 为随机变量序列，则： ( i ) ( 条件期望的l e v i 引理) 若y 翼j1 、z ，贝0 ： 挈e ( x oi 国) = e ( j i 国) a s ( 2 2 4 ) 若y 以上x ，则：( 2 2 4 ) 式也成立。 ( i i ) ( 条件期望的f a t o u 引理) 若置j ，则： 6 江苏大学硕士学位论文 e ( 1 i m i n fx i 国) _ l i m i n fe ( x i 国) ( 2 2 5 ) 若以y ，则 e ( 1 i m s u p 瓦l 国) l i m s u pe ( x , i 国) ( 2 2 6 ) ( i i i ) ( 条件期望的l e b e s g u e 控制收敛定理) 若五y ，瓦一z a s 贝0 ： l i m e ( 瓦i 壤) = e ( x i 国) a s ( 2 2 7 ) 引理22 3 ( i ) 若y 为国可测的随机变量，且，姗7 可积随机变量，则 e ( 鄹i 廊) = 甩( l 国)( 2 2 8 ) ( i i ) 墨亡国，x 为可积的随机变量，则： e ( e ( x i 雹) i 国) = e ( x i 岛) = e ( e ( x i 国) i 国)( 2 2 9 ) ( i i i ) 若z 为可积的随机变量，仃( z ) 与曰独立，则： e ( x i 国) = e x 。特别地，当x 与y 相互独立时，e ( x i l ，) = e x 。 以上三个引理的证明见 3 0 】， 2 2 2 鞅的定义和性质 定义2 ，2 2 设( q ，多，p ) 是完备的概率空间，= f o ，1 ，2 ， 是非负整数全体 如果乎的子盯域族，= 焉，刀e n 满足下列条件： ( i ) 鼋包含乎中的一切可略集； ( i i ) 对每一个力n ，焉 焉+ ，亡只即焉1 、， 则称f = 鼋，咒n ) 为盯域流。( q ，只f ，p ) 称为带流概率空间。 以下的概念和性质都在带流概率空间，只f ，p ) 上讨论。 定义2 2 3 随机变量序列j = f 五，刀，若满足： i ) x 是f 适应的，即对每个n ，五焉( 此时称 五，鼋，力o 为随机适应序列) ； 且对每个胛，z 是可积的； 江苏大学硕士学位论文 i i ) 对每个月n ，e ( 置+ i - f ) = 以 a s ( 2 2 1 0 ) 则称 ，焉，胛0 ) 为f 鞅或鞅。如果将( 2 2 1 0 ) 式中的等号换成( ) ，则称 瓦，”0 为上( 下) 鞅。 引理22 4 ( i ) 对于鞅，有e x = e x o ；对于上( 下) 鞅，：r f f e x ( ) e x 0 ( i i ) 五 为上鞅的充要条件是 一五 ；为t n i ( i i i ) 瓦) 为鞅的充要条件是 五 既为上鞅又为下鞅 ( i i i i ) 上( 下) 鞅为鞅的充要条件是e x = e x o ，v n ，a s 引理证明参见 3 0 2 2 3 鞅差序列的定义和性质 定义22 4 设 ，n 0 ) 为随机适应序列，如果e ( e + 1 焉) = 0a s 则称 e ，鼋，肝0 ) 为鞅差序列。 引理225 如果 ，n o ) 为鞅差序列，n g2 舌茸，焉，n o ) 为鞅； 反之，设 邑，磊，月0 ) 为鞅，令= 以一x n 一。( h 1 ) ，k = 蜀，则 e 焉，肝0 为鞅 差序列。 引理证明参见【3 0 2 2 4 鞅基本收敛定理 引理226 ( d o o b 鞅收敛定理) 设_ = 五，胛o ) 为下鞅，蒿：s u p e x , , + 0 3 i i 或等价地s u p e i 以i c o ，n n n 寸。时， 以) a s 收敛于可积随机变量置。 n 引理证明见 3 0 1 推论：若 瓦，行0 ) 为非负鞅，则五a s 收敛于可积的随机变量。 证明：若 瓦，胛0 ) 为非负鞅，则： 由d o o b 鞅收敛定理即得。 e x = ej 五j = e l 蜀| o ) 层上的每个顶点均与第行+ l 层上的虬+ 。个顶点相邻，y s t 为广义b e t h e 树 或广义c a y l e y 树。设n 是正整数，如果n i = + 1 且对所有的胛2 ，。：n ，则 称r 为b e t h e 树，记为，；如果对所有的即l ，虬= n ，则称r 为c a y l e y 树，记 为，。b e t h e 树瓦2 如图所示： 图3 1b e t h e 树矗2 第三层 第二层 第层 根 江苏大学硕士学位论文 3 1 3 树上马氏链场的定义 设s ，t 是树图丁上任两个顶点，如果s 处在从0 到f 的唯一路径上，则记为 s t ，并记为这个路径的边数。显然若= h ，则f 是处于第”层上的顶点。对于 树图上的任两个顶点j ，f ，记s x f 是满足 s f s s xr f 离0 最远的顶点。设f 0 ，记；是满足i t 且i ；i = - 1 的顶点，即f 是；的子 代。 定义3 1 1 【1 q 设g = o ，1 ，2 ，j 为一可列集合，讧，t r ) 是定义在概率空 间 q ，乎，p ) 上在g 中取值的随机变量族，设 p = ( z ) ，x g ( 3 i 1 ) 是g 上一概率分布， p = ( p ( y 1 工) ) x ，y g ( 3 1 2 ) 是定义在gz 上的随机矩阵，如果v t ，s t 满足s r ；，有 p ( 五：y l x i = t 五) p k ，= y 1 五= x ) = p ( y l x ) v x ，y g( 3 1 ，3 ) 并且 e ( x 。= x ) = p ( x ) v x g ，( 3 i 4 ) 则称 五，f t 为具有初始分布( 3 1 1 ) 与转移矩阵( 3 1 2 ) 在g 上取值的树指标马 氏链，也称树丁上的马氏链场。 本章主要研究广义b e t h e 树上马氏链场的若干强极限性质。以下以r 表示广 义b e t h e 树或广义c a y l e y 树，丁( ”) 表示含有从第0 层( 根顶点) 到第n 层的所有 顶点的子图， 三。表示第n 层上所有顶点的子图，i b l 表示子图b 的顶点数，并 令i n o l = l ，则 丁( ”1 = 砉乓= 磊n 0 m 。为方便起见，树中的顶点用坐标形式表 示。用( n ，j ) ( 1 j n ，n n ，n 1 ) 表示第n 层上的第j 个顶点，易知，( h ，) 1 ) 江苏大学硕士学位论文 的第n + 1 层上的相邻顶点为+ 1 ，。+ 1 ( ，一1 ) + 1 ) 、( n + 1 ，n ( ，一1 ) + 2 ) 、 ( ”+ 1 ，。，) 。n n - - n n ，记根顶点o 为( 0 ，i ) 。 3 2 树上马氏链场的局部收敛定理 引理3 21 设丁为广义b e t i l e 树，协，f t 是树r 上的马氏链场，g ( x ，y ) 是定义在g2 上且取值为0 或1 的函数，爱= 盯伍7 “) 令 e ( ) ：n 邑- 1 蓍“。，”。，g 。，x 。，) ( 3 2 1 ) e ( ) 。磊善，“乏。) + 1 9 w ，x m 扎- j ( 3 2 1 。珊总珂”n i f 卜t i 帅一1 净k ，h ( 3 2 2 ) 则叠。( a ，l 焉，n 1 是非负鞅。 证明由( 3 1 3 ) 知 | p k k = x “f ”1 由( 3 2 3 ) ， e 五“茗”1 ，：篇：小s ( 以。z ，l ，f 焉一。 显然 “一窆。g x o 。 ，) = 五4 ”“( j - o “ ，：廪岫p h 。) ( 3 z s ) p k k f “) ：f 戋， 胤乱瓤屯h ，) = 茸创臻n i 。卜。享斧p b 。j 鼻吐，) = “茸“，：黛i i l l ) “l p k 伍删，矗，) = 。陬扎， + 舻k 伍删，以，) = t i x 删 = 酋一，意。 i + 以一皿k k 帕瓦，】以吐；l ( s 2 。) 槲 = 、li， r x 江苏大学硕士学位论文 。甸叫甸霉丽知而瓦i 而 兀丌n + 一1 皿x h 。，x 。，j z ，i j = l ，= 。“一1 卜1 一4一 咋彤叫霹17煮11 eg i=1i-t 兀 + ( a 一) l 瓦。，以，) l 瓦。i j = “( 1 ) “ 、 l 、” “”“w 因此 ，。( 旯，国x 鼋，n 1 ) 是非负鞅。 ( 3 2 5 ) ( 3 2 6 ) 定理3 2 1 设仁，r t ) j 壬f - y b e t h e 树r 上的马氏链场，g ( x ，_ y ) 是定义在 g2 上且在 o ，1 ) 中取值的函数， 口。，n i ) 是正的随机变量序列，e ( ) 如( 3 2 1 ) 定义， 瓯o ) = n - i 蓍4 ，、，n 荨”+ 。l i 。e k 伍。，x m 扎，】瓦，。】 g 一( ) 2 磊善m + 。e k ，扎_ 瓦，一1 ：薹詈”量m + 。g 伍。，j ) p 0 t x p 0 t x 。) ( 3 2 7 ) 2 磊善乏m + g 忸w ， w ) ( 3 2 7 ) 令 4 = 挚a = o o , l i m 。s u p l g m b z s ， 则 l i m i f , , ( c o ) 一g 。b ) 】：o a e ，爿( 3 2 9 ) 证明f 。以，功) 如( 3 2 2 ) 定义，由引理3 2 1 知矗。q ，m l 焉， 1 是非负鞅， 于是由d o o b 鞅收敛定理，有 l i mo 以，) = f q ，) 1 ，在( 3 2 1 2 ) 两边同除以l n a ，有 。去妒，xmi,ym+1jimsup g ( x m = 0i = l j = n ) 1土 ) n d 。h 1 i 0 a e 出a i n 0 + “1 ) e g ( x 。 扎，i x 。9 由上极限的性质 l i m s u p ( a 一6 j ) 0 j l i m s u p ( a 一c n ) l i ms u p ( b 一c 。) 和不等式? 二兰l n ( i + x ) 兰x ( o z 1 ) 及式( 3 2 1 3 ) 有 l + x l n a l i m s u p1 窆f 8 ，n 1 + t i 。， g ( x 。j ，z 。，) 一e g 伍。，x 。“，】x 。 ) 。z 。，) 一b 。，。，j x 。 ) 月 a 。m = o i = l j - h 十t ( i 1 ) + 1 。 一 ( 3 2 1 3 ) 川叩去笔氍矗n = t i i = 1h f 虹业尝n 生生监蝠舭肛，廿 。口。m - o= “+ 。( - l h i l 4 i 蛐絮叩去am 宝= o 誊i = l 急1 型絮与茅睑坷妣肛。，。j = ，+ l o l 卜1 i【 一l j ”1 。1 ”l 蔓( 2 - 1 ) 1 i m 。s u p 一一1 7。一篇nm+iit=l叫+ 。e 蚍，n 以。m = 0 ，；+ ( + 1 。 ” 1 a e 国a l i m 妒。，蔓，k扎产kj厶，l_sup-n-i e g 谊e 。，。，) 一k z 。“，j 厶，j ，。 a 。m = 0 j = l j ；“+ l ( i - 1 ) + 1 、 ” 一 1 0 a e 0 9 a 令0 五 1 ，在( 3 2 1 2 ) 两边同除以l n 2 ，有 -。去兰妒，兰岫仁xmj爿m+l,jiminf i = 1ni - ) l二 g ) ” 月m 2 0 产，“i1 卜1 i ( 3 2 1 4 ) ( 3 2 1 5 ) n o + 0 一，净b k 。，工。扎，】x 。9 1 n 0 a e ，国a ( 3 2 1 6 ) 由下极限的性质 l i m i n f ( a , , 一以) o j l i m i n f ( a 一巳) l i n i n f ( 巨一巳) 1 5 如瓯 一 叩 哞有 o ， 一 r 叱 令 江苏丈学硕士学位论文 和不等式? l l n ( 1 + x ) - 1 ) 层上 的第( 1s ，o t o 书口1 孚3 口2 【詈】) 个顶点，易知，聆( f ) 时，其第月+ 1 层上的相邻 顶点分别为+ 1 ，a , ( j - i ) + 1 ) ，( n + l ，a ：( j 一1 ) + 2 ) ，( r t + 1 ，口，j ) ，i = 0 , i ，2 。 为统一起见，记根顶点为( 0 , 1 ) 。 4 2 若干记号 对v k ，g ，记只( i c ，c o ) ，瓯”( j ，c o ) ，s n t o ( | i ，c o ) 和鼠“( 尼，c o ) 分别表示随机变 量族x l = x ，r 瓦) ，x 矿= 五，t 瓦。) ，x “1 = 置，t l 1 ) 和 z 7 。= 五，t z 一2 ) 中状态七出现的次数，s 。( 七，c o ) ，s 。o ( i ，l ，c o ) ，s n ( 1 ) ( 七，功) 和 s n ( 2 ) ( 后，c o ) 分别表示随机变量序偶集 ( 瓦，x m 扎a o 珊 一1 ，l _ i - n o n m ，虬+ 。( f 一1 ) + l - j - 1 k 州，x 。“，l o 朋疗一1 ，州( 1 ) ，1 f 口。孚1 口。孚j 口：嘲，口。( f 一1 ) + 1 s 口。f ，”2 1 ) 和 戤驯，。扎，l o 聊胛一1 ，珊( 2 ) ，1 j 口。孚1 口l 学口2 目，口2 ( f 一1 ) + 1 j 口2 f ，船1 中状态序偶f 七。n 出现的次数。令 2 0 江苏大学硕士学位论文 则 c ，( 。) ：o h4 ( f ? i = 0 , 1 , 2 1 1 n6 t i )跏) = ? 篓 瓯g ，) ：窆“窆瓠k ) ( 4 2 1 )s 。g ，) = 瓯。)( 4 1 ) 瓯= m = 0 掣一p ，伽) i l k ( x 。) ( 4 2 2 ) s 。o ，)( m ) f i k 伍。)( 4 2 3 ) s 。 ，缈) = m = 0 1 篁i = l 3 k 2 1 严( 川) 瓯)( 4 圳 c o ) 瓯伍。，h 忸。，) ( 4 2 5 )。托，= 瓯。，膀忸。，)( ) m = 0i = i 户n m + l ( i - 1 ) + l ” 洲，国) = 互n - i “学1 一赢6 t o l ( 蚰b ，) ( 4 2 6 ) 最 f ，脚) = n 薹- i “_ 。莲3 k 2 1 辈， p ，( m ) 瓯伍。b 。，) ( 4 2 7 ) m = of = l j = a i f 1 1 1 + 1 ” 瓯g ，f ，) = 薹n - 1 甜￥亨k 2 吁1萋。严，伽) 瓯忸。h ( 瓦扎，) ( 4 2 8 ) m = o= l j = a ，f i - 1 1 + 1 。 4 3 强大数定律 引理4 3 1 设留，e t 是树丁上的马氏链场，g ( x ，y ) 是定义在g2 上且取 值为0 或1 的函数，焉：盯伍) 令 f 。以，) f 。如) 兰“蓍4 。”。，g 伍。，以“，) ( 4 3 1 ) 互善削m + l ( i - m 。g b w ，x 州j ( 4 庐(。)箭督“。，龟。n，4+1皿k。，x。，ix 。9 ( 4 3 2 ) m = oi = i p “+ i ( p 1 m 、”“。“。、 则叠。 ，脚l 焉，n 1 是非负鞅。 引理证明同引理3 2 1 ，不再赘述。 2 l ， 口 善 孚 口 。 江苏大学硕士学位论文 定理4 3 1 设 五，t t ) 是树丁上的马氏链场，g ( x ，y ) 是定义在g2 上在 o ，1 ) 中取值的函数， a 。，n 1 ) 是正的随机变量序列，f 。如) 如( 4 3 1 ) 定义 令 则 g 。c o ) 。，n 荨m + l i 。，伍。，以+ 1 ，x m e g，i 忙。，以+ 1 ， = + l ( - 1 ) + l ” ：呈爹堇n m “，j ) p ( ，) = + ，g 讧。，jp u f 瓦，) m = ol 。l，e g 。 ( 4 3 3 ) 4 = ：- 驴a = m , l i 雩u p 去aq 如) = 7 r ( k ) 齐 笔s 。( 0 ( 工) = p 一( 0 | ，i 面笺s o ) - i) = p 一i i ，茎s 。( 2 ( ，。) 户0，= o，= 0 f h ( 4 3 | 2 1 ) 一( 4 3 2 3 ) r p 得( 4 3 1 5 ) 一( 4 3 1 7 ) 。 推龃。争产= 而0 r o ( c z t ( 2 2 砌h 州。a z 。， l i m 墨警掣：l m ) a e ( 4 3 2 5 ) ” j e m l 口o + 口。口i + a 0 1 2 l 口2 、 l i m 星警掣：_ j 盟一砌) a e ( 4 3 2 6 ) ” f 正l口o + 口o a l + 口。口1 口2 、7、 2 5 u 一 一 s 一 搓。 妫一 屯一卦 一 肌 一 瓯 ” 江苏大学硕士学位论文 证明显然 l i m 坠二等型：鱼墅，l f m ) a e ( 4 3 2 7 ) ” p3 m + l口。口1 + o 0 0 f l o f 2 + o f 0o f l o l 2 l i m 坠掣粤堕：鱼丝_ _ 丌( 七) a e ( 4 3 2 8 ) “ l t 3 m + l lo f o 口t + 口。口1 口2 + o f o2 0 f 1 口2 、。 1 i m 坠玉掣：型l 一石( 七) a _ e ( 4 3 2 9 ) “ i t 3 m “l口。口i + 口o o f l o f 2 + o f 0 2 口l o f 2 。、 l i m 坠圣兰篓型：l m ) 。息( 4 3 3 0 ) l t 3 i1 + o f o + a o o f l 一 、 1 i m 些掣：旦一砌) a - e ( 4 3 3 1 ) “ 1 巧m + 2 l1 + a o + o f o 盯1 、。 、 1 i m 坠害二等型：旦盟一m ) a e ( 4 3 3 2 ) l l + 2 i1 + 口o + 口。口1 、 s ac o ) ( 缸c o ) 一 引 ( j ，) l t o ) | 垆i i t i 当 = 3 m 时，由( 4 1 1 ) 和( 4 1 4 ) ，有 1 个( o ) l j 13 mi o f o o f l o f 2 l i m! j = l l m l 盯o + 口。口【+ 口。口i 口2 f h ( 4 3 3 3 ) ，( 4 - 3 3 4 ) 和定理4 3 2 即得( 4 3 2 4 ) 。 同理可证( 4 3 2 5 ) - - ( 4 3 3 2 ) 。 从而 定理4 3 3 证明注意到 万( 七) a e 万( i ) a e l i m 遑丝掣：。( 七) 。 m l t 3 。+ 2 l 守眢叫帅e s 。( _ j ，) = s 。0 1 ( j j ，c o ) + s n ( 1 ) ( i c ，o o ) + s n (