第3章馬氏過(guò)程

隨機(jī)數(shù)學(xué)

第三章馬氏過(guò)程教師:陳萍prob123@13.1Markov鏈

一、馬氏鏈的概念及轉(zhuǎn)移矩陣定義3.1.1若隨機(jī)序列{Xn,nN},狀態(tài)空間E={1,2,…}.對(duì)任意n1,任意i0,i1,···,inE,都有則稱(chēng){Xn,nN},為是一個(gè)可數(shù)狀態(tài)的Markov鏈，簡(jiǎn)稱(chēng)馬氏鏈。注式(3.1.1)所反映這種性質(zhì)稱(chēng)為Markov性或無(wú)后效性，它與第一章論述的Markov性是等價(jià)的.2馬氏鏈的等價(jià)描述：1)(3.1.2）僅證:事實(shí)上:32)證:2)(3.1.1)取則反之,由定義,于是,43)4)課外練習(xí)5定義3.1.2Markov鏈X={Xn,nN},E={1,2,…}.1)--n步轉(zhuǎn)移概率；2)若與m無(wú)關(guān)--齊次（或時(shí)齊）Markov鏈，此時(shí)特別,以下僅限于討論齊次馬氏鏈.3)--n步轉(zhuǎn)移概率矩陣.6隨機(jī)矩陣若馬氏鏈的狀態(tài)空間E={1，2，···，N}，則稱(chēng)此馬氏鏈?zhǔn)怯邢揆R氏鏈。此時(shí)，其k步轉(zhuǎn)移矩陣是一個(gè)N階方陣顯然7定理3.1.3C-K方程.或記--n時(shí)刻Xn的概率分布向量.--Markov鏈的絕對(duì)分布;--Markov鏈的初始分布.可證,一個(gè)Markov鏈的特性完全由它的一步轉(zhuǎn)移概率矩陣P及初始分布向量決定…8定理3.1.4EX

設(shè)系統(tǒng)有三種可能狀態(tài)E={1,2,3}.“1”表示系統(tǒng)運(yùn)行良好，“2”表示運(yùn)行不正常，“3”表示系統(tǒng)失效.以Xn表示系統(tǒng)在時(shí)刻n的狀態(tài),并設(shè){Xn,n≥0}是一Markov鏈.沒(méi)有維修及更換條件下，其自然轉(zhuǎn)移概率矩陣為P,初始分布為π,試求系統(tǒng)在時(shí)刻1,2及n∞時(shí)出現(xiàn)各種狀態(tài)的概率.9二若干實(shí)例例3.1.1獨(dú)立隨機(jī)變量和的序列設(shè){ξn,n≥0}為獨(dú)立同分布隨機(jī)變量序列，分布律為P{ξn=k}=qk,k=0,1,…，令,則{Xn,n≥0}是一Markov鏈，且

