第4章馬爾可夫鏈

1、第4章 馬爾可夫鏈,馬爾可夫過(guò)程按其狀態(tài)和時(shí)間參數(shù)是連續(xù)的或離散的，可分為三類(lèi)： （1）時(shí)間、狀態(tài)都是離散的馬爾可夫過(guò)程，稱(chēng)為馬爾可夫鏈。 （2）時(shí)間連續(xù)、狀態(tài)離散的馬爾可夫過(guò)程，稱(chēng)為連續(xù)時(shí)間的馬爾可夫鏈。 （3）時(shí)間、狀態(tài)都連續(xù)的馬爾可夫過(guò)程。,4.1 馬爾可夫鏈的概念及轉(zhuǎn)移概率,一、馬爾可夫鏈的定義,上式是馬爾可夫鏈的馬氏性（或無(wú)后效性）的數(shù)學(xué)表達(dá)式。由定義知,可見(jiàn)，馬爾可夫鏈的統(tǒng)計(jì)特性完全由條件概率,所決定。,二、轉(zhuǎn)移概率,下面我們只討論齊次馬爾可夫鏈，通常將“齊次”兩字省略。,稱(chēng)為系統(tǒng)狀態(tài)的一步轉(zhuǎn)移概率矩陣。它具有性質(zhì)：,(2)式中對(duì)j求和是對(duì)狀態(tài)空間I的所有可能狀態(tài)進(jìn)行的，此性質(zhì)說(shuō)明

2、一步轉(zhuǎn)移概率矩陣中任一行元素之和為1。通常稱(chēng)滿(mǎn)足上述(1)，(2)性質(zhì)的矩陣為隨機(jī)矩陣。,證 (1)利用全概率公式及馬爾可夫性，有,(3)在(1)中令l=1，利用矩陣乘法可證。 (4)由(3)，利用歸納法可證。,定理1中(1)式稱(chēng)為切普曼-柯?tīng)柲缏宸蚍匠?，?jiǎn)稱(chēng)C-K方程。它在馬爾可夫鏈的轉(zhuǎn)移概率的計(jì)算中起著重要的作用。(2)式說(shuō)明n步轉(zhuǎn)移概率完全由一步轉(zhuǎn)移概率決定。(4)式說(shuō)明齊次馬爾可夫鏈的n步轉(zhuǎn)移概率矩陣是一步轉(zhuǎn)移概率矩陣的n次乘方。,由（1）知，絕對(duì)概率由初始分布和n步轉(zhuǎn)移概率完全確定,（1）,證,三、馬爾可夫鏈的一些簡(jiǎn)單例子,例1 無(wú)限制隨機(jī)游動(dòng),設(shè)在第k步轉(zhuǎn)移中向右移了x步，向左移

3、了y步，且經(jīng)過(guò)k步轉(zhuǎn)移狀態(tài)從i進(jìn)入j，則,從而,分析,例2 賭徒輸光問(wèn)題,賭徒甲有資本a元，賭徒乙有資本b元，兩人進(jìn)行賭博，每賭一局輸者給贏(yíng)者1元，沒(méi)有和局，直賭至兩人中有一人輸光為止。設(shè)在每一局中，甲獲勝的概率為p，乙獲勝的概率為 ，求甲輸光的概率。,這個(gè)問(wèn)題實(shí)質(zhì)上是帶有兩個(gè)吸收壁的隨機(jī)游動(dòng)。從甲的角度看，他初始時(shí)刻處于a，每次移動(dòng)一格，向右移（即贏(yíng)1元）的概率為p，向左移（即輸1元）的概率為q。如果一旦到達(dá)0（即甲輸光）或a + b（即乙輸光）這個(gè)游動(dòng)就停止。這時(shí)的狀態(tài)空間為0，1，2，c，c = a + b，?，F(xiàn)在的問(wèn)題是求質(zhì)點(diǎn)從a出發(fā)到達(dá)0狀態(tài)先于到達(dá)c狀態(tài)的概率。,考慮質(zhì)點(diǎn)從j出發(fā)移

4、動(dòng)一步后的情況,解,同理,根據(jù)全概率公式有,這一方程實(shí)質(zhì)上是一差分方程，它的邊界條件是,于是,設(shè),則可得到兩個(gè)相鄰差分間的遞推關(guān)系,于是,欲求,先求,需討論 r,當(dāng),而,兩式相比,故,當(dāng),而,因此,故,用同樣的方法可以求得乙先輸光的概率,由以上計(jì)算結(jié)果可知,例3 天氣預(yù)報(bào)問(wèn)題 設(shè)昨日、今日都下雨，明日有雨的概率為0.7；昨日無(wú)雨，今日有雨，明日有雨的概率為0.5；昨日有雨，今日無(wú)雨，明日有雨的概率為0.4；昨日、今日均無(wú)雨，明日有雨的概率為0.2。若星期一、星期二均下雨，求星期四下雨的概率。,解：設(shè)昨日、今日連續(xù)有雨稱(chēng)為狀態(tài)(RR) ，昨日無(wú)雨、今日有雨稱(chēng)為狀態(tài)(NR)，昨日有雨、今日無(wú)雨稱(chēng)為

