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

1、第五章 连续时间的马尔可夫链5.1 连续时间的马尔可夫链考虑取非负整数值的连续时间随机过程 X(t),t 0.定义5.1 设随机过程 X(t),t 0. ,状态空间 I in,n 0 ,若对任意0 t1 t2 . tn 1及 i1,i2,.in 1 I ,有PX(tn1) in 1X(t1) i1,X(t2) i2,.X(tn) in=PX(tn1) in 1 X(tn) in (5.1)则称X(t),t 0. 为连续时间马尔可夫链 .由定义知 ,连续时间马尔可夫链是具有马尔可夫性的随机过程 ,即过程在已知 现在时刻 tn及一切过去时刻所处状态的条件下 ,将来时刻 tn 1的状态只依赖于现 在

2、状态而与过去无关 .记(5.1)式条件概率一般形式为PX(s t) j X(s) i pij(s,t)(5.2)它表示系统在 s时刻处于状态 i,经过时间 t后转移到状态 j的转移概率 .定义 5.2 若(5.2)式的转移概率与 s 无关 ,则称连续时间马尔可夫链具有平稳的 或齐次的转移概率 ,此时转移概率简记为pij (s,t) pij (t),其转移概率矩阵简记为 P(t) (pij(t),(i, j I,t 0).以下的讨论均假定我们所考虑的连续时间马尔可夫链都具有齐次转移概率.简称为齐次马尔可夫过程 .假设在某时刻 ,比如说时刻 0,马尔可夫链进入状态 i,而且接下来的 s 个单位时间

3、 单位中过程未离开状态 i,(即未发生转移 ),问随后的 t 个单位时间中过程仍不离开 状态 i 的概率是多少呢 ?由马尔可夫我们知道 ,过程在时刻 s 处于状态 i 条件下 ,在 区间s,s+t中仍然处于 i的概率正是它处于 i至少 t个单位的无条件概率 .若记 hi 为记过程在转移到另一个状态之前停留在状态 i 的时间 ,则对一切 s,t 0有Phi s thi s Phi t,可见,随机变量 hi具有无记忆性 ,因此hi服从指数分布 .由此可见,一个连续时间马尔可夫链 ,每当它进入状态 i,具有如下性质 :(1) 在转移到另一状态之前处于状态 i 的时间服从参数为 vi 的指数分布 ;(

4、2) 当过程离开状态 i 时,接着以概率 pij 进行状态 j, pij 1 .ji 上述性质也是我们构造连续时间马尔可夫链的一种方法 .当 vi时 , 称状态 i 为瞬时状态 , 因为过程一旦进入此状态立即就离开 .vi 0 时 ,称状态 i 为吸收状态 ,因为过程一旦进入状态就永远不再离开了 .尽管 瞬时状态在理论上是可能的 ,但以后假设对一切 i, 0 vi.因此 ,实际上一个连续时间的马尔可夫链是一个这样的随机过程 ,它按照一个离散时间的马尔可夫链 从一个状态转移到另一个状态 ,但在转移到下一个状态之前 ,它在各个状态停留的 时间服从指数分布 .此外在状态 i 过程停留的时间与下一个到

5、达的状态必须是相 互独立的随机变量 .因此下一个到达的状态依赖于 hi ,那么过程处于状态 i 已有多 久的信息与一个状态的预报有关 ,这与马尔可夫性的假定相矛盾 .定理 5.1 齐次马尔可夫过程的转移概率具有下列性质 :(1) pij 0;(2)pij 1;jI(3) pij (t s)pik (t)pkj(s).kI其中 (3)式即为连续时间齐次马尔可夫链的切普曼 柯尔哥洛夫方程 .证明 只证 (3).由全概率公式及马尔可夫性可得pij(t s) PX(t s) j X(0) i)= PX(t s) j,X(t) k X(0) ikI= PX(t) kX(0) iPX(t s) j X(t

6、) kkIpik (t)pkj (s).kI对于转移概率 pij (t) ,一般还假定它满足 :1,i jlimt 0 pij(t)(5.3)0,i j.称 (5.3)式为正则条件 .正则条件说明 ,过程刚进入某状态不可能立即又跳跃到另一 状态 .这正好说明一个物理系统要在有限时间内发生限多次跳跃,从而消耗无穷多的能量这是不可能的 .定义 5.3 对于任 一t 0 记pj(t) P X(t) j,pjpj (0) PX(0) j, j I,分别称 p j (t), j I,pj,j I 齐次马尔可夫过程的绝对概率分布和初始概率分 布.(1)pj(t)0,(2)jIpj(t)1,(3)pj(t)

