随机过程Ch5连续时间马尔可夫链.ppt

第五章连续时间马尔可夫链,I马尔可夫链,54321012345T,5.1连续时间马尔可夫链,定义5.1设随机过程X(t)，t0，状态空间I=0,1,2,，若对任意0t1t2tn+1及非负整数i1,i2,in+1，有PX(tn+1)=in+1|X(t1)=i1,X(t2)=i2,X(tn)=in=PX(tn+1)=in+1|X(tn)=in，则称X(t)，t0为连续时间马尔可夫链。转移概率：在s时刻处于状态i，经过时间t后转移到状态j的概率pij(s,t)=PX(s+t)=j|X(s)=i,5.1连续时间马尔可夫链,定义5.2齐次转移概率pij(s,t)=pij(t)(与起始时刻s无关，只与时间间隔t有关)转移概率矩阵P(t)=(pij(t)，i,jI，t0性质：若i为过程在状态转移之前停留在状态i的时间，则对s,t0有(1)(2)i服从指数分布,5.1连续时间马尔可夫链,s,s+t,0,i,i,i,i,t,i,证(1)事实上,5.1连续时间马尔可夫链,5.1连续时间马尔可夫链,(2)设i的分布函数为F(x),(x0),则生存函数G(x)=1-F(x)由此可推出G(x)为指数函数，G(x)=e-x,则F(x)=1-G(x)=1-e-x为指数分布函数。,5.1连续时间马尔可夫链,过程在状态转移之前处于状态i的时间i服从指数分布(1)当i=时，状态i的停留时间i超过x的概率为0，则称状态i为瞬时状态；(2)当i=0时，状态i的停留时间i超过x的概率为1，则称状态i为吸收状态。,5.1连续时间马尔可夫链,定理5.1齐次马尔可夫过程的转移概率具有下列性质：(1)pij(t)0;(2)(3)证由概率的定义，(1)(2)显然成立，下证(3),5.1连续时间马尔可夫链,5.1连续时间马尔可夫链,注：此为转移概率的正则性条件。,5.1连续时间马尔可夫链,定义5.3(1)初始概率(2)绝对概率(3)初始分布(4)绝对分布定理5.2齐次马尔可夫过程的绝对概率及有限维概率分布具有下列性质：,5.1连续时间马尔可夫链,(1)pj(t)0(2)(3)(4)(5),5.1连续时间马尔可夫链,例5.1证明泊松过程X(t),t0为连续时间齐次马尔可夫链。证先证泊松过程的马尔可夫性。泊松过程是独立增量过程，且X(0)=0，对任意0t1t2tn0，则称状态i与j是互通的。若所有状态都是互通的，则称此马尔可夫链为不可约的。可定义状态的常返性,5.2柯尔莫哥洛夫微分方程,例5.2设两个状态的连续时间马尔可夫链，状态转移概率满足，试讨论平稳分布。,5.2柯尔莫哥洛夫微分方程,5.2柯尔莫哥洛夫微分方程,5.2柯尔莫哥洛夫微分方程,转移概率为,5.2柯尔莫哥洛夫微分方程,转移概率的极限为平稳分布为,5.2柯尔莫哥洛夫微分方程,若取初始分布为平稳分布，即则过程在时刻t的绝对概率分布为,5.2柯尔莫哥洛夫微分方程,5.2柯尔莫哥洛夫微分方程,定理5.7设连续时间马尔可夫链是不可约的，则有下列性质：(1)若它是正常返的，则极限存在且等于j0，jI。这里j是的唯一非负解，此时称j0，jI是该过程的平稳分布，并且有(2)若它是零常返的或非常返的，则,例如上例中马氏链有两个状态I=0,1，那么,生灭过程,设某系统具有状态集S=0,1,2,或S=0,1,2,k,N(t)表示系统在时刻t(t=0)的状态。若在N(t)=n的条件下，随机过程N(t),t=0满足以下条件:(1)N(t+t)转移到“n+1”的概率为Pn,n+1(t)=nt;(2)N(t+t)转移到“n-1”的概率为Pn,n-1(t)=nt);(3)N(t+t)转移到其他状态“S-n+1,n-1”的概率为o(t)(高阶无穷小);则称随机过程N(t),t=0为生灭过程。,生灭过程状态变化的性质,(1)在无穷小t内,系统或生长1个;或灭亡1个;或既不生长又不灭亡（概率:1-n(t)-n(t)）;(2)系统生长一个的概率n(t)与t有关，而与t无关;与系统当前状态n有关，而与以前的状态无关；(3)系统灭亡一个的概率n(t)与t有关，而与t无关;与系统当前状态n有关，而与以前的状态无关；,马尔可夫性质,若排队系统具有下列性质:(1)顾客到达为泊松流，时间间隔服从参数为n的负指数分布;(2)顾客服务时间服从参数为n的负指数分布;则排队系统的随机过程N(t),t=0具有马尔可夫性质,为一个生灭过程.,排队系统,(四)排队系统状态转移图,三、排队系统稳态概率Pn的求解,第五章连续时间的马尔可夫链,第四章讨论了时间与状态都是离散的最简单的马尔可夫过程,第五章介绍另一类应用广泛的特殊类型的马尔可夫链,即时间连续状态离散的马尔可夫过程.5.1连续时间的马尔可夫链考虑取非负整数值的连续时间随机过程X(t),t0.定义5.1若随机过程X(t),t0,状态空间I=in,n0,对任意0t1t2tn+1及i1,i2,in+1I,有PX(tn+1)=in+1|X(t1)=i1,X(t2)=i2,X(tn)=in=PX(tn+1)=in+1|X(tn)=in(),则称X(t),t0为连续时间马尔可夫链.由定义知,连续时间马尔可夫链是具有马尔可夫性的随机过程.,连续时间的马尔可夫链,一般,记条件概率()式为:PX(s+t)=j|X(s)=i=pij(s,t)().表示系统在时刻s处于状态i,经过时间t后转移到状态j的转移概率.定义5.2如果()式的转移概率与s无关,则称连续时间马尔可夫链具有齐次(平稳)的转移概率.此时简记其转移概率为pij(s,t)=pij(t),转移概率矩阵为:P(t)=(pij(t),(i,jI,t0).一般,简称具有齐次转移概率的连续时间马尔可夫链为齐次马尔可夫过程.在以下的讨论中,均假定所考虑的都是齐次马尔可夫过程.如果在某时刻,譬如时刻0,马尔可夫链进入状态i,而在,连续时间的马尔可夫链,接下来的s个单位时间中过程并未离开状态i(即未发生转移),问:在随后的t个单位时间中过程仍不离开状态i的概率是多少呢?由马尔可夫性,过程在时刻s处于状态i的条件下,在区间s,s+t中仍然处于状态i的概率正是它处于状态i至少t个单位时间的(无条件)概率.若记i为过程在转移到另一状态之前,停留在状态i的时间,则对一切s,t0有:Pis+t|is=Pit.可见,随机变量i具有无记忆性,它服从指数分布.于是:一个连续时间马尔可夫链,每当它进入状态i,就具有性质(连续时间马尔可夫链的特征性质):,连续时间的马尔可夫链,(1)在转移到另一状态之前处于状态i的时间,服从参数为vi的指数分布:(2)当过程离开状态i时,接着以概率pij进入状态j,且有pij=1.以上两条性质,是构造连续时间马尔可夫链的一个方法.如果vi=,则称状态i为瞬时状态,在这种情况,过程一旦进入此状态立即就离开;如果vi=0,则称状态i为吸收状态,在这种情况,过程一旦进入此状态就永远不再离开.瞬时状态只是一种理论状态,在后文的讨论中我们总假设0vi.于是,一个连续时间马尔可夫链是这样的随机过程,它按照一个离散时间的马尔可夫链从一个状态转,f(x)=(vi0),连续时间的马尔可夫链,移到另一个状态,但在转移到下一个状态之前,它在各个状态停留的时间服从指数分布.而且,在状态i过程停留的时间与下一个到达的状态必须是相互独立的随机变量(因为若下一个到达的状态依赖于i,那么过程处于状态i已有多久的信息与下一个状态的预报有关,这与马尔可夫性矛盾).定理5.1齐次马尔可夫过程的转移概率具有下列性质:(1)pij(t)0;(2)pij(t)=1;(3)pij(t+s)=pik(t)pkj(s).其中(3)式,即是连续时间齐次马尔可夫链的C-K方程.,连续时间的马尔可夫链,证明:(1)与(2)式由概率定义以及pij(t)的定义显然可得.下证(3)式.由全概率公式和马尔可夫性得:pij(t+s)=PX(t+s)=j|X(0)=i=PX(t+s)=j,X(t)=k|X(0)=i=PX(t)=k|X(0)=iPX(t+s)=j|X(t)=k=PX(t)=k|X(0)=iPX(s)=j|X(t)=k=pik(t)pkj(s).对于转移概率pij(t),一般还假定它满足:limpij(t)=并称之为正则性条件.,t0,连续时间的马尔可夫链,正则性条件说明,过程刚进入某状态不可能立即又跳跃到另一状态.这正好说明一个物理系统要在有限时间内发生无限此跳跃、从而消耗无穷多的能量这是不可能的.定义5.3对于任一t0,记pj(t)=PX(t)=j,pj=pj(0)=PX(0)=j,jI并分别称pj(t),jI和pj,jI为齐次马尔可夫过程的绝对概率分布和初始概率分布.定理5.2齐次马尔可夫过程的绝对概率及有限维概率分布具有以下性质:(1)pj(t)0;(2)pj(t)=1;,连续时间的马尔可夫链,(3)pj(t)=pipij(t);(4)pj(t+)=pi(t)pij();(5)PX(t1)=i1,X(tn)=in=.例5.1证明泊松过程X(t),t0为连续时间齐次马尔可夫链.证明:先证泊松过程具有马尔可夫性,再证齐次性.由泊松过程的定义知它是独立增量过程,且X(0)=0.对任意0t1t2tntn+1,有PX(tn+1)=in+1|X(t1)=i1,X(tn)=in,连续时间的马尔可夫链,=PX(tn+1)-X(tn)=in+1-in|X(t1)-X(0)=i1,X(t2)-X(t1)=i2-i1,X(tn)-X(tn-1)=in-in-1=PX(tn+1)-X(tn)=in+1-in;另一方面,由于PX(tn+1)=in+1|X(tn)=in=PX(tn+1)-X(tn)=in+1-in|X(tn)-X(0)=in=PX(tn+1)-X(tn)=in+1-in.所以PX(tn+1)=in+1|X(t1)=i1,X(tn)=in=PX(tn+1)=in+1|X(tn)=in,即泊松过程是一个连续时间马尔可夫链.下证齐次性.当ji时,由泊松过程的定义,得,连续时间的马尔可夫链,PX(s+t)=j|X(s)=i=PX(s+t)-X(s)=j-i=e-t.当ji时,由于过程的增量只取非负整数值,此时pij(s,t)=0.因而pij(s,t)=pij(t)=即转移概率只与t有关,泊松过程具有齐次性.下文讨论连续时间齐次马尔可夫链的转移概率pij(t)的求解方法.,柯尔莫哥洛夫微分方程,5.2柯尔莫哥洛夫微分方程对于离散时间齐次马尔可夫链,如果已知其一步转移概率矩阵P=(pij),则k步转移概率矩阵由一步转移概率矩阵的k次方即可求得.但是,对于连续时间齐次马尔可夫链,转移概率pij(t)的求解一般较为复杂.下面首先讨论pij(t)的可微性及pij(t)所满足的柯尔莫哥洛夫微分方程;然后给出pij(t)的一种求解方法.引理5.1设齐次马尔可夫过程满足正则条件,则对于任意固定i,jI,pij(t)是t的一致连续函数.证明:设h0,由定理5.1得pij(t+h)-pij(t)=pir(h)prj(t)-pij(t),柯尔莫哥洛夫微分方程,=pii(h)pij(t)-pij(t)+pir(h)prj(t)=-1-pii(h)pij(t)+pir(h)prj(t).故有pij(t+h)-pij(t)-1-pii(h)pij(t)-1-pii(h),pij(t+h)-pij(t)pir(h)prj(t)pir(h)=1-pii(h),因此有|pij(t+h)-pij(t)|1-pii(h).对于h0,同样有pij(t)-pij(t+h)=pir(-h)prj(t+h)-pij(t+h)=pii(-h)pij(t+h)-pij(t+h)+pir(-h)prj(t+h)=-1-pii(-h)pij(t+h)+pir(-h)prj(t+h).,柯尔莫哥洛夫微分方程,故有pij(t)-pij(t+h)-1-pii(-h)pij(t+h)-1-pii(-h),pij(t)-pij(t+h)pir(-h)prj(t+h)pir(-h)=1-pii(-h),因此有|pij(t)-pij(t+h)|1-pii(-h).综上所述,一般地有|pij(t+h)-pij(t)|1-pii(|h|).由正则性条件知lim|pij(t+h)-pij(t)|=0.即pij(t)关于t是一致连续的.,h0,柯尔莫哥洛夫微分方程,在以下讨论中,我们恒假定齐次马尔可夫过程满足正则性条件.定理5.3设pij(t)是齐次马尔可夫过程的转移概率,则下列极限存在:(1)lim=vi=qii(i=j);(2)lim=qij,ij.一般称定理中的qij为齐次马尔可夫过程从状态i到状态j的转移概率(或跳跃强度).定理中极限的概率意义是:在长为t的时间区间内,过程从状态i转移到另一其它状态的转移概率1-pii(t),等于qijt加上一个比t,t0,t0,柯尔莫哥洛夫微分方程,高阶的无穷小量;而从状态i转移到状态j的概率pij(t)等于qijt加上一个比t高阶的无穷小量.推论对有限齐次马尔可夫过程,有qii=qij.证明:由定理5.1,有pij(t)=1,即1-pii(t)=pij(t).由于求和是在有限集中进行,故有lim=lim=qij,即:qii=qij().对于状态空间无限的马尔可夫过程,一般只有qiiqij.,t0,t0,柯尔莫哥洛夫微分方程,若连续时间齐次马尔可夫链,具有有限状态空间I=0,1,n,则它的转移速率可构成下述形式的矩阵:由()式知,Q的每一行元素的和都为0,因而对角线元素为负或0,且当ij时,qij0.利用Q矩阵,可推出任意时间间隔t的转移概率所满足的方程组,从而可以求解转移概率.由C-K方程,有pij(t+h)=pik(h)pkj(t).等价地,有,Q=,-q00q01q0nq10-q11q1nqn0qn1-qnn,柯尔莫哥洛夫微分方程,pij(t+h)-pij(t)=pik(h)pkj(t)-1-pii(h)pij(t).两边除以h并令h0取极限,由定理5.3,得lim=limpkj(t)-qiipkj(t).如果在上式的右边极限与求和可交换次序,那么运用定理5.3,就有以下结论:定理5.4(柯尔莫哥洛夫向后方程)设qij=qii,则对一切i,j以及t0,有pij(t)=qikpkj(t)-qiipkj(t).证明:这其实只需证明式右边极限与求和可交换次序.对任意固定的N,有liminfpkj(t)liminfpkj(t),h0,h0,h0,h0,柯尔莫哥洛夫微分方程,=qikpkj(t).鉴于该式对一切N都成立,故有liminfpkj(t)qikpkj(t)().下面来倒转这一不等式.注意到对Ni,由pkj(t)1知limsuppkj(t)limsuppkj(t)+limsuppkj(t)+-=qikpkj(t)+qii-qik.最后的等式由定理5.3获得.因上述不等式对一切Ni,h0,h0,h0,柯尔莫哥洛夫微分方程,成立,令N且由qij=qii,便得limsuppkj(t)qikpkj(t).由此式与()式即得limpkj(t)=qikpkj(t).定理5.4中pij(t)满足的微分方程组,以柯尔莫哥洛夫向后方程所著称.所以称它们为向后方程,是因为在计算时刻t+h的状态的概率分布时,需要对退后到时刻h的状态取条件,即要从pij(t+h)=PX(t+h)=j|X(0)=i,X(h)=kPX(h)=k|X(0)=i=pkj(t)pik(h)开始计算.,h,h,柯尔莫哥洛夫微分方程,对时刻t的状态取条件,可以导出另一组方程,称柯尔莫哥洛夫向前方程:pij(t+h)=pik(t)pkj(h),或pij(t+h)-pij(t)=pik(t)pkj(h)-pij(t)=pik(t)pkj(h)-1-pjj(h)pij(t),所以lim=limpik(t)-pij(t).如果在上式的右边极限与求和可交换次序,则由定理5.3即得pij(t)=pik(t)qkj-qijpij(t).,h0,h0,柯尔莫哥洛夫微分方程,令人遗憾的是:前式右边极限与求和的次序交换并不恒成立.不过在大多数模型中-包括全部生灭过程和全部有限状态的模型,是成立的.定理5.5(柯尔莫哥洛夫向前方程)在适当的正则条件下pij(t)=pik(t)qkj-qijpij(t).利用定理5.4和定理5.5中的方程组以及初始条件pii(0)=1,pij(0)=0,ij.便可解得pij(t).柯尔莫哥洛夫向后方程和向前方程虽然形式不同,但它们所求得的pij(t)是相同的.在实际应用中,当固定回后所处状态j,研究pij(t)时(i=0,1,),采用向后方程较方便;当固定状态i,研究pij(t),柯尔莫哥洛夫微分方程,时(j=0,1,),则采用向前方程比较方便.向后方程和向前方程可以写成矩阵形式:p(t)=QP(t);p(t)=P(t)Q.式中矩阵p(t)的元素是矩阵p(t)的元素的导数,这,-q00q01q02q10-q11q12q20q21-q22,Q=,P(t)=,p00(t)p01(t)p02(t)p10(t)p11(t)p12(t)p20(t)p21(t)p22(t),柯尔莫哥洛夫微分方程,这样,连续时间马尔可夫链的转移概率的求解问题就化成矩阵微分方程的求解问题,其转移概率由其转移速率矩阵Q决定.特别,如果Q是一个有限维矩阵,则向后方程和向前方程矩阵形式的解为:p(t)=eQt=.定理5.6齐次马尔可夫过程在t时刻处于状态jI的绝对概率pj(t)满足下列方程pj(t)=-pj(t)qjj+pk(t)qkj.证明:由定理5.2,有pj(t)=pipij(t),柯尔莫哥洛夫微分方程,将定理5.5中向前方程式的两边同乘以pi,并对i求和,得pipij(t)=(-pipij(t)qjj)+pipik(t)qkj,故有pj(t)=-pj(t)qjj+pk(t)qkj.与离散马尔可夫链类似,以下讨论转移概率pij(t)当t时的极限分布与平稳分布的有关性质.定义5.4设pij(t)为连续时间马尔可夫链的转移概率,若存在时刻t1和t2,使得pij(t1)0,pji(t2)0,则称状态i与j是互通的.若所有状态都是互通的,则称此马尔可夫链为不可约的.关于状态的常返性及非常返性等概念与离散马尔可夫链类似,此处不再一一定义.,柯尔莫哥洛夫微分方程,下面定理(不加证明)给出:转移概率pij(t)在t时的性质及其与平稳分布的关系.定理5.7设连续时间的马尔可夫链是不可约的,则该链具有下列性质:(1)若它是正常返的,则极限limpij(t)存在且等于j(0),jI.这里j是方程组jqjj=kqkj,j=1的惟一非负解.此时称j,jI为该过程的平稳分布并且有limpj(t)=j.(2)若它是零常返的或非常返的,则,t,t,柯尔莫哥洛夫微分方程,limpij(t)=limpj(t)=0,i,jI.在实际应用中,有些问题可以用柯尔莫哥洛夫方程直接求解,有些问题虽不能直接求解,但可以用定理5.7(1)中方程求解.以下讨论几个在应用中有一定代表性的例题.例5.2考虑两个状态的连续时间马尔可夫链,在转移状态1之前链在状态0停留的时间是参数为的指数变量,而在回到状态0之前,它停留在状态1的时间是参数为的指数变量.显然,该链是一个齐次马尔可夫过程,其状态转移概率为:p01(h)=h+o(h),p10(h0=h=o(h).,t,t,柯尔莫哥洛夫微分方程,由定理5.3知q00=lim=lim=p01(h)|h=0=q01,q11=lim=lim=p10(h)|h=0=q10.由柯尔莫哥洛夫向前方程得p00(t)=p01(t)-p00(t)=-(+)p00(t)+.其中最后一个等式来自p01(t)=1-p00(t).因而e(+)tp00(t)+(+)p00(t)=e(+)t,或e(+)tp00(t)=e(+)t,于是e(+)tp00(t)=e(+)t+c.,h0,h0,h0,h0,柯尔莫哥洛夫微分方程,由于p00(0)=1,可见c=,于是p00(t)=+e-(+)t.若记0=,0=,则p00(t)=0+0e-(+)t.类似地,由向前方程p01(t)=p00(t)-p01(t)可解得:p01(t)=01-e-(+)t.再由对称性知:p11(t)=0+0e-(+)t,p10(t)=01-e-(+)t.转移概率的极限:limp00(t)=0=limp10(t),t,t,柯尔莫哥洛夫微分方程,limp11(t)=0=limp01(t).由此可见,当t时,pij(t)的极限存在且与i无关.由定理5.7知,平稳分布为:0=0,1=0.如果取初始分布为平稳分布,即PX(0)=0=p0=0,PX(0)=1=p1=0.则过程在时刻t的绝对概率分布为:p0(t)=p0p00(t)+p1p11(t)=00e-(+)t+0+001-e-(+)t=0,p1(t)=p0p01(t)+0p11(t)=001-e-(+)t+00+0e-(+)t=0.,t,t,柯尔莫哥洛夫微分方程,例5.3机器维修问题.假定例5.2中状态0代表某机器正常工作,状态1代表机器出故障.状态转移概率与例5.2相同,即在h时间内,机器从正常工作变为出故障的概率为p01(h)=h+o(h);在h时间内,机器从有故障变为经修复后正常工作的概率为p10(h)=h+o(h).试求在t=0时正常工作的机器,在t=5时正常工作的概率.解:由例5.2已经求得该过程的Q矩阵是:Q=.根据题意,要求的是机器最后所处的状态为正常工作,只需计算p00(t).由例2知:p00(t)=0+0e-(+)t.故p00(5)=0+0e-5(+).因为PX(0)=0=p0=1,所以PX(5)=0=p0(5)=p0p00(5)=0+0e-5(+).,-,生灭过程,连续时间马尔可夫链的一类重要的特殊情形是生灭过程,它的特征是在很短的时间内,系统的状态只能从状态i转移到状态i-1或i+1或保持不变.其确切定义是:定义5.5设齐次马尔可夫X(t),t0的状态空间是I=0,1,2,转移概率为pij(t),如果pi,i+1(h)=ih+o(h),i0,pi,i-1(h)=ih+o(h),i0,0=0,pii(h)=1-(i+i)h+o(h),pij(h)=o(h),|i-j|2则称X(t),t0为生灭过程.i为出生率,i为死亡率.若i=i,i=i(,正常数),则称X(t),t0,生灭过程,为线性生灭过程.若i0,则称X(t),t0为纯生过程;若i0,则称X(t),t0为纯灭过程.生灭过程的概率解释:如果以X(t)表示一个生物群体在t时刻的大小,则在很短的时间h内(不计高阶无穷小o(h),群体变化有三种可能:状态由i变到i+1,即增加一个个体,其概率为ih;状态由i变到i-1,机5减少一个个体,其概率为ih;群体大小不增不减,其概率为1-(i+i)h.柯尔莫哥洛夫向前方程与向后方程.由定理5.3,得qii=-pii(h)|h=0=i+i,i0.,生灭过程,qij=pij(h)|h=0=qij=0,|i-j|2.故柯尔莫哥洛夫向前方程为pij=j-1pi,j-1(t)-(j+j)pij(t)+jpi,j+1(t),i,jI.柯尔莫哥洛夫向后方程为pij=ipi-1,j(t)-(i+i)pij(t)+ipi+1,j(t),i,jI.由于上述柯尔莫哥洛夫向前、向后方程组求解较为困难,我们转而讨论其平稳分布.由定理5.7(1)式,有,i,j=i+1,i0,i,j=i-1,i0.,生灭过程,00=11,(j+j)j=j-1j-1+j+1j+1,j1.逐步递推,得1=0,2=1=0,j=j-1=0,.再利用j=1,得平稳分布():0=(1+)-1,j=(1+)-1,j0.该式也指出,平稳分布存在的充要条件是:.,生灭过程,例5.4两个生灭过程.(1)M/M/s排队系统.假设顾客按照参数为的泊松过程来到一个有s个服务员的服务站,即相继来到之间的时间是均值均为1/的独立指数随机变量,每一个顾客一来到,如果有服务员空闲,则直接进行服务,否则此顾客要加入排队行列在队列中等待.当一个服务员结束对一位顾客的服务时,顾客就离开服务系统,排队的下一个顾客(如有顾客等待)进入服务.假定相继的服务时间是独立的指数随机变量,均值为1/.如果以X(t)记时刻t系统中的人数,则X(t),t0是生灭过程:n=n=,n0.,n,1ns,s,sn,生灭过程,M/M/s排队系统中的M表示马尔可夫过程,s代表s个服务员(一般,A/B/C:A为顾客到达间隔时间分布;B为服务时间的分布;C为服务站内服务台个数).特别,在M/M/1排队系统中,n=,n=.于是若/1,则由平稳分布()式,得n=()n(1-),n0.要平稳分布(即极限分布)存在,必须小于是直观的.顾客按速率到来且以速率受到服务,因而当时顾客到来的速率高于接受服务的速率,排队的长度趋于无穷.=时的情况,类似于对称的随机游动,它是零常返的,从而没有极限概率.,生灭过程,(2)有迁入的线性增长模型模型:n=n,n1,n=n+,n0.称为有迁入的线性增长模型.这种过程来自于对生物繁殖与群体增长的研究.假定群体中的每个个体以指数率出生;而且由于从外界迁入的因素,群体又以指数率增加,因此当系统中有n个成员时,整个出生率是n+.假定该群体的各个成员以指数率死亡,从而n=n.例5.5尤尔(Yule)过程设群体中各个成员独立地活动且以指数率生育.如果假设没有任何成员死亡,以X(t)记时刻t群体的总量,则X(t)是一个纯生过程:n=n,n0并称之为尤尔过程.试计,生灭过程,算:(1)从一个个体开始,在时刻t群体总量的分布;(2)从一个个体开始,在时刻t群体诸成员年龄之和的均值.解:(1)记Ti(i1)为第i个与第i+1个成员出生之间的时间,即Ti是群体总量从i变到i+1所花的时间.由尤尔过程的定义可见Ti(i1)是独立的具有参数i的指数变量.故有PT1t=1-e-t,PT1+T2t=PT1+T2t|T1=xe-xdx=(1-e-2(t-x)e-xdx=(1-e-t)2.及PT1+T2+T3t=PT1+T2+T3t|T1+T2=xd,生灭过程,=(1-e-3(t-x)(1-e-t)2e-xdx=(1-e-t)3.一般地,由归纳法可得:PT1+T2+Tjt=(1-e-t)j.由于PT1+T2+Tjt=PX(t)j+1|X(0)=1,所以p1j(t)=(1-e-t)j-1-(1-e-t)j=e-t(1-e-t)j-1,j1.由此可见,从一个个体开始,在时刻t群体的总量具有几何分布,其均值为et.一般,如果群体从i个个体开始,在时刻t群体总量是i个独立同几何分布随机变量之和,则具有负二项分布,即pij(t)=e-it(1-e-t)j-i,ji1.(2)记A(t)为群体在时刻t诸成员的年龄之和,则可以,生灭过程,证明,A(t)=a0+X(s)ds,式中a0是初始个体在t=0时的年龄.取期望有EA(t)=a0+EX(s)ds=a0+EX(s)ds=a0+esds=a0+.例5.6传染模型考虑有m个个体的群体,在时刻0由一个已感染的个体与m-1个未受到感染但可能被感染的个体组成.个体一旦受到感染将永远地处于此状态.假设在任意长为h的时间区间内任意一个已感染的人将以概率ah+o(h)引起任一指定的未感染者成为感染者.若以X(t)记时刻t群体中已受感染的个体数,则X(t),t0是一纯生过程,其,生灭过程,n=这是因为,当有n个已受感染的个体时则m-n个未受感染者的每一个将以速率na变成已感染者.记T为直至整个群体被感染的时间,Ti为从i个已感染者到i+1个已感染者的时间,则T=Ti.由于Ti是相互独立的指数随机变量,其参数分别为i=(m-i)ia,i=1,2,m-1.故ET=ETi=,DT=DTi=.,(m-n)na,n=1,2,m-1,0,其它.,生灭过程,对规模合理的群体,ET渐进地为ET=(+)(+)dt=.例5.7机器维修设有m台机床,s个维修工人(sm).机床或者工作,或者损坏等待修理.机床损坏后,空着的维修工人立即来修理;若维修工人不空,则机床按先后排队等待维修.假定在h时间内,每台机床从工作到损坏的概率为h+o(h),每台修理的机床转到工作的概率为h+o(h).用X(t)表示时刻t损坏的机床台数,则x(t),t0是马尔可夫链,其状态空间I=0,1,m.设时刻t有i台机床损坏,则在(t,t+h)内又有一台机床损坏的概率,在不计高阶无穷小,生灭过程,时,它应等于原来正在工作的m-i台机床中,在(t,t+h)内恰有一台损坏的概率.于是pi,i+1(h)=(m-i)h+o(h),i=0,1,m-1.类似地,有pi,i-1(h)=,pij(h)=o(h),|i-j|2.显然,这是一个生灭过程,其i=(m-i),i=0,1,m;i=.由平稳分布()式,得该问题的平稳分布:,ih+o(h),1is,sh+o(h),sim,i,1is,s,sim,生灭过程,0=1+()j+()j-1,()j0,1js,()j0,sjm.当已知m,后,便可由上述平稳分布计算出安排s个维修工人时平均不工作的机床台数.因而也就可以具体计划如何适当安排维修工人的人数s.在第五章,主要讨论了连续时间的马尔可夫链、柯尔莫哥洛夫微分方程以及生灭过程.如何理解其内的一些概念呢?,j=,关于第五章中的几个概念,若连续时间的马尔可夫链以概率1在任意长的时间内转移的次数是有限的,则该马尔可夫链就是正则的.如果齐次马尔可夫过程满足正则性条件,那么对任意固定的i,jI,pij(t)都是t的一致连续函数.pij是齐次马尔可夫过程从状态i到状态j的转移概率,由其极限式得到转移速率qij,这极限式的概率意义是:在长度为t的时间区间内,过程从状态i转移到另一其它状态的转移概率1-pii(t),等于qii(t)加上一个比t高阶的无穷小量;而从状态i转移到状态j的概率pij(t)等于qij(t)加上一个比t高阶的无穷小量.Q矩阵的意义:Q矩阵称为齐次马尔可夫过程的转移速率矩阵.由于Q=P(0),故又称为转移概率矩阵P(t)的密度,关于第五章中的几个概念,矩阵.它反映齐次马尔可夫过程的转移概率(函数)在t=0的变化率.Q矩阵是一个常数矩阵,而转移概率矩阵是一个函数矩阵.Q矩阵比转移概率矩阵容易求得.柯尔莫哥洛夫微分方程的实际意义与限制条件:柯尔莫哥洛夫微分方程建立了齐次马尔可夫过程的Q矩阵与转移概率矩阵P(t)之间的联系.如果给了密度矩阵Q,在一定条件下,可以通过柯尔莫哥洛夫向后(前)方程解出转移概率pij(t).若Q是一个有限维矩阵,则由向后(前)方程可以解得:P(t)=eQt=(Qt)/j!.在柯尔莫哥洛夫微分方程的证明中,需要交换极限与,关于第五章中的几个概念,求和的次序.但是,对向前方程来说,必须附加适当的条件才能实现.这使得方程的应用受到一定的限制.对于只有有限个状态的马尔可夫过程的遍历性,在应用中有一个简便的充分条件判定方法:定理设齐次马氏链Xn,n1的状态空间为I=a1,a2,aN,P是它的一步转移概率矩阵,如果存在正整数m,使对任意的ai,ajI,都有Pij(m)0,i,j=1,2,N,则此链具有遍历性;且具有极限分布=(1,2,N),它是方程组=P,或j=ipij,j=1,2,N的满足条件j0,j=1的惟一解.依照定理,为证有限链是遍历的,只需找一正整数m,使m,关于第五章中的几个概念,步转移概率矩阵Pm无零元即可.生灭过程的概率的意义:由生灭过程的转移概率pij(t)的性质知,若忽略t的高阶无穷小量,生灭过程即种群群体的状态变化有三种可能:(1)由状态ii+1,即增加了一个个体,概率是it;(2)由状态ii-1,即减少了一个个体,概率是it;(3)由ii,即群体个数没有变化.由此可以得出:生灭过程的所有状态都是互通的.但是在充分小的时间区间内,只能在两个相邻状态内变化,或者状态无变化.,