馬爾可夫鏈課件

CHAPTER5馬爾可夫鏈第一節(jié)基本概念1、分類離散連續(xù)離散連續(xù)馬爾可夫鏈馬爾可夫序列可數(shù)狀態(tài)馬爾可夫過程連續(xù)狀態(tài)馬爾可夫過程按馬爾可夫過程參數(shù)空間和狀態(tài)空間的不同可分為一、馬爾可夫鏈的定義及例子CHAPTER5馬爾可夫鏈第一節(jié)基本概念1、分類

隨機(jī)過程稱為馬爾可夫鏈，若它只取有限或可列個(gè)值（稱為過程的狀態(tài)，記為0，1，2，…），并且，對(duì)任意及狀態(tài)，有2.馬爾可夫鏈的定義隨機(jī)過程

定義稱為n時(shí)刻的一步轉(zhuǎn)移概率。

若，即pij與n無關(guān)，稱轉(zhuǎn)移概率具有平穩(wěn)性.此時(shí)稱{Xn,n≥0}為齊次（或時(shí)齊的）馬爾可夫鏈。記P=(pij)，稱P為{Xn,n≥0}的一步轉(zhuǎn)移概率矩陣.3、轉(zhuǎn)移概率定義稱4、馬爾可夫鏈的例子顯然{Yn,n≥1}也是一馬爾可夫鏈。例1

獨(dú)立隨機(jī)變量和的序列

設(shè){Yn,n≥1}為獨(dú)立同分布隨機(jī)變量序列，且Yn取值為非負(fù)整數(shù)，其概率分布為P{Yn=i}=ai，i=0,1,2,…令X0=0,Xn=Y1+…+Yn

，則易證{Xn,n≥0}是一馬爾可夫鏈，且4、馬爾可夫鏈的例子顯然{Yn,n≥1}也是一馬爾可夫鏈例2

M/G/1排隊(duì)系統(tǒng)假設(shè)顧客依參數(shù)為的泊松過程來到一服務(wù)中心，只有一個(gè)服務(wù)員，來客發(fā)現(xiàn)服務(wù)員空著即刻得到服務(wù)；其他人排隊(duì)等待服務(wù)。相繼來到的顧客的服務(wù)時(shí)間Ti假定為相互獨(dú)立的隨機(jī)變量，具有共同的分布G；且假定他們與來到過程獨(dú)立。

M/G/1排隊(duì)系統(tǒng)中字母M代表顧客來到時(shí)間間隔服從指數(shù)分布，G代表服務(wù)時(shí)間的分布，數(shù)字1代表只有一個(gè)服務(wù)員。若以X(t)記在t時(shí)刻系統(tǒng)中的顧客數(shù)，{X(t),t≥0}則不具馬爾可夫性。因?yàn)?，若我們知道在t時(shí)刻系統(tǒng)中的顧客數(shù)，那么為了預(yù)測(cè)將來的狀態(tài)，我們不用關(guān)心從最近的一位顧客來到后已過去了多長時(shí)間（因?yàn)閬淼竭^程是無記憶的），但和服務(wù)中的顧客服務(wù)了多長時(shí)間有關(guān)（因?yàn)榉?wù)時(shí)間分布不具無記憶性）。例2M/G/1排隊(duì)系統(tǒng)Xn-----第n個(gè)顧客走后剩下的顧客數(shù)，Yn-----第n+1個(gè)顧客接受服務(wù)期間來到的顧客數(shù)，則容易證明{Yn，n≥1}獨(dú)立同分布，且因此，{Xn，n≥1}是馬爾可夫鏈。其轉(zhuǎn)移概率為

為了克服上述困難，我們可以只在顧客離去的時(shí)刻考察系統(tǒng)，記Xn-----第n個(gè)顧客走后剩下的顧客數(shù)，容易證明{Yn，n例3

G/M/1排隊(duì)系統(tǒng)

來到時(shí)間間隔分布為G，服務(wù)時(shí)間分布為指數(shù)分布，參數(shù)為，且與顧客到達(dá)過程獨(dú)立。

Xn-----第n個(gè)顧客來到時(shí)見到系統(tǒng)中的顧客數(shù)（包括該顧客），則{Xn，n≥1}是馬爾可夫鏈。記

Yn-----第n個(gè)顧客來到時(shí)刻到第n+1個(gè)顧客來到時(shí)刻之間系統(tǒng)服務(wù)完的顧客數(shù)，則例3G/M/1排隊(duì)系統(tǒng)Xn-

pi0公式略有不同，它是服務(wù)臺(tái)由有i個(gè)顧客轉(zhuǎn)為空閑的概率，即第n個(gè)顧客來到時(shí)刻到第n+1個(gè)顧客來到時(shí)刻之間系統(tǒng)服務(wù)完的顧客數(shù)≥i+1。pi0公式略有不同，它是服務(wù)臺(tái)由有i個(gè)顧客轉(zhuǎn)為空閑例4

直線上的隨機(jī)游動(dòng)

（1）無限制的隨機(jī)游動(dòng)設(shè)有一質(zhì)點(diǎn)在數(shù)軸上隨機(jī)游動(dòng)，每隔一單位時(shí)間移動(dòng)一次，每次只能向左或向右移動(dòng)一單位，或原地不動(dòng)。設(shè)質(zhì)點(diǎn)在0時(shí)刻的位置為a,向右移動(dòng)的概率為p，向左移動(dòng)的概率為q，原地不動(dòng)的概率為r(p+q+r=1),且各次移動(dòng)相互獨(dú)立，以Xn表示質(zhì)點(diǎn)經(jīng)n次移動(dòng)后所處的位置，則{Xn,n≥0}是一馬爾可夫鏈,轉(zhuǎn)移概率為Pi,i+1=p,Pi,i-1=q,Pi,i=r,其余Pi,j=0

（2）帶吸收壁的隨機(jī)游動(dòng)設(shè)（1）中的隨機(jī)游動(dòng)限制在S={0,1,2,…b}，當(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}稱為帶兩個(gè)吸收壁0和b的隨機(jī)游動(dòng)，它是一有限狀態(tài)馬爾可夫鏈。例4直線上的隨機(jī)游動(dòng)例5Polya（波利亞）模型

罐中有b只黑球及r只紅球，每次隨機(jī)地取出一只后把原球放回，并加入與抽出球同色的球c只，再第二次隨機(jī)地取球重復(fù)上面步驟進(jìn)行下去，{Xn=i}表示第n回摸球放回操作完成后，罐中有i只黑球這一事件，所以這是一個(gè)非齊次的馬爾可夫鏈，在傳染病研究中有用。例5Polya（波利亞）模型罐中

下面的定理提供了一個(gè)非常有用的獲得馬爾可夫鏈的方法，并可用于檢驗(yàn)一隨機(jī)過程是否為馬爾可夫鏈。定理：設(shè)隨機(jī)過程{Xn,n≥0}滿足（1）Xn=f(Xn-1,Yn),(n≥1),其中f:S×S→S,且Yn取值在S上，（2）{Yn,n≥1}為獨(dú)立同分布隨機(jī)變量，且X0與{Yn,n≥1}也相互獨(dú)立，則{Xn,n≥0}是馬爾可夫鏈，其一步轉(zhuǎn)移概率為

pij=P[f(i,Y1)=j]證明：設(shè)n≥1，則Yn+1與X0,X1,…,Xn相互獨(dú)立，事實(shí)上，

因?yàn)閄1=f(X0,Y1)，Y2與X0,Y1獨(dú)立，所以，

Y2與X1，X0獨(dú)立。同理，X2=f(X1,Y2)=f(f(X0,Y1),Y2)，所以，

Y3與X2，X1，X0獨(dú)立。歸納可得Yn+1與X0,X1,…,Xn相互獨(dú)立。下面的定理提供了一個(gè)非常有用的獲得馬爾可夫鏈所以{Xn,n≥0}是馬爾可夫鏈，且所以有所以{Xn,n≥0}是馬爾可夫鏈，且所以有二、切普曼-柯爾莫哥洛夫方程

顯然馬爾可夫鏈{Xn,n≥0}的一步轉(zhuǎn)移概率矩陣P為隨機(jī)矩陣。2，n步轉(zhuǎn)移概率定義：設(shè){Xn,n≥0}是一馬爾可夫鏈，稱1，隨機(jī)矩陣

