第三章 馬爾可夫鏈

1、第三章 馬爾可夫鏈一、馬爾可夫鏈的概念馬爾可夫過(guò)程是一類有重要應(yīng)用意義的隨機(jī)過(guò)程，它具有如下特征：隨機(jī)過(guò)程將來(lái)所處的狀態(tài)僅與現(xiàn)在所處的狀態(tài)有關(guān)，而與過(guò)去曾處于什么狀態(tài)無(wú)關(guān)。馬爾可夫過(guò)程按其狀態(tài)和時(shí)間參數(shù)是離散還是連續(xù)的可以分成三類（1） 時(shí)間和狀態(tài)都是離散的馬爾可夫過(guò)程，稱為馬爾可夫鏈。（2） 時(shí)間連續(xù)、狀態(tài)離散的馬爾可夫過(guò)程，稱為連續(xù)時(shí)間的馬爾可夫鏈。（3） 時(shí)間和狀態(tài)都連續(xù)的馬爾可夫過(guò)程。本章介紹馬爾可夫鏈定義1 設(shè)為隨機(jī)序列，其狀態(tài)空間為，如果對(duì)任意正整數(shù)n及任意n+2個(gè)狀態(tài)，有 則稱此隨機(jī)序列為馬爾可夫鏈。若將時(shí)刻n稱為現(xiàn)在，將時(shí)刻n+1稱為將來(lái)，而把0，1，2，n-1稱為過(guò)去。定義中

2、的等式便可通俗解釋為：在已知 現(xiàn)在所處的狀態(tài)條件下，將來(lái)所要達(dá)到的狀態(tài)與過(guò)去所經(jīng)歷的狀態(tài)無(wú)關(guān)，這一特性常稱為馬爾可夫的無(wú)后效性。例1一個(gè)n級(jí)數(shù)字傳輸系統(tǒng)，每一級(jí)的輸入和輸出信號(hào)只取0或1兩個(gè)值，每一級(jí)的輸出是下一級(jí)的輸入；并假定當(dāng)一級(jí)輸入為0時(shí)，其輸出為0和為1的概率分別為p和1-p;當(dāng)輸入為1時(shí)，其輸出為1和0的概率分別為p和1-p（見(jiàn)圖） 令Xn表示第n級(jí)輸出，則 Xn,n0便為一個(gè)馬爾可夫鏈。例2從1，2，N數(shù)字中任取一個(gè)數(shù)，記為X0；再?gòu)?，2，X0數(shù)字中任取一個(gè)數(shù)，記為X1；再?gòu)?，2，X1中任取一個(gè)數(shù)，記為X2；依此類推，在1，2，Xn-1中任取一個(gè)數(shù)，記為Xn?？梢宰C明

3、 Xn,n0為馬爾可夫鏈。事實(shí)上， Xn,n0的狀態(tài)空間為I=1，2，N，對(duì)任意正整數(shù)n，取n+1個(gè)狀態(tài),由題意可知故 Xn,n0為馬爾可夫鏈。二、轉(zhuǎn)移概率由馬爾可夫鏈的無(wú)后效性和乘法公式有由此可見(jiàn)，馬爾可夫鏈的統(tǒng)計(jì)特性完全由條件概率所確定，所以如何確定這個(gè)條件概率就顯得非常重要，我們把這個(gè)條件概率稱為一步轉(zhuǎn)移概率。一般一步轉(zhuǎn)移概率為，它表示系統(tǒng)在時(shí)刻n處于狀態(tài)的條件下，到時(shí)刻n+1轉(zhuǎn)移到狀態(tài)的概率，記為。定義2 稱條件概率 為馬爾可夫鏈在時(shí)刻n的一步轉(zhuǎn)移概率。一般，轉(zhuǎn)移概率不僅與狀態(tài)有關(guān)，而且與時(shí)刻n有關(guān)，但當(dāng)它與時(shí)刻n無(wú)關(guān)時(shí)，表示馬爾可夫鏈具有平穩(wěn)轉(zhuǎn)移概率，即與起點(diǎn)無(wú)關(guān)，此時(shí)我們稱馬爾可夫

