刘次华《随机过程及其应用(第三版)》课件7c资料

1、7 马尔可夫链 内容提要 q马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 q马尔可夫链的状态分类马尔可夫链的状态分类 q状态空间的分解状态空间的分解 q pij(n) 的渐近性质与平稳分布的渐近性质与平稳分布 马尔可夫过程的四种类型 n马尔可夫链马尔可夫链 v时间、状态都离散时间、状态都离散 n马尔可夫序列马尔可夫序列 v时间离散、状态连续时间离散、状态连续 n纯不连续马尔可夫过程纯不连续马尔可夫过程 v时间连续、状态离散时间连续、状态离散 n连续马尔可夫过程（或扩散过程）连续马尔可夫过程（或扩散过程） v时间、状态都连续时间、状态都连续 7.1 马尔可夫链的概念及转移概率 定义 设有

2、设有随机过程随机过程 Xn , n T ， 若对于任意的整若对于任意的整 数数n T 和任意的和任意的 i0, i1, , in+1 I ，条件概率满足条件概率满足 则称则称 Xn , n T 为为马尔可夫链，简称，简称马氏链。 , 11 110011 nnnn nnnn iXiXP iXiXiXiXP 马氏性 （无后效性） 马尔可夫链马尔可夫链的统计特性完全由以下条件概率所决定：的统计特性完全由以下条件概率所决定： , 11 110011 nnnn nnnn iXiXP iXiXiXiXP , , , , 000011 221111 11110011 111100 111100 1100 i

