《马尔可夫链》PPT课件

1、Markov 过程,安德雷.安德耶维奇.马尔可夫 (A.A.Markov): 俄数学家，18561922 概率和统计领域专家。 当年Markov研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了Markov过程的数学模型 Markov过程80年代兴起，在现代工程、自然科学、社会科学中应用广泛,Markov过程,1马尔可夫性,2. 马尔可夫过程,的条件分布函数恰好等于,3.马尔可夫链,定义 参数集和状态空间都是离散的马尔可夫过程 称为马尔可夫链,注 只讨论马尔可夫链的状态空间为有限或可列无限,则马尔可夫性可表示为,时间离散状态离散的马尔科夫链,时间离散状态连续的马尔科夫序列,时间连续状态连

2、续的马尔科夫过程,时间连续状态离散的马尔科夫过程,Markov过程,第六章 Markov链,第一节 基本概念,第二节 Markov链的状态分类及性质,第三节 极限定理及平稳分布,第四节 Markov链的应用,第六章 Markov链,第一节 基本概念,1. 转移概率,Chapman-kolmogorov方程,3. Markov链的分布,4.齐次Markov链,Markov 链举例,1. 转移概率,经过k步转移,于n+k时到达状态j的条件概率,在n时的k步转移概率,n时的k步转移概率矩阵,第一节 基本概念,特别 当k=1时,第一节 基本概念,1. 转移概率,特别k时，约定,第一节 基本概念,1.

3、转移概率,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方程,第

4、一节 基本概念,若取m=1,则由C-K方程的矩阵形式,得,分量形式,Chapman-kolmogorov方程,第一节 基本概念,定理 马尔可夫链的k 步转移概率由其一步 转移概率所完全确定,Chapman-kolmogorov方程,第一节 基本概念,1）初始分布,为马尔可夫链的初始分布,3.马尔可夫链 的分布,第一节 基本概念,2）有限维分布,证明,3.马尔可夫链 的分布,第一节 基本概念,2）有限维分布,3.马尔可夫链 的分布,第一节 基本概念,又因为马尔可夫链的k步转移概率由一步转移概率所 完全确定,所以马尔可夫链的有限维分布由其初始分布和 一步转移概率所完全确定,3.马尔可夫链 的分布,

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

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

