随机过程第五章连续时间的马尔可夫链

1、第五章连续时间的马尔可夫链5.1连续时间的马尔可夫链考虑取非负整数值的连续时间随机过程X(t),t之0.定义5.1设随机过程X(t),t20.,状态空间I=in,n占0,若对任意0tit2<.<tn-1及ii,i?,.in4匚,有PX(tn书)=inX(ti)=ii,X(t2)=i2,.X.(tn)=in=PX(-X(tn)=in(5.1)则称X(t),t之0.为连续时间马尔可夫链.由定义知，连续时间马尔可夫链是具有马尔可夫性的随机过程，即过程在已知现在时刻tn及一切过去时刻所处状态的条件下，将来时刻tn书的状态只依赖于现在状态而与过去无关.记(5.1)式条件概率一般形式为PX(s

2、+t)=j|X(s)=i=Pij(s,t)(5.2)它表示系统在s时刻处于状态i,经过时间t后转移到状态j的转移概率.定义5.2若(5.2)式的转移概率与s无关，则称连续时间马尔可夫链具有平稳的或齐次的转移概率，此时转移概率简记为Pij(s,t)=Pj(t),其转移概率矩阵简记为P二0),。,jI,t一0).以下的讨论均假定我们所考虑的连续时间马尔可夫链都具有齐次转移概率.简称为齐次马尔可夫过程.假设在某时刻，比如说时刻0,马尔可夫链进入状态i,而且接下来的s个单位时间单位中过程未离开状态i,(即未发生转移)，问随后的t个单位时间中过程仍不离开状态i的概率是多少呢？由马尔可夫我们知道，过程在时

3、刻s处于状态i条件下，在区间s,s+t中仍然处于i的概率正是它处于i至少t个单位的无条件概率.若记hi为记过程在转移到另一个状态之前停留在状态i的时间，则对一切s,t>0有Phisthis=Pht,可见，随机变量几具有无记忆性，因此hi服从指数分布.由此可见，一个连续时间马尔可夫链，每当它进入状态i,具有如下性质：(1)在转移到另一状态之前处于状态i的时间服从参数为Vi的指数分布；(2)当过程离开状态i时，接着以概率Pj进行状态j,ZPj=1.jJ；上述性质也是我们构造连续时间马尔可夫链的一种方法.当吊=七时，称状态i为瞬时状态，因为过程一旦进入此状态立即就离开M=0时,称状态i为吸收状

4、态，因为过程一旦进入状态就永远不再离开了.尽管瞬时状态在理论上是可能的，但以后假设对一切i,0MVi吧.因此，实际上一个连续时间的马尔可夫链是一个这样的随机过程，它按照一个离散时间的马尔可夫链从一个状态转移到另一个状态，但在转移到下一个状态之前，它在各个状态停留的时间服从指数分布.此外在状态i过程停留的时间与下一个到达的状态必须是相互独立的随机变量.因此下一个到达的状态依赖于hi,那么过程处于状态i已有多久的信息与一个状态的预报有关，这与马尔可夫性的假定相矛盾.定理5.1齐次马尔可夫过程的转移概率具有下列性质：(1)Pj-0；(2) '、Pj=1；ji(3) Pj(ts)=Pik(t)

5、Pkj(s).k三I其中(3)式即为连续时间齐次马尔可夫链的切普曼柯尔哥洛夫方程.证明只证(3).由全概率公式及马尔可夫性可得Pj(t+s)=PX(t+s)=j|X(0)=i)='、'PX(ts)=j,X(t)=kX(0)=ik三I='PX(t)=k|X(0)-iPX(ts)=j|X(t)=kkii='Pik(t)Pkj(s).kii对于转移概率Pij(t),一般还假定它满足：'1,ijlimPj(t)=(5.3)P，i手J.称(5.3)式为正则条件.正则条件说明，过程刚进入某状态不可能立即又跳跃到另一状态.这正好说明一个物理系统要在有限时间内发生限多次

6、跳跃，从而消耗无穷多的能量这是不可能的.定义5.3对于任一t2。记Pj(t)=PX(t)=j,p=Pj(0)=PX(0)=j,jI,分别称p乂t),j=I,Pj,jWI)齐次马尔可夫过程的绝对概率分布和初始概率分布.定理5.2齐次马尔可夫过程的绝对概率及有限维概率分布具有下列性质：(1)Pj(t)-0,(2)“Pj(t)=1,ji(3) Pj(t)-PiPj(t);i.i(4) Pj(th)=，Pi(t)Pj(h);i.i(5)PX(ti)=ii,.,X(tn)=in)=二'、PiPiiiPiii2(t2ti)Pj(tntn).iI一例5.i试证明泊松过程X(t),t>0)为连续