7、iIpi pij (t);(4)pj(th)pi(t)pij (h);iI(5)p X (t1 ) i1,., X (t n ) inpi pii1 pi1i2 (t2 t1 ).pin 1in (tn tn 1).定理 5.2 齐次马尔可夫过程的绝对概率及有限维概率分布具有下列性质 :iI例 5.1试证明泊松过程 X(t),t 0 为连续时间齐次马尔可夫链 .证明 先证泊松过程具有马尔可夫性 ,再证明齐次性 .由泊松过程的定义 它是独立增量过程 ,且X(0)=0. 0 t1,. tn tn 1, 有PX(tn 1) in 1 X(t1) i1,.,X(tn) in= PX(tn1) X(tn

8、) in1 in X(t1) X(0) i1,.=X(t2) X(t1) i2 i1,.X (t n ) X(tn 1) in in1,= PX(tn 1) X(tn) in1 in .另一方面 ,因为PX(tn 1) in1 X(tn) in=PX(tn1) X(tn) in 1 in X(tn) X(0) in=PX(tn1) X(tn) in 1 in所以P X (tn 1) in1X(t1) i1,.,X(tn) in=PX(tn 1) in1 X(tn) in. 即泊松过程是一个连续时间马尔可夫过程 .以下证明齐次性 .当 j i 时 ,由泊松过程的定义=et ( t)j i(j i

9、)!j<i.时,由于过程的增量只取非负整数 ,故 pij(s,t) 0,所以pij (s,t) pij (t)e t (jt)ji)i!, j ( j i)!0, j i即转移概率只与 t 有关 ,泊松过程具有齐次性 .5.2 柯尔莫哥洛夫微分方程对于连续时间齐次马尔可夫链转移概率 pij (t) 的求解一般比较复杂 .下面首先讨论 pij (t) 的可微性及 pij(t) 满足的柯尔莫哥洛夫微分程引理 5.1 设齐次马尔可夫过程满足正则性条件 (5.3),则对于任意固定的 i, j I,pij(t)是t 的一致连续函数 .证明 设 h>0,由定理 5.1 得pij (t h) p

10、ij (t)pir (h)prj (t) pij (t)rIpir (h)prj(t) pii(h)pij(t) pij (t) ripir (h)prj (t) 1 pii (h)pij (t) ri故有 pij (t h) pij (t)1pii (h) pij (t)1 pii (h),pij (t h) pij (t)ripir (h)prj (t)rpir (h) 1 pii (h) i因此pij (t h) pij (t)1pii (h).对于 h<0,同样有 pij (th)pij (t) 1 pii( h).综上所述得到pij (t h) pij (t)1pii(h).由

11、正则性条件知limh 0 pij (t h) pij (t) 0,即 pij (t) 关于 t 是一 致连续的 .以下我们恒设齐次马尔可夫过程满足正则性条件 (5.3)式. 定理 5.3 设 pij (t) 是齐次马尔可夫过程的转移概率 ,则下列极限存在(1)limt01 pii ( t)viqii(2)limpij ( t)t0qij我们称qij为齐次马尔可夫过程从状态 i到状态 j的转移概率或跳跃强度 .定理中 的极限的概率意义为 :在长为 t 的时间区间内 ,过程从状态 i 转移到另一其他状态 的转移概率为 1 pii( t)等于qii t 加一个比 t高阶的无穷小量 ,而过程从状态 i

12、转移到状态 j 的转移概率为 pij( t)等于 qijt 加一个比t 高阶的无穷小量 .推论 对有限齐次马尔可夫过程 qiiqijji 证明 由定理 5.1 ,有,有pij ( t) 1,1 pii ( t) jIpij ( jit)由于求和是在有限集中进行 ,故有1 pii ( t) qii lim t 0iitlim t 0pij ( t)qij .(5.4)jij i t对于状态空间无限的齐次马尔可夫过程,一般只有qiiqij .ji若连续时间齐次马尔可夫是具有有限状态空间 I=0,1,2, ,n,则其转移速率构 成以下形式的矩阵q00q01. q0nQq10q11 .q1n(5.5)

