第三章 馬爾可夫鏈

#第三章馬爾可夫鏈一、馬爾可夫鏈的概念馬爾可夫過程是一類有重要應(yīng)用意義的隨機過程，它具有如下特征：隨機過程‘將來'所處的狀態(tài)僅與‘現(xiàn)在'所處的狀態(tài)有關(guān)，而與‘過去'曾處于什么狀態(tài)無關(guān)。馬爾可夫過程按其狀態(tài)和時間參數(shù)是離散還是連續(xù)的可以分成三類（1）時間和狀態(tài)都是離散的馬爾可夫過程，稱為馬爾可夫鏈。（2）時間連續(xù)、狀態(tài)離散的馬爾可夫過程，稱為連續(xù)時間的馬爾可夫鏈。（3）時間和狀態(tài)都連續(xù)的馬爾可夫過程。本章介紹馬爾可夫鏈定義1設(shè)｛X,n>0｝為隨機序列，其狀態(tài)空間為I二｛i,i,i，…｝，如果對任意正n012整數(shù)n及任意n+2個狀態(tài)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稱為‘現(xiàn)在'，將時刻n+1稱為‘將來'，而把0，1，2，……，n-1稱為‘過去'。定義中的等式便可通俗解釋為：在已知｛X,n>0｝‘現(xiàn)在'所n處的狀態(tài)條件下，‘將來'所要達到的狀態(tài)與‘過去'所經(jīng)歷的狀態(tài)無關(guān)，這一特性常稱為馬爾可夫的無后效性。例1.一個n級數(shù)字傳輸系統(tǒng)，每一級的輸入和輸出信號只取0或1兩個值，每一級的輸出是下一級的輸入；并假定當(dāng)一級輸入為0時，其輸出為0和為1的概率分別為P和1-P；當(dāng)輸入為1時，其輸出為1和0的概率分別為P和1-P（見圖）

令Xn表示第n級輸出，貝嘰Xn,n$O｝便為一個馬爾可夫鏈。例2.從1,2,……,N數(shù)字中任取一個數(shù)，記為X0；再從1,2,……,X0數(shù)字中任取一個數(shù)，記為XI；再從1,2,……,X1中任取一個數(shù)，記為X2；依此類推，在1,2,,Xn-1中任取一個數(shù)，記為Xn?？梢宰C明｛Xn,n$O｝為馬爾可夫鏈。事實上，｛Xn,n$O｝的狀態(tài)空間為I=｛1,2,……,N｝，對任意正整數(shù)n,取n+1個狀態(tài)i,i,i，…,ieI,由題意可知012nH當(dāng)4＞也時=玖見=訂兀_1=—｝故｛Xn,n$O｝為馬爾可夫鏈。二、轉(zhuǎn)移概率由馬爾可夫鏈的無后效性和乘法公式有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由此可見，馬爾可夫鏈的統(tǒng)計特性完全由條件概率