5、狀態(tài)2(RN)，昨日、今日無(wú)雨稱(chēng)為狀態(tài)(NN)，于是天氣預(yù)報(bào)模型可以看著一個(gè)四個(gè)狀態(tài)的馬爾可夫鏈，轉(zhuǎn)移概率為,其中R代表有雨，N代表無(wú)雨。類(lèi)似可得所有狀態(tài)的一步轉(zhuǎn)移概率。其一步轉(zhuǎn)移概率矩陣為,其兩步轉(zhuǎn)移概率矩陣為,由于星期四下雨意味著過(guò)程說(shuō)處的狀態(tài)為或，因此星期一、星期二連續(xù)下雨，星期四下雨的概率為,某計(jì)算機(jī)房的一臺(tái)計(jì)算機(jī)經(jīng)常出故障,研究者 每隔15分鐘觀(guān)察一次計(jì)算機(jī)運(yùn)行狀態(tài),收集了24小 時(shí)的數(shù)據(jù) (共作97次觀(guān)察) . 用1表示正常狀態(tài), 用0 表示不正常狀態(tài), 所得的數(shù)據(jù)序列如下:,111001000011110111111001111111110001101101,分析,狀態(tài)空間: I

6、=0, 1.,例7,111011011010111101110111101111110011011111100111,96 次狀態(tài)轉(zhuǎn)移的情況:,因此, 一步轉(zhuǎn)移概率可用頻率近似地表示為:,以下研究齊次馬氏鏈的有限維分布.,特點(diǎn):,用行向量表示為,一維分布由初始分布和 轉(zhuǎn)移概率矩陣決定,馬氏鏈的 n 維分布,有限維分布仍由初始分布 和轉(zhuǎn)移概率矩陣決定,一步轉(zhuǎn)移概率為,例8,解,先求出二步轉(zhuǎn)移概率矩陣,于是:,把兩只黑球和兩只白球平均放在兩個(gè)壇子中, 每次從壇子中隨機(jī)地各取出一球, 然后把被取出的球交換放到壇子中. 設(shè) X(0) 表示開(kāi)始時(shí)第一個(gè)壇子中的白球數(shù),說(shuō)明 X(n) 構(gòu)成一個(gè)齊次馬爾可夫

7、鏈, 并寫(xiě)出狀態(tài)空間.,(2) 寫(xiě)出一步和二步轉(zhuǎn)移概率矩陣.,例9,解,4.2 馬爾可夫鏈的狀態(tài)分類(lèi),一、狀態(tài)分類(lèi),注： 從狀態(tài)是否常返，如常返的話(huà)是否正常返，如正常返的話(huà)是否非周期等三層次上將狀態(tài)區(qū)分為以下的類(lèi)型：,證,證 令,從而由歸納法，我們有d=t證畢。,求從狀態(tài)1出發(fā)經(jīng)n步轉(zhuǎn)移 首次到達(dá)各狀態(tài)的概率。,解 如用（4.16）式計(jì)算將會(huì)很復(fù)雜，我們直接通過(guò)狀態(tài)轉(zhuǎn)移圖（4.5）來(lái)計(jì)算。利用歸納法可得,同理可得,二、常返態(tài)的判別及其性質(zhì),對(duì)于常返態(tài)i，為判別它是遍歷或零常返，我們不加證明地給出下面定理。,由C-K方程，總有,-(4.27),-(4.28),(2) 仍令,下面先看上節(jié)的一個(gè)例題

8、,(4.29),對(duì)固定的狀態(tài)k，記,則由全概率公式,(4.30),上式兩邊求和注意U(k)=0，得,由（4.30）式得,由此知狀態(tài)0是常返的。,4.3 狀態(tài)空間的分解,引理得證。,閉集的意思是自C的內(nèi)部不能到達(dá)C的外部。這意味著一旦質(zhì)點(diǎn)進(jìn)入閉集C中，它將永遠(yuǎn)留在C中運(yùn)動(dòng)。,稱(chēng)狀態(tài)I為吸收的，如=1。顯然狀態(tài)i吸收等價(jià)于單點(diǎn)集i為閉集。,例4.12 無(wú)限制隨機(jī)游動(dòng)為不可約馬氏鏈，各狀態(tài)的周期為2且是正常返的。,我們知道自常返狀態(tài)只能到達(dá)常返狀態(tài)，因此I中全體常返狀態(tài)組成一閉集C。在C中互通關(guān)系具有自返性，對(duì)稱(chēng)性和傳遞性，因而它決定一分類(lèi)關(guān)系。按互通關(guān)系我們可得到狀態(tài)空間的分解定理。,證 記C為全

