第5章 马尔可夫链

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,应用随机过程,主讲教师 段禅伦,2011,年秋季学期,计算机学院研究生专业基础课程,应用数学基础,(Applied Stochastic processes),第,5,章 马尔可夫链,5.1,引言,本章,首先考察取有限个值或者可数个可能值的随机过,程,X,n,n=0,1,2,.,一般将这种随机过程的可能值的集合,也记为,0,1,2,(,即,状态空间,也是非负整数集,).,如果,X,n,=i,那么称随机过程在时刻,n,在状态,i.,设只要过程在状态,i,就有一个固定的概率,p,ij,使它在,下一个时刻在状态,j.,我们有,定义,5.1.1,若对于一切状态,i,0,i,1,i,n-1,i,j,与一切,n0,有,PX,n+1,=j|X,n,=i,X,n-1,=i,n-1,X,1,=i,1,X,0,=i,0,=PX,n+1,=j|X,n,=i,=p,ij,则称,这样的随机过程称为,马尔可夫链,.,并称由此式刻画的马尔,马尔可夫链,可夫链的特性为,Markov,性,亦称,“,无后效性,”,.,此性质说明,:,要确定过程将来的状态,知道它此刻的状态就足够了,并不需要对它以往状况的认识,.,也就是说,对于一个马尔可夫链,在给定,过去的状态,X,0,X,1,X,n-1,和,现在的状态,X,n,时,将来的状态,X,n+1,的,条件分布,独立于过,去的状态而,只依赖于现在的状态,.,p,ij,表示过程处在状态,i,时,下一次转移到状态,j,的概率,.,由于概率值非负且过程必须转移到某个状态,所以有,p,ij,0, i,j0(,即,i,jI);,p,ij,=1, i=0,1,2,(,即,iI),我们称,PX,n+1,=j|X,n,=i=p,ij,为,Markov,链,X,n,n=0,1,2,的,一步转移概率,简称,转移概率,.,(),马尔可夫链,由,Markov,链定义,知,PX,0,=i,0,X,1,=i,1,X,n,=i,n,=PX,n,=i,n,|X,0,=i,0,X,1,=i,1,X,n-1,=i,n-1,PX,0,=i,0,X,1,=i,1,X,n-1,=i,n-1,=PX,n,=i,n,|X,n-1,=i,n-1,PX,0,=i,0,X,1,=i,1,X,n-1,=i,n-1,=,=PX,n,=i,n,|X,n-1,=i,n-1,PX,n-1,=i,n-1,|X,n-2,=i,n-2,PX,1,=i,1,|,X,0,=i,0,PX,0,=i,0,可见一旦,Markov,链,的,初始分布,PX,0,=i,0,给定,其统计特性,就完全由条件概率,PX,n,=i,n,|X,n-1,=i,n-1,所决定,.,马尔可夫链,如何确定这个条件概率,是,Markov,链理论和应用中的重,要问题之一,.,一般,情况下,转移概率,p,ij,与状态,i,j,和时间,n,有关,.,当,Markov,链的转移概率,PX,n+1,=j|X,n,=i,只与状态,i,j,有,关,而与,n,无关时,称,Markov,链,为时齐的,;,否则,称为,非时齐,的,.,我们只讨论,时齐,Markov,链,并简称为,Markov,链,.,当,Markov,链的状态为有限时,称为,有限链,;,否则称为,无,限链,.,但无论状态是有限还是,无限,我们都可以将,p,ij,(,i,j,0,1,2,),排成一个矩阵的,形式,.,记为,: P=(p,ij,),它等于,p,00,p,01,p,02,p,03,p,10,p,11,p,12,p,13,p,i0,p,i1,p,i2,p,i3,马尔可夫链,称,P,为,转移概率矩阵,一般简称为,转移矩阵,.,转移概率矩阵具有性质,(),.,称具有此性质的矩阵为,随,机矩阵,(,随机矩阵是非负实数矩阵且每一行元素的和为,1).,例,5.1,(,天气预报,),假设明天下雨的机会只依赖于前一天的天气条件,即今,天是否下雨,而不依赖过去的天气条件,.,且如果今天下雨,那么明天下雨的概率为,;,若今天没下雨,明天下雨的概,率为,.,如果下雨,记过程在状态,0;,如果不下雨,记过程在状态,1.,如此,本例是一个两状态,0,1,的马尔可夫链,其转移概率,矩阵是,:,P=(p,ij,)= =,p,00,p,01,p,10,p,11, 1-, 1-,马尔可夫链,例,5.2,(,一个通讯系统,),考察一个传送数字,0,和,1,的通信系统,.,每个数字的传送必,须经过几个阶段,.,在每个阶段有一个概率,p,使进入的数字,在离开时不改变,.,以,X,n,记第,n,个阶段进入的数字,则,X,n,n=,0,1,2,是一个两个状态,0,1,的马尔可夫链,具有转移,概率矩阵,: P=,例,5.3,(,随机游动,),有一个醉汉在直线上做,无限制的随机游动其状态,i=0,1,2,.,且,p,i,i+1,=p=1-p,i,i-1,.,这也是一个,Markov,链,其转移矩阵为,:,p 1-p,1-p p,q 0 p 0,0 0 0 0,0 q 0 p,0 0 0 0,0 0 0 0,0 q 0 p,P=,马尔可夫链,考虑一个包含两个生命状态,S,1,和,S,2,以及两个死亡状态,S,3,和,S,4,(,即相异原因的非生命状态,),的模型,.,若个体病愈,则,认为它处于状态,S,1,若患病,则认为它处于,S,2,个体可以从,S,1,S,2,进入,S,3,和,S,4,这是一个马尔可夫链的模型,转移概率,矩阵为,P=,例,5.5,(,赌徒的破产或称带吸收壁的随机游动,),系统的状态,是,0,到,n,反映赌博者,A,在赌博期间拥有的钱数,当他输光或,拥有钱数为,n,时,赌博停止,;,否则他将持续赌博,每次以概,率,p,赢得,1,以概率,q=1-p,输掉,1.,该系统的转移概率矩阵为,p,11,p,12,p,13,p,14,p,21,p,22,p,23,p,24,0 0 1 0,0 0 0 1,例,5.4,(,一个简单的疾病死亡模型,Fix-Neyman(,1951,),马尔可夫链,P=,例,5.6,(,带反射壁的随机游动,),在,例,5.5,中当,A,输光时将获得,赞助,1,让他继续赌下去,就如同一个在直线上做随机游,动的球在到达左侧,0,点处就立即反弹回,1,一样,这就是一,个,一侧带有反射壁的随机游动,.,此时,P=,1,0 0 0,0 0 0,q 0 p 0,0 0 0,0 q 0 p,0 0 0,0 0 0 0,q 0 p,0 0 0 0,0 0,1,(n+1)(n+1),0 1 0 0,0 0 0,q 0 p 0,0 0 0,0 q 0 p,0 0 0,0 0 0 0,q 0 p,0 0 0 0,0 0 1,(n+1)(n+1),马尔可夫链,例,5.7,在任意给定的一天,一个人的心情或者是快乐的,或者是一般的,或者是郁闷的,.,如果今天她是快乐的,那么,明天她分别以概率,0.5,0.4,和,0.1,是快乐的,一般的和郁闷,的,;,如果今天她的心情一般,那么她明天分别以概率,0.3,0.4,和,0.3,是快乐的,一般的和郁闷的,;,如果今天她是郁闷,的,那么她明天分别以概率,0.2,0.3,和,0.5,是快乐的,一般,的和郁闷的,.,以,X,n,记她第,n,天的心情,则,X,n,n0,是一个,三个状态,快乐,一般,郁闷,=0,1,2,的马尔可夫链,其转,移概率矩阵,0.5 0.4 0.1,0.3 0.4 0.3,0.2 0.3 0.5,P=,马尔可夫链,例,5.8,(,图上的简单随机游动,),设有一,蚂蚁在左图的图上爬行,当两个结,点相邻时,蚂蚁将爬向它临近一点,并且,爬向任何一个邻近点的概率,是相同的,则此,Markov,链的转移矩,阵是,下面给出一个如何将一个过程转变为马尔可夫链的例子,.,1,3,6,2,4,5,0,0 0 0,0,0 0 0,0,0,0 0 1 0 0 0,0 0,0 0,0 0 0 0 1 0,P=,马尔可夫链,例,5.9,(,将一个过程转变为马尔可夫链,),假设今天是否下雨依赖于前两天的天气条件,.,如果过去,的两天都下雨,那么明天下雨的概率为,0.7;,如果今天下雨,但昨天没下雨,那么明天下雨的概率为,0.5;,如果昨天下雨,但今天没下雨,那么明天下雨的概率为,0.4;,如果昨、今两,天都没下雨,那么明天下雨的概率为,0.2.,假设在时间,n,的状态只依赖于在时间,n-1,是否下雨,那么,上述模型就不是一个马尔可夫链,.,但是,当假定在任意时间的状态是由这天与前一天两者,的天气条件所决定时,上面的模型就可以转变为一个马尔,可夫链,.,换言之,可以假定过程处在,:,马尔可夫链,状态,0,如果昨天和今天都下雨,;,状态,1,如果昨天没有下雨但今天下雨,;,状态,2,如果昨天下雨但今天没有下雨,;,状态,3,如果昨天和今天都没有下雨,.,这就将题目所给的过程转变成了一个具有,4,个状态的马尔,可夫链,其转移概率矩阵为,0.7 0 0.3 0,0.5 0 0.5 0,0 0.4 0 0.6,0 0.2 0 0.8,例,5.10,考虑订货问题,.,设某商店使用,(s,S),订货策略,每天,早上检查某商品的剩余量,设为,x,则定购额为,0,若,xs; S-x,若,x,s.,P=,马尔可夫链,设订货和进货不需要时间,每天的需求量,Y,n,独立同分布,且,PY,n,=j=a,j,j=0,1,2,.,现在我们要从上述问题中寻,找一个,Markov,链,.,令,X,n,为第,n,天结束时的存货量,则,X,n,-Y,n+1,若,X,n,s,S-Y,n+1,若,X,n,s.,构成的,X,n,n1,是,Markov,链,.,例,5.11,以,S,n,表示保险公司在时刻,n,的盈余,这里的时间以,适当的单位来计算,(,如天,月等,),初始盈余,S,0,=x,显然为,已知,但未来的盈余,S,1,S,2,却必须视为随机变量,增量,S,n,-S,n-1,解释为,n-1,和,n,之间获得的盈利,(,可以为负,).,假定,X,1,X,2,是不包含利息的盈利且独立同分布于,F(x),则,X,n+1,=,马尔可夫链,S,n,=S,n-1,(1+i)+X,n,i,为固定的利率,S,n,n0,是一个,Markov,链,转移概率为,p,xy,=Fy-(1+i)x.,例,5.12,考察掷硬币的例子,.,硬币的正反面分别记为,U,和,D,于是状态空间为,U,D=1,2,式中,1,2,分别代表,U,D.,假定硬币初始时为正面,我们一共投掷了,50,次,.,在,每一次投掷时,硬币以概率,20%,翻转,.,于是转移概率为,:,p,11,=0.8, p,12,=0.2, p,21,=0.2, p,22,=0.8.,状态转移矩阵,P= .,进而算得,P,2,= ,P,4,= .,于是,PX,4,=U=PX,0,=UX,4,=U=,=,0.5648,.,0.8 0.2,0.2 0.8,0.68 0.32,0.32 0.68,0.5648 0.4352,0.4352 0.5648,马尔可夫链,例,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.,转移矩阵为,4,4,的矩阵,.,0.9 0.1,0.05 0.95,马尔可夫链,我们可以计算转移概率,比如,UMUM,首先有,UU(,无,转移,),而后,MM(,无转移,).,于是转移概率为,PUU|M,P,MM=0.8,0.7=0.56.,其它转移概率类似可得,.,转移方式,是,UMUM UMDM UMUW UMDW,DMUM DMDM DMUW DMDW,UWUM UWDM UWUW UWDW,DWUM DWDM DWUW DWDW,转移概率矩阵为,0.8,0.7 0.2,0.7 0.8,0.3 0.2,0.3,0.2,0.7 0.8,0.7 0.2,0.3 0.8,0.3,0.9,0.3 0.1,0.3 0.9,0.7 0.1,0.7,0.05,0.3 0.95,0.3 0.05,0.7 0.95,0.7,若从状态,UM,出发,要求在第,4,个时间周期后,硬币处于状态,D,的概率,则由于,2=DM,和,4=DW,都是状态,D,所求概率为,+ .,P=,.,马尔可夫链,例,5.14,确定汽车年保险金的系统称,好,-,坏系统,.,在该系统,中,每个参保人被赋予一个正整数值的状态,.,年保险金是,这个状态,(,保险车类型以及保险水平,),的函数,.,参保人的状态随着参保人要求理赔的次数而一年一年,地变化,.,低的状态对应于低的年保险金,.,如果参保人在上,一年没有理赔要求,他的状态就将降低,;,如果参保人在上,一年至少有一次理赔要求,他的状态一般会增加,(,可见,无,理赔是好的,并且会导致低保险金,;,而要求理赔是坏的,一,般会导致更高的保险金,).,对于给定的一个好,-,坏系统,以,s,i,(k),记一个在上一年,处在状态,i,且在该年有,k,次理赔要求的参保人在下一年的,状态,.,马尔可夫链,一般,一个特定的参保人年理赔要求的次数是参数为,的泊松随机变量,那么此参保人相继的状态将构成一个马,尔可夫链,并具有转移概率,p,ij,= ,j0,通常有多个状态,.,以下表格给出了一个假定有,4,个状态,的好,-,坏系统,:,下一个状态,状态 年保险金,0,个理赔,1,个理赔,2,个理赔,3,个理赔以上,1 200 1 2 3 4,2 250 1 3 4 4,3 400 2 3 4 4,4 600 3 4 4 4,马尔可夫链,此表说明了,:,s,2,(0)=1; s,2,(1)=3; s,2,(k)=4,k2.,考察,年理赔次数是参数为,的泊松随机变量的某个参,保人,.,如果这个参保人一年中有,k,次理赔要求的概率是,k,那么,k,= ,k0,对于表中表示的,好,-,坏系统,参保人相继的状态的转移概,率矩阵为,0,1,2,1-,0,-,1,-,2,0,0,1,1-,0,-,1,0,0,1,1-,0,-,1,0,0,0,1-,0,P=,马尔可夫链,5.2 C-K,(,Chapman-Kolmogorov,),方程,上节讨论了一步转移概率,p,ij,本节首先来定义,n,步转移,概率,它是状态处于,i,的过程,在,n,次转移后处于状态,j,的概率,即,称条件概率,=PX,n+k,=j|X,k,=i, i,jS, n0, i,j0,为,Markov,链的,n,步转移概率,相应地称,P,(n),=( ),为,n,步,转移矩阵,.,当,n=1,时, =p,ij, P,(1),=P,此外规定,= .,n,步转移概率 指的就是系统从状态,i,经过,n,步后转移到,j,的概率,它对中间的,n-1,步转移经过的状态无限制,.,0, ij,1, i=j,马尔可夫链,下面的定理给出了在归纳意义下 和,p,ij,的关系,它为,我们提供了计算,n,步转移概率的一个方法,.,定理,5.2.1,(,Chapman-Kolmogorov,方程,简称,C-K,方程,),对一,切,n,m0,和一切状态,i,j,有,(1),=,;,o,t,m,n,m,m+n,i,j,k,马尔可夫链,(2),P,(n),=P,P,(n-1),=P,P,P,(n-2),=,=P,n,.,证明,:,=PX,m+n,=j|X,0,=i,=,= (,全概率公式,),=,= PX,m+n,=j|X,m,=k,X,0,=iPX,m,=k|X,0,=i,=,= .,马尔可夫链,(2),是,(1),的矩阵形式,利用矩阵乘法即可获得,.,例,5.15,在,例,5.5,中,取,n=3,p=q=1/2.,赌徒,A,从,2,元赌金开始,赌博,.,求解他经过,4,次赌博之后输光的概率,.,解,:,这个概率为,=PX,4,=0|X,0,=2,转移矩阵,利用矩阵乘法得,所以,=5/16(,即,P,(4),中第,3,行第,1,列元素,).,1 0 0 0,0,0,0,0,0 0 0 1,P= ,1 0 0 0,5/8 1/16 0 5/16,5/16 0 1/16 5/8,0 0 0 1,P,(4),=P,4,= .,马尔可夫链,例,5.16,(,广告效益的推算,),某种鲜奶,A,改变了广告方式,.,经,调查发现,买,A,种鲜奶及另外三种鲜奶,B,C,D,的顾客每两,个月的平均转换率为,(,设市场中只有这四种鲜奶,):,A A(95%) B(2%) C(2%) D(1%);,B A(30%) B(60%) C(6%) D(4%);,C A(20%) B(10%) C(70%) D(0%);,D A(20%) B(20%) C(10%) D(50%).,假设目前购买,A,B,C,D,等四种鲜奶的顾客的分布是,(25%,30%,35%,10%).,试求半年后鲜奶,A,B,C,D,的市场份额,.,解,:,令,P,为转移矩阵,则,0.95 0.02 0.02 0.01,0.30 0.60 0.06 0.04,0.20 0.10 0.70 0.00,0.20 0.20 0.10 0.50,P= .,马尔可夫链,令,=(,1,2,3,4,)=(0.25,0.30,0.35,0.10).,经过半年,顾客在这四种鲜奶上的转移概率是,:P,(3),=P,3,.,经,计算得,因为我们所关心的是鲜奶半年后的市场占有率,故只须求,出,P,3,的前三列,.,它们依次是,A,B,C,D,四种鲜奶经,3,次转移后,转到,A,B,C,的概率,.,于是知,A,的市场占有率变为,v,A,=(,0.25,0.30,0.35,0.10,) 0.622;,B,的市场占有率变为,0.8894 0.0458 0.0466 0.0182,0.6017 0.2559 0.0988 0.0436,0.4834 0.1388 0.3658 0.0120,0.5009 0.2134 0.1426 0.1431,P,3,= .,0.8894,0.6017,0.4834,0.5009,马尔可夫链,v,B,=(,0.25,0.30,0.35,0.10,) 0.158;,C,的市场占有率变为,v,C,=(,0.25,0.30,0.35,0.10,) 0.184;,从而知,D,的市场占有率为,v,D,=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.0458,0.2559,0.1388,0.2134,0.0466,0.0988,0.3658,0.1426,马尔可夫链,例,5.17,在,例,5.1,中,如果,=0.7,=0.4,那么若今天下雨,则往后,4,天都下雨的概率是多少,?,解,:,在,=0.7,=0.4,时,例,5.1,的一步转移概率矩阵,P=,进而知,P,(2),=P,2,=,P,(4),=P,4,=,往后,4,天都下雨的概率是,P,(4),中的,即,0.5749.,例,5.18,在,例,5.9,中,已知星期一与星期二下雨,问星期四,下雨的概率是多少,?,解,:,做计算,0.7 0.3,0.4 0.6,0.61 0.39,0.52 0.48,0.5749 0.4251,0.5668 0.4332,马尔可夫链,P,(2),=P,2,=,由于星期四下雨,等价于星期四处在状态,0,或状态,1,的过,程,所以要求的概率由,=0.49+0.12,确定,即,0.61.,被定义为,给定在时间,k,时的状态,i,时,在时间,k+n,时,过程处于状态,j,的概率,这个概率是条件概率,.,前面,我们,曾指出,一旦,Markov,链,的,初始状态,PX,0,=i,0,给定,其统计特,性就完全由条件概率,PX,n,=i,n,|X,n-1,=i,n-1,所决定,.,该表述的含义是,0.49 0.12 0.21 0.18,0.35 0.20 0.15 0.30,0.20 0.12 0.20 0.48,0.10 0.16 0.10 0.64,马尔可夫链,首先,当给定在时间,0,时的状态,i,时,在时间,n,时过程处于,状态,j,的概率,仍为条件概率,;,如果要求在时间,n,的状态的无条件分布,可以经过对初,始状态取条件算得,即,PX,n,=j= PX,n,=j|X,0,=iPX,0,=i,= ,i,式中,i,=PX,0,=i, i0, ,i,=1.,例如,在,例,5.17,中,如果,0,=0.4,1,=0.6,那么在保留今,天天气记录下,往后四天在下雨的无条件概率,PX,4,=0=0.4,+0.6,=0.4,0.5749+0.6,0.5668,=0.5700.,马尔可夫链,考虑马尔可夫链到时间,n,为止进入任意一个特定的状态,集合,A,的概率,.,取得它的一个途径是,重置离开,A,中状态的转移概率,为,PX,m+1,=j|X,m,=i=,即,A,中所有的状态转变为吸收态,一旦进入此状态就不能,离开,.,因为,原来的和转变后的马尔可夫链直到进入,A,中的一,个状态前遵从相同的概率,由此可以推知原来的马尔可夫,链到时间,n,为止进入,A,中的一个状态的概率等于转变后的,马尔可夫链在时间,n,处在,A,中的一个状态的概率,.,例,5.19,一个领养老金的人在每月初领收,2(,千元,).,她每月,需要花费的金额独立于她拥有的,金额,并以概率,p,i,等于,1,若,i,A,j=i,0,若,i,A,ji,马尔可夫链,i,i=1,2,3,4, p,i,=1.,如果她在月末金额多于,3,她便将超过,3,的金额送给她的,儿子,.,如果在月初领收养老金后她有金额,5,问在随后的四,个月中的任意时间,她拥有的资金等于或者少于,1,的概率,是多少,?,解,:,为了求得,“,她拥有的资金等于或者少于,1,的概率,”,我们,考察一个马尔可夫链,其状态是该养老人在月末拥有的,金额,.,由于所关心的是这一金额是否,1,我们就以,1,表示,“,她,的月末金额最终,1,”,(,A,=1).,因为,这个养老人在月末将任何超过,3,的部分送给了她,的儿子,所以只需考虑状态为,1,2,3,的马尔可夫链,.,转移,马尔可夫链,概率矩阵,P=(p,ij,)=,为了理解这一转移概率矩阵,考虑,p,21,.,它是给定养老人在,月末拥有金额,2,时,她在下一个月月末拥有的金额小于或,等于,1,的概率,.,因为她一个新月份的月初金额是,2+2=4,只,有她花费,3,或,4,在月末她拥有的金额才小于或等于,1.,因,此,p,21,=p,3,+p,4,.,假定,p,i,=1/4,i=1,2,3,4.,于是,转移概率矩阵,P=,1 0 0,p,3,+p,4,p,2,p,1,p,4,p,3,p,1,+p,2,1 0 0,1/2 1/4 1/4,1/4 1/4 1/2,马尔可夫链,P,(4),=P,4,=,因为,养老人初始月末的资金是,3,所以要求的概率是,=,201/256.,设,X,n,n0,是转移概率为,p,ij,的马尔可夫链,如果以,q,ij,记转变,A,中的一切状态为吸收态的转移概率,则,q,ij,=,对于,i,j,A,n,阶段转移概率 代表开始处于状态,i,的原,来的链,并没有进入,A,中的任一状态,且在时间,n,处于状态,j,的概率,.,1 0 0,222/256 13/256 21/256,201/256 21/256 34/256,1,若,i,A,j=i,0,若,i,A,ji,P,ij,其它,马尔可夫链,例如,在,例,5.19,中,在一月初开始是,5,养老人的金额从未小,于或等于,1,且在,5,月初的资金是,4,的概率是,=21/256.,假定链在开始时处在状态,i,到时间,n,为止从未进入过,A,中的任一状态时,X,n,的条件概率可以这样计算,:,对于,i,j,A,PX,n,=j|X,0,=i,X,k,A,k=1,2,n,PX,n,=j,X,k,A,k=1,2,n|X,0,=i,PX,k,A,k=1,2,n|X,0,=i,= .,=,马尔可夫链,5.3,状态的分类,本节,我们首先讨论,Markov,链各个状态之间的关系,并,以这些关系将状态分类,然后研究它们的一些性质,.,状态,j,称为是从状态,i,可达的,(,或,状态,i,可达状态,j,),对,i,j0,1,2,若存在,n0,使有,0,记为,ij.,若同时有状态,ji,则,称,i,与,j,互通,记为,i j.,以,0,定义,j,从状态,i,可达,是合理的,因为,如果状态,j,不是从状态,i,可达的,那么,P,最终进入状态,j|,开始在状态,i,=P X,n,=j|X,0,=i PX,n,=j|X,0,=i= =0.,马尔可夫链,例,5.20,考虑转移概率矩阵如右的由,0,1,1/2 1/2 0,2,三个状态组成的马尔可夫链,.01,且,P=,1/2 1/4 1/4,12,其转移概率分别为,1/2,和,1/4.,0 1/3 2/3,显然,任意状态都与它自己是互通的,因为,=PX,0,=i|X,0,=i=1.,互通,作为状态之间的关系,它是状态空间上的一种等价,关系,.,定理,5.3.1,互通是状态空间上的等价关系,即互通具有以,下三个性质,:,(1),自返性,状态,i0, i i;,(2),对称性 若状态,i j,则状态,j i;,(3),传递性 若状态,i j,且状态,j k,则状态,i k.,马尔可夫链,证明,:,(1),、,(2),互通性的成立是显然的,.,只证,(3),.,由互通定义知,需证,ik,且,ki.,首先,由,ij,jk,知道,存在,m,n,使得 ,0,0.,再由,C-K,方程得,= ,0,故,ik;,反过来同样有,ki.,所以,i k.,我们把任何两个,互通状态,归为一类,由,定理,5.3.1,同在,一类的状态都是互通的,并且任何一个状态不能同时属于,两个不同的类,.,定义,5.3.1,若,Markov,链只存在一个类,(,所有的状态彼此互,通,),则称它是不可约的,.,否则称它为,可约的,.,例,5.20,中的,3,个状态,0,1,2,之间是互通,的,(210,的转,移概率分别是,1/3,和,1/2),因而这个,Markov,链,是,不可约的,.,马尔可夫链,下面,我们首先给出状态的一些性质,然后证明同在一类,的状态具有相同的性质,.,定义,5.3.2,(,周期性,),若集合,n:n1,0,非空,则称它,的,最大公约数,d=d(i),为状态,i,的,周期,.,若,d,1,称,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.,马尔可夫链,命题,设状态,i,的周期为,d,则存在正整数,M,对一切,nM,有,0.,证明,:,令,n:n1,0=n,1,n,2,记,t,k,=G.C.Dn,1,n,2,n,k,则,t,1,t,2,d1.,因此,存在正整数,N,使有,t,N,=t,N+1,=,=d.,可见,d=G.C.Dn,1,n,2,n,N,.,于是,存在正整数,M,对一切,M,之,n,成立,nd=d (n,k,=d ,k=1,2,N),并有,马尔可夫链,例,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).,证明,:,由类的定义知,i j,即存在,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,马尔可夫链,+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,马尔可夫链,记,=PT,ij,=n|X,0,=i(,T,ij,=min(n|X,0,=i,X,n,=j),首进时间,),=PX,n,=j,X,k,j,k=1,2,n-1|X,0,=i,n1;,=0.,式中的,i,j,是状态空间中的任意两个状态,(,注意 与,定义不同,).,它表示过程由状态,i,出发,经,n,步首次到达状态,j,的概率,这个概率也称,首中概率,.,记,f,ij,= (,当,i=j,时,简记,f,ii,为,f,i,),它表示过程由状态,i,出发,经有限步最终到达状态,j,的概率,.,显然,表示过程从状态,i,出发,经,n(n=1,2,),步返回,i,的概率,.,如果, ,n1,构成一概率分布,则该分布的,期,望值,i,= n,表示从状态,i,出发再返回到,i,的平均时间,.,马尔可夫链,例,5.21,考虑由,0,1,2,3,四个状态组成的,Markov,链,.,其转移,概率矩阵为,1/2 1/2 0 0,1/2 1/2 0 0,1/4 1/4 1/4 1/4,0 0 0 1,在该,Markov,链中,0 1.,尽管,0,与,1,都是从,2,可达的,但是,2,既不能从,0,可达,也不能从,1,可达,所以,2,与,0,、,2,与,1,是不,互通的,.,状态,3,是一个吸收态,(,即,p,33,=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,马尔可夫链,态变化,.,由转移矩阵可得转移图,:,容易看出,S,1,S,1,S,2,S,1,S,1,S,2,S,2,S,2,S,1,S,3,S,2,S,3,S,1,S,4,S,2,S,4,.,所以只有,S,1,S,2,但,S,3,S,1,S,4,S,1,S,3,S,2,S,4,S,2,S,3,S,4,S,4,S,3,.,状态可分为三类,:S,1,S,2,S,3,和,S,4,.,以类似的方法,可以说明,例,5.5,中赌徒输光问题中满足,0,i,j,n,的任何两个状态,i,j,都互通,而且该链的所有状,态可分为三类,:0,1,2,n-1,n.,对于任一状态,i,我们知,f,i,记开始在状态,i,的过程,最终,再,进入,i,的概率,.,状态,i,称为常返态,如果,f,i,=1,;,状态,i,称为暂态,如果,f,i,1,.,S,1,S,2,S,3,S,4,p,11,p,22,P,33,=1,P,44,=1,p,14,p,12,p,21,p,24,p,13,p,23,马尔可夫链,假设过程开始在状态,i,且,i,是常返态,.,那么,过程将以概,率,1,再进入,i.,但是,由马尔可夫链的定义,当它在进入,i,时,该过程将又重复,.,从而状态,i,最终将再度被访问,.,继续重复以上推理,我们产生以下,结论,:,如果状态,i,是常返态,那么开始在状态,i,的过程将一再地,进入,i,(,进入的次数事实上无穷,).,另一方面,假设状态,i,是暂态,.,此时,过程每次进入,i,将有,一个正的概率,1-f,i,不再进入这个状态,.,所以,开始,(0,时刻,),在状态,i,的过程恰好在状态,i,停留,n,个时间周期的概率等于,(1-f,i,),n1.,换句话说,:,如果状态,i,是暂态,那么,开始在状态,i,的过程处于状态,i,马尔可夫链,的时间周期个数有一个有限均值为,1/(1-f,i,),的,几何分布,.,定义,5.3.3,对于常返态,i,若,i,+,则称,i,为,正常返态,;,若,i,=+,则称,i,为,零常返态,.,特别地,若,i,正常返且是,非周期的,则称之为,遍历状态,.,若,i,是遍历状态且,=1,则称,i,为,吸收状态,此时,显然,i,=1.,可以证明,对于同属一类的状态,i,j,它们同为常返态或,暂态,;,且当它们是常返态时,又同为正常返态和零常返态,.,以下,是对上述概念和性质的总结,:,齐次马氏链的状态分类,1.,称,d=d(i)=GCDn:n1,p,ii,(n),0,为,状态,i,的周期,.,(1),d,1,称,状态,i,为周期的,;,(2),d=1,称,状态,i,为非周期的,.,马尔可夫链,事实,.,(1),若,i,有周期,d,则对一切非零的,n0(mod d),都,有,p,ii,(n),=0,但并非对任意,nd,有,p,ii,(nd),0;,(2),若,i,的周期为,d,则存在正整数,M,对一切,nM,有,p,ii,(nd),0.,首达概率,对,n1,f,ij,(n),=PX,n,=j,X,k,j,k=1,2,n-1|X,0,=i;f,ij,(0),=0.,及,过程由,i,出发,经有限步,最终到达,j,的概率,.,f,ij,= f,ij,(n),如,i=j,时,则简记,f,ii,为,f,i,.,当,f,i,=1,时,称,状态,i,是常返态,;,当,f,i,1,时,称状态,i,是暂,态,(,滑过的状态,).,事实,.,(1),若,i,是暂态,则由,i,出发将以正概率,1-f,i,永远不,再返回到,i;,对常返态此现象不会发生,;,马尔可夫链,(2),对常返态,i,f,ii,(n),n1,构成一概率分布,该分,布的期望值,i,= nf,ii,(n),表示过程由,i,出发再返,回到,i,的,平均返回时间,.,2.,设状态,i,为常返态,若,i,则称,常返态,i,是正常返,的,;,若,i,=,则称,常返态,i,是零常返的,;,非周期的正,常返态称为,遍历状态,.,重要事实,.,对任意,i,jS,n1,有,p,ij,(n),= f,ij,(k),p,jj,(n-k),.,证明,:,=PX,n,=j|X,0,=i,= PX,n,=j,X,v,j,v=1,2,k-1|X,0,=i,= PX,n,=j|X,k,=j,X,v,j,v=1,2,k-1,X,0,=i,PX,k,=j,X,v,j,v=1,2,k-1|X,0,=i,= p,jj,(n-k),f,ij,(k),= f,ij,(k),p,jj,(n-k),.,马尔可夫链,从对,事实,的证明,我们还可看出所述事实的对称形式,:,p,ij,(n),= f,ij,(n-k),p,jj,(k),.,C-K,方程,以及以上,事实,是,马尔可夫链的关键性公式,它,们可以把,p,ii,(n),分解成较低步的转移概率之和的形式,.,而且,通过这个事实,我们可以得到关于,周期的等价定,义,: GCDn:n1,p,ii,(n),0=GCDn:n1,f,ii,(n),0.,马尔可夫链的状态,有以下,分类,:,暂态,状态 零常返态,常返态 是周期的,正常返态,是非周期的,-,遍历态,马尔可夫链,例,5.23,设马尔可夫链的状态空间,S=1,2,3,4,其一步转,移概率矩阵,:,状态转移图,:,P=,试对其状态分类,进而确定哪些状态是常返态,并确定,其周期,.,解,:,因为对一切,n1,f,44,(n),=0,所以,f,4,= f,44,(n),=0,1,可见状态,4,是一个暂态,.,又,f,33,(1),=2/3,且对,n2,f,33,(n),=0,所以,f,3,=2/3,1,从,而知,状态,3,也是暂态,.,而,f,1,=f,11,(1),+f,11,(2),=1/2+1/2=1(n,步,首中概率,求和,),及,1/2 1/2 0 0,1 0 0 0,0 1/3 2/3 0,1/2 0 1/2 0,1,2,3,4,1/2,1/2,1/2,1/2,1/3,2/3,1,马尔可夫链,f,2,=f,22,(1),+f,22,(2),+,=0+1/2+1/2,2,+,=1,所以状态,1,和状态,2,是常返态,.,显然,状态,1,与状态,2,的周期为,1.,再由,1,= nf,11,(n),=1,(1/2)+2,(1/2)=3/2,2,= nf,22,(n),=1,0+2,(1/2)+3,(1/2,2,)+,=3,知,状态,1,与状态,2,是正常返态,且为遍历态,.,为何成立,1,0+,2,(1/2)+3,(1/2,2,)+,=3,?,因为,当记,f(n)=2,1/2+3,1/2,2,+4,1/2,3,+5,1/2,4,+ 6,1/2,5,+,+n,1/2,n-1,以及,g(n)=1/2+1/2,2,+1/2,3,+1/2,4,+1/2,5,+,+1/2,n-1,时,f(n)-g(n)=1/2+(1/2)f(n)-n/2,n,.,而此式即,f(n)=1+2,g(n)-n/2,n-1,.,于是有,当,n,时, n/2,n-1,0, g(n)=1,f(n)=3.,马尔可夫链,例,5.24,已知马尔可夫链,X,n,n0,的状态空间,S=1,2,3,4,其转移概率矩阵,P,的状态转移图为,:,试对该马尔可夫链的状态进行分类,.,解,:,显然,S,中的状态是互通的,.,因为,p,11,=1/4,所以,n:p,11,(n),0,的最大公约数,d=1,可见,状态,1,是非周期的,.,于是,状态,2,3,4,也是非周期的,