定義：稱矩陣A=(aij)S×S為隨機(jī)矩陣，若aij≥0，且二、切普曼-柯爾莫哥洛夫方程顯然馬爾可夫鏈{X為馬爾可夫鏈{Xn,n≥0}的n步轉(zhuǎn)移概率。記稱為n時(shí)刻Xn的概率分布向量。稱為馬爾可夫鏈{Xn,n≥0}的初始分布向量。結(jié)論：一個(gè)馬爾可夫鏈的特性完全由它的一步轉(zhuǎn)移概率矩陣及初始分布向量決定。為馬爾可夫鏈{Xn,n≥0}的n步轉(zhuǎn)移概率。記稱為n時(shí)刻Xn

類似地可以證明馬爾可夫鏈任意個(gè)時(shí)刻的聯(lián)合分布也完全由一步轉(zhuǎn)移概率矩陣及初始分布向量決定。事實(shí)上類似地可以證明馬爾可夫鏈任意個(gè)時(shí)刻的聯(lián)合分布3、定理：切普曼-柯爾莫哥洛夫方程（C-K方程）或其中為馬爾可夫鏈{Xn,n≥0}的n步轉(zhuǎn)移概率矩陣。3、定理：切普曼-柯爾莫哥洛夫方程（C-K方程）或其中為馬爾證明：證明：

例（馬爾可夫預(yù)測(cè)）某種鮮奶A改變了廣告方式，經(jīng)調(diào)查發(fā)現(xiàn)購買A種鮮奶及另外三種鮮奶B、C、D的顧客每兩個(gè)月的平均轉(zhuǎn)換率為：（假設(shè)市場(chǎng)上只有這4種鮮奶）

A→A（95%）B（2%）C（2%）D（1%）

B→A（30%）B（60%）C（6%）D（4%）

C→A（20%）B（10%）C（7%）D（0%）

D→A（20%）B（20%）C（10%）D（50%）假設(shè)目前購買A、B、C、D4種鮮奶的顧客的分布為（25%，30%，35%，10%），求半年后鮮奶A、B、C、D的市場(chǎng)份額。例（馬爾可夫預(yù)測(cè)）某種鮮奶A改變了廣告方式解一階轉(zhuǎn)移矩陣為初始分布為解一階轉(zhuǎn)移矩陣為初始分布為則半年后A種鮮奶的市場(chǎng)占有率為則半年后A種鮮奶的市場(chǎng)占有率為（1）寫出狀態(tài)空間；（2）求P(2)；（3）問在甲獲得1分的情況下，再賽二局可以結(jié)束比賽的概率是多少？例甲、乙兩人進(jìn)行比賽，設(shè)每局比賽中甲勝的概率p，乙勝的概率是q，和局的概率是r,(p+q+r=1)。設(shè)每局比賽后，勝者記“+1”分，負(fù)者記“-1”分，和局不記分。當(dāng)兩人中有一人獲得2分結(jié)束比賽。以Xn表示比賽至第n局時(shí)甲獲得的分?jǐn)?shù)。（1）寫出狀態(tài)空間；（2）求P(2)；（3）問在甲獲得1分的

解（1）記甲獲得“負(fù)2分”為狀態(tài)1，獲得“負(fù)1分”為狀態(tài)2，獲得“0分”為狀態(tài)3，獲得“正1分”為狀態(tài)4，獲得“正2分”為狀態(tài)5，則狀態(tài)空間為一步轉(zhuǎn)移概率矩陣為解（1）記甲獲得“負(fù)2分”為狀態(tài)1，獲得“負(fù)1（2）二步轉(zhuǎn)移概率矩陣（2）二步轉(zhuǎn)移概率矩陣（3）在P2中P45(2)是在甲得1分的情況下經(jīng)二步轉(zhuǎn)移至2分從而結(jié)束比賽的概率；P41(2)是在甲得1分的情況下經(jīng)二步轉(zhuǎn)移至-2分（即乙得2分）從而結(jié)束比賽的概率。（3）在P2中P45(2)是在甲得1分的情況下經(jīng)二步轉(zhuǎn)移至2解例解例第5章-馬爾可夫鏈課件第5章-馬爾可夫鏈課件

某計(jì)算機(jī)房的一臺(tái)計(jì)算機(jī)經(jīng)常出故障,研究者每隔15分鐘觀察一次計(jì)算機(jī)運(yùn)行狀態(tài),收集了24小時(shí)的數(shù)據(jù)(共作97次觀察).用1表示正常狀態(tài),用0表示不正常狀態(tài),所得的數(shù)據(jù)序列如下:1110010011111110011110111111001111111110001101101分析狀態(tài)空間:I={0,1}.例111011011010111101110111101111110011011111100111某計(jì)算機(jī)房的一臺(tái)計(jì)算機(jī)經(jīng)常出故障,研究者11100196次狀態(tài)轉(zhuǎn)移的情況:因此,一步轉(zhuǎn)移概率可用頻率近似地表示為:96次狀態(tài)轉(zhuǎn)移的情況:因此,一步轉(zhuǎn)移概率可用頻率近似地表第二節(jié)狀態(tài)的分類及性質(zhì)

定義1:若存在某個(gè)n使得，則稱從狀態(tài)i可達(dá)狀態(tài)j，記為i→j，如果i→j且j→i

，則稱i與j相通，記為。若一馬爾可夫鏈的任意兩個(gè)狀態(tài)都是相通的，則稱該馬爾可夫鏈?zhǔn)遣豢杉s的。若pii=1。則稱狀態(tài)i為吸收態(tài)。定理：相通是一種等價(jià)關(guān)系。即第二節(jié)狀態(tài)的分類及性質(zhì)定義1:若存在某

定義2：若集合

則稱該數(shù)集的最大公約數(shù)d(i)為狀態(tài)i的周期。若d(i)>1，稱i為周期的，若d(i)=1，稱i為非周期的。

注意：若狀態(tài)i的周期為d,則對(duì)一切n≠0（mod(d)）都有,但并非對(duì)任意的n，都有。例如①②③④⑤⑥⑦⑧⑨定義2：若集合則稱該數(shù)集的最大公約數(shù)d(i)定理：則d(i)=d(j)。證明：若i與j相通，則存在m,n，使得對(duì)任意的s，若有，則則，對(duì)應(yīng)狀態(tài)1而言，集合的最大公約數(shù)為2，所以，。但是，當(dāng)時(shí)，。但可以證明：對(duì)于充分大的n，有。定理：則d(i)=d(j)。證明：若i與j

因?yàn)閐(i)是i的周期，所以d(i)應(yīng)同時(shí)整除n+m和n+m+s，則d(i)一定整除s，而d(j)是j的周期，所以d(i)整除d(j)。反過來也可證明d(j)整除d(i)，于是d(i)=d(j)。定義3：首達(dá)時(shí)間定義為若右邊為空集，則令

Tij表示從i出發(fā)首次到達(dá)j的時(shí)間，Tii表示從i出發(fā)首次回到i的時(shí)間.因?yàn)閐(i)是i的周期，所以d(i)應(yīng)同時(shí)整除n定義4：首達(dá)概率定義為表示從i經(jīng)n步首次到達(dá)j的概率。顯然有定義5fij表示過程從i出發(fā)在有限步內(nèi)能夠到達(dá)j的概率，（或者說從i出發(fā)遲早轉(zhuǎn)移到狀態(tài)j的概率）。fii表示過程從i出發(fā)在有限步內(nèi)（遲早）回到狀態(tài)i的概率。定義6:

若fii=1,則稱i為常返狀態(tài)，若fii<1,則稱i為非常返狀態(tài)（或瞬時(shí)狀態(tài)或稱滑過的）。定義4：首達(dá)概率定義為表示從i經(jīng)n步首次到達(dá)j的概率。顯然定義7:

若i為常返狀態(tài)，即fii=1,記稱為從狀態(tài)i出發(fā)再回到i的平均回轉(zhuǎn)時(shí)間（或平均回轉(zhuǎn)步數(shù)）。若，稱為正常返狀態(tài)，若，稱為零常返狀態(tài)。

定義8:

