随机过程Ch4马尔可夫链.ppt

《随机过程Ch4马尔可夫链.ppt》由会员分享，可在线阅读，更多相关《随机过程Ch4马尔可夫链.ppt（113页珍藏版）》请在三一办公上搜索。

1、第四章 马尔可夫链,4.1 马尔可夫链与转移概率,定义 设 X(t)，t T 为随机过程，若对任意正整数n及t10，且条件分布PX(tn)xn|X(t1)=x1,X(tn-1)=xn-1=PX(tn)xn|X(tn-1)=xn-1，则称X(t)，t T 为马尔可夫过程。若t1,t2,tn-2表示过去，tn-1表示现在，tn表示将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与过去状态无关。,4.1 马尔可夫链与转移概率,常见马尔可夫过程通常有三类：(1)时间、状态都是离散的，称为马尔可夫链(2)时间连续、状态离散的，称为连续时间马尔可夫链(3)时间、状态都是连续的，称为马尔可夫过

2、程（时间离散、状态连续的马尔可夫过程，通常用泛函中二元函数的范数进行研究）,随机过程Xn，nT，参数T=0,1,2,状态空间I=i0,i1,i2,定义 若随机过程Xn，nT，对任意nT和i0,i1,in+1 I，条件概率PXn+1=in+1|X0=i0,X1=i1,Xn=in=PXn+1=in+1|Xn=in，则称Xn，nT 为马尔可夫链，简称马氏链。,4.1 马尔可夫链与转移概率,4.1 马尔可夫链与转移概率,马尔可夫链的性质 PX0=i0,X1=i1,Xn=in=PXn=in|X0=i0,X1=i1,Xn-1=in-1 PX0=i0,X1=i1,Xn-1=in-1=PXn=in|Xn-1=

3、in-1 PXn-1=in-1|X0=i0,X1=i1,Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-2=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-2,4.1 马尔可夫链与转移概率,=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2 PX1=i1|X0=i0PX0=i0 马尔可夫链的统计特性完全由条件概率PXn+1=in+1|Xn=in确定。,4.1 马尔可夫链与转移概率,定义 称条件概率pij(n)=PXn+1=j|Xn=i 为马尔可夫链Xn，nT 在时刻n的一步转移概率，简称转

4、移概率，其中i,jI。定义 若对任意的i,jI，马尔可夫链Xn,nT 的转移概率pij(n)与n无关，则称马尔可夫链是齐次的，并记pij(n)为pij。齐次马尔可夫链具有平稳转移概率，状态空间I=1,2,3,，一步转移概率为,4.1 马尔可夫链与转移概率,转移概率性质(1)(2)P称为随机矩阵,4.1 马尔可夫链与转移概率,例4.1 赌博问题。甲乙二人进行一系列赌博，甲有a元，乙的赌本无限，每赌一局输者给赢者1元，没有和局，如果甲输光，再输则赌本为负。设在每一局中，甲赢的概率为p，输的概率为q=1-p。设Xn表示第n次赌博结束后甲的赌本，则Xn，n1是马尔科夫链，求Xn的转移矩阵,4.1 马尔

5、可夫链与转移概率,例4.1 无限制随机游动,q p,-1 0 1 i-1 i i+1,一步转移概率:,4.1 马尔可夫链与转移概率,n步转移概率:i经过k步进入j,向右移了x步,向左移了y步则,4.1 马尔可夫链与转移概率,例4.4 具有吸收壁和反射壁的随机游动状态空间1,2,3,4，1为吸收壁，4为反射壁 状态转移图 状态转移矩阵,4.1 马尔可夫链与转移概率,定义 称条件概率=PXm+n=j|Xm=i 为马尔可夫链Xn，nT 的n步转移概率(i,jI,m0,n1)。n步转移矩阵其中 P(n)也为随机矩阵,4.1 马尔可夫链与转移概率,定理4.1 设Xn，nT 为马尔可夫链，则对任意整数n0

