（应用数学专业论文）树上马氏链的若干极限定理.pdf

江苏大学硕士毕业论文 摘要 树上的随机场是随机过程理论在树一这一新的数学模型上的应 用，它产生于信息理论的编码和译码问题假设一个序y d x 。 ，其中 的状态和状态序偶出现的频率是否遵从大数定律，直接影响到编译 码方法的优劣，故这一领域一直是众多学者研究的重点三十几年前， 诞生的“随机场”这一概率论与统计物理的交叉学科与其它概率物理 分支，代表着当今数学与物理相互渗透的大潮流的一个重要侧面最 近，杨卫国及其合作者利用研究概率论极限定理的新方法，把传统马 氏链中的若干强极限定理、s h a n n o n m c m i l l a n 定理推广到了b e t h e 树 和c a y l e y 树上的马氏链场本论文的工作首先给出了广义c a y l e y 树的 定义，研究了有限状态下齐次树上二重马氏链上普遍成立的强极限理 论，作为推论得到了有限状态下齐次树上状态频率和状态序偶频率的 一类强极限定理，并且给出有限状态齐次树上的强大数定律和 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 定理；鞅； 随机转移概率；调和平均；状态和状态序偶 江苏大学硕士毕业论文 r a n d o mf i e l d so nt r e e sa l ea p p l i c a t i o n so nt r e e so ft h e o r yo fr a n d o mp r o c e s s 。a n e wm a t h e m a t i c a lm o d e l ，w h i c hd e v e l o p e df r o mc o d i n ga n de n c o d i n gp r o b l e mi n i n f o r m a t i o nt h e o r y a s s u m i n gt h e r ei sas e q u e n c eo f k ) ，w h e t h e rt h ea p p e a r i n g f r e q u e n c yo fs t a t ea n ds t a t ec o u p l eo b e yt h es t r o n gl a wo fl a r g en u m b e r si st h ek e yo f ag o o dc o d i n ga n de n c o d i n gm e t h o d ，s ot h i sd o m a i ni sa l w a y sb e i n gar c s e a r c h i i l g e m p h a s e sf o rm a n y s c h o l a r st h i r t yy e a r sa g o ，w h e nr a n d o mf i e l d sc a m ei n t ob e i n g i t t sas u b j e c to fi 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 rw i t ho t h e rb r a n c h e so fp r o b a b i l i s t i cp h y s i c s ，s t a n df o ra ni m p o r t a n ta s p e c to f at r e n d ，w h i c hi st h ei n t e r p e n e t r a t i o no fm a t ha n dp h y s p r o f e s s o ry a n gw e i g u oa n d h i sa s s o c i a t e se x t e n ds o m es t r o n gl i m i tt h e o r e m sa n ds h a n n o n m c m i l l a nt h e o r e mf o r c l a s s i c a lm a r k o vc h a i n st om a r k o vc h a i n so nb e t h et r e e sa n dc a y l e yt r e e sr e c e n t l y i n t h i sp a p e r , w ef i r s tg i v et h ed e f i n i t i o no fag e n e r a lc a y l e yt r e ea n ds t u d yal o c a l c o n v e r g e n c et h e o r e mf o raf i n i t es e c o n do r d e rm a r k o vc h a i ni n d e x e db yag e n e r a l c a y l e yt r e e a sc o r o l l a r i e s ，w eo b t a i ns o m el i m i tt h e o m m sf o rt h i sm a r k o vc h a i n f i n a l l y ，w e a l s oo b t a i nt h e s t r o n g l a wo f l a r g en u m b e r s ( l l n ) a n d s h a n n o n m c m ：i l l a nt h e o r e mf o rac l a s so ff i n i t es e c o n do r d e rm a r k o vc h a i ni n d e x e d b yag e n e r a lc a y l e yt r e e a tt h es a m et i m e ，w es t u d yal i m i tp r o p e r t yo f t h eh a r m o n i c m e a no 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 si n d e x e d b yat r e e t h i sf 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 eh a r m o n i cm e a no f r 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 k e y w o r d s ：t r e e ；m a r k o vc h a i n s ；s t r o n gl a wo fl a r g en u m b e r s ；s h a n n o n m c m i l l a n t h e o r e m ；m a r t i n g a l e ；r a n d o mt r a n s i t i o np r o b a b i l i t y ；h a r m o n i cm e a n ； s t a t e sa n ds t a t ec o u p l e s 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 广1 保密u 本学位论文属于，在年我解密后适用本授权书。 不保密口 学位论文作者签名：忑、之素 钟l 二月l 罗e l 指导教师签名：剐 如否年k 月拯日 独创性申明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：忑恚亮 日期：游h 月谬e l 江苏大学硕士毕业论文 第一章绪论 在概率论的发展史上，极限理论的研究一直占有重要地位，刘文教授和杨 卫国教授利用纯分析方法在极限理论的研究方面作了许多工作，得到了一些广泛 而深刻的结果本论文是在杨卫国教授研究工作的基础上对树图上马氏链的强 极限性质加以推广 二十世纪七十年代诞生的“随机场 这一概率论与统计物理的交叉学科，它 一方面大大扩充了概率论的研究领域，另一方面也为统计物理提供了一个严格 的数学工具这个学科及其他概率物理分支，代表着当今数学与物理相互渗透 的大潮流的一个重要侧面新近超导研究的突破，为随机场提出了许多迷人的 新课题，带来了巨大推动力马氏链场即是一种特殊的随机场近年来有不少 数学工作者进行了这方面的研究见 1 一 4 树模型近年来引起物理学、概率论及信息论界的广泛兴趣，信息论中 s h a n n o n - m c m i l l a n 定理的研究【5 l - 7 1 ，也一度成为学者们研究的一个热点树图 上马氏链场的强大数定律与熵定理在图像分析与数据压缩理论、遗传算法、淬火 算法、排队网络理论等方面有广泛的应用【8 1 - 【1 0 】关于树上马氏链场的早期研究 见s p i t z e r 1 1 1 和k e m e n y 1 2 1 的文献p e m a n t l e 根据随机游动的理论证明了树上 p p g 不变随机场单边尾域的平凡性，由此得到树上p p g 不变和遍历随机场的弱大 数定律【1 3 1 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 il l a n 定理 1 1 4 - 【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 c m il l a n 定理【1 7 - i 3 4 1 本文是在杨 卫国教授研究的基础上加以推广，首先得到了广义c a y l e y 树图上二重马氏链有 江苏大学硕士毕业论文 限状态下齐次树上二重马氏链上普遍成立的强极限理论，作为推论得到了有限 状态下广义c a y l e y 树上状态频率和状态序偶频率的一类强极限定理，并且也证 明了有限状态下广义c a y e y 树上二重马氏链的强大数定律和s h a n n o n - m c m i l l a n 定理同时，本论文也研究了树上非齐次马氏链的随机转移概率的调和平均的极 限性质，所得结果将非齐次马氏链的随机转移概率的调和平均的性质推广到树图 上 全文共分为五章第一章是绪论部分，介绍了本论文的选题背景，并对已 有的工作做了扼要的介绍；第二章回顾一下概率论中随机变量序列的基本收敛 性、鞅的概念性质以及马氏链的基本概念和指标马氏链的定义及近年来研究的结 果；第三章第四章为主要内容，第三章给出了广义c a y l e y 树及广义c a y l e y 树上 二重马氏链的概念，并证明了广义c a y l e y 树上二重马氏链的的强极限理论及强 大数定律和s h a n n o n - m c m i l l a n 定理；第四章是研究树上非齐次马氏链的随机转 移概率的调和平均的极限性质：第五章是结束语 2 江苏大学硕士毕业论文 第二章基本理论与概念 2 1随机变量序列的基本收敛 2 1 1 以分布收敛 定义2 1 1 设弘，e ，n q 是概率空间( q ，g ，p ) 上的随机变量序列，如果 弘。 的分布函数列 e ( 工) 弱收敛于随机变量x 的分布函数f ( 力，则称x 。以分 布收敛于x ，记作以与x 。 2 1 2 几乎必然收敛( a 。s ) 定义2 1 2 设弘，邑，n q 是概率空间( q ，乎，p ) 上的随机变量序列，如果存 在a 多，并且p 似) = 0 ，使得当缈a 。时，有l 乎e ( 叫= x ( 功，则称 以，l 廿几 乎必然收敛于x ，或简称弘。) a s 收敛于x ，记为瓦一x a s 如果存在集合a 多，e ( a ) = 0 使得当缈a 。时，有 t i mx ( c o ) 一l ( 国) l = 0 ( 2 1 1 ) ， 则称，n q 是c a u c h ya s 收敛的。 引理2 1 1 设仁，邑，n 1 ) 是概率空间( q ，多，d 上的随机变量序列，则 眠，a s 收敛于x 的充要条件是隅，n q 是c a u c h ya s 收敛的。 引理证明见【3 5 】 引理2 1 2 a s 收敛于x 的充要条件是v g 0 1 1 婴尸 u ( 1 以一x l g ) ) = 0 ( 2 1 2 ) m = 刀 引理证明见【3 5 】 推论2 1 1 如果v o , - 0 ，有 3 江苏大学硕士毕业论文 则有疋一z a s 二p i 以- x l 占) o ，那么中任一随机变量序列的以概 率收敛性蕴含着a s 收敛性的充要条件是q 为可列多个互不相交的原子之并。 引理2 1 4 ( i ) 设e 与x ，则有子列x 础，x 础一x a s ( i i ) 设e 与x ，则有以与x ( i i i ) 鼍与c 等价于k 山c ，其中c 为常数 引理证明见 3 5 1 4 江苏大学硕士毕业论文 一一：二二一 2 1 4 岛收敛( 平均收敛) 对0 p o ，存在简单随机变量y5 等鲰丘工p 使得 e i x y l p s 这就是说，对任一p 次可积的简单随机变量序列 k p 阶平均收敛 于x 引理2 1 5 若x 。b x ，则有x 。上专x 引理证明见【3 5 】 应用测度论中关于极限号与积分号交换的有关定理，可得下面的三个重要的 定理。 l e b e s g u e 控制收敛定理设以与x ，随机变量y 厶使n i x - l r l a s o 1 ) ，那么x 。，x 厶且x 。且专x 这时栅。一以 单调收敛定理设x 。厶，x 。o 且邑个x 氖s ， ( i ) 我们有l i 。m e x , = e x 因此，如果l 译臣k o 。，则有x 厶 ( i i ) 反之，若z 厶，则每一x 。厶且l 印e 邑= x f a t o u 引理设x 。厶 1 ) 是非负随机变量，使得l i r a 。i n fe x 。 ，则 l i i n 。i n f 厶，且 e ( 1 i m i n fx 。) _ l i m 。i n fe x , 证明见 3 5 1 2 2 鞅的定义及基本概念 为了引进鞅的概念，首先给出条件期望的概念和性质。 5 江苏大学硕士毕业论文 2 2 1 条件期望的定义和性质 涉及的问题都将固定在完备的概率空间( q ，乎，p ) 上进行。 1 条件期望的定义 定义2 2 1 设国为多的子o r 一域，x 为( 准) 可积随机变量，y 为满足下 列条件的随机变量： ( i ) y 为回可测的 ( i i ) 对每一个刀国，p 卯= d 御 则称l ，为x 关于国的条件期望，记为y = e ( x9 3 ) 。特别地，当国= 仃( z ) 时，也 称y 关于z 的条件期望，记为e ( xl z ) 注2 2 i - e ( x f z ) 是盯( z ) 可测的。 2 条件期望的性质： 以下国，墨，墨等都是乎的子o r 一域。 引理2 2 1 ( i ) 若x ，y 为可积随机变量，口，夕为任意常数，则： e ( a x + i9 3 ) = a e 僻i 国) + 肚i 国) a s ( 2 2 1 ) ( i i ) e ( 1 l 国) = 1 a - s ( 2 2 2 ) ( i i i ) 若z y ，则：e ( 彳f b ) e ( y i b ) a s ( 2 2 3 ) 特别地，当x 0 时，e ( x i9 3 ) 0 ie ( xl 品) l 0 ) 为随机适应序列，如果e ( k 。l 焉) = o a s 则称 匕，焉，n 0 ) 为鞅差序列。 引理2 2 5 如果 k 壤，胛o 为鞅差序列，则 邑= 砉k ，焉，聆吣为鞅；反 之，设 以焉，n o ) 为鞅，令k = 邑一x - - - 0 ，k = 凰，则 e 焉，刀o 为鞅差 序列。 引理证明参贝, 1 3 6 1 2 2 4 鞅基本收敛定理 引理2 2 。6 ( d o o b 鞅收敛定理) 设x = 邑，刀0 ，为下鞅， s u p e x + o 。， 或等价地s u p 以。 0 ，总有 p ( x 。= 厶+ li x o = i o , x l = ，x 。= 厶) = p ( x 肿。= 屯+ li x 。= f 。) ( 2 3 1 ) 成立，则称z 为离散参数的马尔科夫链。若s 为可列集或有限集，则称x 分别 依次为离散参数的马尔可夫链和有限马尔可夫链。 下面我们给出马氏链的等价性质： 引理2 3 1 设x = 弘。，n = o 工- ，是定义在概率空间( q ，f ，p ) 上的随机序 列，j 的状态空间s 是可列集或有限集，则下列陈述互相等价： ( i ) x 是离散参数的马氏链，即式( 2 3 1 ) 成立。 ( “) 对任何正整数n ，任何非负整数列：0 t o t 1 o ，以下均同。 ( ii i ) 对任何正整数玎，任何非负整数列：0 f o t l r 川以及任何 i o ，i l ，乙+ l s ，恒有 p ( x , o = i o , 五2 毛，= 乇，x t “= 厶+ ) = p ( x o = 乇) 以x = 毛i 民= o ) p ( k = 乇+ ，i = 乇) ( 2 3 3 ) = e e ( x o = f ) 尸( 气= 毛i 凰= 沪p 。= 乇+ 。i 五= ) ( 2 3 4 ) ( i v ) 对任何正整数胛、m ，任何非负整数列0 t o f l t 。 t 川 f 。+ 肘以 及任何i o ，i 1 ，”i 。，+ l ，i 。s ，恒有 p r 。= 屯+ 1 ，盖i 。= + 。i x r 0 = o ，x = i 1 ，x = 厶) = p ( 五乙= 厶+ ，盖- 。= + 。i x t = ) ( 2 3 5 ) ( v ) 对任何正整数刀、m ，任何非负整数列0 f o - t z 岛 乙+ l 厶+ 。 以及任何i o ，i l ，一l l l ，厶棚s ，恒有 p ( x r o2 毛，j i d = 厶一- ，j i 。= 屯卅，j i 。= 屯+ 。i x t = ) = p ( x f o2 f o ，x d2 一1i x = 乇) p 。= + l ，x t 。= 屯+ ，i x = 厶)( 2 3 6 ) ( v i ) 对任何正整数胛、m ，任何非负整数列0 - t o 乙十l 乙+ 所 以及任何i o ，i l ”i 。，i 州，i 。棚s ，恒有 e ( x 白2 毛，名_ 一2 屯一l x t = ，x 。= 屯+ l ，x t 。= + 。) = p ( x ，o = 毛，丑i 。= 屯一，l j i = 屯) ( 2 3 7 ) ( v i i ) 对任何正整数咒以及任何，s ，记叫瓦，0 七刀一1 ) 是由x 。，x 柑生成 的最小盯一代数，即包含q 及一切形如p ：x ( 砷= j , o k 万一1 ，_ s ) 的国 集，并对取余及可列并运算封闭的最小集类，又记f ( 以，k 厅+ 1 ) 是由 1 0 江苏大学硕士毕业论文 以小x 棚，生成的最小o r 一代数，则对任何 a 吼鼍，o 1 ) 为定义在s 2 上的 函数族设 ，行1 ) 为一列正的随机变量设 记 则 n - l e ( 国) = g i + 。( 以，x ，) i = 0 盯e 厶f e s ( a 1 q ( ) = e p ( + 。( x o ，x ，) ik ) 曰= 国：。l i m 。a = ) ， 。c 口，= 国：n 竺p 1 ，。丢吐9 2 f + l ( l ，墨) p 籼( 以蚓i 以 = m c ， o 。) n b l i m l 。f ( 缈) 一q ( 缈) _ o p 一纰于d ( 0 0 定理2 4 4 ( 杨卫国，叶中行，2 0 0 7 ，文 2 0 ) 设r 为齐次， 以：盯t ) 为定义在概率空问( q 厂) 上取值于s 的树z 指标 非齐次马氏链，其初始分布为p = 尸( 功，x s ) ，转移矩阵为 1 8 江苏大学硕士毕业论文 只= ( 只( y i 砷，x ，j ，s ) 假设随机矩阵尸= ( 尸( ，i d ，i ，s ) 为另一个为遍历的矩 阵七s 如果 f l m 只( j li ) = p ( jif ) ，v i ，j s ， 疗- - 0 0 1 骢潲叫妫p - a e 疗1 + i m 。s j 丁( ( k 甩, ，f 1 ) = 万( 后) p ( ，i 后) 尸口名。， 月l i ，m 。f , , ( 缈) = 一荟荟万( k ) p ( j i 助1 n p ( j l 动 凡仉色， 其中万= ( 刀( o ) ，刀( 1 ) ，万p 一1 ) ) 为由矩阵p 决定的平稳分布，( ) 为x 川在概 定理2 4 5 ( 黄辉林，杨卫国，2 0 0 8 ，文 2 2 ) 设r 为一致有界树( 即每个顶点的相邻顶点数是一致有界的) ， 五：t e t ) 为 定义在概率空间( q 厂) 上取值于s 的树r 指标马氏链( 定义见文 2 2 ) ，( g t 似y ) ，f 丁) 为定义在s 2 上的函数族设 ，刀1 ) 为一列正的随机变 量设 ( 彩) = g t ( x 。，z ) ， g ( 缈) = 萎，町& ( 墨，墨) l 五 t e t 【“， d 一 记 则 b = 彩：。l i m 。a , = ， )l _ 7 j 一卜竺p 巩1 群 9 2 ，( 置) p 书( 叫五，卜( c o ) 1 ) 是非负鞅 定理3 2 1 设 五，t t 和船，( x ，y ，z ) ，t t ) 如引理3 2 1 ，a n ，疗1 是一非 负随机序列e ( 功j t h ( 3 2 1 ) 所定义 g 。( 叻= e g ，( x 2 ，x k ，x ，) i x l | x 2 ，】， ( 3 2 8 ) f e 一”十l ， o 如果存在一非负实数口，使得1 2 1 口且 d 位) = 则 。l i m ，。a , , = o o , l i m 。+ s 。u p1 口。，。一。) 、 _ 一, 1 ， 。 e 9 2 t ( x 2 ，五，x ：) 口f 氆酹( j 工i ；“，j 巳，】= 万( 颤。) 。 ( 3 2 9 ) 江苏大学硕士毕业论文 l i m 二( e ( 缈) 一g ：( 缈) ) = 0口p 缈d ( 口) ( 3 2 1 0 ) “。”a 证明由引理3 2 1 知 乙( 五，缈) ，e ，刀1 ) 是非负鞅由d o o b 鞅收敛定理得 l i r a t , ( a , c o ) = f ( 以c o ) a e h - - - 0 0 令彳= 舰= ) ，由( 3 2 1 1 ) 1 l i m s u p 二h a t ( 2 c o ) 0 a e 国a h _ a n ( 3 2 11 ) ( 3 2 1 2 ) 由( 3 2 1 ) ，( 3 。2 2 ) 和( 3 2 1 2 ) 得 h m 。s 。u p z i 。 z f ( o ) - ，。一叭 。，h e k 豫( 如，扎 l 五，鼍， 。a e c o a ( 3 2 1 3 ) i 妇( 3 2 1 3 ) 和不等式l n x 0 ) ，。p 。一1 一x 萼，当。q 五i 口时可得 l i m s 。u p l l 【五e 沏) - 见州叭 0 删e g t ( 置，五，鼻) | 五，五，】 l i m 。一s u p 丢 旧。磊删l i l e 瞳训l 五，置，】矧。焉删研( 五，气，置) f 墨，置，】j = l i m s u p _ 1 i n e e 馅如 i x l ，五， - e a g t ( x 2 ，五，五) i 五，置。】 “。 “月t e t t ) q o ， 一i l i m s u p _ 1 e e 编札，i x , 。，墨，卜1 - e a g , ( x 2 。，五，x , ) l g ，墨，】 “- 。 “月l e 一“、 o ，卜i 等l i m s u p e g ( x 2 ，五，置) 一吲如凡别，置，】 二月+ 。 a nr e 一”、 o 一i - - i - m ( 0 0 觚 缈。( 口) ( 3 2 1 4 ) 令0 五口，由( 3 2 1 4 ) 得 h m s u p 丢 驰卜一，c 驯也，滓脚，w e d ( a ) 江苏大学硕士毕业论文 在( 3 2 1 5 ) 中令兄- - ) 0 + ，由( 3 2 9 ) 可得 n m s u p l 吒i 。f ( c o ) - 旧。蒜冰川研“，五，墨，i 五，置，】) 。 ( 3 2 1 5 ) ( 3 2 1 6 ) 当一口 0m ，l ，keg ， ( 3 4 4 ) 则声是遍历的 定理3 4 1