若狀態(tài)i是正常返的并且是非周期的，則稱狀態(tài)i為遍歷狀態(tài)。注：當(dāng)i為非常返狀態(tài)（滑過的）時(shí)，。定義7:若i為常返狀態(tài)，即fii=1,記稱定理：與有如下關(guān)系定理：與有如下關(guān)系定理：狀態(tài)i是常返狀態(tài)，當(dāng)且僅當(dāng)狀態(tài)i是非常返狀態(tài)，當(dāng)且僅當(dāng)證明：約定，定理：狀態(tài)i是常返狀態(tài)，當(dāng)且僅當(dāng)狀態(tài)i是非常返狀態(tài)，的含義則表示過程到達(dá)i

的次數(shù)。所以表示過程從i出發(fā)返回到i的平均次數(shù)。的含義則表示過程到達(dá)i的次數(shù)。所以表示過程從i出發(fā)返

若狀態(tài)i是滑過的（非常返的）則

即滑過狀態(tài)i只能有限次到達(dá)i。從而有限狀態(tài)的馬爾可夫鏈不可能全部狀態(tài)都是滑過的。即有限狀態(tài)的馬爾可夫鏈至少有一個(gè)狀態(tài)是常返的。定理：若，則i,j同為常返的和非常返的。即常返性具有類性質(zhì)。若為常返的，則它們同為正常返狀態(tài)或零常返狀態(tài)。證明：由，知存在n,m，使得，由C-K方程總有若狀態(tài)i是滑過的（非常返的）則所以，相互控制，同為無窮或有限，從而同為常返或非常返。所以，相互控制，同

以Nj(t)記到時(shí)刻t為止轉(zhuǎn)移到j(luò)的次數(shù)。若j是常返的，且X0=j，則因?yàn)橐坏┺D(zhuǎn)移到j(luò)，過程在概率上重新從頭開始，故{Nj(t),t≥0}是一個(gè)來到時(shí)間間隔分布為的更新過程。若X0=i，，且j是常返的，則{Nj(t),t≥0}是一個(gè)延遲更新過程，其初始來到時(shí)間間隔分布為。

為什么要將狀態(tài)進(jìn)行分類呢？

常返態(tài)表明，過程從常返狀態(tài)出發(fā)能無窮次返回該狀態(tài)，而滑過狀態(tài)最多只能有限次地返回，因此，隨著時(shí)間的發(fā)展，滑過狀態(tài)將逐漸消失。所以，在對(duì)Markov鏈作穩(wěn)態(tài)設(shè)計(jì)時(shí)，滑過狀態(tài)是不予考慮的，這也說明了區(qū)分常返態(tài)與滑過狀態(tài)是十分重要的。以Nj(t)記到時(shí)刻t為止轉(zhuǎn)移到j(luò)的例考慮直線上無限制的隨機(jī)游動(dòng)，狀態(tài)空間為轉(zhuǎn)移概率為則對(duì)于狀態(tài)0，有由斯特林(Stirling)公式可知：當(dāng)n充分大時(shí)有所以例考慮直線上無限制的隨機(jī)游動(dòng)，狀態(tài)空間為轉(zhuǎn)移概率為則對(duì)于狀注意到所以，當(dāng)時(shí)，此時(shí)，狀態(tài)0是常返的。當(dāng)時(shí)，此時(shí)，狀態(tài)0是滑過的。

由于過程的各個(gè)狀態(tài)都是相通的，由此可判斷其它狀態(tài)的常返性。注意到所以，當(dāng)時(shí)，此時(shí)例轉(zhuǎn)移矩陣試對(duì)其狀態(tài)分類。解按一步轉(zhuǎn)移概率，畫出各狀態(tài)間的傳遞圖21/4111/41/411/4143例轉(zhuǎn)移矩陣試對(duì)其狀態(tài)分類。解按一步轉(zhuǎn)移概率，畫出各狀態(tài)間的傳從圖可知，此鏈的每一狀態(tài)都可到達(dá)另一狀態(tài)，即4個(gè)狀態(tài)都是相通的?？紤]狀態(tài)1是否常返，從圖可知，此鏈的每一狀態(tài)都可到達(dá)另一狀態(tài)，即4個(gè)狀態(tài)都是相通類似地可求得所以于是狀態(tài)1是常返的。又因?yàn)樗誀顟B(tài)1是正常返的。由定理可知，此鏈所有狀態(tài)都是正常返的。類似地可求得所以于是狀態(tài)1是常返的。又因?yàn)樗誀顟B(tài)1是正常返例設(shè)馬氏鏈的狀態(tài)空間I={0,1,2,…}，其一步轉(zhuǎn)移概率為其中試證此馬氏鏈?zhǔn)且粋€(gè)不可約常返態(tài)鏈證先證I不可約設(shè)i，j是I中任意兩個(gè)狀態(tài)，則有例設(shè)馬氏鏈的狀態(tài)空間I={0,1,2,…}，其一步轉(zhuǎn)移概率為類似地可證所以即I中任意兩個(gè)狀態(tài)都是相通的。因此，I是一個(gè)不可約的閉集再證I中狀態(tài)0是一個(gè)常返態(tài)：由狀態(tài)的轉(zhuǎn)移規(guī)則，得所以102345類似地可證所以即I中任意兩個(gè)狀態(tài)都是相通的。因此，I是一個(gè)不由定義知狀態(tài)0為常返態(tài)。因此，由定理知I中所有狀態(tài)都是常返態(tài)。故此馬氏鏈為不可約常返鏈。由定義知狀態(tài)0為常返態(tài)。因此，由定理知I中所有狀態(tài)都是常返態(tài)

例股票價(jià)格的馬爾科夫性考慮離散時(shí)間的股票價(jià)格過程，對(duì)時(shí)間t(t=0,1,2,…),設(shè)S(t)表示某一股票在t時(shí)刻的價(jià)格，每間隔一個(gè)單位時(shí)間股票價(jià)格以概率q上升到前一期的u倍，或以概率1-q下降到前一期的d倍，且各次漲跌是相互獨(dú)立的，即以概率q,以概率1-q,

設(shè)S(0)=S，則例股票價(jià)格的馬爾科夫性以概率q,以概

定義獨(dú)立同分布的隨機(jī)變量序列第i

次上漲,第i

次下跌。則并且定義第i

次上漲,第i

次下跌。則是一Markov鏈。(隨機(jī)游動(dòng))定義獨(dú)立同分布的隨機(jī)變量序列第i次上漲

狀態(tài)空間的分解

定義1

設(shè)馬爾可夫鏈的狀態(tài)空間為S，，若對(duì)任意的，都有，則稱C為（隨機(jī)）閉集。若C的狀態(tài)相通，則稱閉集C是不可約的。

注：狀態(tài)i是吸收態(tài)等價(jià)于單點(diǎn)集{i}是閉集；馬爾可夫鏈的整個(gè)狀態(tài)空間為S構(gòu)成一閉集。

閉集C的直觀意義是自C的內(nèi)部不能到達(dá)C的外部，這意味著系統(tǒng)狀態(tài)一旦進(jìn)入閉集C內(nèi)，它就永遠(yuǎn)在C中運(yùn)動(dòng)。狀態(tài)空間的分解定義1設(shè)馬

引理1

C是閉集的充要條件是對(duì)任意的都有。

證明：充分性顯然，下證必要性，用歸納法證明：當(dāng)n=1時(shí)，由定義知結(jié)論成立，假設(shè)n=k時(shí)結(jié)論成立，即對(duì)任意的有則引理1C是閉集的充要條件是對(duì)任意的

引理2

若

i是常返的，且，則。

證明：若假如，則以正概率，使得從j出發(fā)不能在有限步內(nèi)到達(dá)i。而，這意味著系統(tǒng)中存在著一個(gè)正概率，使得它從i出發(fā)不能在有限步內(nèi)回到i,從而，與i是常返狀態(tài)矛盾，所以只能。

引理3

若

i是常返的，且，則j是常返的。

證明：由引理2知，于是存在n使得從而，即。所以。即j也是常返狀態(tài)。引理2若i是常返的，且

定理1

所有的常返狀態(tài)構(gòu)成一閉集。

