Markov鏈的狀態(tài)分類與例子

1、1Markov鏈的狀態(tài)分類鏈的狀態(tài)分類互達性和周期性互達性和周期性定義定義1. 設(shè)i 和j 是時齊的Markov鏈的兩個狀態(tài), 如果存在n0, 使得 , 則稱從狀態(tài)i 可達可達狀態(tài)j, 記作ij. 反之, 以i j表示從狀態(tài)i 不可達不可達狀態(tài)j, 即對一切n0, .若ij且ji, 則稱狀態(tài)i和j互達互達(相通), 記作ij.0)(nijp0)(nijp注注: 引入互達性概念是為了對狀態(tài)進行分類.2命題命題1.1 互達性是等價關(guān)系, 即滿足:(1) 自反性: ii ;(2) 對成性: 若ij, 則ji ;(3) 傳遞性: 若ik 且kj, 則ij .證證: (3) 若ik 且kj, 則存在整數(shù)

2、n和m使得:. 0,0)()(mkjnikpp由Chapman-Kolmogorov方程得:. 0)()()()()(mkjnikrmrjnirmnijppppp即: ij. 類似可證ji. 3在數(shù)學上, 等價關(guān)系可以用于對集合進行分割. 因此, 我們也可以利用互達性對狀態(tài)空間進行分類, 并且這些類在互達關(guān)系下是等價類.定義定義2. 一個Markov鏈的狀態(tài)空間, 如果在互達性這一等價關(guān)系下都居于同一類, 那么就稱這個Markov鏈是不可約不可約的. 否則, 這個Markov鏈就被稱為是可約可約的.注注: 引入可約/不可約概念是為了以后研究狀態(tài)的周期,進一步是為了研究轉(zhuǎn)移概率的極限性質(zhì).4則顯

3、然1, 2和3, 4, 5是狀態(tài)在互達意義下的兩個等價類. 因此, 這個Markov鏈是可約的. 比如其中一個子鏈為:例例1. 若Markov鏈有轉(zhuǎn)移概率矩陣010005 . 005 . 000010000005 . 05 . 000075. 025. 0P5給出這個Markov鏈狀態(tài)的等價類, 并且試給出其n步轉(zhuǎn)移概率矩陣.例例2. 若Markov鏈有轉(zhuǎn)移概率矩陣4 . 0006 . 0006 . 0004 . 0001006 . 0004 . 0004 . 0006 . 0P答答: 等價類為: 1, 4, 2, 5和3. 其中3為吸收態(tài).622.0122.0122.0122.016.04.

4、04.06.0nnnnn用Mathematica軟件計算知:所以2)2 .0(12)2 .0(12)2 .0(12)2 .0(14 .06 .06 .04 .0nnnnn7定義定義3. 設(shè)i為Markov鏈的一個狀態(tài), 使 的所有正整數(shù)n (n1)的最大公約數(shù), 稱為狀態(tài)i的周期周期, 記作d(i) 或 di . 如果對所有n1, 都有 , 則約定周期為;d(i)=1的狀態(tài)i稱為是非周期非周期的.0)(niip0)(niip推論推論: 如果n不能被周期d(i)整除, 則必有 .0)(niip注注: 當狀態(tài)i的周期為d時, 不一定成立.0)(diip8試求狀態(tài)0的周期.例例3. 若Markov鏈

5、有狀態(tài)0,1,2,3和轉(zhuǎn)移概率矩陣05 . 005 . 0100001000010P解解: 狀態(tài)轉(zhuǎn)移可以用下圖表示9用數(shù)學歸納法不難求出:2,211)2(00npnn1,0,0) 12(00)2(00nppn所以 d(0) = 2. 10試求狀態(tài)1的周期.例例4. 若Markov鏈有狀態(tài)1,2,3和轉(zhuǎn)移概率矩陣0105 . 005 . 0010P解解: 狀態(tài)轉(zhuǎn)移可以用下圖表示11所以 d(1) = 2. 您能求出狀態(tài)您能求出狀態(tài)2的周期嗎的周期嗎?1,21, 0)2(11) 12(11nppnnn12命題命題2. 如果ij, 則 di = dj.證證: 設(shè)m1, n1,使得 , 則0,0)()

