7 马尔可夫链
马尔可夫链的概念及转移概率马尔可夫链的状态分类 状态空间的分解 pij(n) 的渐近性质与平稳分布 马尔可夫链 时间、状态都离散 马尔可夫序列 时间离散、状态连续
连续时间马尔可夫过程 时间连续、状态离散
连续马尔可夫过程（或扩散过程）时间、状态都连续 7.1 马尔可夫链的概念及转移概率
[定义] 设有随机过程 { Xn , n ?T }， 若对于任意的整数n ?T 和任意的 i0, i1, …, in+1 ?I ，条件概率满足
P{Xn?1?in?1X0?i0,X1?i1,?,Xn?in}
则称 { Xn , n ?T } 为马尔可夫链，简称马氏链。 马氏性（无后效性） P{Xn?1?in?1X0?i0,X1?i1,,Xn?in} ?P{X?iX?i}n?1n?1nn?P{Xn?1?in?1Xn?in}P{X0?i0,X1?i1,,Xn?in},Xn?1?in?1},Xn?1?in?1},Xn?1?in?1}?P{Xn?inX0?i0,X1?i1, ?P{X0?i0,X1?i1, ?P{Xn?inXn?1?in?1}?P{X0?i0,X1?i1, ?P{Xn?inXn?1?in?1}?P{Xn?1?in?1Xn?2?in?2} ?P{X1?i1X0?i0}?P{X0?i0}马尔可夫链的统计特性完全由以下条件概率所决定： P{Xn?1?in?1Xn?in}转移概率
[定义] 称条件概率
pij(n)?P{Xn?1?j Xn?i}
为马尔可夫链 { Xn , n ?T } 在时刻 n 的一步转移概率，其中 i , j ?I ，简称为转移概率。 pij(n) 不仅与状态 i , j 有关，而且与时刻 n 有关。
当 pij(n) 与时刻 n 无关时，表示马尔可夫链具有平稳转移概率，此时称齐次马尔可夫链，我们只研究齐次的，通常将齐次省略。 定义] 若对任意的 i , j ，马尔可夫链 { Xn , n 的转移概率 pij(n) 与时刻 n 无关，则称马尔可夫链是齐次的，并记为 pij (n) 为 pij 。 ?pp12p1n?11?一步转移概率矩阵 （见右面）
P??ppp222n?21?性质： (1) pij?0 , i,j?I????
(2) pij?1 , i?I 随机矩阵 j?In 步转移概率 定义] 称条件概率
?(n)pij?P{Xm?n?jXm?i}, (i,j?I, m?0, n?1)
为马尔可夫链 { Xn , n ?T } 的 n 步转移概率，并称
P(n)??p(n)ij?
p(0)ij??0, i?j????1, i?j
为马尔可夫链 的 n 步转移矩阵。规定：（右上图）
n 步转移概率 的性质
初始概率和绝对概率 初始概率：绝对概率：初始分布：
pj?P{X0?j}, (j?I)
pj(n)?P{Xn?j}, (j?I){pj}?{pj , j?I}
TP初始概率向量：(0)??p1, p2, ??
TP绝对概率向量(n)??p1(n), p2(n), ?? , (n?0)
绝对概率 pj(n) 的性质[定理] 设 { Xn , n ?T } 为马尔可夫链，则对于任意整数n ? 1 和
(n)j ? I ，绝对概率 pj (n) 具有下列性质： pj(n)??pipij(1) i?I
(2) pj(n)??pi(n?1)?pij i?I T(0)?P(n)(3) PT(n)?P (3) PT(n)?PT(n?1)?P[定理] 设 { Xn , n ? T } 是马尔可夫链，则对任意 n ? 1和 i1 , … , in ? I ，有 P?X?i, , X?i??pipii1pin?1in11nni?I
马尔可夫链的有限维分布完全由它的初始概率和一步转移概率所决定。 马尔可夫链的几个简单例子
[例1] 二进制对称信道模型——是常用于表征通信系统的错误产生机制的离散无记忆信道模型。假设某级信道输入0, 1数字信号后，其输出正确的概率为p，产生错误的概率为q，则该级信道输入状态和输出状态构成一个两状态的齐次马尔可夫链。
2设质点在数轴上游动。每次游动一格，向右游动的概率为P，向左游动的概率为q =1-P，○
若以Xn 表示质点在时刻 n 所处的位置，则{ Xn , n 是一个齐次马尔可夫链，试写出它的一步和 k 步转移概率。（上述具体解决见课件） 描述马氏链的三种方式
（1）状态转移图 （2）转移概率矩阵 （3）函数表达式 pij = f ( i , j )
??0p1q1??P??q0p22??[例] 设{ Xn , n是一个马尔可夫链，其状态空间 I = {a, b, c}，转移矩阵为
?q3 0???p3求：?P{X?b,X?c,X?a,X?cX?c}; ?1/21/41/4(1) 12340? P??2/301/3??(2) P{Xn?2?cXn?b} ??3/52/50??设 { Xn , n >0 } 是齐次马尔可夫链，其状态空间 I = { 0, 1, 2, … }，转移概率是 pij ， i , j 初始分布为{ Pj , j 。 （2）状态的常返性
首中概率——状态 i 经 n 步首次到达状态 j 的概率： (n)fij(0)?0 fij?P{Xm?n?j, Xm?v?j, 1?v?n?1Xm?i}, n?1系统从状态 i 出发，经有限步迟早会（首次）到达状态 j 的概率：
? (n)f?fijij 0?fij(n)?fij?1n?1
，
?nn 的关系 (n)(k)(n?k) pij?fijpjj?fij(n?k)p(jjk)[定理] 对任意状态 i , j 及 1 ，有 k?1k?0上式可用来求从状态 i 经 n 步首次到达状态 j 的概率： (n)n?1G.C.D {n:n?1,pii?0} ( n) (n ) ( k ) (n ? k ) 周期的等价定义
fij?pij?fijpjj ?G.C.D {n:n?1,fii(n)?0}k?1[例] （例4.8）设马尔可夫链的状态空间 I = {1, 2, 3}，其转移概率矩阵为 ? 0 p 1 q 1 ?
??P??q20p2? 求从状态1出发经n步转移首次到达各状态的概率。 ? (具体解答见课件) p 3 q 3 0 ???常返性的判别及其性质
(n)pij(n)fij与
???[定理] （1）状态 i 常返的充要条件n?0?p?(n)ii?? ,
状态 i 非常返的充要条件为n?0?pii(n)??1?? .1?fiin??
（2）若状态 i 是常返态，则 i 是零常返 i 是遍历状态
(n)limpii?1?i?0n??(n)limpii?0
(nd)limpii?d（3）若 i 是周期为 d 的常返态，则 若 i 是非常返态，则
(n)limpii?0n??n???i
（3）可达关系与互通关系
[定义] （1）若存在 n > 0, 使得 pij(n) > 0 ，则称自状态 i 可达状态 j ，并记为 i ? j 。 （2）若 i ? j , 且 j ? i , 则称状态 i 与状态 j 互通，并记为 i ? j 。 [定理1] 若 i ? j , 且 j ? k , 则 i ? k 。 若 i ? j , 且 j ? k , 则 i ? k 。
[定理2] 若 i ? j , 则（1）i 与 j 同为常返或非常返；（2）i 与 j 同为正常返或零常返；（3）i 与 j 有相同的周期。
[例] （例4.9）设马氏链的状态空间 I = {0, 1, 2, …}，其转移概率为 111p00?, pi,i?1?, pi0?, i?I 222分析各状态的类型。 7.3 状态空间的分解
[定义] 状态空间 I 的子集 C，若对于任意 i 及 k 都有 pik = 0 ，则称子集 C 为（随机）闭集。
若闭集 C 的状态互通，则称 C 为不可约的。
若马氏链{ Xn }的状态空间是不可约的，则称该马氏链为不可约。 闭集的充要条件
[定理] C 是闭集的充要条件是：
对于任意 i ? C 及 k ? C 都有 pik(n) = 0 , n ? 1。 状态 i 为吸收态（pii = 1）? 单点集 { i } 是闭集。
[例] （例4.11）设马氏链 { Xn } 的状态空间 I = { 1, 2, 3, 4, 5 } ，转移矩阵为P，试分析其闭集及不可约性。（解答见课件）
分解1——按照常返性和互通性进行
[定理] 任一马氏链的状态空间 I ，可唯一地分解成有限个或可列个互不相交的子集 D, C1, C2, … 之和，使得
（1）每个 Cn 是常返态组成的不可约闭集； （2）Cn 中的状态同类（全为正常返或零常返），它们有相同的周期，且 fjk = 1，j, k ?Cn ； （3）D 由全体非常返态组成。自 Cn 中的状态不能到达 D 中的状态。 称Cn 是基本常返闭集
[例] （例4.13）设状态空间 I = { 1, 2, … , 6 } ，转移矩阵为P，试分解此链并指出各状态的常返性及周期性。（解答见课件） 随机矩阵
?a[定义] 若矩阵 (a ij ) 的元素非负且对每个 i 都有 机矩阵。
显然，k 步转移矩阵
(k)?P(k)??pijij?1 ，则称矩阵 (a ij ) 为随
j 是随机矩阵。
是 C 上所得的 k 步转移子矩阵，则 G
[定理] 设 C 是闭集，又
(k)? ,i,j?CG??pij仍是随机矩阵。
分解2——对周期的不可约马氏链的分解
[定理] 周期为 d 的不可约马氏链，其状态空间 C 可唯一地分解为 d 个互不相交的子集之和，即
C??Gr , Gr?Gs?? , (r?s)r?0d?1
且使得自 Gr 中任一状态出发，经一步转移必进入 Gr+1 中（其中 Gd = G0 ）。 G?{ j: 对某个n?0, p(nd?r)?0 }rij
[例] （例4.14）设不可约马氏链的状态空间 C = { 1, 2, 3, 4, 5, 6 }，转移矩阵为P，试对其状态空间进行分解。。（解答见课件） 周期性不可约马氏链的子链
[定理] 设{ Xn , n ? 0 } 是周期为 d 的不可约马氏链，
（1）若只在时刻 0, d, 2d, … 上考虑 { Xn } ，即得一新马氏链（子链），其转移矩阵
(d)?P(d)??pij ，对此新链，每一子状态空间 Gr 是非周期的不可约闭集；
（2）若原马氏链 { Xn } 常返，则子链 { Xnd } 也常返。
7.4 pij(n)的渐近性质与平稳分布 对于转移概率 pij (n) 的极限n??1) 是否存在？
2) 是否与 i 有关？
（1）pij(n)的渐近性质 [定理] 若 j 非常返或零常返，则
(n)limpij?0 , ?i?In??(n)limpij
[推论1] 有限状态的马氏链，不可能全是非常返态，也不可能含有零常返态； 不可约的有限马氏链必为正常返的。
[推论2] 若马氏链有一个零常返态，则必有无限多个零常返态。 fij (r) 的定义
自状态 i 出发，在时刻 n = r ( mod( d ) ) 首次到达 j 的概率记为：
?d?1?d?1? (md?r)(md?r)fij(r)??fijm?0, 0?r?d?1显然
?fr?0ij(r)???fijm?0r?0??fij(m)?fijm?0常返或到达的平均次数
n?1?0 , 当 j 非常返或零常返(k)[定理] 对于任意状态 i , j ，有 limpij??n??n?1j ， 有??[推论] 若 { Xn } 不可约常返，则对任意 ki , fij?j, 当 j 正常返 1 n (k ) 1 limp? n??nk?1ij?j（2）平稳分布 [定义] 称绝对概率分布 { ? j , j ? I } 为齐次马氏链的平稳分布，若它满足
??令 π???i?, P??pij?, T则 π?PT?π
平稳分布
[定理] 不可约非周期马氏链是正常返的充要条件：存在平稳分布，且此平稳分布就是极限分布
??j???ipij ?i?I????i?1, ?j?0?i?I{ 1?j, j?I }
[推论1] 有限状态的不可约非周期马氏链必存在平稳分布。
[推论2] 若不可约马氏链的所有状态是非常返或零常返的，则不存在平稳分布。 [推论3] 若{ ? j , j ? I } 是不可约非周期马氏链的平稳分布，则 1limpj(n)???j n?? ?j
[例] （例4.16）设马尔可夫链的转移概率矩阵为P，求马氏链的平稳分布及各状态的平均返回时间。（解答见课件） 0.1?0.70.10.2?0.7??0.1?因为该马氏链是不可约的非周期有限状态，所以存在平稳分布。 P??0.10.8P?0.10.80.2?0.1?
??1?0.7?1 ?0.1?2?0.05? ???2?0.1?1 ?0.8?2?0.05?3 ???3?0.2?1 ?0.1?2?0.9?3???1 ??2??3?1各状态的平均返回时间分别为：
??0.050.050.9?????0.05??0.050.9???平稳分布为： ?1?0.1765, ?2?0.2353, ?3?0.5882 ?11?1??5.67, ?2?1??4.25, ?3?12??1.703