-马尔可夫链.ppt

.Markov 过程过程.安德雷安德雷.安德耶维奇安德耶维奇.马尔可夫马尔可夫 (A.A.Markov):俄数学家，俄数学家，18561922 概率和统计领域专家。概率和统计领域专家。当年当年Markov研究普希金诗歌里元音字母和辅研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了音字母交替出现的规律时提出了Markov过程的数过程的数学模型学模型 Markov过程过程80年代兴起，在现代工程、自然年代兴起，在现代工程、自然科学、社会科学中应用广泛。科学、社会科学中应用广泛。Markov过程过程2024/5/26 周日.1马尔可夫性马尔可夫性通俗地说，通俗地说，就是在知道过程现在的条件下，其就是在知道过程现在的条件下，其将来的条件分布不依赖于过去，将来的条件分布不依赖于过去，则称则称具有具有马尔可夫（马尔可夫（Markov)性。性。定义定义设设是一个随机过程，如果是一个随机过程，如果在在t0时刻所处的状态为已知，它在时刻所处的状态为已知，它在时刻时刻 所处状态的条件分布与其在所处状态的条件分布与其在 t0 之前之前 所处的状态无关。所处的状态无关。.2.马尔可夫过程马尔可夫过程定义定义 设设的状态空间为S,的条件分布函数恰好等于.3.马尔可夫链马尔可夫链定义定义 参数集和状态空间都是离散的马尔可夫过程参数集和状态空间都是离散的马尔可夫过程称为马尔可夫链。称为马尔可夫链。注注 只讨论马尔可夫链的状态空间为有限或可列无限只讨论马尔可夫链的状态空间为有限或可列无限.则马尔可夫性可表示为则马尔可夫性可表示为.时间时间离散离散状态状态离散离散的的马尔科夫链马尔科夫链 时间时间离散离散状态状态连续连续的马尔科夫序列的马尔科夫序列 时间时间连续连续状态状态连续连续的马尔科夫过程的马尔科夫过程 时间时间连续连续状态状态离散离散的马尔科夫过程的马尔科夫过程Markov过程过程2024/5/26 周日7.第六章 Markov链第一节 基本概念第二节 Markov链的状态分类及性质第三节 极限定理及平稳分布第四节 Markov链的应用8.第六章 Markov链第一节 基本概念1.1.转移概率转移概率.Chapman-kolmogorov.Chapman-kolmogorov方程方程3.Markov3.Markov链的分布链的分布4.4.齐次齐次MarkovMarkov链链.Markov.Markov 链举例链举例9.1.转移概率转移概率定义定义 设是马尔可夫链,称条件概率经过k步转移,于n+k时到达状态j的条件概率).在在n时的时的k步转移概率步转移概率.n时的k步转移概率矩阵步转移概率矩阵.第一节 基本概念.特别特别 当当k=1时，时，第一节 基本概念1.转移概率转移概率.定义定义 称可数维的矩阵称可数维的矩阵为随机矩阵，如果为随机矩阵，如果显然，显然，在在n时的时的k步转移概率矩阵步转移概率矩阵是一随机是一随机矩阵矩阵.特别特别k时，约定时，约定第一节 基本概念1.转移概率转移概率.Chapman-kolmogorov方程方程定理定理(C-K方程方程)或矩阵形式或矩阵形式（解决了（解决了k步转移概率与一步转移概率间的关系）步转移概率与一步转移概率间的关系）证明证明第一节 基本概念.Chapman-kolmogorov方程方程定理定理(C-K方程方程)或矩阵形式或矩阵形式（解决了（解决了k步转移概率与一步转移概率间的关系）步转移概率与一步转移概率间的关系）证明证明第一节 基本概念.系统在系统在n 时从状态时从状态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方程的矩阵形式方程的矩阵形式:得得分量形式分量形式.Chapman-kolmogorov方程方程第一节 基本概念.定理定理 马尔可夫链的马尔可夫链的k 步转移概率由步转移概率由 其一步其一步 转移概率所完全确定转移概率所完全确定.Chapman-kolmogorov方程方程第一节 基本概念.1）初始分布）初始分布为马尔可夫链为马尔可夫链的的初始分布初始分布3.马尔可夫链马尔可夫链 的分布的分布称称 第第i个分量为个分量为的的(行行)向量向量为马尔可夫链为马尔可夫链的的初始分布向量初始分布向量.即即第一节 基本概念.2）有限维分布）有限维分布定理定理 马尔可夫链马尔可夫链的的有限维分布有限维分布由其由其初始初始分布分布和和一步转移概率一步转移概率所完全确定所完全确定.证明证明3.马尔可夫链马尔可夫链 的分布的分布第一节 基本概念.2）有限维分布）有限维分布3.马尔可夫链马尔可夫链 的分布的分布第一节 基本概念.又因为马尔可夫链的又因为马尔可夫链的k步转移概率由一步转移概率所步转移概率由一步转移概率所完全确定完全确定.所以马尔可夫链的有限维分布由其所以马尔可夫链的有限维分布由其初始分布初始分布和和一步转移概率一步转移概率所完全确定所完全确定.3.马尔可夫链马尔可夫链 的分布的分布第一节 基本概念2）有限维分布）有限维分布.3）绝对分布）绝对分布为马尔可夫链为马尔可夫链 的的绝对分布绝对分布称称 第第j个分量为个分量为的的(行行)向量向量为马尔可夫链为马尔可夫链的的绝对分布向量绝对分布向量.即即绝对分布、初始分布和绝对分布、初始分布和n步转移概率有如下关系：步转移概率有如下关系：或矩阵形式或矩阵形式3.马尔可夫链马尔可夫链 的分布的分布第一节 基本概念.3）绝对分布）绝对分布3.马尔可夫链马尔可夫链 的分布的分布第一节 基本概念.4.齐次马尔可夫链齐次马尔可夫链定义定义是一马尔可夫链是一马尔可夫链,如果其一步转移如果其一步转移概率概率恒与起始时刻恒与起始时刻n无关，记为无关，记为为为齐次齐次(时间其次或时齐时间其次或时齐)马尔可夫链马尔可夫链.否则，称为非齐次马尔可夫链否则，称为非齐次马尔可夫链.显然对齐次马尔可夫链，显然对齐次马尔可夫链，k步转移概率也与起始步转移概率也与起始时刻时刻n无关记为无关记为第一节 基本概念.为方便，一般假定时间起点为零即为方便，一般假定时间起点为零即相应的相应的k步与一步转移概率矩阵分别记为步与一步转移概率矩阵分别记为定理定理 的有限维分布由其初始分布和一的有限维分布由其初始分布和一步转移概率所完全确定4.齐次马尔可夫链齐次马尔可夫链第一节 基本概念.例例(天气预报问题天气预报问题)如果明天是否有雨仅与今天的如果明天是否有雨仅与今天的天气天气(是否有雨是否有雨)有关，而与过去的天气无关有关，而与过去的天气无关.并设并设今天下雨、明天有雨的概率为今天下雨、明天有雨的概率为a，今天无雨而明天有雨的概率为今天无雨而明天有雨的概率为b，又假设，又假设有雨称为有雨称为0状态天气，无雨称为状态天气，无雨称为1状态天气状态天气.Xn表示时刻表示时刻n时的天气状态，则时的天气状态，则是以为状态空间的齐次马尔可夫链.其一步转移概率矩阵为其一步转移概率矩阵为.马尔可夫链举例马尔可夫链举例第一节 基本概念.例例2(有限制随机游动问题有限制随机游动问题)设质点只能在设质点只能在0，1，2，a中的各点上作随机中的各点上作随机 游动，移动规则如下：游动，移动规则如下：ii+1i-101a-1a第一节 基本概念.马尔可夫链举例马尔可夫链举例.设设Xn表示质点在表示质点在n时刻所处的位置，则时刻所处的位置，则其一步转移概率矩阵为 例例2(有限制随机游动问题有限制随机游动问题)第一节 基本概念.马尔可夫链举例马尔可夫链举例.设一个坛子中装有设一个坛子中装有m个球，它们或是红色的，或是黑个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反颜色的，从坛子中随机的摸出一球，并换入一个相反颜色的球色的球.为状态空间的齐次马尔可夫链为状态空间的齐次马尔可夫链.设经过设经过n次摸换次摸换,坛中黑球数为坛中黑球数为Xn,则则 例例3(坛子放回摸球问题坛子放回摸球问题)第一节 基本概念.马尔可夫链举例马尔可夫链举例.其其一步转移概率矩阵为一步转移概率矩阵为 例例3(坛子放回摸球问题坛子放回摸球问题)第一节 基本概念.马尔可夫链举例马尔可夫链举例.甲有赌资甲有赌资a元，乙有赌资元，乙有赌资b元，赌一局输者元，赌一局输者给赢者给赢者1元，无和局。甲赢的概率为元，无和局。甲赢的概率为p，乙赢的概率为乙赢的概率为q=1-p，求甲，求甲输光的输光的概率。概率。解解 状态空间状态空间I=0,1,2,c，c=a+bq pa-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下输光：甲赢一局后输光或甲下输光：甲赢一局后输光或甲输一局后输光）输一局后输光）第一节 基本概念.马尔可夫链举例马尔可夫链举例 例例4(赌徒输光问题赌徒输光问题).第一节 基本概念第一节 基本概念.马尔可夫链举例马尔可夫链举例 例例4(赌徒输光问题赌徒输光问题).第一节 基本概念第一节 基本概念.马尔可夫链举例马尔可夫链举例 例例4(赌徒输光问题赌徒输光问题).第一节 基本概念.第一节 基本概念.第一节 基本概念.例例5 天气预报问题天气预报问题 RR表示连续两天有雨，记为状态表示连续两天有雨，记为状态0NR表示第表示第1天无雨第天无雨第2天有雨，记为状态天有雨，记为状态1RN表示第表示第1天有雨第天有雨第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第一节 基本概念.类似地得到其他转移概率，类似地得到其他转移概率，于是转移概率矩阵为于是转移概率矩阵为若星期一、星期二均下雨，求星期四下雨若星期一、星期二均下雨，求星期四下雨的概率的概率第一节 基本概念.星期四下雨的情形如右，星期四下雨的情形如右，星期四下雨的概率星期四下雨的概率2步转移概率矩阵为步转移概率矩阵为一一 二二 三三 四四R R R R00R R N R01第一节 基本概念.例例6 设是具有三个状态0，1，2的齐次马尔可夫链，其一步转移概率矩阵为初始分布初始分布试求：第一节 基本概念.解解第一节 基本概念.第一节 基本概念.练习练习 设是状态空间为a,b,c的齐次马氏链.其一步转移概率矩阵为第一节 基本概念.第六章 Markov链第一节 基本概念第二节 Markov链的状态分类及性质第三节 极限定理及平稳分布第四节 Markov链的应用45.1 基本概念基本概念2 状态类别的划分和判别状态类别的划分和判别3 状态间的关系状态间的关系 l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别l定义（可达、互通）定义（可达、互通）l性质性质l互通的两个状态之间的关系互通的两个状态之间的关系4 状态空间的分解状态空间的分解 l定义及重要结论（闭集、等价类）定义及重要结论（闭集、等价类）l分解定理（两个定理）分解定理（两个定理）第六章 Markov链第二节 Markov链的状态分类及性质.一、基本概念一、基本概念1.返回概率返回概率自状态自状态 i出发，经过出发，经过n步首次到达步首次到达状态状态j 的概率的概率自状态自状态i出发，经出发，经有限步终于到达有限步终于到达状态状态j的概率的概率自状态自状态i出发，经有限步终于出发，经有限步终于返回返回状态状态 i的的概率概率第二节第二节 Markov链的状态分类及性质链的状态分类及性质.定理定理1 对任意及，有说明说明1该定理表示n步转移概率按照首次到达时间的所有可能值进行分解说明说明2第二节第二节 Markov链的状态分类及性质链的状态分类及性质.首首达达时间时间系统从状态系统从状态i出发，出发，首次到达首次到达状态状态j的的时刻时刻称称为为从从状状态态 i 出出发发首首次次进进入入状状态态 j 的的时时间间，或或称称自自i 到到j 的的首达时间。首达时间。如果这样的如果这样的n不存在，规定不存在，规定说明说明12.平均返回时间平均返回时间一、基本概念一、基本概念第二节第二节 Markov链的状态分类及性质链的状态分类及性质.说明说明2平均返回时间平均返回时间状态状态i的的平均返回时间平均返回时间2.平均返回时间平均返回时间一、基本概念一、基本概念第二节第二节 Markov链的状态分类及性质链的状态分类及性质.状态状态i的的周期周期若若di 1,称称i是周期的；若是周期的；若di=1,称称i是非周期的。是非周期的。说明说明13.周期周期di体体现现系系统统的的发发展展变变化化种种状状态态i重重复复出出现现的的概概率率周期。周期。说明说明2若若i的周期是的周期是di，并不是对所有的，并不是对所有的n满足满足 说明说明3一、基本概念一、基本概念第二节第二节 Markov链的状态分类及性质链的状态分类及性质greatest common divisor.1 基本概念基本概念2 状态类别的划分和判别状态类别的划分和判别l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别第二节第二节 Markov链的状态分类及性质链的状态分类及性质.二、状态类别的划分及判别二、状态类别的划分及判别1.状态类别的划分状态类别的划分状态状态 i非常返态非常返态常返态常返态零常返态零常返态正常返态正常返态周期周期非周期（遍历态）非周期（遍历态）常返态常返态非常返态非常返态正常返态正常返态零常返态零常返态第二节第二节 Markov链的状态分类及性质链的状态分类及性质.注注“常返常返”一词，有时又称一词，有时又称“返回返回”、“常驻常驻”或或“持久持久”“瞬时瞬时”也称也称“滑过滑过”或或“非常返非常返”定理定理2证证则系统从状态则系统从状态i出发，经过有限次转移之后，出发，经过有限次转移之后，必定以概率必定以概率1返回状态返回状态i。再由马氏性再由马氏性系统返回状态系统返回状态i要重复发生要重复发生这这样样，系系统统从从状状态态i出出发发，又又返返回回，再再出出发发，再再返返回回，随随着着时间的无限推移，将无限次访问状态时间的无限推移，将无限次访问状态i。第二节第二节 Markov链的状态分类及性质链的状态分类及性质.将将“不返回不返回i”称为成功，称为成功，则首次成功出现的次数服从几何分布，则首次成功出现的次数服从几何分布，也就是说以概率也就是说以概率1只有有穷次返回只有有穷次返回i。即即第二节第二节 Markov链的状态分类及性质链的状态分类及性质.2.判别判别（1）判别是否常返态）判别是否常返态定理定理3第二节第二节 Markov链的状态分类及性质链的状态分类及性质.2.判别判别（2）判别是否零常返态、正常返有（非）周期）判别是否零常返态、正常返有（非）周期定理定理4对任意给定的状态对任意给定的状态i，如，如果果i是常返态且有周期是常返态且有周期di，则存在极限，则存在极限第二节第二节 Markov链的状态分类及性质链的状态分类及性质.2.判别判别（3）判别是否有周期）判别是否有周期第二节第二节 Markov链的状态分类及性质链的状态分类及性质.1 基本概念基本概念2 状态类别的划分和判别状态类别的划分和判别3 状态间的关系状态间的关系 l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别第二节第二节 Markov链的状态分类及性质链的状态分类及性质l定义（可达、互通）定义（可达、互通）l性质性质l互通的两个状态之间的关系互通的两个状态之间的关系.三、状态间的关系三、状态间的关系1.定义定义状态状态 i可达可达状态状态j2.性质性质简记为简记为 ij状态状态 i与状态与状态j互通互通ijj i且且传递性、对称性传递性、对称性第二节第二节 Markov链的状态分类及性质链的状态分类及性质.三、状态间的关系三、状态间的关系3.利用首达概率刻画可达和互通关系利用首达概率刻画可达和互通关系第二节第二节 Markov链的状态分类及性质链的状态分类及性质结论结论1结论结论2.4.互通的两个状态的状态类型互通的两个状态的状态类型互通的两个状态必有相同的状态类型互通的两个状态必有相同的状态类型定理定理5三、状态间的关系三、状态间的关系第二节第二节 Markov链的状态分类及性质链的状态分类及性质.1 基本概念基本概念2 状态类别的划分和判别状态类别的划分和判别3 状态间的关系状态间的关系 l返回概率返回概率l平均返回时间平均返回时间l周期周期l分类分类l判别判别第二节第二节 Markov链的状态分类及性质链的状态分类及性质l定义（可达、互通）定义（可达、互通）l性质性质l互通的两个状态之间的关系互通的两个状态之间的关系4 状态空间的分解状态空间的分解 l定义及重要结论（闭集、等价类）定义及重要结论（闭集、等价类）l分解定理（两个定理）分解定理（两个定理）63.四、状态空间的分解四、状态空间的分解互通满足：自反性、对称性、传递性。互通满足：自反性、对称性、传递性。互通是一种互通是一种等价关系等价关系（常返态）（常返态）按互通关系是等价关系，可以把状态空间按互通关系是等价关系，可以把状态空间 I 划分划分为若干个不相交的集合（或者说等价类），并称之为为若干个不相交的集合（或者说等价类），并称之为状态类。状态类。若两个状态相通，则这两个状态属于同一类。若两个状态相通，则这两个状态属于同一类。任意两个类或不相交或者相同。任意两个类或不相交或者相同。说明说明第二节第二节 Markov链的状态分类及性质链的状态分类及性质.（1）定义）定义四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质A闭集闭集设设C为状态空间为状态空间I 的一个子集，的一个子集，则则C称为闭集。称为闭集。注注1 若若C为闭集，则表示自为闭集，则表示自C内任意状态内任意状态i出发，始出发，始终不能到达终不能到达C以外的任何状态以外的任何状态j。整个状态空间构成一个闭集。整个状态空间构成一个闭集。吸收态吸收态指一个闭集中只含一个状态指一个闭集中只含一个状态.（1）定义）定义四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质A闭集闭集设设C为状态空间为状态空间I 的一个子集，的一个子集，则则C称为闭集。称为闭集。注注2若若状状态态空空间间含含有有吸吸收收状状态态，那那么么这这个吸收状态构成一个最小的闭集。个吸收状态构成一个最小的闭集。.（1）定义）定义四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质B不可约的不可约的 设设C为闭集，如果为闭集，如果C中不再含有任何非空真闭子中不再含有任何非空真闭子集，则称集，则称C是不可约闭集，或称不可约的，不可分的，是不可约闭集，或称不可约的，不可分的，最小的。最小的。若整个状态空间是不可约的，则称此链为不可若整个状态空间是不可约的，则称此链为不可约马氏链。约马氏链。.A.有关闭集有关闭集（2）一些重要结论）一些重要结论四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质.B.有关等价类有关等价类（2）一些重要结论）一些重要结论四、状态空间的分解四、状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质 结结论论2 设设C是是闭闭集集，当当且且仅仅当当C中中的的任任何何两两个个状状态态都都互互通时，通时，C是不可约的。是不可约的。结论结论1 等价类若是闭集，则必定是不可约的。等价类若是闭集，则必定是不可约的。结结论论3 齐齐次次马马氏氏链链不不可可约约的的充充要要条条件件是是它它的的任任意意两两个个状态均互通。状态均互通。结论结论4 包含常返态的等价类是不可约闭集。包含常返态的等价类是不可约闭集。.例例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.2/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其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.111/21/21/2311/24521 闭集，由图可知状态3为吸收态且闭集，闭集，其中 是不可约的。又因状态空间I有闭子集，故此链为非不可约链。解先按一步转移概率，画出各状态间的传递图第二节第二节 Markov链的状态分类及性质链的状态分类及性质.（3）状态空间的分解）状态空间的分解如果已知类中有一个常返态，则这个类中其它状态都是如果已知类中有一个常返态，则这个类中其它状态都是常返的。常返的。若类中有一个非常返态，则类中其它状态都是非常返态。若类中有一个非常返态，则类中其它状态都是非常返态。若对不可约马氏链，则要么全是常返态，要么全是非常若对不可约马氏链，则要么全是常返态，要么全是非常返态。返态。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.定理定理6任一马氏链的状态空间任一马氏链的状态空间I必可分解为必可分解为其中其中N是非常返态集，是非常返态集，而且而且（3）状态空间的分解）状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.如果从某一非常返态出发，系统可能一直在非常返集中，如果从某一非常返态出发，系统可能一直在非常返集中，也可能进入某个常返闭集，一旦进入某个常返闭集后，也可能进入某个常返闭集，一旦进入某个常返闭集后，将一直停留在这个常返闭集中；如果系统从某一常返状将一直停留在这个常返闭集中；如果系统从某一常返状态出发，则系统就一直停留在这个状态所在的常返闭集态出发，则系统就一直停留在这个状态所在的常返闭集中。中。说明说明1（3）状态空间的分解）状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.定理定理7（1）非常返态集）非常返态集N不可能是闭集；不可能是闭集；（2）至少有一个常返态；）至少有一个常返态；（3）不存在零常返态；）不存在零常返态；（4）若链是不可约的，那么状态都是正常返的）若链是不可约的，那么状态都是正常返的（5）其状态空间可分解为）其状态空间可分解为是互不相交的由正常返态组成的闭集。（3）状态空间的分解）状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.定理定理8(周期链分解定理周期链分解定理)（3）状态空间的分解）状态空间的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.转移概率矩阵的标准形式转移概率矩阵的标准形式状态空间的分解状态空间的分解周期链的分解周期链的分解第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.例例转移矩阵试对其状态分类。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.解解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。.考虑状态1是否常返，第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解82.类似地可求得所以于是状态1是常返的。又因为所以状态1是正常返的。由定理可知，此链所有状态都是正常返的。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.例例设马氏链的状态空间I=0,1,2,，转移概率为试讨论各状态的遍历性。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.解解根据转移概率作出状态传递图1/21/21/21/21/21/20121/231/2第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解从图可知，对任一状态 都有 ，故由定理可知，I 中的所以状态都是相通的，.因此只需考虑状态0是否正常返即可。故从而0是常返态。又因为所以状态0为正常返。又由于故状态0为非周期的从而状态0是遍历的。故所有状态i都是遍历的。第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.一般一般情况情况End.第二节第二节 Markov链的状态分类及性质链的状态分类及性质四、状态空间的分解四、状态空间的分解.第六章 Markov链第一节 基本概念第二节 Markov链的状态分类及性质第三节 极限定理及平稳分布第四节 Markov链的应用88.第六章 Markov链第三节 极限定理及平稳分布一、极限定理二、平稳分布与极限分布89.一、极限定理例 设马尔可夫链的转移概率矩阵为现在来计算令第三节 极限定理及平稳分布则.所以一、极限定理第三节 极限定理及平稳分布.定理：若i与j相通，则(3),若j是非周期的,则(4),若j有周期d,则一、极限定理第三节 极限定理及平稳分布.一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。推论1：如i是常返的，则i为零常返的充要条件是.一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。推论2：如i是遍历的(正常返的并且是非周期的)，则.一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。1，若j为非常返或零常返的，则 有2，若j为常返的且周期为d，则 有 推论3（遍历性定理）.一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。推论5：有限状态的马尔可夫链，不可能全为非常返状态，也不可能有零常返状态。从而不可约的有限马尔可夫链的状态全为正常返的。.一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。推论6：若马尔可夫链有一个零常返态，则必有无限个零常返态。.状态性质判别法i非常返i零常返i正常返i遍历的i正常返i正常返且非周期（即遍历）i正常返且周期为d第三节 极限定理及平稳分布.例设马氏链的状态空间I=0,1,2,，转移概率为试讨论各状态的遍历性。第三节 极限定理及平稳分布.解根据转移概率作出状态传递图1/21/21/21/21/21/20121/231/2第三节 极限定理及平稳分布从图可知，对任一状态 都有 ，故由定理可知，I 中的所以状态都是相通的，因此只需考虑状态0是否正常返即可。.故从而0是常返态。又因为所以状态0为正常返。又由于故状态0为非周期的从而状态0是遍历的。故所有状态i都是遍历的。因此只需考虑状态0是否正常返即可。第三节 极限定理及平稳分布.二、平稳分布与极限分布 1，定义：设pij是马尔可夫链Xn,n1的转移概率。若概率分布pj,j 0满足则称pj,j 0为Xn,n1的平稳分布。记第三节 极限定理及平稳分布.则平稳分布可表示为如下矩阵形式显然有即 若马尔可夫链Xn,n0的初始分布pj=PX0=j是平稳分布，则对任意的n，有 即Xn与X0有相同的 分布，这说明过程Xn,n0是平稳过程。这也是称分布pj=PX0=j 为平稳分布的原因。二、平稳分布与极限分布第三节 极限定理及平稳分布.2，定义：若马尔可夫链是遍历的（即所有状态相通且均为周期为1的正常返态），则极限称为马尔可夫链的极限分布。显然此时二、平稳分布与极限分布第三节 极限定理及平稳分布.定理：一个不可约非周期的马尔可夫链属于下列两种情况之一：1，状态或全是滑过的（非常返的）或全是零常返的。此时对一切的 i,j 有二、平稳分布与极限分布第三节 极限定理及平稳分布因而不存在平稳分布。2，状态全是正常返态。即此时是平稳分布，且不存在任何其它的平稳分布。此时极限分布即是平稳分布。.只证2，若马尔可夫链是遍历的,则存在，且下证是平稳分布，证明：（1）显然二、平稳分布与极限分布第三节 极限定理及平稳分布.利用C-K方程从而是平稳分布。二、平稳分布与极限分布第三节 极限定理及平稳分布.再证是惟一的平稳分布，假设另外还有一个平稳分布则二、平稳分布与极限分布第三节 极限定理及平稳分布.注：1，对于不可约的遍历链（不可约、正常返、周期为1）因为所以，可被解释为马尔可夫链长时间之后处于状态的的时间所占的比率。二、平稳分布与极限分布第三节 极限定理及平稳分布.2，对于不可约的遍历链，因为极限分布存在且等于平稳分布，这意味着当n充分大时有，即Xn,n0是一渐近平稳序列(平稳过程)，这在实际问题中是很有意义的。二、平稳分布与极限分布第三节 极限定理及平稳分布.例例 1 设状态空间为设状态空间为S=0,1,2,的马尔可夫链的马尔可夫链,其一步其一步 转移概率矩阵为转移概率矩阵为试求它的极限分布试求它的极限分布解解 易知此链为不可约遍历链易知此链为不可约遍历链.故其平稳分布就是极限分布故其平稳分布就是极限分布第三节 极限定理及平稳分布.例例2 设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S=0,1,2,3,4,其一步转移概率矩阵为其一步转移概率矩阵为求它的平稳分布求它的平稳分布第三节 极限定理及平稳分布.解解 易知是不可约链易知是不可约链,且为遍历链且为遍历链.故其平稳分布存在且唯一故其平稳分布存在且唯一.平稳分布为平稳分布为第三节 极限定理及平稳分布.例例3 设有状态空间设有状态空间S=0,1,2,3,4,5,6的齐次马尔可夫链的齐次马尔可夫链 其一步转移概率矩阵为其一步转移概率矩阵为(1)试对试对S进行分类，并说明各状态类型进行分类，并说明各状态类型(2)求平稳分布，其平稳分布是否唯一？为什么？求平稳分布，其平稳分布是否唯一？为什么？(3)求求第三节 极限定理及平稳分布.2501634(1)第三节 极限定理及平稳分布.(2)由由(1)知知,该链有三个不同的正常返不可约闭集该链有三个不同的正常返不可约闭集所以平稳分布不唯一所以平稳分布不唯一三个闭集对应的转移概率矩阵分别为三个闭集对应的转移概率矩阵分别为第三节 极限定理及平稳分布.(2)由由(1)知知,该链有三个不同的正常返不可约闭集该链有三个不同的正常返不可约闭集解方程组解方程组平稳分布为平稳分布为第三节 极限定理及平稳分布.第三节 极限定理及平稳分布.例设有6个球（其中2个红球，4个白球）分放于甲、乙两个盒子中，每盒放3个，今每次从两个盒中各任取一球并进行交换，以 表示开始时甲盒中红球的个数，（）表示经n次交换后甲盒中的红球数。(1)求马氏链 ，的转移概率矩阵；(2)证明 ，是遍历的；（3）求（4）求第三节 极限定理及平稳分布.解其一步转移矩阵为甲乙红球0白球3红球2白球1红球1白球2红球1白球2红球2白球1红球0白球3第三节 极限定理及平稳分布.并作出状态传递图1/32/95/92/32/91/30122/3（2）由于它是一个有限马氏链，故必有一个常返态，又链中三个状态0、1、2都相通，所以每个状态都是常返态。所以是一个不可约的有限马氏链，从而每个状态都是正常返的。所以此链为非周期的。故此链是不可约非周期的正常返链，即此链是遍历的。第三节 极限定理及平稳分布.（2）可以利用定理证明遍历性第三节 极限定理及平稳分布.第三节 极限定理及平稳分布.解之得故得第三节 极限定理及平稳分布.（4）第三节 极限定理及平稳分布.