1、（优选）第六章马尔可夫链Markov 过程过程 安德雷安德雷.安德耶维奇安德耶维奇.马尔可夫马尔可夫 (A.A.Markov): 俄数学家，俄数学家，18561922 概率和统计领域专家。概率和统计领域专家。 当年当年Markov研究普希金诗歌里元音字母和研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了辅音字母交替出现的规律时提出了Markov过程的过程的数学模型数学模型 Markov过程过程80年代兴起，在现代工程、自然年代兴起，在现代工程、自然科学、社会科学中应用广泛。科学、社会科学中应用广泛。2022-4-22Markov过程过程1马尔可夫性马尔可夫性通俗地说，通俗地说，就是在知
2、道过程现在的条件下，其就是在知道过程现在的条件下，其将来的条件分布不依赖于过去，将来的条件分布不依赖于过去，则称则称),(TttX具有具有马尔可夫（马尔可夫（Markov)性。性。定义定义设设),(TttX是一个随机过程，如果是一个随机过程，如果),(TttX在在t0时刻所处的状态为已知，它在时刻所处的状态为已知，它在时刻时刻0tt 所处状态的条件分布与其在所处状态的条件分布与其在 t0 之前之前 所处的状态无关。所处的状态无关。0tt现在0tt将来0tt过去2. 马尔可夫过程马尔可夫过程定义定义 设设),(TttX的状态空间为S,122,nntttT 如果对( ),1,2,1iiiX txx
3、Sin在条件下)(ntX的条件分布函数恰好等于11()nnX tx在条件下的条件分布函数,即11221111( ),( ),()( )(,)()nnnnnnnnnP X txP X txX txX txX txXRtxx( ),X t tT马尔则称为可夫过程.3.马尔可夫链马尔可夫链定义定义 参数集和状态空间都是离散的马尔可夫过程参数集和状态空间都是离散的马尔可夫过程称为马尔可夫链。称为马尔可夫链。注注 只讨论马尔可夫链的状态空间为有限或可列无限只讨论马尔可夫链的状态空间为有限或可列无限.则马尔可夫性可表示为则马尔可夫性可表示为12122, , ,nnntttT i iiS 对11111122
4、()( ),( )( )(),),nnnnnnnnnP X tiP X tixX tiX tiRX tiX ti有2022-4-227 时间时间离散离散状态状态离散离散的的马尔科夫链马尔科夫链 时间时间离散离散状态状态连续连续的马尔科夫序列的马尔科夫序列 时间时间连续连续状态状态连续连续的马尔科夫过程的马尔科夫过程 时间时间连续连续状态状态离散离散的马尔科夫过程的马尔科夫过程Markov过程过程8/32 第六章 Markov链第一节 基本概念第二节 Markov链的状态分类及性质第三节 极限定理及平稳分布第四节 Markov链的应用9/32 第六章 Markov链第一节 基本概念1. 1. 转
5、移概率转移概率. Chapman-. Chapman-kolmogorovkolmogorov方程方程3. Markov3. Markov链的分布链的分布4.4.齐次齐次MarkovMarkov链链.Markov .Markov 链举例链举例1. 转移概率转移概率定义定义 设0,nXn是马尔可夫链,称条件概率,0nXnni(它表示系统在 时处于状态的条件下经过k步转移,于n+k时到达状态j的条件概率).( )( )(,0,)1kijn knpnP Xj Xi jS nik,0nXn 为在在n时的时的k步转移概率步转移概率.( )( )kijipnj称以为第 行底 列元素的矩阵)()()()(n
6、pnkijkP,0nXn 为系统在n时的k步转移概率矩阵步转移概率矩阵.第一节 基本概念( )( )ijnp nP记为特别特别 当当k=1时，时，(1)( )ijnpn 为系统在 时的一步转移概率,(1)(1)( )( )ijnpnP为系统的一步转移概率矩阵( )ijpn记为第一节 基本概念1. 转移概率转移概率定义定义 称可数维的矩阵称可数维的矩阵)(ijpP 为随机矩阵，如果为随机矩阵，如果0,(, )1,()ijijjpi jpi显然，显然，0,nXn在在n时的时的k步转移概率矩阵步转移概率矩阵)()(nkP是一随机是一随机矩阵矩阵.特别特别k时，约定时，约定(0)1,00ijijijp
7、i jS nij(0)( )I.Pn 此时为单位矩阵第一节 基本概念1. 转移概率转移概率. Chapman-kolmogorov方程方程定理定理 (C-K方程方程)()( )()( )( )(),0, ,k mkmijilljlpnpn pnkn m ki jS或矩阵形式或矩阵形式)()()()()()(knnnmkmkPPP（解决了（解决了k步转移概率与一步转移概率间的关系）步转移概率与一步转移概率间的关系）证明证明()( )k mijn k mnpnP Xj Xi ,()n kmnln kPXjliXX ,)()n k mnn klPXj XliX,)()n k mnnlkPXj XiX
8、l 第一节 基本概念. Chapman-kolmogorov方程方程定理定理 (C-K方程方程)()( )()( )( )(),0, ,k mkmijilljlpnpn pnkn m ki jS或矩阵形式或矩阵形式)()()()()()(knnnmkmkPPP（解决了（解决了k步转移概率与一步转移概率间的关系）步转移概率与一步转移概率间的关系）证明证明,)()n k mnnlkPXj XiXl 第一节 基本概念)(,)(nn k mnnn klkPXiP Xj XXlXil )()nn k mn kn klPXiPllXXj X ( )()( )()kmilljlpn pnk系统在系统在n 时
9、从状态时从状态i的出发的出发,经过经过k+m步转移步转移,于于n+k+m时到达状态时到达状态j,可以先在可以先在n时从状态时从状态i出发，经出发，经过过k步转移于步转移于n+k时到达某种中间状态时到达某种中间状态l,再在再在n+k时时从中间状态从中间状态l出发经过出发经过m步转移于步转移于n+k+m时到达最时到达最终状态终状态j,而中间状态而中间状态l要取遍整个状态空间要取遍整个状态空间S.C-K方程的直观意义：方程的直观意义：. Chapman-kolmogorov方程方程第一节 基本概念若取若取m=1,则由则由C-K方程的矩阵形式方程的矩阵形式:)()()()()()(knnnmkmkPP
10、P得得(1)( )(1)( )( )()kknnnkPPP(1)( )(1)()knnknkPPP( )(1)(1)()nnnknkPPPP分量形式分量形式11 212(1)( )( )(1)()kkkijijj jj jjjjpnpnpnpnk ( ,0)n k ( ,0, ,)n ki jS. Chapman-kolmogorov方程方程第一节 基本概念定理定理 马尔可夫链的马尔可夫链的k 步转移概率由步转移概率由 其一步其一步 转移概率所完全确定转移概率所完全确定. Chapman-kolmogorov方程方程第一节 基本概念1）初始分布）初始分布(0)0(),iqP XiiS称为马尔可
11、夫链为马尔可夫链的的初始分布初始分布3.马尔可夫链马尔可夫链 的分布的分布0,nXn称称 第第i个分量个分量为为)0(iq的的(行行)向量向量)0(q为马尔可夫链为马尔可夫链的的初始分布向量初始分布向量. 即即)()0()0(iqq第一节 基本概念2）有限维分布）有限维分布定理定理 马尔可夫链马尔可夫链0,nXn的的有限维分布有限维分布由其由其初始初始分布分布和和一步转移概率一步转移概率所完全确定所完全确定.证明证明12121, 0, , , ,nnnttt i ii iS 对3.马尔可夫链马尔可夫链 的分布的分布0,nXn第一节 基本概念1212,ntttnP Xi XiXi12120,()
12、,ntnittPXi XiXiiX12201,(),nttitnPXi XXiiXi12012(,)ntttniPXi XiXiXi121110200,()()()tttiXiXiPP XXiiP XiXi11110(,)nntnttnXiP XiXiXi12100121()()()tttiXiXiPP XiP Xi Xi11()nntntnP Xi Xi112111 21(0)11(0)( )().nninntttttiii iiiniqpptpt2）有限维分布）有限维分布3.马尔可夫链马尔可夫链 的分布的分布0,nXn第一节 基本概念又因为马尔可夫链的又因为马尔可夫链的k步转移概率由一步转
13、移概率所步转移概率由一步转移概率所完全确定完全确定.所以马尔可夫链的有限维分布由其所以马尔可夫链的有限维分布由其初始分布初始分布和和一步转移概率一步转移概率所完全确定所完全确定.3.马尔可夫链马尔可夫链 的分布的分布0,nXn第一节 基本概念2）有限维分布）有限维分布3）绝对分布）绝对分布( )(),0,njnqP XjnjS称为马尔可夫链为马尔可夫链 的的绝对分布绝对分布0,nXn称称 第第j个分量为个分量为)(njq的的(行行)向量向量)0(q为马尔可夫链为马尔可夫链0,nXn的的绝对分布向量绝对分布向量. 即即)()()(njnqq绝对分布、初始分布和绝对分布、初始分布和n步转移概率有如
14、下关系：步转移概率有如下关系：( )(0)( )(0)0, ,nnjiijiqqpni jS或矩阵形式或矩阵形式)0()()0()(nnPqq3.马尔可夫链马尔可夫链 的分布的分布0,nXn第一节 基本概念( )()njnqP Xj(0)( )(0)0, ,niijiqpni jS0(),)niPXiXj0(,)niPXi Xj0(,)niP Xi Xj00()()niP XiP Xj Xi3）绝对分布）绝对分布3.马尔可夫链马尔可夫链 的分布的分布0,nXn第一节 基本概念4.齐次马尔可夫链齐次马尔可夫链定义定义,0nXn 设是一马尔可夫链是一马尔可夫链,如果其一步转移如果其一步转移概率概率
15、)(npij恒与起始时刻恒与起始时刻n无关，记为无关，记为ijp,0nXn 则称为为齐次齐次(时间其次或时齐时间其次或时齐)马尔可夫链马尔可夫链.否则，称为非齐次马尔可夫链否则，称为非齐次马尔可夫链.显然对齐次马尔可夫链，显然对齐次马尔可夫链，k步转移概率也与起始步转移概率也与起始时刻时刻n无关记为无关记为( )kijp第一节 基本概念为方便，一般假定时间起点为零即为方便，一般假定时间起点为零即( )0(),0kijkpP Xj Xii jS k相应的相应的k步与一步转移概率矩阵分别记为步与一步转移概率矩阵分别记为(k)PP与定理定理 ( )( )(0)(1),0;(2),0;(3) ,0kk
16、kknkkXnPPqqP的有限维分布由其初始分布和一的有限维分布由其初始分布和一步转移概率所完全确定4.齐次马尔可夫链齐次马尔可夫链第一节 基本概念例例(天气预报问题天气预报问题) 如果明天是否有雨仅与今天的如果明天是否有雨仅与今天的天气天气(是否有雨是否有雨)有关，而与过去的天气无关有关，而与过去的天气无关. 并设并设今天下雨、明天有雨的概率为今天下雨、明天有雨的概率为a，今天无雨而明天有雨的概率为今天无雨而明天有雨的概率为b，又假设，又假设有雨称为有雨称为0状态天气，无雨称为状态天气，无雨称为1状态天气状态天气. Xn表示时刻表示时刻n时的天气状态，则时的天气状态，则0,nXn是以1 ,
17、0S为状态空间的齐次马尔可夫链.其一步转移概率矩阵为其一步转移概率矩阵为bbaa11P. .马尔可夫链举例马尔可夫链举例第一节 基本概念 例例2(有限制随机游动问题有限制随机游动问题) 设质点只能在设质点只能在0，1，2，a中的各点上作随机中的各点上作随机 游动，移动规则如下：游动，移动规则如下：11,2,1ia（）移动前处; 1, 0,rqprqp0000,0,1p rprii+1i-1pqr010p0r20i （ ）移动前处3ia（ ）移动前处a-1aqaar,0,1aaaaq rqr第一节 基本概念. .马尔可夫链举例马尔可夫链举例设设Xn表示质点在表示质点在n时刻所处的位置，则时刻所处
18、的位置，则其一步转移概率矩阵为,00,1, nXnSa是以为状态空间的齐次马尔可夫链.aarqprqprqprqpr000000000000000000000000P 例例2(有限制随机游动问题有限制随机游动问题)第一节 基本概念. .马尔可夫链举例马尔可夫链举例设一个坛子中装有设一个坛子中装有m个球，它们或是红色的，或是黑个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反色的，从坛子中随机的摸出一球，并换入一个相反颜色的球颜色的球.,0nXn 是以, 1 , 0mS为状态空间的齐次马尔可夫链为状态空间的齐次马尔可夫链.设经过设经过n次摸换次摸换,坛中黑球数为坛中黑球数为
19、Xn,则则 例例3(坛子放回摸球问题坛子放回摸球问题)第一节 基本概念. .马尔可夫链举例马尔可夫链举例其其一步转移概率矩阵为一步转移概率矩阵为01000001010000000202000001010000010mmmmmmmmmP 例例3(坛子放回摸球问题坛子放回摸球问题)第一节 基本概念. .马尔可夫链举例马尔可夫链举例甲有赌资甲有赌资a元，乙有赌资元，乙有赌资b元，赌一局输者元，赌一局输者给赢者给赢者1元，无和局。甲赢的概率为元，无和局。甲赢的概率为p， 乙赢的概率为乙赢的概率为q=1- -p，求甲，求甲输光的输光的概率。概率。解解 状态空间状态空间I=0,1,2,c，c=a+bq p
20、a- -1 a a+10 a+b第一节 基本概念. .马尔可夫链举例马尔可夫链举例 例例4(赌徒输光问题赌徒输光问题) 设设ui表示甲从状态表示甲从状态i出发转移到状态出发转移到状态0的的概率，求概率，求ua 显然显然u0 =1，uc =0(u0表示已知甲输光情表示已知甲输光情形下甲输光的概率，形下甲输光的概率，uc表示已知乙输光表示已知乙输光情形下甲输光的概率情形下甲输光的概率) ui =pui+1 + qui- -1 (i=1,2,c- -1)（甲在状态（甲在状态i下输光：甲赢一局后输光或甲下输光：甲赢一局后输光或甲输一局后输光）输一局后输光）第一节 基本概念. .马尔可夫链举例马尔可夫链
21、举例 例例4(赌徒输光问题赌徒输光问题) 1, 2 , 1)()()()(111111ciuupquuuuquupqupuuqpiiiiiiiiiii第一节 基本概念第一节 基本概念. .马尔可夫链举例马尔可夫链举例 例例4(赌徒输光问题赌徒输光问题) 21, 1 (1)012111uuuuuuuuqppqiiiiii即即第一节 基本概念第一节 基本概念. .马尔可夫链举例马尔可夫链举例 例例4(赌徒输光问题赌徒输光问题) baaubabcauciiuccuiiuuiuuiuuuuuuuubaiciiiiiiii同同理理可可得得即即,111101) 1(1) 1() 1() 1()( )()(
22、)(0101012111 第一节 基本概念rrruuuruuruuuuruurpqqppqckckiiiickikciiii1) 1( )()()(, 1 (2)10111111设设即即第一节 基本概念 ccbcbbccacaacckckkcccrrrrrruurrrrrruurrrrrruurrurrruuuk11) 1(11) 1(11) 1(1111) 1(0,1111010从从而而则则令令第一节 基本概念 天气预报问题天气预报问题 RR表示连续两天有雨，记为状态表示连续两天有雨，记为状态0NR表示第表示第1天无雨第天无雨第2天有雨，记为状态天有雨，记为状态1RN表示第表示第1天有雨第天
23、有雨第2天无雨，记为状态天无雨，记为状态2NN表示连续两天无雨，记为状态表示连续两天无雨，记为状态3p00=PR今今R明明| R昨昨R今今=PR明明| R昨昨R今今=0.7p01=PN今今R明明| R昨昨R今今=0p02=PR今今N明明| R昨昨R今今= PN明明| R昨昨R今今=0.3p03=PN今今N明明| R昨昨R今今=0第一节 基本概念类似地得到其他转移概率，类似地得到其他转移概率，于是转移概率矩阵为于是转移概率矩阵为若星期一、星期二均下雨，求星期四下雨若星期一、星期二均下雨，求星期四下雨的概率的概率8 . 002 . 006 . 004 . 0005 . 005 . 003 . 00
24、7 . 033323130232221201312111003020100ppppppppppppppppP第一节 基本概念星期四下雨的情形如右，星期四下雨的情形如右，星期四下雨的概率星期四下雨的概率2步转移概率矩阵为步转移概率矩阵为64. 010. 016. 010. 048. 020. 012. 020. 030. 015. 020. 035. 018. 021. 012. 049. 02)2(PP一一 二二 三三 四四R R R R00R R N R0161. 012. 049. 0 )2(01)2(00ppp第一节 基本概念例例6 设0,nXn是具有三个状态0，1，2的齐次马尔可夫链，
25、其一步转移概率矩阵为3104411142431044P初始分布初始分布, 2 , 1 , 0,31)0(iqi试求：022(1) (0,1);(2) (1).P XXP X第一节 基本概念解解020201(0,1)(0(10)P XXP XP XX（）)(2)0113p(2)01p其中为一个两步转移概率，在两步转移概率矩阵中是第一行第二列的元素.22PP（ ）5181 65131 621 63911 611 6645(2)01516p02(0,1)P XX1553 1648第一节 基本概念(0)(2)21(2)(1)iiiP Xqp(2)(2)(2)0111211()3ppp1 519()3
26、162161124第一节 基本概念练习练习 设0,nXn是状态空间为a,b,c的齐次马氏链.其一步转移概率矩阵为1112442103332055P712345602(1) ,(2) ,nnP Xb Xc Xa Xc Xa Xc Xb XcP Xc Xb求第一节 基本概念45/32 第六章 Markov链第一节 基本概念第二节 Markov链的状态分类及性质第三节 极限定理及平稳分布第四节 Markov链的应用 1 基本概念基本概念2 状态类别的划分和判别状态类别的划分和判别3 状态间的关系状态间的关系 l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别l定义（可达、互通
27、）定义（可达、互通）l性质性质l互通的两个状态之间的关系互通的两个状态之间的关系4 状态空间的分解状态空间的分解 l定义及重要结论（闭集、等价类）定义及重要结论（闭集、等价类）l分解定理（两个定理）分解定理（两个定理） 第六章 Markov链第二节 Markov链的状态分类及性质一、基本概念一、基本概念1.返回概率返回概率( )0,1,2,1|nijnkfP Xj Xj knXi自状态自状态 i出发，经过出发，经过n步首次到达步首次到达状态状态j 的概率的概率自状态自状态i出发，经出发，经有限步终于到达有限步终于到达状态状态j的概率的概率( )1nijijnff自状态自状态i出发，经有限步终于
28、出发，经有限步终于返回返回状态状态 i的的概率概率iif第二节第二节 Markov链的状态分类及性质链的状态分类及性质定理定理1 )()(1)(mnjjmijnmnijpfpIji,1n对任意及，有说明说明1该定理表示n步转移概率按照首次到达时间的所有可能值进行分解建立了)(mijf与)(nijp之间的关系公式说明说明2( )( )01nnijijijfpf第二节第二节 Markov链的状态分类及性质链的状态分类及性质首首达达时间时间系统从状态系统从状态i出发，出发， 首次到达首次到达状态状态j的的时刻时刻称为从状态称为从状态 i 出发首次进入状态出发首次进入状态 j 的时间，或称自的时间，或
29、称自i 到到j 的的首达时间。首达时间。0,min0njXiXnTnij：如果这样的如果这样的n不存在，规定不存在，规定ijT说明说明1ijT是一个随机变量，它的取值是系统从状态 i 出发使jXn的最小正整数n。2.平均返回时间平均返回时间一、基本概念一、基本概念第二节第二节 Markov链的状态分类及性质链的状态分类及性质|0)(iXnTPfijnij1)(ijnnijijTPff( )1()defnijijijnE Tnf说明说明2平均返回时间平均返回时间状态状态i的的平均返回时间平均返回时间ii2.平均返回时间平均返回时间一、基本概念一、基本概念第二节第二节 Markov链的状态分类及性
30、质链的状态分类及性质状态状态i的的周期周期若若di 1,称称i是周期的；若是周期的；若di =1,称称i是非周期的。是非周期的。( )gcd :1,0niiidn np说明说明13.周期周期di体现系统的发展变化种状态体现系统的发展变化种状态i重复出现的概率重复出现的概率周期。周期。说明说明2若若i的周期是的周期是di，并不是对所有的，并不是对所有的n满足满足 ()0indiip说明说明3( )gcd :1,0niiihn nf一、基本概念一、基本概念第二节第二节 Markov链的状态分类及性质链的状态分类及性质greatest common divisor 1 基本概念基本概念2 状态类别的
31、划分和判别状态类别的划分和判别l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别第二节第二节 Markov链的状态分类及性质链的状态分类及性质二、状态类别的划分及判别二、状态类别的划分及判别1.状态类别的划分状态类别的划分状态状态 iiif非常返态非常返态常返态常返态零常返态零常返态正常返态正常返态周期周期非周期（遍历态）非周期（遍历态）iiid常返态常返态非常返态非常返态1iif1iif正常返态正常返态零常返态零常返态ii ii 第二节第二节 Markov链的状态分类及性质链的状态分类及性质注注“常返常返”一词，有时又称一词，有时又称“返回返回”、“常驻常驻”或或“持
32、久持久”“瞬时瞬时”也称也称“滑过滑过” 或或“非常返非常返”定理定理2若1iif，则系统以概率 1 无穷次返回 i；若1iif，则系统以概率 1 只有有穷次返回 i。 证证若1iif则系统从状态则系统从状态i出发，经过有限次转移之后，出发，经过有限次转移之后，必定以概率必定以概率1返回状态返回状态i。再由马氏性再由马氏性系统返回状态系统返回状态i要重复发生要重复发生这样，系统从状态这样，系统从状态i出发，又返回，再出发，再返回，随着出发，又返回，再出发，再返回，随着时间的无限推移，将无限次访问状态时间的无限推移，将无限次访问状态i。第二节第二节 Markov链的状态分类及性质链的状态分类及性
33、质将将“不返回不返回i”称为成功，称为成功， 则首次成功出现的次数服从几何分布，则首次成功出现的次数服从几何分布，若1iif则每次回到 i 后都有正的概率iif1不返回 i， 其均值为iif11， 平均回到 i 共iif11次 就不再回到 i 了。 也就是说以概率也就是说以概率1只有有穷次返回只有有穷次返回i。即即第二节第二节 Markov链的状态分类及性质链的状态分类及性质2.判别判别（1）判别是否常返态）判别是否常返态1iif()1niinp 定理定理31iif()1niinp ()1()1lim1NnijnijNNnjjnpfp 第二节第二节 Markov链的状态分类及性质链的状态分类及
34、性质2.判别判别零 常 返()lim0niinp （2）判别是否零常返态、正常返有（非）周期）判别是否零常返态、正常返有（非）周期正 常 返 非 周 期()1lim0niiniip 正 常 返 有 周 期()limniinp 不 存 在 ， 但 有 一收 敛 于 某 一 正 数 的 收 敛 子 列定理定理4()limindiiiniidp 对任意给定的状态对任意给定的状态i，如，如果果i是常返态且有周期是常返态且有周期di，则存在极限则存在极限第二节第二节 Markov链的状态分类及性质链的状态分类及性质2.判别判别（3）判别是否有周期）判别是否有周期( )(1),0,0,nniiiinppi
35、（1）若有正整数使则 非周期,mmPj（ 2） 若 有 正 整 数 使 得步 转 移 概 率 矩 阵中相 应 于 某 的 那 列 元 素 为 0， 则 状 态 非 周 期 。003,0N diiidNNNp（）（ ） 设 状 态有 周 期则 必 存 在 正 整 数， 使 得 对 所 有均 有。第二节第二节 Markov链的状态分类及性质链的状态分类及性质 1 基本概念基本概念2 状态类别的划分和判别状态类别的划分和判别3 状态间的关系状态间的关系 l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别第二节第二节 Markov链的状态分类及性质链的状态分类及性质l定义（可达
36、、互通）定义（可达、互通）l性质性质l互通的两个状态之间的关系互通的两个状态之间的关系三、状态间的关系三、状态间的关系1.定义定义( ),0nijnNp 使得状态状态 i可达可达状态状态j2.性质性质简记为简记为 ij状态状态 i与状态与状态j互通互通ijj i且且传递性、对称性传递性、对称性第二节第二节 Markov链的状态分类及性质链的状态分类及性质三、状态间的关系三、状态间的关系3.利用首达概率刻画可达和互通关系利用首达概率刻画可达和互通关系第二节第二节 Markov链的状态分类及性质链的状态分类及性质,0,0ijijjii jIijfijf f结论结论1,1ijjiijI jjijif
37、f设是常返态，则且结论结论24.互通的两个状态的状态类型互通的两个状态的状态类型互通的两个状态必有相同的状态类型互通的两个状态必有相同的状态类型定理定理5三、状态间的关系三、状态间的关系第二节第二节 Markov链的状态分类及性质链的状态分类及性质63/34 1 基本概念基本概念2 状态类别的划分和判别状态类别的划分和判别3 状态间的关系状态间的关系 l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别第二节第二节 Markov链的状态分类及性质链的状态分类及性质l定义（可达、互通）定义（可达、互通）l性质性质l互通的两个状态之间的关系互通的两个状态之间的关系4 状态空间
38、的分解状态空间的分解 l定义及重要结论（闭集、等价类）定义及重要结论（闭集、等价类）l分解定理（两个定理）分解定理（两个定理）四、状态空间的分解四、状态空间的分解互通满足：自反性、对称性、传递性。互通满足：自反性、对称性、传递性。互通是一种互通是一种等价关系等价关系（常返态）（常返态） 按互通关系是等价关系，可以把状态空间按互通关系是等价关系，可以把状态空间 I 划划分为若干个不相交的集合（或者说等价类），并称之分为若干个不相交的集合（或者说等价类），并称之为状态类。为状态类。 若两个状态相通，则这两个状态属于同一类。若两个状态相通，则这两个状态属于同一类。 任意两个类或不相交或者相同。任意两
39、个类或不相交或者相同。说明说明第二节第二节 Markov链的状态分类及性质链的状态分类及性质（1）定义）定义四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质A闭集闭集设设C为状态空间为状态空间I 的一个子集，的一个子集，若对任意Ci和任意Cj 有0)(nijp（0n） ，则则C称为闭集。称为闭集。注注1 若若C为闭集，则表示自为闭集，则表示自C内任意状态内任意状态i出发，始出发，始终不能到达终不能到达C以外的任何状态以外的任何状态j。 整个状态空间构成一个闭集。整个状态空间构成一个闭集。吸收态吸收态指一个闭集中只含一个状态指一个闭集中只含一个状
40、态（1）定义）定义四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质A闭集闭集设设C为状态空间为状态空间I 的一个子集，的一个子集，若对任意Ci和任意Cj 有0)(nijp（0n） ，则则C称为闭集。称为闭集。注注2若状态空间含有吸收状态，那么这若状态空间含有吸收状态，那么这个吸收状态构成一个最小的闭集。个吸收状态构成一个最小的闭集。（1）定义）定义四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质B不可约的不可约的 设设C为闭集，如果为闭集，如果C中不再含有任何非空真闭子中不再含有任何非空真闭子集
41、，则称集，则称C是不可约闭集，或称不可约的，不可分的，是不可约闭集，或称不可约的，不可分的，最小的。最小的。 若整个状态空间是不可约的，则称此链为不可若整个状态空间是不可约的，则称此链为不可约马氏链。约马氏链。A.有关闭集有关闭集（2）一些重要结论）一些重要结论0,ijCpiC jC 是闭集四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质B. 有关等价类有关等价类（2）一些重要结论）一些重要结论四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质 结论结论2 设设C是闭集，当且仅当是闭集，当且仅当C
42、中的任何两个状态都互中的任何两个状态都互通时，通时， C是不可约的。是不可约的。结论结论1 等价类若是闭集，则必定是不可约的。等价类若是闭集，则必定是不可约的。 结论结论3 齐次马氏链不可约的充要条件是它的任意两个齐次马氏链不可约的充要条件是它的任意两个状态均互通。状态均互通。 结论结论4 包含常返态的等价类是不可约闭集。包含常返态的等价类是不可约闭集。例例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。设马氏链0,nXn的状态空间 I=0，1，232310414121021211P第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解2/
43、31/41/41/31/21/20121/2由图可知状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0。因此，状态空间I的各状态都是互通的。又由于I 的任意状态i (i = 0，1，2)不能到达I 以外的任何状态， 所以I是一个闭集而且I 中没有其它闭集 所以此马氏链是不可约的。解先按一步转移概率，画出各状态间的传递图第二节第二节 Markov链的状态分类及性质链的状态分类及性质例例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。设 马 氏 链 的 状 态 空 间 为 I = 1， 2， 3， 4， 5000100000100100002/102/
44、102/1002/11P第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解111/21/21/2311/24521 闭集，由图可知状态3为吸收态且故 1C= 3为闭 集2C=1,43C=1,3,4闭集，闭集，4C=1,2,3,4 其中 是不可约的。1C，2C又因状态空间I有闭子集，故此链为非不可约链。解先按一步转移概率，画出各状态间的传递图第二节第二节 Markov链的状态分类及性质链的状态分类及性质（3）状态空间的分解）状态空间的分解如果已知类中有一个常返态，则这个类中其它状态都是如果已知类中有一个常返态，则这个类中其它状态都是常返的。常返的。
45、若类中有一个非常返态，则类中其它状态都是非常返态。若类中有一个非常返态，则类中其它状态都是非常返态。若对不可约马氏链，则要么全是常返态，要么全是非常若对不可约马氏链，则要么全是常返态，要么全是非常返态。返态。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解定理定理6任一马氏链的状态空间任一马氏链的状态空间I必可分解为必可分解为kCCCNI21其中其中N是非常返态集，是非常返态集，21CC是互不相交的由常返态组成的闭集而且而且（1）对每一个确定的 h，hC内任意两个状态相通；（2）hC和gC（gh ）中的状态不相同。（3）状态空间的分解）状态空间
46、的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解如果从某一非常返态出发，系统可能一直在非常返集中，如果从某一非常返态出发，系统可能一直在非常返集中，也可能进入某个常返闭集，一旦进入某个常返闭集后，也可能进入某个常返闭集，一旦进入某个常返闭集后，将一直停留在这个常返闭集中；如果系统从某一常返状将一直停留在这个常返闭集中；如果系统从某一常返状态出发，则系统就一直停留在这个状态所在的常返闭集态出发，则系统就一直停留在这个状态所在的常返闭集中。中。说明说明1（3）状态空间的分解）状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分
47、类及性质四、状态空间的分解四、状态空间的分解定理定理7设, 2 , 1 , 0, nXn是状态空间I有限的马氏链，则 （1）非常返态集）非常返态集N不可能是闭集；不可能是闭集；（2）至少有一个常返态；）至少有一个常返态；（3）不存在零常返态；）不存在零常返态；（4）若链是不可约的，那么状态都是正常返的）若链是不可约的，那么状态都是正常返的（5）其状态空间可分解为）其状态空间可分解为kCCCNI21其中 N 是非常返态集， kCCC，21是互不相交的由正常返态组成的闭集。（3）状态空间的分解）状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空
48、间的分解定理定理8(周期链分解定理周期链分解定理)（3）状态空间的分解）状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解转移概率矩阵的标准形式转移概率矩阵的标准形式121212NNNCCPPPNPCPCP(1)1(1)1( )0000ddddJPPJPJP状态空间的分解状态空间的分解周期链的分解周期链的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解例例转移矩阵已知马氏链, 2 , 1 , 0,nXn的状态空间4 , 3 , 2 , 1I00011000010041414141
49、P试对其状态分类。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解解解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。82/34考虑状态1是否常返，需要计算11f：41)1(11f1| 1, 1012)2(11XXXPf 1| 2, 1012XXXP 1| 3, 1012XXXP1|4, 1012XXXP 1, 4| 1012XXXP1|401XXP41411
50、4pp第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解类似地可求得所以41413413)3(11pppf4141342312)4(11ppppf0)(11nf（, 6 , 5n）)(11111nnff141414141于是状态1是常返的。又因为25)(1111nnfn所以状态1是正常返的。由定理可知，此链所有状态都是正常返的。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解例例设马氏链的状态空间I = 0,1,2,，转移概率为试讨论各状态的遍历性。2100p，211,iip，210ip，Ii第二
