离散时间的马尔可夫链

1、第1章离散时间的马尔可夫链§1随机过程的基本概念定义1设(C,F,P)是概率空间，(E,E)是可测空间，T是指标集.若对任何t”，有Xt:CtE,且X的F/E,则称“,tT是(QF,P)上的取值于(E,E)中的随机过程，在无混淆的情况下简称Xt(&),twT为随机过程，称(E,E)为状态空间或相空间，称E中的元素为状态，称T为时间域.对每个固定的切wc,称Xt8)为1Xt®),twT对应于缶的轨道或现实，对每个固定的twT,称“侬)为£值随机元.有时Xt(o)也记为Xt()=Xt=X(t)=X(t,)设TUR,匕，tWT是F中的一族单调增的子仃代数(仃代数

2、流)，即VtwTnFtuF,且Ft是仃代数；-s,tT,s：t=FsFt.若XtwFt/E(VtT),则称Xt,t亡丁是适应的随机过程，或适应于的随机过程.特别地，若令Ft-(Xs,s<t,sT)：二(Xs(E)s讨s争是由Xs,s<t,sT所生成的仃代数，则Xt,HT是Ft适应的随机过程.当(E,E)=(R,B1)时，称Xt,HT为实值随机过程；当(E,E)=(C,Bc)时，称Xt,YT为复值随机过程；当(E,E)=(Rn,BJ时，称汉，HT为n维随机过程；当E是可列集(有限集)时，称Xt,t乏丁为可列(有限)随机过程；当T=R,R+或b,b时，称%,tT)为连续参数的随机过程；

3、当T=2或2+时，称Xt,tT为离散参数的随机过程(随机序列)；当T=Rn,(R+)n,Z"或(Z+)n(n之2)时，称区,tT)为随机场.随机过程的四种类型:(1)(2)(3)(4)指标集指标集指标集指标集T离散，状态空间T离散，状态空间T连续，状态空间T连续，状态空间E离散的随机过程;E连续的随机过程；E离散的随机过程；E连续的随机过程.然而，以上分类是表面的，更深刻的是按随机过程的概率结构而分类例如：马尔可夫（Markov）过程、平稳过程、独立增量过程、二阶矩过程、正态过程、泊松（Poisson）过程、生灭过程、分枝过程、更新过程、鞅等对于随机过程Xt,twT而言，可以这样设想

4、，有一个作随机游动的质点M,以Xt表示在时刻t质点M的位置，于是Xt,tWT描绘了质点M所作的随机运动的变化过程，一般把“Xt=x”形象地说成“在时刻t质点M处于状态x”.定义2设Xt,twT是概率空间（QF,P）上的、以（E,E）为状态空间的随机过程，T=R+（或R或直线上的任一区间）.如果VAWE，有【（t,）:（t,）T''?,X（t,）AB（T）F则称Xt,t亡丁是可测的.设Ft,tT是F中的一族单调增的子仃代数.如果VtT,AWE,有（u,）：（u,）三0,tI；：,X（tj）A”B1.0,11Ft则称Xt,t亡丁关于（Ft,twT循序可测.命题1设XuCtE,XtF

5、t/E（VtwT）,K,twT是F中的一族单调增的子仃代数.如果Xt,t丁关于K,tT循序可测，则Xt,tT是可测的.定义3设Xt,tT是随机过程，称Ft（x）P：,:Xt（）<x?=P：Xt<x?,xR,-tT为随机过程Xt,t亡丁的一维分布函数；称Ft1,t2（x1,x2）：P'：Xt1MXi,Xt2Ex2）,Xi,X2R,-t1,t2T为随机过程Xt,t丁的二维分布函数；一般地，称Ft1,t2：tn（X1,X2,，Xn）"汉1",Xt2MX2,，XtnMXn）Xi,X2,XnR,-tj,tnT为随机过程1Xt,tT的n维分布函数；而称F.武Ft/；

6、,tn（x1,X2，Xn）:t1,t2,tnT,n-1?为随机过程Xt,twT的有限维分布函数族.随机过程Xt,twT的有限维分布函数族F具有下列性质：1 .对Vn>1,，1,t2,，tnWT,及t1,t2,，tn的任意排列匕儿,，八,有Ft",1（%/,，）=Ft1,t2：:tn（X1,X2，）（对称性）2 .对V1<mn,有Fj,tm（X1,X2，Xm）=凡心tm，gtn（X1,&,，。，+，+8）（相容性）注若知道了随机过程Xt,t乏T的有限维分布函数族F,便知道了这一随机过程中任意有限个随机变量的联合分布，也就可以完全确定它们之间的相互关系.可见，随机过程

7、的有限维分布函数族能够完整地描述随机过程的统计特征.但是在实际问题中，要知道随机过程的有限维分布函数族是不可能的，因此，人们想到了用随机过程的某些数字特征来刻画随机过程.定义4设Xt,twT是随机过程，称m(t).：EXt=：xdFt(x)=平()P(d),tT为Xt,twT的均值函数；称D(t).：DXt=E(Xt-m(t)2,tT为Xt,twT的方差函数；称C(s,t).Cov(Xs,Xt)=E(Xs-m(s)(Xt-m(t),s,tT为Xt,twT的协方差函数；称R(s,t)=E(XsXJ,s,tT为<Xt,yt的相关函数.注若Xt,tET是复值随机过程，则方差函数的定义为D(t)

8、=EXt-m(t)2,tT协方差函数的定义为C(s,t)=E(Xs-m(s)(Xt-m(t),s,tT相关函数的定义为R(s,t)=E(XsX?),s,tT性质(1) C(t,t)=D(t),t”；(2) C(s,t)=R(s,t)-m(s)m(t),s,tT;(3)若m三0,则C(s,t)=R(s,t),s,tT.§2马尔可夫链的定义在实际中有一类很广泛的随机过程，其特点是：过去只影响现在，而不影响将来.这种随机过程称为马尔可夫过程.状态离散的马尔可夫过程称为马尔可夫链，本章介绍时间离散的马尔可夫链(简称马尔可夫链)马尔可夫(Markov)过程的研究始于1906年，是随机过程的一个

9、重要分支，它在近代物理、生物学、管理科学、信息处理、自动控制、金融保险等方面有着许多重要应用.在本章中，无特别声明我们总是假设：1 .参数集合T=<0,1,2,;2 .状态空间$=0,1,2-7或$=卜"2,1,0,1,2广或其子集.定义5设收口，n主0是定义在概率空间(QF,P)上的随机过程，状态空间为S.若对于任意的n之1及任意的整数0Mti<t2c<tn<t,i1,i2，in,jwS,有PXt=j|Xt1=i1,Xt2=i2,->Xtn=in)=PXt=jXtn=in(%)则称<Xn>n至0为马尔可夫链，简称马氏链.等式(*)称为马氏性

10、或无后效性，且假定(w)式两端的条件概率都有意义(以下涉及到条件概率的式子都作类似的假定)定理1随机过程Xn,n之0是马尔可夫链的充要条件是对任意的n之1及任意的i/,，in”S,有P<Xn+=jX1=i1,X2=i2,1Xn=in=PXnH1=jXn=in)§3转移概率对于马尔可夫链Xn,n之0,描述它概率性质最重要的是它在时刻m的一步转移概率Pij(m)=PXm.=j|Xm=i,i,jws.马尔可夫链是描述某些特定的随机现象的数学.型，而产生这种特定的随机现象的具体模型一般称为系统，因此我们经常把事件Xm=i说成是在时刻m时系统处于状态1 ,把PXm书=jXm=i说成已知在

11、时刻m时系统处于状态i,而在时刻m+1时系统转移到状态j的概率等等.定义6设Xn,n20是状态空间为S的马尔可夫链，称Pi(n)(m)=PXm*"j|Xm=i,i,jWS为系统在时刻m时处于状态i的条件下，经n步转移到状态j的n步转移概率，简称时刻m的n步转移概率.显然，pjn)(m)具有下列性质：(1) pjn)(m)之0,i,jWS；(2) “Pijn)(m)八PiXmn=jXm=i=1,iS.jSjS上述性质说明了，对于任意给定的iWS及m之0,n1,p(m),jws是一个概率分布.规定：(1) p；)(m)=Pj(m)；C1i=j(2) P；)(m)j=0.二:0,Ij.若p

12、(n)(m)与m无关，则称Xn,n之0是时齐的或齐次白马尔可夫链.此时，记pjn)=pjn)(m),i,jwS,n1；一步转移概率记为p0=pj1),i,jwS.对时齐的马尔可夫链Xn,n20,有pjn)=PXm4n=j|Xm=i=PXn=j|X。=i,i,jWS,Vm20以下恒设马尔可夫链Xn,n之0是时齐的，并简称为马尔可夫链.性质马尔可夫链Xn,n之0的n步转移概率p具有下列性质(1)Vi,jeS,pjn)之0；(2)VieS,Zp(n)=1.j三S定理2(Chapman-Kolmogorov)设p是马尔可夫链Xn,n之0的n步转移概率，则Vi,jwS,m,n之0,有pi(m*)=

13、63;pi(km)pkjn)(C-K方程)k:S证明pij)=PXm=jX0=i=pjk守Xm=k,Xm4n=jX0=i=pjk台Xm=k,Xm+=jX0=i=gPXm=k,Xm*=jX0=ikSk三S=£PXm=k|X0=iPXm*=j|X0=i,Xm=kkS=£PXm=k|X0=iPXm*=j|Xm=kkS=ZP(Xm=k|X0=i)PXn=j|X0=k)=Sp(km)pkjn)kSk.S定理3马尔可夫链(Xn,n至0的一步转移概率pij可以确定所有的n步转移概率(n)pij.证明由C-K方程，显然.记P=(pjn)i,j稔，P=P(1)=(pij)i,j含.称P为马尔

14、可夫链Xn,n占0的n步转移矩阵，称P为马尔可夫链Xn,n±0的(一步)转移矩阵.此时，C-K方程可表示为P(m+)=P(m)p且p=pn.定义7设Xn,n至0是马尔可夫链，对任意的n至0,称K(n)=PXn=iLiwS为绝对概率，特别地，称40)=px0=0,小S为初始概率.显然，绝对概率和初始概率具有下列性质：Mn)之0,i亡Sf方(0)>0,i=S卜4(n)=1,所(0)=1.i.S.iS故对任意n占0,.(n),iwS)是概率分布，通常称为绝对(概率)分布；特别，仁(0),iWS称为初始(概率)分布.记口(0)=展0)金，n(n)=(n)后.定理4设Xn,n20是马尔可

