第5章 马尔可夫链PPT课件

精选,1,应用随机过程,主讲教师段禅伦2011年秋季学期,计算机学院研究生专业基础课程应用数学基础,(AppliedStochasticprocesses),精选,2,第5章马尔可夫链,5.1引言本章,首先考察取有限个值或者可数个可能值的随机过程Xn,n=0,1,2,.一般将这种随机过程的可能值的集合也记为0,1,2,(即状态空间也是非负整数集).如果Xn=i,那么称随机过程在时刻n在状态i.设只要过程在状态i,就有一个固定的概率pij,使它在下一个时刻在状态j.我们有定义5.1.1若对于一切状态i0,i1,in-1,i,j与一切n0,有PXn+1=j|Xn=i,Xn-1=in-1,X1=i1,X0=i0=PXn+1=j|Xn=i=pij则称这样的随机过程称为马尔可夫链.并称由此式刻画的马尔,精选,3,马尔可夫链,可夫链的特性为Markov性,亦称“无后效性”.此性质说明:要确定过程将来的状态,知道它此刻的状态就足够了,并不需要对它以往状况的认识.也就是说对于一个马尔可夫链,在给定过去的状态X0,X1,Xn-1和现在的状态Xn时,将来的状态Xn+1的条件分布独立于过去的状态而只依赖于现在的状态.pij表示过程处在状态i时,下一次转移到状态j的概率.由于概率值非负且过程必须转移到某个状态,所以有pij0,i,j0(即i,jI);pij=1,i=0,1,2,(即iI)我们称PXn+1=j|Xn=i=pij为Markov链Xn,n=0,1,2,的一步转移概率,简称转移概率.,(),精选,4,马尔可夫链,由Markov链定义知PX0=i0,X1=i1,Xn=in=PXn=in|X0=i0,X1=i1,Xn-1=in-1PX0=i0,X1=i1,Xn-1=in-1=PXn=in|Xn-1=in-1PX0=i0,X1=i1,Xn-1=in-1=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2PX1=i1|X0=i0PX0=i0可见一旦Markov链的初始分布PX0=i0给定,其统计特性就完全由条件概率PXn=in|Xn-1=in-1所决定.,精选,5,马尔可夫链,如何确定这个条件概率,是Markov链理论和应用中的重要问题之一.一般情况下,转移概率pij与状态i,j和时间n有关.当Markov链的转移概率PXn+1=j|Xn=i,只与状态i,j有关,而与n无关时,称Markov链为时齐的;否则,称为非时齐的.我们只讨论时齐Markov链,并简称为Markov链.当Markov链的状态为有限时,称为有限链;否则称为无限链.但无论状态是有限还是无限,我们都可以将pij(i,j0,1,2,)排成一个矩阵的形式.记为:P=(pij),它等于,p00p01p02p03p10p11p12p13pi0pi1pi2pi3,精选,6,马尔可夫链,称P为转移概率矩阵,一般简称为转移矩阵.转移概率矩阵具有性质().称具有此性质的矩阵为随机矩阵(随机矩阵是非负实数矩阵且每一行元素的和为1).例5.1(天气预报)假设明天下雨的机会只依赖于前一天的天气条件,即今天是否下雨,而不依赖过去的天气条件.且如果今天下雨,那么明天下雨的概率为;若今天没下雨,明天下雨的概率为.如果下雨,记过程在状态0;如果不下雨,记过程在状态1.如此,本例是一个两状态0,1的马尔可夫链,其转移概率矩阵是:P=(pij)=,p00p01p10p11,1-1-,精选,7,马尔可夫链,例5.2(一个通讯系统)考察一个传送数字0和1的通信系统.每个数字的传送必须经过几个阶段.在每个阶段有一个概率p使进入的数字在离开时不改变.以Xn记第n个阶段进入的数字,则Xn,n=0,1,2,是一个两个状态0,1的马尔可夫链,具有转移概率矩阵:P=例5.3(随机游动)有一个醉汉在直线上做无限制的随机游动其状态i=0,1,2,.且pi,i+1=p=1-pi,i-1.这也是一个Markov链,其转移矩阵为:,p1-p1-pp,q0p000000q0p000000000q0p,P=,精选,8,马尔可夫链,考虑一个包含两个生命状态S1和S2以及两个死亡状态S3和S4(即相异原因的非生命状态)的模型.若个体病愈,则认为它处于状态S1,若患病,则认为它处于S2,个体可以从S1,S2进入S3和S4,这是一个马尔可夫链的模型,转移概率矩阵为P=例5.5(赌徒的破产或称带吸收壁的随机游动)系统的状态是0到n,反映赌博者A在赌博期间拥有的钱数,当他输光或拥有钱数为n时,赌博停止;否则他将持续赌博,每次以概率p赢得1,以概率q=1-p输掉1.该系统的转移概率矩阵为,p11p12p13p14p21p22p23p2400100001,例5.4(一个简单的疾病死亡模型,Fix-Neyman(1951),精选,9,马尔可夫链,P=例5.6(带反射壁的随机游动)在例5.5中当A输光时将获得赞助1让他继续赌下去,就如同一个在直线上做随机游动的球在到达左侧0点处就立即反弹回1一样,这就是一个一侧带有反射壁的随机游动.此时P=,1000000q0p00000q0p0000000q0p0000001,(n+1)(n+1),0100000q0p00000q0p0000000q0p0000001,(n+1)(n+1),精选,10,马尔可夫链,例5.7在任意给定的一天,一个人的心情或者是快乐的,或者是一般的,或者是郁闷的.如果今天她是快乐的,那么明天她分别以概率0.5,0.4和0.1是快乐的,一般的和郁闷的;如果今天她的心情一般,那么她明天分别以概率0.3,0.4和0.3是快乐的,一般的和郁闷的;如果今天她是郁闷的,那么她明天分别以概率0.2,0.3和0.5是快乐的,一般的和郁闷的.以Xn记她第n天的心情,则Xn,n0是一个三个状态快乐,一般,郁闷=0,1,2的马尔可夫链,其转移概率矩阵0.50.40.10.30.40.30.20.30.5,P=,精选,11,马尔可夫链,例5.8(图上的简单随机游动)设有一蚂蚁在左图的图上爬行,当两个结点相邻时,蚂蚁将爬向它临近一点,并且,爬向任何一个邻近点的概率是相同的,则此Markov链的转移矩阵是下面给出一个如何将一个过程转变为马尔可夫链的例子.,1,3,6,2,4,5,00000000000010000000000010,P=,精选,12,马尔可夫链,例5.9(将一个过程转变为马尔可夫链)假设今天是否下雨依赖于前两天的天气条件.如果过去的两天都下雨,那么明天下雨的概率为0.7;如果今天下雨但昨天没下雨,那么明天下雨的概率为0.5;如果昨天下雨但今天没下雨,那么明天下雨的概率为0.4;如果昨、今两天都没下雨,那么明天下雨的概率为0.2.假设在时间n的状态只依赖于在时间n-1是否下雨,那么上述模型就不是一个马尔可夫链.但是,当假定在任意时间的状态是由这天与前一天两者的天气条件所决定时,上面的模型就可以转变为一个马尔可夫链.换言之,可以假定过程处在:,精选,13,马尔可夫链,状态0,如果昨天和今天都下雨;状态1,如果昨天没有下雨但今天下雨;状态2,如果昨天下雨但今天没有下雨;状态3,如果昨天和今天都没有下雨.这就将题目所给的过程转变成了一个具有4个状态的马尔可夫链,其转移概率矩阵为0.700.300.500.5000.400.600.200.8例5.10考虑订货问题.设某商店使用(s,S)订货策略,每天早上检查某商品的剩余量,设为x,则定购额为0,若xs;S-x,若xs.,P=,精选,14,马尔可夫链,设订货和进货不需要时间,每天的需求量Yn独立同分布且PYn=j=aj,j=0,1,2,.现在我们要从上述问题中寻找一个Markov链.令Xn为第n天结束时的存货量,则Xn-Yn+1,若Xns,S-Yn+1,若Xns.构成的Xn,n1是Markov链.例5.11以Sn表示保险公司在时刻n的盈余,这里的时间以适当的单位来计算(如天,月等),初始盈余S0=x显然为已知,但未来的盈余S1,S2,却必须视为随机变量,增量Sn-Sn-1解释为n-1和n之间获得的盈利(可以为负).假定X1,X2,是不包含利息的盈利且独立同分布于F(x),则,Xn+1=,精选,15,马尔可夫链,Sn=Sn-1(1+i)+Xn,i为固定的利率,Sn,n0是一个Markov链,转移概率为pxy=Fy-(1+i)x.例5.12考察掷硬币的例子.硬币的正反面分别记为U和D,于是状态空间为U,D=1,2,式中1,2分别代表U,D.假定硬币初始时为正面,我们一共投掷了50次.在每一次投掷时,硬币以概率20%翻转.于是转移概率为:p11=0.8,p12=0.2,p21=0.2,p22=0.8.状态转移矩阵P=.进而算得P2=,P4=.于是PX4=U=PX0=UX4=U=0.5648.,0.80.20.20.8,0.680.320.320.68,0.56480.43520.43520.5648,精选,16,马尔可夫链,例5.13(隐Markov链模型)这里用简单例子引出隐Markov链模型.假定有分别记为M和W的两枚硬币.在任何给定的时刻两枚硬币或者为正面或者为反面.在任何给定时刻只有一枚硬币呈现,但是有时硬币可能被替换(M换成W或W换成M)但不改变其正反面.硬币M具有与例5.12相同的转移概率,硬币W具有转移概率.在任何给定时刻硬币被替换的概率为30%,替换完成时,硬币的状态不变.这一Markov链有4个状态,分别记为1:UM;2:DM;3:UW;4:DW.状态1,3表示正面U,状态2,4表示反面D.转移矩阵为44的矩阵.,0.90.10.050.95,精选,17,马尔可夫链,我们可以计算转移概率,比如UMUM,首先有UU(无转移),而后MM(无转移).于是转移概率为PUU|MPMM=0.80.7=0.56.其它转移概率类似可得.转移方式是UMUMUMDMUMUWUMDWDMUMDMDMDMUWDMDWUWUMUWDMUWUWUWDWDWUMDWDMDWUWDWDW转移概率矩阵为0.80.70.20.70.80.30.20.30.20.70.80.70.20.30.80.30.90.30.10.30.90.70.10.70.050.30.950.30.050.70.950.7若从状态UM出发,要求在第4个时间周期后,硬币处于状态D的概率,则由于2=DM和4=DW都是状态D,所求概率为+.,P=,.,精选,18,马尔可夫链,例5.14确定汽车年保险金的系统称好-坏系统.在该系统中,每个参保人被赋予一个正整数值的状态.年保险金是这个状态(保险车类型以及保险水平)的函数.参保人的状态随着参保人要求理赔的次数而一年一年地变化.低的状态对应于低的年保险金.如果参保人在上一年没有理赔要求,他的状态就将降低;如果参保人在上一年至少有一次理赔要求,他的状态一般会增加(可见,无理赔是好的,并且会导致低保险金;而要求理赔是坏的,一般会导致更高的保险金).对于给定的一个好-坏系统,以si(k)记一个在上一年处在状态i,且在该年有k次理赔要求的参保人在下一年的状态.,精选,19,马尔可夫链,一般,一个特定的参保人年理赔要求的次数是参数为的泊松随机变量,那么此参保人相继的状态将构成一个马尔可夫链,并具有转移概率pij=,j0通常有多个状态.以下表格给出了一个假定有4个状态的好-坏系统:下一个状态状态年保险金0个理赔1个理赔2个理赔3个理赔以上12001234225013443400234446003444,精选,20,马尔可夫链,此表说明了:s2(0)=1;s2(1)=3;s2(k)=4,k2.考察,年理赔次数是参数为的泊松随机变量的某个参保人.如果这个参保人一年中有k次理赔要求的概率是k,那么k=,k0对于表中表示的好-坏系统,参保人相继的状态的转移概率矩阵为0121-0-1-20011-0-10011-0-10001-0,P=,精选,21,马尔可夫链,5.2C-K(Chapman-Kolmogorov)方程上节讨论了一步转移概率pij,本节首先来定义n步转移概率,它是状态处于i的过程,在n次转移后处于状态j的概率,即称条件概率=PXn+k=j|Xk=i,i,jS,n0,i,j0为Markov链的n步转移概率,相应地称P(n)=()为n步转移矩阵.当n=1时,=pij,P(1)=P,此外规定=.n步转移概率指的就是系统从状态i经过n步后转移到j的概率,它对中间的n-1步转移经过的状态无限制.,0,ij1,i=j,精选,22,马尔可夫链,下面的定理给出了在归纳意义下和pij的关系,它为我们提供了计算n步转移概率的一个方法.定理5.2.1(Chapman-Kolmogorov方程,简称C-K方程)对一切n,m0和一切状态i,j有(1)=;,o,t,m,n,m,m+n,i,j,k,精选,23,马尔可夫链,(2)P(n)=PP(n-1)=PPP(n-2)=Pn.证明:=PXm+n=j|X0=i=(全概率公式)=PXm+n=j|Xm=k,X0=iPXm=k|X0=i=.,精选,24,马尔可夫链,(2)是(1)的矩阵形式,利用矩阵乘法即可获得.例5.15在例5.5中,取n=3,p=q=1/2.赌徒A从2元赌金开始赌博.求解他经过4次赌博之后输光的概率.解:这个概率为=PX4=0|X0=2,转移矩阵利用矩阵乘法得所以=5/16(即P(4)中第3行第1列元素).,100000000001,P=,10005/81/1605/165/1601/165/80001,P(4)=P4=.,精选,25,马尔可夫链,例5.16(广告效益的推算)某种鲜奶A改变了广告方式.经调查发现,买A种鲜奶及另外三种鲜奶B,C,D的顾客每两个月的平均转换率为(设市场中只有这四种鲜奶):AA(95%)B(2%)C(2%)D(1%);BA(30%)B(60%)C(6%)D(4%);CA(20%)B(10%)C(70%)D(0%);DA(20%)B(20%)C(10%)D(50%).假设目前购买A,B,C,D等四种鲜奶的顾客的分布是(25%,30%,35%,10%).试求半年后鲜奶A,B,C,D的市场份额.解:令P为转移矩阵,则,0.950.020.020.010.300.600.060.040.200.100.700.000.200.200.100.50,P=.,精选,26,马尔可夫链,令=(1,2,3,4)=(0.25,0.30,0.35,0.10).经过半年,顾客在这四种鲜奶上的转移概率是:P(3)=P3.经计算得因为我们所关心的是鲜奶半年后的市场占有率,故只须求出P3的前三列.它们依次是A,B,C,D四种鲜奶经3次转移后转到A,B,C的概率.于是知A的市场占有率变为vA=(0.25,0.30,0.35,0.10)0.622;B的市场占有率变为,0.88940.04580.04660.01820.60170.25590.09880.04360.48340.13880.36580.01200.50090.21340.14260.1431,P3=.,0.88940.60170.48340.5009,精选,27,马尔可夫链,vB=(0.25,0.30,0.35,0.10)0.158;C的市场占有率变为vC=(0.25,0.30,0.35,0.10)0.184;从而知D的市场占有率为vD=1-0.622-0.158-0.1840.036.A种鲜奶的市场份额由原来的25%增至62.2%,B种鲜奶的市场份额由原来的30%减到15.8%,C种鲜奶的市场份额由原来的35%减至18.4%,D种鲜奶的市场份额由原来的10%减为3.6%.综上所述,可知关于A种鲜奶的新广告方式很有效益.,0.04580.25590.13880.2134,0.04660.09880.36580.1426,精选,28,马尔可夫链,例5.17在例5.1中,如果=0.7,=0.4,那么若今天下雨,则往后4天都下雨的概率是多少?解:在=0.7,=0.4时,例5.1的一步转移概率矩阵P=进而知P(2)=P2=P(4)=P4=往后4天都下雨的概率是P(4)中的,即0.5749.例5.18在例5.9中,已知星期一与星期二下雨,问星期四下雨的概率是多少?解:做计算,0.70.30.40.6,0.610.390.520.48,0.57490.42510.56680.4332,精选,29,马尔可夫链,P(2)=P2=由于星期四下雨,等价于星期四处在状态0或状态1的过程,所以要求的概率由=0.49+0.12确定,即0.61.被定义为,给定在时间k时的状态i时,在时间k+n时过程处于状态j的概率,这个概率是条件概率.前面,我们曾指出,一旦Markov链的初始状态PX0=i0给定,其统计特性就完全由条件概率PXn=in|Xn-1=in-1所决定.该表述的含义是,0.490.120.210.180.350.200.150.300.200.120.200.480.100.160.100.64,精选,30,马尔可夫链,首先,当给定在时间0时的状态i时,在时间n时过程处于状态j的概率,仍为条件概率;如果要求在时间n的状态的无条件分布,可以经过对初始状态取条件算得,即PXn=j=PXn=j|X0=iPX0=i=i式中,i=PX0=i,i0,i=1.例如在例5.17中,如果0=0.4,1=0.6,那么在保留今天天气记录下,往后四天在下雨的无条件概率PX4=0=0.4+0.6=0.40.5749+0.60.5668=0.5700.,精选,31,马尔可夫链,考虑马尔可夫链到时间n为止进入任意一个特定的状态集合A的概率.取得它的一个途径是重置离开A中状态的转移概率为PXm+1=j|Xm=i=即A中所有的状态转变为吸收态,一旦进入此状态就不能离开.因为,原来的和转变后的马尔可夫链直到进入A中的一个状态前遵从相同的概率,由此可以推知原来的马尔可夫链到时间n为止进入A中的一个状态的概率等于转变后的马尔可夫链在时间n处在A中的一个状态的概率.例5.19一个领养老金的人在每月初领收2(千元).她每月需要花费的金额独立于她拥有的金额,并以概率pi等于,1,若iA,j=i0,若iA,ji,精选,32,马尔可夫链,i,i=1,2,3,4,pi=1.如果她在月末金额多于3,她便将超过3的金额送给她的儿子.如果在月初领收养老金后她有金额5,问在随后的四个月中的任意时间,她拥有的资金等于或者少于1的概率是多少?解:为了求得“她拥有的资金等于或者少于1的概率”,我们考察一个马尔可夫链,其状态是该养老人在月末拥有的金额.由于所关心的是这一金额是否1,我们就以1表示“她的月末金额最终1”(A=1).因为,这个养老人在月末将任何超过3的部分送给了她的儿子,所以只需考虑状态为1,2,3的马尔可夫链.转移,精选,33,马尔可夫链,概率矩阵P=(pij)=为了理解这一转移概率矩阵,考虑p21.它是给定养老人在月末拥有金额2时,她在下一个月月末拥有的金额小于或等于1的概率.因为她一个新月份的月初金额是2+2=4,只有她花费3或4,在月末她拥有的金额才小于或等于1.因此,p21=p3+p4.假定pi=1/4,i=1,2,3,4.于是,转移概率矩阵P=,100p3+p4p2p1p4p3p1+p2,1001/21/41/41/41/41/2,精选,34,马尔可夫链,P(4)=P4=因为,养老人初始月末的资金是3,所以要求的概率是=201/256.设Xn,n0是转移概率为pij的马尔可夫链,如果以qij记转变A中的一切状态为吸收态的转移概率,则qij=对于i,jA,n阶段转移概率代表开始处于状态i的原来的链,并没有进入A中的任一状态,且在时间n处于状态j的概率.,100222/25613/25621/256201/25621/25634/256,1,若iA,j=i0,若iA,jiPij,其它,精选,35,马尔可夫链,例如在例5.19中,在一月初开始是5,养老人的金额从未小于或等于1,且在5月初的资金是4的概率是=21/256.假定链在开始时处在状态i,到时间n为止从未进入过A中的任一状态时,Xn的条件概率可以这样计算:对于i,jA,PXn=j|X0=i,XkA,k=1,2,nPXn=j,XkA,k=1,2,n|X0=iPXkA,k=1,2,n|X0=i=.,=,精选,36,马尔可夫链,5.3状态的分类本节,我们首先讨论Markov链各个状态之间的关系,并以这些关系将状态分类,然后研究它们的一些性质.状态j称为是从状态i可达的(或状态i可达状态j),对i,j0,1,2,若存在n0,使有0记为ij.若同时有状态ji,则称i与j互通,记为ij.以0定义j从状态i可达是合理的,因为如果状态j不是从状态i可达的,那么P最终进入状态j|开始在状态i=PXn=j|X0=iPXn=j|X0=i=0.,精选,37,马尔可夫链,例5.20考虑转移概率矩阵如右的由0,1,1/21/202三个状态组成的马尔可夫链.01且P=1/21/41/412其转移概率分别为1/2和1/4.01/32/3显然,任意状态都与它自己是互通的,因为=PX0=i|X0=i=1.互通作为状态之间的关系,它是状态空间上的一种等价关系.定理5.3.1互通是状态空间上的等价关系,即互通具有以下三个性质:(1)自返性状态i0,ii;(2)对称性若状态ij,则状态ji;(3)传递性若状态ij且状态jk,则状态ik.,精选,38,马尔可夫链,证明:(1)、(2)互通性的成立是显然的.只证(3).由互通定义知,需证ik且ki.首先,由ij,jk知道,存在m,n使得0,0.再由C-K方程得=0,故ik;反过来同样有ki.所以ik.我们把任何两个互通状态归为一类,由定理5.3.1,同在一类的状态都是互通的,并且任何一个状态不能同时属于两个不同的类.定义5.3.1若Markov链只存在一个类(所有的状态彼此互通)则称它是不可约的.否则称它为可约的.例5.20中的3个状态0,1,2之间是互通的(210的转移概率分别是1/3和1/2),因而这个Markov链是不可约的.,精选,39,马尔可夫链,下面我们首先给出状态的一些性质,然后证明同在一类的状态具有相同的性质.定义5.3.2(周期性)若集合n:n1,0非空,则称它的最大公约数d=d(i)为状态i的周期.若d1,称i是周期的;若d=1,称i是非周期的.并特别规定集合n:n1,0为空集时,称i的周期无穷大.说明:由定义5.3.2知,虽然i有周期d但并不是对所有的n,都大于0.例如,如果集合n:n1,0为3,9,18,21,其公约数d=3,即3是i的周期,显然,n=6,12,15都不属于该集合即=0,=0,=0.但是可以证明,当n充分大之后,必定有0.,精选,40,马尔可夫链,命题设状态i的周期为d,则存在正整数M,对一切nM,有0.证明:令n:n1,0=n1,n2,记tk=G.C.Dn1,n2,nk,则t1t2d1.因此,存在正整数N,使有tN=tN+1=d.可见d=G.C.Dn1,n2,nN.于是,存在正整数M,对一切M之n,成立nd=d(nk=d,k=1,2,N),并有,精选,41,马尔可夫链,例5.21考察右图所示的Markov链.由状态1出发再回到状态1的可能步长为T=4,6,8,10,它的最大公约数为2,显然从状态1出发2步并不能回到状态1(2却是状态1的周期).但是,对2的n=2,3,4,5,倍,都有0,换言之,都能够从状态1出发,经2n步回到1.定理5.3.2若状态i,j同属一类,则d(i)=d(j).证明:由类的定义知ij,即存在m,n使0,0.则=0.对所有使得0的s,有0.显然d(i)应同时整除n+m和n,1,2,3,4,5,6,8,9,7,1,1,1,1,1,1,1,1,1/3,2/3,精选,42,马尔可夫链,+m+s,则它必定整除s.而d(j)是j的周期,所以也有d(i)整除d(j)(这是因为d(i)能整除所有的s,所以d(i)就能整除这些s的最大公因d(j).反过来同样可证d(j)可整除d(i).于是,就有d(i)=d(j).考虑状态空间S=1,2,3,4其概率转移矩阵的转移图如右上所示的马尔可夫链.状态2与状态3有相同的周期2.不过,从状态3出发,经两步必定返回.而状态2则不然.当2转移到3后,它再也不能返回到2.为区分这样的两种状态,我们引入常返性的概念.,1,2,3,4,1,1,1,1/2,1/2,精选,43,马尔可夫链,记=PTij=n|X0=i(Tij=min(n|X0=i,Xn=j)首进时间)=PXn=j,Xkj,k=1,2,n-1|X0=i,n1;=0.式中的i,j是状态空间中的任意两个状态(注意与定义不同).它表示过程由状态i出发,经n步首次到达状态j的概率,这个概率也称首中概率.记fij=(当i=j时,简记fii为fi)它表示过程由状态i出发,经有限步最终到达状态j的概率.显然,表示过程从状态i出发,经n(n=1,2,)步返回i的概率.如果,n1构成一概率分布,则该分布的期望值i=n表示从状态i出发再返回到i的平均时间.,精选,44,马尔可夫链,例5.21考虑由0,1,2,3四个状态组成的Markov链.其转移概率矩阵为1/21/2001/21/2001/41/41/41/40001在该Markov链中01.尽管0与1都是从2可达的,但是2既不能从0可达,也不能从1可达,所以2与0、2与1是不互通的.状态3是一个吸收态(即p33=1),没有从它可达的状态.此链被互通关系分为三个类:0,1,2,3.例5.22我们来看例5.4中疾病死亡模型的4个状态之间的关系.为清楚起见,经常以转移图来表示Markov链的状,P=,0,1,2,3,1/2,1/2,1/2,1/2,1/4,1/4,1/4,1/4,1,精选,45,马尔可夫链,态变化.由转移矩阵可得转移图:容易看出S1S1,S2S1,S1S2,S2S2,S1S3,S2S3,S1S4,S2S4.所以只有S1S2,但S3S1,S4S1,S3S2,S4S2,S3S4,S4S3.状态可分为三类:S1,S2,S3和S4.以类似的方法可以说明,例5.5中赌徒输光问题中满足0i,jn的任何两个状态i,j都互通,而且该链的所有状态可分为三类:0,1,2,n-1,n.对于任一状态i,我们知fi记开始在状态i的过程最终再进入i的概率.状态i称为常返态,如果fi=1;状态i称为暂态,如果fi1.,S1,S2,S3,S4,p11,p22,P33=1,P44=1,p14,p12,p21,p24,p13,p23,精选,46,马尔可夫链,假设过程开始在状态i,且i是常返态.那么,过程将以概率1再进入i.但是,由马尔可夫链的定义,当它在进入i时,该过程将又重复.从而状态i最终将再度被访问.继续重复以上推理,我们产生以下结论:如果状态i是常返态,那么开始在状态i的过程将一再地进入i(进入的次数事实上无穷).另一方面,假设状态i是暂态.此时,过程每次进入i将有一个正的概率1-fi不再进入这个状态.所以,开始(0时刻)在状态i的过程恰好在状态i停留n个时间周期的概率等于(1-fi),n1.换句话说:如果状态i是暂态,那么,开始在状态i的过程处于状态i,精选,47,马尔可夫链,的时间周期个数有一个有限均值为1/(1-fi)的几何分布.定义5.3.3对于常返态i,若i+,则称i为正常返态;若i=+,则称i为零常返态.特别地,若i正常返且是非周期的,则称之为遍历状态.若i是遍历状态且=1,则称i为吸收状态,此时,显然i=1.可以证明,对于同属一类的状态i,j,它们同为常返态或暂态;且当它们是常返态时,又同为正常返态和零常返态.以下是对上述概念和性质的总结:齐次马氏链的状态分类1.称d=d(i)=GCDn:n1,pii(n)0为状态i的周期.(1)d1,称状态i为周期的;(2)d=1,称状态i为非周期的.,精选,48,马尔可夫链,事实.(1)若i有周期d,则对一切非零的n0(modd)都有pii(n)=0,但并非对任意nd,有pii(nd)0;(2)若i的周期为d,则存在正整数M,对一切nM,有pii(nd)0.首达概率对n1fij(n)=PXn=j,Xkj,k=1,2,n-1|X0=i;fij(0)=0.及过程由i出发,经有限步最终到达j的概率.fij=fij(n),如i=j时,则简记fii为fi.当fi=1时,称状态i是常返态;当fi1时,称状态i是暂态(滑过的状态).事实.(1)若i是暂态,则由i出发将以正概率1-fi永远不再返回到i;对常返态此现象不会发生;,精选,49,马尔可夫链,(2)对常返态i,fii(n),n1构成一概率分布,该分布的期望值i=nfii(n),表示过程由i出发再返回到i的平均返回时间.2.设状态i为常返态,若i,则称常返态i是正常返的;若i=,则称常返态i是零常返的;非周期的正常返态称为遍历状态.重要事实.对任意i,jS,n1有pij(n)=fij(k)pjj(n-k).证明:=PXn=j|X0=i=PXn=j,Xvj,v=1,2,k-1|X0=i=PXn=j|Xk=j,Xvj,v=1,2,k-1,X0=iPXk=j,Xvj,v=1,2,k-1|X0=i=pjj(n-k)fij(k)=fij(k)pjj(n-k).,精选,50,马尔可夫链,从对事实的证明,我们还可看出所述事实的对称形式:pij(n)=fij(n-k)pjj(k).C-K方程以及以上事实,是马尔可夫链的关键性公式,它们可以把pii(n)分解成较低步的转移概率之和的形式.而且,通过这个事实,我们可以得到关于周期的等价定义:GCDn:n1,pii(n)0=GCDn:n1,fii(n)0.马尔可夫链的状态有以下分类:暂态状态零常返态常返态是周期的正常返态是非周期的-遍历态,精选,51,马尔可夫链,例5.23设马尔可夫链的状态空间S=1,2,3,4,其一步转移概率矩阵:状态转移图:P=试对其状态分类,进而确定哪些状态是常返态,并确定其周期.解:因为对一切n1,f44(n)=0,所以f4=f44(n)=01,可见状态4是一个暂态.又f33(1)=2/3,且对n2,f33(n)=0,所以f3=2/31,从而知,状态3也是暂态.而f1=f11(1)+f11(2)=1/2+1/2=1(n步首中概率求和),及,1/21/200100001/32/301/201/20,1,2,3,4,1/2,1/2,1/2,1/2,1/3,2/3,1,精选,52,马尔可夫链,f2=f22(1)+f22(2)+=0+1/2+1/22+=1,所以状态1和状态2是常返态.显然,状态1与状态2的周期为1.再由1=nf11(n)=1(1/2)+2(1/2)=3/2,2=nf22(n)=10+2(1/2)+3(1/22)+=3知,状态1与状态2是正常返态,且为遍历态.为何成立10+2(1/2)+3(1/22)+=3?因为当记f(n)=21/2+31/22+41/23+51/24+61/25+n1/2n-1以及g(n)=1/2+1/22+1/23+1/24+1/25+1/2n-1时,f(n)-g(n)=1/2+(1/2)f(n)-n/2n.而此式即f(n)=1+2g(n)-n/2n-1.于是有,当n时,n/2n-10,g(n)=1,f(n)=3.,精选,53,马尔可夫链,例5.24已知马尔可夫链Xn,n0的状态空间S=1,2,3,4,其转移概率矩阵P的状态转移图为:试对该马尔可夫链的状态进行分类.解:显然,S中的状态是互通的.因为p11=1/4,所以n:p11(n)0的最大公约数d=1,可见状态1是非周期的.于是,状态2,3,4也是非周期的.考虑状态1是否是常返态.因为f11(1)=1/4,而f11(2)=PX2=1,X11|X0=1=PX2=1,X1=2|X0=1+PX2=1,X1=3|X0=1+PX2=1,X1=4|X0=1=PX2=1|X1=4,X0=1PX1=4|X0=1=p41p14=1/4.,1,1,2,1/4,1/4,1/4,1/4,1,1,3,4,精选,54,马尔可夫链,类似地(其实,从图上观测即可),得f11(3)=1/4,f11(4)=1/4;n5,f11(n)=0.所以f1=f11=f11(n)=1/4+1/4+1/4+1/4=1,可见状态1是常返态.又1=nf11(n)=11/4+21/4+31/4+41/4=5/2,可见状态1是正常返态.状态1的d=1,是非周期的,因而1是遍历的.再由各状态互通,即知状态1,2,3,4都是正常返中的遍历态.而且还知,该马尔可夫链是不可约的.*例5.25(生灭链)考察生物群体.以Xn,n0记马尔可夫链(表示在时间n时生物个体的数目),其状态空间S=0,1,2,.设pi,i+1=i,pi,i-1=i(0=0),pii=i=1-,精选,55,马尔可夫链,-i-i,i0.令X0=1,i0,i0,证明当=时,Xn的所有状态都是常返的.证明:显然,所有状态都是互通的,因此只需考察状态0.记对固定的状态k,ui=PTi0Tik|X0=i,并有ui=iui+1+iui-1+(1-i-i)ui或ui+1-ui=i(ui-ui-1)/i=(u1-u0).令0=1,i=,(u0=1,uk=0),并对上式两边就i=0,1,k-1求和,得,精选,56,马尔可夫链,1=(1-u1)i.从而得出u1=PT10T1k|X0=1=1-(j)-1.由于T10T1k关于k单调增加并趋向于T10及条件j=,当令k时,则由上式得PT10|X0=1=f10=1,所以,由f00=p00+p01f10=0+0=1-0-0+0=1(0=0)知状态0是常返态.如果ii0,则所证等式成立,且所有状态都是常返态.一般,称这一过程为生灭链.,精选,57,马尔可夫链,为什么要对马尔可夫链的状态进行分类?对齐次马氏链代表的系统进行研究时要讨论两个问题:(1)在某一固定时刻n时的概率特性即求n步转移概率或绝对概率pj(n)=PXn=j(称瞬态分析);(2)当n后系统的概率特性,即n时,pij(n)的极限是否存在,若存在又与状态的关系如何,极限概率能否构成概率分布(称稳态分析).解决此类问题需要对状态(状态空间)进行分类(分解).下面,我们首先给出常返性的另一个判定方法.定理5.3.3状态i为常返态当且仅当=;状态i为暂态时=,因而有lim=0.,n,精选,58,马尔可夫链,证明:由前述事实,有=+()=1+=1+()()所以,=,收敛,lim=0.从而收敛fii1;=fii=1.引理5.3.4若ij且i为常返态,则fji=1.证明:假如fji1,则以正概率1-fji0使得从j出发不能在有限步内回到i.这意味着系统中存在着一个正概率,使得它从i出发不能在有限步内回到i,可见fii1与假,n,精选,59,马尔可夫链,设i是常返态矛盾.所以只能有fji=1.定理5.3.5常返性是一个类性质.证明:首先来证明若ij,则i,j同为常返态或暂态.由ij知,存在n,m,使得0,0,由C-K方程,总有,求和,得可见,相互控制,同为无穷或有限,从而i,j同为常返态或暂态.,精选,60,马尔可夫链,其实还可以证明,当i,j同为常返态时,它们同为正常返态或零常返态.闭集概念:状态空间S的子集C称为闭集,如果对于任意iC和kC都有pik=0.如果C的状态还是互通的,则称闭集C是不可约的.已知,Markov链Xn,n0不可约当且仅当它的状态空间S不可约.在S中按照互通关系,可形成如下的状态空间分解定理.定理5.3.6任意Markov链的状态空间S,可惟一分解为有限个或可列个互不相交的子集D,C1,C2,之和,使得(1)每个Cn是常返态组成的不可约闭集(称基本常返闭集);(2)Cn中的状态同类,或者全是正常返态,或者全是零常返态.它们有相同的周期,而且对i,jCn,fij=1.,精选,61,马尔可夫链,(3)D由全体暂态组成.自Cn中状态出发不能到达D中的状态.证明:记C为全体常返态组成的集合,则D=S-C为暂态全体.将C按互通关系进行分解,则得S=DC1C2,其中每一个Cn是由常返态组成的不可约闭集,即基本常返闭集.由定理5.3.5知,Cn中的状态同类型,即或者全是正常返态,或者全是零常返态且它们有相同的周期.再由定理5.3.4知有对i,jCn,fij=1.显然,Cn中的状态不能到达D中的状态.因为,一旦进入D,就不再返回Cn,这与Cn的不可约闭集性矛盾.,精选,62,马尔可夫链,对于不可约的Markov链,我们有如下的分解定理.定理5.3.7周期为d的不可约Markov链,其状态空间S可惟一分解为d个互不相交的子集之和,即S=Sr,SrSs=,rs,且使得自Sr中任意状态出发,经1步转移必进入Sr+1中(这里,Sd=S0).证明:首先,任意取状态i,对每一个r=0,1,d-1,定义集合Sr=j:对某个n0,0.()因为S不可约,所以Sr=S.其次如果存在jSrSs,由()式知,存在n,m使得0,0.又因为ij,故存在h,使得0,于是0,精选,63,马尔可夫链,0.由此可见r+h和s+h都能被d整除,从而其差r+h-(s+h)=r-s也能被d整除.但是0r,sd-1,故只能r-s=0,于是得到Sr=Ss.这说明,当rs时,SrSs=.再者证明对任意jSr有pjk=1.事实上若0,则当kSr+1时,0=pjk0,从而pjk=0,于是有1=pjk=pjk+pjk=pjk.最后证明分解的惟一性.这只需证明Sr与最初状态i的选择无关,亦即如果对某个固定的i,状态j与k属于某个Sr,则对另外选定的i,状态j与k仍属于同一个,精选,64,马尔可夫链,(r与r可以不同).实际上,设对某个i得到分解S0,S1,Sd-1,对i得到分解,又假设j,kSr,iSs,则当rs时,从i出发,只能在r-s,r-s+d,r-s+2d,步上到达j或k,故j与k都属于.而当rs时,从i出发,只能在d-(s-r)=r-s+d,r-s+2d,步上到达j或k,故j与k都属于.*例5.26设Markov链的状态S=0,1,2,转移概率是:p00=1/2,pi,i+1=1/2,pi0=1/2,iS.该链转移概率矩阵P的转移图为,0,1,2,i,i+1,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,精选,65,马尔可夫链,由状态图易知:=1/2,=(1/2)(1/2)=1/4,=1/2n.故f00=1/2n=1,0=n(1/2n)=3.可见状态0是正常返态,显然它是非周期的,所以0是遍历状态.对其它状态i0,由i0知,i也是遍历状态.*例5.27考虑直线上无限制随机游动.状态空间S=0,1,2,转移概率为pi,i+1=1-pi,i-1=p,iS.对于状态0,可知=0,n=1,2,即从0出发奇数次不可能返回到0.而=pn(1-p)n=p(1-p)n,精选,66,马尔可夫链,即经过偶数次回到0当且仅当它向左、向右移动的距离相同.由Stirling公式知,当n充分大时,n!e-n.于是.而p(1-p),且p(1-p)=p=.于是,当p=时,=;否则,.即当p时,状态0是瞬时状态,即暂态;p=时,是常返状态.显然,过程的各个状态都是相通的,故以此可知其它状态也是常返状态.,精选,67,马尔可夫链,闭集的涵义是:自C的内部不能到达C的外部.这意味着:一旦质点进入闭集C中,它将永远留在C