1、三三 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类1. 状态的属性状态的属性定义定义, i jS设( )0,1,2,1nijnkfP Xj Xj knXi称为系统0时从状态i出发,经n步转移后,首次到达状态j的概率.简称首达概率.( )1nijijnff称01(,1,2,1)nknPXj Xj knXi为系统0时从状态i出发,经n步转移后,迟早到达状态j的概率.简称迟早概率.()0,1,2,ijnfP Xj nXi称ij为系统0时从状态出发,永远也不能到达状态 的概率.引理引理1( )( )(1) 01nnijijijfpf11 21121( )(2)nnnijiii iijij ijij
2、fp pp( )( )()1(3)nnln lijijjjlpfp证明证明( ) 0(1nijf0,1,2,1nkP Xj Xj knXi0nP Xj Xi( )nijp01(,1,2,),1,nknllXj XjPXj Xlik01(,1,2,1)nlklnXjXj kPXjXil10(,1,2,1)lklXj XjPXikl( )1lijlf01(,1,2,1)kllXjXj klPXi），1ijf( )0,1,2,1,ninkjfP XjknXXji(2)0(,1,2,1)kkkijnP XjkiXXni0,1,2,),1(kijknkPXjknXXii1211122011(,)nnnn
3、ij ijijXi XiXiXjPXi1211122110,(),nij innnjijXi XiXiXPXij12111221100(,)(,)nij ijijXiXPXiPXii Xi11101,(,)nnnXj XiXiPXi1211122011()()nij ijijPXiPXiXi Xi11()nnnXP Xji1112121nniii iijjiijjippp( )0(3)nijnpP Xj Xi01(,1,2,),1,nknllXj XjPXj Xlik01(,1,1),2,nknllXj XjPXj Xlik( )()1nln lijjjlfp01,1,2,(,)1nkllnP
4、Xj XXj Xj kli01,1,2(,1)llknXj Xj klPXi0,1,2,1lknXj Xj kP XjXil定义定义 2min1,jnjSTn nXjj设,称为系统首次到达状态 的时间，简称首达时.1,njn nXjT 当时，定义引理引理2( )0(1)nijjfP Tn Xi0(2)ijjfP TXi ( )01(3)EnijjijnT Xin f()jT的作用证明证明0(1)jjTP Tn Xi由 的定义知：0,1,2,1nkP Xj Xj knXi( ) nijf0(2)jP TXi ijf01()jnPTn Xi01()jnP Tn Xi( )1nijnf0(3)Eij
5、jT Xi( )1nijnn f01()jnn P Tn Xi系统从状态系统从状态i出发出发,首次到首次到达状态达状态j的平均转移步数的平均转移步数定义定义3( )1,0niiiSn np 设,若自然数集iid状态的周期则称其最大公约数为，记 .即( )GCD1,0niiidn np( )1,0.niin nf 若集合则记( )GCD1,0niiihn nf 下面的引理给出下面的引理给出di 与与 hi二者的关系二者的关系引理引理3( )(1)0,1niiipmnmd若则存在，使( )(2)0,1niiifmnm h若则存在，使(3).iiiidhdh若 与 中一个存在,则另一个也存在且（显然
6、）（显然）证明证明( )( )12(3)1,0,1,0nniiiiNn npNn nf记1N 若，10niinp （ ）则，使( )( )()10nnln liiiiiilpfp( )1,0,liinfl则一定使( )(0)niip否则2lN2N 2N 反之，若，10niinf （ ）则，使( )( )nniiiifp又( )0niip1N .iidh综上 若 与 中一个存在,另一个也存在( )( )nniiiifp又由于21NNiidh另一方面，由归纳法可证明：iihdiidh定义定义4iS设1(1),iifi若则称状态 是(常返的 返回的)1,iiif 非常返的若则称状态 是(滑过状态)(
7、2),iiii 若 是则称常返状态,且正常状态 为返状态.,iiii 若 是则称状态 为零常返状态,且常返状态.（消极常返状态）3), 1.(iiidd周期状态若则称状态 为且周期为, 1.iid 若则称状态非周期状态为.i若状态 是的状态则称之为正常遍返非周期历状态.常返非常返状态正常返零常返周期非周期遍历态1iif 1iif ii ii 1id 1id 例1：在直线上，如果质点每次向前、向后移动1步的概率都是1/3，向后移动2步的概率也是1/3，试证明每个状态都是非周期的。(2),11,(3),22,11,12002=k3=kiii iiiiii iiiiipppppppdi证明：易见于是
8、从d，得到d=1.i的周期是d=1是非周期的。例2：在直线上，如果质点每次向前移动1步的概率都是p，向后移动5步的概率是q=1-p，试证明每个状态的周期都是6。(6)506.iipp qid证明：质点从i出发，经过n次转移回到i时，需要证明n=6m.设质点向前一共移动了k次，向后一共移动了m次，根据题意得到k=5m. 于是，质点移动的次数n=k+m=6m.又所以状态的周期是定义定义5( ),1,0.niji jSnp 设若使jjii 可达状态则称状态，记ijji若，且ijij互则称状态 与状态.记通引理引理4,ijjkik(1)若，则（可达的传递性）,ijjkik(2)若，则（互通的传递性）i
9、jji(3)若，则（互通的对称性）ijjk(1)设，证明证明121,1,nn则12()()0,0nnijjkpp使由C-K方程:1212()()()nnnnikillkl Sppp12()()0nnijjkppik ,(3)类似可证 (2)引理引理 5,i jS设则(1)0ijijf(2)0ijjiijf f证明证明(1)ij设1n则( )0nijp使( )01nijijpf由引理0ijf 反,若之( )1nijijnff由于0( )1,0nijnf 使( )( )1nnijijpf由引理0ij即(2)ij设0ijjiff0,0ijjiff由(1)0ijjiff反之，若0,0ijjiffijj
10、i ，ij 引理引理 6,i jS ijjji设， 是常返状态，,1ijjiijff则且证证jjiifjj令表示从状态 出发最终到达状态 而中间不经过 的概率.,50,jijif则由引理0jijf10,jiNjfN （ ）使下面用反正法证明下面用反正法证明:1ijf 1ijf 假设则从状态则从状态j出发最终不能到达出发最终不能到达j的概率为的概率为:1(1)jlljjjjNjlfff（ ）(1)jiijNjff（ ）01jjf(j与 是常返状态矛盾！)1ijf,1.jiijf 同理证2. 状态属性的判断状态属性的判断定理定理1 (Doeblin公式公式),i jS有( )1( )1lim1Nn
11、ijnijNNnjjnpfp证明思路证明思路(1)上极限存在上极限存在(2)下极限存在下极限存在(3) 相等相等证明证明 (找上界找上界)( )()1( )11nln lijjjlNNnijnnfpp（交换求和顺序）( )()1Nln lijjjn lNlfp( )1()Nln lijjjNln lfpnlm （令）( )()10NN llmijjjlmfp(1( )0lmiNjjjNlmfp( )()111lmijjjmNlNfp（）( )( )1( )1111NnijNlnijNnljjnpfp( )( )11Nllijijllff（1ijf ）(有上界必有上极限有上界必有上极限)( )(
12、 )1( )11limlim1NnijNlnijNnNnNljjpfp( )1limNlNijijlff(找下界找下界)1,NNN固定 的，使则有( )(1)(01NN llmijjjNlnijnmfpp01( )()N llmijjjmlNfp( )01(NlmijjjmNNlfp( )()111NlmijjjNlmNfp（）1( )( )11( )1NnjjnNnijlnijNNlpfp(不等式左边对固定的不等式左边对固定的N 有下界有下界,从而有下极限从而有下极限)( )11(lim1NNNnjjNijnnnpp( )1(1)i1l mNNNnjnijnjnpp( )1lijlNf( )
13、( )11( )11limNNnjjNnijlnijlnNpfp即N （再令，得）( )( )111liml m1iNNnjjnNNNnijlnijlpfpijf( )( )( )111( )11liml m1iNNNNnnjjjjnNNnnijijnnijjnippffpp综上有( )1( )1lim1NnijnijNNnjjnpfp推论推论1,iS则( )111lim1iiNNniinfp 推论推论2,iS则( )11(1)niiiinpf ( )11(2)niiiinpf 定理定理2iS常返状态充要条是的是以下三件条件之一成立(1)1iif 0(2)()1iP TXi ( )1(3)ni
14、inp iS非常返状态充要条是的是以下三件条件之一成立(1)1iif 0(2)() 1ip TXi ( )1(3)niinp （定义）0ijjfP TXiji （时即可）（由推论2得）（定义）0ijjfP TXiji （时即可）（由推论2得）（由推论2得）定理定理3iiid是常返状对 给定的状态，若，周期是且态则存在极限()limindiiiniidp10iiii 规定：时，定理定理4iS常设是返状态，则(1) i零常返是的充要条件是( )lim0niinp(2) i遍历态是的充要条件是( )1lim0niiniip(3) i正常返周是期的充要条件是( )limniinp不存在但此时它有一收敛
15、于某正数的子列.证明证明(1)iii 设 是（即零常返，），3由定理 得()lim0indiinp( )lim0niinp综上idm当 不能整除 时，iimp（ ）由周期定义limiimmidmp（ ）(即 能整除 时,)( )lim0niinp反之，若iii 是（即假设正常返，），3由定理 得()im0lindiiiniidp矛盾！i是零常返(2)i设 是遍历态)iiidi ，且 是正常返的（3由定理 得()( )1limlim0indniiiinniipp( )1lim0niiniip反之，若i则由(1)知， 为正常返另由极限的保号性：，使n时，有( )(1)0,0nniiiipp( ,1
16、n n 的最大公约数一定为)i 是非周期i是遍历态(3)i正若 是常返周期态( )limniinp（）假设反正法存在( )( )0limnniiiinpp则由于0( )limniinp若0i由(1)知 是零常返，矛盾！( )limniinp若0i由(2)知 是遍历态，矛盾！( )limniinp所以不存在()limiiindiniip由定理d知但()indiiiiidp即有子列收敛于( )limniinp反之，若不存在i不是零则由(1常返),(2)知，不是遍历态.i正常所以是返周期态推论推论,jSiS 非常返状态零常返状态则对,设是或有( )lim0nijnp证明证明ijj 时是非常返( )1
17、niinp ( )lim0niinpijj 时是零常返( )lim0niinpninj，对时当有( )( )()1jjnnln lijijlpfp( )()( )11jjnln llijijlnl nfpf,n 令取上极限ij当时( )( )( )11lim0nllijijijnlnl npff (1)l nlijf,n 再令取极限( )lim0nijnp( )lim0nijnp0nijp（ ）又lim0nijnp（ ）定理定理 5,.i jS设( )(1),0(10,),.nniiiinppi若 正整数使则 非周期,.(2)mmjj(m)若 正整数使 步转移矩阵P 中对应于状态 的那列元素全
18、不为零,则 非周期00,(3),idNNN设状态的周期为则 正整数使时,有()0Ndiip证明证明（显然）()20mijiSp 由已知,对，（ ）00,0iiipS 一定使0)mjjp（ ）自然也（有(1)()mmijikkjk SiSppp 又对，00()imii jpp01)0mjjp（）（自然也有.j 为非周期( ),01,(2,3)niimpnm将n n1记为GCD1,2, .1mtdn tmm令112123123(GCD ,GCD ,GCD ,dndn ndn n n12123,GCD ,GCD ,),mmdnnnnnnd121ddd则有1lllddd 正整数 ，使1.d是一有限正整
19、数12GCD1,2,GCDlltndntdnln, ,由初等数论知识00NNN正整数，使得对，有1 122llNdN nN nN n12,()lN NN为正整数1 12 2()()l lN nN nN nNiidiipp1 12 211 21121()()()l lllN nN nN nikk kkikkkppp 1 12 2()()()l lN nN nN niiiiiippp()1m mlN niimp()1Nmmmmlnnniimp 个11 21121()()()1)mmmNmNmlnnniii iiiiiimppp （()()()1mmmlnnniiiiiimppp()1()mmlnN
20、iimp0( )( 1,2,00)mnnmiiiinmpp（）即为n n1， ,i jSij互通的两个状态有相同的状态类型，即设且则, i j或者同为非常返状态; 或者同为零常返状态;或同为正常返周期状或同为正常态,且周返非周期期相同.定理定理 6证明证明 ,ijij ji, l n正整数，使( )( )00lnijjippC-Km由方程，对 正整数 有)()( )( )lmnikkssikl m niispppp( )( )mjjlnijjippp()mjjp()()(1)l m nmiijjpp即()()(2)l m njiimjpp同理()1mjjmjp 若 为常返，则()1(1)l m
21、 niimp 由知()1miimp i即 为常返态i之,若反为常返态()1(2)mjjmp 由知j 为常返态所以所以, i ,j 或者同为常返态同为常返态,或者同为非常返态或者同为非常返态.下面考虑下面考虑 当当i ,j 同为常返态时的情况同为常返态时的情况:j若 为零常返()lim0l m njjmp()(2)lim0miimp由知()lim0mjjmp则i为零常返ij同理时，为可得 也零常返是零常返所以所以, i ,j 或者同为零常返态同为零常返态,或者同为正常返态或者同为正常返态.下面证明下面证明 当当i ,j 同为正常返态时同为正常返态时,周期相同周期相同,iji jd d设同为正常返
22、状态，周期分别为()( )( )( )( )C-Kn lnlnljjjkkjjiijkppppp由方程0 jd nlm又对有()()jjl m nmiipp()1,0miimm mp则对自然也有()()0l m nmjjiippjd nmljd mjid djiddijdd同理可证jidd所以所以, i ,j 或者同为正常返非周期状态或者同为正常返非周期状态(遍历态遍历态), 或者同为正常返周期状态或者同为正常返周期状态,且周期相同且周期相同.作业：1.0,1,2,3,0.20.8000001,00101000Ip马氏链的状态空间是转移概率矩阵是：试界定该马氏链的状态性质。( )2.0,0.nijijnp如果 是常返状态， 是非常返状态。证明对