10例3.1.2直線(xiàn)上的隨機(jī)游動(dòng)(1)無(wú)限制的隨機(jī)游動(dòng)設(shè)有一質(zhì)點(diǎn)在數(shù)軸上隨機(jī)游動(dòng)，每隔一單位時(shí)間Δt(設(shè)Δt=1)移動(dòng)一次，每次只能向左或向右移動(dòng)Δx單位(設(shè)Δx=1)，或原地不動(dòng).設(shè)質(zhì)點(diǎn)在0時(shí)刻的位置為a，它向右移動(dòng)的概率為p≥0，向左移動(dòng)的概率為q≥0，原地不動(dòng)的概率為r≥0(p+q+r=1)，且各次移動(dòng)相互獨(dú)立，以Xn表示質(zhì)點(diǎn)經(jīng)n次移動(dòng)后所處的位置，則{Xn,n≥0}是一Markov鏈，且pi,i+1=p,pi,i-1=q,pii=r，其余pij=0.11(2)帶吸收壁的隨機(jī)游動(dòng)設(shè)(1)中的隨機(jī)游動(dòng)限制在E={0,1,2,…,b}內(nèi)，當(dāng)質(zhì)點(diǎn)移動(dòng)到狀態(tài)0或b后就永遠(yuǎn)停留在該位置，即p00=1，pbb=1，其余pij(1≤i,j≤b-1)同(1).這時(shí)序列{Xn,n≥0}稱(chēng)為帶兩個(gè)吸收壁0和b的隨機(jī)游動(dòng)，是一有限狀態(tài)Markov鏈.(3)帶反射壁的隨機(jī)游動(dòng)如(2)中的質(zhì)點(diǎn)到達(dá)0或b后，下次移動(dòng)必返回到1或b-1，即其余同(1)，稱(chēng)為帶反射壁0和b的隨機(jī)游動(dòng)，且為Markov鏈。12例3.1.3M/G/1排隊(duì)系統(tǒng)假設(shè)顧客依參數(shù)為λ的Poisson過(guò)程來(lái)到只有一個(gè)服務(wù)員的服務(wù)站，若服務(wù)員空閑來(lái)客就立刻得到服務(wù)，否則排隊(duì)等待直至輪到他。設(shè)每名顧客接受服務(wù)的時(shí)間獨(dú)立同分布，分布函數(shù)為G(x)，且與顧客到達(dá)過(guò)程相互獨(dú)立。這個(gè)系統(tǒng)稱(chēng)為M/G/1排隊(duì)系統(tǒng).(M--到達(dá)的時(shí)間間隔服從指數(shù)分布,G--服務(wù)時(shí)間的分布，1--單個(gè)服務(wù)員)。令Xn--第n個(gè)顧客服務(wù)完畢時(shí)等待接受服務(wù)的顧客數(shù)，Un--第n個(gè)顧客接受服務(wù)的時(shí)間內(nèi)來(lái)到服務(wù)機(jī)構(gòu)的顧客數(shù)，則其中可證{Xn,n=0,1,2,…}是齊次Markov鏈,其一步轉(zhuǎn)移概率為13例3.1.4分枝過(guò)程分枝過(guò)程是Markov過(guò)程的重要特例。常用來(lái)描述細(xì)胞分裂，種群繁衍，粒子裂變等現(xiàn)象，在隨機(jī)過(guò)程的理論和應(yīng)用中占有非常重要的地位。下面介紹的模型是英國(guó)博物學(xué)家Galton,Watson在研究家族譜系關(guān)系時(shí)引入的，因此也稱(chēng)為Galton-Watson分枝過(guò)程（簡(jiǎn)稱(chēng)G-W過(guò)程）?？紤]一個(gè)能產(chǎn)生同類(lèi)后代的個(gè)體組成的群體。每個(gè)個(gè)體以概率產(chǎn)生m個(gè)新后代，與別的個(gè)體產(chǎn)生的后代個(gè)數(shù)相互獨(dú)立。初始的個(gè)體個(gè)數(shù)為X0，其后代構(gòu)成第一代，總數(shù)記為X1。以此類(lèi)推，以Xn表示第n代的總數(shù)，記表示第n代的第i個(gè)個(gè)體的后代個(gè)數(shù)，那么就為一個(gè)齊次Markov鏈，稱(chēng)之為時(shí)間離散的分枝過(guò)程.pij=…14數(shù)學(xué)模型為設(shè)獨(dú)立同分布取非負(fù)整數(shù)，其公共分布為。X0任意取正整數(shù)的隨機(jī)變量則是一個(gè)離散時(shí)間的分枝過(guò)程，或分枝鏈。可證:為齊次Markov鏈.且15EX設(shè){Xi,i=1,2,…}是相互獨(dú)立的隨機(jī)變量，且使得P{Xi=j}=aj，j=0,1,…,如果其中就稱(chēng)在時(shí)刻n產(chǎn)生了一個(gè)記錄.若在時(shí)刻n產(chǎn)生了一個(gè)記錄，就稱(chēng)Xn為記錄值，以Rn表示第n個(gè)記錄值.證明，是Markov鏈，并求其轉(zhuǎn)移概率；16證明：根據(jù)題意有：滿(mǎn)足故故是一個(gè)馬爾可夫鏈且17§3.2Markov鏈的狀態(tài)分類(lèi)與判別例3.2.1設(shè)系統(tǒng)有三種可能狀態(tài)E={1,2,3}.“1”表示系統(tǒng)運(yùn)行良好，“2”表示運(yùn)行不正常，“3”表示系統(tǒng)失效.以Xn表示系統(tǒng)在時(shí)刻n的狀態(tài),并設(shè){Xn,n≥0}是一Markov鏈.其一步轉(zhuǎn)移概率矩陣為P用有向圖表示為：18定義3.2.1稱(chēng)狀態(tài)iE為吸收態(tài)，若pii=1.定義3.2.2對(duì)i,j