7、时间齐次马尔可夫链.证明先证泊松过程具有马尔可夫性，再证明齐次性.由泊松过程的定义它是独立增量过程，且X(0)=0.0<ti,.<tn<3斗，有PX(tn+)=in+X(ti)=ii,.X,(tn)=in)=PX32-X(tn)书-in|X(ti)-X(0)=ii,.=X(t2)-X(ti)1i,.X(tn)-X(")/-3)=PX(tni)-X(tn)=ini-目另一方面，因为PX(tn书)=3X(tn)=in)=PX(tn+)一X(tn)=in«inX(tn)-X(0)=in)=PX(tni)-X(tn)="iin)所以PX(i)=/X(ti

8、)=ii，.,X(tn)=in)=PX(tn*)=in*X(tn)f).即泊松过程是一个连续时间马尔可夫过程.以下证明齐次性.PX(st)=j当ji时，由泊松过程的定义X(s)=i)=PX(st)-X(s)=j-i)=eS(j-i)!j<i.时，由于过程的增量只取非负整数，故Pj(s,t)=0,所以丁(M严.丁.e八-I>iPj(s,t)=Pj(t)=(j_i)!一,0,j<i即转移概率只与t有关,泊松过程具有齐次性.5.2柯尔莫哥洛夫微分方程对于连续时间齐次马尔可夫链转移概率Pj的求解一般比较复杂.下面首先讨论Pj(t)的可微性及Pj(t)满足的柯尔莫哥洛夫微分程.引理5.

9、1设齐次马尔可夫过程满足正则性条件(5.3)，则对于任意固定的1, jwI,Pj(t)是t的一致连续函数.证明设h>0,由定理5.1得Pj(th)-Pj(t)=Pir(h)Prj(t)-Pj(t)r三I二，Pir(h)Prj(t)PH(h)Pj(t)-Pj(t)rd="Pir(h)Pd(t)-1-PH(h)Pj(t)r-i：故有Pj(th)-Pj(t)=-1-P.(h)Pj(t),-1-Ri(h),Pj(th)-Pj(t)<Pir(h)Prj(t)三'、Pir(h)=1-P"(h),r-irT因此Pj(t+h)-Pj(t)«1-Pii(h).对

10、于h<0,同样有Pij(t+h)-Pj(t)<1-Pii(-h).综上所述得到Pj(t+h)-Pj(t)|W1P"(h).由正则性条件知limhTPj(t+h)Pj(t)=0,即Pj(t)关于t是一一致连续的.以下我们包设齐次马尔可夫过程满足正则性条件(5.3)式.定理5.3设Pj(t)是齐次马尔可夫过程的转移概率，则下列极限存在limt/二Pii(：t)-Vi=q"m二;一二tPj(；：t).:t=qj二二，i二j.我们称qj为齐次马尔可夫过程从状态i到状态j的转移概率或跳跃强度.定理中的极限的概率意义为：在长为&的时间区间内，过程从状态i转移到另一其

11、他状态的转移概率为1-Pii(M)等于qHAt加一个比At高阶的无穷小量，而过程从状态i转移到状态j的转移概率为Pj(At)等于qj与加一个比占高阶的无穷小量.推论对有限齐次马尔可夫过程，有qn二'、qj：二二证明由定理5.1，有'Pj(t)=1,1一Pii(.：t)="Pj(：t)jIjd由于求和是在有限集中进行，故有(5.4).1-Pii(t)Pj(：t)qii-lmt0-lim_0-qij.：tjitj-i对于状态空间无限的齐次马尔可夫过程，一般只有qii-'qj.j大若连续时间齐次马尔可夫是具有有限状态空间I=0,1,2,n,则其转移速率构(5.5)成

12、以下形式的矩阵一q00q01.q°n1q10一q11q1n._qn0.qn1.一qnn-Q二由(5.4)式知,Q矩阵的每一行元素之和为0,对角线元素为负或0,其余，qj之0.利用Q矩阵可以推出任意时间间隔t的转移概率所满足的方法组，从而可以求解转移概率.由切普曼柯尔莫哥洛夫方程有Pj(th)Pik(h)Pkj(t),k-I或等价地Pj(th)-pj(t)="Pik(h)PM)-1-pH(h)pj(t)k4两边除以h后令hT0取极限，应用定理5.3得到Pj(th)-Pj(t)Rk(h)limh0=limhJ。Pkj(t)qiiPj(t)(5.6)hkjh假定在(5.6)式的右

13、边可交换极限与求和，再运用定理5.3，于是得到以下结论：定理5.4(柯尔莫哥洛夫向后方程)假设Zqik=q.,则对一切i,j及t之0,有Pij(t)-qikPkj(t)-qPj,(5.7)kT证明只要证明(5.6)式右边极限与求和可交换次序.现在对于任意固定的N,有limh)Dinfvh)Pkj(t)-limh力inf'(h)Pkj(t)=xqikPkj(t)kdhkT,k：Nhk-i,k:：N因为上式对一切N成立，所以limh力inf%Pkj(t)-“qikPkj(t)(5.8)kr.i,hkd为了倒转不等式，注意对于N>i,由于Pkj(t)<1,所以limosuPPik

