第5章 马尔可夫链

《第5章 马尔可夫链》由会员分享，可在线阅读，更多相关《第5章 马尔可夫链（178页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,应用随机过程,主讲教师 段禅伦,,2011,年秋季学期,计算机学院研究生专业基础课程,《,应用数学基础,》,(Applied Stochastic processes),第,5,章 马尔可夫链,5.1,引言,,本章,,,首先考察取有限个值或者可数个可能值的随机过,,程,{X,n,,n=0,1,2,,…,}.,一般将这种随机过程的可能值的集合,,也记为,{0,1,2,,…,}(,即,状态空间,也是非负整数集,).,,,如果,X,n,=i,,那么称随机过程在时刻,n,在状态,i.,,,设只要

2、过程在状态,i,,就有一个固定的概率,p,ij,,,使它在,,下一个时刻在状态,j.,我们有,,定义,5.1.1,若对于一切状态,i,0,,i,1,,,…,,i,n-1,,i,j,与一切,n≥0,,,有,P{X,n+1,=j|X,n,=i,X,n-1,=i,n-1,,,…,,,X,1,=i,1,,X,0,=i,0,},,=P{X,n+1,=j|X,n,=i},,=p,ij,则称,,这样的随机过程称为,马尔可夫链,.,并称由此式刻画的马尔,马尔可夫链,可夫链的特性为,Markov,性,,,亦称,“,无后效性,”,.,此性质说明,:,,,要确定过程将来的状态,,,知道它此刻的状态就足够了,,,,并

3、不需要对它以往状况的认识,.,也就是说,,对于一个马尔可夫链,,,在给定,过去的状态,X,0,,X,1,,,…,,X,n-1,,和,现在的状态,X,n,时,,,将来的状态,X,n+1,的,条件分布,独立于过,,去的状态而,只依赖于现在的状态,.,,p,ij,表示过程处在状态,i,时,,,下一次转移到状态,j,的概率,.,,由于概率值非负且过程必须转移到某个状态,,,所以有,,,p,ij,≥0, i,j≥0(,即,i,j∈I);,,p,ij,=1, i=0,1,2,,…,(,即,i∈I),,我们称,P{X,n+1,=j|X,n,=i}=p,ij,为,Markov,链,{X,n,,n=0,1,2,

4、,…,},的,,一步转移概率,,,简称,转移概率,.,,(★),马尔可夫链,由,Markov,链定义,知,,,P{X,0,=i,0,,X,1,=i,1,,,…,,X,n,=i,n,},,=P{X,n,=i,n,|X,0,=i,0,,X,1,=i,1,,,…,,X,n-1,=i,n-1,}P{X,0,=i,0,,X,1,=i,1,,,…,,,,X,n-1,=i,n-1,},,=P{X,n,=i,n,|X,n-1,=i,n-1,}P{X,0,=i,0,,X,1,=i,1,,,…,,X,n-1,=i,n-1,},,=,…,,=P{X,n,=i,n,|X,n-1,=i,n-1,}P{X,n-1,=i,

5、n-1,|X,n-2,=i,n-2,},…,P{X,1,=i,1,|,,X,0,=i,0,}P{X,0,=i,0,},,可见一旦,Markov,链,的,初始分布,P{X,0,=i,0,},给定,,,其统计特性,,就完全由条件概率,,,P{X,n,=i,n,|X,n-1,=i,n-1,},,所决定,.,马尔可夫链,,如何确定这个条件概率,,,是,Markov,链理论和应用中的重,,要问题之一,.,,一般,情况下,,,转移概率,p,ij,与状态,i,j,和时间,n,有关,.,,,当,Markov,链的转移概率,P{X,n+1,=j|X,n,=i},,只与状态,i,,,j,有,,关,,,而与,n,无

6、关时,,,称,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,,…,,…,,