P｛X=i|X=i｝所確定，所以如何確定這個條件概率就顯得非常重要，我n+1n+1nn們把這個條件概率稱為一步轉(zhuǎn)移概率。一般一步轉(zhuǎn)移概率為P｛X=jX=i｝，n+1n它表示系統(tǒng)在時刻n處于狀態(tài)i的條件下，到時刻n+1轉(zhuǎn)移到狀態(tài)j的概率，記為p(n)。ij定義2稱條件概率p(n)=P｛X=j|X=i｝為馬爾可夫鏈｛X,n>0｝在時刻nijn+1nn的一步轉(zhuǎn)移概率。一般，轉(zhuǎn)移概率p(n)不僅與狀態(tài)i,j有關(guān)，而且與時刻n有關(guān)，但當(dāng)它與時刻nij無關(guān)時，表示馬爾可夫鏈具有平穩(wěn)轉(zhuǎn)移概率，即與起點無關(guān)，此時我們稱馬爾可夫鏈是齊次的。定義3如果對任意的i,jgI,馬爾可夫鏈的轉(zhuǎn)移概率p(n)與n無關(guān)，則稱ij｛X,n>0｝為齊次馬爾可夫鏈，并記p(n)=p。nijij下面我們只討論齊次馬爾可夫鏈。設(shè)P為一步轉(zhuǎn)移概率p所組成的矩陣，狀態(tài)空間I二｛1,2,…｝，稱ij(p11p12(p11p12p21p221np???2n為馬爾可夫鏈的一步轉(zhuǎn)移概率矩陣。轉(zhuǎn)移概率矩陣具有下面性質(zhì)p>0，i,jgIij(2)工p二1，igIijjgI稱具有上面兩條性質(zhì)的矩陣為隨機矩陣。下面給出n步轉(zhuǎn)移概率的概念定義4稱條件概率p(n)=P{X=j|X=i},i,jgI,m>0,n>1ijm+nm為馬爾可夫鏈的n步轉(zhuǎn)移概率，并稱P(n)=(p(n))ij為馬爾可夫鏈的n步轉(zhuǎn)移概率矩陣。其中p(n)>0,Xp(n)=1。ijijjgI當(dāng)n=1時，P(1)=P，規(guī)定p(0)=[°''豐'，即P⑼為單位矩陣。ijI1,i=j切普曼--柯爾莫哥洛夫方程定理1設(shè)｛X,n>0｝為馬爾可夫鏈，則對任意正整數(shù)n0<l<n，和狀態(tài)i,jgI,nn步轉(zhuǎn)移概率具有下列性質(zhì)(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）式是關(guān)于轉(zhuǎn)移概率的一個重要結(jié)果，切普曼-柯爾莫哥洛夫方程（簡稱為C-K方程），直觀上可以作如下解釋：馬爾可夫鏈｛Xn,n$O｝在時刻m處于狀態(tài)i，經(jīng)過n步，即在時刻m+n轉(zhuǎn)移到狀態(tài)j的過程可以視為它在時刻m處于狀態(tài)i，先經(jīng)過l步，即在時刻m+l遍歷所有狀態(tài)k（k二1,2,…），然后再經(jīng)過n-1步,即在時刻m+n轉(zhuǎn)到狀態(tài)j的轉(zhuǎn)移過程（見下圖）C-K方程的矩陣形式為P（n）二P（l）P（n-l）當(dāng)l=1時，即為（3）P（n）二PP（n-1），再利用歸納法可證（4）

在（1）中令l=1,k=k，得p（n）pp（n-1）這是一個遞推公式，逐步遞推可1ijik1k1jkel證（2）例3（隨機游動）設(shè)質(zhì)點在線段上做隨機游動。（見圖）。每隔一秒鐘移動一步。當(dāng)質(zhì)點處于O'點時，必然要以概率1向右移動一步至‘1'點；當(dāng)質(zhì)點處于‘4'點時，下一步必然以概率1向左移動一步至‘3'點；當(dāng)質(zhì)點處于其它點時，下一步便均分別以概率亍向左、向右或停留在原地不動。令Xn表示n次移動后質(zhì)點所處的位置。顯然，｛Xn,n$O｝為一齊次馬爾可夫鏈,其狀態(tài)空間為I=｛0,1,2,3,4｝試求｛Xn,n$O｝的一步和二步轉(zhuǎn)移概率矩陣：解：按題意可知砂廠H耳+廠0耳丸｝=0如=H兀+】=1氐=0｝=1鞏廠Fg=2|耳=0｝=0同樣可求得其它轉(zhuǎn)移概率于是便得一步轉(zhuǎn)移概率矩陣二步轉(zhuǎn)移概率矩陣便為r010001r010001r010001111…1110000333333^1111110000333333…1111110033333300010i0001oj111010333152109999123219999901251999900111333齊次馬爾可夫鏈的有限維分布1.一維分布定義5設(shè)｛X,n>0｝為齊次馬爾可夫鏈，其狀態(tài)空間為I,稱下列一組概率np(0)=P｛X=j｝，jgIj0為｛X,n>0｝的初始分布，p(0)稱為初始概率。將其寫成向量形式為njPt(0)=(p(0),p(0),…,p(0),...)，稱為初始概率向量。12N定義6設(shè)｛X,n>0｝為齊次馬爾可夫鏈，其狀態(tài)空間為I,稱下列一組概率nP(n)二P｛X二j｝,jgIjn為｛X,n>0｝的絕對分布，p(n)稱為絕對概率。將其寫成向量形式為njPt(n)二(pW，p2(n)，…,pN(n)，…)，稱為絕對概率向量。定理2設(shè)｛X,n>0｝為齊次馬爾可夫鏈，則對任意jgI和n>1，絕對概率具有n下列性質(zhì)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設(shè)｛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)此式表明齊次馬爾可夫鏈的有限維分布同樣可由其初始分布和轉(zhuǎn)移概率而確定。例4．某計算機經(jīng)常出故障?，F(xiàn)每隔15分鐘觀察一次此計算機的狀態(tài)，共收集97次觀察結(jié)果。用‘1'表示工作正常，用‘0'表示工作不正常，所測得數(shù)據(jù)如下：1110010000111令Xn表示第n個時間段計算機的狀態(tài)。顯然{Xn,n$0}為齊次馬爾可夫鏈。其狀態(tài)空間為1={0,1}。由統(tǒng)計的結(jié)果可得轉(zhuǎn)移情況如下：0T0有8次；1—0有1欣0—侑1欽；1T侑立次利用頻率‘代替'概率的原理,可得轉(zhuǎn)移概率=P{^M+1=0^=0}=1818+5218=P{^M+1=0^=0}=1818+521870即得其轉(zhuǎn)移概率矩陣為「818126261852假定初始分布為肌?=尸閃=0}=5(0)=尸徑廠1}=0則此計算機能連續(xù)工作四個時間段(即一小時)的概率便為P{X.=\x2=1尼=1疋=1}=$>◎內(nèi)⑴皿⑴皿⑴皿⑴jjj書上例題例1無限制隨機游動設(shè)質(zhì)點在數(shù)軸上移動，每次移動一格，向右移動的概率為p,向左移動的概率為q=l-p，這種運動稱為無限制隨機游動，以X表示質(zhì)點在時刻n所處的位置，則n{X,n>0}是一個齊次馬爾可夫鏈，試寫出它的一步轉(zhuǎn)移概率矩陣和k步轉(zhuǎn)移概n率。解顯然狀態(tài)空間為I={0,±1,±2,.?.}，一步轉(zhuǎn)移概率矩陣為q0p0…0q0p…丿設(shè)質(zhì)點在k步轉(zhuǎn)移過程中向右移了x步，向左移了y步，并且經(jīng)過k步轉(zhuǎn)移狀態(tài)從i進入j，則解出由于x,y是正整數(shù)，所以k土(j-i)必須是偶數(shù)，又在k步轉(zhuǎn)移中哪x步向右哪y步向左是任意的，于是[Cxpxqy,k土(j-i)為偶數(shù)

?[0，k土(j-i)為奇數(shù)例2賭徒輸光問題兩賭徒甲、乙進行一系列賭博，甲有a元，乙有b元，每賭一局輸者給贏者1元,沒有和局，直到兩人中有一人輸光為止，設(shè)在每一局中，甲贏的概率為P，輸?shù)母怕蕿閝=1-p，求甲輸光的概率。這個問題實際上是帶有兩個吸收壁的隨機游動，狀態(tài)空間為I二{0,1,2,…,c},c二a+b，求質(zhì)點從狀態(tài)a出發(fā)到達狀態(tài)0先于到達狀態(tài)c的概率。解設(shè)u表示甲從狀態(tài)i出發(fā)轉(zhuǎn)移到狀態(tài)0的概率，現(xiàn)要計算u。ia由于0和c是吸收狀態(tài)，故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，表明必有一人要輸光，賭博遲早要結(jié)束。ab例3天氣預(yù)報問題設(shè)昨日、今日都下雨，明日有雨的概率為0.7；昨日無雨、今日有雨，明日有雨的概率為0.5；昨日有雨、今日無雨，明日有雨的概率為0.4；昨日、今日都無雨，明日有雨的概率為0.2；若星期一、星期二均下雨，求星期四下雨的概率。解設(shè)昨日、今日都有雨稱為狀態(tài)0（記為RR）,昨日無雨、今日有雨稱為狀態(tài)1（記為NR），昨日有雨、今日無雨稱為狀態(tài)2（記為RN），昨日、今日都無雨稱為狀態(tài)3（記為NN），于是此問題可看作是一個4狀態(tài)的馬爾可夫鏈，求現(xiàn)在處于狀態(tài)0的條件下將來處于狀態(tài)0或1的兩部轉(zhuǎn)移概率p（2）+p（2）,下面求出一0001步概率轉(zhuǎn)移矩陣明昨今p=P{RRRR}=P{連續(xù)三天有雨}=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=