證明：設(shè)i是常返狀態(tài)，且，則引理1，2知，且j也是常返狀態(tài)，說明從常返狀態(tài)出發(fā)只能到達(dá)常返狀態(tài)，不可能到達(dá)非常返狀態(tài)。

定理2

馬爾可夫鏈的狀態(tài)空間S可分解為其中為基本常返閉集，且T為所有非常返狀態(tài)組成的集合（不一定是閉集）。定理1所有的常返狀態(tài)構(gòu)成一閉集。

【注】當(dāng)系統(tǒng)從某非常返狀態(tài)出發(fā)，系統(tǒng)可能一直在非常返集T中（當(dāng)T為閉集時(shí)），也可能在某時(shí)刻離開T進(jìn)入到基本常返集中運(yùn)動(dòng)，一旦進(jìn)入到基本常返集，就永遠(yuǎn)在該常返集中運(yùn)動(dòng)。

定理3

若S為有限集，則所有非常返狀態(tài)組成的集合T一定是非閉集。即不管系統(tǒng)自什么狀態(tài)出發(fā)，遲早要進(jìn)入常返閉集。

推論有限不可約馬爾可夫鏈的狀態(tài)都是常返態(tài)。即【注】當(dāng)系統(tǒng)從某非常返狀態(tài)出發(fā)，系統(tǒng)可能一

定理4

設(shè)是閉集，只考慮上所得的m步轉(zhuǎn)移概率子矩陣，則是一隨機(jī)矩陣。

證明：顯然，任取所以，矩陣為隨機(jī)矩陣。定理4設(shè)是

定理5（系統(tǒng)進(jìn)入基本常返閉集后的運(yùn)動(dòng)情形）若基本常返閉集中的狀態(tài)的周期為d，則可進(jìn)一步d個(gè)不交子集之和，即這些子集有性質(zhì)：自中任一狀態(tài)出發(fā)，下一步（經(jīng)1步轉(zhuǎn)移）必轉(zhuǎn)移到中去。如果i=d-1，則i+1=d解釋為0，即中的的狀態(tài)下一步轉(zhuǎn)移到中去。證略。定理5（系統(tǒng)進(jìn)入基本常返閉集后的運(yùn)動(dòng)情形第三節(jié)極限定理與平穩(wěn)分布

一、極限定理

在實(shí)際應(yīng)用中，人們常常關(guān)心兩個(gè)問題：

（1）當(dāng)時(shí)，的極限是否存在？

（2）當(dāng)什么條件下，一個(gè)馬爾可夫鏈?zhǔn)且粋€(gè)平穩(wěn)序列？第三節(jié)極限定理與平穩(wěn)分布一、極限定理

注意到：，故對(duì)（1）的研究可轉(zhuǎn)化為對(duì)的漸近性質(zhì)的研究。即是否存在？若存在，其極限是否與狀態(tài)i有關(guān)？Markov鏈理論中，有關(guān)這一問題的定理統(tǒng)稱為遍歷定理。

問題(2)的實(shí)際上是討論馬爾可夫鏈平穩(wěn)分布是否存在的問題。這兩個(gè)問題之間有密切聯(lián)系。注意到：

例1設(shè)馬爾可夫鏈的轉(zhuǎn)移概率矩陣為現(xiàn)在來計(jì)算令例1設(shè)馬爾可夫鏈的轉(zhuǎn)移概率矩陣為現(xiàn)在來計(jì)則所以則所以

定理1

若j是非常返態(tài)（滑過的）則對(duì)任意的i

有證明：因?yàn)樗裕ɡ?若j是非常返態(tài)（滑過的）則對(duì)任令，得（因?yàn)閖是非常返態(tài)）顯然此時(shí)有令，得（因?yàn)閖是非常

定理2

若j是常返態(tài)，則（1）若，則有（2）若時(shí)（不可達(dá)）則有證明（1）若，則使得而故

（2）顯然。定理2若j是常返態(tài)，則（1）若的含義則表示過程到達(dá)j

的次數(shù)。所以表示過程從i出發(fā)進(jìn)入狀態(tài)j的平均次數(shù)。的含義則表示過程到達(dá)j的次數(shù)。所以表示過程從i出發(fā)進(jìn)

定理3

若j是非常返態(tài)或零常返態(tài)，則對(duì)任意的i

有

證明：定理1已證j是非常返態(tài)情形，當(dāng)j是零常返態(tài)時(shí)，取有，定理3若j是非常返態(tài)或零常返態(tài)，則對(duì)先固定m，令得這是因?yàn)樯鲜街?，且是有限?xiàng)和。從而再令，注意到所以先固定m，令得這是因?yàn)?/p>

推論1

有限狀態(tài)的馬爾可夫鏈沒有零常返態(tài)。

推論2

有限狀態(tài)的馬爾可夫鏈的狀態(tài)不可能全為非常返狀態(tài)。

推論3不可約的有限狀態(tài)馬爾可夫鏈的狀態(tài)全為正常返的。

推論4若馬爾可夫鏈有一個(gè)零常返態(tài)，則必有無限個(gè)零常返態(tài)。（由推論1可得）。推論1有限狀態(tài)的馬爾可夫鏈沒有零常返態(tài)。

定理4

若j是正常返態(tài)，周期為d,則對(duì)任意的i

及有

當(dāng)j是正常返狀態(tài)時(shí)情況較復(fù)雜，此時(shí)不一定存在，即使存在也可能與i有關(guān)。這時(shí)有一下結(jié)論:(證略)其中

表示從狀態(tài)i

出發(fā)，在時(shí)刻n=r(mod(d)首次到達(dá)狀態(tài)j的概率。且定理4若j是正常返態(tài)

推論1

若j是遍歷狀態(tài)（正常返的并且是非周期的），則對(duì)任意的狀態(tài)i∈S有

證明：在定理4

中取d=1,r=0。

推論2

對(duì)于不可約的遍歷鏈（即所有狀態(tài)是遍歷狀態(tài)且相通），若對(duì)任意狀態(tài)i

，j∈S，有

注意到：若，且j為常返態(tài)，則。由推論1即得。推論1若j是遍歷狀態(tài)（正常返

定理4

若j是常返狀態(tài)，則對(duì)任意的i∈S，有

推論若不可約馬爾可夫鏈的狀態(tài)是常返狀態(tài)，則對(duì)任意的i，j∈S，有

注意：表示過程從i出發(fā)前n個(gè)單位時(shí)間進(jìn)入狀態(tài)j的總的平均次數(shù)，表示每單位時(shí)間到達(dá)狀態(tài)j的平均次數(shù)，與表達(dá)的含義相同。定理4若j是常返狀態(tài)，則對(duì)狀態(tài)性質(zhì)判別法：i非常返i零常返i正常返i遍歷的狀態(tài)性質(zhì)判別法：i非常返i零常返i正常返i遍歷的二、平穩(wěn)分布與極限分布1，定義：設(shè)pij是馬爾可夫鏈{Xn,n≥1}的轉(zhuǎn)移概率。若概率分布{pj,j≥0}滿足則稱{pj,j≥0}為{Xn,n≥1}的平穩(wěn)分布。記二、平穩(wěn)分布與極限分布1，定義：設(shè)pij是馬

則平穩(wěn)分布可表示為如下矩陣形式顯然有即

注意：由知，所以1是矩陣P的左特征值，平穩(wěn)分布是P的左特征向量。則平穩(wěn)分布可表示為如下矩陣形式顯然有即

證明：若馬爾可夫鏈{Xn,n≥0}的初始分布

即Xn與X0有相同的分布，這說明過程{Xn,n≥0}是平穩(wěn)過程。這也是稱分布pj=P{X0=j}為平穩(wěn)分布的原因。

定理：設(shè){Xn,n≥0}是馬爾可夫鏈，則{Xn,n≥0}是平穩(wěn)過程的充要條件是其初始分布是平穩(wěn)分布。是平穩(wěn)分布，則對(duì)任意的n，有證明：若馬爾可夫鏈{Xn,n≥0}

反之，若{Xn,n≥0}是平穩(wěn)過程，則而所以即是平穩(wěn)分布。

平穩(wěn)分布可通過求方程組的非負(fù)解得到。其中。反之，若{Xn,n≥0}是平穩(wěn)過程，則而2，定義：若不可約馬爾可夫鏈?zhǔn)潜闅v的（即所有狀稱為馬爾可夫鏈的極限分布。態(tài)相通且均為周期為1的正常返態(tài)），則極限

