随机过程-14连续时间马尔科夫链课件.ppt

1、5.1 连续时间马尔可夫链连续时间马尔可夫链 前面考虑的马尔科夫链中，我们假设状态前面考虑的马尔科夫链中，我们假设状态的转移都是在单位时间内发生。的转移都是在单位时间内发生。本章将考虑连续时间模型本章将考虑连续时间模型:按照一定的转移按照一定的转移概率从一个状态转移到下一个状态，但两概率从一个状态转移到下一个状态，但两次转移之间的时间间隔是一个连续的随机次转移之间的时间间隔是一个连续的随机变量。变量。例如泊松过程。例如泊松过程。0 1 2 3 4 5I jpij(t,)Tt t+I pi(0)pi(t)定义定义5.1 设设随机过程随机过程X(t)，t 0，状态空，状态空间间I=0,1,2,若对

2、任意若对任意0 t1 t2tn+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)，t 0 为为连续时间马尔可夫链连续时间马尔可夫链。经过时间经过时间t后的后的转移概率转移概率转移概率转移概率：在：在s时刻处于状态时刻处于状态i，经过时间，经过时间t后后转移到转移到状态状态j的的概率概率:pij(s,t)=PX(s+t)=j|X(s)=i 定义定义5.2 齐次齐次转移概率转移概率 pij(s,t)=pij(t)(与起始时刻与起始时刻s无关，只与时间间隔

3、无关，只与时间间隔t有关有关)经过时间经过时间t转移概率矩阵：转移概率矩阵：P(t)=(pij(t)，i,j I，t 0 )()()()()()()()()()(212222111211tptptptptptptptptptPmmmmmm定理定理5.15.1 齐次马尔可夫过程的转移概率具有齐次马尔可夫过程的转移概率具有下列性质：下列性质：(1)0)(tpij(2)Ijijtp;1)(Ikkjikijsptpstp)()()(3)性质性质3用矩阵表示就是：用矩阵表示就是：)()()()()()()()()(212222111211tsptsptsptsptsptsptsptsptspmmmmmm

4、 )()()()()()()()()()()()()()()()()()(212222111211212222111211tptptptptptptptptpspspspspspspspspspmmmmmmmmmmmm证证 由概率的定义，由概率的定义，(1)(2)(1)(2)显然成立，下证显然成立，下证(3)(3)0(|)()(iXjstXPstpij IkiXktXjstXP)0(|)(,)()0(|)()0(,)(|)(iXktXPiXktXjstXPIk IkiXktXPktXjstXP)0(|)()(|)(IkkjikIkikkjsptptpsp)()()()(正则性正则性分布律分布律

5、转移方程转移方程时间时间离散离散时间时间连续连续(0)(0)1,0()iiijppij01,lim()0,ijtijp tij()()0,1nijnijjIpp()0()1ijijj Ip tp tIkkjikijsptpstp)()()(Iklnkjliknijppp)()()(定义定义5.35.3(1)(1)初始概率初始概率IjjXPppjj,)0()0(2)(2)绝对概率绝对概率0,)()(tIjjtXPtpj(3)(3)初始分布初始分布 Ijpj,(4)(4)绝对分布绝对分布 0,)(tIjtpj 如果已知了初始分布则如果已知了初始分布则t时刻的分布为：时刻的分布为：)()()()()