13、qn0qn1. qnn由(5.4)式知,Q矩阵的每一行元素之和为 0,对角线元素为负或 0,其余 ,qij 0.利用 Q 矩阵可以推出任意时间间隔 t 的转移概率所满足的方法组 ,从而可以求 解转移概率 .由切普曼 -柯尔莫哥洛夫方程有pij (t h)pik(h)pkj (t),kI或等价地pij (t h) pij (t)pik(h)pkj(t) 1 pii (h)pij(t)ki两边除以 h 后令 h 0取极限,应用定理 5.3得到pij (t h) pij (t)pik (h)lim h 0 limh 0pkj(t) qii pij (t)(5.6)h k i h假定在 (5.6)式的

14、右边可交换极限与求和 ,再运用定理 5.3,于是得到以下结论 : 定理5.4 (柯尔莫哥洛夫向后方程 )假设 qik qii ,则对一切 i,j 及t 0,有 kipij(t)qikpkj(t) qii pij, (5.7)ki证明 只要证明 (5.6)式右边极限与求和可交换次序 .现在对于任意固定的 N, 有pik (h)limh 0inf k i pikh(h)pkj(t) limh0 infpik (h)ikpkj (t)qik pkj (t)k i,k N h k i,k N因为上式对一切 N 成立,所以pik (h)lim h 0 inf ikpkj (t)k i, hqik pkj

15、 (t)(5.8)k i,为了倒转不等式 ,注意对于 N>i,由于 pkj(t) 1, 所以lim h0 supk i,pik (h)pkj (t)lim h0 supki,kpikh(h)pkj(t)Nhpik (h)lim h 0 supk i ,kpikh(h)pkj(t)Nhpii (h) hpik (h) k i,k N hk i,k 令Nqik pkj (t)Nlim h0 supki,pik(h)pkj(t)qik pkj(t) . k i,qiiqik ,k i,k N ,由定理 5.3 和条件得上式连同 (5.8)可得limh 0 pik(h)pkj(t)qik pkj

16、(t).k i, h k i,定理 5.4 中 pij (t) 满足的微分方程组以柯尔莫可洛夫向后方程著称 .称它们为向后方程 ,是因为在计算时刻 t+h 的状态的概率分布时我们对退后到时刻 h的状态 取条件 ,即我们从pij(t h) PX(t h) j X(0) i,X(h) k. kI.PX(h) k X(0) ipkj(t)pik(h)kI开始计算 .对时刻 t 的状态取条件 ,我们可以导出另一组方程 ,称为柯尔莫哥洛夫向前方程 可得pij (t h)kpik(t)pkj(h),Ipij (th) pij (t)pik(t)pkj(h) pij (t) kIpik (t)pkj (h)

17、1 p jj (h) pij (t),k所以limhpij (t h)0pij (t) h假定我们能交换极限与求和pkj (h) pik (t) jh,则由定理 5.3 便得到lim h 0k1 phjj (h) pij (t). hpij (t)pik (t)qkj qii pij (t),kj 令人遗憾的是上述极限与求和的交换不是恒成立 ,所以上式并非总是成立 .然而在 大多数模型中 包括全部生灭过程与全部有限状态的模型 ,它们是成立的 .定理 5.5(柯尔莫哥洛夫向前方程 ) 在适当的正则条件下 , pij(t)pik(t)qkj pij (t)qjj ,(5.9)ki利用方程组 (5.

18、7)或 (5.9)及初始条件pii(0) 1,pij (0) 0,i j.我们可以解得 pij (t) .柯尔莫哥洛夫向后和向前方程虽然形式不同,但是可以证明它们所求得的解 pij (t)是相同的.在实际应用中 ,当固定最后所处状态 j,研究 pij(t)时(i=0,1,2,n),采用向后方程比较方便 ;当固定状态 i,研究 pij (t) 时(j=0,1,2,),则 采用向前方程较方便 .向后方程和向前方程可以写成矩阵形式(5.10)(5.11)P (t) QP(t),P (t) P(t)Q,其中q00q01q02q10q11q12q20q21q22p00p01p02p10p11p12p20

19、p21p22QP这样,连续时间马尔可夫链的转移概率的求解问题就是矩阵微分方程的求解问 题,其转移概率由其转移速率矩阵 Q决定.特别地,若 Q 是一个有限维矩阵 ,则(5.10) 和(5.11)的解为P(t) eQt(Qt) j 0 j!定理 5.6 .齐次马尔可夫过程在 t 时刻处于状态 j I 的绝对概率 pj (t )满足下列方程:pj (t)pj (t)qjjpk (t )qkj .kj(5.12)证明 由定理 5.2,有 pj (t)pi pij (t) t iI将向前方程 (5.9)式两边乘以pi,并对 i 求和得pipij (t)(i I i Ipi pij (t)qjj )i I

