第三章 马尔可夫链

#第三章马尔可夫链一、马尔可夫链的概念马尔可夫过程是一类有重要应用意义的随机过程，它具有如下特征：随机过程‘将来'所处的状态仅与‘现在'所处的状态有关，而与‘过去'曾处于什么状态无关。马尔可夫过程按其状态和时间参数是离散还是连续的可以分成三类（1）时间和状态都是离散的马尔可夫过程，称为马尔可夫链。（2）时间连续、状态离散的马尔可夫过程，称为连续时间的马尔可夫链。（3）时间和状态都连续的马尔可夫过程。本章介绍马尔可夫链定义1设｛X,n>0｝为随机序列，其状态空间为I二｛i,i,i，…｝，如果对任意正n012整数n及任意n+2个状态i,i,i，…,ieI，有012n+1P{X=iX=i,X=i，…，X=i}n+1n+10011nn=P{X=i|X=i}n+1n+1nn则称此随机序列｛X,n>0｝为马尔可夫链。n若将时刻n称为‘现在'，将时刻n+1称为‘将来'，而把0，1，2，……，n-1称为‘过去'。定义中的等式便可通俗解释为：在已知｛X,n>0｝‘现在'所n处的状态条件下，‘将来'所要达到的状态与‘过去'所经历的状态无关，这一特性常称为马尔可夫的无后效性。例1.一个n级数字传输系统，每一级的输入和输出信号只取0或1两个值，每一级的输出是下一级的输入；并假定当一级输入为0时，其输出为0和为1的概率分别为P和1-P；当输入为1时，其输出为1和0的概率分别为P和1-P（见图）

