(优选)第六章马尔可夫链课件

1、（优选）第六章马尔可夫链Markov 过程 安德雷.安德耶维奇.马尔可夫 (A.A.Markov): 俄数学家，18561922 概率和统计领域专家。 当年Markov研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了Markov过程的数学模型 Markov过程80年代兴起，在现代工程、自然科学、社会科学中应用广泛。2022/7/14Markov过程1马尔可夫性通俗地说，就是在知道过程现在的条件下，其将来的条件分布不依赖于过去，则称具有马尔可夫（Markov)性。定义设是一个随机过程，如果在t0时刻所处的状态为已知，它在时刻 所处状态的条件分布与其在 t0 之前 所处的状态无关。2. 马

2、尔可夫过程定义 设的状态空间为S,的条件分布函数恰好等于3.马尔可夫链定义 参数集和状态空间都是离散的马尔可夫过程称为马尔可夫链。注 只讨论马尔可夫链的状态空间为有限或可列无限.则马尔可夫性可表示为2022/7/147 时间离散状态离散的马尔科夫链 时间离散状态连续的马尔科夫序列 时间连续状态连续的马尔科夫过程 时间连续状态离散的马尔科夫过程Markov过程8/32 第六章 Markov链第一节 基本概念第二节 Markov链的状态分类及性质第三节 极限定理及平稳分布第四节 Markov链的应用9/32 第六章 Markov链第一节 基本概念1. 转移概率. Chapman-kolmogoro

3、v方程3. Markov链的分布4.齐次Markov链.Markov 链举例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

4、方程)或矩阵形式（解决了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-kol

5、mogorov方程第一节 基本概念1）初始分布为马尔可夫链的初始分布3.马尔可夫链 的分布称 第i个分量为的(行)向量为马尔可夫链的初始分布向量. 即第一节 基本概念2）有限维分布定理 马尔可夫链的有限维分布由其初始分布和一步转移概率所完全确定.证明3.马尔可夫链 的分布第一节 基本概念2）有限维分布3.马尔可夫链 的分布第一节 基本概念又因为马尔可夫链的k步转移概率由一步转移概率所完全确定.所以马尔可夫链的有限维分布由其初始分布和一步转移概率所完全确定.3.马尔可夫链 的分布第一节 基本概念2）有限维分布3）绝对分布为马尔可夫链 的绝对分布称 第j个分量为的(行)向量为马尔可夫链的绝对分布向

6、量. 即绝对分布、初始分布和n步转移概率有如下关系：或矩阵形式3.马尔可夫链 的分布第一节 基本概念3）绝对分布3.马尔可夫链 的分布第一节 基本概念4.齐次马尔可夫链定义是一马尔可夫链,如果其一步转移概率恒与起始时刻n无关，记为为齐次(时间其次或时齐)马尔可夫链.否则，称为非齐次马尔可夫链.显然对齐次马尔可夫链，k步转移概率也与起始时刻n无关记为第一节 基本概念为方便，一般假定时间起点为零即相应的k步与一步转移概率矩阵分别记为定理 的有限维分布由其初始分布和一步转移概率所完全确定4.齐次马尔可夫链第一节 基本概念例(天气预报问题) 如果明天是否有雨仅与今天的天气(是否有雨)有关，而与过去的天

7、气无关. 并设今天下雨、明天有雨的概率为a，今天无雨而明天有雨的概率为b，又假设有雨称为0状态天气，无雨称为1状态天气. Xn表示时刻n时的天气状态，则是以为状态空间的齐次马尔可夫链.其一步转移概率矩阵为.马尔可夫链举例第一节 基本概念 例2(有限制随机游动问题) 设质点只能在0，1，2，a中的各点上作随机 游动，移动规则如下：ii+1i-101a-1a第一节 基本概念.马尔可夫链举例设Xn表示质点在n时刻所处的位置，则其一步转移概率矩阵为 例2(有限制随机游动问题)第一节 基本概念.马尔可夫链举例设一个坛子中装有m个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反颜色的