15、夫链，则它的任意有限维概率分布完全由初始分布和一步转移概率决定.证明对任意的n至1,任意的整数0Eti<t2cctn及任意的ii,i2，"乏S,有PXt1-i1,Xt2-i2>,Xtn-inrf=PliSX0=ir?,Xt|=ii,Xt2=i2,Xtn=3=P''iSX0=i,Xt-ii,Xt2-i2>,XtniSi2n=ziSPIX。=i,Xt1=ii,Xt2=i2>>XtnIS2n二in)=in=£噌Px0=ipXt1=iiX°=ipXt2=i2X0=i,Xti=ii'pixtn=inX0=i,Xti=ii

16、>'Jb,Xtni=inJ=Zipx。viMx%-iiX0#：P：Xt2=i2Xt1=ii)=£PiXtn=in=in,'人也-tn1)Rnjn§4若干例子n定义8设二，。，J,是取整数值的独立同分布的随机变量序列，令Xn=£:，k=0则称Xn，n之0为随机游动.定理5随机游动Xn,n之0是时齐的马尔可夫链.(证明略)例i(无限制的随机游动)若随机游动Xn,n之0的状态空间为S=k-2,i,0,i,2,且转移概率为aj=ii,Pij=«q,j=i-i,i,jeS0,其它.其中0<P<i,q=i-P.求：n步转移概率pjn