4、鏈?zhǔn)驱R次的。定義3 如果對(duì)任意的，馬爾可夫鏈的轉(zhuǎn)移概率與n無(wú)關(guān)，則稱為齊次馬爾可夫鏈，并記。下面我們只討論齊次馬爾可夫鏈。設(shè)P為一步轉(zhuǎn)移概率所組成的矩陣，狀態(tài)空間，稱P為馬爾可夫鏈的一步轉(zhuǎn)移概率矩陣。轉(zhuǎn)移概率矩陣具有下面性質(zhì)（1），（2），稱具有上面兩條性質(zhì)的矩陣為隨機(jī)矩陣。下面給出n步轉(zhuǎn)移概率的概念定義4 稱條件概率 ，為馬爾可夫鏈的n步轉(zhuǎn)移概率，并稱 P(n) 為馬爾可夫鏈的n步轉(zhuǎn)移概率矩陣。其中。當(dāng)n=1時(shí)，規(guī)定，即為單位矩陣。切普曼-柯爾莫哥洛夫方程定理1 設(shè)為馬爾可夫鏈，則對(duì)任意正整數(shù)n，和狀態(tài)，n步轉(zhuǎn)移概率具有下列性質(zhì)（1）（切普曼柯爾莫哥洛夫方程）（2）（3）（4）證明 （1）利

5、用全概率公式和馬爾可夫性，有（1）式是關(guān)于轉(zhuǎn)移概率的一個(gè)重要結(jié)果，切普曼-柯爾莫哥洛夫方程（簡(jiǎn)稱為C-K方程），直觀上可以作如下解釋：馬爾可夫鏈 Xn,n0在時(shí)刻m處于狀態(tài)，經(jīng)過(guò)n步，即在時(shí)刻m+n轉(zhuǎn)移到狀態(tài)的過(guò)程可以視為它在時(shí)刻m處于狀態(tài)，先經(jīng)過(guò)步，即在時(shí)刻遍歷所有狀態(tài)，然后再經(jīng)過(guò)步，即在時(shí)刻m+n轉(zhuǎn)到狀態(tài)的轉(zhuǎn)移過(guò)程（見(jiàn)下圖）         C-K方程的矩陣形式為 當(dāng)時(shí)，即為（3），再利用歸納法可證（4）在（1）中令，得 這是一個(gè)遞推公式，逐步遞推可證（2）例3（隨機(jī)游動(dòng)）設(shè)質(zhì)點(diǎn)在線段上做隨機(jī)游動(dòng)。（

6、見(jiàn)圖）。每隔一秒鐘移動(dòng)一步。當(dāng)質(zhì)點(diǎn)處于O點(diǎn)時(shí)，必然要以概率1向右移動(dòng)一步至1點(diǎn)；當(dāng)質(zhì)點(diǎn)處于4點(diǎn)時(shí)，下一步必然以概率1向左移動(dòng)一步至3點(diǎn)；當(dāng)質(zhì)點(diǎn)處于其它點(diǎn)時(shí)，下一步便均分別以概率 向左、向右或停留在原地不動(dòng)。令Xn表示n次移動(dòng)后質(zhì)點(diǎn)所處的位置。顯然， Xn,n0為一齊次馬爾可夫鏈，其狀態(tài)空間為I=0，1，2，3，4試求 Xn,n0的一步和二步轉(zhuǎn)移概率矩陣： 解：按題意可知同樣可求得其它轉(zhuǎn)移概率等等。于是便得一步轉(zhuǎn)移概率矩陣 二步轉(zhuǎn)移概率矩陣便為齊次馬爾可夫鏈的有限維分布   1. 一維分布定義5 設(shè)為齊次馬爾可夫鏈，其狀態(tài)空間為I，稱下列一組概率 ，為的初

7、始分布，稱為初始概率。將其寫成向量形式為 ，稱為初始概率向量。定義6 設(shè)為齊次馬爾可夫鏈，其狀態(tài)空間為I，稱下列一組概率 ，為的絕對(duì)分布，稱為絕對(duì)概率。將其寫成向量形式為 ，稱為絕對(duì)概率向量。定理2 設(shè)為齊次馬爾可夫鏈，則對(duì)任意和，絕對(duì)概率具有下列性質(zhì)（1）（2）（3）（4）證明 (1) （2）（3）（4）式是（1）（2）的矩陣形式。   2n維分布定理3 設(shè)為齊次馬爾可夫鏈，對(duì)任意和，則馬爾可夫鏈的n維分布有 此式證明利用了乘法公式和馬爾可夫的無(wú)后效性。（見(jiàn)教材P45）此式表明齊次馬爾可夫鏈的有限維分布同樣可由其初始分布和轉(zhuǎn)移概率而確定。例4 某計(jì)算機(jī)經(jīng)常出故障

