第四章马氏链

对任意的 n 及 i 0 , i 1 , L , i n , i n + 1 S ,
P {X n +1 = i n +1 X 0 = i 0 , X 1 = i1 , L , X n = i n } 0 i n +1 > i n =1 = P{X n +1 = i n +1 | X n = i n } i n +1 i n in
1/ 3 1/ 3
0
5/ 9 2/ 9 1/ 9 2/9 3/9 2/9 1/ 9 2/ 9 5/ 9 0 1/ 3 1/ 3
0 0 1 / 9 1 / 9 1 / 3
5、有限维分布
1．有限维分布 设马氏链{Xn,n≥0},状态空间S，n步转移概率矩阵P(n).
(1)一维分布
L p1j(n ) L L p 2j(n ) L L L L pij (n ) L L L
为齐次马尔可夫链的n步转移概率矩阵。
其中 p ij ( n) 0, p ij ( n) = 1.
a j x
定理4.1.2 设{Xn，n=0,1,…}为齐次马氏链，则对于任 意的正整数k,m，有Pij (m + k ) = Pir (m) Prj (k ) 此方程称为Chapman-kolmogorov(切普曼－柯尔莫哥 洛夫)方程,简称C-K方程.
关的，所以｛ Xn,n=0 ， 1,2,… ｝是一马氏链，且是齐次
的。它的一步转移概率和一步转移概率矩阵分别为
1 3 , j = i - 1, i , i + 1, 1 < i < 5 pij = P{Xn+1 = j | Xn = i} = 1, i = 1, j = 2 或 i = 5, j = 4 - 0, j i 2.
=
=
P { X m = i , X m +1 = j1 , , X n+ m -1 = jn-1 , X n+ m = j |}
P { X m = i} pij1 p j1 j2 p jn-1 j P { X m = i}
P { X m = i}
= pij1 p j1 j2 p jn-1 j
1
2
3
4
5
1 0 1 0 0 0 2 1 / 3 1 / 3 1 / 3 0 0 P = 3 0 1/ 3 1/ 3 1/ 3 0 4 0 0 1 / 3 1 / 3 1 / 3 5 0 0 1 0 0
如果把1这一点改为吸收壁，即Q一旦到达1，就永远
留在点1上。此时，相应链的转移概率矩阵只须把P中第1横
行改为（1，0，0，0，0）。总之，改变游动的概率规则， 就可得到不同方式的游动和相应的马氏链。
例4.1.3 设Xn,n=0，1，2,…是独立同分布的随机变量 列,记Xn可能取值的全体为S={i,i 1},证明{Xn}为马氏 链，并求其一步转移概率。 解 对任意的n及
设订货和进货不需要时间，每天的需求量 立同分布且 P{Yn = j} = a j ( j = 0,1, 2,...) 。
独
4. n步转移概率及C-K方程
称条件概率Pij (m, m + n) P { X n+m = j | X m = i} 为马尔 可夫链在时刻m处于状态i的条件下，在时刻m+n步转移到 状态j的n步转移概率。
r
注释：如果把转移概率写成矩阵的形式，那么C－K方程
具有以下简单的形式 P(m+k)=P(m)P(k) 步转移概率完全决定。 m, k≧0
特别地，对齐次马氏链有P(n)=Pn, n步转移概率由一
证：
Pij (m + k ) = P { Xn+m+k = j | X n = i}
= P { X n+ m = r , X n+ m + k = j | X n = i}
=
r
= pir (m) prj (k )
r
例4.1.4 求带有两个反射壁的一维随机游动的两步转移 概率矩阵。 1 0 0 0 0 0 1 / 3 1 / 3 1 / 3 0 解 ：P ( 2) = P 2 = 0 1 / 3 1 / 3 1 / 3 0 0 1 / 3 1 / 3 1 / 3 0 0 0 0 1 0
有
P { X n+1 = in+1 X 0 = i0 , X 1 = i1 , , X n = in } = P { X n + 1 = in + 1 | X n = i n }
则称｛Xn,n0｝为马氏链。 注：定义4.1.2与定义4.1.1是等价的。
例4.1.1：记从数1,2, …,N中任取一数为X0，当n1时， 记从数1,2, …,Xn-1中任取一数为Xn,问｛Xn,n=0，1， 2,…｝是马氏链吗？ 证：｛Xn,n=0，1，2,…｝的状态空间S={i,1iN},
P { X m + n = j | X m = i}
=
j1 , j2 ,, jn-1