定理：不可約遍歷的馬爾可夫鏈有唯一的平穩(wěn)分布此時(shí)唯一的平穩(wěn)分布就是極限分布。即2，定義：若不可約馬爾可夫鏈?zhǔn)潜闅v的（即

注：若狀態(tài)都是滑過的（非常返）或都是零常返的，則平穩(wěn)分布不存在。

證明：由定理4的推論2知不可約遍歷的馬爾可夫鏈的極限分布存在，且下證是平穩(wěn)分布。由于則有易知上式中極限與求和可交換，則有注：若狀態(tài)都是滑過的（非常返）或都是零常返的再由C-K方程得，兩邊取極限得，即，從而是平穩(wěn)分布。再證平穩(wěn)分布的唯一性：

假設(shè)還有另外一個(gè)平穩(wěn)分布，則有再由C-K方程得，兩邊取極限得，即歸納可證令有，因?yàn)?，所以有，即平穩(wěn)分布是唯一的。歸納可證令有，因?yàn)?/p>

定理：一個(gè)不可約非周期的馬爾可夫鏈屬于下列兩種情況之一：1，狀態(tài)或全是滑過的（非常返的）或全是零常返的。此時(shí)對(duì)一切的i,j有因而不存在平穩(wěn)分布。2，狀態(tài)全是正常返態(tài)。即此時(shí)是平穩(wěn)分布，且不存在任何其它的平穩(wěn)分布。此時(shí)極限分布即是平穩(wěn)分布。定理：一個(gè)不可約非周期的馬爾可夫鏈屬于下列兩種注：1，對(duì)于不可約的遍歷鏈（不可約、正常返、周期為1）因?yàn)樗?，可被解釋為馬爾可夫鏈長時(shí)間之后處于狀態(tài)j

的時(shí)間所占的比率。2，對(duì)于不可約的遍歷鏈，因?yàn)闃O限分布存在且等于平穩(wěn)分布，這意味著當(dāng)n充分大時(shí)有，

即{Xn,n≥0}是一漸近平穩(wěn)序列(平穩(wěn)過程)，這在實(shí)際問題中是很有意義的。注：1，對(duì)于不可約的遍歷鏈（不可約、正常返、周期為1）所以，例設(shè)馬氏鏈的狀態(tài)空間I={0,1,2,…}，轉(zhuǎn)移概率為試討論各狀態(tài)的遍歷性。解根據(jù)轉(zhuǎn)移概率作出狀態(tài)傳遞圖…1/21/21/21/21/21/20121/231/2例設(shè)馬氏鏈的狀態(tài)空間I={0,1,2,…}，轉(zhuǎn)移概率為試從圖可知，對(duì)任一狀態(tài)都有，故由定理可知，I中的所以狀態(tài)都是相通的，因此只需考慮狀態(tài)0是否正常返即可。…故從而0是常返態(tài)。又因?yàn)樗誀顟B(tài)0為正常返。又由于故狀態(tài)0為非周期的從而狀態(tài)0是遍歷的。故所有狀態(tài)i都是遍歷的。從圖可知，對(duì)任一狀態(tài)都有例設(shè)有6個(gè)球（其中2個(gè)紅球，4個(gè)白球）分放于甲、乙兩個(gè)盒子中，每盒放3個(gè)，今每次從兩個(gè)盒中各任取一球并進(jìn)行交換，以表示開始時(shí)甲盒中紅球的個(gè)數(shù)，（）表示經(jīng)n次交換后甲盒中的紅球數(shù)。(1)求馬氏鏈{，}的轉(zhuǎn)移概率矩陣；(2)證明{，}是遍歷的；（3）求（4）求例設(shè)有6個(gè)球（其中2個(gè)紅球，4個(gè)白球）分放于甲、乙兩個(gè)盒子中解其一步轉(zhuǎn)移矩陣為甲乙紅球0白球3紅球2白球1紅球1白球2紅球1白球2紅球2白球1紅球0白球3解其一步轉(zhuǎn)移矩陣為甲乙紅球0紅球2紅球1紅球1紅球2紅球0并作出狀態(tài)傳遞圖1/32/95/92/32/91/30122/3（2）由于它是一個(gè)有限馬氏鏈，故必有一個(gè)常返態(tài)，又鏈中三個(gè)狀態(tài)0、1、2都相通，所以每個(gè)狀態(tài)都是常返態(tài)。所以是一個(gè)不可約的有限馬氏鏈，從而每個(gè)狀態(tài)都是正常返的。所以此鏈為非周期的。故此鏈?zhǔn)遣豢杉s非周期的正常返鏈，即此鏈?zhǔn)潜闅v的。并作出狀態(tài)傳遞圖1/32/95/92/32/91/30122（2）可以利用定理證明遍歷性（2）可以利用定理證明遍歷性解之得故得解之得故得（4）（4）討論對(duì)時(shí)間連續(xù)狀態(tài)離散的馬爾可夫過程，取時(shí)間參數(shù)，狀態(tài)空間I={0,1,2,…}第五節(jié)時(shí)間連續(xù)馬爾可夫鏈一、定義及性質(zhì)時(shí)間連續(xù)的馬爾可夫鏈轉(zhuǎn)移概率討論對(duì)時(shí)間連續(xù)狀態(tài)離散的馬爾可夫過程，取時(shí)間參數(shù)齊次馬氏鏈轉(zhuǎn)移概率僅由t決定而與s無關(guān)2．性質(zhì)性質(zhì)1切普曼——柯爾莫哥洛夫方程齊次轉(zhuǎn)移概率僅由t決定而與s無關(guān)2．性質(zhì)性質(zhì)1切普曼——柯爾性質(zhì)2連續(xù)時(shí)間齊次馬氏鏈的有限維概率分布由它的初始分布和轉(zhuǎn)移矩陣所確定注性質(zhì)3注對(duì)時(shí)間來說是可逆性性質(zhì)2連續(xù)時(shí)間齊次馬氏鏈的有限維概率分布由它的初始分布和轉(zhuǎn)移性質(zhì)4已知現(xiàn)在，那么過去與將來是獨(dú)立注性質(zhì)5

（遍歷性定理）馬爾可夫定理設(shè){,}是狀態(tài)空間I={0,1，2,…,s}的時(shí)間連續(xù)的齊次馬氏鏈，則性質(zhì)4已知現(xiàn)在，那么過去與將來是獨(dú)立注性質(zhì)5（遍歷性定理）的滿足條件的唯一解。例1考慮一個(gè)電話總機(jī)接到的呼喚流，以表示這個(gè)總機(jī)在[0，t]中接到的呼喚次數(shù)，由于呼喚流在不相交的時(shí)間區(qū)間中接到的呼喚次數(shù)是相互獨(dú)立的，且服從泊松分布，所以是一個(gè)時(shí)間連續(xù)狀態(tài)離散的馬氏過程，而且是齊次的。寫出它的轉(zhuǎn)移概率。的滿足條件的唯一解。例1考慮一個(gè)電話總機(jī)接到的呼喚流，以當(dāng)呼喚次數(shù)時(shí)轉(zhuǎn)移概率當(dāng)時(shí)其狀態(tài)空間I={0，1，2，…}轉(zhuǎn)移概率為當(dāng)呼喚次數(shù)時(shí)轉(zhuǎn)移概率當(dāng)1．隨機(jī)連續(xù)則稱{}是隨機(jī)連續(xù)的。定理1二、可爾莫哥洛夫微分方程時(shí)間連續(xù)的齊次馬氏鏈{,}是隨機(jī)連續(xù)的充要條件為：對(duì)任意的，有隨機(jī)連續(xù)直觀意義當(dāng)系統(tǒng)經(jīng)過很短時(shí)間，其狀態(tài)幾乎不變。1．隨機(jī)連續(xù)則稱{}是隨機(jī)連續(xù)的。定理1二標(biāo)準(zhǔn)轉(zhuǎn)移概率

