第4章馬爾可夫鏈

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

2、一步轉移概率矩陣中任一行元素之和為1。通常稱滿足上述(1)，(2)性質的矩陣為隨機矩陣。,證 (1)利用全概率公式及馬爾可夫性，有,(3)在(1)中令l=1，利用矩陣乘法可證。 (4)由(3)，利用歸納法可證。,定理1中(1)式稱為切普曼-柯爾莫哥洛夫方程，簡稱C-K方程。它在馬爾可夫鏈的轉移概率的計算中起著重要的作用。(2)式說明n步轉移概率完全由一步轉移概率決定。(4)式說明齊次馬爾可夫鏈的n步轉移概率矩陣是一步轉移概率矩陣的n次乘方。,由（1）知，絕對概率由初始分布和n步轉移概率完全確定,（1）,證,三、馬爾可夫鏈的一些簡單例子,例1 無限制隨機游動,設在第k步轉移中向右移了x步，向左移

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

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

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

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

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

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

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

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

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