13第四章马尔可夫链

1、1 第四章第四章 马尔可夫链马尔可夫链 v马尔可夫链马尔可夫链定义定义 v一步转移概率一步转移概率及及多步转移概率多步转移概率 v初始概率初始概率及及绝对概率绝对概率 vChapman-Kolmogorov（C-K）方程）方程 v遍历遍历的马尔可夫链及的马尔可夫链及平稳分布平稳分布 v马尔可夫链马尔可夫链状态分类状态分类 2 时间、状态都是离散的马尔可夫过程，称时间、状态都是离散的马尔可夫过程，称 为为马尔可夫链。马尔可夫链。 例如：天气预报例如：天气预报 质点的随机游动质点的随机游动 3 例如例如：在某数字通信系统中传递：在某数字通信系统中传递0，1两种两种 信号，且传递需要经过若干级。因为

2、系统中有信号，且传递需要经过若干级。因为系统中有 噪声，各级将造成错误，若某级输入噪声，各级将造成错误，若某级输入0，1信号信号 后，其输出不产生错误的概率为后，其输出不产生错误的概率为p，产生错误，产生错误 的概率为的概率为1-p，则该级的输入输出状态构成了，则该级的输入输出状态构成了 一个两个状态的一个两个状态的马氏链马氏链。 4 马尔可夫链定义马尔可夫链定义 设有随机过程设有随机过程Xn,nT，若对于任意的整数，若对于任意的整数 nT和任意的和任意的i0,i1, ,in+1I，条件概率满足，条件概率满足 | ,| 11 110011 nnnn nnnn iXiXP iXiXiXiXP 则

3、称则称Xn,nT为马尔可夫链，简称马氏链为马尔可夫链，简称马氏链 将来的状态只与当前状态有关，与过去状态无关将来的状态只与当前状态有关，与过去状态无关 5 为了描述马尔可夫链（为了描述马尔可夫链（n+1）维分布率，）维分布率， 最重要的是最重要的是条件概率条件概率PXn+1=in+1|Xn=in. 它它 表示在表示在时刻时刻n取取in值的条件下，下一时刻值的条件下，下一时刻 n+1取值为取值为in+1的概率的概率（一步转移概率一步转移概率） 6 定义定义4.2 称条件概率称条件概率 为马尔可夫链为马尔可夫链Xn,nT在在时刻时刻n的的一步转移概一步转移概 率率，其中，其中i,jI，简称，简称转

