概率統(tǒng)計(jì)及隨機(jī)過(guò)程：第十三章 馬爾可夫鏈

1、第十三章第十三章 馬爾可夫鏈馬爾可夫鏈 馬爾可夫過(guò)程是一類(lèi)特殊的隨機(jī)過(guò)程, 馬爾可夫鏈 是離散狀態(tài)的馬爾可夫過(guò)程,最初是由俄國(guó)數(shù)學(xué)家馬 爾可夫1896年提出和研究的. 應(yīng)用十分廣泛,其應(yīng)用領(lǐng)域涉及計(jì)算機(jī),通信,自動(dòng) 控制,隨機(jī)服務(wù),可靠性,生物學(xué),經(jīng)濟(jì),管理,教育,氣象, 物理,化學(xué)等等. 第一節(jié)第一節(jié): 馬爾可夫鏈的定義馬爾可夫鏈的定義 一定義1 設(shè)隨機(jī)過(guò)程 的狀態(tài)空間 是 ),(TttXS 有限集或可列集,對(duì)任意正整數(shù) 對(duì)于內(nèi)任意個(gè) , n 參數(shù) 和 內(nèi)任意 個(gè)狀態(tài) 121 nn ttttS1n , 121 nn jjjj 如果條件概率 )(,)(,)(|)( 221111nnnn jtX

2、jtXjtXjtXP 恒成立,則稱(chēng)此過(guò)程為馬爾可夫鏈. )(|)( 11nnnn jtXjtXP (13.1) 式(13.1)稱(chēng)為馬爾可夫性,或稱(chēng)無(wú)后效性. 馬氏性的直觀(guān)含義可以解釋如下: 將 看作為現(xiàn)在時(shí)刻,那末 ,就是過(guò)去時(shí) n t 121 , n ttt 刻,而 則是將來(lái)時(shí)刻.于是, (13.1) 式是說(shuō),當(dāng)已知 1n t 系統(tǒng)現(xiàn)時(shí)情況的條件下,系統(tǒng)將來(lái)的發(fā)展變化與系 統(tǒng)的過(guò)去無(wú)關(guān).我們稱(chēng)之為無(wú)后效性. 許多實(shí)際問(wèn)題都具有這種無(wú)后效性. 例如 生物基因遺傳從這一代到下一代的轉(zhuǎn)移中僅 依賴(lài)于這一代而與以往各代無(wú)關(guān). 二：馬爾可夫鏈的分類(lèi) 狀態(tài)空間 是離散的(有限集或可列集),參數(shù)集 ST

3、可為離散或連續(xù)的兩類(lèi). 三：離散參數(shù)馬爾可夫鏈 （1）轉(zhuǎn)移概率 定義2 在離散參數(shù)馬爾可夫鏈,),( 210 n ttttttX 中,條件概率 稱(chēng)為 在 )()(|)( 1mijmm tpitXjtXP )(tX 時(shí)刻(參數(shù)) 由狀態(tài) 一步轉(zhuǎn)移到狀態(tài) 的一步轉(zhuǎn)移 m tij 概率,簡(jiǎn)稱(chēng)轉(zhuǎn)移概率. 條件概率 稱(chēng)為 在時(shí) )()(|)( )( m n ijmnm tpitXjtXP )(tX n 刻(參數(shù)) 由狀態(tài) 經(jīng) 步轉(zhuǎn)移到狀態(tài) 的 步 m t i njn 轉(zhuǎn)移概率. (2)轉(zhuǎn)移概率的性質(zhì):對(duì)于狀態(tài)空間 內(nèi)的任意兩個(gè)S 狀態(tài) 和 ,恒有ij (1) 0)( )( m n ij tp (2) ,

4、 1)( )( m Sj n ij tp , 2 , 1n )( )( m Sj n ij tp )(|)(itXjtXP mnm Sj )( )(,)( itXP itXjtXP m Sj mnm )( )()( itXP itXjtXP m Sj mnm 1 )( )( itXP itXP m m 四.離散參數(shù)齊次馬爾可夫鏈 定義3 在離散參數(shù)馬爾可夫鏈 ,),( 210 n ttttttX 中,如果一步轉(zhuǎn)移概率 不依賴(lài)于參數(shù) ,即 )( mij tp m t 對(duì)任意兩個(gè)不等的參數(shù) 和 , 有 m t k tkm )()(|)( 1mijmm tpitXjtXP ijkijkk ptpit

5、XjtXP )()(|)( 1 則稱(chēng)此馬爾可夫鏈具有齊次性或時(shí)齊性,稱(chēng) )(tX 為離散參數(shù)齊次馬爾可夫鏈. 例1： Bernoulli序列是離散參數(shù)齊次馬爾可夫鏈. 第二節(jié)：參數(shù)離散的齊次馬爾可夫鏈 對(duì)離散參數(shù)齊次馬爾可夫鏈,本節(jié)討論以下四個(gè)問(wèn)題. 一：轉(zhuǎn)移概率矩陣 設(shè) 是齊次馬爾可夫鏈,由于狀 ,),( 210 n ttttttX 態(tài)空間 是離散的(有限集或可列集),不妨設(shè)其狀態(tài) S 空間 . , 2 , 1 , 0 nS 則對(duì)內(nèi)的任意兩個(gè)狀態(tài) 和 ,由轉(zhuǎn)移概率 排序i j ij p 一個(gè)矩陣 ijii j j ppp ppp ppp P 10 11110 00100 稱(chēng)為(一步)轉(zhuǎn)移概率

6、矩陣 )(|)( 1 itXjtXPp mmij 轉(zhuǎn)移概率矩陣的性質(zhì)： (1) ,即元素均非負(fù);0 ij p (2) ,即每行和為1.1 Sj ij p 具有以上兩個(gè)特點(diǎn)的方陣稱(chēng)為隨機(jī)矩陣. 轉(zhuǎn)移概率矩陣就是一個(gè)隨機(jī)矩陣. 例1 Bernoulli序列的狀態(tài)空間 ,轉(zhuǎn)移概率矩陣1 , 0S pq pq pp pp P 1110 0100 )(|)( 1 itXjtXPp mmij 1, 0, )( 1 jp jq jtXP m 例2：一維隨機(jī)游動(dòng) 一個(gè)質(zhì)點(diǎn)在直線(xiàn)上的五個(gè)位置:0,1,2,3,4之上隨機(jī) 游動(dòng).當(dāng)它處在位置1或2或3時(shí),以的1/3概率向左移 動(dòng)一步而以2/3的概率向右移動(dòng)一步;當(dāng)

7、它到達(dá)位置 0時(shí),以概率1返回位置1;當(dāng)它到達(dá)位置4時(shí)以概率1停 留在該位置上(稱(chēng)位置0為反射壁,稱(chēng)位置4為吸收壁). 例3（成功流） 設(shè)在一串貝努里試驗(yàn)中,每次試驗(yàn)成功的概率為 , p 令 nkknk n X n 1 , , 0 次成功次試驗(yàn)接連第第 次試驗(yàn)失敗第 則 是齊次馬爾可夫鏈.求轉(zhuǎn)移矩陣。 , 3 , 2 , 1, nX n 二：切普曼-柯?tīng)柲缏宸蚍匠?定理一 設(shè) 是馬爾可夫鏈,則有 ,),( 210 n ttttttX )()()( )()()( nm l kj k m n ikm ln ij tptptp (13.6) 稱(chēng)為切普曼-柯?tīng)柲缏宸蚍匠? 如果馬爾可夫鏈具有齊次性