若時(shí)間連續(xù)的齊次馬氏鏈?zhǔn)请S機(jī)連續(xù)的，則稱其轉(zhuǎn)移概率是標(biāo)準(zhǔn)的。并且滿足性質(zhì):2．轉(zhuǎn)移概率的性質(zhì)性質(zhì)1性質(zhì)2定理2并且對(duì)任意，有標(biāo)準(zhǔn)轉(zhuǎn)移概率若時(shí)間連續(xù)的齊次馬氏鏈?zhǔn)请S機(jī)連續(xù)的，（2）對(duì)時(shí)間連續(xù)的齊次有限馬氏鏈，，有若注1推論則對(duì)任意，有即為吸收態(tài)（2）對(duì)時(shí)間連續(xù)的齊次有限馬氏鏈，，有若等價(jià)它表明系統(tǒng)從狀態(tài)i出發(fā)，是繼續(xù)留在狀態(tài)i，還是跳躍到狀態(tài)j，在不計(jì)一個(gè)高階無窮小時(shí)，決定于與注2等價(jià)跳躍強(qiáng)度

與稱為跳躍強(qiáng)度3．密度矩陣由跳躍強(qiáng)度構(gòu)成的矩陣等價(jià)它表明系統(tǒng)從狀態(tài)i出發(fā)，是繼續(xù)留在若對(duì)一切，有由定理2推論可知也稱時(shí)間連續(xù)馬氏鏈?zhǔn)潜Ｊ氐摹?/p>

矩陣保守時(shí)間連續(xù)的齊次有限馬氏鏈?zhǔn)潜Ｊ氐摹?、可爾莫哥洛夫定理則若對(duì)一切，有由定理2推論可知也稱時(shí)間連續(xù)推論(1)(2)注1（1）與（2）兩式分別稱為可爾莫哥洛夫向前方程和向后方程，其矩陣形式（向前方程）（向后方程）推論(1)(2)注1（1）與（2）兩式分別稱為可爾莫哥洛夫向?qū)r(shí)間連續(xù)齊次有限馬氏鏈，向前方程和向后方程均成立，且有如何求

注2在實(shí)際問題中往往是很困難。但考慮到密度矩陣，是由在的導(dǎo)數(shù)組成，即所以實(shí)際問題中先得到，再算注3費(fèi)勒已經(jīng)證明了向后方程與向前方程有同一解但具體應(yīng)用哪一個(gè)方程組求解，要看具體問題而定。對(duì)時(shí)間連續(xù)齊次有限馬氏鏈，向前方程和向后方程均成立，且有如何設(shè)狀態(tài)空間I={0,1}時(shí)間連續(xù)馬氏鏈而由狀態(tài)1轉(zhuǎn)到0的概率為且規(guī)定在時(shí)間內(nèi)，由狀態(tài)0轉(zhuǎn)到1的概率為例2兩狀態(tài)鏈試求時(shí)間t時(shí)的轉(zhuǎn)移概率設(shè)狀解類似地所以密度矩陣于是相應(yīng)的可爾莫哥洛夫前進(jìn)方程是即解類似地所以密度矩陣于是相應(yīng)的可爾莫哥洛夫前進(jìn)方程是即據(jù)題意有初始條件解上列微分方程，可得滿足此初始條件的解。例如求由得據(jù)題意有初始條件解上列微分方程，可得滿足此初始條件的解。例如因此或于是故由得因此或于是故由類似地可解得三、生滅過程

生滅過程是一類特殊的連續(xù)馬氏鏈，它有許多重要的應(yīng)用。類似地可解得三、生滅過程生滅過程是一類特殊的連設(shè)有同一類型的個(gè)體組成的一群體，其每一個(gè)體在任意時(shí)間內(nèi)，并設(shè)每一個(gè)體在此時(shí)間內(nèi)也會(huì)死亡，且壽命服從參數(shù)為的指數(shù)分布。模型含義設(shè)有同一類型的個(gè)體組成的一群體，其每一個(gè)體在任意時(shí)間若它的轉(zhuǎn)移概率滿足則稱此鏈為齊次生滅過程生率和滅率生滅過程定義若它的轉(zhuǎn)移概率滿足則稱此鏈為齊次生滅過程生率和滅率生滅過程定純生過程純滅過程由定義中的轉(zhuǎn)移規(guī)則知，生滅過程的狀態(tài)是互通的，并且在長為的一小段時(shí)間內(nèi)，若不計(jì)高階無窮小，狀態(tài)轉(zhuǎn)移只有三種可能：把理解為t時(shí)刻某群體的個(gè)體總數(shù)，這時(shí)經(jīng)過了生出了一個(gè)個(gè)體理解為經(jīng)過了，死去了一個(gè)個(gè)體純生過程純滅過程由定義中的轉(zhuǎn)移規(guī)則知，生滅過程的狀態(tài)是互通的密度矩陣由即可得密度矩陣由即可得可爾莫哥洛夫向前方程是向后方程是可爾莫哥洛夫向前方程是向后方程是假定平穩(wěn)分布由可得由可知假定平穩(wěn)分布由可得由可知定理4若其密度矩陣可表示成其中則是生滅過程。定理4若其密度矩陣可表示成其中則放映結(jié)束！無悔無愧于昨天，豐碩殷實(shí)的今天，充滿希望的明天。放映結(jié)束！無悔無愧于昨天，豐碩殷實(shí)的今天，充滿希望的明天。CHAPTER5馬爾可夫鏈第一節(jié)基本概念1、分類離散連續(xù)離散連續(xù)馬爾可夫鏈馬爾可夫序列可數(shù)狀態(tài)馬爾可夫過程連續(xù)狀態(tài)馬爾可夫過程按馬爾可夫過程參數(shù)空間和狀態(tài)空間的不同可分為一、馬爾可夫鏈的定義及例子CHAPTER5馬爾可夫鏈第一節(jié)基本概念1、分類

隨機(jī)過程稱為馬爾可夫鏈，若它只取有限或可列個(gè)值（稱為過程的狀態(tài)，記為0，1，2，…），并且，對(duì)任意及狀態(tài)，有2.馬爾可夫鏈的定義隨機(jī)過程

定義稱為n時(shí)刻的一步轉(zhuǎn)移概率。

若，即pij與n無關(guān)，稱轉(zhuǎn)移概率具有平穩(wěn)性.此時(shí)稱{Xn,n≥0}為齊次（或時(shí)齊的）馬爾可夫鏈。記P=(pij)，稱P為{Xn,n≥0}的一步轉(zhuǎn)移概率矩陣.3、轉(zhuǎn)移概率定義稱4、馬爾可夫鏈的例子顯然{Yn,n≥1}也是一馬爾可夫鏈。例1

獨(dú)立隨機(jī)變量和的序列

設(shè){Yn,n≥1}為獨(dú)立同分布隨機(jī)變量序列，且Yn取值為非負(fù)整數(shù)，其概率分布為P{Yn=i}=ai，i=0,1,2,…令X0=0,Xn=Y1+…+Yn

，則易證{Xn,n≥0}是一馬爾可夫鏈，且4、馬爾可夫鏈的例子顯然{Yn,n≥1}也是一馬爾可夫鏈例2

M/G/1排隊(duì)系統(tǒng)假設(shè)顧客依參數(shù)為的泊松過程來到一服務(wù)中心，只有一個(gè)服務(wù)員，來客發(fā)現(xiàn)服務(wù)員空著即刻得到服務(wù)；其他人排隊(duì)等待服務(wù)。相繼來到的顧客的服務(wù)時(shí)間Ti假定為相互獨(dú)立的隨機(jī)變量，具有共同的分布G；且假定他們與來到過程獨(dú)立。

M/G/1排隊(duì)系統(tǒng)中字母M代表顧客來到時(shí)間間隔服從指數(shù)分布，G代表服務(wù)時(shí)間的分布，數(shù)字1代表只有一個(gè)服務(wù)員。若以X(t)記在t時(shí)刻系統(tǒng)中的顧客數(shù)，{X(t),t≥0}則不具馬爾可夫性。因?yàn)?，若我們知道在t時(shí)刻系統(tǒng)中的顧客數(shù)，那么為了預(yù)測(cè)將來的狀態(tài)，我們不用關(guān)心從最近的一位顧客來到后已過去了多長時(shí)間（因?yàn)閬淼竭^程是無記憶的），但和服務(wù)中的顧客服務(wù)了多長時(shí)間有關(guān)（因?yàn)榉?wù)時(shí)間分布不具無記憶性）。例2M/G/1排隊(duì)系統(tǒng)Xn-----第n個(gè)顧客走后剩下的顧客數(shù)，Yn-----第n+1個(gè)顧客接受服務(wù)期間來到的顧客數(shù)，則容易證明{Yn，n≥1}獨(dú)立同分布，且因此，{Xn，n≥1}是馬爾可夫鏈。其轉(zhuǎn)移概率為