17、).解设在n步转移中，向右移动x步，向左移动y步，则经n步从i到达j,x和y应满足x+y=n,xy=ji.所以x=(n(j-i),2,y=(n-(j-i)2由于x,y只能取正整数，故n+(j-i)与n-(j-i)必须是偶数.又因在n步转移中有x步向右移动，故经n步转移由i到j共有C：种方式，于是-n(j.l)n(j,l)n，j_i)Pi(n)=JCn2p2q2,n+(ji)偶0,n+(ji)奇特另Unnnp(n)=Jc2p2q2,n偶Q,n奇例2(带有一个吸收壁的随机游动)设Xn,n20是随机游动，其状态空间为S=0,1,2,若转移概率为1 i=j=0,p, j=i+1,Pij=.i,j乏S(

18、0<p<1,p+q=1)q, j=i-10,其它.则称Xn,n至0为带有吸收壁0的随机游动.其转移矩阵为10q0P=0q00<例3（带有两个吸收壁的随机游动）S=0,1,2，舟，其转移概率为1,i=j=0,1,i=j=b,pij=，p,j=i+1,i,jq,j=iT，0,其它.其转移矩阵为Z100q0p0q0P=000000例4（带有一个反射壁的随机游动）00、p00pq0）设Xn,n之0是随机游动，其状态空间为S(0：二p：二1,pq=1)00000000p0000q0p0001/设(Xn,n之0是随机游动，其状态空间为S=0,1,2,其转移概率为1,i=0,j=1,i,j

19、S(0<p<1,pq=1)P,j=i+1,Pijq,j=i-1，o,其它.其转移矩阵为,0qp=00<例5（带有两个反射壁的随机游动）Xn,n>0,其转移概率为1 00、0P0q0P0q0,.,设xn,n20是随机游动，其状态空间为1,i=0,j=1,1,i=b,j=b-1,Pj=P,j=i1,q,j=i-1，0,其它.i,jS(0二P；1,Pq=1)其转移矩阵为01q0D0qp=0000例6（带有弹性壁的随机游动）00000P00000P00000q0P00010>设Xn,n父0是随机游动，其状态空间为S=&.，2,1,0,1,2,其转移概率为P,j=i

20、+1,r,j=i,q,j=-1,q其它.i,jS(0二P,q,r<1,Pqr=1)其转移矩阵为例7设Xn,n20是只有两个状态（PrPqr'+,JS=0,1）的随机游动，其转移矩阵为1-pp'P=,0<p<1,0cq<1、q1-q>这里p+q未必等于1.求P(n),lim旗(n)，lim叫(n).n'，n：'，(n)zp00n()p01(n)pi0pi(n)由C-K方程，得p00)jkSp0kd)pk0=p009P00p0nqp10=(1-p)p00,)+q(1-p0)=q+(1-p-q)p00)六（1心5,(n)(n)(n)ppn

