1、7 马尔可夫链内容提要q马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率q马尔可夫链的状态分类马尔可夫链的状态分类q状态空间的分解状态空间的分解q pij(n)的渐近性质与平稳分布的渐近性质与平稳分布马尔可夫过程的四种类型n马尔可夫链马尔可夫链v时间、状态都离散时间、状态都离散n马尔可夫序列马尔可夫序列v时间离散、状态连续时间离散、状态连续n纯不连续马尔可夫过程纯不连续马尔可夫过程v时间连续、状态离散时间连续、状态离散n连续马尔可夫过程（或扩散过程）连续马尔可夫过程（或扩散过程）v时间、状态都连续时间、状态都连续7.1 马尔可夫链的概念及转移概率定义 设有设有随机过程随机过程 Xn,n T
2、，若对于任意的整若对于任意的整数数n T 和任意的和任意的 i0,i1,in+1 I，条件概率满足条件概率满足则称则称 Xn,n T 为为马尔可夫链，简称，简称马氏链。,11110011nnnnnnnniXiXPiXiXiXiXP马氏性（无后效性）马尔可夫链马尔可夫链的统计特性完全由以下条件概率所决定：的统计特性完全由以下条件概率所决定：,11110011nnnnnnnniXiXPiXiXiXiXP ,000011221111111100111111001111001100iXPiXiXPiXiXPiXiXPiXiXiXPiXiXPiXiXiXPiXiXiXiXPiXiXiXPnnnnnnnn
3、nnnnnnnnnnnnnn11nnnniXiXP转移概率npij(n)不仅与状态不仅与状态 i,j 有关，而且与时刻有关，而且与时刻 n 有关。有关。n当当 pij(n)与时刻与时刻 n 无关时，表示马尔可夫链具有平稳无关时，表示马尔可夫链具有平稳转移概率。转移概率。定义 称称条件概率条件概率为马尔可夫链为马尔可夫链 Xn,n T 在时刻在时刻 n 的的一步转移概率，其中其中 i,j I，简称为简称为转移概率。)(1iXjXPnpnnij齐次马尔可夫链定义 若对任意的若对任意的 i,j I，马尔可夫链马尔可夫链 Xn,n T 的转移的转移概率概率 pij(n)与时刻与时刻 n 无关，则称无关
4、，则称马尔可夫链是马尔可夫链是齐次的，并记为的，并记为 pij(n)为为 pij 。一步转移概率矩阵性质：性质：nnpppppp2222111211PIipIjipIjijij ,1 )2(,0 )1(（随机矩阵）（随机矩阵）n 步转移概率定义 称称条件概率条件概率为马尔可夫链为马尔可夫链 Xn,n T 的的 n 步转移概率，并称，并称为马尔可夫链为马尔可夫链 的的 n 步转移矩阵。)1 ,0 ,(,)(nmIjiiXjXPpmnmnij)()(nijnpP规定：规定：jijipij ,1 ,0)0(n 步转移概率 的性质)(nijp定理 设设 Xn,n T 为马尔可夫链，为马尔可夫链，则对于
5、任意整数则对于任意整数n 0,0 l 0 是齐次马尔可夫链，其状态空间是齐次马尔可夫链，其状态空间 I=0,1,2,，转移概率是，转移概率是 pij，i,j I，初始分布，初始分布为为 Pj,j I 。786951112/31/3111111234（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，则存在正整数，则
6、存在正整数 M，对一，对一切切 n M，有，有 pii(nd)0。（2）状态的常返性首中概率状态状态 i 经经 n 步首次到达状态步首次到达状态 j 的概率的概率：1 ,11 ,)(niXnvjXjXPfmvmnmnij0)0(ijf系统从状态系统从状态 i 出发，经有限步迟早会（首次）到达出发，经有限步迟早会（首次）到达状态状态 j 的概率的概率：1)(nnijijff10)(ijnijff常返性的定义称期望值称期望值 为状态为状态 i 的的平均返回时间。1)(nniifnn若若 fii=1，则称状态，则称状态 i 是是常返的；若的；若 fii 1，则称，则称状态状态 i 是是非常返的（或的
7、（或滑过的）。的）。n若若 i ，则称常返态，则称常返态 i 是是正常返的；的；若若 i=，则称常返态，则称常返态 i 是是零常返的。的。n非周期的正常返态称为非周期的正常返态称为遍历状态。与 的关系上式可用来求从状态上式可用来求从状态 i 经经 n 步首次到达状态步首次到达状态 j 的概率：的概率：)(nijp)(nijf定理 对任意对任意状态状态 i,j I 及及 1 n 0,使得使得 pij(n)0，则称自，则称自状态状态 i 可达状态状态 j，并记为并记为 i j。（2 2）若若 i j,且且 j i,则称则称状态状态 i 与状态与状态 j 互通，并记为，并记为 i j。定理1 若若
8、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,，其，其转移概率为转移概率为分析各状态的类型。分析各状态的类型。,21)1(00f解：Iipppiii ,21 ,21 ,2101,00先考查状态先考查状态0，,412121)2(00f,21)(00nnf,121100nnf可见状态
9、可见状态0为正常返，且是非周期，因而是遍历的。为正常返，且是非周期，因而是遍历的。因为因为 i 0，故，故 i 也是遍历的。也是遍历的。7.3 状态空间的分解定义 状态空间状态空间 I 的子集的子集 C，若，若对于任意对于任意 i C 及及 k C 都有都有 pik=0，则称则称子集子集 C 为为（随机）（随机）闭集。若闭集若闭集 C 的状态互通，则称的状态互通，则称 C 为为不可约的。的。若马氏链若马氏链 Xn 的状态空间是不可约的，的状态空间是不可约的，则称该马氏链为则称该马氏链为不可约。闭集的充要条件状态状态 i 为为吸收态吸收态（pii=1）单点集单点集 i 是闭集。是闭集。定理 C
10、是闭集的充要条件是：是闭集的充要条件是：对于任意对于任意 i C 及及 k C 都有都有 pik(n)=0,n 1。例（例（例4.11）设马氏链设马氏链 Xn 的状态空间的状态空间 I=1,2,3,4,5 ，转移矩阵为，转移矩阵为P，试分析其闭集及不可约性。，试分析其闭集及不可约性。000100000100100005.005.005.0005.0P1/21/21/211/211状态状态 3为吸收态，故为吸收态，故 3 是闭集；是闭集；1,4 ，1,4,3，1,4,2,3 都是闭集；都是闭集；3 和和 1,4 是不可约闭集；是不可约闭集；因为因为 I 含有闭子集，故马氏链含有闭子集，故马氏链
11、Xn 不是不可约链。不是不可约链。分解1按照常返性和互通性进行定理 任一马氏链的状态空间任一马氏链的状态空间 I，可唯一地分解成有限，可唯一地分解成有限个或可列个互不相交的子集个或可列个互不相交的子集 D,C1,C2,之和，使得之和，使得（1）每个）每个 Cn 是常返态组成的不可约闭集；是常返态组成的不可约闭集；（2）Cn 中的状态同类（全为正常返或零常返），它们有中的状态同类（全为正常返或零常返），它们有相同的周期，且相同的周期，且 fjk=1，j,k Cn；（3）D 由全体非常返态组成。自由全体非常返态组成。自 Cn 中的状态不能到达中的状态不能到达 D 中的状态。中的状态。称称Cn 是基
12、本常返闭集是基本常返闭集例（例（例4.13）设设状态空间状态空间 I=1,2,6 ，转移矩阵为，转移矩阵为P，试分解此链并指出各状态的常返性及周期性。，试分解此链并指出各状态的常返性及周期性。2/10002/10000001003/103/13/1010000100000000100P1/31/31/211/21111/36 ,25 ,3 ,1421CCDI随机矩阵定义 若若矩阵矩阵(a ij)的元素非负且对每个的元素非负且对每个 i 都有都有 ，则则称称矩阵矩阵(a ij)为为随机矩阵。显然，显然，k 步转移矩阵步转移矩阵 是随机矩阵是随机矩阵。)()(kijkpP1jija定理 设设 C
13、是闭集，又是闭集，又 是是 C 上所上所得的得的 k 步转移子矩阵，则步转移子矩阵，则 G 仍是随机矩阵。仍是随机矩阵。Cjipkij,)(G分解2对周期的不可约马氏链的分解定理 周期为周期为 d 的不可约马氏链，其状态空间的不可约马氏链，其状态空间 C 可唯一可唯一地分解为地分解为 d 个互不相交的子集之和个互不相交的子集之和，即，即且使得自且使得自 Gr 中任一状态出发，经一步转移必进入中任一状态出发，经一步转移必进入 Gr+1 中（其中中（其中 Gd=G0）。）。)(,10srGGGCsrdrr 0 ,0 :)(rndijrpnjG对某个例（例（例4.14）设不可约马氏链设不可约马氏链的
14、状态空间的状态空间 C=1,2,3,4,5,6，转移矩阵为，转移矩阵为P，试对其状态空间进行分解。，试对其状态空间进行分解。04/304/1000000100001000000103/103/1003/102/102/100P3/41/31/211/2111/31/31/425 ,36 ,4 ,1210GGGC1,4,63,52111周期性不可约马氏链的子链定理 设设 Xn,n 0 是是周期为周期为 d 的不可约马氏链，的不可约马氏链，（1）若只在时刻）若只在时刻 0,d,2d,上考虑上考虑 Xn ，即得一新马，即得一新马氏链（子链），其转移矩阵氏链（子链），其转移矩阵 ，对此新，对此新链，每
15、一子状态空间链，每一子状态空间 Gr 是非周期的不可约闭集；是非周期的不可约闭集；（2）若原马氏链）若原马氏链 Xn 常返，则子链常返，则子链 Xnd 也常返。也常返。)()(dijdpP例（例例4.15）设设 Xn 是例是例4.14中的中的马氏链，已知马氏链，已知 d=3，则则 X3n,n 0 的转移矩阵为的转移矩阵为3/103/1003/1012/5012/7003/103/1003/1012/5012/7000000103/103/1003/1)3(P15/125/127/127/121/31/31/31/31/31/31/325 ,36 ,4 ,1210GGG7.4 pij(n)的渐近
16、性质与平稳分布n是否存在？是否存在？n是否与是否与 i 有关？有关？)(limnijnp对于转移概率对于转移概率 pij(n)的极限的极限（1）pij(n)的渐近性质推论1 有限状态的马氏链，不可能全是非常返态，有限状态的马氏链，不可能全是非常返态，也不可能含有零常返态；也不可能含有零常返态；不可约的有限马氏链必为正常返的。不可约的有限马氏链必为正常返的。定理 若若 j 非常返或零常返非常返或零常返，则，则Iipnijn ,0lim)(推论2 若马氏链有一个零常返态，则必有无限多个若马氏链有一个零常返态，则必有无限多个零常返态。零常返态。fij(r)的定义自状态自状态 i 出发，在时刻出发，在
17、时刻 n=r(mod(d)首次到达首次到达 j 的概率记为：的概率记为：10 ,)(0)(drfrfmrmdijij显然，显然，ijmmijmdrrmdijdrijfffrf0)(010)(10)(正常返态的渐近性定理 若若 j 正常返正常返，周期为，周期为 d，则对任意，则对任意 i 及及 0 r d 1，有有jijrndijndrfp)(lim)(推论 对于不可约、对于不可约、周期为周期为 d 的正常返马氏链，其状态空的正常返马氏链，其状态空间为间为 C，则对任意，则对任意 i,j C，有有其它同属于子集当 ,0,lim)(sjndijnGjidp常返或到达的平均次数定理 对于任意状态对于
18、任意状态 i,j，有，有推论 若若 Xn 不可约不可约常返，则对任意常返，则对任意 i,j，有有正常返当非常返或零常返当 ,01lim1)(jfjpnjijnkkijnjnkkijnpn11lim1)(（2）平稳分布定义 称绝对概率分布称绝对概率分布 j,j I 为齐次马氏链的为齐次马氏链的平稳分布，若它满足，若它满足0 ,1 jIiiIiijijpPPTijTip ,则令平稳分布定理 不可约非周期马氏链是正常返的充要条件：不可约非周期马氏链是正常返的充要条件：存在平稳分布，且此平稳分布就是极限分布存在平稳分布，且此平稳分布就是极限分布 ,1 Ijj推论1 有限状态的不可约非有限状态的不可约非
19、周期马氏链必存在平稳分布。周期马氏链必存在平稳分布。推论2 若不可约若不可约马氏链的所有状态是非常返或零常返的，则马氏链的所有状态是非常返或零常返的，则不存在平稳分布。不存在平稳分布。推论3 若若 j,j I 是不可约非是不可约非周期马氏链的平稳分布，则周期马氏链的平稳分布，则jjjnnp1)(lim例（例例4.16）设马尔可夫链设马尔可夫链的转移概率矩阵为的转移概率矩阵为P，求马，求马氏链的平稳分布及各状态的平均返回时间。氏链的平稳分布及各状态的平均返回时间。9.005.005.01.08.01.02.01.07.0P解：因为该因为该马氏链是马氏链是不可约的非不可约的非周期周期有有限状态限状态，所以存在平稳分布。所以存在平稳分布。各状态的平均返回时间分别各状态的平均返回时间分别为：为：1 0.90.1 2.00.050.8 1.00.050.1 7.032132133212211平稳分布为：平稳分布为：5882.0 ,2353.0 ,1765.032170.11 ,25.41 ,67.51332211