為了克服上述困難，我們可以只在顧客離去的時(shí)刻考察系統(tǒng)，記Xn-----第n個(gè)顧客走后剩下的顧客數(shù)，容易證明{Yn，n例3

G/M/1排隊(duì)系統(tǒng)

來到時(shí)間間隔分布為G，服務(wù)時(shí)間分布為指數(shù)分布，參數(shù)為，且與顧客到達(dá)過程獨(dú)立。

Xn-----第n個(gè)顧客來到時(shí)見到系統(tǒng)中的顧客數(shù)（包括該顧客），則{Xn，n≥1}是馬爾可夫鏈。記

Yn-----第n個(gè)顧客來到時(shí)刻到第n+1個(gè)顧客來到時(shí)刻之間系統(tǒng)服務(wù)完的顧客數(shù)，則例3G/M/1排隊(duì)系統(tǒng)Xn-

pi0公式略有不同，它是服務(wù)臺(tái)由有i個(gè)顧客轉(zhuǎn)為空閑的概率，即第n個(gè)顧客來到時(shí)刻到第n+1個(gè)顧客來到時(shí)刻之間系統(tǒng)服務(wù)完的顧客數(shù)≥i+1。pi0公式略有不同，它是服務(wù)臺(tái)由有i個(gè)顧客轉(zhuǎn)為空閑例4

直線上的隨機(jī)游動(dòng)

（1）無限制的隨機(jī)游動(dòng)設(shè)有一質(zhì)點(diǎn)在數(shù)軸上隨機(jī)游動(dòng)，每隔一單位時(shí)間移動(dòng)一次，每次只能向左或向右移動(dòng)一單位，或原地不動(dòng)。設(shè)質(zhì)點(diǎn)在0時(shí)刻的位置為a,向右移動(dòng)的概率為p，向左移動(dòng)的概率為q，原地不動(dòng)的概率為r(p+q+r=1),且各次移動(dòng)相互獨(dú)立，以Xn表示質(zhì)點(diǎn)經(jīng)n次移動(dòng)后所處的位置，則{Xn,n≥0}是一馬爾可夫鏈,轉(zhuǎn)移概率為Pi,i+1=p,Pi,i-1=q,Pi,i=r,其余Pi,j=0

（2）帶吸收壁的隨機(jī)游動(dòng)設(shè)（1）中的隨機(jī)游動(dòng)限制在S={0,1,2,…b}，當(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}稱為帶兩個(gè)吸收壁0和b的隨機(jī)游動(dòng)，它是一有限狀態(tài)馬爾可夫鏈。例4直線上的隨機(jī)游動(dòng)例5Polya（波利亞）模型

罐中有b只黑球及r只紅球，每次隨機(jī)地取出一只后把原球放回，并加入與抽出球同色的球c只，再第二次隨機(jī)地取球重復(fù)上面步驟進(jìn)行下去，{Xn=i}表示第n回摸球放回操作完成后，罐中有i只黑球這一事件，所以這是一個(gè)非齊次的馬爾可夫鏈，在傳染病研究中有用。例5Polya（波利亞）模型罐中

下面的定理提供了一個(gè)非常有用的獲得馬爾可夫鏈的方法，并可用于檢驗(yàn)一隨機(jī)過程是否為馬爾可夫鏈。定理：設(shè)隨機(jī)過程{Xn,n≥0}滿足（1）Xn=f(Xn-1,Yn),(n≥1),其中f:S×S→S,且Yn取值在S上，（2）{Yn,n≥1}為獨(dú)立同分布隨機(jī)變量，且X0與{Yn,n≥1}也相互獨(dú)立，則{Xn,n≥0}是馬爾可夫鏈，其一步轉(zhuǎn)移概率為

pij=P[f(i,Y1)=j]證明：設(shè)n≥1，則Yn+1與X0,X1,…,Xn相互獨(dú)立，事實(shí)上，

因?yàn)閄1=f(X0,Y1)，Y2與X0,Y1獨(dú)立，所以，

Y2與X1，X0獨(dú)立。同理，X2=f(X1,Y2)=f(f(X0,Y1),Y2)，所以，

Y3與X2，X1，X0獨(dú)立。歸納可得Yn+1與X0,X1,…,Xn相互獨(dú)立。下面的定理提供了一個(gè)非常有用的獲得馬爾可夫鏈所以{Xn,n≥0}是馬爾可夫鏈，且所以有所以{Xn,n≥0}是馬爾可夫鏈，且所以有二、切普曼-柯爾莫哥洛夫方程

顯然馬爾可夫鏈{Xn,n≥0}的一步轉(zhuǎn)移概率矩陣P為隨機(jī)矩陣。2，n步轉(zhuǎn)移概率定義：設(shè){Xn,n≥0}是一馬爾可夫鏈，稱1，隨機(jī)矩陣

定義：稱矩陣A=(aij)S×S為隨機(jī)矩陣，若aij≥0，且二、切普曼-柯爾莫哥洛夫方程顯然馬爾可夫鏈{X為馬爾可夫鏈{Xn,n≥0}的n步轉(zhuǎn)移概率。記稱為n時(shí)刻Xn的概率分布向量。稱為馬爾可夫鏈{Xn,n≥0}的初始分布向量。結(jié)論：一個(gè)馬爾可夫鏈的特性完全由它的一步轉(zhuǎn)移概率矩陣及初始分布向量決定。為馬爾可夫鏈{Xn,n≥0}的n步轉(zhuǎn)移概率。記稱為n時(shí)刻Xn

類似地可以證明馬爾可夫鏈任意個(gè)時(shí)刻的聯(lián)合分布也完全由一步轉(zhuǎn)移概率矩陣及初始分布向量決定。事實(shí)上類似地可以證明馬爾可夫鏈任意個(gè)時(shí)刻的聯(lián)合分布3、定理：切普曼-柯爾莫哥洛夫方程（C-K方程）或其中為馬爾可夫鏈{Xn,n≥0}的n步轉(zhuǎn)移概率矩陣。3、定理：切普曼-柯爾莫哥洛夫方程（C-K方程）或其中為馬爾證明：證明：

例（馬爾可夫預(yù)測(cè)）某種鮮奶A改變了廣告方式，經(jīng)調(diào)查發(fā)現(xiàn)購買A種鮮奶及另外三種鮮奶B、C、D的顧客每兩個(gè)月的平均轉(zhuǎn)換率為：（假設(shè)市場(chǎng)上只有這4種鮮奶）

A→A（95%）B（2%）C（2%）D（1%）

B→A（30%）B（60%）C（6%）D（4%）

C→A（20%）B（10%）C（7%）D（0%）

D→A（20%）B（20%）C（10%）D（50%）假設(shè)目前購買A、B、C、D4種鮮奶的顧客的分布為（25%，30%，35%，10%），求半年后鮮奶A、B、C、D的市場(chǎng)份額。例（馬爾可夫預(yù)測(cè)）某種鮮奶A改變了廣告方式解一階轉(zhuǎn)移矩陣為初始分布為解一階轉(zhuǎn)移矩陣為初始分布為則半年后A種鮮奶的市場(chǎng)占有率為則半年后A種鮮奶的市場(chǎng)占有率為（1）寫出狀態(tài)空間；（2）求P(2)；（3）問在甲獲得1分的情況下，再賽二局可以結(jié)束比賽的概率是多少？例甲、乙兩人進(jìn)行比賽，設(shè)每局比賽中甲勝的概率p，乙勝的概率是q，和局的概率是r,(p+q+r=1)。設(shè)每局比賽后，勝者記“+1”分，負(fù)者記“-1”分，和局不記分。當(dāng)兩人中有一人獲得2分結(jié)束比賽。以Xn表示比賽至第n局時(shí)甲獲得的分?jǐn)?shù)。（1）寫出狀態(tài)空間；（2）求P(2)；（3）問在甲獲得1分的