6、(njimijpp0, 0)()()()()()(mijnjimnjjnjimijnmiipppppp因此, m+n同時能被di及dj整除. 若 ,則0)(siip, 0)()()()(nijsiimjinsmjjpppp即: m+s+n也能被dj整除. 因此, s能被dj整除. 從而dj整除的 最大公因子di.根據(jù)對稱性, di也整除dj , 所以 di = dj .0:1)(miipm對于任意的s1滿足 , 則0)(siip13引理引理1. 設(shè)m2, 正整數(shù)s1, s2, sm的最大公因子為d, 則存在正整數(shù)N, 使得nN時, 必有非負整數(shù)c1, c2,cm使 .miiiscnd1我們引入

7、狀態(tài)周期概念的目的，是為了研究狀態(tài)轉(zhuǎn)移矩陣的極限性質(zhì)，即當n時P(n)的極限，這個矩陣可以反映出Markov鏈在平穩(wěn)狀態(tài)時的特征。因此，下面我們將討論周期的基本性質(zhì)，為此先給出一個數(shù)論中的結(jié)論：14推論推論1. 設(shè)狀態(tài)i的周期為di. 如果 , 則存在整數(shù)N, 使得對所有nN恒有. 0)(indmjip0)(mjip證證: 這時存在正整數(shù)s1, s2, sm, 使得它們的最大公因子為d, 且 .mkpksii, 2 , 1, 0)(命題命題3. 如果狀態(tài)i有周期d, 則存在整數(shù)N, 使得對所有nN恒有 .0)(ndiip由引理3.1, 存在正整數(shù)N, 使得nN時, 必有非負整數(shù)c1, c2,c

8、m使 . 從而miiiscnd1 0)()()()(2211mmcsiicsiicsiindiipppp15因為狀態(tài)空間有限, 對全部的狀態(tài)對(i,j), 求出N(i,j). 并取 , 則顯然對所有狀態(tài)i和j, 當nN時有 .), (), (max), (jiNjimNji0)(nijp證證: 由于Markov鏈是不可約的, 過程的任兩個狀態(tài)i和j都是互達的, 于是m (與i和j有關(guān))使得 . 由推論3.1及鏈的非周期性知, 存在N, 使得當nN時, .0)(mijp0) 1(nmijp命題命題4. 設(shè)P為一個不可約、非周期、有限狀態(tài)Markov鏈的轉(zhuǎn)移矩陣, 則必存在N, 使得當nN時, P

9、(n)的所有元素都大于0.1622.0122.0122.0122.01nnnnnP顯然這是一個不可約、非周期、有限狀態(tài)的Markov鏈.例例5. 若Markov鏈有轉(zhuǎn)移概率矩陣6 . 04 . 04 . 06 . 0P17 常返與瞬過常返與瞬過定義：定義：則 表示從狀態(tài)i出發(fā)在第n次轉(zhuǎn)移時首次到達狀態(tài)j的概率。0)0(ijf| 1, 1,0)(iXnkjXjXPfknnij)(nijf定義：定義：則 表示從狀態(tài)i出發(fā)在第n次轉(zhuǎn)移時首次回到狀態(tài)i的概率。0)0(iif| 1, 1,0)(iXnkiXiXPfknnii)(niif18定義：定義：則 表示從狀態(tài)i出發(fā)最終到達狀態(tài)j的概率.1)(nn

10、ijijffijf性質(zhì)：性質(zhì)：當i j 時, 則 i j fij 0. 定義定義5. 如果 fii = 1, 則稱狀態(tài)i是常返常返的. 否則, 即fii 0, 有0)(mjip0)(nijp因此,.1)()()(1)(1)(ssiinijmjisnsmjjkkjjppppp24例例6. 考慮整數(shù)點上的隨機游動. 向右移動一格的概率為p, 向左移動一格的概率為q=1-p. 從原點0出發(fā), 則一步轉(zhuǎn)移概率矩陣為:0000000000000000021012qpqpqpqpP25所以, 2, 1, 02)2 (00) 12 (00nqpCppnnnnnn利用Stirling公式知, 當n充分大時212!nnnen于是1,2121,1)4()2(00cpncpnnpqpnnn因此, 當p=0.5時 , 當p0.5時1)(00nnp1)(00nnp即當p=0.5時狀態(tài)0是常返的; 當p0.5時0是瞬過的.26定義定義 對常返狀