8、?，F(xiàn)每隔15分鐘觀察一次此計(jì)算機(jī)的狀態(tài)，共收集97次觀察結(jié)果。用1表示工作正常，用0表示工作不正常，所測(cè)得數(shù)據(jù)如下：               令Xn表示第n個(gè)時(shí)間段計(jì)算機(jī)的狀態(tài)。顯然 Xn,n0為齊次馬爾可夫鏈。其狀態(tài)空間為I=0，1。由統(tǒng)計(jì)的結(jié)果可得轉(zhuǎn)移情況如下：利用頻率代替概率的原理，可得轉(zhuǎn)移概率             

9、0;                                 即得其轉(zhuǎn)移概率矩陣為                  假定

10、初始分布為 則此計(jì)算機(jī)能連續(xù)工作四個(gè)時(shí)間段（即一小時(shí)）的概率便為書上例題例1 無(wú)限制隨機(jī)游動(dòng)設(shè)質(zhì)點(diǎn)在數(shù)軸上移動(dòng)，每次移動(dòng)一格，向右移動(dòng)的概率為p，向左移動(dòng)的概率為q=1-p，這種運(yùn)動(dòng)稱為無(wú)限制隨機(jī)游動(dòng)，以表示質(zhì)點(diǎn)在時(shí)刻n所處的位置，則是一個(gè)齊次馬爾可夫鏈，試寫出它的一步轉(zhuǎn)移概率矩陣和k步轉(zhuǎn)移概率。解 顯然狀態(tài)空間為，一步轉(zhuǎn)移概率矩陣為設(shè)質(zhì)點(diǎn)在步轉(zhuǎn)移過(guò)程中向右移了步，向左移了步，并且經(jīng)過(guò)步轉(zhuǎn)移狀態(tài)從進(jìn)入，則 解出 ，由于是正整數(shù)，所以必須是偶數(shù)，又在步轉(zhuǎn)移中哪步向右哪步向左是任意的，于是 例2 賭徒輸光問(wèn)題兩賭徒甲、乙進(jìn)行一系列賭博，甲有元，乙有元，每賭一局輸者給贏者1元，沒(méi)有和局，直到兩人中有

11、一人輸光為止，設(shè)在每一局中，甲贏的概率為，輸?shù)母怕蕿?，求甲輸光的概率。這個(gè)問(wèn)題實(shí)際上是帶有兩個(gè)吸收壁的隨機(jī)游動(dòng)，狀態(tài)空間為，求質(zhì)點(diǎn)從狀態(tài)出發(fā)到達(dá)狀態(tài)0先于到達(dá)狀態(tài)c的概率。解 設(shè)表示甲從狀態(tài)出發(fā)轉(zhuǎn)移到狀態(tài)0的概率，現(xiàn)要計(jì)算。由于0和c是吸收狀態(tài)，故 由全概率公式 即 ，所以 這是一個(gè)差分方程，下面只討論的情況，此時(shí) 令 ，則，即 ，所以 ， 由于甲、乙的地位是對(duì)等的，同樣可計(jì)算出乙輸光的概率為 上式表明甲輸光的概率與乙的賭本成正比，所以賭本小者輸光的可能性大（輸贏等可能的情況下），又，表明必有一人要輸光，賭博遲早要結(jié)束。例3 天氣預(yù)報(bào)問(wèn)題設(shè)昨日、今日都下雨，明日有雨的概率為0.7；昨日無(wú)雨、今

12、日有雨，明日有雨的概率為0.5；昨日有雨、今日無(wú)雨，明日有雨的概率為0.4；昨日、今日都無(wú)雨，明日有雨的概率為0.2；若星期一、星期二均下雨，求星期四下雨的概率。解 設(shè)昨日、今日都有雨稱為狀態(tài)0（記為RR），昨日無(wú)雨、今日有雨稱為狀態(tài)1（記為NR），昨日有雨、今日無(wú)雨稱為狀態(tài)2（記為RN），昨日、今日都無(wú)雨稱為狀態(tài)3（記為NN），于是此問(wèn)題可看作是一個(gè)4狀態(tài)的馬爾可夫鏈，求現(xiàn)在處于狀態(tài)0的條件下將來(lái)處于狀態(tài)0或1的兩部轉(zhuǎn)移概率，下面求出一步概率轉(zhuǎn)移矩陣（不可能事件）（不可能事件）（不可能事件）（不可能事件）同樣方法可求出 ，所以一步轉(zhuǎn)移概率矩陣為所以星期一、星期二均下雨，星期四又下雨的概率為 =0.49+0.12