第三章-马尔可夫链.doc
- 格式：docx
- 大小：71.43 KB
- 文档页数：19
第三章马尔可夫链
、马尔可夫链的概念
马尔可夫过程是一类有重要应用意义的随机过程，它具有如下特征：随机过 程‘将来’所处的状态仅与‘现在’所处的状态有关，而与‘过去’曾处于什么 状态无关。
马尔可夫过程按其状态和时间参数是离散还是连续的可以分成三类
(1) 时间和状态都是离散的马尔可夫过程，称为马尔可夫链。
(2) 时间连续、状态离散的马尔可夫过程，称为连续时间的马尔可夫链
(3) 时间和状态都连续的马尔可夫过程。
本章介绍马尔可夫链 定义1设｛Xn，n 0｝为随机序列，其状态空间为I ｛i0,i1,i2，｝，如果对任意正
整数n及任意n+2个状态i0,i1,i2, ,in 1 I，有
P{Xn 1 in 1X0 io,X1 i1, ,Xn *}
P{Xn1 in1 Xn 叨 则称此随机序列｛Xn，n 0｝为马尔可夫链。
若将时刻n称为‘现在’，将时刻n+1称为‘将来’，而把0，1, 2，……，n-1 称为‘过去’。定义中的等式便可通俗解释为：在已知 ｛Xn，n 0｝ ‘现在’所
处的状态条件下，‘将来’所要达到的状态与‘过去’所经历的状态无关，这一 特性常称为马尔可夫的无后效性。
例1.一个n级数字传输系统，每一级的输入和输出信号只取 0或1两个值，每 一级的输出是下一级的输入；并假定当一级输入为0时，其输出为0和为1的概 率分别为p和1-p；当输入为1时，其输出为1和0的概率分别为p和1-p(见图)令Xn表示第n级输出，则｛ Xn,n > 0｝便为一个马尔可夫链。
例2•从1, 2,……,N数字中任取一个数，记为 X0;再从1, 2,……,X0数 字中任取一个数，记为X1;再从1, 2,……,X1中任取一个数，记为X2;依此 类推，在1, 2, , Xn-1中任取一个数，记为Xn。可以证明｛ Xn,n > 0｝为马 尔可夫链。
事实上，｛ Xn,n >0｝的状态空间为I=｛1 , 2,……,N｝，对任意正整数n,取n+1 个状态
i0,i1,i2, ,i n I , 由题意可知 故｛ Xn,n >0｝为马尔可夫链。
二、转移概率
由马尔可夫链的无后效性和乘法公式有
P{Xo io,Xi ii, ,Xn in}
P{Xn inXnl in l} ?P{ Xo io,Xi ii, ,Xn 1 in l}
P{Xn inXnl in l}P{ Xn 1 ini Xn 2 in 2} P{ Xi hX° io}P{X。 i。}
由此可见，马尔可夫链的统计特性完全由条件概率
P{Xn 1 iniXn in}所确定，所以如何确定这个条件概率就显得非常重要，我
们把这个条件概率称为一步转移概率。一般一步转移概率为 P{Xn 1 j Xn i}， 它表示系统在时刻n处于状态i的条件下，到时刻n+1转移到状态j的概率，记 为 Pj(n)。
定义2称条件概率Pij(n) P{Xn 1 j|Xn i}为马尔可夫链{Xn，n 0}在时刻n 的一步转移概率。
一般，转移概率Pij(n)不仅与状态i, j有关，而且与时刻n有关，但当它与时刻n 无关时，表示马尔可夫链具有平稳转移概率， 即与起点无关，此时我们称马尔可
夫链是齐次的。
定义3如果对任意的i,j I，马尔可夫链的转移概率Pj(n)与n无关，则称 {Xn,n 0}为齐次马尔可夫链，并记Pjj(n)卩耳。
下面我们只讨论齐次马尔可夫链。
设P为一步转移概率Pj所组成的矩阵，状态空间I {1,2, }，称
Pl1 P12 P1n
P P21 P22 P2n P{Xn inXo io,Xi i1 , , X n 1 in i}?P{Xo io,Xi ini} 为马尔可夫链的一步转移概率矩阵。
转移概率矩阵具有下面性质
（1）Pij 0，i,j I (2) Pij 1 , i I
j i
称具有上面两条性质的矩阵为随机矩阵。
下面给出n步转移概率的概念
定义4称条件概率
P(n) P｛Xm n jXm i｝，'，j 5 0, n 1
为马尔可夫链的n步转移概率，并称
P(n) (P『)
为马尔可夫链的n步转移概率矩阵。其中p(n) 0, p(n) 1
j i
当n=1时，P⑴P，规定
切普曼--柯尔莫哥洛夫方程
定理1设｛Xn, n 0｝为马尔可夫链，则对任意正整数n,0 l n，和状态i, j I，
n步转移概率具有下列性质
(1) (n) Pij Pik) pkjn "(切普曼一柯尔莫哥洛夫方程)
k I
(2) (n) Pij Pi/ Pg Pkn 和
k1 1 kn 1 1
(3) p(n) pp(n 1)
(4) p(n) Pn
证明(1)利用全概率公式和马尔可夫性，有 (0)
Pij 0, i
1, i j，即P(0)为单位矩阵
j Pi(n) P{Xmn jXm i} P{ (Xml k), X m n jXm i}
k I
P{ (Xm1
k I k, X m n j)Xm i}
k I P{Xm 1 k, X m n jXm i}
P{Xm i,Xm 1 k, X m n j}
k I
P{Xm i}
P{Xm i}P{Xmi kXm i}P{Xmn jXm Mmi k}
k I P{Xm i}
P{Xm 1 kXm i}P{Xmn jXml k}
k I
(1) (n 1) (1) (n 1) Pik (m)Pkj (m 1) Pik Pkj
k I k I
(1)式是关于转移概率的一个重要结果，切普曼 -柯尔莫哥洛夫方程(简称为
C-K方程)，直观上可以作如下解释：马尔可夫链 { Xn,n >0}在时刻m处于状态
i，经过n步，即在时刻m+n转移到状态j的过程可以视为它在时刻 m处于状态i ,
先经过I步，即在时刻m I遍历所有状态k (k 1,2,)，然后再经过n I步，
即在时刻m+n转到状态j的转移过程(见下图)
[J] ” mH ，nr+n
C-K 方程的矩阵形式为 P（n） P（l）P（n l）
当 l 1 时，即为（ 3） P（n） PP（n 1） ，再利用归纳法可证（ 4） 在（1）中令丨1,k ，得p（n） piklpk；j1）这是一个递推公式，逐步递推可
kI
证（ 2）
例 3 （随机游动）
设质点在线段上做随机游动。 （见图）。每隔一秒钟移动一步。当质点处于‘ O' 点时，必然要以概率 1 向右移动一步至‘ 1'点；当质点处于‘ 4'点时，下一步 必然以概率 1 向左移动一步至‘ 3'点；当质点处于其它点时，下一步便均分别
以概率 向左、向右或停留在原地不动。
令Xn表示n次移动后质点所处的位置。显然，｛ Xn,n >0｝为一齐次马尔可夫链, 其状态空间为 I=｛0 ， 1 ， 2， 3， 4｝
试求｛ Xn,n >0｝的一步和二步转移概率矩阵：
解：按题意可知
同样可求得其它转移概率
于是便得一步转移概率矩阵 步转移概率矩阵便为
1. 一维分布
定义5设｛Xn，n 0｝为齐次马尔可夫链,
Pj（O） P｛X。 j｝，j I
为｛Xn，n 0｝的初始分布，Pj（0）称为初始概率。将其写成向量形式为
PtO） （5（0门2（0）, ，PN（0）,），称为初始概率向量
f 0 1 0 0 0 1
r 0 1 0 0 0 1
1 1 1 1 1 1
---00 --------- 0 0
3 3 3 3 3 3
^111 1 1 1
0 ---------- 0 0 ---------- 0
3 3 3 3 3 3
…1 1 1 1 1 1
0 0——- 0 0 -----------
3 3 3 3 3 3
0 0 0 10 Q 0 0 1 0
\
i
齐次马尔可夫链的有限维分布 r 1 i 1 0
0 3 3 3
[ 5 2 [ a g g 9 g
i 2 3 2 1
9 9 9 9 9
0 1 2 5 1
9 9
1 1 ]
为I，称下列一组概率 定义6设｛Xn，n 0｝为齐次马尔可夫链，其状态空间为I，称下列一组概率
Pj(n) Pg j｝，j I
为｛Xn，n 0｝的绝对分布，Pj(n)称为绝对概率。将其写成向量形式为
pT(n) (Pi(n), P2(n), ，PN(n),)，称为绝对概率向量。
定理2设｛Xn, n 0｝为齐次马尔可夫链，则对任意j I和n 1，绝对概率具有
下列性质
(1) Pj( n) Pi(0) Pi(n)
i I
(2) Pj( n) Pi(n 1)Pij
i I
(3) PT( n) PT (0)P(n)
(4) PT( n) PT(n 1)P
(3)( 4)式是(1)( 2)的矩阵形式。
2. n维分布
定理3设｛Xn，n 0｝为齐次马尔可夫链，对任意 m, ,in I和n 1,则马尔可 证明(1) Pj(n) P{Xn j} P{Xo i,Xn j}
i I
P{Xo i}P{Xn
i I Xo i} Pi (0)P(n)
i I
(2)Pj( n) P{Xn j} P{Xni i,Xn j}
i I
P{Xn i i}P{Xn
i I j Xn i i} Pi(n 1) Pj
i I