20、 k jpi pik (t)qkj.故pj (t)pj (t)qjjpk (t )qkj. . kj与离散马尔可夫链类似,我们讨论转移概率pij (t) 当 t时的极限分布与平稳分布的有限性质 .定义 5.4 设 pij(t) 为连续时间马尔可夫链的转移概率 ,若存在时刻 t1,t2,使得pij (t1) 0, pij (t2) 0,则称状态 i 和 j 是互通的 .若所有状态都是互通的 ,则称此马尔可夫链为不可约 的.定理 5.7 设连续时间的马尔可夫是不可约的 ,则有下列性质 :(1) 若它是正常返的,则极限limt pij(t) 存在且等于 j 0,j I. 这里0, j I. 是方程组

21、jqjjk qkj ,k j j Ij1(5.13)的唯一非负解 .此时称 j 0, jI .是该过程的平稳分布 ,并且有limt pj (t)j.(2)若它是零常返的或非常返的,则limtpij(t) limt pj(t) 0,i, j I.在实际问题中 ,有些问题可以用柯尔莫哥洛夫方程直接求解 ,有些问题虽然不 能求解但是可以用方程 (5.13)求解 .例 5.2 考虑两个状态的连续时间马尔可夫链 ,在转移到状态 1 之前链在状态 0 停留的时间是参数为 的指数变量 ,而在回到状态 0 之前它停留在状态 1 的时 间是参数为 的指数变量 ,显然该链是一个齐次马尔可夫过程 ,其状态转移概率o

22、(h),p01 ( h)h o(h), p10 (h) h由定理 5.3 知q00lim h 01 p00(h)limh 0 p01(h)ddhp01(h)h0q01,q11 limp11(h)limh 0 p10(h)p10 (h) h 0 dhq10 ,)t,则由柯尔莫哥洛夫向前方程得到p00(t) p01(t) p00(t)= ( )p00(t) ,其中最后一个等式来自 p01(t) 1 p00 (t).因为 p00(0) 1,由常数变易法得p00(t)p00 (t) 0 0e)t若记 0由对称性知 p11(t) 00e ()t,p10 (t)00e ()t,转移概率的极限为lim t

23、p00 (t)0limt p10 (t ), lim t p01(t) 0 lim t p11 (t ),由此可见,当t时, pij (t)的极限存在且与 i无关.定理 5.6知,平稳分布为0 0 , 1 0若取初始分布为平稳分布 ,即PX(0) 0 p00, PX(0) 1 p1 0则过程在时刻 t 的绝对概率分布为p0(t) p0 p00(t) p1p10(t)= 0 0e0 0 01 e 0p1(t) p0 p01(t) p1p10(t)0 01 e ()t0 00e ()t例 5.3 机器维修问题 .设例 5.2中状态 0代表某机器正常工作状态 1 代表机器出 故障.状态转移概率与例

24、5.2 相同,即在 h 时间内 ,机器从正常工作变为出故障的概 率为 p01(h) h o(h), 在 h 时间内,机器从有故障变为经修复后正常工作的概率为 p10 (h) h o(h), 试求在 t=0 时正常工作的机器 ,在 t=5 时为正常工作的概率 解 由例 5.2已求得该过程的 Q 矩阵为根据题意 ,要求机器最后所处的状态为正常工作 ,只需计算 p00(t) 即可.由例 5.2 知p00(t)00e ()t ,0p00(5)00e ()5P X(5) 0 p0 (5) p0 p00(5) p00(5) 0 0e ( )55.3 生灭过程连续时间马尔可夫链的一类重要特殊情形是生灭过程

25、,它的特征是在很短的时 间内,系统的状态只能从状态 i转移到状态 i-1或i+1或保持不变,确切定义如下 .定义5.5 设齐次马尔可夫过程 X(t),t 0 的状态空间为 I=0,1,2, ,转移概率 为 pij (t) ,如果pi,i 1(h)i h o(h), i 0,pi,i 1(h)i h o(h), i 0, 0 0,pi,j (h) o(h),i j 2,pi,i(h) 1 ( i i )h o(h),则称 X(t),t 0为生灭过程 , i为出生率,i 为死亡率 .若 i i , i i ,(是正常数),则称 X (t), t 0为线性生灭过程 .若 i 0,则称X(t),t 0为纯生