隨機過程第5章

1、5 5.3 Markov鏈的狀態(tài)分類鏈的狀態(tài)分類互達性和周期性互達性和周期性定義定義5.7 設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)進行分類.定理定理5.3 互達性是等價關系, 即滿足:(1) 自反性: ii ;(2) 對稱性: 若ij, 則ji ;(3) 傳遞性: 若ik 且kj, 則ij .證證: (3) 若ik 且kj,

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

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

4、, 使 的所有正整數(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)(diip試求狀態(tài)0的周期.例例2 若Markov鏈有狀態(tài)0,1,2,3和轉移概率矩陣05 . 005 . 0100001000010P解解: 狀態(tài)轉移可以用下圖表示試求狀態(tài)1的周期.練習練習: 若Markov鏈有狀態(tài)1,2,3和轉移概率矩陣0105 . 005 . 00

5、10P解解: 狀態(tài)轉移可以用下圖表示命題命題5.4如果ij, 則 di = dj.證證: 設m1, n1,使得 , 則0,0)()(njimijpp0, 0)()()()()()(mijnjimnjjnjimijnmiipppppp因此, m+n同時能被di及dj整除. 對于任意的s1 , 0)()()()(nijsiimjinsmjjpppp即: m+s+n也能被dj整除. 因此, s能被dj整除. 從而dj整除的 最大公因子di.根據(jù)對稱性, di也整除dj , 所以 di = dj .0:1)(miipm滿足 , 則0)(siip引理引理5.1 設m2, 正整數(shù)s1, s2, sm的最大

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

7、對所有nN恒有 .0)(ndiip由引理3.1, 存在正整數(shù)N, 使得nN時, 必有非負整數(shù)c1, c2,cm使 . 從而miiiscnd1 0)()()()(2211mmcsiicsiicsiindiipppp因為狀態(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有關)使得 . 由推論3.1及鏈的非周期性知, 存在N, 使得當nN時, .0)(mijp0) 1(nmijp命題

8、命題5.4 設P為一個不可約、非周期、有限狀態(tài)Markov鏈的轉移矩陣, 則必存在N, 使得當nN時, P(n)的所有元素都大于0.22.0122.0122.0122.01nnnnnP顯然這是一個不可約、非周期、有限狀態(tài)的Markov鏈.例例3 若Markov鏈有轉移概率矩陣6 . 04 . 04 . 06 . 0P常返和暫留31.從一個狀態(tài)出發(fā)是不是一定能夠在有限時間內(nèi)返問題：回該狀態(tài)？2.如果能夠返回，那么平均返回時間（） 一定平均回轉時有限嗎？3.如果能夠返回，那么平均返回時間的精確值是多少？（常返，暫留）正常返，（零常返）（平穩(wěn)分布） 常返與瞬過常返與瞬過定義：定義：則 表示從狀態(tài)i出

9、發(fā)在第n次轉移時首次到達狀態(tài)j的概率。0)0(ijf| 1, 1,0)(iXnkjXjXPfknnij)(nijf定義：定義：則 表示從狀態(tài)i出發(fā)在第n次轉移時首次回到狀態(tài)i的概率。0)0(iif| 1, 1,0)(iXnkiXiXPfknnii)(niif定義：定義：則 表示從狀態(tài)i出發(fā)最終到達狀態(tài)j的概率.1)(nnijijffijf性質(zhì)：性質(zhì)：當i j 時, 則 i j fij 0. 定義定義5.5 如果 fii = 1, 則稱狀態(tài)i是常返常返的. 否則, 即fii 0, 有0)(mjip0)(nijp因此,.1)()()(1)(1)(ssiinijmjisnsmjjkkjjppppp例

10、例3.9 考慮整數(shù)點上的隨機游動. 向右移動一格的概率為p, 向左移動一格的概率為q=1-p. 從原點0出發(fā), 則一步轉移概率矩陣為:0000000000000000021012qpqpqpqpP所以, 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是瞬過的.定義定義 對常返狀態(tài)i我們定義Ti為首次返回狀態(tài)i的時刻, 即:稱作常返時常

11、返時. 記 , 則有 , 所以是首次返回i的期望步數(shù), 叫作狀態(tài)i的平均常返時平均常返時.| 1, 1,:1inf0iXnkiXiXnTkni)(iiTE1)(nniiinf定義定義 一個常返狀態(tài)i當且僅當i=時稱為是零零常返常返的, 當且僅當i0（每一分量均大于0），則稱此馬爾鏈為一正則鏈正則鏈(regular chain)補充：正則鏈與吸收鏈補充：正則鏈與吸收鏈定理定理C1. 若A為正則鏈的轉移矩陣，則必有：(1) ，其中W為任一分量均大于零的隨機矩陣；(2) W的所有行向量均相同WPnnlim定理定理C2. 記定理 C1中W的行向量為=(1, m)，則：(1) 對任意隨機向 量x，有 ；

12、(2) 是P的不動點向量,即P=, P的不動點向量是唯一的nnxPlim定義定義C2. 狀態(tài)Si 稱為馬氏鏈的吸收狀態(tài)吸收狀態(tài)，若轉移矩陣P的第i 行滿足：Pii=1，Pij=0 (ji)定義定義C3. 馬氏鏈被稱為吸收鏈吸收鏈，若其滿足：(1) 至少存在一個吸收狀態(tài) ；(2) 從任一狀態(tài)出發(fā)，經(jīng)有限步轉移總可到達某一吸收 狀態(tài)根據(jù)定義C3，例例3.1中Xn即為一吸收鏈 具有r個吸收狀態(tài)，mr個非吸收狀態(tài)的吸收鏈，它的mm轉移矩陣P的標準形式為QROIPr其中Ir為r 階單位陣，O為r(m-r)零陣，R為(m-r)r 矩陣，Q為(m-r)(m-r)矩陣令B=(IQ) -1，稱B為基矩陣基矩陣定

13、理定理C3. 吸收鏈的基矩陣B中的每個元素，表示過程從一個非吸收狀態(tài)出發(fā)到達每個非吸收狀態(tài)的平均轉移次數(shù)定理定理C4. 設N=BC, B為吸收鏈的基矩陣, C=(1,1,1)T，則N的每個元素表示從非吸收狀態(tài)出發(fā)，到達某個吸收狀態(tài)被吸收之前的平均轉移次數(shù)定理定理C5. 設F=BR=(fij)，其中B為吸收鏈的基矩陣，R為T中的子陣，則fij表示從非吸收狀態(tài)i出發(fā)，被吸收狀態(tài) j吸收的概率例例C1.1 (競賽問題競賽問題)甲乙兩隊進行一場搶答競賽，競賽規(guī)則規(guī)定：開始時每隊各記2分，搶答題開始后，如甲取勝則甲加1分而乙減1分，反之則乙加1分甲減1分 (每題必需決出勝負 )規(guī)則還規(guī)定，當其中一方的得

14、分達 到4分時，競賽結束求： (1) 甲隊獲勝的概率有多大？ (2) 競賽從開始到結束，平均轉移的次數(shù)為多少？(3) 甲獲得1、2、3分的平均次數(shù)是多少？設甲取勝一題的概率為p (0p1)，p與兩隊的實力有關甲隊得分有5種可能，即0，1，2，3，4我們分別記為狀態(tài)S0，S1，S2，S3，S4，其中S0和S4是吸收狀態(tài)，S1，S2和S3是非吸收狀態(tài)過程以S2作為初始狀態(tài)根據(jù)甲隊贏得1分的概率為p，建立轉移矩陣P：100000100001000010000143210ppppppSSSSSPS 0 S 1 S 2 S 3 S 4 將上式改記為標準形 式T：QRIT02其中 0100100 ,00001ppppQppR計算基矩陣B：10100100100010001ppppB記q=1-p，則pqqqpqpppqpqB1112112211101101pppp因為S2是初始狀態(tài)，根據(jù)定理C3，甲隊獲分為1，2，3分的平均次數(shù)為 又 111 11121122pqqqpqpppqpqBCN.21,211,21pqppqpqq2221221211qppq根據(jù)定理C4，以S2為初始狀態(tài)，甲隊最終獲勝的平均轉移次數(shù)為pq2