21、-(1-p-q)pqpqpqn(1-p-q)pqpq同理可求p01,pl0,p11,故+-(1-p-q)P(n)p+qp+qP33(1-p-q)、p+qp+q设初始分布为n(0)=质(0),1(0)1,则q(1-p-q)np+qJ质S)=0t(0(500-1冗p(n0j0=无(0)?+p(1pq)n+(1%(0)q<p+qp+qJ<p+q=-q+(1-p-q)npq质(0)-pp+q故lim演（n）=q，同理limw（n）=.n一p,qn；-pq例8设1Xn,n之0是马尔可夫链，状态空间S=1,2,3,转移矩阵为143/40、P=1/41/41/2<03/41/4j初始分布为

22、*0),2(0),3(0)=l/6,1/2,1/3,求(2)(1)二步转移矩阵P;(2)PX1=2%=1;(3)PJ3=2,X202,X1#2X0=2.(1)P(2)1/4143/40¥1/43/41/41/21/41/40r1/41/2=1/83/41/4人03/414J3163858383/8'1/47/16(2)由全概率公式、乘法公式、马氏性，得pix=2,X3=14PXiip1X-2,X1(XLi3=£jjx0=i扣以=2X0=iU=1X1=2=£q（0）Pi2P2;（注：也可直接由定理4得至|J）1311131642434816(3)由加法公式、

23、乘法公式、马氏性，得PX3=2,X2#2,X1#2X0=2=P1X3=2,X2=1,X1=1X0=2+PX3=2,X2=3,X1=1X0=2+PX3=2,X2=1,X1=3X0=2+PX3=2,X2=3,X1=3X0=2二P21R1P12P21P13P32P23P31P12P23P33P32964113113二，-00-444244例9设随机游动板口，n20）的状态空间S=0,1,2，小，其中0和b是吸收壁,初始状态为a,转移概率为1,P,q,。,i=j=0或i=j=b,j=i1,j-i-1,其它.0p1,q=1-p求质点被0点吸收的概率.解设Ui表示质点初始位置为i而被0点吸收的概率，则U0

24、=1,Ub=0,Ui=pUi1qUi4,i=1,2,b-1由于p+q=1，故p(ui+-u,)=q(uuiJL).(1)若p=q=1*，则u4u=5u=C(常数)，故5=C+u，ui=iC+u0.1 i.a因u0=1,ub=0,故C=一一，从而U=-+1,故ua=1-.bbb(2)若p=q，则ui1-ui=(q,p)(ui-uil)=(q.p)i(u1-1)iuiLUq.p(u-1)从而b_Jub=ubq；p(u1-1)bNubj=ubNq.p(u17).0,u二u°q.p(u1-1)相加，得ub=u0.1-(qp)b1-(qp)1)，所以d_1-(qp)u11-(qp)b.1-(q

25、p)a1-(qp)(u1-1)=1+1(q.p)a'1-(q/p)、1-(q/p)<1-(q/p)l_1-(qp)a1-(qp)b§5状态的分类设Xn，n之。是马氏链，S为状态空间，pj为转移概率.定义9设A二S,令minn:Xn亡A,n之"，3n1,使XneATa=（收，Vn4,有XA称Ta为Un,n之0首达A的时刻（或A的首达时），Ta是随机变量，其可能值为1,2,，F当A为单点集j时，记T6户/.令fjn)=P，：Tj叫Xo=i>,n_1则fj表示系统从状态i出发，经n步首次到达状态j的概率.利用乘法公式、马氏性易知：)=PjXi=j,X2=j,X

26、nj,Xn=jXo'i)'Pilip2P_iijn1ii=j2；jn_ii；j一fii表示系统从i出发，经n步首次返回i的概率.下面的定理是联系转移概率Pj(n)和首达概率fjn)之间关系的常用定理.n定理6对任意斗犬态i,j亡S,n至1,有p(n)=£fj)p%m)m：1证明Pijn)=pXn=j|Xo=i=pWn,Xn=j|Xo=i'nni1jIXo=i=P5=m,Xn=jXo=im=1'n,=P；"Tj=m,Xn=.mmn=£P1Tj=m,Xn=j|Xo=im1n=ZPTj=m|Xo=加Xn=j|xo=i,Tj=mm1n=&#

27、163;fj(m)PXn=j|Xo=i,X1#j,，Xm#j,Xm=jm1nn=£fij(m)PXn=j|Xm=j=Zfij(m)PXn5=j|Xo=jm1m1n(m)(n-m)=fijPjjm1令QOcOfj=£fj=EP<Tj=n|Xo=i=P'Tj<9|X0=in1n1则fj表示系统从状态i出发，经有限次到达状态j的概率(也可以说成系统从状态i出发,迟早要到达状态j的概率).显然有o三廿三P"M1特别，为表示从状态i出发，迟早要返回状态i的概率.定义10若品=1,则称i是常返状态；若<1,则称i是非常返状态或滑过状态（显然，吸收状态