7、…,,…,,…,,…,马尔可夫链,称,P,为,转移概率矩阵,,,一般简称为,转移矩阵,.,,,转移概率矩阵具有性质,(★),.,称具有此性质的矩阵为,随,,机矩阵,(,随机矩阵是非负实数矩阵且每一行元素的和为,1).,,例,5.1,(,天气预报,),,,假设明天下雨的机会只依赖于前一天的天气条件,,,即今,,天是否下雨,,,而不依赖过去的天气条件,.,且如果今天下雨,,,,那么明天下雨的概率为,α;,若今天没下雨,,,明天下雨的概,,率为,β.,,,如果下雨,,,记过程在状态,0;,如果不下雨,,,记过程在状态,1.,,如此,,,本例是一个两状态,{0,1},的马尔可夫链,,,其转移概率,,矩

8、阵是,:,,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,,±

9、,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,(,即相异原因的非生命状态,),的模型,.,若

10、个体病愈,,,则,,认为它处于状态,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

11、 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,,…,,…,,…,,…,,…

12、,,…,,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,,在任意给定的一天,,,一个人的心情或者是快乐的,,,,或者是一般的,,,或者是郁闷的,.,如果今天她是快乐的,

13、,,那么,,明天她分别以概率,0.5,0.4,和,0.1,是快乐的,,,一般的和郁闷,,的,;,如果今天她的心情一般,,,那么她明天分别以概率,0.3,,,0.4,和,0.3,是快乐的,,,一般的和郁闷的,;,如果今天她是郁闷,,的,,,那么她明天分别以概率,0.2,0.3,和,0.5,是快乐的,,,一般,,的和郁闷的,.,以,X,n,记她第,n,天的心情,,,则,{X,n,,n≥0},是一个,,三个状态,{,快乐,,,一般,,,郁闷,}={0,1,2},的马尔可夫链,,,其转,,移概率矩阵,,,0.5 0.4 0.1,,0.3 0.4 0.3,,0.2 0.3 0.5,P=,马尔

14、可夫链,例,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

15、,(,将一个过程转变为马尔可夫链,),,,假设今天是否下雨依赖于前两天的天气条件,.,如果过去,,的两天都下雨,,,那么明天下雨的概率为,0.7;,如果今天下雨,,但昨天没下雨,,,那么明天下雨的概率为,0.5;,如果昨天下雨,,但今天没下雨,,,那么明天下雨的概率为,0.4;,如果昨、今两,,天都没下雨,,,那么明天下雨的概率为,0.2.,,,假设在时间,n,的状态只依赖于在时间,n-1,是否下雨,,,那么,,上述模型就不是一个马尔可夫链,.,,,但是,,,当假定在任意时间的状态是由这天与前一天两者,,的天气条件所决定时,,,上面的模型就可以转变为一个马尔,,可夫链,.,,,换言之,,,可以

16、假定过程处在,:,马尔可夫链,,状态,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,,

17、若,x≥s; S-x,,若,x,＜,s.,,P=,马尔可夫链,,设订货和进货不需要时间,,,每天的需求量,Y,n,独立同分布,,且,P{Y,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,,n≥1},是,Markov,链,.,,例,5.11,,以,S,n,表示保险公司在时刻,n,的盈余,,,这里的时间以,,适当的单位来计算,(,如天,,,月等,),,初始盈余,S,0,=

18、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,,n≥0},是一个,Markov,链,,,转移概率为,,,p,xy,=F[y-(1+i)x].,,例,5.12,,考察掷硬币的例子,.,硬币的正反面分别记为,U,和,D,,,,于是状态空间为,{U,D}={1,2},,式中,