9、體常返狀態(tài)所成的集合, D=I-C為非常返狀態(tài)全體。將C按互通關(guān)系進(jìn)行分解，則,試分解此鏈并指出各狀態(tài)的常返性及周期性。,可見(jiàn)1為正常返狀態(tài)且周期等于3。含1的基本常返閉集為,從而狀態(tài)3及5也為正常返且周期為3。同理可知6為正常返狀態(tài)。,可見(jiàn)2是遍歷狀態(tài)。,IDC1C241,3,52,6。,定理4.11 周期為d的不可約馬氏鏈，其狀態(tài)空間C可唯一地分解為d個(gè)互不相交地子集之和，即,實(shí)際上,例4.14 設(shè)不可約馬氏鏈的狀態(tài)空間為C=1,2,3,4,5,6，轉(zhuǎn)移陣為,由右狀態(tài)轉(zhuǎn)移圖易見(jiàn)各狀態(tài)的周期d=3。今固定狀態(tài)i=1，令,故,此鏈在C中的運(yùn)動(dòng)如圖,例 設(shè)X為一齊次馬氏鏈，狀態(tài)空間為Sa,b,c

10、,d,e，轉(zhuǎn)移概率矩陣為,試分析其狀態(tài)類(lèi)型。,解 畫(huà)出其狀態(tài)轉(zhuǎn)移概率圖，如下頁(yè)圖所示。從圖中不難發(fā)現(xiàn)Ca,c,e是一個(gè)狀態(tài)閉集，Db,d是非常返態(tài)集，自然C是正常返的而且是非周期的。,如果我們能夠發(fā)現(xiàn)轉(zhuǎn)移矩陣能夠重排為,這相當(dāng)于將狀態(tài)的次序重排為Sa,c,e,b,d。由上及P的標(biāo)準(zhǔn)形式即知非常返態(tài)集Db,d和遍歷態(tài)集Ca,c,e。D和C也是S的兩個(gè)等價(jià)類(lèi)，顯然C是閉集，D不是閉集。,例 設(shè)一齊次馬氏鏈的狀態(tài)空間為S1,2,3,4,5,6,7,8，轉(zhuǎn)移概率矩陣為,例 設(shè)一齊次馬氏鏈的狀態(tài)空間為S1,2,3,4,5,6,7,8,9，其轉(zhuǎn)移概率矩陣有如下形式：,其中*表示正的一個(gè)數(shù)，其余均為零。試確

11、定此齊次馬氏鏈的狀態(tài)類(lèi)型。,例 設(shè)一齊次馬氏鏈的狀態(tài)空間為S0,1,2,，其轉(zhuǎn)移矩陣如下（狀態(tài)轉(zhuǎn)移圖如下）：,試討論此鏈?zhǔn)浅７垫湹某浞直匾獥l件。,4.4 的漸近性質(zhì)與平穩(wěn)分布,證 由定理4.4，對(duì)Nn我們有,推論1 有限狀態(tài)的馬氏鏈，不可能全是非常返狀態(tài)，也不可能含有零常返狀態(tài)，從而不可約的有限馬氏鏈必為正常返的。,這就產(chǎn)生了矛盾。,矛盾,證畢。,推論2 如馬氏鏈有一個(gè)零常返狀態(tài)，則必有無(wú)限多個(gè)零常返狀態(tài)。,則我們有下面一般性定理。,因此（4.37）式得證。,定理 4.15 對(duì)任意狀態(tài)i,j有,二、平穩(wěn)分布,根據(jù)歸納法可得,故有,事實(shí)上，因?yàn)?如此類(lèi)推即可得。,再證必要性，設(shè)馬氏鏈?zhǔn)钦７档?，于?由C-K方程，對(duì)任意正數(shù)N，有,下面要進(jìn)一步證明等號(hào)成立，由,(I),將(I)式對(duì)j求和，并假定對(duì)某個(gè)j， (I)式為嚴(yán)格大于，則,于是有自相矛盾得結(jié)果：,故有,推論1 有限狀態(tài)的不可約非周期馬爾可夫鏈必存在平穩(wěn)分布。,推論