28、是常返状态）对于常返状态i,因品=P1<sXo=i=1,这表明，从状态i出发必定要返回它自身.记SR=i：iwS,%=1,SN=i：iwS,为<仆，则S=SrUSn,SrSn=*.例10设马氏链Xn,n20的状态空间为S=1,2,3,4,转移矩阵为何401/41/2、01/21/20-0100【0001，试判别状态的常返性.解（1（11）=1；4,fn1）=0n2）储=1.4f2（2）=1-2,f22）=1.2,f2V=0（n-3）f22=1.f3（；）=0,f3；22.12,f3鼠）（12f,f33=1.f4?=1,f47=0（n至2）f44=1.故Sr=2,3,4）,Sn=11

29、卜记片=E（TjX。=i）,S=E（TiX。=i）,则%表示系统从状态i出发，首达状态j的平均时间；色表示系统从状态i出发，首次返回i的平均时间.记Nj表示系统经过Nj的次数，Nj是随机变量，Ij（Xn）表示系统在时刻n经过状态j的次数，即(n-1)1,Xn=jIj(Xn)=0,Xn=j记mj=E(NjX0=i),则NjbIj(Xn).n1m=E（NX0=i）,则mj表示系统从状态i出发，经过状态j的平均次数；中表示系统从状态i出发，返回状态i的平均次数oOoO定理7证明设ijS,则mj=ZpF,m=工pin).n1nd00mj=E(NjX0=i)=EIj(Xn)X0=i)n1oO=、E(Ij

30、(Xn)X0=i)n1p(Xn=jX0=i)=ZP；n，n1n1oOmi=E(NjX0=i)=工Pi；)n1tffij,jwSr,定理8设i,jwS,则PNjX=Ji=«jj0,jwSn.证明pN=s|X=i=pN|n0i=Mrnp至N声伙n4nE-而pNjnX0=i=p!u=m,N之nX0=iJU|J*iUm3QO°=£p/=m,N>nX0=im=1CO=£pl/=mX0=1扣帅n.X0=i,/=mmz1cd=£fij(m)pNjin1X0=j=fijpNj2n1X0=jmz1=fijfjjp(NjWn-2X0=j=fij(fjj)n,

31、pNj>0X0=j故f、飞，jw&pNj=8X0=i=lim%(品)=jn°jj0,jwSnt1，iwSR,推论设iS,则pNi=8Xo=i)=R0,YSn.该推论说明了定义6的合理性，即：如果状态i是常返的，则以概率1,系统无穷次返回状态i；如果状态i是非常返的，则以概率1,系统只有有限次返回状态i,亦即系统无穷次返回状态i的概率为0.定理9设i,jwS,则0,jw0,%=0mj=E(Nj|X0=i)=俨，jw0,fj>0J“(1-九)，j证明(1)若jwSr,fij=0,则vn之1,有品=0,由定理6知，vn之1,有Pijn)=0,所以mj=E(Nj|Xo=i

32、)=0.(2)若jwSr,tj>Q则由定理8知，PNj=TXo=>0,所以mj=PE(NjXq=i)=笛.(3)若j,则由定理8知，PNj=8Xq=i=0,所以mj=E(Nj|X0=i)=£nPNj=n|X0=i=£：nRNj之nXq=iPNj之n+1,X0=i="nJlljij(fjj)n'-fij(fjj/=fij(1-fjj)”n6fjj'=fij(1-fjj)占乙(fjj)=fij/(1-fjj)二，iSr,推论设iWS,则m=E(NiXq=i)=«,fii(1.fi)iSn.定义11设i,jwS,若mn1,使pjn)

33、>Q,则称状态i可达状态j,记为itj；若Vn之1,有pi(n)=Q,则称状态i不可达状态j,记为i-yj；若itj且jti,则称状态i和状态j相通（或互通），记为ihj.定理1Q(1)若iTk且kTj,则iTj；(2)若iHk且kJj,则iaj.证明因itk且ktj,所以3m>1,n>1,使得p：m)>Q,pkjn)>Q,由C-K方程，有p加=£p；m)p(n)之pi(km)pkjn)>Q,故iTj.l.S(2)由(1)易知(2)成立.定理11设i,jwS,则(1)iTj=fij>Q；(2)gj=fijfji>Q.证明只证明(1).&

34、quot;="设iTj,则3n>1,>p(n)>Q,而(n)-n(m)(n_m)Fij=mdfijpjj因此，fj，fj，fj(n)中至少有一个大于Q,从而%=£二俨)>Q."u"设fj>Q,因fj=L：)，所以：3n*,使fj(n)>Q,故(n)=.,nf.(m)D(nmf.(n)(Q)=f.(n),Qpij,一m丑"jpjjijpjjij0即ij.qQ定理12(1)i亡SrU=£np(n)*;(2)iwSn工nLp(n)<8，这时必有nmpiin)=0；(3)若i,jWS,iWSr,iTj