14、(h)Pkj(t)<Eh'Pik(h)Pik(h).-limhqsupPkj(t)三k-i,k:Nhk_NhPik(h)1-Pii(h)Pik(h).-limhqsupPkj(t)二k-t,k:NhhkJ,k;Nhe%qikPkj(t)qn-qik,km,k：Nk寸，k：N令Nt笛，由定理5.3和条件得limhosup'PikJh)Pkj(t)qikPkj(t).k$hk;i,上式连同(5.8)可得limho%Pik(h)Pkj(t)=、：qikPkj(t).k寸，hkK,定理5.4中Pj(t)满足的微分方程组以柯尔莫可洛夫向后方程著称.称它们为向后方程，是因为在计算时刻

15、t+h的状态的概率分布时我们对退后到时刻h的状态取条件，即我们从Pj(th)-P(X(th)=jX(0)=i,X(h)=k.k.P(X(h)=kX(0)=i=£Pkj(t)Pik(h)k汪开始计算.对时刻t的状态取条件我们可以导出另一组方程，称为柯尔莫哥洛夫向前方程可得Pij(th)-Pik(t)Pkj(h),k.IPij(th)-Pj(t)=Pik(t)Pkj(h)-Pj(t)k=i=，Pik(t)Pkj(h)-1-Pjj(h)Pj(t),k二j所以limh0Pj(th)-Pj(t)hPkj(h)=limh»Pik(t)-yh1-Pjj(h)Pj(t).假定我们能交换极限

16、与求和，则由定理5.3便得到Pj(t)="Pik(t)qkj-qiiPj(t),k；j令人遗憾的是上述极限与求和的交换不是包成立，所以上式并非总是成立.然而在大多数模型中-包括全部生灭过程与全部有限状态的模型，它们是成立的.定理5.5(柯尔莫哥洛夫向前方程)在适当的正则条件下，Pij(t)-Pik(t)qkj-Pj(t)qjj,(5.9)kj利用方程组(5.7)或(5.9)及初始条件Pii(0)=1,Pij(0)=0,i=j.我们可以解得Pj(t).柯尔莫哥洛夫向后和向前方程虽然形式不同，但是可以证明它们所求得的解Pj(t)是相同的.在实际应用中，当固定最后所处状态j,研究Pj(t)

17、时(i=0,1,2,n),采用向后方程比较方便；当固定状态i,研究p/t)时(j=0,1,2,),则采用向前方程较方便.向后方程和向前方程可以写成矩阵形式P(t)=QP(t),(5.10)(5.11)P=P(t)Q,其中q00q01q02.1Q=1q10一q11q12.q20.q21.-q22.p00P01p02.P=P10p20.P11P21.P12p22.这样，连续时间马尔可夫链的转移概率的求解问题就是矩阵微分方程的求解问题，其转移概率由其转移速率矩阵Q决定.特别地，若Q是一个有限维矩阵，则(5.10)和(5.11)的解为P二eQ；皿Ij!定理5.6.齐次马尔可夫过程在t时刻处于状态jI的

18、绝对概率pj(t)满足下列方程：Pj(t)=一Pj(t)qjj八Pk(t)qkj.(5.12)y证明由定理5.2，有Pj(t)=£PiPij(t)til将向前方程(5.9)式两边乘以Pn并对i求和得'PiPij(t)八(-RPj(t)qjj),二.二PiPik(t)qkj.iEliEli三1k刁故Pj(t)=-Pj(t)qjj八Pk(t)q.k=与离散马尔可夫链类似，我们讨论转移概率Pij(t)当tTS时的极限分布与平稳分布的有限性质.定义5.4设Pj(t)为连续时间马尔可夫链的转移概率，若存在时刻ti,t2，使得Pij(ti)0,Pij(t2)0,则称状态i和j是互通的.若

19、所有状态都是互通的，则称此马尔可夫链为不可约的.定理5.7设连续时间的马尔可夫是不可约的，则有下列性质：(1)若它是正常返的，则极限limcPij。)存在且等于J>0,产I.这里%>0,j=I.是方程组jqjj="-kqkj,j=1k；jj-I(5.13)的唯一非负解.此时称nja0,jwI.是该过程的平稳分布，并且有iim；：Pj(t)=、.(2)若它是零常返的或非常返的，则limt：Pij(t)=limt"Pj(t)=0,i,jI.在实际问题中，有些问题可以用柯尔莫哥洛夫方程直接求解，有些问题虽然不能求解但是可以用方程(5.13)求解.例5.2考虑两个状态的