8、球.为状态空间的齐次马尔可夫链.设经过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表示已知乙输光情形下甲输光

9、的概率) 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=

10、PN今R明| R昨R今=0p02=PR今N明| R昨R今= PN明| R昨R今=0.3p03=PN今N明| R昨R今=0第一节 基本概念类似地得到其他转移概率，于是转移概率矩阵为若星期一、星期二均下雨，求星期四下雨的概率第一节 基本概念星期四下雨的情形如右，星期四下雨的概率2步转移概率矩阵为一二三四RRRR00RRNR01第一节 基本概念例6 设是具有三个状态0，1，2的齐次马尔可夫链，其一步转移概率矩阵为初始分布试求：第一节 基本概念解第一节 基本概念第一节 基本概念练习 设是状态空间为a,b,c的齐次马氏链.其一步转移概率矩阵为第一节 基本概念45/32 第六章 Markov链第一节 基本

11、概念第二节 Markov链的状态分类及性质第三节 极限定理及平稳分布第四节 Markov链的应用 1 基本概念2 状态类别的划分和判别3 状态间的关系 返回概率平均返回时间周期分类判别定义（可达、互通）性质互通的两个状态之间的关系4 状态空间的分解 定义及重要结论（闭集、等价类）分解定理（两个定理） 第六章 Markov链第二节 Markov链的状态分类及性质一、基本概念1.返回概率自状态 i出发，经过n步首次到达状态j 的概率自状态i出发，经有限步终于到达状态j的概率自状态i出发，经有限步终于返回状态 i的概率第二节 Markov链的状态分类及性质定理1 对任意及，有说明1该定理表示n步转移

12、概率按照首次到达时间的所有可能值进行分解说明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一、基本概

13、念第二节 Markov链的状态分类及性质greatest common divisor 1 基本概念2 状态类别的划分和判别返回概率平均返回时间周期分类判别第二节 Markov链的状态分类及性质二、状态类别的划分及判别1.状态类别的划分状态 i非常返态常返态零常返态正常返态周期非周期（遍历态）常返态非常返态正常返态零常返态第二节 Markov链的状态分类及性质注“常返”一词，有时又称“返回”、“常驻”或“持久”“瞬时”也称“滑过” 或“非常返”定理2证则系统从状态i出发，经过有限次转移之后，必定以概率1返回状态i。再由马氏性系统返回状态i要重复发生这样，系统从状态i出发，又返回，再出发，再返回

14、，随着时间的无限推移，将无限次访问状态i。第二节 Markov链的状态分类及性质将“不返回i”称为成功，则首次成功出现的次数服从几何分布，也就是说以概率1只有有穷次返回i。即第二节 Markov链的状态分类及性质2.判别（1）判别是否常返态定理3第二节 Markov链的状态分类及性质2.判别（2）判别是否零常返态、正常返有（非）周期定理4对任意给定的状态i，如果i是常返态且有周期di，则存在极限第二节 Markov链的状态分类及性质2.判别（3）判别是否有周期第二节 Markov链的状态分类及性质 1 基本概念2 状态类别的划分和判别3 状态间的关系 返回概率平均返回时间周期分类判别第二节 M

15、arkov链的状态分类及性质定义（可达、互通）性质互通的两个状态之间的关系三、状态间的关系1.定义状态 i可达状态j2.性质简记为 ij状态 i与状态j互通ijj i且传递性、对称性第二节 Markov链的状态分类及性质三、状态间的关系3.利用首达概率刻画可达和互通关系第二节 Markov链的状态分类及性质结论1结论24.互通的两个状态的状态类型互通的两个状态必有相同的状态类型定理5三、状态间的关系第二节 Markov链的状态分类及性质63/34 1 基本概念2 状态类别的划分和判别3 状态间的关系 返回概率平均返回时间周期分类判别第二节 Markov链的状态分类及性质定义（可达、互通）性质互