35、,则产Sr,且fii=fij=fji=fjj=1.证明由定理7及定理9的推论即知（1）和（2）;（3）略.对于常返状态，即iwSr,由于九=2;俨=1,因此"i，n之1）是一个概率分布，故4=E(TX。=i)=£nPT=nX°=i=£2nfj，易知Ji1.定义12设状态i是常返的，即iwSr.若叫g,则称i是正常返白若Ni=g,则称i是零常返的.记S=i：iwSR,如',sR=i:iwSR,Ni=妙上定义13(1)设CuS,若ViwC,jwSC,有iTj,则称C是闭集；(2)设CuS,若Vi,jwC,都有iTj,则称C是不可约的；(3)若S是不可

36、约的，则称马氏链Xn,n之0是不可约的(即Vi,jwSniTj).定理13设CuS,则下列各条等价(1) C是闭集；(2) VieC,j2C,n21=pjn)=0；(3) -iC,j-C=fj-0.注(1)若C是闭集，则ViwC,n之1,有£j»Pijn)=1.(2)整个状态空间S是闭集，是最大的闭集；吸收状态i(即pii=1)是闭集，是最小的闭集定理14Sr,SR,SR都是闭集.证明设iwSr,jSR.若fj>0,则iTj,故jw0.矛盾，从而%=0,由上面的定理13,知&是闭集.同理可证sR,SR也是闭集.例11设以0，n±0是马尔可夫链，状态空

37、间为S=11,2,3,4,5),转移矩阵为1/20”000000001/2001/201/2P=0011001010问状态空间S=1,2,3,4,5中是否含有真的不可约的闭子集？Xn,nA0是否是不可约马尔可夫链.解易知，状态3是吸收状态，故3是闭集；1,4,”3,4,1,2,3,4均是闭集;其中3,11,4均是不可约的；因为S含有真的闭子集，所以Xn,n之0为非不可约马尔可夫链.例12设马尔可夫链Xn，n之0的状态空间为S=1,2，9,状态之间的转移概率如图所示.由图可见：自状态1出发，再返回状态1的可能步数为T-4,6,8,10,?显然T的最大公约数为2.但2更T,即自状态1出发经过2步不

38、能返回状态1.但我们仍把2定义为状态2的周期.pjn)，对于定义14设马尔可夫链Xn,n之0的状态空间为S,n步转移概率为iwS,若集合nn之1,p：n)a。非空，则称该集合的最大公约数d-d(i)：G.C.D:nn_1,p)0/为状态i的周期.如果d>1,称状态i为周期的，如果d=1,称状态i为非周期的.若n:n至1,piin)>0是空集，则不对状态i定义周期.由定义知，如果状态i有周期d,则对一切n00mod(d),者B有p(n)=0.但这并不是说对任意的nd,都有p(nd)>0.如在例12中，状态1的周期d=2,但p21=0.然而有如下结论.定理15设状态i的周期为d,

39、则存在正整数M,对一切nAM,有pd)>0.证明略(证明用到了初等数论的知识)定理16设状态iS,如果集合n|n之1,"n)>0非空，则G.C.Dinn_1,p(n).0.G.C.Dinn-1,fH(n)0)证明记d=G.C.Dn|n>1,pa。,c=G.C.Dnn>1,fH(n)>01,由定理6有n(n)(m)c(nm(n)(0)(n)pii-fiipii'一fiiRi-fiim1从而nn>1,pi(n)>OLn21fiJ>>)0于是有1WdWc.如果c=1,则d=c=1.如果ca1,只需证明d之c,为此只需证明c是Ln

40、之1,p(n)>0的公约数即可.换言之，只需证明对于一切n¥0【mod(c)，都有p=0.实际上，由c的定义知，当1Wr<c时，有fH(r)=0.于是，对1Wn<c,有nn(n)(m)(nw)(n而)pii二，fiipii=，0Pii=0m1m1现假设当n=kc+r,k=0,1,2,，N1时，有pi(n)=0.注意到n#0mod(c)时，有个)=0.则由定理6得Nc“r(Ncr)(m)(Ncr_m)Pii二三fiiPiimz4(c)(Nc.r_c)(2c)(NcTc)(Nc)(r)=TiiPiiLiPiiLiPii=0于是，由归纳法知，当n二0mod(c)1时，有P

41、i(n)=0.定理17设状态i常返且有周期d,则limP，d)=d/Hi.(其中巳为状态i的平均n_返回时间，当冉=七时，约定d/H=0)证明见可数状态的马尔可夫过程，胡迪鹤，武汉大学出版社，1983,F25/6.定义15非周期的正常返状态称为遍历状态定理18设i是常返状态，则i是零常返状态limP(n)=0；nj二i是遍历状态limPiin)=1/4>0.证明设i是零常返状态，则叶=g,由定理17,得lim3=0,而当n卜n#0mod(d)时，有r/)=0,于是得nimPr=0.反之，设n>mP=0,假设i是正常返状态，则/<s,于是由定理17,得limPiind)>