E，若存在n

N，使，則稱(chēng)自狀態(tài)i出發(fā)可達(dá)狀態(tài)j，記為i

j.如果ij且ji，則稱(chēng)i,j相通，記為ij.定理3.2.1相通是一種等價(jià)關(guān)系,即滿(mǎn)足自返性ii;對(duì)稱(chēng)性ij,則ji;傳遞性ij,jk則ik.19定義3.2.3若一Markov鏈的任意兩個(gè)狀態(tài)都相通，則稱(chēng)為不可約鏈。定義3.2.4令Tij=min{n:X0=i,Xn=j,n1}，稱(chēng)為系統(tǒng)在0時(shí)刻從狀態(tài)i出發(fā)，首次到達(dá)狀態(tài)j的時(shí)間，簡(jiǎn)稱(chēng)為首達(dá)時(shí).且規(guī)定,若右邊為空集，則Tij=∞.EX設(shè){Xn}是無(wú)限制的隨機(jī)游動(dòng),且p,q,r都大于0.證明{Xn}是不可約鏈.20

定義3.2.5令表示0時(shí)刻從狀態(tài)i出發(fā)，經(jīng)n步轉(zhuǎn)移后首次到達(dá)狀態(tài)j的概率，稱(chēng)為n步首達(dá)概率；由i出發(fā)，經(jīng)過(guò)有限步首次到達(dá)狀態(tài)j的概率為21

定義3.2.6若fii=1，則稱(chēng)狀態(tài)i為常返態(tài);若fii<1，則稱(chēng)狀態(tài)i為瞬時(shí)態(tài)（非常返態(tài)）。定義3.2.7如果fij=1,記則表示從i出發(fā)到達(dá)j的平均轉(zhuǎn)移時(shí)間.特別，稱(chēng)為從狀態(tài)i出發(fā)，返回狀態(tài)i的平均返回時(shí)間.若<∞，稱(chēng)i為正常返態(tài)；若=∞，稱(chēng)i為零常返狀態(tài).例3.2.1（續(xù)1）求系統(tǒng)由1出發(fā)，經(jīng)過(guò)有限步首次到達(dá)狀態(tài)2的概率.并求fii,i=1,2,322例3.2.2

設(shè)馬爾可夫鏈的狀態(tài)空間E={1,2,3,4}，轉(zhuǎn)移概率矩陣為試判斷各狀態(tài)的常返性。23引理

對(duì)任意i,jE及n1，有

注：由式(3.2.1)可得遞推公式:上式也稱(chēng)為M.C從狀態(tài)i首次到達(dá)狀態(tài)j的分解式，簡(jiǎn)稱(chēng)首達(dá)分解式。推論定理3.2.224i為瞬時(shí)態(tài)定理3.2.3推論有限狀態(tài)馬氏鏈的狀態(tài)空間至少有一個(gè)常返態(tài)。定理3.2.4常返態(tài)全體構(gòu)成一個(gè)閉集。定義3.2.8設(shè)CE，若對(duì)任意的iC，和任意的jC,及任意的nT，pij(n)=0，則稱(chēng)C為E的閉集。i為常返態(tài)25