令Xn表示第n级输出，贝叽Xn,n$O｝便为一个马尔可夫链。例2.从1,2,……,N数字中任取一个数，记为X0；再从1,2,……,X0数字中任取一个数，记为XI；再从1,2,……,X1中任取一个数，记为X2；依此类推，在1,2,,Xn-1中任取一个数，记为Xn。可以证明｛Xn,n$O｝为马尔可夫链。事实上，｛Xn,n$O｝的状态空间为I=｛1,2,……,N｝，对任意正整数n,取n+1个状态i,i,i，…,ieI,由题意可知012nH当4＞也时=玖见=订兀_1=—｝故｛Xn,n$O｝为马尔可夫链。二、转移概率由马尔可夫链的无后效性和乘法公式有P｛X二i,X二i，…，X二i｝0011nn=P{X=i|X=i,X=i，…,X=i}•P{X=i,X=i，…,X=i}TOC\o"1-5"\h\znn0011n-ln-l0011n-1n-l=P{X=i|X=i}•P{X=i,X=i，…,X=i}二P{Xnnn-1n-10011n-1n-二P{X二i}P{X二iX二i}•••P{X二iX二i}P{X二i}n-1n-1n-1n-1n-2n一2110000由此可见，马尔可夫链的统计特性完全由条件概率

P｛X=i|X=i｝所确定，所以如何确定这个条件概率就显得非常重要，我n+1n+1nn们把这个条件概率称为一步转移概率。一般一步转移概率为P｛X=jX=i｝，n+1n它表示系统在时刻n处于状态i的条件下，到时刻n+1转移到状态j的概率，记为p(n)。ij定义2称条件概率p(n)=P｛X=j|X=i｝为马尔可夫链｛X,n>0｝在时刻nijn+1nn的一步转移概率。一般，转移概率p(n)不仅与状态i,j有关，而且与时刻n有关，但当它与时刻nij无关时，表示马尔可夫链具有平稳转移概率，即与起点无关，此时我们称马尔可夫链是齐次的。定义3如果对任意的i,jgI,马尔可夫链的转移概率p(n)与n无关，则称ij｛X,n>0｝为齐次马尔可夫链，并记p(n)=p。nijij下面我们只讨论齐次马尔可夫链。设P为一步转移概率p所组成的矩阵，状态空间I二｛1,2,…｝，称ij(p11p12(p11p12p21p221np•・・2n为马尔可夫链的一步转移概率矩阵。转移概率矩阵具有下面性质p>0，i,jgIij(2)工p二1，igIijjgI称具有上面两条性质的矩阵为随机矩阵。下面给出n步转移概率的概念定义4称条件概率p(n)=P{X=j|X=i},i,jgI,m>0,n>1ijm+nm为马尔可夫链的n步转移概率，并称P(n)=(p(n))ij为马尔可夫链的n步转移概率矩阵。其中p(n)>0,Xp(n)=1。ijijjgI当n=1时，P(1)=P，规定p(0)=[°''丰'，即P⑼为单位矩阵。ijI1,i=j切普曼--柯尔莫哥洛夫方程定理1设｛X,n>0｝为马尔可夫链，则对任意正整数n0<l<n，和状态i,jgI,nn步转移概率具有下列性质(1)p(n)=Xp(l)p(n_l)(切普曼一柯尔莫哥洛夫方程)ijikkjkgI2)p(n)=工…工pp…pijikkkkj112n_1kgIkgI1n_13)P(n)=PP(n_1)4)P(n)=Pn证明(1)利用全概率公式和马尔可夫性，有p(n)=P{X=j|X=i}=P{U(X=k),X=j|X=i}(/m+nmm+lm+nmkgI

TOC\o"1-5"\h\z=P{U(X=k,X=j)1X=i}m+lm+nmkwI二工P{X二k,X二j|X二i}m+lm+nmkwI_yP{X=i,X=k,X=j}=乙mm+lm+nP{X=i}kImP{X二i}P{XP{X二i}P{X二kX二i}P{X二jXm.m+lmm+nP{X=i}m二i,X二k}mm+l二工P{X二k|X二i}P{X二j|X二k}m+lmm+nm+lkI工P(l)p(n-l)ikkjkI工p(l)(m)p(工P(l)p(n-l)ikkjkIikkjkI（1）式是关于转移概率的一个重要结果，切普曼-柯尔莫哥洛夫方程（简称为C-K方程），直观上可以作如下解释：马尔可夫链｛Xn,n$O｝在时刻m处于状态i，经过n步，即在时刻m+n转移到状态j的过程可以视为它在时刻m处于状态i，先经过l步，即在时刻m+l遍历所有状态k（k二1,2,…），然后再经过n-1步,即在时刻m+n转到状态j的转移过程（见下图）C-K方程的矩阵形式为P（n）二P（l）P（n-l）当l=1时，即为（3）P（n）二PP（n-1），再利用归纳法可证（4）

在（1）中令l=1,k=k，得p（n）pp（n-1）这是一个递推公式，逐步递推可1ijik1k1jkel证（2）例3（随机游动）设质点在线段上做随机游动。（见图）。每隔一秒钟移动一步。当质点处于O'点时，必然要以概率1向右移动一步至‘1'点；当质点处于‘4'点时，下一步必然以概率1向左移动一步至‘3'点；当质点处于其它点时，下一步便均分别以概率亍向左、向右或停留在原地不动。令Xn表示n次移动后质点所处的位置。显然，｛Xn,n$O｝为一齐次马尔可夫链,其状态空间为I=｛0,1,2,3,4｝试求｛Xn,n$O｝的一步和二步转移概率矩阵：解：按题意可知砂厂H耳+厂0耳丸｝=0如=H兀+】=1氐=0｝=1巩厂Fg=2|耳=0｝=0同样可求得其它转移概率于是便得一步转移概率矩阵二步转移概率矩阵便为r010001r010001r010001111…1110000333333^1111110000333333…1111110033333300010i0001oj111010333152109999123219999901251999900111333齐次马尔可夫链的有限维分布1.一维分布定义5设｛X,n>0｝为齐次马尔可夫链，其状态空间为I,称下列一组概率np(0)=P｛X=j｝，jgIj0为｛X,n>0｝的初始分布，p(0)称为初始概率。将其写成向量形式为njPt(0)=(p(0),p(0),…,p(0),...)，称为初始概率向量。12N定义6设｛X,n>0｝为齐次马尔可夫链，其状态空间为I,称下列一组概率nP(n)二P｛X二j｝,jgIjn为｛X,n>0｝的绝对分布，p(n)称为绝对概率。将其写成向量形式为njPt(n)二(pW，p2(n)，…,pN(n)，…)，称为绝对概率向量。定理2设｛X,n>0｝为齐次马尔可夫链，则对任意jgI和n>1，绝对概率具有n下列性质p(n)二工P(0)p(n)jiijigIp(n)二工p(n-1)pjiijigI(3)PT(n)二PT(O)P(n)(4)PT(n)二PT(n-1)P证明⑴p(n)二P{X二j}二工P{X二i,X二j}TOC\o"1-5"\h\zjn0nigI二工P{X二i}P{X二j|X二i}二工p(0)p(n)0n0i(/igIigIp(n)=P{X=j}二工P{X=i,X=j}jnn-1nigI二工P{X二i}P{X二j|X二i}二工p(n-1)pn-1nn-1ijigIigI(4)式是(1)(2)的矩阵形式。2．n维分布定理3设｛X,n>0｝为齐次马尔可夫链，对任意i,i，…显gI和n>1，则马尔可n12n夫链的n维分布有

P{X二i,X二i，…，X二i}=工p(0)pp…p1122nn'"1化ln-1lniel此式证明利用了乘法公式和马尔可夫的无后效性。(见教材P45)此式表明齐次马尔可夫链的有限维分布同样可由其初始分布和转移概率而确定。例4．某计算机经常出故障。现每隔15分钟观察一次此计算机的状态，共收集97次观察结果。用‘1'表示工作正常，用‘0'表示工作不正常，所测得数据如下：1110010000111令Xn表示第n个时间段计算机的状态。显然{Xn,n$0}为齐次马尔可夫链。其状态空间为1={0,1}。由统计的结果可得转移情况如下：0T0有8次；1—0有1欣0—侑1欽；1T侑立次利用频率‘代替'概率的原理,可得转移概率=P{^M+1=0^=0}=1818+5218=P{^M+1=0^=0}=1818+521870即得其转移概率矩阵为「818126261852假定初始分布为肌®=尸闪=0}=5(0)=尸徑厂1}=0则此计算机能连续工作四个时间段(即一小时)的概率便为P{X.=\x2=1尼=1疋=1}=$>◎內⑴皿⑴皿⑴皿⑴jjj书上例题例1无限制随机游动设质点在数轴上移动，每次移动一格，向右移动的概率为p,向左移动的概率为q=l-p，这种运动称为无限制随机游动，以X表示质点在时刻n所处的位置，则n{X,n>0}是一个齐次马尔可夫链，试写出它的一步转移概率矩阵和k步转移概n率。解显然状态空间为I={0,±1,±2,.・.}，一步转移概率矩阵为q0p0…0q0p…丿设质点在k步转移过程中向右移了x步，向左移了y步，并且经过k步转移状态从i进入j，则解出由于x,y是正整数，所以k土(j-i)必须是偶数，又在k步转移中哪x步向右哪y步向左是任意的，于是[Cxpxqy,k土(j-i)为偶数

©[0，k土(j-i)为奇数例2赌徒输光问题两赌徒甲、乙进行一系列赌博，甲有a元，乙有b元，每赌一局输者给赢者1元,没有和局，直到两人中有一人输光为止，设在每一局中，甲赢的概率为P，输的概率为q=1-p，求甲输光的概率。这个问题实际上是带有两个吸收壁的随机游动，状态空间为I二{0,1,2,…,c},c二a+b，求质点从状态a出发到达状态0先于到达状态c的概率。解设u表示甲从状态i出发转移到状态0的概率，现要计算u。ia由于0和c是吸收状态，故u二1,u二00c由全概率公式u二pu+qu,i二1,2,…,c—1TOC\o"1-5"\h\zii+1i-1艮卩(p+q)u二pu+qu，pu-pu二qu-quii+1i-1i+1iii-1所以u一u=r(u一u),r=q,i=1,2,…,c一1i+1iii-1p1这是一个差分方程，下面只讨论p=q=丄,即r=1的情况，此时2u—u=u—ui=1,2,•…,c—1i+1iii-1令u=u+a，贝I」10u=u-u+u=u+a=u+2a，210110u=u+a=u+3a，320••・u=u+iai0…，u=u+ca，即0=1+ca，a1c0c所以u=1——1au=1—=b，a+bicac由于甲、乙的地位是对等的，同样可计算出乙输光的概率为

au二ba+b上式表明甲输光的概率与乙的赌本成正比，所以赌本小者输光的可能性大（输赢等可能的情况下），又u+u二1，表明必有一人要输光，赌博迟早要结束。ab例3天气预报问题设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨、今日有雨，明日有雨的概率为0.5；昨日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日都无雨，明日有雨的概率为0.2；若星期一、星期二均下雨，求星期四下雨的概率。解设昨日、今日都有雨称为状态0（记为RR）,昨日无雨、今日有雨称为状态1（记为NR），昨日有雨、今日无雨称为状态2（记为RN），昨日、今日都无雨称为状态3（记为NN），于是此问题可看作是一个4状态的马尔可夫链，求现在处于状态0的条件下将来处于状态0或1的两部转移概率p（2）+p（2）,下面求出一0001步概率转移矩阵明昨今p=P{RRRR}=P{连续三天有雨}=P{RRR}=0.7明昨今00今明昨今明昨今p=P{NRRR}=0（不可能事件）01今明昨今明昨今p=P{RNRR}=P{NRR}=1-0.7=0.3明昨今02今明昨今明昨今p=P{NNRR}=0（不可能事件）03今明昨今p=p{rrInr}=p{rInr}=0.510今明1昨今明|昨今p=P{NRInR}=0（不可能事件）11今明I昨今p=P{RNNR}=P{N|NR}=1-0.5=0.512今明昨今明I昨今p=P{NNInR}=0（不可能事件）13今明I昨今20同样方法可求出p=P{RRRN}=0，p=P{NRRN}=0.420“今明昨今21今明昨今p=P{RNRN}=p=P{RNRN}=0，22今明昨今昨今p=P{NNRN}=0.623今明昨今昨今30=