马尔可夫链的概念及转移概率.doc

第四章4.1 马尔可夫链的的概念及转移概率一、知识回顾二、马尔可夫链的的定义三、转移概率四、马尔可夫链的一些简单例子五、总结一、知识回顾1. 条件概率定义：设A，B为两个事件，且P(A)0，称PBA=P(AB)P(A)为事件A发生条件下B事件发生的条件概率。将条件概率公式移项即得到所谓的乘法公式：PAB=P(A)P(B|A)2.全概率公式设试验E的样本空间为S，A为E的事件，若B1,B2，Bn为S的一个完备事件组，既满足条件：1). B1,B2，Bn两两互不相容，即BiBj=，ij,i,j=1,2,n2). B1B2Bn=S，且有PBi0,i=1,2,n，则 PA=i=1nPBiPA|Bi 此式称为全概率公式。 3.矩阵乘法矩阵乘法的定义A=a11a12a13a21a22a23，B=b11b12b21b22b31b32C=c11c12c21c22如果c11=a11b11+a12b21+a13b31c12=a11b12+a12b22+a13b32c21=a21b11+a22b21+a23b31c22=a21b12+a22b22+a23b32那么矩阵C叫做矩阵A和B的乘积，记作C=AB4.马尔可夫过程的分类马尔可夫过程按其状态和时间参数是连续的或离散的，可分为三类：（1） 时间、状态都是离散的马尔科夫过程，称为马尔可夫链；（2） 时间连续、状态离散的马尔科夫过程称为连续时间的马尔可夫链的；（3） 时间、状态都连续的马尔科夫过程。二、马尔科夫链的定义定义4.1 设有随机过程Xn,nT，若对于任意的整数nT和任意的i0,i1,in+1I，条件概率都满足PXn+1=in+1|X0=i0,X1=i1,Xn=in=PXn+1=in+1|Xn=in (4.1.1) 则称Xn,nT为马尔科夫链，简称马氏链。 式(4.1.1)即为马氏链，他表明在状态X(0)=i0,X(1)=i1,X(n)=in已知的条件下，X(n+1)=j的条件概率与X(0)=i0,X(1)=i1,X(n-1)=in-1无关，而仅与X(n)所处的状态in有关。式(4.1.1)是马尔科夫链的马氏性（或无后效性）的数学表达式。由定义知 PX0=i0,X1=i1,Xn=in=PXn=inX0=i0,X1=i1,Xn-1=in-1 PX0=i0,X1=i1,Xn-1=in-1=PXn=inXn-1=in-1 PX0=i0,X1=i1,Xn-1=in-1=PX1=i1X0=i0PX0=i0可见，马尔科夫链的统计特性完全由条件概率PXn+1=in+1|Xn=in所决定。如何确定这个条件概率，是马尔科夫链理论和应用中的重要问题之一。现举一例说明上述概念： 例4.1.1 箱中装有c个白球和d个黑球，每次从箱子中任取一球，抽出的球要到从箱子中再抽出一球后才放回箱中，每抽出一球作为一次取样试验。 现引进随机变量序列为Xn,n=1,2,每次取样试验的所有可能结果只有两个，即白球或黑球。若以数a1代表白球，以数a2代表黑球则有 Xn=a1，第n次抽球结果为白球a2，第n次抽球结果为黑球由上所述的抽球规则可知，任意第n次抽到黑球或白球的概率只与第n-1次抽得球的结果有关，而与第n-2次，第n-3次，第1次，抽的球的结果无关，由此可知上述随机变量序列Xn,n=1,2,为马氏链。三、转移概率定义4.2 称条件概率pijn=PXn+1=j|Xn=i为马尔科夫链Xn,nT在时刻N的一步转移概率，其中i,jT，简称为转移概率。条件概率pijn：随机游动的质点在时刻n处于状态i的条件下，下一步转移到状态j的你改率。一般地，转移概率pijn不仅与状态i，j有关，而且与时刻n有关。当pijn不依赖与时刻n时，表示马尔科夫链具有平稳转移概率。定义4.3 若对任意的i,jT，马尔科夫链Xn,nT的转移概率pijn与n无关则称马尔科夫链是齐次的，并记pijn为pij。下面我们只讨论齐次马尔科夫链通常将“齐次”两个字省略。设P表示一步转移概率pij所组成的矩阵，且状态空间I=1,2,，则P=p11p12p21p22 p1np2n称为系统状态的一步转移概率矩阵。它具有性质：(1) pij0，i，jI；(2) jTpij=1，iI.(2)式中对j求和是对状态空间I的所有可能状态进行的，此性质说明一步转移概率矩阵中任一行元素之和为1.通常称满足上述（1）、（2）性质的矩阵为随机矩阵。定义4.4 称条件概率pij(n)=PXm+n=jXm=i, i,jI, m0, n1为马尔科夫链Xn,nT的n步转移概率，并称P(n)=(pij(n)为马尔科夫链的n步转移矩阵，其中pijn0，jTpijn=1，即P(n)也是随机矩阵。当n=1是，pij(1)=pij，此时一步转移矩阵P(1)=P. 此外我们规定pij0=0，ij，1，i=j.定理4.1 设Xn,nT为马尔科夫链，则对任意整数n0，0ln和i,jT，n步转移概率pij(n)具有下列性质：(1) pij(n)=kIpiklpkjn-l;(2) pij(n)=k1Ikn-1Ipik1pk1k2pkn-1j;(3) P(n)=PP(n-1);(4) P(n)=Pn.证 (1)利用全概率公式及马尔科夫性，有pij(n)=PXm+n=j|Xm=i=PXm=i,Xm+n=jPXm=i=kIPXm=i,Xm+l=k,Xm+n=jPXm=i,Xm+l=kPXm+l=k|Xm=i=kIpkjn-lpikl(m)=kIpiklpkjn-l(2)在(1)中令l=1,k=k1得pij(n)=kIpik1pk1jn-l;这是一个递推公式，故可递推得到pij(n)=k1Ikn-1Ipik1pk1k2pkn-1j;(3)在(1)中令l=1,利用矩阵乘法可证。(4)由(3)，利用归纳法可证。定理4.1中(1)式称为切普曼柯尔莫哥洛夫方程，简称C-K方程。它在马尔科夫链的转移概率的计算中起着重要的作用。(2)式说明n步转移概率完全由一步转移概率决定。(4)式说明齐次马尔科夫链的n步转移概率矩阵是一步转移概率矩阵的n次乘方。定义4.5 设Xn,nT为马尔科夫链，称pj=PX0=j和pjn=pXn=j，(jI)为Xn,nT的初始概率和绝对概率，并分别成pj,jI和pj(n),jI为Xn,nT的初始分布和绝对分布，简记为pj和pjn。称概率向量PTn=(p1n，p2n，)为n时刻的绝对概率向量，而称PT0=(p1，p2，)为初始概率 定理4.2 设Xn,nT为马尔科夫链，则对任意jI和n1，绝对概率pj(n)具有下列性质：（1）pjn=iIpipij(n)；（2）pjn=iIpi(n-1)pij；（3）PTn=PT(0)P(n)；（4）PTn=PT(n-1)P.证 (1) pjn=PXn=j=iIPX0=i, Xn=j =iIPXn=j|X0=iPX0=i=iIpipij(n)(2)pjn=PXn=j=iIPXn=j, Xn-1=i =iIPXn=j| Xn-1=iPXn-1=i =iIpi(n-1)pij (3)与(4)中式是(1)与(2)中式的矩阵乘积形式，显然成立。证毕。 定理4.3 设Xn,nT为马尔科夫链，则对任意i1,inI和n1，有PX1=i1,Xn=in=iIpipii1pin-1in证由全概率公式及马氏性质有PX1=i1,Xn=in=PiIX0=i, X1=i1,Xn=in=iIPX0=i, X1=i1,Xn=in=iIPX0=iPX1=i1X0=iPXn=in|X0=i, ,Xn-1=in-1 =iIPX0=iPX1=i1X0=iPXn=in|Xn-1=in-1 =iIpipii1pin-1in证毕一、 马尔可夫链的的一些简单例子马尔科夫链在研究质点的随机运动、自动控制、通信技术、生物工程、经济管理等领域中有着广泛的应用。例4.1 无限制随机游动设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动的概率为q=1-p，这种运动称为无限制随机游动。以Xn表示时刻n质点所处的位置，则Xn,nT是一个齐次马尔科夫链，试写出它的一步和k步转移概率。解 显然Xn,nT的状态空间I=0,1,2,，其一步转移概率矩阵为P=q 0p 00 q0 p设在第k不转移中向右移了x步，向左移了y步，且经过k步转移状态从i进入j，则x+y=k，x-y=j-i，从而x=k+(j-i)2，y=k-(j-i)2.由于x，y都只能取整数，所以k(j-i)必须是偶数。又在k步中哪x步向右，哪y步向左是任意的，选取的方法有ckx种。于是pij(k)=ckxpxqy，k+j-i为偶数0，k+j-i为奇数。例4.2 赌徒输光问题两赌徒甲、乙一系列赌博。赌徒甲有a元。赌徒乙有b元，每赌一局输者给赢者1元，没有和局，直到两人中有一个输光为止。设在每一局中，甲赢的概率为p，输的概率为q=1-p，求甲输光的概率。这个实质上是带有两个吸收壁的随机游动，其状态空间I=0,1,2,c，c=a+b.故现在的问题是求质点从a点出发到达0状态先于到达c状态的概率.解 设ui表示甲从状态i出发转移到状态0的概率，我们要计算的就是ua。由于0和c是吸收状态，故u0=1，uc=0.由全概率公式ui=pui+1+qui-1，i=1,2,c-1. （3.1）上式的含义是，甲从有i元开始赌到输光的概率等于“他接下去赢了一局（概率为p），处于状态i+1后再输光”；和“他接下去输了一局（概率为q），处于状态i-1后再输光”这两个事件的和事件的概率。由于p+q=1,（3.1）式实质上是一个差分方程ui+1-ui=rui-ui-1，i=1,2,c-1， （3.2）其中r=qp，其边界条件为u0=1，uc=0. （3.3）先讨论r=1，即p=q=12的情况，此时（3.2）为ui+1-ui=ui-ui-1，令i=1,2,c-1，u1=u0+a，得u2=u1+a=u0+2a，ui=ui-1+a=u0+ia，uc=uc-1+a=u0+ca.将u0=1，uc=0代入最后一式，得参数a=-1c，所以ui=1-ic，i=1,2,c-1.令i=a，求得甲输光的概率为ui=1-ac=ba+b.上述结果表明，在p=q情况下（即甲、乙每局比赛中输赢是等可能的情况下），甲输光的概率与乙的赌本b成正比，即赌本小者输光的可能性大。由于甲、乙的地位是对称的，故乙输光的概率为ub=aa+b.由于ua+ub=1，表明甲、乙中必有一人要输光，赌博迟早要结束。再讨论r1，即pq的情况。由（3.2）式得uc-uk=i=kc-1r(ui-ui-1)=i=kc-1riu1-u0 =u1-1rk-rc1-r. （4.14） 令k=0，由于uc=0，有1=1-u11-rc1-r即 1-u1=1-r1-rc代入（3.4）式，得ua=rk-rc1-rc，k=1,2,c-1.令k=a，的甲输光的概率ua=ra-rc1-rc由对称性，乙输光的概率为(r1=p/q)ub=r1b-r1c1-r1c由于ua+ub=1，因此在r1时，即pq时两个人中也总有一个人要输光的。例4.3 天气预报有问题设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨，今日有雨，明日有雨的概率为0.5；昨日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为0.2.若星期一、星期二均下雨，求星期四下雨的概率。解 设昨日，今日连续两天有雨称为状态0(RR)；昨日无雨，今日有雨称为状态1(NR)；昨日有雨，今日无雨称为状态2(RN)；昨日，今日无雨称为状态3(NN)；。由于天气预报模型可看作一个四状态的马尔可夫链，其转移概率为p00=PR今R明R昨R今=P连续三天有雨=PR明R昨R今=0.7，p01=PN今R明R昨R今=0(不可能事件)，p02=PR今N明R昨R今=PN明R昨R今=1-0.7=0.3，p03=PN今N明R昨R今=0(不可能事件)，其中R代表有雨，N代表无雨。类似的可以得到所有状态的一步转移概率。于是它的一步转移概率矩阵为P=p00p01p10p11p02p03p12p13p20p21p30p31p22p23p32p33=0.700.500.300.5000.400.200.600.8其两步转移概率矩阵为:P(2)=PP=0.700.500.300.5000.400.200.600.80.700.500.300.5000.400.200.600.8=0.490.120.350.200.210.180.150.300.200.120.100.160.200.480.100.64由于星期四下雨意味着过程所处的状态为0或1，因此星期一，星期二连续下雨，星期四又下雨的概率为P=p00(2)+p01(2)=0.49+0.12=0.61例4.4 设质点在线段1,4上作随机游动，假设它只能在时刻nT发生移动，且只能停留在1,2,3,4点上。当质点转移到2,3点时，它以13的概率向左或向右移动一格，或停留在原处。当质点移动到点1时，它以概率1停留在原处。当质点移动到点4时，它以概率1移动到点3。若以Xn表示质点在时刻n所处的位置，则Xn,nT是一个齐次马尔科夫链，其转移概率矩阵为P=101313 0013001300 131310各状态之间的转移关系及相应的转移概率如图所示。例中的点1称为吸收壁，即质点一旦到达这种状态后就被吸收住了，不再移动；点4称为反射壁，即质点一旦到达这种状态后，必然被反射出去。例4.5 生灭链。观察某种生物群体，以Xn表示在时刻n群体的数目，设为i个数量单位，如在时刻n+1增生到i+1个数量单位的概率为bi，减灭到i-1个数量单位的概率为ai，保持不变的概率为ri=1-(ai+bi)，则Xn,n0为齐次马尔科夫链，I=0,1,2,，其转移概率为pij=bi，j=i+1，ri，i=j，ai，j=i-1.(a0=0)，称此马尔科夫链为生灭链。总结