16、通的两个状态之间的关系4 状态空间的分解 定义及重要结论（闭集、等价类）分解定理（两个定理）四、状态空间的分解互通满足：自反性、对称性、传递性。互通是一种等价关系（常返态） 按互通关系是等价关系，可以把状态空间 I 划分为若干个不相交的集合（或者说等价类），并称之为状态类。 若两个状态相通，则这两个状态属于同一类。 任意两个类或不相交或者相同。说明第二节 Markov链的状态分类及性质（1）定义四、状态空间的分解第二节 Markov链的状态分类及性质A闭集设C为状态空间I 的一个子集，则C称为闭集。注1 若C为闭集，则表示自C内任意状态i出发，始终不能到达C以外的任何状态j。 整个状态空间构成

17、一个闭集。吸收态指一个闭集中只含一个状态（1）定义四、状态空间的分解第二节 Markov链的状态分类及性质A闭集设C为状态空间I 的一个子集，则C称为闭集。注2若状态空间含有吸收状态，那么这个吸收状态构成一个最小的闭集。（1）定义四、状态空间的分解第二节 Markov链的状态分类及性质B不可约的 设C为闭集，如果C中不再含有任何非空真闭子集，则称C是不可约闭集，或称不可约的，不可分的，最小的。 若整个状态空间是不可约的，则称此链为不可约马氏链。A.有关闭集（2）一些重要结论四、状态空间的分解第二节 Markov链的状态分类及性质B. 有关等价类（2）一些重要结论四、状态空间的分解第二节 Mar

18、kov链的状态分类及性质 结论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 以

19、外的任何状态，所以I是一个闭集而且I 中没有其它闭集所以此马氏链是不可约的。解先按一步转移概率，画出各状态间的传递图第二节 Markov链的状态分类及性质例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。第二节 Markov链的状态分类及性质四、状态空间的分解111/21/21/2311/24521 闭集，由图可知状态3为吸收态且闭集，闭集，其中 是不可约的。又因状态空间I有闭子集，故此链为非不可约链。解先按一步转移概率，画出各状态间的传递图第二节 Markov链的状态分类及性质（3）状态空间的分解如果已知类中有一个常返态，则这个类中其它状态都是常返的。若类中有一个非常返态，则类中其

20、它状态都是非常返态。若对不可约马氏链，则要么全是常返态，要么全是非常返态。第二节 Markov链的状态分类及性质四、状态空间的分解定理6任一马氏链的状态空间I必可分解为其中N是非常返态集，而且（3）状态空间的分解第二节 Markov链的状态分类及性质四、状态空间的分解如果从某一非常返态出发，系统可能一直在非常返集中，也可能进入某个常返闭集，一旦进入某个常返闭集后，将一直停留在这个常返闭集中；如果系统从某一常返状态出发，则系统就一直停留在这个状态所在的常返闭集中。说明1（3）状态空间的分解第二节 Markov链的状态分类及性质四、状态空间的分解定理7（1）非常返态集N不可能是闭集；（2）至少有一

21、个常返态；（3）不存在零常返态；（4）若链是不可约的，那么状态都是正常返的（5）其状态空间可分解为是互不相交的由正常返态组成的闭集。（3）状态空间的分解第二节 Markov链的状态分类及性质四、状态空间的分解定理8(周期链分解定理)（3）状态空间的分解第二节 Markov链的状态分类及性质四、状态空间的分解转移概率矩阵的标准形式状态空间的分解周期链的分解第二节 Markov链的状态分类及性质四、状态空间的分解例转移矩阵试对其状态分类。第二节 Markov链的状态分类及性质四、状态空间的分解解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143第二节 Markov链的状态分