6、()()()()()0(),.,0(),0(21222211121121tptptptptptptptptppppmmmmmmm)(),.,(),(21tptptpm定理定理5.25.2 齐次马尔可夫过程的绝对概率齐次马尔可夫过程的绝对概率及有限维概率分布具有下列性质：及有限维概率分布具有下列性质：0)()1(tpj Ijjtp1)()2(Iiijijtpptp)()()3(Iiijijptptp)()()()4()(,)()5(11nnitXitXP Iinniiiiiiittpttptppnn)()()(11211211 假定某个时刻，马尔科夫链进入状态假定某个时刻，马尔科夫链进入状态i,

7、然后然后在状态在状态i停留，直到转移到另一个状态。停留，直到转移到另一个状态。设设停留的时间为停留的时间为 i，下面讨论，下面讨论 i服从什么样服从什么样的分布。的分布。ss+t0 itTss+t0 iiiiti 假定在进入状态假定在进入状态i之后之后的的s个单位时间中从未个单位时间中从未离开状态离开状态i(即没有发生过转移即没有发生过转移)，随后，随后t个单个单位时间中仍未离开状态位时间中仍未离开状态i的概率：的概率：它处于状态它处于状态i至少至少t个单位时间的个单位时间的(无条件无条件)概概率：率：根据马尔科夫性，根据马尔科夫性，|stsPiitPi|tPstsPiiiT 可见，停留时间可

8、见，停留时间 i具有无记忆性，具有无记忆性，因此因此 i服从指数分布。服从指数分布。假定假定 i的参数为的参数为vi，则，则 i的密度函数为的密度函数为 平均停留时间平均停留时间 且且 0,00,)(xxevxfxviii iivE1)(txviidtevtFtPii0)()(tvie1tviietP)(性质：性质：若若 i 为过程在状态转移之前停留在为过程在状态转移之前停留在状态状态 i 的时间，则对的时间，则对 s,t 0 有有(1)(2)i 服从指数分布，即服从指数分布，即 当当vi=时，时，对于任意对于任意t，称状态称状态i为为瞬时状态瞬时状态；当当vi=0时，时，称状态称状态i为为吸

9、收状态吸收状态；今后我们假定对一切今后我们假定对一切i，0vi0,对所有的常返态对所有的常返态jiiXjtXPjt对所有的对所有的,)0(|)(lim mkkjkkjkjkjkjmjqq11,.,2,1,为了进一步阐述平衡方程组，我们把为了进一步阐述平衡方程组，我们把 j看成看成过程花费在状态过程花费在状态j上的时间平均长期频率。上的时间平均长期频率。那么那么 kqkj就可以看成从就可以看成从k到到j的转移的平均的转移的平均频率（单位时间内，转移从频率（单位时间内，转移从k到到j的品均次的品均次数）所以平衡方程的本质就是从状态数）所以平衡方程的本质就是从状态j开始开始的转移频率（方程的左边）等

10、于进入状态的转移频率（方程的左边）等于进入状态j的转移频率（方程的右边）的转移频率（方程的右边）mijqqjkkjkjkjkj,.,2,为了进一步阐述平衡方程组，我们把为了进一步阐述平衡方程组，我们把 j看成看成过程花费在状态过程花费在状态j上的时间平均长期频率。上的时间平均长期频率。那么那么 kqkj就可以看成从就可以看成从k到到j的转移的平均的转移的平均频率（单位时间内，转移从频率（单位时间内，转移从k到到j的品均次的品均次数）所以平衡方程的本质就是从状态数）所以平衡方程的本质就是从状态j开始开始的转移频率（方程的左边）等于进入状态的转移频率（方程的左边）等于进入状态j的转移频率（方程的右

11、边）的转移频率（方程的右边）mijqqjkkjkjkjkj,.,2,例例14 一台运转中的机器会一直工作，直到一台运转中的机器会一直工作，直到警告信号产生。从开始工作一直到产生警警告信号产生。从开始工作一直到产生警告信号的时间服从参数为告信号的时间服从参数为1的指数分布。产的指数分布。产生警告之后，机器将被检修，检修的时间生警告之后，机器将被检修，检修的时间服从参数为服从参数为5的指数分布。检修结果以的指数分布。检修结果以1/2的概率将机器维修好，此时机器将恢复正的概率将机器维修好，此时机器将恢复正常生产；而另一个可能结果是机器已经损常生产；而另一个可能结果是机器已经损坏坏(概率为概率为1/2

12、)，机器将送去修理。修理时，机器将送去修理。修理时间服从参数为间服从参数为3的指数分布。我们假设前面的指数分布。我们假设前面提到的随机变量都是相互独立的，且独立提到的随机变量都是相互独立的，且独立于检修结果。写出转移概率矩阵和转移速于检修结果。写出转移概率矩阵和转移速率矩阵率矩阵,并求其稳态概率。并求其稳态概率。解解 令状态令状态1,2,3分别表示正常工作，检修和分别表示正常工作，检修和修理。转移速率是修理。转移速率是v1=1，v2=5，v3=3.转移概率矩阵和转移速率矩阵表示如下转移概率矩阵和转移速率矩阵表示如下,0012/102/1010 P,0032/502/5010 Q 忽略忽略o()

13、项，对应的马尔科夫链项，对应的马尔科夫链Zn的转移概的转移概率矩阵为率矩阵为 31032/5512/501 平衡方程组和归一化方程为：平衡方程组和归一化方程为：0032/502/5010Q32123123211,253,5,325 唯一解为：唯一解为：.415,416,4130321 注意要区分该稳态概率注意要区分该稳态概率 j和嵌入马尔科夫链和嵌入马尔科夫链Xn的稳态概率的稳态概率 嵌入马尔科夫链的平稳方程组和归一化方嵌入马尔科夫链的平稳方程组和归一化方程为：程为：得到：得到：j 32123123211,21,21 .51,52,52321 ,21 注意，尽管注意，尽管(转移到状态转移到状态

14、1的次数和的次数和到达状态到达状态2的次数相当的次数相当),也有也有,21 因为因为 因为过程在状态因为过程在状态1上花费的时间相对于花费上花费的时间相对于花费在状态在状态2上的时间要长。所以给定一个时刻上的时间要长。所以给定一个时刻t，过程，过程X(t),更有可能处于状态更有可能处于状态1.一般情况，两组稳态概率一般情况，两组稳态概率 是不同的。是不同的。jj 例例15（排队论）在一个通信系统中到达缓（排队论）在一个通信系统中到达缓冲器的信号包的过程是一个参数为冲器的信号包的过程是一个参数为的泊的泊松过程，信号存放在容积为松过程，信号存放在容积为m m的缓冲器里，的缓冲器里，每次只传输一个信

15、号。但是如果缓冲期里每次只传输一个信号。但是如果缓冲期里的信号已满，新来的信号就会丢失。传输的信号已满，新来的信号就会丢失。传输一个信号需要的时间服从参数为一个信号需要的时间服从参数为的指数的指数分布。不同信号之间的传输时间是相互独分布。不同信号之间的传输时间是相互独立的，也独立于所有间隔时间。立的，也独立于所有间隔时间。设状态设状态X(t)X(t)表示表示t t时刻对应系统中的信号数时刻对应系统中的信号数量量(如果如果X(t)0,X(t)-1X(t)0,X(t)-1表示表示队列中等表示表示队列中等待的信号数量，有一个信号正在被传输待的信号数量，有一个信号正在被传输).).当新信号达到，状态将