42、0,矛盾.n一设nmPi(n)=1/4>0，由知，i不能是零常返状态，从而只能是正常返状态，由定理17,得limPd)=d*i,注意到limPd)=limPi(n),得d=1,所以，i是遍历n-n-n状态.反之，由定理17是显然的.定理19设状态i,jwS,且iHj,则(1) i与j同为常返状态或同为非常返状态；如果同为常返状态，则它们同为正常返状态或同为零常返状态(2) i与j有相同的周期.证明(1)由于i修j,由可达的定义知存在l之1和n之1,使得P；n)0由C-K方程，对任意的m之1,总有(lmn)(l)(m)(n)(m)(lmn)(n)(m)(l)(m)PiiPijPjjPji-

43、Pjj,PjjPjiPiiPjPii将上式两边从1到00求和，得(lmn)一二D(m)(lmn)m)m4Pli一mdPJJ，m4PJJ一mdPii可见，z:厂与工工P；k)相互控制，所以它们同为无穷或同为有限.由定理12知,i与j同为常返状态或同为非常返状态若i与j同为常返状态，在以上的不等式中取极限，令mT8,得.(1由由)_R.(m).(l+mFi)”.Q(m)limpH至uplimpjj,1impjj>li喃piimmmm二二'因此，limp；k)与limp同为正或同为零，由定理18知，i与j同为正常返状态或同为k_-k_零常返状态.(2)设状态i的周期为d,状态j的周期为

44、c.因为p：=0>0,pjn)=P>0,所(m)(lOm：(n)(l)(m)(n)(m)以对任一使pj>0的m,必有pii>pijpjjppjj>0,从而d可除尽l+m+n.又因为膏十)至piJ(l)p(in)=aP>0,所以d也可除尽l+n.因此，d可除尽m.这说明d<c.同理可证d2c.故d=c,即状态i与j有相同的周期.注状态的常返性与马尔可夫链的初始分布是无关的定理20状态空间S可唯一地分解成有限个或可列无穷个互不相交的子集之和，即S=SNUsUS2)U，且使得(i)每个sRk)是常返状态组成的不可约闭集；(2)sRk)中的状态或全是正常返状态

45、，或全是零常返状态，且有相同的周期；(3) Sn是由全体非常返斗态组成，自S，)中的状态不能到达Sn中的状态.定理21周期为d的不可约马尔可夫链，其状态空间S可唯一地分解为d个互不相交的子集之和，即Sn&UsU&UUsd，且使彳#自Sr中任一状态出发，经一步转移必进入Sr+中，r=0,1,2,，d1.(约定：Sd=S0)证明(1)任意取定一状态iwS,令Sr=j|三n20,使p(nd">0>,r=0,1,2；",d-1因S是不可约的，即S中的状态是互通的，故u：sr=s.(2)若刃wSrSt(r列)，由定义知，必存在非负整数n和m使得p；nd4r

46、)>0,p(md+)>0.又由于j修i,必存在正整数h，使p(h)>0,于是由C-K方程，有(ndr,：h)(ndr)(h)(mdt：h)(mdt)(h)Pi之pijpji>0,pi之pijpji>0所以，d能除尽nd十r十h,又能除尽md+t+h,从而d能除尽(ndrh)-(mdth)=(n-m)dr-t故d能除尽r-t,注意到0<r<d-1,0<t<d-1,故只能rt=0,这说明，当r#t时，SrSt=.(3)下面证明对任一j乞Sr,有Zk+pjk=1.事实上1二kSPjkksr1.Pjk-k.Sr1Pjk二kSr1Pjk最后一个等式是

47、因：jsr,由定义有pijnd+)>0,而当kSr卡时，由定义有pfdH)=0,由C-K方程，有0=pfdH，故Pjk=0.(4)最后证明分解的唯一性，这只需证明So,§,，Sd不依赖于最初取定的状态i.亦即只需证明：对取定的状态i,如果j,kWSr，则对另取的状态i，仍有j,kwSr，(r'可以与r不同).设对i的分解为&,&,$,，Sd',对i'的分解为S0,S,S2,，Sd,又设j,kw&,i'wS.于是，当r>t时，自i'出发，以概率1只能在rt,rt+d,rt+2d,等这些步上转移到j或k,从而j,

48、kwSr'；当r<t时，自i'出发，以概率1只能在d_(t-r)=r-t+d,rt+2d,r-t+3d,等这些步上转移至Uj或k,从而j,kSr/.定理22设Xn,n±0是周期为d的不可约的马尔可夫链，则得一新的马尔可夫链Xnd,n至0,其一步转移矩阵为P(d)=(p(d),原马尔可夫链1Xn,n至0按照定理21分解出的每个S,是新马尔可夫链(Xnd,n20的不可约的闭集，且S中的状态对新马尔可夫链是非周期的.(证明略)例13设不可约马尔可夫链Xn,n20的状态空间为S=1,2,3,4,5,6,周期为d=3,转移矩阵为001/301200101201301300

49、0000010000、001/403/40对取定的状态1,易知S°j三n20,使P1(3n)>0=1,4,6S1:qn一0,使pn1)0：=13,5)S2二。n一0,使p*2)0)-3故$=$01§11$2=1,4,6U3,5U2.马尔可夫链X3n,n0的转移矩阵为13001/301/3、010000(3) _007/1205/120-1/3001/301/3007/1205/120“3001/301/31§6n步转移概率pjn)的渐近性质与平稳分布对p(n)极限性质，我们讨论两个问题.一是limpjn)是否存在；二是其极限是否与i有n_关.这就与马尔可夫链