P { X m+1 = j1 ,, X n+ m-1 = jn-1 , X n+ m = j | X m = i}
而P { Xm+1 = j1 ,, Xn+m-1 = jn-1 , Xn+m = j | Xm = i}
则称｛Xn,n=0,1，2，…｝为马氏链。
{
}
Pij (m, m + n) P { X n+m = j | X m = i}
称为马氏链在时刻 m 系统处于状态 i 的条件下，经过
n步转移到状态 j 的转移概率。
设{Xn,n0},其状态空间为S,若对于任意的 正整数n和任意的 i0 , i1 , , in+1 , 定义4.1.2
Pij n, n + 1 = Pij m, m + 1 即马氏链{Xn,n0}的转移概率Pij(n,n+1)与n无关，
则称转移概率具有平稳性，这时，马尔可夫链称为是
若对任意的正整数m,n及任意的ai，aj，有
齐次的。
定理4.1.1：若{Xn}为齐次马氏链，则对任意正整数n,及任意 的i，j，有 P { X m+n = j | X m = i} 与m无关。 证明：
i , j S , m 0, n 1
为齐次马氏链{Xn,n≥0}的n步转移概率，并称由pij(n) 组成的矩阵
p11(n ) p12(n ) p 21(n ) p 22(n ) P(n ) = pij (n ) = pi 1(n ) pi 2(n )
pij pij 1 = P { X m+1 = j | X m = i}
称为齐次马氏链的一步转移概率；
P P(1) = pij (1)
a1 a2 P (1) = ai a1 p11 p 21 pi1 a2 p12 p 22 pi 2 L L L L L L aj p1 j p2 j p ij L L L L L L
i S
由于Xn, n=0，1，2,…独立同分布，因而
P {X n +1 = j | X n = i } = P {X n +1 = j }
= q j = P{X m +1 = j | X m = i}
所以{Xn}为齐次马氏链。其一步转移概率P:
pij = qj ,
i,j S .
例： M/G/1 排队系统 假设顾客依参数为λ的Poisson过程来到只有一个服务员的服 务站，若服务员空闲来客就立刻得到服务，否则排队等待直 至轮到他。设每名顾客接受服务的时间独立同分布，分布函 数为G(x)，且与顾客到达过程相互独立。这个系统称为M/G/1 排队系统. (M--到达的时间间隔服从指数分布, G--服务时间 的分布，1--单个服务员)。 令Xn--第n个顾客结束服务时剩下的顾客数， Un--第n个顾客接受服务的时间内来到服务机构的顾客数，则
称X0的分布 q j (0) = P{ X0 = j}, j = 0,1, 2,
i 0 , i1 ,L, i n , i n+1 I
= P{X n+1 = i n+1 | X n = i n }
P{X n+1 = i n+1 | X 0 = i0 ,L, X n = i n } = P{X n+1 = i n+1 }
所以{Xn}为马氏链。
记 P{ X n = i} = qi ,
在原处；如果Q现在位于1（或5）这点上，则下一时刻就 以概率1移动到2（或4）点上。1和5这两点称为反射壁。 上面这种游动称为带有两个反射壁的随机游动。
1
2
3
4
5
若以 Xn 表示时刻 n 时 Q 的位置，不同的位置就是 Xn 的不同 状态，那么｛Xn,n=0，1,2,…｝是一随机过程，状态空间 就是 I ，而且当 Xn=i,iI 为已知时 ,Xn+1 所处的状态的概率 分布只与Xn=i有关，而与Q在时刻n以前如何到达i是完全无
1 0 0 0 0 0 1 / 3 1 / 3 1 / 3 0 0 1/ 3 1/ 3 1/ 3 0 0 1 / 3 1 / 3 1 / 3 0 0 0 0 1 0
1 / 3 1 / 9 = 1 / 9 0 0
称为齐次马氏链的一步转移概率矩阵。
例4.1.2(一维随机游动) 设一醉汉Q（或看作一随机游 动的质点），在如图所示直线的点集I＝｛1，2，3，4， 5｝上作游动，仅仅在1秒、2秒…等时刻发生游动。游动 的概率规则是：如果Q现在位于点i (1<i <5)，则下一时刻