定理3.2.6設(shè)馬氏鏈的狀態(tài)空間為E，(1)對(duì)任意i,jE，若ij，則它們同為常返態(tài)或瞬時(shí)態(tài)；而且當(dāng)i,j是常返態(tài)時(shí)，i,j同為正常返態(tài)或同為零常返態(tài)；(2)不可約的有限齊次馬氏鏈的狀態(tài)都是正常返的。定義3.2.7如果集合{n:n≥1,>0}≠φ，稱(chēng)該數(shù)集的最大公約數(shù)d(i)為狀態(tài)i的周期.若d(i)>1，稱(chēng)i為周期的，若d(i)=1，稱(chēng)i為非周期的.定義3.2.8若狀態(tài)i為正常返態(tài)的且非周期的，則稱(chēng)i為遍歷狀態(tài).定義3.2.9稱(chēng)Markov鏈?zhǔn)潜闅v的,如果所有狀態(tài)都是遍歷態(tài).26小結(jié)相通、閉集、不可約狀態(tài)常返瞬時(shí)正常返、零常返周期、非周期遍歷定理3.2.7設(shè)馬氏鏈的狀態(tài)空間為E，i,jE，（1）若iE是一個(gè)周期態(tài)，且ij，則j也是周期態(tài)，且di=dj；（2）若此鏈不可約，且對(duì)iE有pii>0，則此鏈?zhǔn)欠侵芷阪湣?73.3狀態(tài)空間分解定理任意Markov鏈的狀態(tài)空間E可唯一分解為有限或可列個(gè)互不相交的子集之和其中N由全體瞬時(shí)態(tài)組成;每個(gè)或是零常返或正常返態(tài)組成的不可約閉集;(3)每個(gè)或中的狀態(tài)同類(lèi).它們有相同的周期,且28EX設(shè)齊次馬爾可夫鏈的矩陣一步轉(zhuǎn)移概率矩陣為試對(duì)其狀態(tài)空間進(jìn)行分解.29例3.4.1

設(shè)Markov鏈的轉(zhuǎn)移矩陣為(1)試求狀態(tài)1,2的n步首達(dá)概率并求(2)求Pn并考慮當(dāng)?shù)那闆r.3.4極限定理及平穩(wěn)分布解(1)30同理例3.4.1

設(shè)Markov鏈的轉(zhuǎn)移矩陣為(1)試求狀態(tài)1,2的n步首達(dá)概率.31例3.4.1

設(shè)Markov鏈的轉(zhuǎn)移矩陣為(2)求Pn并考慮當(dāng)?shù)那闆r.取從而32表明33定理3.4.1若狀態(tài)j是周期為d的常返態(tài),則推論3.4.1若狀態(tài)j是常返態(tài),則j是0常返態(tài)極限定理定理3.4.2

若j是瞬時(shí)態(tài)或零常返態(tài),則對(duì)任意iS,34定理3.4.3

若j是正常返態(tài)且周期為d,則對(duì)任意i及,有推論設(shè){Xn}是不可約遍歷鏈,則i,j∈E35定義3.4.1對(duì)于馬氏鏈{Xn，n0},概率分布稱(chēng)為是平穩(wěn)的,若平穩(wěn)分布與極限分布定理3.4.4不可約Markov鏈?zhǔn)潜闅v鏈對(duì)任意i,jS，存在僅依賴(lài)于j的常數(shù)j，使得j稱(chēng)為Markov鏈的極限分布.且有36例3.3.2設(shè)有6個(gè)車(chē)站,車(chē)站中間的公路連接情況如圖.汽車(chē)每天可以從一個(gè)站駛向與之直接相鄰的車(chē)站,并在夜晚到達(dá)車(chē)站留宿,次日凌晨重復(fù)相同的活動(dòng).設(shè)每天凌晨汽車(chē)開(kāi)往臨近的任一車(chē)站都是等可能的,試說(shuō)明很長(zhǎng)時(shí)間后,各站每晚留宿的汽車(chē)比例趨于穩(wěn)定.求出這個(gè)比例以便正確地設(shè)置各站的服務(wù)規(guī)模.125364P10037>>P100=P^100P100=0.12500.18750.12500.18750.12500.25000.12500