应用随机过程课件 ch5 连续时间马氏链

应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE12/77第五章连续时间马氏链第五章连续时间马氏链应用随机过程中国人民大学出版社本章内容本章内容1定义和例子1连续时间马氏链的概念连续时间马氏链的性质转移速率2连续时间马氏链的例子转移概率2柯尔莫哥洛夫向后方程转移概率的求解3极限行为3

平稳分布细致平衡条件4嵌入链4嵌入链的概念及特征利用嵌入链计算平稳分布5离出时间和离出分布离出时间的计算离出分布的计算5连续时间马氏链的概念连续时间马氏链的概念连续时间马氏链的概念定义和例子对于任意状态i,j,i0,...,in连续时间马氏链的概念定义和例子0≤s0<s1<···<sn<s，有：P(Xt+s=j|Xs=i,Xsn=in,...,Xs0=i0)=P(Xt+s=j|Xs=i)=P(Xt=j|X0=i)满足上式的就是连续时间马氏链。注意：在离散时间马氏链中，时间和状态均是离散的。而在连续时间马氏链中，时间是连续的，状态是离散的。从时刻s的状态i到时刻(t+s)的状态j的概率，只依赖于时间间隔t，而与起始时间s无关。注意：在离散时间马氏链中，时间和状态均是离散的。而在连续时间马氏链中，时间是连续的，状态是离散的。定义和例子 定义和例子 连续时间马氏链的概念连续时间马氏链的概念(cont.)为了便于区分，离散时间马氏链经过n步，从状态i转移到状态j的概率记作pn(i,)（注意：n是以上标形式体现，即：pn(i,j)=P(Xt+n=j|Xt=i)=P(Xn=j|X0=i), n,t∈Zh>0ij的概率记作h(,j)（注意：h是以下标形式体现，即：ph(i,j)=P(Xt+h=j|Xt=i)=P(Xh=j|X0=i), h,t∈R+此处的连续时间马氏链仍然假设其具有时间齐次性。定义和例子 定义和例子 连续时间马氏链的性质连续时间马氏链的性质——p(is,k)p(kt,j)=ps+t(i,j)kC-KC-K方程：

i k j0 s s+ts t与离散时间马氏链类似，由连续时间马氏链的C-K方程也可以得到如下不等式：ps+t(i,j)≥ps(i,k)·pt(k,j), ∀k定义和例子 定义和例子 连续时间马氏链的性质连续时间马氏链的相关定理假设Ti是连续时间马氏链停留在状态i的时长，则Ti服从指数分布。对于连续时间马氏链，若对于某个t>0，有pt(i,j)>0，则对任意s>0，均有pt+s(i,j)>0。连续时间马氏链中的所有状态均是非周期的，因此无须考虑周期性。定义和例子 定义和例子 转移速率转移速率当h→0时，引入转移速率q(i,j)，即：q(i,j)=limph(i,j)=limP(Xt+h=j|Xt=i)h→0 h h→0 h其中，q(i,j)表示从状态i跳到j的转移速率。在连续时间马氏链中，除了要考虑某一时刻马氏链处于什么状态以外，还要关心它在离开这个状态之前会停留多长时间。前面已经证明了这个停留时间具备无记忆性，服从指数分布。通常在连续时间下，通过转移速率来描述系统更为简单。转移速率转移速率q(i,j)的性质转移速率定义和例子q(i,i)≤0, i=1,2,...,转移速率定义和例子寸q(i,j)≥0,i̸=j, i,j=1,2,...,N寸Nj=1