16、增加当新信号达到，状态将增加1 1，当已存信号，当已存信号被传输，状态将减少被传输，状态将减少1.1.下面用马尔科夫过下面用马尔科夫过程的描述性定义，证明程的描述性定义，证明X(t)X(t)确实是一个连确实是一个连续时间的马尔科夫链。续时间的马尔科夫链。首先考虑系统中为空的情况，也就是状态首先考虑系统中为空的情况，也就是状态X(t)为为0的情况。从状态的情况。从状态0转移只有当新信号转移只有当新信号到达才能发生。这种情况下，状态变成了到达才能发生。这种情况下，状态变成了1.因为信号的到来是一个泊松过程，所以有因为信号的到来是一个泊松过程，所以有 于是于是 接下来考虑系统中信号已满的情况也就是接

17、下来考虑系统中信号已满的情况也就是状态状态X(t)=m的情况的情况)(!1)()0)(|1)(1 oetXtXP 其他其他如果如果,01,0jqj 状态状态m转移只有当现有的一个信号完成传输转移只有当现有的一个信号完成传输才能发生，传输完成后状态变成了才能发生，传输完成后状态变成了m-1.因因为传输的时间服从指数分布（具有无记忆为传输的时间服从指数分布（具有无记忆性），所以有性），所以有 以及以及 最后，考虑系统状态最后，考虑系统状态X(t)等于某个中间状态等于某个中间状态i,0im.)()(|1)(omtXmtXP 其他其他若若,01,mjqmj 在下一个时间在下一个时间中，新信号到来的概率是中，新信号到来的概率是+o(),使得状态变成了使得状态变成了i+1；完成一个信号；完成一个信号传输的概率是传输的概率是+o(),使得状态变成了使得状态变成了i-1.在时间间隔在时间间隔中同时有新信号到达和已知信中同时有新信号到达和已知信号传输完成的概率是号传输完成的概率是 可以忽略掉。所以可以忽略掉。所以 以及以及)()()(2 Ooo )()(|1)(oitXitXP )()(|1)(oitXitXP 其他其他对于所有的对于所有的若若若若,01,.,2,1,1,1,miijijqij