7、一步转移概率矩阵为,例3(坛子放回摸球问题,第一节 基本概念,马尔可夫链举例,甲有赌资a元，乙有赌资b元，赌一局输者给赢者1元，无和局。甲赢的概率为p， 乙赢的概率为q=1-p，求甲输光的概率。 解 状态空间I=0,1,2,c，c=a+b,q p,a-1 a a+1,0 a+b,第一节 基本概念,马尔可夫链举例,例4(赌徒输光问题,设ui表示甲从状态i出发转移到状态0的概率，求ua 显然u0 =1，uc =0(u0表示已知甲输光情形下甲输光的概率，uc表示已知乙输光情形下甲输光的概率) ui =pui+1 + qui-1 (i=1,2,c-1) （甲在状态i下输光：甲赢一局后输光或甲输一局后输

8、光,第一节 基本概念,马尔可夫链举例,例4(赌徒输光问题,第一节 基本概念,第一节 基本概念,马尔可夫链举例,例4(赌徒输光问题,第一节 基本概念,第一节 基本概念,马尔可夫链举例,例4(赌徒输光问题,第一节 基本概念,第一节 基本概念,第一节 基本概念,例5 天气预报问题 RR表示连续两天有雨，记为状态0 NR表示第1天无雨第2天有雨，记为状态1 RN表示第1天有雨第2天无雨，记为状态2 NN表示连续两天无雨，记为状态3 p00=PR今R明| R昨R今=PR明| R昨R今=0.7 p01=PN今R明| R昨R今=0 p02=PR今N明| R昨R今= PN明| R昨R今=0.3 p03=PN今

9、N明| R昨R今=0,第一节 基本概念,类似地得到其他转移概率， 于是转移概率矩阵为 若星期一、星期二均下雨，求星期四下雨的概率,第一节 基本概念,星期四下雨的情形如右， 星期四下雨的概率 2步转移概率矩阵为,第一节 基本概念,第一节 基本概念,解,第一节 基本概念,第一节 基本概念,练习 设,是状态空间为a,b,c的齐次马氏链,其一步转移概率矩阵为,第一节 基本概念,第六章 Markov链,第一节 基本概念,第二节 Markov链的状态分类及性质,第三节 极限定理及平稳分布,第四节 Markov链的应用,1 基本概念,2 状态类别的划分和判别,3 状态间的关系,返回概率 平均返回时间 周期,

10、分类 判别,定义（可达、互通） 性质 互通的两个状态之间的关系,4 状态空间的分解,定义及重要结论（闭集、等价类） 分解定理（两个定理,第六章 Markov链,第二节 Markov链的状态分类及性质,一、基本概念,1.返回概率,自状态 i出发，经过n步首次到达状态j 的概率,自状态i出发，经有限步终于到达状态j的概率,自状态i出发，经有限步终于返回状态 i的概率,第二节 Markov链的状态分类及性质,定理1,说明1,该定理表示n步转移概率按照首次到达时间的所有可能值进行分解,说明2,第二节 Markov链的状态分类及性质,首达时间,系统从状态i出发， 首次到达状态j的时刻,称为从状态 i 出

11、发首次进入状态 j 的时间，或称自i 到j 的首达时间,如果这样的n不存在，规定,说明1,2.平均返回时间,一、基本概念,第二节 Markov链的状态分类及性质,说明2,平均返回时间,状态i的平均返回时间,2.平均返回时间,一、基本概念,第二节 Markov链的状态分类及性质,状态i的周期,若di 1,称i是周期的；若di =1,称i是非周期的,说明1,3.周期,di体现系统的发展变化种状态i重复出现的概率周期,说明2,若i的周期是di，并不是对所有的n满足,说明3,一、基本概念,第二节 Markov链的状态分类及性质,greatest common divisor,1 基本概念,2 状态类别

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

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

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

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

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

17、 有关等价类,2）一些重要结论,四、状态空间的分解,第二节 Markov链的状态分类及性质,结论2 设C是闭集，当且仅当C中的任何两个状态都互通时， C是不可约的,结论1 等价类若是闭集，则必定是不可约的,结论3 齐次马氏链不可约的充要条件是它的任意两个状态均互通,结论4 包含常返态的等价类是不可约闭集,例1,其一步转移矩阵为,试研究各状态间的关系，并画出状态传递图,第二节 Markov链的状态分类及性质,四、状态空间的分解,由图可知,状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0,因此，状态空间I的各状态都是互通的,又由于I 的任意状态i (i = 0

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

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

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

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

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

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

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

25、,i正常返,i正常返且非周期 （即遍历,i正常返且周期为d,第三节 极限定理及平稳分布,例,设马氏链的状态空间I = 0,1,2,，转移概率为,试讨论各状态的遍历性,第三节 极限定理及平稳分布,解,根据转移概率作出状态传递图,第三节 极限定理及平稳分布,从图可知，对任一状态 都有,故由定理可知，I 中的所以状态都是相通的,因此只需考虑状态0是否正常返即可,故,从而0是常返态,又因为,所以状态0为正常返,又由于,故状态0为非周期的,从而状态0是遍历的,故所有状态i都是遍历的,因此只需考虑状态0是否正常返即可,第三节 极限定理及平稳分布,二、平稳分布与极限分布,1，定义：设pij是马尔可夫链Xn,

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

27、非周期的马尔可夫链属于下列两种情况之一： 1，状态或全是滑过的（非常返的）或全是零常返的。此时对一切的 i, j 有,二、平稳分布与极限分布,第三节 极限定理及平稳分布,因而不存在平稳分布。 2，状态全是正常返态。即,此时,是平稳分布，且不存在任何其它的平稳分布。此时极限分布 即是平稳分布,只证2，若马尔可夫链是遍历的,则,存在，且,证明：（1）显然,二、平稳分布与极限分布,第三节 极限定理及平稳分布,利用C-K方程,从而,是平稳分布,二、平稳分布与极限分布,第三节 极限定理及平稳分布,再证,是惟一的平稳分布，假设另外还,有一个平稳分布,则,二、平稳分布与极限分布,第三节 极限定理及平稳分布,注：1，对于不可约的遍历链（不可约、正常返、周期为1） 因为,所以， 可被解释为马尔可夫链长时间之后处于状态 的的时间所占的比率,二、平稳分布与极限分布,第三节 极限定理及平稳分布,2，对于不可约的遍历链，因为极限分布存在且等于平 稳分布，这意味着当n充分大时有,即Xn,n0是一渐近平稳序列(平稳过程)，这在实际问题中是很有意义的,二