3、XPiXiXP iXiXPiXiXP iXiXiXPiXiXP iXiXiXP iXiXiXiXP iXiXiXP nnnnnnnn nnnnnn nn nnnn nn 11nnnn iXiXP 转移概率 npij(n) 不仅与状态不仅与状态 i , j 有关，而且与时刻有关，而且与时刻 n 有关。有关。 n当当 pij(n) 与时刻与时刻 n 无关时，表示马尔可夫链具有平稳无关时，表示马尔可夫链具有平稳 转移概率。转移概率。 定义 称称条件概率条件概率 为马尔可夫链为马尔可夫链 Xn , n T 在时刻在时刻 n 的的一步转移概率， 其中其中 i , j I ，简称为简称为转移概率。 )(

4、1 iXjXPnp nnij 齐次马尔可夫链 定义 若对任意的若对任意的 i , j I ，马尔可夫链马尔可夫链 Xn , n T 的转移的转移概率概率 pij(n) 与时刻与时刻 n 无关，则称无关，则称马尔可夫链是马尔可夫链是 齐次的，并记为的，并记为 pij (n) 为为 pij 。 一步转移概率矩阵 性质：性质： n n ppp ppp 22221 11211 P Iip Ijip Ij ij ij , 1 )2( , , 0 )1 ( （随机矩阵）（随机矩阵） n 步转移概率 定义 称称条件概率条件概率 为马尔可夫链为马尔可夫链 Xn , n T 的的 n 步转移概率，并称，并称 为

5、马尔可夫链为马尔可夫链 的的 n 步转移矩阵。 ) 1 , 0 ,( , )( nmIjiiXjXPp mnm n ij )()(n ij n pP 规定：规定： ji ji pij , 1 , 0 )0( n 步转移概率 的性质 )(n ij p 定理 设设 Xn , n T 为马尔可夫链，为马尔可夫链，则对于任意整数则对于任意整数 n 0, 0 l 0 是齐次马尔可夫链，其状态空间是齐次马尔可夫链，其状态空间 I = 0, 1, 2, ，转移概率是，转移概率是 pij ， i , j I ，初始分布，初始分布 为为 Pj , j I 。 7 8 6 9 5 1 1 1 2/3 1/3 1

6、1 1 1 1 1 2 3 4 （1）状态的周期性 定义 如集合如集合 n : n 1, pii(n) 0 非空，则称该集合非空，则称该集合 的最大公约数的最大公约数 d = d(i) = G.C.D n : pii(n) 0 为状态为状态 i 的的周期。 如如 d 1 就称就称 i 为为周期的；如的；如 d = 1 就称就称 i 为为非周期的。的。 定理 如果如果状态状态 i 的周期为的周期为d ，则存在正整数，则存在正整数 M，对一，对一 切切 n M ，有，有 pii(nd) 0 。 （2）状态的常返性 首中概率状态状态 i 经经 n 步首次到达状态步首次到达状态 j 的概率的概率： 1

7、 ,11 , , )( niXnvjXjXPf mvmnm n ij 0 )0( ij f 系统从状态系统从状态 i 出发，经有限步迟早会（首次）到达出发，经有限步迟早会（首次）到达 状态状态 j 的概率的概率： 1 )( n n ijij ff10 )( ij n ij ff 常返性的定义 称期望值称期望值 为状态为状态 i 的的平均返回时间。 1 )( n n ii fn n若若 fii = 1，则称状态，则称状态 i 是是常返的；若的；若 fii 1，则称，则称 状态状态 i 是是非常返的（或的（或滑过的）。的）。 n若若 i ，则称常返态，则称常返态 i 是是正常返的；的； 若若 i

8、= ，则称常返态，则称常返态 i 是是零常返的。的。 n非周期的正常返态称为非周期的正常返态称为遍历状态。 与 的关系 上式可用来求从状态上式可用来求从状态 i 经经 n 步首次到达状态步首次到达状态 j 的概率：的概率： )(n ij p )(n ij f 定理 对任意对任意状态状态 i , j I 及及 1 n 0, 使得使得 pij(n) 0 ，则称自，则称自状态状态 i 可达状态状态 j ， 并记为并记为 i j 。 （2 2）若若 i j , 且且 j i , 则称则称状态状态 i 与状态与状态 j 互通，并记为，并记为 i j 。 定理1 若若 i j , 且且 j k , 则则

9、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, ，其，其 转移概率为转移概率为 分析各状态的类型。分析各状态的类型。 , 2 1 )1( 00 f 解： Iippp iii , 2 1 , 2 1 , 2 1 01,00 先考查状态先考查状态0， , 4 1 2

10、1 2 1 )2( 00 f, 2 1 )( 00 n n f, 1 2 1 1 00 n n f 可见状态可见状态0为正常返，且是非周期，因而是遍历的。为正常返，且是非周期，因而是遍历的。 因为因为 i 0 ，故，故 i 也是遍历的。也是遍历的。 7.3 状态空间的分解 定义 状态空间状态空间 I 的子集的子集 C，若，若对于任意对于任意 i C 及及 k C 都有都有 pik = 0 ，则称则称子集子集 C 为为（随机）（随机）闭集。 若闭集若闭集 C 的状态互通，则称的状态互通，则称 C 为为不可约的。的。 若马氏链若马氏链 Xn 的状态空间是不可约的，的状态空间是不可约的，则称该马氏链

11、为则称该马氏链为 不可约。 闭集的充要条件 状态状态 i 为为吸收态吸收态（pii = 1） 单点集单点集 i 是闭集。是闭集。 定理 C 是闭集的充要条件是：是闭集的充要条件是： 对于任意对于任意 i C 及及 k C 都有都有 pik(n) = 0 , n 1。 例 （例（例4.11）设马氏链设马氏链 Xn 的状态空间的状态空间 I = 1, 2, 3, 4, 5 ，转移矩阵为，转移矩阵为P，试分析其闭集及不可约性。，试分析其闭集及不可约性。 00010 00001 00100 005 . 005 . 0 05 . 0005 . 0 P 1/2 1/21/2 11/2 1 1 状态状态 3

12、为吸收态，故为吸收态，故 3 是闭集；是闭集； 1, 4 ， 1, 4, 3 ， 1, 4, 2, 3 都是闭集；都是闭集； 3 和和 1, 4 是不可约闭集；是不可约闭集； 因为因为 I 含有闭子集，故马氏链含有闭子集，故马氏链 Xn 不是不可约链。不是不可约链。 分解1按照常返性和互通性进行 定理 任一马氏链的状态空间任一马氏链的状态空间 I ，可唯一地分解成有限，可唯一地分解成有限 个或可列个互不相交的子集个或可列个互不相交的子集 D, C1, C2, 之和，使得之和，使得 （1）每个）每个 Cn 是常返态组成的不可约闭集；是常返态组成的不可约闭集； （2）Cn 中的状态同类（全为正常返

13、或零常返），它们有中的状态同类（全为正常返或零常返），它们有 相同的周期，且相同的周期，且 fjk = 1，j, k Cn ； （3）D 由全体非常返态组成。自由全体非常返态组成。自 Cn 中的状态不能到达中的状态不能到达 D 中的状态。中的状态。 称称Cn 是基本常返闭集是基本常返闭集 例 （例（例4.13）设设状态空间状态空间 I = 1, 2, , 6 ，转移矩阵为，转移矩阵为 P，试分解此链并指出各状态的常返性及周期性。，试分解此链并指出各状态的常返性及周期性。 2/10002/10 000001 003/103/13/1 010000 100000 000100 P 1/3 1/3

14、1/2 1 1/2 1 1 1 1/3 6 , 25 , 3 , 14 21 CCDI 随机矩阵 定义 若若矩阵矩阵 (a ij ) 的元素非负且对每个的元素非负且对每个 i 都有都有 ， 则则称称矩阵矩阵 (a ij ) 为为随机矩阵。 显然，显然，k 步转移矩阵步转移矩阵 是随机矩阵是随机矩阵。 )()(k ij k pP 1 j ij a 定理 设设 C 是闭集，又是闭集，又 是是 C 上所上所 得的得的 k 步转移子矩阵，则步转移子矩阵，则 G 仍是随机矩阵。仍是随机矩阵。 Cjip k ij , )( G 分解2对周期的不可约马氏链的分解 定理 周期为周期为 d 的不可约马氏链，其状

15、态空间的不可约马氏链，其状态空间 C 可唯一可唯一 地分解为地分解为 d 个互不相交的子集之和个互不相交的子集之和，即，即 且使得自且使得自 Gr 中任一状态出发，经一步转移必进入中任一状态出发，经一步转移必进入 Gr+1 中（其中中（其中 Gd = G0 ）。）。 )( , , 1 0 srGGGC sr d r r 0 ,0 : )( rnd ijr pnjG对某个 例 （例（例4.14）设不可约马氏链设不可约马氏链的状态空间的状态空间 C = 1, 2, 3, 4, 5, 6 ，转移矩阵为，转移矩阵为P，试对其状态空间进行分解。，试对其状态空间进行分解。 04/304/ 100 0000

16、10 000100 000010 3/ 103/ 1003/ 1 02/ 102/ 100 P 3/41/3 1/2 1 1/2 1 1 1/3 1/3 1/4 25 , 36 , 4 , 1 210 GGGC 1,4,63,5 2 1 1 1 周期性不可约马氏链的子链 定理 设设 Xn , n 0 是是周期为周期为 d 的不可约马氏链，的不可约马氏链， （1）若只在时刻）若只在时刻 0, d, 2d, 上考虑上考虑 Xn ，即得一新马，即得一新马 氏链（子链），其转移矩阵氏链（子链），其转移矩阵 ，对此新，对此新 链，每一子状态空间链，每一子状态空间 Gr 是非周期的不可约闭集；是非周期的不

17、可约闭集； （2）若原马氏链）若原马氏链 Xn 常返，则子链常返，则子链 Xnd 也常返。也常返。 )()(d ij d pP 例 （例例4.15）设设 Xn 是例是例4.14中的中的马氏链，已知马氏链，已知 d = 3， 则则 X3n , n 0 的转移矩阵为的转移矩阵为 3/103/1003/1 012/5012/700 3/103/1003/1 012/5012/700 000010 3/103/1003/1 )3( P 1 5/12 5/12 7/12 7/12 1/3 1/3 1/31/3 1/3 1/3 1/3 2 5 , 3 6 , 4 , 1 2 1 0 G G G 7.4 p

18、ij(n)的渐近性质与平稳分布 n是否存在？是否存在？ n是否与是否与 i 有关？有关？ )( lim n ij n p 对于转移概率对于转移概率 pij (n) 的极限的极限 （1）pij(n)的渐近性质 推论1 有限状态的马氏链，不可能全是非常返态，有限状态的马氏链，不可能全是非常返态， 也不可能含有零常返态；也不可能含有零常返态； 不可约的有限马氏链必为正常返的。不可约的有限马氏链必为正常返的。 定理 若若 j 非常返或零常返非常返或零常返，则，则 Iip n ij n , 0lim )( 推论2 若马氏链有一个零常返态，则必有无限多个若马氏链有一个零常返态，则必有无限多个 零常返态。零

19、常返态。 fij (r) 的定义 自状态自状态 i 出发，在时刻出发，在时刻 n = r ( mod( d ) ) 首次到达首次到达 j 的概率记为：的概率记为： 10 ,)( 0 )( drfrf m rmd ijij 显然，显然， ij m m ij m d r rmd ij d r ij fffrf 0 )( 0 1 0 )( 1 0 )( 正常返态的渐近性 定理 若若 j 正常返正常返，周期为，周期为 d ，则对任意，则对任意 i 及及 0 r d 1， 有有 j ij rnd ij n d rfp )(lim )( 推论 对于不可约、对于不可约、周期为周期为 d 的正常返马氏链，其状

20、态空的正常返马氏链，其状态空 间为间为 C ，则对任意，则对任意 i , j C ， 有有 其它 同属于子集当 , 0 , , lim )(sjnd ij n Gjid p 常返或到达的平均次数 定理 对于任意状态对于任意状态 i , j ，有，有 推论 若若 Xn 不可约不可约常返，则对任意常返，则对任意 i , j ， 有有 正常返当 非常返或零常返当 , , 0 1 lim 1 )( jf j p n jij n k k ij n j n k k ij n p n 11 lim 1 )( （2）平稳分布 定义 称绝对概率分布称绝对概率分布 j , j I 为齐次马氏链的为齐次马氏链的 平稳分布，若它满足，若它满足 0 , 1 j Ii i Ii