《数学随机过程马尔可夫过程.pptx》由会员分享，可在线阅读，更多相关《数学随机过程马尔可夫过程.pptx（152页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 马尔可夫链马尔可夫链 马尔可夫链马尔可夫链是最简明的马尔可夫过程是最简明的马尔可夫过程,它是状态、它是状态、时时间都是离散量的马尔可夫过程间都是离散量的马尔可夫过程.马尔可夫过程马尔可夫过程是随机过程中历史最悠久且充满活力是随机过程中历史最悠久且充满活力的的一类随机过程一类随机过程.自自2020世纪初俄罗斯数学家世纪初俄罗斯数学家A.A.MapkoA.A.MapkoB B等人等人开始研究马尔可夫过程以来开始研究马尔可夫过程以来,可以说久盛不衰可以说久盛不衰.它有极它有极为为深厚的理论基础深厚的理论基础,如拓扑学、函数论、泛函分析、近世如拓扑学、函数论、泛函分析、近世代代数和几何学
2、数和几何学;又有广泛的应用空间又有广泛的应用空间,如近代物理、随机如近代物理、随机分分形形、公共事业中的服务系统公共事业中的服务系统、电子信息、计算机技术电子信息、计算机技术等等.自然界很多现象遵从这样的演变规则自然界很多现象遵从这样的演变规则:由时刻由时刻t t0 0系系统或统或过程所处的状态过程所处的状态(现在现在)可以决定系统或过程在时刻可以决定系统或过程在时刻t tt t0 0所处的状态所处的状态(将来将来),),而无需借助于而无需借助于t t0 0以前系统或过程所以前系统或过程所处处状态状态(过去过去)的历史资料的历史资料.如微分方程初值问题即属于如微分方程初值问题即属于此此.第1页
3、/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率4.14.1 马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率1.1.马尔可夫链的定义马尔可夫链的定义 设随机过程设随机过程XXn n,nT,nT的参数集的参数集T=0,1,2,T=0,1,2,X,Xn n可可能能取值的全体组成的状态空间为取值的全体组成的状态空间为I=iI=i1 1,i,i2 2,i,i3 3,.定义定义4.14.1 设有随机过程设有随机过程XXn n,nT,nT,若对于任意的整数若对于任意的整数nn T T和任意的和任意的i i0 0,i,i1 1,i,in+1n+1I,I,条件概率满足条件概率满足 PXP
4、Xn+1n+1=i=in+1n+1|X|X0 0=i=i0 0,X,X1 1=i=i1 1,X,Xn n=i=in n =PX =PXn+1n+1=i=in+1n+1|X|Xn n=i=in n (4.1)(4.1)则称则称XXn n,nT,nT为为马尔可夫链马尔可夫链,简称简称马氏链马氏链.(4.1)(4.1)是马尔可夫链的是马尔可夫链的马氏性马氏性(也称也称无后效性无后效性)的数学的数学表达表达式式.利用积事件的概率及上述定义知利用积事件的概率及上述定义知:第2页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 PX PX0 0=i=i0 0,X,X1 1=i=i1 1,X
5、,Xn n=i=in n =PX =PXn n=i=in n|X|X0 0=i=i0 0,X,X1 1=i=i1 1,X,Xn-1n-1=i=in-1n-1PXPX0 0=i=i0 0,X,X1 1=i=i1 1,X Xn-n-1 1=i=in-1n-1 =PX =PXn n=i=in n|X|Xn-1n-1=i=in-1n-1PXPX0 0=i=i0 0,X,X1 1=i=i1 1,X,Xn-1n-1=i=in-1n-1 =PX =PXn n=i=in n|X|Xn-1n-1=i=in-1n-1PXPXn-1n-1=i=in-1n-1|X|Xn-2n-2=i=in-2n-2 PXPX1 1=
6、i=i1 1|X X0 0=i=i0 0PXPX0 0=i=i0 0.即马尔可夫链的统计特性完全由条件概率即马尔可夫链的统计特性完全由条件概率 PXPXn+1n+1=i=in+1n+1|X|Xn n=i=in n 所决定所决定.如何确定这个条件概率如何确定这个条件概率,是马尔可夫链理论和是马尔可夫链理论和应应用中的重要问题之一用中的重要问题之一.第3页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率2.2.转移概率转移概率 条件概率条件概率PXPXn+1n+1=j|X=j|Xn n=i=i的直观含义是的直观含义是:系统在时刻系统在时刻n n处处于状态于状态i i的条件下的条件下
7、,在时刻在时刻n+1n+1系统处于状态系统处于状态j j的概率的概率.这相这相当于随机游动的质点在时刻当于随机游动的质点在时刻n n处于状态处于状态i i的条件下的条件下,下一下一步步转移到状态转移到状态j j的概率的概率.记此条件概率为记此条件概率为p pijij(n),(n),其严格定其严格定义义是是:定义定义4.24.2 称条件概率称条件概率 p pijij(n)=PX(n)=PXn+1n+1=j|X=j|Xn n=i=i 为马尔可夫链为马尔可夫链XXn n,nT,nT在时刻在时刻n n的的一步转移概率一步转移概率,简简称称 为为转移概率转移概率,其中其中i,jI.i,jI.一般一般,转
8、移概率转移概率p pijij(n)(n)不仅与状态不仅与状态i,ji,j有关有关,而且与时而且与时刻刻n n有关有关.当当p pijij(n)(n)不依赖时刻不依赖时刻n n时时,表示马尔可夫链具有表示马尔可夫链具有平稳平稳第4页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率转移概率转移概率.定义定义4.34.3 若对任意的若对任意的i,jI,i,jI,马尔可夫链马尔可夫链XXn n,nT,nT的的转转 移概率移概率p pijij(n)(n)与时间与时间n n无关无关,则称马尔可夫链是则称马尔可夫链是齐次齐次的的,(亦称是亦称是时齐的时齐的,即即具有平稳转移概率具有平稳转移概
9、率)并记并记p pijij(n)(n)为为p pijij.下面下面只讨论齐次马尔可夫链只讨论齐次马尔可夫链,并将并将齐次齐次两字省略两字省略.设设P P为一步转移概率为一步转移概率p pijij所组成的矩阵所组成的矩阵,状态空间状态空间I=1,2,I=1,2,则则 P=P=称为系统状态的称为系统状态的一步转移概率矩阵一步转移概率矩阵.一步转移概率矩阵具有性质一步转移概率矩阵具有性质:p11 p12 p1n p21 p22 p2n pi1 pi2 pin 第5页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 (1)(1)p pijij0,i,jI;0,i,jI;(2)(2)p
10、pijij=1,iI.=1,iI.(2)(2)式中对式中对j j求和求和,是对状态空间是对状态空间I I的所有可能状态进行的所有可能状态进行的的,此性质说明一步转移概率矩阵中任一行元素之和为此性质说明一步转移概率矩阵中任一行元素之和为1.1.通通常称满足常称满足(1)(1)、(2)(2)性质的矩阵为性质的矩阵为随机矩阵随机矩阵.为进一步讨论为进一步讨论马尔可夫链的统计性质马尔可夫链的统计性质,还须了解还须了解n n步步转转移概率移概率,初始概率初始概率和和绝对概率绝对概率的概念的概念.定义定义4.44.4 称条件概率称条件概率 p pijij(n)(n)=PX=PXm+nm+n=j|X=j|X
11、m m=i,i,jI,m0,n1=i,i,jI,m0,n1 为马尔可夫链为马尔可夫链XXn n,nT,nT的的n n步转移概率步转移概率,并称并称 P P(n)(n)=(p=(pijij(n)(n)为马尔可夫链的为马尔可夫链的n n步转移矩阵步转移矩阵,其中其中p pijij(n)(n)0,p0,pijij(n)(n)=第6页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 1,1,即即P P(n)(n)也是随机矩阵也是随机矩阵.当当n=1n=1时时,p,pijij(1)(1)=p=pijij,此时一步转移矩阵此时一步转移矩阵P P(1)(1)=P.=P.此外规此外规定定p p
12、ijij(0)(0)=(P=(P(0)(0)是单位矩阵是单位矩阵).).例例4.14.1(一维随机游动一维随机游动)设一醉汉设一醉汉Q Q(即一随机游动的质点即一随机游动的质点),),在如右上图所在如右上图所示的示的直线点集直线点集I=1,2,3,4,5I=1,2,3,4,5作随机游动作随机游动,并且仅仅在并且仅仅在1 1秒秒,2,2秒秒等时刻发生游动等时刻发生游动.游动的概率规则是游动的概率规则是:如果如果Q Q现在位于现在位于点点i(1i(1i i5),5),则下一时刻各以则下一时刻各以1/31/3的概率向左或向右的概率向左或向右移动移动一格一格,或以或以1/31/3的概率留在原处的概率留
13、在原处;如果如果Q Q现在位于点现在位于点1 1(或或5)5)上上,则下一时刻就以概率则下一时刻就以概率1 1移动到点移动到点2(2(或或4)4)上上.点点1 1与与5 5称为称为反射壁反射壁.并称上述这种游动为并称上述这种游动为带有两个反射壁的随机游带有两个反射壁的随机游动动.若以若以X Xn n表示时刻表示时刻n n时时Q Q的位置的位置,不同的位置就是不同的位置就是X Xn n的不的不同同0,ij,0,ij,1,i=j.1,i=j.12345第7页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率状态状态,则则XXn n,n=0,1,2,n=0,1,2,是一随机过程是一随机
14、过程,状态空间就状态空间就是是I,I,而且当而且当X Xn n=i,iI=i,iI为已知时为已知时,X,Xn+1n+1所处的状态的概率分布所处的状态的概率分布只只与与X Xn n=i=i有关有关,而与而与Q Q在时刻在时刻n n以前以前,如何到达如何到达i i是完全无关是完全无关的的,所以所以XXn n,n=0,1,2,n=0,1,2,是一马氏链是一马氏链,而且还是齐次的而且还是齐次的.这这一一齐次马氏链的一步转移概率和一步转移概率矩阵分别齐次马氏链的一步转移概率和一步转移概率矩阵分别为为:p pijij=PX=PXn+1n+1=j|X=j|Xn n=i=i=P=.P=.1/3,j=i-1,i
15、,i+1,11/3,j=i-1,i,i+1,1i i5,5,1,i=1,j=21,i=1,j=2或或i=5,j=4,i=5,j=4,0,|j-i|2.0,|j-i|2.1 2 3 4 51 0 1 0 0 0 2 1/3 1/3 1/3 0 0 3 0 1/3 1/3 1/3 04 0 0 1/3 1/3 1/35 0 0 0 1 0 改变游动的概率规则改变游动的概率规则,可以可以得到不同方式的随机游动和相得到不同方式的随机游动和相应的马氏链应的马氏链.如当把点如当把点1 1(及及5 5)改改为为吸吸收壁收壁,Q Q一旦到达点一旦到达点1 1(5 5),则则将永将永远留在点远留在点1 1(5)
16、5)上上.此时相应此时相应第8页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率链的链的转移概率矩阵只须在上述矩阵转移概率矩阵只须在上述矩阵P P中将第一行改为中将第一行改为(1,0,(1,0,0,0,0),0,0,0),第五行改为第五行改为(0,0,0,0,1)(0,0,0,0,1)即可即可.例例4.24.2(排队模型排队模型)设设服务系统服务系统,由一个服务员和只可能容纳两个人的等由一个服务员和只可能容纳两个人的等候候室组成室组成,见右下图见右下图.服务规则是服务规则是:先到先服务先到先服务,后来者需后来者需在在等候室依次排队等候室依次排队.假定假定一个需一个需要服务的顾客
17、到达系统时要服务的顾客到达系统时,发发现系统内已有现系统内已有3 3个顾客个顾客(一个正一个正在接受服务在接受服务,两个在等候室排两个在等候室排队队),),则该顾客即离去则该顾客即离去.设设时间间隔时间间隔tt内将有一个顾客内将有一个顾客进进入系统的概率为入系统的概率为q,q,有一原来被服务的顾客离开系统有一原来被服务的顾客离开系统(即即服服务完毕务完毕)的概率为的概率为p.p.又设又设当当tt充分小时充分小时,在这时间间隔在这时间间隔内内等候室等候室 服务台服务台系统系统离去者离去者随机随机到达到达者者第9页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率多于一个顾客进入或离
18、开系统实际上是不可能的多于一个顾客进入或离开系统实际上是不可能的.再设再设有有无顾客来到与服务是否完毕是相互独立的无顾客来到与服务是否完毕是相互独立的.如何用马氏链描述这一服务系统如何用马氏链描述这一服务系统?设设定定X Xn nX(nt),X(nt),表示时间表示时间ntnt时系统内的顾客数时系统内的顾客数,即即系统的状态系统的状态.则则XXn n,n=0,1,2,n=0,1,2,是一随机过程是一随机过程,状态空状态空间间I=0,1,2,3.I=0,1,2,3.由于当由于当X Xn n=i,iI=i,iI为已知时为已知时,X,Xn+1n+1所处的状所处的状态态的概率分布只与的概率分布只与X
19、Xn n=i=i有关有关,而与时间而与时间ntnt以前所处的状以前所处的状态态无关无关,所以该随机过程是一个齐次马氏链所以该随机过程是一个齐次马氏链.怎样计算此马氏链的一步转移概率怎样计算此马氏链的一步转移概率?记记 p p0000为为:在系统内没有顾客的条件下在系统内没有顾客的条件下,经经tt后仍无顾客后仍无顾客的的概率概率(显然显然p p0000是条件概率是条件概率,以下与此同以下与此同),p),p0000=1-q.=1-q.第10页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 p p0101为为:在系统内没有顾客的条件下在系统内没有顾客的条件下,经经tt后有一顾客后有
20、一顾客进进入系统的概率入系统的概率,p,p0101=q.=q.p p1010为为:系统内恰有一顾客正在接受服务的条件下系统内恰有一顾客正在接受服务的条件下,经经tt后系统内无人进入的概率后系统内无人进入的概率,它等于在它等于在tt间隔内顾客因间隔内顾客因服服务完毕而离去务完毕而离去,且无人进入系统的概率且无人进入系统的概率,p,p1010=p(1-q).=p(1-q).p p1111为为:系统内恰有一顾客的条件下系统内恰有一顾客的条件下,在在tt间隔内间隔内,他因他因服务完毕而离去服务完毕而离去,而另一顾客进入系统而另一顾客进入系统,或者正在接受或者正在接受服服务的顾客将继续要求服务务的顾客将
21、继续要求服务,且无人进入系统的概率且无人进入系统的概率,p,p1111=pq=pq+(1-p)(1-q).+(1-p)(1-q).p p1212为为:正在接受服务的顾客将继续要求服务正在接受服务的顾客将继续要求服务,且另一且另一顾顾客进入系统的概率客进入系统的概率,p,p1212=q(1-p).=q(1-p).p p1313为为:正在接受服务的顾客继续要求服务正在接受服务的顾客继续要求服务,且在且在tt间间隔隔第11页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率内有两个顾客进入系统的概率内有两个顾客进入系统的概率.由假设这种情况是不可由假设这种情况是不可能能发生的发生的,p
22、,p1313=0.=0.考虑到系统内有一顾客正在接受服务考虑到系统内有一顾客正在接受服务,有一顾客正在有一顾客正在排排队队,在在tt间隔内顾客因服务完毕离去间隔内顾客因服务完毕离去,但再无顾客进入但再无顾客进入;以以及系统内有一顾客正在接受服务及系统内有一顾客正在接受服务,有两顾客正在排队有两顾客正在排队,在在tt间隔内顾客因服务完毕离去间隔内顾客因服务完毕离去,但再无顾客进入的概但再无顾客进入的概率率相等相等,故有故有p p2121=p=p3232=p(1-q).=p(1-q).又系统内有两顾客又系统内有两顾客,其中一人正在接受服务其中一人正在接受服务,在在tt间间隔隔内内,他因服务完毕而离
23、去他因服务完毕而离去,而另一顾客进入系统而另一顾客进入系统,或者正或者正在在接受服务的顾客将继续要求服务接受服务的顾客将继续要求服务,且再无人进入系统的且再无人进入系统的概概率为率为:p:p2222=pq+(1-p)(1-q).=pq+(1-p)(1-q).类似地类似地,系统内有两顾客系统内有两顾客,正在接受服务的顾客将继正在接受服务的顾客将继续续第12页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率要求服务要求服务,且另一顾客进入系统的概率为且另一顾客进入系统的概率为:p:p2323=q(1-p).=q(1-p).而且而且,显然有显然有:当当|i-j|2|i-j|2时时,p
24、,pijij=0.=0.p p3333为为:系统内有三位顾客系统内有三位顾客,或者一人将离去另一人将或者一人将离去另一人将进进入系统入系统;或者无人离开的概率或者无人离开的概率,p,p3333=pq+(1-p).=pq+(1-p).于是得该马氏链的一步转移概率矩阵于是得该马氏链的一步转移概率矩阵:P=P=.在实际问题中在实际问题中,一步转移概率矩阵通常可通过统计试一步转移概率矩阵通常可通过统计试验验确定确定.下面是一实例下面是一实例.例例4.34.3 某计算机机房的一台计算机经常出故障某计算机机房的一台计算机经常出故障,研究者研究者每每0 1 2 3 (1-q)q 0 0(1-q)q 0 0
25、p(1-q)pq+(1-p)(1-q)q(1-p)0 p(1-q)pq+(1-p)(1-q)q(1-p)0 0 p(1-q)pq+(1-p)(1-q)q(1-p)0 p(1-q)pq+(1-p)(1-q)q(1-p)0 0 p(1-q)pq+(1-p)0 0 p(1-q)pq+(1-p)0 1 2 3第13页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率隔隔1515分钟观察一次计算机的运行状态分钟观察一次计算机的运行状态,收集了收集了2424小时的小时的数数据据(共做共做9797次观察次观察).).用用1 1表示正常状态表示正常状态,0,0表示不正常状表示不正常状态态,所得的
26、数据序列为所得的数据序列为:设设X Xn n为第为第n(n=1,2,n(n=1,2,97),97)次观测的计算机状态次观测的计算机状态,可以可以认认为它是一个齐次马氏链为它是一个齐次马氏链,状态空间状态空间I=0,1.96I=0,1.96次状态次状态转移转移的情况是的情况是:00,8:00,8次次;01,18;01,18次次;10,18;10,18次次;11,52;11,52次次.因此因此,一步转移概率可用频率近似地表示为一步转移概率可用频率近似地表示为:p p0000=PX=PXn+1n+1=0|X=0|Xn n=08/(8+18)=4/13,=08/(8+18)=4/13,p p0101=
27、PX=PXn+1n+1=1|X=1|Xn n=018/(8+18)=9/13,=018/(8+18)=9/13,p p1010=PX=PXn+1n+1=0|X=0|Xn n=118/(18+52)=9/35,=118/(18+52)=9/35,p p1111=PX=PXn+1n+1=1|X=1|Xn n=152/(18+52)=26/35.=152/(18+52)=26/35.11100100111111100111101111110011111111100011011011110010011111110011110111111001111111110001101101111011011010
28、111101110111101111110011011111100111.111011011010111101110111101111110011011111100111.0 10 4/13 9/131 9/35 26/35P=P=第14页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率定理定理4.14.1 设设XXn n,nT,nT是马尔可夫链是马尔可夫链,则对任意整数则对任意整数n0,n0,0 0l ln n和和i,jI,ni,jI,n步转移概率步转移概率p pijij(n)(n)具有下列性质具有下列性质:(1)(1)p pijij(n)(n)=p=pikik(l l)p
29、pkjkj(n-(n-l l);(2)(2)p pijij(n)(n)=;=;(3)(3)P P(n)(n)=PP=PP(n-1)(n-1);(4)(4)P P(n)(n)=P=Pn n.证明证明:(1)(1)利用条件概率公式及马尔可夫性利用条件概率公式及马尔可夫性,有有 p pijij(n)(n)=PX=PXm+nm+n=j|X=j|Xm m=i=i=第15页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 =PX=PXm+nm+n=j|X=j|Xm+m+l l=kPX=kPXm+m+l l=k|X=k|Xm m =i=i =p =pkjkj(n-(n-l l)(m+(m+l
30、 l)p)pikik(l l)(m)=p(m)=pikik(l l)p pkjkj(n-(n-l l).(2)(2)在在(1)(1)中中,令令l l=1,k=k=1,k=k1 1,得得 p pijij(n)(n)=;=;这是一个递推公式这是一个递推公式,递推可得递推可得 p pijij(n)(n)=.=.(3)(3)在在(1)(1)中中,令令l l=1,=1,利用矩阵乘法可证利用矩阵乘法可证.(4)(4)由由(3)(3),利用归纳法可证利用归纳法可证.定理定理4.14.1中的中的(1)(1)式式,称称切普曼切普曼-柯尔莫哥洛夫柯尔莫哥洛夫(ChapmanChapman-第16页/共152页马尔
31、可夫链的概念及转移概率马尔可夫链的概念及转移概率 Kolmogorov Kolmogorov)方程方程,这一方程一般简称为这一方程一般简称为C-KC-K方程方程,它在它在 马尔可夫链的转移概率计算中起着重要的作用马尔可夫链的转移概率计算中起着重要的作用.而而(2)(2)式说明式说明n n步转移概率完全由一步转移概率决定步转移概率完全由一步转移概率决定.(4)(4)式说式说 明齐次马尔可夫链的明齐次马尔可夫链的n n步转移概率矩阵是一步转移概步转移概率矩阵是一步转移概率率 矩阵的矩阵的n n次方次方.定义定义4.54.5 设设XXn n,nT,nT是马尔可夫链是马尔可夫链,称称 p pj j=P
32、X=PX0 0=j=j和和p pj j(n)=PX(n)=PXn n=j,jI=j,jI 为为XXn n,nT,nT的的初始概率初始概率和和绝对概率绝对概率,并分别称并分别称 ppj j,jI,jI和和ppj j(n),jI(n),jI 为为XXn n,nT,nT的的初始分布初始分布和和绝对分布绝对分布,简记为简记为 ppj j 和和ppj j(n).(n).称概率向量称概率向量P PT T(n)=(p(n)=(p1 1(n),p(n),p2 2(n),(n),)(n)(n0)0)为为n n时刻时刻的的第17页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 绝对概率向量绝对概
33、率向量,而称而称 P PT T(0)=(p(0)=(p1 1,p,p2 2,)为为初始概率向量初始概率向量.例例4.44.4(接接例例4.34.3)若计算机在前一段若计算机在前一段(15(15分钟分钟)的状态的状态为为0,0,问从本时段起问从本时段起,此计算机能连续正常工作一小时此计算机能连续正常工作一小时(4(4个个时时 段段)的概率是多少的概率是多少?解解:由题意由题意,前一时段的状态为前一时段的状态为0,0,就是初始分布就是初始分布p p0 0(0)=P(0)=PXX0 0 =0=1.=0=1.于是计算机能正常工作于是计算机能正常工作4 4个时段的概率为个时段的概率为:PX PX0 0=
34、0,X=0,X1 1=1,X=1,X2 2=1,X=1,X3 3=1,X=1,X4 4=1=1 =p =p0 0(0)p(0)p0101(1)p(1)p1111(1)p(1)p1111(1)p(1)p1111(1)(1)=0.28.=0.28.第18页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率关于关于切普曼切普曼-柯莫哥洛夫柯莫哥洛夫(ChapmanChapman-KolmogorovKolmogorov)方程方程 设设XXn n,n,nTT是一齐次马氏链是一齐次马氏链,则对任意的则对任意的i i,jIjI及及T T 中中n0,0n0,0l ln n有有 P Pijij(
35、n)(n)=P=Pikik(l l)P Pkjkj(n-(n-l l).这一方程基于这样的事实这一方程基于这样的事实:“从某时刻所处的状态从某时刻所处的状态i i(即即X X =i)=i)出发出发,经过时段经过时段n n转移到状态转移到状态j(j(即即X=j)X=j)”这一事件这一事件可分可分解成解成“从从X=iX=i出发出发,先经时段先经时段l l 转移到中间状转移到中间状k(kI),k(kI),再从再从k k经时段转经时段转n-n-l l 移到状态移到状态j j”.如下图所示如下图所示:后一阶段的状态转移与前一阶段的状后一阶段的状态转移与前一阶段的状态转移独立态转移独立,所以两个阶段的转移
36、概率所以两个阶段的转移概率是相乘的关系是相乘的关系.但经过但经过l l 步到达的状态步到达的状态k k不受任何限制不受任何限制,因而要对全部的因而要对全部的k k求和求和.toikj:l ln n-l ln n第19页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率例例4.54.5 设设XXn n,n0,n0是具有是具有3 3个状态个状态0 0,1 1,2 2的齐次马氏链的齐次马氏链,一一 步转移概率矩阵如右所示步转移概率矩阵如右所示:初始分布初始分布p pi i(0)=PX(0)=PX0 0=i=1/3,i=0,1,2.=i=1/3,i=0,1,2.试求试求(1)(1)PXP
37、X0 0=0,X=0,X2 2=1;=1;(2)(2)PX PX2 2=1.=1.解解:先求出二步转移概率矩阵先求出二步转移概率矩阵(如右下如右下):):于是有于是有 (1)(1)PXPX0 0=0,X=0,X2 2=1=1 =PX =PX0 0=0PX=0PX2 2=1|X=1|X0 0=0=0 =p =p0 0(0)p(0)p0101(2)(2)=(1/3)=(1/3)(5/16)=5/48;(5/16)=5/48;(2)(2)p p1 1(2)=PX(2)=PX2 2=1=1 =p =p0 0(0)p(0)p0101(2)+p(2)+p1 1(0)p(0)p1111(2)+p(2)+p2
38、 2(0)p(0)p2121(2)(2)=(1/3)(5/16+1/2+9/16)=11/24.=(1/3)(5/16+1/2+9/16)=11/24.0 1 2 0 0 0120 1 25/8 5/16 1/165/16 1/2 3/16 3/16 9/16 1/4P P2 2=01 2第20页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率定理定理4.24.2 设设XXn n,nT,nT为马尔可夫链为马尔可夫链,则对任意则对任意jIjI和和nn 1,1,绝对概率绝对概率p pj j(n)(n)具有下列性质具有下列性质:(1)(1)p pj j(n)=p(n)=pi ip p
39、ijij(n)(n);(2)(2)p pj j(n)=p(n)=pi i(n-1)p(n-1)pij ij;(3)(3)P PT T(n)=P(n)=PT T(0)P(0)P(n)(n);(4)(4)P PT T(n)=P(n)=PT T(n-1)P.(n-1)P.证明证明:(1)(1)p pj j(n)=PX(n)=PXn n=j=PX=j=PX0 0=i,X=i,Xn n=j=j =PX =PX0 0=i,X=i,Xn n=j|X=j|X0 0=iPX=iPX0 0=i=i=p pi ip pijij(n)(n).(2)(2)p pj j(n)=PX(n)=PXn n=j=PX=j=PXn
40、 n=j,X=j,Xn-1n-1=i=i 第21页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 =PX =PXn n=j|X=j|Xn-1n-1=iPX=iPXn-1n-1=i=i =p =pi i(n-1)p(n-1)pijij.(3)(3)与与(4)(4)式是式是(1)(1)与与(2)(2)式的矩阵形式式的矩阵形式,显然成立显然成立.定理定理4.34.3 设设XXn n,nT,nT为马尔可夫链为马尔可夫链,则对任意则对任意i i1 1,i,in n I I和和n1,n1,有有 PXPX1 1=i=i1 1,X,Xn n=i=in n=.=.证明证明:由条件概率公式及马氏
41、性由条件概率公式及马氏性,有有 PXPX1 1=i=i1 1,X,Xn n=i=in n=P X=P X0 0=i,X=i,X1 1=i=i1 1,X,Xn n=i=in n =PX =PX0 0=i,X=i,X1 1=i=i1 1,X,Xn n=i=in n=PXPX0 0=iPX=iPX1 1=i=i1 1|X X0 0=i=iPXPXn n=i=in n|X|X0 0=i,X=i,X1 1=i=i1 1,X,Xn-1n-1=i=in-1n-1 第22页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率 =PX=PX0 0=iPX=iPX1 1=i=i1 1|X|X0 0=i
42、=iPXPXn n=i=in n|X|Xn-n-1 1=i=in-1n-1 =.=.定理定理4.24.2表明表明,绝对概率绝对概率p pj j(n)(n)也具有类似于也具有类似于n n步转移步转移概概 率的性质率的性质.定理定理4.34.3则进一步说明则进一步说明,马尔可夫链的有马尔可夫链的有限维限维 分布完全由它的初始概率和一步转移概率所决定分布完全由它的初始概率和一步转移概率所决定.因因此此 只要知道初始概率和一步转移概率只要知道初始概率和一步转移概率,就可以描述马尔就可以描述马尔可可 夫链的统计特性夫链的统计特性.3.3.马尔可夫链的应用举例马尔可夫链的应用举例 在讨论马尔可夫链的应用之
43、前在讨论马尔可夫链的应用之前,再对再对定理定理4.34.3的马的马尔可尔可夫过程的概率意义夫过程的概率意义,做一必要的说明做一必要的说明.第23页/共152页马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率对于对于齐次马尔可夫链齐次马尔可夫链XXn n,nT,nT,其其有限维分布函数有限维分布函数由由它的它的初始分布初始分布和和一步转移概率一步转移概率惟一确定惟一确定.因为因为:PX PX1 1=i=i1 1,X,X2 2=i=i2 2,X,Xn n=i=in n =P X=P X0 0=i=i0 0,X,X1 1=i=i1 1,X,X2 2=i=i2 2,X,Xn n=i=in n =P
44、X=PX0 0=i=i0 0,X,X1 1=i=i1 1,X,X2 2=i=i2 2,X,Xn n=i=in n =PX=PX0 0=i=i0 0PXPX1 1=i=i1 1|X|X0 0=i=i0 0 PXPXn n=i=in n|X|X0 0=i=i0 0,X Xn-1n-1=i=in-1n-1 =PX=PX0 0=i=i0 0PXPX1 1=i=i1 1|X|X0 0=i=i0 0 PXPXn n=i=in n|X|Xn-1n-1=i=in-1n-1 =.=.反之反之,若一个随机变量序列若一个随机变量序列XXn n,nT,nT的有限维分布由的有限维分布由上上式给出式给出,其中其中ppi
45、i,iI,iI为一概率分布为一概率分布,p,pijij为转移概率为转移概率,则则XXn n,nT,nT是一马尔可夫链是一马尔可夫链(即具有马尔可夫性即具有马尔可夫性),(p),(pijij)是是其转移概率矩阵其转移概率矩阵,p,pi i 是其初始分布是其初始分布.第24页/共152页马尔可夫链的应用举例马尔可夫链的应用举例例例4.64.6(无限制随机游动无限制随机游动)设质点在数轴上移动设质点在数轴上移动,每次移动一格每次移动一格,向右移动的概向右移动的概率率为为p,p,向左移动的概率向左移动的概率q=1-p(q=1-p(这种运动称无限制随机游这种运动称无限制随机游动动).).以以X Xn n
46、表示时刻表示时刻n n质点所处的位置质点所处的位置,则则XXn n,nT,nT是一个齐是一个齐次次马尔可夫链马尔可夫链.试写出试写出XXn n,nT,nT的一步和的一步和k k步转移概率步转移概率.解解:XXn n,nT,nT的状态空间的状态空间I=0,1,2,I=0,1,2,其一步其一步转移转移 概率矩阵为概率矩阵为:设在设在第第k k步步转移中向右移了转移中向右移了x x 步步,向左移了向左移了y y步步,且经过且经过k k步步转转 移状态从移状态从i i进入进入j,j,则则 ,从而从而x=,y=.x=,y=.由于由于x,yx,y只能只能P=P=q 0 p 0 q 0 p 0 0 q 0
47、p 0 q 0 p x+y=kx+y=kx-y=j-ix-y=j-i第25页/共152页马尔可夫链的应用举例马尔可夫链的应用举例 取整数取整数,所以所以k(j-i)k(j-i)必为偶数必为偶数.考虑到在考虑到在k k步步中哪中哪x x步步 向右向右,哪哪y y步向左是任意的步向左是任意的,选取的方法有选取的方法有 种种,故有故有 p pijij(k)(k)=.=.例例4.74.7(赌徒输光问题赌徒输光问题)两赌徒甲、乙进行一两赌徒甲、乙进行一系列赌博系列赌博.赌徒甲有赌徒甲有a a元元,赌徒乙赌徒乙有有 b b元元,每赌一局输者给赢者每赌一局输者给赢者1 1元元,没有和局没有和局,直到两人直到
48、两人中有中有 一人输光为止一人输光为止.设在每一局中设在每一局中,甲赢的概率为甲赢的概率为p,p,输输的概的概 率为率为q=1-p,q=1-p,求甲输光的概率求甲输光的概率.解解:与与例例4.14.1带有两个反射壁的一维随机游动带有两个反射壁的一维随机游动相比相比,这个这个 问题实质上是问题实质上是带有两个吸收壁的随机游动带有两个吸收壁的随机游动,其状态空其状态空间间 I=0,1,2,I=0,1,2,c(c=a+b).c(c=a+b).所以问题是要求质点从所以问题是要求质点从a a点出点出 p px xq qy y,k+(j-i),k+(j-i)为偶数为偶数 0,k+(j-i)0,k+(j-i
49、)为奇数为奇数第26页/共152页马尔可夫链的应用举例马尔可夫链的应用举例 发到达发到达0 0状态状态先于先于到达到达c c状态的概率状态的概率.解解:设设u ui i表示甲从状态表示甲从状态i i出发转移到状态出发转移到状态0 0的概率的概率,我们我们的的 任务是计算任务是计算u ua a.由于由于0 0和和c c是是 吸收状态吸收状态,故故u u0 0=1,u=1,uc c=0.=0.由由 条件概率公式条件概率公式:u ui i=pu=pui+1i+1+qu+qui-1i-1,i=1,2i=1,2,c-1c-1.(此式的此式的含含 义是义是:甲从有甲从有a a元开始赌博到输光的概率等于元开
50、始赌博到输光的概率等于“他接他接下去下去 赢了一局赢了一局(概率为概率为p),p),处于状态处于状态i+1i+1后再输光后再输光”;和和“他接他接 下去输了一局下去输了一局(概率为概率为q),q),处于状态处于状态i-1i-1后再输光后再输光”这两这两 个事件的和事件的概率个事件的和事件的概率.)由于由于p+q=1,p+q=1,所以所以u ui i=pu=pui+1i+1+qu+qui-1i-1,i=1,2,i=1,2,c-1,c-1实质实质上上 是一个差分方程是一个差分方程:u ui+1i+1-u-ui i=r(u=r(ui i-u-ui-1i-1),i=1,2,),i=1,2,c-1.,c