q(i,j)=0, i=1,2,...,N由于状态间的转移是发生在状态空间内，因此总的转移速率应当为AB处的xBA−x，流速之和仍然为零。q(ijjq(ij0i是吸收态。此时的转移速率均为零，对应到转移速率矩阵上，体现为状态i一行的元素取值均为零，说明马氏链将永远停留在状态i处。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE9/77寸Nj=1q(i,j)=0的含义q(i,j)寸Nj=1q(i,j)=0的含义q(i,j)可看成是转移概率ph(i,j)关于时间h的导数。转移速率定义和例子寸h→0 h寸由于 j∈Sph(i,j)=1，即转移概率之和是常数1，所以其对时间h的导数为0，即：j∈Sj∈Sj∈Sj∈Sj∈Sj∈Sh→0hh→0hlim1—h(,j)=—「limh(,j)1j∈Sj∈Sj∈Sj∈Sj∈Sj∈Sh→0hh→0h因此总的转移速率之和应当为零。定义和例子 定义和例子 转移速率转移速率矩阵 q(1,1) q(1,2) ··· q(1 Q= q(2,1) q(2,2) ··· q(2,N . . . q(N,1)q(N,2)··· q(N,N)—需要注意的是，由于转移速率矩阵每行元素之和等于零，因此该矩q(ii)的绝对值应当等于该行其他元素之和，即：—|(i,)|= q(i,k), ∀ik̸=i记i=|(i,i)|=−q(,i)，这里的i就是离开状态i的速率。定义和例子 定义和例子 连续时间马氏链的例子举例1：泊松过程N(t)表示速率为λ的泊松过程到时刻t为止的到达数。对于任意时间段h，到达数由n增加到(n+1)的概率为：ph(

n,n

+1)=

(λh)1e−λh1!

=λhe−λh3!2因此：3!2

λh「1λh+

1(λh)2−1(λh)3+···1q(n,n+1)=limh(n,n+1)「−3!h→0 「−3!2=limλ1 λh+2h→0

1(λh)2−1(λh)3+···1=λ定义和例子 定义和例子 连续时间马氏链的例子泊松过程(cont.)在时间h内至少经历两步转移的概率为：=1−（e−λh+λe−λh）=1−(1+λh)e−λhP[=1−（e−λh+λe−λh）=1−(1+λh)e−λh3!2因此：3!2

=1−(1+λh)「1−λh+1(λh)2−1(λh)3+···1P[N(t+h)≥n+2|N(t)=n] 12

132h =2λh−3λhlimP[N(t+h)≥n+2|N(t)=n]=o(h)

+···从而：

h→0 hq(n,n+k)=0, k≥2因此，在到达发生的速率为λ的泊松过程中，到达数N(t)由n增加到(n+1)的速率为λ，其余情形下超过两步的转移速率为0，即：q(n,n+k)=0, q(n,n+k)=0, k≥2

∀n≥0−λ λ 0 0 ··· 0 −λ λ 0 · Q= 0 0 −λ λ ···0 0 0 −λ··应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE14/77泊松过程的转移速率图泊松过程的转移速率图连续时间马氏链的例子定义和例子q(n,n连续时间马氏链的例子定义和例子q(n,n+k)=0, k≥2

∀n≥0λ λ λ λ泊松过程属于计数过程，因此m>n时，q(m,n)=0泊松过程属于计数过程，因此m>n时，q(m,n)=0。说明：应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE15/77举例举例2：生灭过程连续时间马氏链的例子定义和例子{012N的生灭过程（birth-and-deathprocess）λnµ连续时间马氏链的例子定义和例子q(n,n+1)=λn, n=0,1,2,...,N−1q(n,n−1)=µn, n=1,2,...,N相应的转移速率矩阵Q如下：−λ0 λ0 0 0 ··· µ1 −(λ1+µ1) λ1 0 ··· 0 0 ..Q= 0 µ2 −(λ2+µ2)λ2 ··· 0 0. . .

. ... .0 0 0 0 µN−1 −(λN−1+µN−1)λN−10 0 0 0 ··· µN −µN应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE16/77生灭过程的转移速率图生灭过程的转移速率图连续时间马氏链的例子定义和例子q(n,n+1)=λn, n=0,1,2,...,N−连续时间马氏链的例子定义和例子q(n,n−1)=µn, n=1,2,...,Nλ0 λ1 λ2 λ30 1 2 3µ1 µ2 µ3 µ4

···

λN−1NµN应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE17/77举例举例3：纯生过程连续时间马氏链的例子定义和例子当µ=0时，生灭过程称为纯生过程（pure-birthprocess连续时间马氏链的例子定义和例子q(n,n+1)=λn, n=0,1,2,...q(n,n−1)=0, n=1,2,...相应的转移速率矩阵Q如下：−λ0 λ0 0 0 ·−λ0 λ0 0 0 ···Q=0 0 −λ2 λ2 ··应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE18/77纯生过程的转移速率图纯生过程的转移速率图连续时间马氏链的例子定义和例子λ0 λ1 λ连续时间马氏链的例子定义和例子泊松过程可看作转移速率不变（λn=λ）的纯生过程。注意：0 1 2 ·泊松过程可看作转移速率不变（λn=λ）的纯生过程。注意：应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE19/77举例举例4：M/M/s排队系统连续时间马氏链的例子定义和例子顾客按速率λ到达，柜台有s个服务窗口，对每个顾客的服务时间相互独立且服从速率为连续时间马氏链的例子定义和例子q(n,n+1)=λ, n=0,1,2,...s−1sµ, n≥sq(n,n−1)=nµ, 0≤sµ, n≥s(nsnµ(ns时，所有服务窗口都在sµ。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE20/77举例举例4：M/M/s排队系统(cont.)连续时间马氏链的例子连续时间马氏链的例子定义和例子质：τ1τ2τnE(λ)，下式成立：τ=min(τ1,τ2,...,τn)∼E(nλ)因此，在有n位顾客正在接受服务的情况下，最先结束服务离开的时间就是τ，相应的离开速率即为nλ。λ λ λ0 1 2µ 2µ 3µ

···

λ λssµ sµ

···定义和例子 定义和例子 连续时间马氏链的例子举例5：分支过程假设每个个体死亡的速率为µ；生育一个新个体的速率为λ，则有：q(n,n+1)=nλ, q(n,n−1)=nµλ0 1µ 2µ

2λ2 ···3µ

(n−1)λnnµ

nλ说明：(n+1)µ说明：

···当当µ=0时，该过程也称为尤尔过程（uleprocess。转移概率 转移概率 柯尔莫哥洛夫向后方程柯尔莫哥洛夫向后方程将[0,t+h]拆分成[0,h]和[h,t+h]状态时刻时间段

i k j0 h t+hh tkp+h(i,)−pt(i,j)=「—ph(i,k)t(k,j)l−pt(i,j)k— = ph(i,k)pt(k,j)+[ph(i,i)−1]pt(i,— k̸=i对上式两端同时除以h，并令h→0。转移概率̸=i̸=i柯尔莫哥洛夫向后方程h→0hh→0hh→0hp′(ijq(ik)pt(kj「limph(ii11pt(ij)limt+h(i,j)−t(i,j)=lim̸=i̸=i柯尔莫哥洛夫向后方程h→0hh→0hh→0hp′(ijq(ik)pt(kj「limph(ii11pt(ij)tkilimlimph(i,i)−1=−lim—h(i,k)=−—q(i,k)=q(i,i)

h→0 h因此：

h→0 h

h→0ki h

k̸=i—t̸=ih→0hp′(i,j)=—q(i,k)pt(k,j)−「lim1−ph(i,i)1pt—t̸=ih→0h= q(i,k)pt(k,j)+q(i,i)pt(i,j)—k̸=i—= q(i,k)pt(k,j)k应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE24/77转移概率对应的矩阵形式如下：

j)= q(i,k)pt(k,j)柯尔莫哥洛夫向后方程—柯尔莫哥洛夫向后方程—t(1,1)··· pt(1,) q(1,1)··· q(1,n)t(1,1)··· t(1,n) 1)··· n) = q(2,1)··· q(2,n) pt(2,1)··· pt(2, . .

.

. . . ppt(n,1)··· pt(n,n)1)··· n)q(n,1)··· q(n,n)pt(n,1)··· pt(n,n)使用矩阵符号，上式可简写为：dPtdt=QPtvbackwardequationQ[0th[0h[hth]。转移概率 转移概率 柯尔莫哥洛夫向后方程举例6：泊松过程的柯尔莫哥洛夫向后方程假设泊松过程的速率为λ，因此：q(i,i+1)=λ, q(i,i)=−λ根据p′t(i,j)=寸kq(i,k)pt(k,j)，可得：p′t(i,j)=q(i,i+1)pt(i+1,j)+q(i,i)pt(i,j)=λpt(i+1,j)−λpt(i,j)转移概率 转移概率 柯尔莫哥洛夫向后方程举例7：生灭过程的柯尔莫哥洛夫向后方程假设生灭过程的出生速率为λn，死亡速率为µn，因此：q(n,n+1)=λn, q(n,n−1)=µn, q(n,n)=−(λn+µn)根据p′t(n,m)=寸kq(n,k)pt(k,m)，可得：(n,m)=q(n,n+1)pt(n+1,m)+q(n,n−1)pt(n−1,m)+q(n,n)pt(n,m)=λnpt(n+1,m)+µnpt(n−1,m)−(λn+µn)pt(n,m)转移概率 转移概率 柯尔莫哥洛夫向后方程柯尔莫哥洛夫向前方程[0th][0t][tth]，那么得到的方程称为柯尔(Kolmogorovforwardequation)，使用矩阵符号可以简写为：dPtdt=PtQ转移概率 转移概率 转移概率的求解转移概率的求解根据微分方程的知识，以下方程的通解为P(t)=Ceat：dP(t)dt =aP(t)在多维情形下也有类似的结论。由于：因此：

dPtdt=QPt,

dPtdt=PtQPt=eQt其中，Q是转移速率矩阵；Pt是转移概率矩阵。举例举例转移概率的求解转移概率「 l考虑两状态{0,转移概率的求解转移概率「 lQ=−1 12 −2要计算转移概率矩阵Pt，就要求得eQt。转移概率 转移概率 转移概率的求解举例(cont.)将矩阵Q对角化：Q→Λ，相应地：eQt→eΛt=diag（eλ1t,eλ2t,...,eλnt）diag(λ1λ2λn)Q0−3，相应的矩阵可写为：其中：

「1 1l

Q=XΛX−1「0 0l − 「2 1l1111X=1−2

, Λ= , X1= 3 30−3 3 −3相应地：Pt=eQt=XeΛtX−1「1 0l−

「2 1l11

−t「1

−1l22=X0e−3t

X1= 323

3 +e3 3 323 −3 32最终可得转移概率矩阵：Qt

「2 1l11

−t「1

−1l22Pt=e = 323

3 +e3 3 323 −3 32=3333「2+1e−3t 1−1e−3tl=333333332−2e−3t 1+2e−3t3333Pt=3333「2+1e−3t 1−1e−Pt=333333332−2e−3t 1+2e−3t3333当t→2 1limPt= 3 333t→∞ 2 133该连续时间马氏链的平稳分布为2 1π1=3, π2=3极限行为 极限行为 平稳分布不可约马氏链如果对任意状态如果对任意状态i和j，都有可能从i经过有限步转移到j，则称马氏链是不可约的，即，存在状态序列k0=i,k1,...,kn=j，使得q(km−1,km)>0(1≤m≤n)。定义定理如果一个连续时间马氏链Xt不可约，且t>0，则pt(i,j)>0。如果一个连续时间马氏链Xt不可约，且具有平稳分布π，则：定义定理limpt(i,j)=π(j)t→∞平稳分布平稳分布平稳分布极限行为平稳分布极限行为当且仅当πQ=0时，π是一个平稳分布。定理在离散时间下，平稳分布是πP=π的一个解；而在连续时间下，∀tπPtπPtπ当且仅当πQ=0时，π是一个平稳分布。定理应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE35/77平稳分布平稳分布(cont.)简单证明平稳分布极限行为由概率平稳性的定义可知：πPt=π简单证明平稳分布极限行为dPtdt=PtQ方程两端同时左乘平稳概率π，可得：d(πPt)dt =(πPt)Qdπdt=πQ由于平稳概率π与时间t无关，因此可得：πQ=0应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE36/77举例举例7：天气链平稳分布极限行为某地的天气有三种状态，分别为晴、雾、雨。已知晴天的持续时间3天的指数分布，随后会变为雾天；雾天的持续时间服从均4平稳分布极限行为33−1 1 03344Q=0 −1 144思路：求每种天气所占的比例。思路：

1 0 −1根据根据πQ=0计算。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE37/77天气链天气链(cont.)平稳分布极限行为平稳分布极限行为−1+π3=03 12⇒π1131−12⇒π1131−4π=01π2=0.5

=0.3751 212+π2+π3134π2+π2+π313

π==1

=0.12522因此，晴天、雾天和雨天所占的比例分别为37.5%、50%和12.5%。应用随机过程第五章连续时间马氏链中国人民大学出版社应用随机过程第五章连续时间马氏链中国人民大学出版社38/77使用软件求解使用软件求解平稳分布极限行为平稳分布极限行为−π1+π3=013 13⇒1=011π1−4π2=3⇒1=011π1−4π2=031π1−π3331+π2+π34ππ1π21+π2+π34ππ

31 42+π++π+π=1=1 1 2=11231+π2+1+π2+π3=1删减后的方程组的矩阵-向量形式如下：0 −110 −11=⇒ πA=bπ1π1 π2 π3001＿3 3 ＿ 4 001001

1 0 1、 .,

、 .,极限行为 极限行为 平稳分布使用软件求解(cont.)应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE39/77对矩阵-向量形式的方程进行运算，可得：将数值代入计算，可得：

π=bA−10 −10 −1001001＿3 3 001 40014001 40014π=π=bA−1=π的结果刚好就是对应的A−1的最后一行。π=0.3750.50.125＿极限行为 极限行为 细致平衡条件细致平衡条件连续时间马氏链，若对∀j̸=k，均有：π(k)q(k,j)=π(j)q(j,k)离散时间马氏链的细致平衡条件：π(k)离散时间马氏链的细致平衡条件：π(k)p(k,j)=π(j)p(j,k)对比：细致平衡条件细致平衡条件(cont.)细致平衡条件细致平衡条件极限行为π(k)q(k,j)=π(j)q(j,k), ∀j̸=k则π是一个平稳分布。可以根据此定理，利用细致平衡条件，进而求得平稳分布π，从而不必通过πQ=0来求平稳分布。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE42/77举例举例8：生灭链细致平衡条件极限行为考虑状态空间为S={0,1,...,N细致平衡条件极限行为q(n,n+1)=λn, n<Nq(n,n−1)=µn, n>0求其平稳分布。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE43/77生灭链生灭链(cont.)细致平衡条件细致平衡条件极限行为π(n)q(n,n+1)=π(n+1)q(n+1,n)π(n)λn=π(n+1)µn+1因此：

π(n+1)π(n)

=λnµn+1π(n+1)·π(n)·····π(1)=λn·λn−1·····λ0π(n)

π(n−1)

π(0)

µn+1 µn µ1从而：

π(n+1)=λn·λn−1·····λ0π(0)µn+1·µn·····µ1·π(n)=λn−1·λn−2·····λ0π(0), 0<n<N·µn·µn−1·····µ1其中，π(n)是生灭链中状态n的平稳概率。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE44/77极限行为细致平衡条件举例9：M/M/∞排队系统细致平衡条件状态S={0,1,...}，其转移速率如下：q(n,n+1)=λ, q(n,n−1)=nµM/MM/M/s(s可看作生灭过程的特殊形式。µn=nµ,λ0=λ1=···=λ思路：应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE45/77极限行为细致平衡条件M/M/∞排队系统(cont.)细致平衡条件根据生灭链的公式可得：λn−1·λn−2·····λ0

λn (λ/µ)nπ(n)=

µn·µn−1

·····µ1

π(0)=n!µnπ(0)=

n! π(0)进一步地，由于概率要满足完备性，因此：—π(n)=—π(n)=—λπ(0)=π(0)·—(λ/µ)=1因此：最终可得：

n=0

n=0

n!µnπ(0)=e−λ/µ

n!n=0(λ/µ)n

−λ/µπ(n)=

n! ·e由此可见，M/M/∞排队系统的平稳分布π服从均值为λ/µ的泊松分布。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE46/77举例举例10：理发店问题细致平衡条件极限行为3（这里以每小时的顾客数为单位，即每位顾客的理发时间服从均值为20分钟的指数分布，假设顾客按照细致平衡条件极限行为2222220 1 2 33 3 3思路：转移速率图极限行为 极限行为 细致平衡条件理发店问题(cont.)该问题中的状态空间S={0,1,2,3}，其对应的转移速率如下：q(n,n−1)=3, n=1,2,3(,q(n,n−1)=3, n=1,2,3根据细致平衡条件π(n)q(n,n+1)=π(n+1)q(n+1,n)，有：π(0)q(0,1)=π(1)q(1,π(1)q(0,2)=π(2)q(2,1)π(2)(0,3)=π(3)(3,2)

π(0)=3π(1)22π(1)=3π(2)⇒π(2)=3π(3)⇒π(0)π(1)π(2)π(3)1，可得：π(0)=

27, π(1)=65

18, π(2)=65

12 8, π(3)=65 65 若采用πQ=0 − Q 0 3 −5 20 0 3 −3从而得到：

−2π0+3π1=0π0−π1+3π2=022π1−5π2+3π3=0

27=π1=1812π=π1=1812π⇒ 65⇒652π2

−3π3=0

π2=65π0+π1+ππ0+π1+π2+π3=165应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE49/77嵌入链嵌入链定义嵌入链的概念及特征嵌入链嵌入链（定义嵌入链的概念及特征嵌入链对于转移速率矩阵为Q的连续时间马氏链而言，满足如下条件的r(i,j)所构成的就是对应的嵌入链。r(i,j)=

q(i,j)寸i̸=jq寸

(i,j)=q(i), i̸=j0, i=j其中，q(i,j)是转移速率矩阵Q的对应元素，q(i)是离开状态i的速率，并且q(i)=−q(i,i)。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE50/77理发店问题回顾理发店问题回顾嵌入链的概念及特征嵌入链状态空间S={0,1,2,3}对应的转移速率矩阵嵌入链的概念及特征嵌入链Q= 3200−5Q= 3200−5203−52003−30 550 1 0 03025302500 3 0 20 0 1 00 0 1 0 5 50 0 1 0R0 0 1 0R=0 0 1 0嵌入链 嵌入链 嵌入链的概念及特征理发店问题(cont.)3 0 25 30250R=50 1R=50 1 0 0 5 50 0 1 0这里转移概率的取值是假设转移服从速率为q(i,j)的指数分布，并利用指数分布的性质得到的。注意：i这里转移概率的取值是假设转移服从速率为q(i,j)的指数分布，并利用指数分布的性质得到的。注意：Q=R=3003 −5 2 0525−2 2 0 0Q=R=3003 −5 2 05250 3 −5 20 0 3 0 0 3

0 3

0 20 0 3 0 0 1 00 0 1 0 5 50 0 3 0 0 1 00 0 1 0从状态1转移到状态0的速率为3，转移到状态2的速率为2，因此从状态1首先转移到状态0的概率为：P(X

=0|X

=1)=P[T

3 31122+35=min(T,T1122+35τ00类似地，从状态1首先转移到状态2的概率为：τ00τP(Xτ

=2|X

=1)=P[T

2 22122+35=min(T,T2122+35应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE53/77泊松过程的嵌入链泊松过程的嵌入链嵌入链的概念及特征嵌入链q(ii1)λq(ii−嵌入链的概念及特征嵌入链r(i,i)=0, r(i,i+1)=1相应的转移速率矩阵与嵌入链的转移概率矩阵分别如下： −λ λ 0 0 0 0 · Q= 0 Q= 0 0 −λ λ 0 0 ···0 0 0 −λ λ 0 ···...0 0 0 0 −λλ·· . . . .

010000··· R= 000100···000010···...000001·· . . . . . . . . . . . . . . 应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE54/77有吸收态的嵌入链有吸收态的嵌入链嵌入链的概念及特征嵌入链嵌入链的概念及特征嵌入链000−2010−3002000100−40Q=Q=0 1000 0300 0对于有吸收态i的连续时间马氏链，q(i,i)=0。同时，与之对应的嵌入链转移概率r(i,i)=1。上面的转移速率矩阵Q有两个吸收态1和5。于是对应的嵌入链转移概率矩阵R如下：0001/201/20001/201/2001/302/301/4000001R= 0R= 0

003/40嵌入链 嵌入链 嵌入链的概念及特征嵌入链转移概率的特点嵌入链的转移概率与连续时间马氏链的转移概率的不同之处在于，前者并未考虑时间因素，只关心状态与状态之间的转移概率。嵌入链 嵌入链 利用嵌入链计算平稳分布嵌入链根据πQ=0可得：iij—π(i)q(i,j)=0 ⇒ —π(i)q(i,j)=π(j)q(j)iij定义ψ(i)=π(i)q((寸i

jπ(i)q(ij寸

i̸=j

ψ(i)(i,j)

i̸=j

ψ(i)r(i,j)因此：

π(j)q(j)=ψ(j)

ψ(j)=—ψ(i)r(i,j)ijijijij其中，r(i,j)是嵌入链对应的转移概率，反映了连续时间马氏链状态之间转移的概率。矩阵矩阵-向量形式利用嵌入链计算平稳分布嵌入链—ψ(j)= ψ(i)r(i,利用嵌入链计算平稳分布嵌入链—i̸=j上式的矩阵-向量形式如下：

ψR=ψ可根据该性质，通过嵌入链R计算连续时间马氏链的平稳分布π。可根据该性质，通过嵌入链R计算连续时间马氏链的平稳分布π。注意：应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE58/77通过嵌入链计算平稳分布的具体步骤通过嵌入链计算平稳分布的具体步骤利用嵌入链计算平稳分布嵌入链 1基于嵌入链R，利用ψR=ψ利用嵌入链计算平稳分布嵌入链 1ψ=ψ(1)ψ(2)··· ψ(n)将得到的嵌入链平稳分布中的各元素分别除以对应的转移速率矩阵主对角线元素的绝对值，即ψ(i)/q(i)，从而得到向量π，即： π=q(1)

ψ(2)q(2)

··· (n)＿最后对向量π进行归一化（normalize分布π，即：

1 1 ＿····π=A=A

ψ(1)

ψ(2)q(2)

ψ(n)q(n)k=1q(k)其中，Ak=1q(k)

ψ(k)。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE59/77ππ(i)与ψ(i)的关系利用嵌入链计算平稳分布嵌入链π(i)iψ(i衡量利用嵌入链计算平稳分布嵌入链简言之，π关注花费在各状态上的时间所占的比重；ψ关注各状态转移的次数所占的比重。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE60/77举例：举例：利用嵌入链计算平稳分布嵌入链利用嵌入链计算平稳分布嵌入链 Q= 2 −4 24 4 −8求该链的平稳分布π。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE61/77解法一解法一利用嵌入链计算平稳分布嵌入链使用πQ=利用嵌入链计算平稳分布嵌入链−2π(1)+2π(2)+4π(3)=π(1)−4π(2)+4π(3)=0

π(1)=47⇒ π(2)=27777π77π(1)+π(2)+π(3)=1π(3)=1应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE62/77解法二解法二利用嵌入链计算平稳分布嵌入链 由转移速率矩阵Q利用嵌入链计算平稳分布嵌入链 0 0.50. R= 0 0.50.5 0由于该链是一个双随机链，因此：从而：

ψ= 1 1 1「1q(3)28612「1q(3)28612q(1)「ψq(1)

ψ(2)qq(2)

ψ(3)1「1/3

1/344

1/31=「1 1

112424应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE63/77解法二解法二(cont.)利用嵌入链计算平稳分布利用嵌入链计算平稳分布嵌入链A=1+1+1=7因此：

6 12 24 24A761224777π=1=24「1 1 11=「4 2 11A761224777不难看出，两种解法得到的结果完全相同。不难看出，两种解法得到的结果完全相同。不难看出，两种解法得到的结果完全相同。不难看出，两种解法得到的结果完全相同。离出时间和离出分布连续时间马氏链吸收态的特征离出时间和离出分布连续时间马氏链吸收态的特征Qi行的所有矩阵元素取值均为iR上，体现为r(ii)1r(ij)0,j̸=i。为了继续研究含吸收态的连续时间马氏链，可以对其中的状态进行简单的分类。其中的吸收态记作A，非常返态记作T，于是状态空间S=A∪T，相应的转移速率矩阵Q可以表示成如下的分块矩阵形式：「A「A0B0lQ=TA离出时间和离出分布 离出时间和离出分布 离出时间的计算离出时间离出时间，是指非常返态最终被吸收态所吸收的期望时长。由于连i的停留时间服从指数分布，相应的停留时间q(i)1/q(i)。—记g(i)表示从状态i,i∈T，最终被吸收的期望时间。—g(i)=1+q(i)

r(i,j)g(j)—「 1j̸=i,j∈—「 1=1+q(i) —j̸=i, —

q(i,j)g(j)q(i)=1 1+q(i)

(i,j)(j)j̸=i,j∈T离出时间的计算离出时间的计算离出时间的计算g(i)=1 1离出时间的计算q(i)

(i,j)(j)离出时间和离出分布 —j̸=i离出时间和离出分布 —由于q(i)=−q(i,i)，上式可以进一步化简：ji,∈T

q(i,j)g(j)+q(i,i)g(i)=−1—q(i,j)g(j)=−1—j∈T应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE67/77离出时间的计算离出时间的计算(cont.)离出时间的计算离出时间和离出分布—q(i,j)g(j)=离出时间的计算离出时间和离出分布—j∈T由于i,j∈T，因此q(i,j)对应的是转移速率矩阵Q的分块矩阵A。于是上式可以进一步表示为矩阵-向量形式如下：g=1 ⇒ g=−−1其中，A是(k×k)的分块矩阵，当中包含了k个非常返态；g与1均是(k×1)1各元素的取值均为。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE68/77例题例题1离出时间的计算离出时间和离出分布121、2、离出时间的计算离出时间和离出分布提示：求病人的平均生存期。提示：

−2 1.5 0.0 0 0Q=0 −.52.0 0 0本题中的状态本题中的状态3是吸收态，对应的状态1和2则是非常返态。应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE应用随机过程第五章连续时间马氏链中国人民大学出版社PAGE