解（1）記甲獲得“負(fù)2分”為狀態(tài)1，獲得“負(fù)1分”為狀態(tài)2，獲得“0分”為狀態(tài)3，獲得“正1分”為狀態(tài)4，獲得“正2分”為狀態(tài)5，則狀態(tài)空間為一步轉(zhuǎn)移概率矩陣為解（1）記甲獲得“負(fù)2分”為狀態(tài)1，獲得“負(fù)1（2）二步轉(zhuǎn)移概率矩陣（2）二步轉(zhuǎn)移概率矩陣（3）在P2中P45(2)是在甲得1分的情況下經(jīng)二步轉(zhuǎn)移至2分從而結(jié)束比賽的概率；P41(2)是在甲得1分的情況下經(jīng)二步轉(zhuǎn)移至-2分（即乙得2分）從而結(jié)束比賽的概率。（3）在P2中P45(2)是在甲得1分的情況下經(jīng)二步轉(zhuǎn)移至2解例解例第5章-馬爾可夫鏈課件第5章-馬爾可夫鏈課件

某計(jì)算機(jī)房的一臺(tái)計(jì)算機(jī)經(jīng)常出故障,研究者每隔15分鐘觀察一次計(jì)算機(jī)運(yùn)行狀態(tài),收集了24小時(shí)的數(shù)據(jù)(共作97次觀察).用1表示正常狀態(tài),用0表示不正常狀態(tài),所得的數(shù)據(jù)序列如下:1110010011111110011110111111001111111110001101101分析狀態(tài)空間:I={0,1}.例111011011010111101110111101111110011011111100111某計(jì)算機(jī)房的一臺(tái)計(jì)算機(jī)經(jīng)常出故障,研究者11100196次狀態(tài)轉(zhuǎn)移的情況:因此,一步轉(zhuǎn)移概率可用頻率近似地表示為:96次狀態(tài)轉(zhuǎn)移的情況:因此,一步轉(zhuǎn)移概率可用頻率近似地表第二節(jié)狀態(tài)的分類及性質(zhì)

定義1:若存在某個(gè)n使得，則稱從狀態(tài)i可達(dá)狀態(tài)j，記為i→j，如果i→j且j→i

，則稱i與j相通，記為。若一馬爾可夫鏈的任意兩個(gè)狀態(tài)都是相通的，則稱該馬爾可夫鏈?zhǔn)遣豢杉s的。若pii=1。則稱狀態(tài)i為吸收態(tài)。定理：相通是一種等價(jià)關(guān)系。即第二節(jié)狀態(tài)的分類及性質(zhì)定義1:若存在某

定義2：若集合

則稱該數(shù)集的最大公約數(shù)d(i)為狀態(tài)i的周期。若d(i)>1，稱i為周期的，若d(i)=1，稱i為非周期的。

注意：若狀態(tài)i的周期為d,則對(duì)一切n≠0（mod(d)）都有,但并非對(duì)任意的n，都有。例如①②③④⑤⑥⑦⑧⑨定義2：若集合則稱該數(shù)集的最大公約數(shù)d(i)定理：則d(i)=d(j)。證明：若i與j相通，則存在m,n，使得對(duì)任意的s，若有，則則，對(duì)應(yīng)狀態(tài)1而言，集合的最大公約數(shù)為2，所以，。但是，當(dāng)時(shí)，。但可以證明：對(duì)于充分大的n，有。定理：則d(i)=d(j)。證明：若i與j

因?yàn)閐(i)是i的周期，所以d(i)應(yīng)同時(shí)整除n+m和n+m+s，則d(i)一定整除s，而d(j)是j的周期，所以d(i)整除d(j)。反過來也可證明d(j)整除d(i)，于是d(i)=d(j)。定義3：首達(dá)時(shí)間定義為若右邊為空集，則令

Tij表示從i出發(fā)首次到達(dá)j的時(shí)間，Tii表示從i出發(fā)首次回到i的時(shí)間.因?yàn)閐(i)是i的周期，所以d(i)應(yīng)同時(shí)整除n定義4：首達(dá)概率定義為表示從i經(jīng)n步首次到達(dá)j的概率。顯然有定義5fij表示過程從i出發(fā)在有限步內(nèi)能夠到達(dá)j的概率，（或者說從i出發(fā)遲早轉(zhuǎn)移到狀態(tài)j的概率）。fii表示過程從i出發(fā)在有限步內(nèi)（遲早）回到狀態(tài)i的概率。定義6:

若fii=1,則稱i為常返狀態(tài)，若fii<1,則稱i為非常返狀態(tài)（或瞬時(shí)狀態(tài)或稱滑過的）。定義4：首達(dá)概率定義為表示從i經(jīng)n步首次到達(dá)j的概率。顯然定義7:

若i為常返狀態(tài)，即fii=1,記稱為從狀態(tài)i出發(fā)再回到i的平均回轉(zhuǎn)時(shí)間（或平均回轉(zhuǎn)步數(shù)）。若，稱為正常返狀態(tài)，若，稱為零常返狀態(tài)。

定義8:

若狀態(tài)i是正常返的并且是非周期的，則稱狀態(tài)i為遍歷狀態(tài)。注：當(dāng)i為非常返狀態(tài)（滑過的）時(shí)，。定義7:若i為常返狀態(tài)，即fii=1,記稱定理：與有如下關(guān)系定理：與有如下關(guān)系定理：狀態(tài)i是常返狀態(tài)，當(dāng)且僅當(dāng)狀態(tài)i是非常返狀態(tài)，當(dāng)且僅當(dāng)證明：約定，定理：狀態(tài)i是常返狀態(tài)，當(dāng)且僅當(dāng)狀態(tài)i是非常返狀態(tài)，的含義則表示過程到達(dá)i

的次數(shù)。所以表示過程從i出發(fā)返回到i的平均次數(shù)。的含義則表示過程到達(dá)i的次數(shù)。所以表示過程從i出發(fā)返

若狀態(tài)i是滑過的（非常返的）則

即滑過狀態(tài)i只能有限次到達(dá)i。從而有限狀態(tài)的馬爾可夫鏈不可能全部狀態(tài)都是滑過的。即有限狀態(tài)的馬爾可夫鏈至少有一個(gè)狀態(tài)是常返的。定理：若，則i,j同為常返的和非常返的。即常返性具有類性質(zhì)。若為常返的，則它們同為正常返狀態(tài)或零常返狀態(tài)。證明：由，知存在n,m，使得，由C-K方程總有若狀態(tài)i是滑過的（非常返的）則所以，相互控制，同為無窮或有限，從而同為常返或非常返。所以，相互控制，同

以Nj(t)記到時(shí)刻t為止轉(zhuǎn)移到j(luò)的次數(shù)。若j是常返的，且X0=j，則因?yàn)橐坏┺D(zhuǎn)移到j(luò)，過程在概率上重新從頭開始，故{Nj(t),t≥0}是一個(gè)來到時(shí)間間隔分布為的更新過程。若X0=i，，且j是常返的，則{Nj(t),t≥0}是一個(gè)延遲更新過程，其初始來到時(shí)間間隔分布為。

為什么要將狀態(tài)進(jìn)行分類呢？

常返態(tài)表明，過程從常返狀態(tài)出發(fā)能無窮次返回該狀態(tài)，而滑過狀態(tài)最多只能有限次地返回，因此，隨著時(shí)間的發(fā)展，滑過狀態(tài)將逐漸消失。所以，在對(duì)Markov鏈作穩(wěn)態(tài)設(shè)計(jì)時(shí)，滑過狀態(tài)是不予考慮的，這也說明了區(qū)分常返態(tài)與滑過狀態(tài)是十分重要的。以Nj(t)記到時(shí)刻t為止轉(zhuǎn)移到j(luò)的例考慮直線上無限制的隨機(jī)游動(dòng)，狀態(tài)空間為轉(zhuǎn)移概率為則對(duì)于狀態(tài)0，有由斯特林(Stirling)公式可知：當(dāng)n充分大時(shí)有所以例考慮直線上無限制的隨機(jī)游動(dòng)，狀態(tài)空間為轉(zhuǎn)移概率為則對(duì)于狀注意到