随机过程第四章.

第四章马尔可夫(Markov)链4.1马尔可夫链与转移概率一、基本概念定义4.0设{X(t)，tT}为随机过程，若对任意正整数n及t1t2tn，P{X(t1)=x1,,X(tn-1)=xn-1}0，且条件分布P{X(tn)xn|X(t1)=x1,,X(tn-1)=xn-1}=P{X(tn)xn|X(tn-1)=xn-1}，则称{X(t)，tT}为马尔可夫过程。4.1马尔可夫链与转移概率★若t1,t2,,tn-2表示过去，tn-1表示现在，tn表示将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与过去状态无关。过去现在将来4.1马尔可夫链与转移概率马尔可夫过程通常分为三类：(1)时间、状态都是离散的，称为马尔可夫链(2)时间连续、状态离散的，称为连续时间马尔可夫链(3)时间、状态都是连续的，称为马尔可夫过程4.1马尔可夫链与转移概率对时间、状态都是离散的随机过程{Xn，nT}，记参数集T={0,1,2,}，状态空间I={0,1,2,}I54321012345T4.1马尔可夫链与转移概率对时间、状态都是离散的随机过程{Xn，nT}，记参数集T={0,1,2,},状态空间I={0,1,2,}定义4.1：若随机过程{Xn，nT}，对任意nT和i0,i1,,in+1I，条件概率P{Xn+1=in+1|X0=i0,X1=i1,,Xn=in}=P{Xn+1=in+1|Xn=in}，则称{Xn，nT}为马尔可夫链，简称马氏链。4.1马尔可夫链与转移概率定义4.2：称条件概率pij(n)=P{Xn+1=j|Xn=i}为马尔可夫链{Xn，nT}在时刻n的一步转移概率，简称转移概率，其中i,jI。Ijinn＋1T4.1马尔可夫链与转移概率定义4.3：若对任意的i,jI，马尔可夫链{Xn,nT}的转移概率pij(n)与n无关，则称马尔可夫链是齐次的，并记pij(n)为pij。I54321012345Tp11P=4.1马尔可夫链与转移概率齐次马尔可夫链具有平稳转移概率，状态空间设为I={1,2,3,}，一步转移概率矩阵为★转移概率满足(2)p21pm1p1np2npmnp12p22pm2(1)pij0,i,jIP称为随机矩阵ijpjI=1,iI=(p=n步转移矩阵4.1马尔可夫链与转移概率(n)ij为马尔可夫链{Xn，nT}的n步转移概率(i,jI,m0,n1)。)(n)(n)ijP((其中pijn)0,pijn)=1,i,jIjIP(n)也为随机矩阵当n=1时,pij(1)=pij,P(1)=P0,ij1,i=j(0)ij当n=0时，规定pp(0)=(p1,p2,)p(n)=(p1(n),p2(n),)4.1马尔可夫链与转移概率定义4.5：初始概率绝对概率初始分布绝对分布初始概率向量绝对概率向量pj=P{X0=j}pj(n)=P{Xn=j}{pj,jI}{pj(n),jI}TT4.1马尔可夫链与转移概率二、基本性质命题：P{X0=i0,X1=i1,,Xn=in}=P{Xn=in|X0=i0,X1=i1,,Xn-1=in-1}P{X0=i0,X1=i1,,Xn-1=in-1}=P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|X0=i0,X1=i1,,Xn-2=in-2}P{X0=i0,X1=i1,,Xn-2=in-2}=P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|Xn-2=in-2}P{X0=i0,X1=i1,,Xn-2=in-2}4.1马尔可夫链与转移概率==P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|Xn-2=in-2}P{X1=i1|X0=i0}P{X0=i0}★马尔可夫链的统计特性完全由条件概率P{Xn+1=in+1|Xn=in}确定。=pp(1)pp=(2)p4.1马尔可夫链与转移概率定理4.1设{Xn，nT}为马尔可夫链，则对任意整数n0,0ln和i,jI，n步(n)(n)(l)(nl)pkn1jpk1k2ijikkjkI(n)ijik1k1Ikn1I(3)P(n)=PP(n-1)(4)P(n)=Pn{+=nmXP{}+==nmmjXiXP,}===miXj|p{}=miXP=4.1马尔可夫链与转移概率证明：(1)kIkIkIij(n)=pkj(nl)(m+l)pik(l)(m)=pik(l)pkj(nl)P{Xm=i,Xm+l=k,Xm+n=j}P{Xm=i,Xm+l=k}kIP{Xm=i,Xm+l=k}P{Xm=i}=P{Xm+n=j|Xm+l=k}P{Xm+l=k|Xm=i}pp4.1马尔可夫链与转移概率(3)矩阵乘法(4)由(3)推出说明：(1)此为C-K方程(切普曼-柯尔莫哥洛夫)(2)n步转移概率由一步转移概率确定，n步转移概率矩阵由一步转移概率矩阵确定(n次幂)=kI(2)在(1)中令l=1,k=k1,得p由此可递推出公式(n)ij(n1)k1j(1)ik1(1)pj(n)=pp(2)p(n)=p(n1)p4.1马尔可夫链与转移概率定理4.2设{Xn，nT}为马尔可夫链，则对任意整数jI和n1，绝对概率pj(n)满足(3)PT(n)=PT(0)P(n)(4)PT(n)=PT(n-1)Piij(n)iIiIijji=ipp4.1马尔可夫链与转移概率证明：(1)iIijiIiI(n)=P{Xn=j|X0=i}P{X0=i}pj(n)=P{Xn=j}=P{X0=i,Xn=j}4.1马尔可夫链与转移概率(2)(3)(4)为(1)(2)的矩阵表示。iIiIiI=pi(n1)pij=P{Xn=j|Xn1=i}P{Xn1=i}pj(n)=P{Xn=j}=P{Xn1=i,Xn=j}P{Xn=in|Xn1=in1}P{X2=i2|X1=i1}=pipii1pi1i2pin1iniI4.1马尔可夫链与转移概率定理4.3设{Xn，nT}为马尔可夫链，则对任意整数i1,i2,,inI和n1有P{X1=i1,,Xn=in}=pipii1pi1i2pin1iniI11nn=P{X0=i,X1=i1,,Xn=in}iI=P{X0=i}P{X1=i1|X0=i}iI4.1马尔可夫链与转移概率三、应用举例例4.1无限制随机游动qp0-1i-1i1i+1一步转移概率:pi,i+1=ppi,i1=q=1ppii=0xy=jix=y=k(ji)Ckxpxqy,k+(ji)为偶数=4.1马尔可夫链与转移概率k步转移概率:i经过k步进入j,向右移了x步,向左移了y步则20，k+(ji)为奇数k+(ji)2x+y=kpij(k)4.1马尔可夫链与转移概率例4.2赌徒输光问题甲有赌资a元，乙有赌资b元，赌一局输者给赢者1元，无和局。甲赢的概率为p，乙赢的概率为q=1-p，求甲输光的概率。解：状态空间I={0,1,2,,c}，c=a+bqpa-1aa+10a+b4.1马尔可夫链与转移概率设ui表示甲从状态i出发转移到状态0的概率，求ua。显然u0=1，uc=0(u0表示已知甲输光情形下甲输光的概率，uc表示已知乙输光情形下甲输光的概率)ui=pui+1+qui-1(i=1,2,,c-1)（甲在状态i下输光：甲赢一局后输光或甲输一局后输光）,c1i=1,2,qp(uiui1)ui+1ui=4.1马尔可夫链与转移概率(p+q)ui=pui+1+qui1p(ui+1ui)=q(uiui1)12(1)=u1u0=ˆqpui+1ui=uiui1=ui1ui2==1,即p=q=acicaa+bba+b=,同理可得ub=ua=11cui=1+i=1uc=1+c=0=4.1马尔可夫链与转移概率(ui+1ui)+(uiui1)+(ui1ui2)++(u1u0)=(i+1)即ui+1u0=(i+1)ui+1=u0+(i+1)=1+(i+1)4.1马尔可夫链与转移概率qpqp=rrkrc1r(2)=(u11)ui+1ui=r(uiui1)c1c1i=ki=k1,即pq,设rr1r1rrrrr4.1马尔可夫链与转移概率ccc===b1rcb1rrkrccrarc1rcrkrc1rrarc1rub=(u11)uk=(u11)ua=(u11)01r令k=0,则ucu0=(u11)1r从而u11=c4.1马尔可夫链与转移概率例4.3天气预报问题RR表示连续两天有雨，记为状态0NR表示第1天无雨第2天有雨，记为状态1RN表示第1天有雨第2天无雨，记为状态2NN表示连续两天无雨，记为状态3p00=P{R今R明|R昨R今}=P{R明|R昨R今}=0.7p01=P{N今R明|R昨R今}=0p02=P{R今N明|R昨R今}=P{N明|R昨R今}=0.3p03=P{N今N明|R昨R今}=0p00P=p030.7=00.60.84.1马尔可夫链与转移概率类似地得到其他转移概率，于是转移概率矩阵为若星期一、星期二均下雨，求星期四下雨的概率000.30.500000.40.2p130.5p23p330p10p20p30p02p12p22p32p01p11p21p31p=p00+p01=P=0.120.200.480.160.100.644.1马尔可夫链与转移概率2步转移概率矩阵为0.120.210.180.200.150.300.4920.350.200.10(2)P一二三四RRRR00RRNR01星期四下雨的情形如右，星期四下雨的概率(2)(2)=0.49+0.12=0.61状态转移图12状态转移矩阵130P=1000104.1马尔可夫链与转移概率例4.4具有吸收壁和反射壁的随机游动状态空间{1,2,3,4}，1为吸收壁，4为反射壁1133113334313131313113113d=G.C.D{np:ii4.2马尔可夫链的状态分类一、状态的分类定义4.6状态i的周期d0}(最大公约数greatestcommondivisor)如果d1，就称i为周期的，如果d=1，就称i为非周期的(n)94.2马尔可夫链的状态分类例4.6设马尔可夫链的状态空间I={1,2,,9}，转移概率如下图从状态1出发再返回状态1的可能步数为T={4,6,8,10,}，T的最大公约数为2，从而状态1的周期为285721342331111161111当n0时，pii0(nd)4.2马尔可夫链的状态分类★注：(1)如果i有周期d，则对一切非零的(n)（若p(iin)0，则n=0modd）(nd)(nd)(2)114.2马尔可夫链的状态分类例4.7状态空间I={1,2,3,4}，转移概率如图，状态2和状态3有相同的周期d=2，但状态2和状态3有显著的区别。当状态2转移到状态3后，再不能返回到状态2，状态3总能返回到状态3。这就要引入常返性概念。234112121fij4.2马尔可夫链的状态分类由i出发经n步首次到达j的概率(首达概率)=P{Xm+vj,1vn1,Xm+n=j|Xm=i}(n)n1(0)由i出发经有限步终于到达j的概率n=1{}=)()(1,,1nnnffiiii表=)(ninf示由i出发再返回到i的平均返回时间4.2马尔可夫链的状态分类定义4.7若fii=1，称状态i为常返的；若fii1，称状态i为非常返的。★注：i为非常返，则以概率1-fii不返回到I；n=1构成一概率分布，期望值iii为常返，则n=14.2马尔可夫链的状态分类若i，则称常返态i为