第四章 马尔可夫链.ppt

1、第四章 马尔可夫链,1、马尔可夫性(无后效性),一、马尔可夫链的定义和转移概率,当已知随机过程在时刻 所处的状态的条件下,过程“将来”的情况和“过去”的情况无关.,过程在t(ti)所处的状态与过程在时刻ti以前所处的,这种特性称为马尔可夫性或 “无后效性”.,具有马尔可夫性的随机过程称为马尔可夫过程.,状态无关,2020年7月10日星期五,参数和状态都是离散的马尔可夫过程称为马尔,可夫链,2、马尔可夫链的定义和转移概率,马氏链的马尔可夫性可具体描述为：,Pij表示处于状态i的过程下一步转移到状态j的概率.,2020年7月10日星期五,Pij称为一步转移概率，由所有的一步转移概率构成,的矩阵,称

2、为一步转移概率矩阵.,显然有,具有这种平稳转移概率的马尔可夫链称为齐次的,2020年7月10日星期五,例1 一维随机游动,游动的概率规则,3、马尔可夫链举例,2020年7月10日星期五,1和5这两点称为反射壁.,上面这种游动称为带有两个反射壁的随机游动.,理论分析:,2020年7月10日星期五,单击图形播放/暂停 ESC键退出,一维随机游动的演示,2020年7月10日星期五,一步转移概率,一步转移概率矩阵,2020年7月10日星期五,说明:,改变游动的概率规则,随机游动和相应的马氏链.,就可得到不同方式的,如果把1改为吸收壁，即一旦到达1点，将永,远留在1点,相应链的转移概率矩阵只需把P的第,

3、一行改成,2020年7月10日星期五,例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年7月10日星期五,2020年7月10日星期五,4、齐次马氏链的性质,定义：,记,称为齐次马氏链的初始分布.,定理: 齐次马氏链完全由其初始分布和一步转移,概率矩阵确定.,证,20

4、20年7月10日星期五,5、切普曼-柯尔莫哥洛夫方程,在齐次条件下，,可得到n步转移概率,由所有的n步转移概率就可得到n步转移概率矩阵,显然有,2020年7月10日星期五,切普曼-柯尔莫哥洛夫方程(C-K方程):,对任意的m,n0,有,即n步转移概率矩阵等于一步转移概率矩阵自乘n次.,为了数学处理便利，通常规定,2020年7月10日星期五,一步转移概率矩阵为,例3,2020年7月10日星期五,解,先求出二步转移概率矩阵,于是:,2020年7月10日星期五,2020年7月10日星期五,解,例4,2020年7月10日星期五,2020年7月10日星期五,2020年7月10日星期五,课堂练习,2020

5、年7月10日星期五,解,(3),2020年7月10日星期五,设Xn, n0是齐次马尔可夫链,pij为转移概率, i,jI,I=1,2,为状态空间,pi, i I为初始分布. 状态i的周期d： d=G.C.Dn:n1, 0 (最大公约数greatest common divisor) 如果d 1，就称i为周期的; 如果d =1，就称i为非周期的.,定义,二、马尔可夫链的状态分类,2020年7月10日星期五,例5 设马尔可夫链的状态空间I=1,2,3,4，转移概 率如下图,易得状态2和3有相同的周期d=2.但是从状态3出发,经两步必定返回状态3，而从状态2出发一旦转移,到状态3后再也不能返回状态2

6、.,为了区别这两种状态，下面引入常返性概念,2020年7月10日星期五,由状态i出发经n步首次到达j的概率(首达概率),规定,由i出发经有限步终于到达j的概率,2020年7月10日星期五,若fii=1，称状态i为常返的； 若fii1，称状态i为非常返的.,定义,注：,表示由i出发再返回到i的平均返回时间(步数）.,(1) 若状态i为非常返的,则由该状态出发将,以1-fii的概率永不返回.,(2) 若状态i为常返的,则 构成一 概率分布，其期望值为,2020年7月10日星期五,若i ，则称常返态i为正常返的; 若i =，则称常返态i为零常返的. 非周期的正常返态称为遍历状态.,设i为常返态,定义

7、,例：判断下面马氏链各状态的类型,2020年7月10日星期五,马氏链状态分类图,2020年7月10日星期五,如果存在n0,使 ,称自状态i可达状态j ,状态的可达与互通,并记为,注：可达关系与互通关系都具有传递性 (1) 若ij , jk ,则ik ; (2) 若ij , jk ,则ik .,2020年7月10日星期五,定理 若ij ，则 (1) i与j同为常返或非常返,如为常返,则它们同 为正常返或零常返; (2) i与j有相同的周期.,2020年7月10日星期五,例6 设马氏链Xn的状态空间I=0,1,2,转 移概率为,试讨论各状态的常返性和周期性.,解：根据题意作出状态转移图如下,202

8、0年7月10日星期五,从而是遍历状态. 对于其它状态i,由于i0,故也都是遍历状态.,可见0是正常返态.,所以0为非周期的，,对互通状态的识别，只需对最简单的状态判断即可.,2020年7月10日星期五,状态空间I 的子集C称为闭集,如对任意iC 及kC都有pik=0; 如果闭集C的状态互通,称C为不可约的; 如果马氏链Xn的状态空间不可约,称其为不 可约的.,三、状态空间的分解,注:(1) 闭集的意思是自C的内部不能到达C的外部;,(2) 如果pii=1,则称状态i为吸收的.,定义：,2020年7月10日星期五,例7 设马氏链Xn的状态空间为 I=1, 2, 3, 4, 5， 转移概率矩阵为,

9、状态3是吸收的,故3是闭集;,1,4,1,3,4,1,2,3,4,其中3,1,4是不可约的;,I含有闭子集,故Xn不是不可约的链.,都是闭集,2020年7月10日星期五,任一马氏链的状态空间I,可唯一地分解成有限 个或可列个互不相交的子集D,C1,C2,之和，使得： (1) 每一Cn是常返态组成的不可约闭集； (2) Cn中的状态同类型,或全是正常返,或全是零常 返,它们有相同的周期,且fij=1,i,jCn； (3) D由全体非常返态组成,自Cn中状态不能到达D中 的状态.,由于自常返态只能到达常返态,因此I中全体常返,态组成一闭集C,在C中根据互通关系可进一步分类.,分解定理：,2020年7月10日星期五,例8 马氏链的状态空间I =1,2,3,4,5,6,转移概率矩阵,其中Cn是由常返态组成的不可约闭集,称为,基本常返闭集.,试分解此链并指出各状态的常返性及周期性.,2020年7月10日星期五,同理对状态6：,解: 由状态转移图知,又状态3、5和1互通，,C1=1,3,5.,故状态3与5也是周期为3的,可见1为正常返态且周期为3;,正常返态,包含1的基本常返闭集为,故f11=1,故f66=1,2020年7月10日星期五,于是I 可分解为 I=DC1C2,C2=2,6.,非周期的正常返态，,