6、,0ln和i,jI，n步转移概率 具有性质(1)(2)(3)P(n)=PP(n-1)(4)P(n)=Pn,4.1 马尔可夫链与转移概率,证(1),4.1 马尔可夫链与转移概率,(2)在(1)中令l=1,k=k1,得由此可递推出公式(3)矩阵乘法(4)由(3)推出说明：(1)此为C-K方程(切普曼-柯尔莫哥洛夫)(2)n步转移概率由一步转移概率确定，n步转移概率矩阵由一步转移概率矩阵确定(n次幂),4.1 马尔可夫链与转移概率,初始概率绝对概率初始分布绝对分布初始概率向量绝对概率向量,定义,4.1 马尔可夫链与转移概率,设Xn，nT 为马尔可夫链，则对任意整数jI和n1，绝对概率pj(n)具有性

7、质(1)(2)(3)PT(n)=PT(0)P(n)(4)PT(n)=PT(n-1)P,定理4.2,例如，设马氏链的状态空间I=1,2，那么时刻n的绝对概率分布 应满足,PT(n)=(p1(n),p2(n),PT(n)=PT(0)P(n),4.1 马尔可夫链与转移概率,证(1),4.1 马尔可夫链与转移概率,(2)(3)(4)为(1)(2)的矩阵表示。,4.1 马尔可夫链与转移概率,定理4.3 设Xn，nT 为马尔可夫链，则对任意整数i1,i2,inI和n1，有性质证,4.1 马尔可夫链与转移概率,例4.2 赌徒输光问题 甲有赌资a元，乙有赌资b元，赌一局输者给赢者1元，无和局。甲赢的概率为p，

8、乙赢的概率为q=1-p，求甲输光的概率。解 状态空间I=0,1,2,c，c=a+b,q p,a-1 a a+1,0 a+b,4.1 马尔可夫链与转移概率,设ui表示甲从状态i出发转移到状态0的概率，求ua 显然u0=1，uc=0(u0表示已知甲输光情形下甲输光的概率，uc表示已知乙输光情形下甲输光的概率)ui=pui+1+qui-1(i=1,2,c-1)（甲在状态i下输光：甲赢一局后输光或甲输一局后输光）,4.1 马尔可夫链与转移概率,4.1 马尔可夫链与转移概率,4.1 马尔可夫链与转移概率,4.1 马尔可夫链与转移概率,4.1 马尔可夫链与转移概率,例4.3 天气预报问题 RR表示连续两天

9、有雨，记为状态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,4.1 马尔可夫链与转移概率,类似地得到其他转移概率，于是转移概率矩阵为若星期一、星期二均下雨，求星期四下雨的概率,4.1 马尔可夫链与转移概率,星期四下雨的情形如右，星期四下雨的概率2步转移概率矩阵为,4.2 马尔可夫链的状态分类,Xn,n0是离散马尔可夫链，pij为转移概率，i,jI，I=0,

10、1,2,为状态空间，pj,jI为初始分布定义4.3 状态i的周期d：d=G.C.Dn:0(最大公约数greatest common divisor)如果d1，就称i为周期的，如果d=1，就称i为非周期的,4.2 马尔可夫链的状态分类,例4.6 设马尔可夫链的状态空间I=1,2,9，转移概率如下图 从状态1出发再返回状态1的可能步数为T=4,6,8,10,，T的最大公约数为2，从而状态1的周期为2,4.2 马尔可夫链的状态分类,注(1)如果i有周期d，则对一切非零的n,n0 mod d，有（若，则n=0 mod d）(2)对充分大的n，（引理4.1）例题中当n=1时，当n1时，,4.2 马尔可夫

11、链的状态分类,例4.7 状态空间I=1,2,3,4，转移概率如图，状态2和状态3有相同的周期d=2，但状态2和状态3有显著的区别。当状态2转移到状态3后，再不能返回到状态2，状态3总能返回到状态3。这就要引入常返性概念。,4.2 马尔可夫链的状态分类,由i出发经n步首次到达j的概率(首达概率)规定由i出发经有限步终于到达j的概率,4.2 马尔可夫链的状态分类,若fii=1，称状态i为常返的；若fii1，称状态i为非常返的i为非常返，则以概率1-fii不返回到ii为常返，则 构成一概率分布，期望值 表示由i出发再返回到i的平均返回时间,定义,4.2 马尔可夫链的状态分类,若i，则称常返态i为正常

12、返的;若 i=，则称常返态i为零常返的，非周期的正常返态称为遍历状态。例：判断下面马氏链各状态的类型,定义,设i为常返,4.2 马尔可夫链的状态分类,引理4.2 周期的等价定义G.C.D=G.C.D例4.8 设马尔可夫链的状态空间I=1,2,3，转移概率矩阵为 求从状态1出发经n 步转移首次到达各状态的概率,4.2 马尔可夫链的状态分类,解 状态转移图如下，首达概率为,4.2 马尔可夫链的状态分类,同理可得,4.2 马尔可夫链的状态分类,首达概率 与n步转移概率 有如下关系式定理4.4 对任意状态i,j及1 n，有,4.2 马尔可夫链的状态分类,证,P(A,B|C)=P(B|A,C)P(A|C

13、),例：已知马氏链转移图如下，求从状态1出发再返回1的n步转移概率，n=1,2,8,4.2 马尔可夫链的状态分类,定理4.5 状态i常返的充要条件为如i非常返，则,以下讨论常返性的判别与性质,4.2 马尔可夫链的状态分类,数列的母函数与卷积an,n0为实数列，母函数bn,n0为实数列，母函数则an与bn的卷积的母函数,4.2 马尔可夫链的状态分类,定理4.5 状态i常返的充要条件为如i非常返，则证:规定，则由定理4.4,4.2 马尔可夫链的状态分类,4.2 马尔可夫链的状态分类,对0s1,4.2 马尔可夫链的状态分类,4.2 马尔可夫链的状态分类,定理4.7 设i常返且有周期为d，则其中i为i

14、的平均返回时间，当i=时推论 设i常返，则(1)i零常返(2)i遍历,例：已知马氏链转移图如下，求从状态1出发再返回1的n步转移概率，n=1,2,8,4.2 马尔可夫链的状态分类,证(1)i零常返，i=，由定理4.7知，对d的非整数倍数的n，从而子序列 i是零常返的,4.2 马尔可夫链的状态分类,(2)子序列所以d=1，从而i为非周期的，i是遍历的i是遍历的，d=1，i，,4.2 马尔可夫链的状态分类,例4.10 对无限制随机游动由斯特林近似公式可推出(1)当且仅当p=q=1/2时，4pq=1,4.2 马尔可夫链的状态分类,状态i是常返的状态i是零常返的,4.2 马尔可夫链的状态分类,(2)当

15、且仅当pq，4pq1状态i是非常返的,4.1 马尔可夫链与转移概率,例4.1 无限制随机游动,p,-1 0 1 i-1 i i+1,一步转移概率:,p,p,p,q,q,q,q,状态的可达与互通状态i可达状态j，ij：存在n0,使状态i与状态j互通，ij：ij且ji 定理4.8 可达关系与互通关系都具有传递性，即(1)若ij，jk，则ik(2)若i j，j k，则i k,4.3 状态空间的分解,4.2 马尔可夫链的状态分类,证(1)ij，存在l 0，使 jk，存在m 0，使由C-K方程所以ik(2)由(1)直接推出,4.2 马尔可夫链的状态分类,定理4.9 如ij，则(1)i与j同为常返或非常返

16、，如为常返，则它们同为正常返或零常返(2)i与j有相同的周期,4.2 马尔可夫链的状态分类,例4.9 设马氏链Xn的状态空间为 I=0,1,2,，转移概率为考察状态0的类型,4.2 马尔可夫链的状态分类,可得出0为正常返的由于，所以0的周期为d=10为非周期的，从而为遍历状态对于其它状态i,由于i0,所以也是遍历的,4.3 状态空间的分解,定义 状态空间I 的子集C称为闭集，如对任意iC及kC都有pik=0;闭集C称为不可约的，如C的状态互通；马氏链Xn称为不可约的，如其状态空间不可约引理4.4 C是闭集的充要条件为对iC及kC都有,4.3 状态空间的分解,证 充分性显然成立必要性（数学归纳法

17、）设C为闭集，由定义当n=1时结论成立设n=m时，iC及kC，则注：如pii=1，称状态i为吸收的，等价于 单点集i为闭集。,4.3 状态空间的分解,例4.11 设马氏链Xn的状态空间为 I=1,2,3,4,5，转移概率矩阵为状态3是吸收的，故3是闭集，1,4，1,3,4，1,2,3,4都是闭集，其中3，1,4是不可约的。I含有闭子集，故Xn不是不可约的链。,4.3 状态空间的分解,例4.12 无限制随机游动为不可约马氏链，各状态的周期为2，当p=q=1/2时，是零常返的，当pq时，是非常返的。,4.3 状态空间的分解,定理4.10 任一马氏链的状态空间I，可唯一地分解成有限个或可列个互不相交

18、的子集D,C1,C2,之和，使得：(1)每一Cn是常返态组成的不可约闭集；(2)Cn中的状态同类型，或全是正常返，或全是零常返，它们有相同的周期，且fij=1，i,jCn；(3)D由全体非常返态组成，自Cn中状态不能到达D中的状态。,4.3 状态空间的分解,例4.13 马氏链的状态空间I=1,2,3,4,5,6,状态转移矩阵为分解此链并指出各状态的常返性及周期性。,4.3 状态空间的分解,解 由状态转移图知可见1为正常返状态且周期为3，含1的基本常返闭集为 C1=k:1k=1,3,5，从而状态3及5也为正常返状态且周期为3。同理可知6为正常返状态，6=3/2，周期为1。含6的基本常返闭集为 C

19、2=k:6k=2,6，可见2，6为遍历状态。,4.3 状态空间的分解,于是I可分解为 I=DC1C2=41,3,52,6定义4.10 称矩阵A=(aij)为随机矩阵，若显然k步转移矩阵 为随机矩阵。,4.3 状态空间的分解,引理4.5 设C为闭集，G是C上所得的k步转移子矩阵，则G仍是随机矩阵。证 任取iC，由引理4.4有从而且，故 是随机矩阵。,4.3 状态空间的分解,注：对I的一个闭子集，可考虑C上的原马氏链的子马氏链，其状态空间为C，转移矩阵为G=(pij)，i,jC是原马氏链的转移矩阵为P=(pij)，i,jI的子矩阵。,4.3 状态空间的分解,定理4.11 周期为d的不可约马氏链，其

20、状态空间C可唯一地分解为d个互不相交的子集之和，即 且使得自Gr中任一状态出发，经一步转移必进入Gr+1中(Gd=G0)。注：任取一状态i，对每一r=0,1,d-1定义集,例：已知马氏链转移图如下，求从状态1出发再返回1的n步转移概率，n=1,2,8,4.3 状态空间的分解,例4.14 设不可约马氏链的状态空间为C=1,2,3,4,5,6，转移矩阵为,4.3 状态空间的分解,4.3 状态空间的分解,由状态转移图可知各状态的周期d=3,固定状态i=1，令故C=G0G1G2=1,4,63,52,4.3 状态空间的分解,定理4.12 设Xn,n0是周期为d的不可约马氏链，则在定理4.11的结论下有(

21、1)如只在0,d,2d,上考虑Xn，即得一新马氏链Xnd，其转移矩阵，对此新链，每一Gr是不可约闭集，且Gr中的状态是非周期的；(2)如原马氏链Xn常返，则新马氏链Xnd也常返。,4.3 状态空间的分解,例4.15 设Xn为例4.14中的马氏链，已知d=3，则Xnd,n0的转移矩阵为,4.3 状态空间的分解,由子链 X3n的状态转移图可知 G0=1,4,6，G1=3,5，G2=2各形成不可约闭集，周期为1,4.3 状态空间的分解,4.4 渐近性质与平稳分布,考虑 渐近性质 定理4.13 如j非常返或零常返，则 证 若j非常返，则由定理4.5，从而若j零常返，则由定理4.7推论，,4.4 渐近性

22、质与平稳分布,由定理4.4，对Nn，有固定N，先令n，则,4.4 渐近性质与平稳分布,4.4 渐近性质与平稳分布,推论1 有限状态的马氏链，不可能全是非常返状态，也不可能含有零常返状态，从而不可约的有限状态的马氏链必为正常返的。证 设I=0,1,N，如I全是非常返状态，则对任意i,jI，由定理4.13知 故 矛盾。,4.4 渐近性质与平稳分布,如I含有零常返状态i，则C=j:ij是有限不可约闭集，由定理4.10知，C中均为零常返状态，由定理4.13知，由引理4.5知 所以,4.4 渐近性质与平稳分布,推论2 如马氏链有一个零常返状态，则必有无限多个零常返状态。证 设i为零常返状态，则C=j:i

23、j是不可约闭集，C中均为零常返状态，故C不能是有限集。否则，,4.4 渐近性质与平稳分布,当j是正常返状态时，不一定存在，即使存在也可能与i有关。,例如下面的马氏链中,不存在,4.4 渐近性质与平稳分布,我们考虑,4.4 渐近性质与平稳分布,定理4.14 如j是正常返状态，周期为d，则对任意i及0 r d-1，有 证对d的非正整数倍数的n，(定理4.4，及设v-r=md，则v=md+r),4.4 渐近性质与平稳分布,于是，对1Nn有固定N，先令n，再令N，由定理4.7可得从而,4.4 渐近性质与平稳分布,推论 设不可约、正常返、周期为d的马氏链，其状态空间为C，则对一切i,jC有其中 为定理4

24、.11中所给出当d=1时，则对一切i,j有,例，已知马氏链的转移矩阵,P2=0.5100 0.4900 0.4200 0.5800P3=0.4470 0.5530 0.4740 0.5260,P4=0.4659 0.5341 0.4578 0.5422P8=0.4616 0.5384 0.4615 0.5385,4.4 渐近性质与平稳分布,定理4.15 对任意状态i,j有 推论 如Xn不可约、常返，则对任意 i,j有,4.4 渐近性质与平稳分布,下面考虑平稳分布 设是Xn,n0齐次马尔可夫链，状态空间为I，转移概率为pij 定义 称概率分布j,jI为马尔可夫链的平稳分布，若,例如，设马氏链的状

25、态空间I=1,2，那么平稳分布 应满足,=(1,2),1+2=1,=P,4.1 马尔可夫链与转移概率,初始概率绝对概率初始分布绝对分布初始概率向量绝对概率向量,定义,4.1 马尔可夫链与转移概率,设Xn，nT 为马尔可夫链，则对任意整数jI和n1，绝对概率pj(n)具有性质(1)(2)(3)PT(n)=PT(0)P(n)(4)PT(n)=PT(n-1)P,定理4.2,4.4 渐近性质与平稳分布,注：(1)若初始概率分布pj,jI是平稳分布，则 pj=pj(1)=pj(2)=pj(n)(2)对平稳分布j,jI，有矩阵形式=P(n)其中=(j)，P(n)=(),4.4 渐近性质与平稳分布,定理4.

26、16 不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布，且此平稳分布就是极限分布推论1 有限状态的不可约非周期马尔可夫链必存在平稳分布。(定理4.13推论1)推论2 若不可约马尔可夫链的所有状态是非常返或零常返，则不存在平稳分布。,4.4 渐近性质与平稳分布,推论3 若j,jI是马尔可夫链的平稳分布，则例4.16 设马尔可夫链的转移概率矩阵为 求马尔可夫链的平稳分布及各状态的平均返回时间。,4.4 渐近性质与平稳分布,解 因为马尔可夫链是不可约非周期有限状态的，所以平稳分布存在，设=(1,2,3)，则=P，1+2+3=1即各状态的平均返回时间为,4.4 渐近性质与平稳分布,例4.17 设

27、马尔可夫链具有状态空间I=0,1,2,，转移概率为pi,i+1=pi,pii=ri,pi,i-1=qi(i 0)，其中q0=0,pi,qi 0,pi+ri+qi=1。此马尔可夫链为生灭链，它是不可约的。记a0=1，证此马尔可夫链存在平稳分布的充要条件为,4.4 渐近性质与平稳分布,证 设j,jI是平稳分布,4.4 渐近性质与平稳分布,4.4 渐近性质与平稳分布,例4.18 设马尔可夫链转移概率矩阵为求每一个不可约闭集的平稳分布。,4.4 渐近性质与平稳分布,解 从状态转移图看出，状态空间可分解为两个不可约常返闭集C1=2,3,4和C2=5,6,7，一个非常返集N=1。在常返集上求平稳分布。,4.4 渐近性质与平稳分布,在C1上，对应的转移概率矩阵为C1上的平稳分布为0,0.4,0.2,0.4,0,0,0同理可求得C2上的平稳分布为 0,0,0,0,1/3,1/3,1/3,马尔可夫过程（无后效性）马尔可夫链（状态、时间离散）齐次马尔可夫链（转移概率与时间无关）,I 初始概率、绝对概率,i pi(0)pi(t)t t+T,