19、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,= .,于是,P{X,4,=U}=P{X,0,=U→X,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.43

20、52 0.5648,,马尔可夫链,例,5.13,(,隐,Markov,链模型,),这里用简单例子引出隐,Markov,,链模型,.,,,假定有分别记为,M,和,W,的两枚硬币,.,在任何给定的时刻,,两枚硬币或者为正面或者为反面,.,在任何给定时刻只有一,,枚硬币呈现,,,但是有时硬币可能被替换,(M,换成,W,或,W,换成,M),,但不改变其正反面,.,硬币,M,具有与,例,5.12,相同的转移概率,,,,硬币,W,具有转移概率,.,,,在任何给定时刻硬币被替换的概率为,30%,,替换完成时,,,,硬币的状态不变,.,这一,Markov,链有,4,个状态,,,分别记为,,,1:UM; 2

21、:DM; 3:UW; 4:DW.,,状态,1,3,表示正面,U,,状态,2,4,表示反面,D.,转移矩阵为,4,×,4,,的矩阵,.,0.9 0.1,,0.05 0.95,马尔可夫链,,我们可以计算转移概率,,,比如,UM→UM,,首先有,U→U(,无,,转移,),,而后,M→M(,无转移,).,于是转移概率为,P{U→U|M},·,P{,,M→M}=0.8,×,0.7=0.56.,其它转移概率类似可得,.,转移方式,,是,UM→UM UM→DM UM→UW UM→DW,,DM→UM DM→DM DM→UW DM→DW,,UW→UM UW→DM UW→UW UW→D

22、W,,DW→UM DW→DM DW→UW DW→DW,,转移概率矩阵为,,,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,,

23、所求概率为,+ .,,P=,,.,,,马尔可夫链,例,5.14,,确定汽车年保险金的系统称,好,-,坏系统,.,在该系统,,中,,,每个参保人被赋予一个正整数值的状态,.,年保险金是,,这个状态,(,保险车类型以及保险水平,),的函数,.,,,参保人的状态随着参保人要求理赔的次数而一年一年,,地变化,.,低的状态对应于低的年保险金,.,如果参保人在上,,一年没有理赔要求,,,他的状态就将降低,;,如果参保人在上,,一年至少有一次理赔要求,,,他的状态一般会增加,(,可见,,,无,,理赔是好的,,,并且会导致低保险金,;,而要求理赔是坏的,,,一,,般会导致更高的保险金,).,,,对于给定的一

24、个好,-,坏系统,,,以,s,i,(k),记一个在上一年,,处在状态,i,,且在该年有,k,次理赔要求的参保人在下一年的,,状态,.,马尔可夫链,,一般,,,一个特定的参保人年理赔要求的次数是参数为,λ,,的泊松随机变量,,,那么此参保人相继的状态将构成一个马,,尔可夫链,,,并具有转移概率,,,p,ij,= ,j≥0,,,通常有多个状态,.,以下表格给出了一个假定有,4,个状态,,的好,-,坏系统,:,,,下一个状态,,状态 年保险金,0,个理赔,1,个理赔,2,个理赔,3,个理赔以上,,,1 200 1 2 3

25、 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,k≥2.,,,考察,,,年理赔次数是参数为,λ,的泊松随机变量的某个参,,保人,.,如果这个参保人一年中有,k,次理赔要求的概率是,α,k,,,,那么,,,α,k,= ,k≥0,,对于表中表示的,好,-,

26、坏系统,,,参保人相继的状态的转移概,,率矩阵为,,,α,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,,的概率,,,即,,称条件概率,,,=P{X,n+k,=j|X,k,=i}, i,j∈S, n≥0, i,j≥0,,为,Markov

27、,链的,n,步转移概率,,,相应地称,P,(n),=( ),为,n,步,,转移矩阵,.,,,当,n=1,时,, =p,ij,, P,(1),=P,,此外规定,= .,,n,步转移概率 指的就是系统从状态,i,经过,n,步后转移到,j,的概率,,,它对中间的,n-1,步转移经过的状态无限制,.,,,,0, i≠j,,1, i=j,,,,,马尔可夫链,,下面的定理给出了在归纳意义下 和,p,ij,的关系,,,它为,,我们提供了计算,n,步转移概率的一个方法,.,,定理,5.2.1,(,Chapman-Kolmogorov,方程,,,简称,C-K,方程,),对一,

28、,切,n,m≥0,和一切状态,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,.,,证明,:,,=P{X,m+n,=j|X,0,=i},,=,,= (,全概率公式,),,=,,= P{X,m+n,=j|X,m,=k,X,0,=i}P{X,m,=k|X,0,=i},,=,·,,= .,,,,,,,,,,,,,,,,,,,,马尔可夫链,,(2),是,(

29、1),的矩阵形式,,,利用矩阵乘法即可获得,.,,例,5.15,在,例,5.5,中,,,取,n=3,p=q=1/2.,赌徒,A,从,2,元赌金开始,,赌博,.,求解他经过,4,次赌博之后输光的概率,.,,解,:,,这个概率为,=P{X,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,

30、,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

31、 → 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.

32、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.

33、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.184≈0.036.,,A,种鲜奶的市场份额由原来的,25%,增至,62.2%,

34、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,的一步转移概率矩阵,

35、,,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,确定,,,即,,,

36、0.61.,,,被定义为,,,给定在时间,k,时的状态,i,时,,,在时间,k+n,时,,过程处于状态,j,的概率,,,这个概率是条件概率,.,前面,,,我们,,曾指出,,,一旦,Markov,链,的,初始状态,P{X,0,=i,0,},给定,,,其统计特,,性就完全由条件概率,,,P{X,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,,,马尔可夫链,,首先,,,当给定在时间,

37、0,时的状态,i,时,,,在时间,n,时过程处于,,状态,j,的概率,,,仍为条件概率,;,,,如果要求在时间,n,的状态的无条件分布,,,可以经过对初,,始状态取条件算得,,,即,,,P{X,n,=j}= P{X,n,=j|X,0,=i}P{X,0,=i},,= α,i,,,式中,,α,i,=P{X,0,=i}, i≥0, α,i,=1.,,,例如,在,例,5.17,中,,,如果,α,0,=0.4,,,α,1,=0.6,,,那么在保留今,,天天气记录下,,,往后四天在下雨的无条件概率,,,P{X,4,=0}=0.4,·,+0.6,·,,,=0.4,·,0.5749+

38、0.6,·,0.5668,,=0.5700.,,,,,,,,马尔可夫链,,考虑马尔可夫链到时间,n,为止进入任意一个特定的状态,,集合,A,的概率,.,取得它的一个途径是,,,重置离开,A,中状态的转移概率,为,,,P{X,m+1,=j|X,m,=i}=,,即,A,中所有的状态转变为吸收态,,,一旦进入此状态就不能,,离开,.,,,因为,,,原来的和转变后的马尔可夫链直到进入,A,中的一,,个状态前遵从相同的概率,,,由此可以推知原来的马尔可夫,,链到时间,n,为止进入,A,中的一个状态的概率等于转变后的,,马尔可夫链在时间,n,处在,A,中的一个状态的概率,.,,例,5.19,,一个领养老金

39、的人在每月初领收,2(,千元,).,她每月,,需要花费的金额独立于她拥有的,金额,,,并以概率,p,i,等于,1,,若,i∈,A,,j=i,,0,,若,i∈,A,,j≠i,,马尔可夫链,i,,i=1,2,3,4, p,i,=1.,,,如果她在月末金额多于,3,,她便将超过,3,的金额送给她的,,儿子,.,如果在月初领收养老金后她有金额,5,,问在随后的四,,个月中的任意时间,,,她拥有的资金等于或者少于,1,的概率,,是多少,?,,解,:,为了求得,“,她拥有的资金等于或者少于,1,的概率,”,,,我们,,考察一个马尔可夫链,,,其状态是该养老人在月末拥有的,,金额,.,,,由于所关心的

40、是这一金额是否≤,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,.,,

41、,假定,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,,n≥0},是转移概率为,p,ij,的马尔可夫链,,,如果以,q,ij,,记转变,A,中的一切状态为吸收态的转移概率,,,则,,,q,ij,=,,对于,i,j∈,A,,n,阶段转移概率

42、 代表开始处于状态,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,,j≠i,,P,ij,,,其它,,,马尔可夫链,例如,在,例,5.19,中,,,在一月初开始是,5,,养老人的金额从未小,,于或等于,1,,且在,5,月初的资金是,4,的概率是,=21/256.,,,假定链在开始时处在状态,i,,到时间,n,为止从未进入过,A,,中的任一状态时,

43、,X,n,的条件概率可以这样计算,:,,,对于,i,j∈,A,,,,P{X,n,=j|X,0,=i,X,k,∈,A,,k=1,2,,…,,n},,P{X,n,=j,X,k,∈,A,,k=1,2,,…,,n|X,0,=i},,P{X,k,∈,A,,k=1,2,,…,,n|X,0,=i},,= .,,,=,,马尔可夫链,5.3,状态的分类,,本节,,,我们首先讨论,Markov,链各个状态之间的关系,,,并,,以这些关系将状态分类,,,然后研究它们的一些性质,.,,,状态,j,称为是从状态,i,可达的,(,或,状态,i,可达状态,j,),,对,i,,,j∈{0,1,2,,…,},

44、,若存在,n≥0,,使有,,＞,0,,记为,i→j.,,,若同时有状态,j→i,,则,称,i,与,j,互通,,,记为,i j.,,以,＞,0,定义,j,从状态,i,可达,是合理的,,,因为,,如果状态,j,不是从状态,i,可达的,,,那么,,,P{,最终进入状态,j|,开始在状态,i},,=P{ {X,n,=j|X,0,=i}≤ P{X,n,=j|X,0,=i}= =0.,,,,,,,,,,,,马尔可夫链,例,5.20,,考虑转移概率矩阵如右的由,0,1,,1/2 1/2 0,,2,三个状态组成的马尔可夫链,.0→1,且,P=,1/2 1/4 1/4,,1→2,其转移

45、概率分别为,1/2,和,1/4.,0 1/3 2/3,,显然,,,任意状态都与它自己是互通的,,,因为,,,=P{X,0,=i|X,0,=i}=1.,,互通,作为状态之间的关系,,,它是状态空间上的一种等价,,关系,.,,定理,5.3.1,,互通是状态空间上的等价关系,,,即互通具有以,,下三个性质,:,,,(1),,自返性,状态,i≥0, i i;,,,(2),,对称性 若状态,i j,,则状态,j i;,,,(3),,传递性 若状态,i j,且状态,j k,,则状态,i k.,,,,,,,,,,,,,,,,,,,马尔可夫链,证明,:,,(1),、,(2),互通性的成立是显然

46、的,.,只证,(3),.,,,由互通定义知,,,需证,i→k,且,k→i.,首先,,,由,i→j,j→k,,,知道,,,存在,m,n,使得 ＞,0,,＞,0.,再由,C-K,方程得,,,= ≥,＞,0,,故,i→k;,反过来同样有,k→i.,,,所以,i k.,,,我们把任何两个,互通状态,归为一类,,,由,定理,5.3.1,,,同在,,一类的状态都是互通的,,,并且任何一个状态不能同时属于,,两个不同的类,.,,定义,5.3.1,,若,Markov,链只存在一个类,(,所有的状态彼此互,,通,),则称它是不可约的,.,否则称它为,可约的,.,,,例,5.20,中的,3,

47、个状态,0,1,2,之间是互通,的,(2→1→0,的转,,移概率分别是,1/3,和,1/2),,因而这个,Markov,链,是,不可约的,.,,,,,,,,,,,马尔可夫链,,下面,我们首先给出状态的一些性质,,,然后证明同在一类,,的状态具有相同的性质,.,,定义,5.3.2,(,周期性,),若集合,{n:n≥1,,＞,0},非空,,,则称它,,的,最大公约数,d=d(i),为状态,i,的,周期,.,若,d,＞,1,,称,i,是,周,,期的,;,若,d=1,,称,i,是,非周期的,.,并特别规定集合,{n:n≥1,,,,＞,0},为空集时,,,称,i,的,周期无穷大,.,,说明,:,由,定义

48、,5.3.2,知,,,虽然,i,有周期,d,但并不是对所有的,n,,,,都大于,0.,例如,,,如果集合,{n:n≥1,,＞,0},为,{3,9,,,18,21,,…,},,其公约数,d=3,,即,3,是,i,的周期,,,显然,,n=6,12,,,15,都不属于该集合即,=0, =0, =0.,但是,可以证,,明,,,当,n,充分大之后,,,必定有 ＞,0.,,,,,,,,,,马尔可夫链,命题,设状态,i,的周期为,d,,则存在正整数,M,,对一切,n≥M,,有,,＞,0.,,证明,:,令,{n:n≥1,,＞,0}={n,1,,n,2,,,…,},,记,,,t,k,=G.C.D{

49、n,1,,n,2,,,…,,n,k,},,则,,,t,1,≥t,2,≥,…,≥d≥1.,,,因此,,,存在正整数,N,,使有,t,N,=t,N+1,=,…,=d.,可见,,,d=G.C.D{n,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,出发,,,

50、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

51、,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,出发,

52、,,经两,,步必定返回,.,而状态,2,则不然,.,当,2,转移到,3,后,,,它再也不能,,返回到,2.,,,为区分,这样的两种状态,,,我们引入,常返性,的概念,.,,,,,,,,,,,,,,,,,,,,,,,,1,2,3,4,1,1,1,1/2,1/2,马尔可夫链,,记,=P{T,ij,=n|X,0,=i}(,T,ij,=min(n|X,0,=i,X,n,=j),首进时间,),,=P{X,n,=j,X,k,≠j,k=1,2,,…,,n-1|X,0,=i},n≥1;,,=0.,,式中的,i,j,是状态空间中的任意两个状态,(,注意 与,,定义不同,).,它表示过程由状态,i,出发,,,

53、经,n,步首次到达状态,,j,的概率,,,这个概率也称,首中概率,.,,,记,,,f,ij,= (,当,i=j,时,,,简记,f,ii,为,f,i,),,它表示过程由状态,i,出发,,,经有限步最终到达状态,j,的概率,.,,,显然,,,表示过程从状态,i,出发,,,经,n(n=1,2,,…,),步返回,,i,的概率,.,如果,{ ,n≥1},构成一概率分布,,,则该分布的,期,,望值,μ,i,= n,表示从状态,i,出发再返回到,i,的平均时间,.,,,,,,,,马尔可夫链,例,5.21,考虑由,0,1,2,3,四个状态组成的,Markov,链,.,其转移,,概率矩阵为,

54、,,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,个状态之间的,,关系,.,为清楚起见,,,经常

55、以,转移图,来表示,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,},和

56、,{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,,马尔可夫链,

57、,假设过程开始在状态,i,,且,i,是常返态,.,那么,,,过程将以概,,率,1,再进入,i.,但是,,,由马尔可夫链的定义,,,当它在进入,i,时,,,,该过程将又重复,.,从而状态,i,最终将再度被访问,.,,,继续重复以上推理,,,我们产生以下,结论,:,,,如果状态,i,是常返态,,,那么开始在状态,i,的过程将一再地,,进入,i,(,进入的次数事实上无穷,).,,,另一方面,,,假设状态,i,是暂态,.,此时,,,过程每次进入,i,将有,,一个正的概率,1-f,i,不再进入这个状态,.,所以,,,开始,(0,时刻,),,在状态,i,的过程恰好在状态,i,停留,n,个时间周期的概率等于

58、,,,(1-f,i,),n≥1.,,换句话说,:,,,如果状态,i,是暂态,,,那么,,,开始在状态,i,的过程处于状态,i,,,,,,,,,,马尔可夫链,的时间周期个数有一个有限均值为,1/(1-f,i,),的,几何分布,.,,定义,5.3.3,,对于常返态,i,,若,μ,i,＜,+∞,,则称,i,为,正常返态,;,,,若,μ,i,=+∞,,则称,i,为,零常返态,.,特别地,,,若,i,正常返且是,,非周期的,,,则称之为,遍历状态,.,若,i,是遍历状态且,=1,,,,则称,i,为,吸收状态,,,此时,,,显然,μ,i,=1.,,可以证明,,,对于同属一类的状态,i,j,,它们同为常返态

59、或,,暂态,;,且当它们是常返态时,,,又同为正常返态和零常返态,.,,,以下,是对上述概念和性质的总结,:,,齐次马氏链的状态分类,,,1.,称,d=d(i)=GCD{n:n≥1,p,ii,(n),＞,0},为,状态,i,的周期,.,,,(1),d,＞,1,,称,状态,i,为周期的,;,,,(2),d=1,,称,状态,i,为非周期的,.,,,,,,,,,,,,马尔可夫链,事实,.,(1),若,i,有周期,d,,则对一切非零的,n≠0(mod d),都,,有,p,ii,(n),=0,,但并非对任意,nd,,有,p,ii,(nd),＞,0;,,,(2),若,i,的周期为,d,,则存在正整数,M,

60、,对一切,n≥M,,,,有,p,ii,(nd),＞,0.,,首达概率,对,n≥1,,f,ij,(n),=P{X,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

61、;,对常返态此现象不会发生,;,,马尔可夫链,,(2),对常返态,i,,,{f,ii,(n),,,n≥1},构成一概率分布,,,该分,,布的期望值,μ,i,= nf,ii,(n),,,表示过程由,i,出发再返,,回到,i,的,平均返回时间,.,,,2.,设状态,i,为常返态,,,若,μ,i,＜∞,,,则称,常返态,i,是正常返,,的,;,若,μ,i,=∞,,则称,常返态,i,是零常返的,;,非周期的正,,常返态称为,遍历状态,.,,重要事实,.,对任意,i,j∈S,n≥1,有,p,ij,(n),= f,ij,(k),p,jj,(n-k),.,,证明,:,=P{X,n,=j|X,0,

62、=i},,= P{X,n,=j,X,v,≠j,v=1,2,,…,,k-1|X,0,=i},,= P{X,n,=j|X,k,=j,X,v,≠j,v=1,2,,…,,k-1,X,0,=i},,,·,P{X,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,方程,以及以上,事实,,,是,马

63、尔可夫链的关键性公式,,,它,,们可以把,p,ii,(n),分解成较低步的转移概率之和的形式,.,,,而且,,,通过这个事实,,,我们可以得到关于,周期的等价定,,义,: GCD{n:n≥1,p,ii,(n),＞,0}=GCD{n:n≥1,f,ii,(n),＞,0}.,,,马尔可夫链的状态,有以下,分类,:,,,暂态,,状态 零常返态,,常返态 是周期的,,正常返态,,是非周期的,--,遍历态,,,,,马尔可夫链,例,5.23,,设马尔可夫链的状态空间,S={1,2,3,4},,其一步转,,移概率矩阵,:,状态转移图,:,,P=,,,试对其状态分类,,,进

64、而确定哪些状态是常返态,,,并确定,,其周期,.,,解,:,,因为对一切,n≥1,f,44,(n),=0,,所以,f,4,= f,44,(n),=0,＜,1,,,,可见状态,4,是一个暂态,.,,,又,f,33,(1),=2/3,,且对,n≥2,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

65、 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,是正常返态,,,且为遍历态,.,,为何

66、成立,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,,n≥0},的状态空间,S={1,2,3,,,4},,其转移概率矩阵,P,的状态转移图为,:,,,试对该马尔可夫链的状态进行分类,.,,解,:,显然,,S,中的状态是互通的,.,,,因为,p,11,=1/4,,,所以,{n:p,11,(n),＞,0},的最大公约数,d=1,,,可见,,状态,1,是非周期的,.,于是,,,状态,2,3,4,也是非周期的,