第11讲 Markov链的状态分类

1、1随机数学随机数学第第11讲讲 Markov链的状态分类链的状态分类与判别与判别教师教师: 陈陈 萍萍2马氏链马氏链的等价描述：的等价描述：1)01011,nnntttNiiiE (3.1.2）2)111:. .,0,|nnnnnnnh RR stE h XnXXE h XE h XX 令=, . . . ,FF3)3 C-K方程方程.()()( )3.1.6m nmnijikkjk Sppp或或 3.1.7m nmnm nPPPP)(1)( ) ;( )(0)(3.1.9)niinn PnP定理定理3.1.411)1,nninttNiiE 101210100 11 2101(,)0nnnnn

2、tttttttttnii ii iiiP XiXiXiPPP43.2 Markov链的状态分类与判别链的状态分类与判别例例3.2.1 设系统有三种可能状态设系统有三种可能状态E= 1, 2, 3. “1”表示表示系统运行良好，系统运行良好，“2”表示运行不正常，表示运行不正常，“3”表示系表示系统失效统失效.以以Xn表示系统在时刻表示系统在时刻n的状态的状态, 并设并设Xn, n0是一是一Markov链链. 其一步转移概率矩阵为其一步转移概率矩阵为P用有向图表示为：用有向图表示为：0.10.10.30.610.95定义定义3.2.13.2.1 称状态称状态i i E E为吸收态，若为吸收态，若

3、p piiii = 1. = 1.定义定义3.2.23.2.2 对对i i, ,j j E E，若存在，若存在n n N N，使，使 ，则称自状态则称自状态i i出发可达状态出发可达状态j j，记为，记为i i j j. .如果如果i ij j且且j ji i，则称，则称i,ji,j 相通，记为相通，记为i ij j. . 定理定理3.2.1 相通是一种等价关系相通是一种等价关系,即满足即满足(1)自返性自返性 i i;(2)对称性对称性 ij,则则 ji;(3)传递性传递性 ij, jk则则 ik.6定义定义3.2.3 若一若一Markov链的任意两个状态都相通，则链的任意两个状态都相通，则

4、称为称为不可约链不可约链。定义定义3.2.4 令令 T Tijij=minn:X=minn:X0 0=i,X=i,X n n=j,n=j,n 1 1 ，称为系统称为系统在在0时刻从状态时刻从状态i出发，首次到达状态出发，首次到达状态j的时间，简称的时间，简称为首达时为首达时.且规定且规定, 若右边为空集，则若右边为空集，则T Tijij =. =.设设Xn是无限制的随机游动是无限制的随机游动, 且且p, q, r 都大于都大于0. 证明证明Xn是不可约链是不可约链 .7 定义定义3.2.5 令令 | 11 ,|00iXnkjXjXPiXnTPfknijnij 1nnijijff表示表示0时刻从

5、状态时刻从状态 i出发，经出发，经 n步转移后首次到达状步转移后首次到达状态态j 的概率，称为的概率，称为n步首达概率；由步首达概率；由i 出发，经过有出发，经过有限步首次到达状态限步首次到达状态 j 的概率为的概率为8 定义定义3.2.6 若若fii=1，则称状态，则称状态 i 为为常返态常返态; 若若fii 1，则称状态则称状态 i 为为瞬时态瞬时态（非常返态）。（非常返态）。定义定义3.2.7 如果如果fij = 1, , 记记则则 表示从表示从i i出发到达出发到达j j的平均转移时间的平均转移时间. .特别，称特别，称为从状态为从状态i出发，返回状态出发，返回状态i的平均返回时间的平

6、均返回时间.若若 0，称该数集，称该数集的最大公约数的最大公约数d(i)为状态为状态i的周期的周期.若若d(i)1，称，称i为为周周期期的，若的，若d(i)=1，称，称i为非周期的为非周期的. niip定义定义3.2.8 若状态若状态 i为正常返态的且非周期的，则称为正常返态的且非周期的，则称i为为遍历状态遍历状态. 如果如果Markov链链的所有状态都是遍历态的所有状态都是遍历态,则称该则称该Markov链是遍历的链是遍历的.13小结小结相通、相通、闭集闭集、不可约不可约状态状态常返常返瞬时瞬时正常返、正常返、零常返零常返周期周期、非周期非周期遍历遍历定理定理3.2.7 设马氏链的状态空间为

7、设马氏链的状态空间为E， i, j E，（1）若）若 i E是一个周期态，且是一个周期态，且 ij，则，则 j 也是周期也是周期态，且态，且di= dj ；（2）若此链不可约，且对）若此链不可约，且对i E有有pii 0，则此链是非，则此链是非周期链。周期链。143.3 状态空间分解定理状态空间分解定理01, ,ijkkfi jRR或任意任意Markov链的状态空间链的状态空间E可唯一分解为有限或可可唯一分解为有限或可列个互不相交的子集之和列个互不相交的子集之和其中其中 (1)N由全体瞬时态组成由全体瞬时态组成;(2)每个每个 或或 是零常返或正常返态组成的不可约是零常返或正常返态组成的不可约闭集闭集;(3)每个每个