8、,那么切普曼-柯?tīng)柲?洛夫方程化為 , )()()(l kj k n ik ln ij ppp (13.7) 當(dāng)時(shí) ,得到 1, 1ln kj k ikij ppp )2( 進(jìn)一步改寫(xiě)為矩陣形式 2)2( PP 其中 是兩步轉(zhuǎn)移概率矩陣, 是一步轉(zhuǎn)移)( )2()2( ij pPP 用數(shù)學(xué)歸納法可得 nn PP )( , 4 , 3 , 2n(13.8) 式(13.8)表明:步轉(zhuǎn)移概率矩陣 等于一步轉(zhuǎn) )( )()(n ij n pP 移概率矩陣 的 次冪.因此也常把 作為 步轉(zhuǎn)移 Pn n Pn 概率矩陣的符號(hào). 例4：在本節(jié)例2中,求 和 . )2( 00 p )2( 31 p 例5 傳

9、輸數(shù)字0和1的通訊系統(tǒng),每個(gè)數(shù)字的傳輸需 經(jīng)過(guò)若干步驟,設(shè)每步傳輸正確的概率為9/10,傳輸 錯(cuò)誤的概率為1/10,(1)問(wèn):數(shù)字1經(jīng)三步傳輸出1的概 率是多少? (2)若某步傳輸出數(shù)字1,那么又接連兩步 都傳輸出1的概率是多少? 三.有限維概率分布 馬爾可夫鏈 在初始時(shí)刻 的概率 ,),( 210 tttttX 0 t 稱(chēng)為初始分布. ,)()( 00 jtXPtp j , 2 , 1 , 0j分布: 初始分布與轉(zhuǎn)移概率完全地確定了馬爾可夫鏈的 任何有限維分布.下面的定理二正是論述這一點(diǎn). 不妨設(shè)齊次馬爾可夫鏈的參數(shù)集和狀態(tài)空間都是 非負(fù)整數(shù)集,那么有如下定理。 定理二 設(shè)齊次馬爾可夫鏈 的

10、狀態(tài) , 2 , 1 , 0),( nnX 空間 則對(duì)任意 個(gè)非負(fù)整數(shù) , 2 , 1 , 0 iSn n kkk 21和 內(nèi)的任意 個(gè)狀態(tài) Sn , 21n jjj 有 )(,)(,)( 2211nn jkXjkXjkXP )()()( 0 1 1 12 21 1 1 )0( nn nn kk jj kk jj k ij i i pppp (13.9) 例6 在本節(jié)例5中,設(shè)初始時(shí)輸入0和1的概率分別為 1/3和2/3,求第2、3、6步都傳輸出1的概率. 馬爾可夫鏈在任何時(shí)刻 的一維概率分布 n t ,)()(jtXPtp nnj , 2 , 1 , 0j 又稱(chēng)為絕對(duì)概率,或稱(chēng)為瞬時(shí)概率.

11、由全概率公式得 , )()()( 0 11 i nijninj tptptp , 2 , 1 , 0j 如果馬爾可夫鏈具有齊次性,那么上式化為 ,)()( 0 1 i ijninj ptptp , 2 , 1 , 0j(13.10) 由式(13.10)遞推得到 ,)()( 0 )( 0 i n ijinj ptptp , 2 , 1 , 0j (13.11) 式中 是初始時(shí)刻.式(13.11)表明:齊次馬爾可夫鏈 0 t 在時(shí)刻 的瞬時(shí)概率完全地由初始分布和 步轉(zhuǎn) n tn 移概率所確定. 將公式(13.11)寫(xiě)成向量形式得 ),(,),(),( 10 njnn tptptp )( 00100

12、 ),(,),(),( n j Ptptptp 步轉(zhuǎn)移概率矩陣 n nn ij n PpP)( )()( 例7 本節(jié)例2中,設(shè)質(zhì)點(diǎn)在初始時(shí)刻 恰處在狀態(tài)2, 0 t 試求在 時(shí)刻,質(zhì)點(diǎn)處在各個(gè)狀態(tài)的概率. 2 t 四.平穩(wěn)分布 如果一維分布 與 無(wú)關(guān),那么式(13.10)化為下式 )( nj tp n t (13.12),于是有 定義4 對(duì)于齊次馬爾可夫鏈 如果,),( 210 tttttX 存在概率分布 滿(mǎn)足 , j p , 2 , 1 , 0j , 0 i ijij ppp , 2 , 1 , 0j(13.12) 則稱(chēng) 為平穩(wěn)分布,稱(chēng) 具有平穩(wěn)性, , j p ), 2 , 1 , 0( j)(tX 是平穩(wěn)齊次馬爾可夫鏈. 改寫(xiě)成向量:平穩(wěn)分布律要滿(mǎn)足 ),( 210j ppppPpppp j ),( 210 并且有 1 0 j j p 定理 如果齊次馬爾可夫鏈 的初,),( 210 tttttX 始分布 ,)()( 00 jtXPtp j ), 2 , 1 , 0( j 是一個(gè)平穩(wěn) 分布,則 ),()()( 0 tpjtXPtp jnnj , 2 , 1 , 0j ), 2 , 1( n 例8 帶一個(gè)反射壁的一維隨機(jī)游動(dòng),以 表示 jtX n )( 在時(shí)刻 粒子處