20、连续时间马尔可夫链，在转移到状态1之前链在状态0停留的时间是参数为九的指数变量，而在回到状态0之前它停留在状态1的时问是参数为N的指数变量，显然该链是一个齐次马尔可夫过程，其状态转移概率为P01(h)=ho(h),P10(h)=ho(h),由定理5.3知1-p0°(h)p01(h)q00-11mh)0'_11mh_0'hhd-小_a一一Poi(h)h=0-九一q。”dhq11=1imhqP1o(h)P10(h)h=0=q=q10,dh由柯尔莫哥洛夫向前方程得到Poo(t)-P01(t)-P00(t)=-(''-：!,-)P00(t),其中最后一个等式来

21、自P01(t)=1-Poo(t).因为Poo(0)=1,由常数变易法得c/*、J,_"JtPoo(t)-.-.e类似地由向前方程P01(t)=Moo(t)一与01。)可解得P0i(t)=-0-ye,由对称性知即二%J0e,'J,Pi0(t)=。-0e,“转移概率的极限为limt,二P00(t)=.二0=limt-R0(t),limtp°i(t)=0=limt,二Pii(t),由此可见，当ttg时，pij(t)的极限存在且与i无关.定理5.6知，平稳分布为：:0二0J-i='0若取初始分布为平稳分布，即PX(0)=0=p。=%,PX(0)=i=pi0,则过程在

22、时刻t的绝对概率分布为pO(t)=p0P00(t)pipi°(t)=0”“°0i-e<7t=0Pi(t)=P0P0i(t)PiPi0(t)=%0i-e，7t'0'0(=?.例5.3机器维修问题.设例5.2中状态0代表某机器正常工作状态i代表机器出故障.状态转移概率与例5.2相同，即在h时间内，机器从正常工作变为出故障的概率为P0i(h)=*h+o(h),在h时间内，机器从有故障变为经修复后正常工作的概率为pi0(h)=。+o(h),试求在t=0时正常工作的机器，在t=5时为正常工作的概率.解由例5.2已求得该过程的Q矩阵为(-九九、Q=J根据题意，要求

23、机器最后所处的状态为正常工作，只需计算P00(t)即可.由例5.2知p00(t)='0''0e"小，10=-,-0=-,九十廿九十廿故P00(5)=0'0eT75,因为PX(0)=0=i=P0,所以PX(5)=0=po(5)=PoP00(5)=P006)=%oe''"5.5.3生灭过程连续时间马尔可夫链的一类重要特殊情形是生灭过程，它的特征是在很短的时问内，系统的状态只能从状态i转移到状态i-1或i+1或保持不变，确切定义如下.定义5.5设齐次马尔可夫过程X(t),t之0的状态空间为I=0,1,2，转移概率为Pj(t),如果P

24、i,i1(h)='3ho(h),i0,Pi,ii(h)-'ho(h),40,J0-0,Pi,i(h)=1-(i)ho(h),Pi,j(h)=o(h),i-j|>2,则称X(t),tA0为生灭过程，%为出生率，均为死亡率.若儿=i1,心=W,(九下是正常数)，则称X(t),t之0为线性生灭过程.若斗三0,则称X(t),t之0为纯生过程.若九i三0,则称X(t),t之0为纯灭过程.生灭过程可作如下概率解释：若以X(t)表示一个生物群体在t时刻的大小，则在很短的时间h内(不计高阶无穷小)，群体变化有三种可能，状态由i变到i+1,即增加一个个体，其概率为h;.状态由i变到i-1,即减少一个个体，.其概率为h;群体大小保持不变，其概率