4、移概率转移概率。 |)( 1 iXjXPnp nnij 定义定义4.3 若对任意的若对任意的i,jI，马尔可夫链，马尔可夫链Xn,nT的的转移转移 概率与概率与n无关无关，则称马尔可夫链是，则称马尔可夫链是齐次齐次马尔可夫马尔可夫 链。我们只讨论齐次马氏链。链。我们只讨论齐次马氏链。 并将并将 记为记为( ) ij pnij p 7 设设P表示一步转移概率所组成的矩阵，则表示一步转移概率所组成的矩阵，则 n n p p pp pp P 2 1 2221 1211 称为系统状态的称为系统状态的一步转移概率矩阵一步转移概率矩阵，它具有，它具有 如下性质：如下性质： 1. Ijip ij ,0 Ij

5、ip Ij ij , 1 满足上述两个性质的矩阵成为满足上述两个性质的矩阵成为随机矩阵随机矩阵 8 定义定义4.4 称条件概率称条件概率 为马尔可夫链为马尔可夫链Xn,nT的的n步转移概率步转移概率，并称，并称 1, 0,| )( nmIjiiXjXPp mnm n ij )( )()(n ij n pP 为马尔可夫链的为马尔可夫链的n步转移矩阵步转移矩阵。规定。规定 (0) 0, 1, ij ij p ij ( )( )( ) 11121 ( )( )( ) 21222 nnn m nnn m ppp ppp 9 例题例题 设马尔可夫链设马尔可夫链Xn,nT有状态空间有状态空间I=0,1，

6、其一步转移概率矩阵为其一步转移概率矩阵为 1110 0100 pp pp P 求求 和两步转移概率矩阵和两步转移概率矩阵P(2) 0| 0 2 mm XXP 10 解：解： (2) m 2m 00m 2m m m 2mm 2m mm m 2m 1m m m 2 m 1m 1 m 1m mm m 1m 1 m PX0,X0 PPX0|X0 PX0 PX0,X0PX0,X0 PX0PX X0,X1 PX0,X0 PX0,X 0 PX0,X0,X0 PX0 PX0,X1 0 ,X0 P X m m 1m m 1m 2m 1mm 1m m 2m 1mm 1m PX0 PX0|X0,X0PX0|X0 P

7、X 1,X0 P 0|X1,X0PX1|X X1,X0 0 11 (2) 000001 (2) 20101 (2)(2) 10111 00 1001111 PP P PPP PPPP PPP m2m1m1m m2m1m1m (1)(1)(1)(1) 00001001 00001001 PX0|X0PX0|X0 PX0 | X1PX1|X0 =PPPP =P PP P nn PP )( 结论：结论：n步转移矩阵步转移矩阵 )2( P 12 定理定理4.1 设设Xn,nT为马尔可夫链，则对任意整数为马尔可夫链，则对任意整数 n0，0L0非空，则称该集合的非空，则称该集合的 最大公约数最大公约数d=

8、d(i)=G.C.Dn:pii(n)0为状态为状态i 的周期。如的周期。如d1就称就称i为为周期的周期的，如如d=1就称就称i 为为非周期的非周期的。 由定义知由定义知,当当n不能被不能被d整除时整除时,pii(n)=0 引理引理4.1 如如i的周期为的周期为d，则存在正整数，则存在正整数M，对一切，对一切nM， 有有pii(nd)0。 38 例题例题:设有设有4个状态的马尔可夫链个状态的马尔可夫链,它的一步转移概它的一步转移概 率矩阵为率矩阵为: 画出其画出其状态传递图状态传递图,该过程是否具有周期性该过程是否具有周期性? 解解: 001/ 21/ 2 001/ 21/ 2 1/ 21/ 2

9、00 1/ 21/ 200 39 001/ 21/ 2 001/ 21/ 2 1/ 21/ 200 1/ 21/ 200 所有状态周期为所有状态周期为2 40 状态转移图状态转移图 状态状态2和和3具有相同的周期具有相同的周期,但是状态但是状态 2,3有区别有区别.为此引入为此引入常返性常返性的概念。的概念。 41 首中概率首中概率 它表示质点由它表示质点由i出发，经出发，经n步首次到达步首次到达j 的概率，的概率， 表示为表示为 )|, 11 ,( )( iXjXnvjXPf mnmvm n ij 同时我们令同时我们令 表示表示质点由质点由i出发，经有限步终于到达出发，经有限步终于到达j 的

10、概率的概率。 1 )( n n ijij ff 42 定义4.7 称状态称状态i为为常返的常返的，如如fii=1；称状态；称状态i为为非常返的非常返的 (滑过态滑过态)，如如fii1。 对于常返态对于常返态i，由定义知，由定义知fii(n),n1构成一概率构成一概率 分布，此分布的期望值分布，此分布的期望值 1 )( n n iii nf 表示由表示由i出发再返回的出发再返回的i的的平均返回时间平均返回时间。 43 定义4.8 如如ui0,即由状态即由状态i出发，出发， 经过经过n次转移以正的次转移以正的 概率达到状态概率达到状态j，则称自状态，则称自状态i可可到达到达状态状态j,并记并记 为

11、为 。反之如果状态。反之如果状态i不能到达不能到达j，记为，记为 例如：例如：无限制的随机游动中，每个状态都能够无限制的随机游动中，每个状态都能够 到达任何其它状态。当时在带有吸收壁的随机到达任何其它状态。当时在带有吸收壁的随机 游动中，吸收状态却不同到达其他状态。游动中，吸收状态却不同到达其他状态。 ij i j 47 定义定义：互通互通 有两个状态有两个状态i和和j，如果由状态，如果由状态i可以到达状态可以到达状态 j,且由状态且由状态j也可以到达状态也可以到达状态i，则称状态，则称状态i，j互互 通通。记为：。记为： 定理定理: 如果由状态如果由状态i可以到达可以到达j状态状态,由由j状

12、态可状态可 以到达以到达k状态状态,则由则由i状态可以到达状态可以到达k状态。状态。 证明：证明： ij 48 状态状态i特性（常返和非常返）的判断准则特性（常返和非常返）的判断准则： 定理定理4.5(证明见证明见P53) 状态状态i常返常返的充要条件为：的充要条件为： ( ) 0 n ii n p 状态状态i非常返非常返的充要条件为：的充要条件为： ( ) 0 1 1 n ii n ii p f 49 零常返和正常返的判断准则零常返和正常返的判断准则： 定理定理4.7以及推论以及推论 状态状态i常返，则：常返，则： （1）零常返）零常返 （2）正常返）正常返 ( ) n lim0 n ii

13、p ( ) n lim0 n ii p 其中，周期为其中，周期为d时候时候, ( ) n lim n ii i d p u 非周期时非周期时,（遍历）（遍历） ( ) n 1 lim n ii i p u (非周期的正常返称为遍历状态遍历状态) 50 定理定理4.9 如果状态如果状态i,j互通，则：互通，则： （1）i和和j同为常返或非常返同为常返或非常返。如为常返，。如为常返，同同 为正常返或零常返为正常返或零常返。 （2） i和和j有有相同的周期相同的周期。 51 判断各状态的性质（从常返和周期性两方面）判断各状态的性质（从常返和周期性两方面） 52 解：解： 53 状态空间的分解 Ci

14、Ck 定义定义： 状态空间状态空间I的子集的子集C称为称为闭集闭集，如果对任意，如果对任意 及及 都有都有 0 ik p 定义：定义： 闭集闭集C称为称为不可约不可约的，如果的，如果C的状态互通。的状态互通。 定义：定义： 马尔可夫链称为不可约马尔可夫链称为不可约的，如果其状态空间不可的，如果其状态空间不可 约。约。 54 如果单个状态构成一个闭集，则称这个闭集如果单个状态构成一个闭集，则称这个闭集 为为吸收态吸收态。它是比较小的闭集。它是比较小的闭集。 （1）闭集意味着质点一旦进入闭集中，将永闭集意味着质点一旦进入闭集中，将永 远留在该闭集中。远留在该闭集中。 （2）一个大的闭集可以包含几个

15、小的闭集。）一个大的闭集可以包含几个小的闭集。 55 问：找出该马氏链中所有闭集，马氏链是否不问：找出该马氏链中所有闭集，马氏链是否不 可约？可约？ 例题例题4.11 设马氏链设马氏链Xn的状态空间的状态空间I=1,2,3,4,5,转转 移矩阵为移矩阵为: 1/ 2001/ 20 1/ 201/ 200 00100 10000 01000 56 状态空间的分解定理：状态空间的分解定理： 任一马尔可夫链的状态空间任一马尔可夫链的状态空间I，可唯一的分解成，可唯一的分解成 有限个或可列个互不相交的子集有限个或可列个互不相交的子集D,C1,C2, 之和，使得之和，使得 每一每一Cn是常返态是常返态组

16、成的组成的不可约闭集不可约闭集； Cn中的状态同类，或中的状态同类，或全是正常返全是正常返，或，或全是零全是零 常返常返。它们有相同的周期且。它们有相同的周期且fjk=1,j,kCn。 D由全体非常返状态由全体非常返状态组成，自组成，自Cn中的状态不中的状态不 能到达能到达D中的状态。中的状态。 57 例题例题4.13.设设I=1,2,6,转移矩阵为转移矩阵为: 试分解此链并指出各状态的试分解此链并指出各状态的常返性常返性及及周期性周期性. 001000 000001 000010 1/31/301/300 100000 01/ 20001/ 2 58 12 41,3,52,6IDCC 59 推论：推论： (1)不可约的有限马尔可夫链必为正常返