第四章 马尔可夫链

第四章马尔可夫链,1、马尔可夫性(无后效性),一、马尔可夫链的定义和转移概率,当已知随机过程在时刻所处的状态的条件下,过程“将来”的情况和“过去”的情况无关.,过程在t(ti)所处的状态与过程在时刻ti以前所处的,这种特性称为马尔可夫性或“无后效性”.,具有马尔可夫性的随机过程称为马尔可夫过程.,状态无关,2020/6/4,参数和状态都是离散的马尔可夫过程称为马尔,可夫链,2、马尔可夫链的定义和转移概率,马氏链的马尔可夫性可具体描述为：,Pij表示处于状态i的过程下一步转移到状态j的概率.,2020/6/4,Pij称为一步转移概率，由所有的一步转移概率构成,的矩阵,称为一步转移概率矩阵.,显然有,具有这种平稳转移概率的马尔可夫链称为齐次的,2020/6/4,例1一维随机游动,游动的概率规则,3、马尔可夫链举例,2020/6/4,1和5这两点称为反射壁.,上面这种游动称为带有两个反射壁的随机游动.,理论分析:,2020/6/4,单击图形播放/暂停ESC键退出,一维随机游动的演示,2020/6/4,一步转移概率,一步转移概率矩阵,2020/6/4,说明:,改变游动的概率规则,随机游动和相应的马氏链.,就可得到不同方式的,如果把1改为吸收壁，即一旦到达1点，将永,远留在1点,相应链的转移概率矩阵只需把P的第,一行改成,2020/6/4,例2取球问题,有甲、乙两袋球,开始时甲袋有3只球,乙袋有,则Xn,n=1,2,是一随机过程，,2球；以后,每次任取一袋,并从袋中取出一球放入,另一袋(若袋中无球则不取).,以Xn表示第n次抽取后甲袋的球数,n=1,2,其一步转移概率矩阵为：,且当Xn=i时,Xn+1=j的概率只与i有关，与n时刻,I=0,1,2,3,4,5,之前的结果是无关的，从而是一个齐次马氏链.,2020/6/4,2020/6/4,4、齐次马氏链的性质,定义：,记,称为齐次马氏链的初始分布.,定理:齐次马氏链完全由其初始分布和一步转移,概率矩阵确定.,证,2020/6/4,5、切普曼-柯尔莫哥洛夫方程,在齐次条件下，,可得到n步转移概率,由所有的n步转移概率就可得到n步转移概率矩阵,显然有,2020/6/4,切普曼-柯尔莫哥洛夫方程(C-K方程):,对任意的m,n0,有,即n步转移概率矩阵等于一步转移概率矩阵自乘n次.,为了数学处理便利，通常规定,2020/6/4,一步转移概率矩阵为,例3,2020/6/4,解,先求出二步转移概率矩阵,于是:,2020/6/4,2020/6/4,解,例4,2020/6/4,2020/6/4,2020/6/4,课堂练习,2020/6/4,解,(3),2020/6/4,设Xn,n0是齐次马尔可夫链,pij为转移概率,i,jI,I=1,2,为状态空间,pi,iI为初始分布.状态i的周期d：d=G.C.Dn:n1,0(最大公约数greatestcommondivisor)如果d1，就称i为周期的;如果d=1，就称i为非周期的.,定义,二、马尔可夫链的状态分类,2020/6/4,例5设马尔可夫链的状态空间I=1,2,3,4，转移概率如下图,易得状态2和3有相同的周期d=2.但是从状态3出发,经两步必定返回状态3，而从状态2出发一旦转移,到状态3后再也不能返回状态2.,为了区别这两种状态，下面引入常返性概念,2020/6/4,由状态i出发经n步首次到达j的概率(首达概率),规定,由i出发经有限步终于到达j的概率,2020/6/4,若fii=1，称状态i为常返的；若fii1，称状态i为非常返的.,定义,注：,表示由i出发再返回到i的平均返回时间(步数）.,(1)若状态i为非常返的,则由该状态出发将,以1-fii的概率永不返回.,(2)若状态i为常返的,则构成一概率分布，其期望值为,2020/6/4,若i0,使,称自状态i可达状态j,状态的可达与互通,并记为,注：可达关系与互通关系都具有传递性(1)若ij,jk,则ik;(2)若ij,jk,则ik.,2020/6/4,定理若ij，则(1)i与j同为常返或非常返,如为常返,则它们同为正常返或零常返;(2)i与j有相同的周期.,2020/6/4,例6设马氏链Xn的状态空间I=0,1,2,转移概率为,试讨论各状态的常返性和周期性.,解：根据题意作出状态转移图如下,2020/6/4,从而是遍历状态.对于其它状态i,由于i0,故也都是遍历状态.,可见0是正常返态.,所以0为非周期的，,对互通状态的识别，只需对最简单的状态判断即可.,2020/6/4,状态空间I的子集C称为闭集,如对任意iC及kC都有pik=0;如果闭集C的状态互通,称C为不可约的;如果马氏链Xn的状态空间不可约,称其为不可约的.,三、状态空间的分解,注:(1)闭集的意思是自C的内部不能到达C的外部;,(2)如果pii=1,则称状态i为吸收的.,定义：,2020/6/4,例7设马氏链Xn的状态空间为I=1,2,3,4,5，转移概率矩阵为,状态3是吸收的,故3是闭集;,1,4,1,3,4,1,2,3,4,其中3,1,4是不可约的;,I含有闭子集,故Xn不是不可约的链.,都是闭集,2020/6/4,任一马氏链的状态空间I,可唯一地分解成有限个或可列个互不相交的子集D,C1,C2,之和，使得：(1)每一Cn是常返态组成的不可约闭集；(2)Cn中的状态同类型,或全是正常返,或全是零常返,它们有相同的周期,且fij=1,i,jCn；(3)D由全体非常返态组成,自Cn中状态不能到达D中的状态.,由于自常返态只能到达常返态,因此I中全体常返,态组成一闭集C,在C中根据互通关系可进一步分类.,分解定理：,2020/6/4,例8马氏链的状态空间I=1,2,3,4,5,6,转移概率矩阵,其中Cn是由常返态组成的不可约闭集,称为,基本常返闭集.,试分解此链并指出各状态的常返性及周期性.,2020/6/4,同理对状态6：,解:由状态转移图知,又状态3、5和1互通，,C1=1,3,5.,故状态3与5也是周期为3的,可见1为正常返态且周期为3;,正常返态,包含1的基本常返闭集为,故f11=1,故f66=1,2020/6/4,于是I可分解为I=DC1C2,C2=2,6.,非周期的正常返态，,因此状态6为,即遍