50、的所谓平稳分布有密切联系定理23若jWS是非常返状态或零常返状态，则对任意iwS,有limp(n)=0.nj证明因jWS是非常返状态或零常返状态，所以limpjn)=0(由定理12和定理18).n：由定理6,对正整数N<n,有nNnNnn(n)(k)(n_k)(k)(n±)(k)(nA)(k)(n<)(k)pij.fijpjj.fijpjj.fijpjj-fijpjj.fijk1k1k用1k1k-N1固定N,令nt比，得(n)(k):f(k)limp10-ff.n一，ijk=N1ijk=N1ijoO再令Nts,因工fj(k)<1,所以limpjn)=0.nkW推论1

51、如果马尔可夫链的状态空间S是有限集，则S中的状态不可能全是非常返状态，也不可能含有零常返状态，从而不可约的有限马尔可夫链的状态都是正常返状态.证明设S=0,1,2，N.如果所有状态都是非常返状态，则对任意i,jwS,由N定理23知limp；n)=0,从而1=Zpjn)T0(nTg).矛盾.j3如果S中有零常返状态i/C=j|jwS,iTj，若iTj,由定理12,有jTi,即C中的状态是互通的，从而C是不可约.又由定理19知，C中全是零常返状态，从而由定理14知，C是闭集，即C是不可约的闭集.故1=2j©pi(n).令nTR，注意到C是有限集，由定理23得1=£叵p；n)T0

52、(nT8).矛盾.于是，有限马尔可夫链的状态空间必含有正常返状态.对于不可约的有限马尔可夫链，由于所有状态是互通的，故所有状态都是正常返状态推论2若马尔可夫链的非常返状态构成的集合Sn是有限集，则Sn不是I集.证明若Sn是闭集，将产生矛盾.推论3若马尔可夫链的状态空间S有一个零常返状态，则必有无限多个零常返状态.证明设有零常返状态iWS,令C=j|jWS,i->j,若C是有限集，将产生矛盾.定理23考虑的是非常返状态或零常返状态的渐近分布，但当jS是正常返状态时,limpi(n)不一定存在，即使存在也可能与i有关.因此，我们退而研究p(nd)及工工二p(k)n二nk-的极限.记fj(r)

53、=£:卫fij(md*),0<r<d-1.则fj(r)表示系统从状态i出发，经n=rmod(d)步首次到达状态j的概率，显然tddx,'(md"r_0fij(r)-rz0m=0fij=Z：一df(md-r)一二：f(m)m=0r=0fijm=0fjfhj定理24设jWS是正常返状态，周期为limp(ndr)n.jd,则ViwS及0WrEd1,有fj(r)证明因为当n#0mod(d)时，p=0.所以(nd：r);ndr(k)(nd：r-k)1n(md：r)(nd-md)pij=k_0fijpjj=m=0fijpjj于是，对1EN<n,有-N(mdf(

54、nd_md).(ndr)m£fjpjj-pij-(md-r)(nd_md)(md-r)iPjj-mzN1fij固定N,令nT1,由定理17,得d-N(md-r)(ndr).d_N(mdr)(mdr),mjjTim：pij三丁"mJm"1fj再令NT七，得白)”-fij(r)0jj是，得顾邛*r)=!fij(r)j推论设周期为d的、不可约的、正常返的马尔可夫链的状态空间为S,则对一切i,j一,有(nd)Jd"j,当i与j同属于某个0nmpij=i0,其他-.d1其中S=USk为定理21中所给出.特别，当d=1时，对一切i,jWS,有k=0limp(n)jdfij(0)证明在定理24中，令r=0,得(nd)limpijnij其中fij(0)=£mfij(md).如果i与j不在同一个Sk中，则由定理21知pi1nd)=0,注意到f0(nd)<p(nd),得fjj(nd)=0,故%(0)=0.如果i与j同属于某个Sk,则当n#0mod(d)】时，pjn)=0,从而fj(n)=0,故二fij(md)(m)fij(0)=m%=mfij由定理