22、类及性质四、状态空间的分解从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。82/34考虑状态1是否常返，第二节 Markov链的状态分类及性质四、状态空间的分解类似地可求得所以于是状态1是常返的。又因为所以状态1是正常返的。由定理可知，此链所有状态都是正常返的。第二节 Markov链的状态分类及性质四、状态空间的分解例设马氏链的状态空间I = 0,1,2,，转移概率为试讨论各状态的遍历性。第二节 Markov链的状态分类及性质四、状态空间的分解解根据转移概率作出状态传递图1/21/21/21/21/21/20121/231/2第二节 Markov链的状态分类及性质四、状态空间的

23、分解从图可知，对任一状态 都有 ，故由定理可知，I 中的所以状态都是相通的，因此只需考虑状态0是否正常返即可。故从而0是常返态。又因为所以状态0为正常返。又由于故状态0为非周期的从而状态0是遍历的。故所有状态i都是遍历的。第二节 Markov链的状态分类及性质四、状态空间的分解一般情况End.第二节 Markov链的状态分类及性质四、状态空间的分解88/32 第六章 Markov链第一节 基本概念第二节 Markov链的状态分类及性质第三节 极限定理及平稳分布第四节 Markov链的应用89/32 第六章 Markov链第三节 极限定理及平稳分布一、极限定理二、平稳分布与极限分布一、极限定理例

24、 设马尔可夫链的转移概率矩阵为现在来计算令第三节 极限定理及平稳分布则所以一、极限定理第三节 极限定理及平稳分布定理：若i与j相通，则(3), 若j是非周期的, 则(4), 若j有周期d, 则一、极限定理第三节 极限定理及平稳分布一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。推论1：如i是常返的，则i为零常返的充要条件是一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。推论2：如i是遍历的(正常返的并且是非周期的)，则一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零

25、常返的。1，若j为非常返或零常返的，则 有2，若j为常返的且周期为d，则 有 推论3（遍历性定理）一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。 推论5：有限状态的马尔可夫链，不可能全为非常返状态，也不可能有零常返状态。从而不可约的有限马尔可夫链的状态全为正常返的。一、极限定理第三节 极限定理及平稳分布记则，如i是常返的，当 时为正常返的。当 时为零常返的。推论6：若马尔可夫链有一个零常返态，则必有无限个零常返态。状态性质判别法i非常返i零常返i正常返i遍历的i正常返i正常返且非周期（即遍历）i正常返且周期为d第三节 极限定理及平稳分布例设马氏链

26、的状态空间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

27、0为Xn, n1的平稳分布。记第三节 极限定理及平稳分布则平稳分布可表示为如下矩阵形式显然有即 若马尔可夫链Xn, n0的初始分布pj=PX0=j是平稳分布，则对任意的n，有 即Xn与X0有相同的 分布，这说明过程Xn, n0是平稳过程。这也是称分布pj=PX0=j 为平稳分布的原因。二、平稳分布与极限分布第三节 极限定理及平稳分布2，定义：若马尔可夫链是遍历的（即所有状态相通且均为周期为1的正常返态），则极限称为马尔可夫链的极限分布。显然此时二、平稳分布与极限分布第三节 极限定理及平稳分布 定理：一个不可约非周期的马尔可夫链属于下列两种情况之一： 1，状态或全是滑过的（非常返的）或全是零常返

28、的。此时对一切的 i, j 有二、平稳分布与极限分布第三节 极限定理及平稳分布因而不存在平稳分布。2，状态全是正常返态。即此时是平稳分布，且不存在任何其它的平稳分布。此时极限分布即是平稳分布。只证2，若马尔可夫链是遍历的,则存在，且下证是平稳分布，证明：（1）显然二、平稳分布与极限分布第三节 极限定理及平稳分布利用C-K方程从而是平稳分布。二、平稳分布与极限分布第三节 极限定理及平稳分布再证是惟一的平稳分布，假设另外还有一个平稳分布则二、平稳分布与极限分布第三节 极限定理及平稳分布注：1，对于不可约的遍历链（不可约、正常返、周期为1）因为所以， 可被解释为马尔可夫链长时间之后处于状态的的时间所占的比率。二、平稳分布与极限分布第三节 极限定理及平稳分布2，对于不可约的遍历链，因为