隨機(jī)過(guò)程第5章

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

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

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

4、, 使 的所有正整數(shù)n (n1)的最大公約數(shù), 稱為狀態(tài)i的周期周期, 記作d(i) 或 di . 如果對(duì)所有n1, 都有 , 則約定周期為;d(i)=1的狀態(tài)i稱為是非周期非周期的.0)(niip0)(niip推論推論: 如果n不能被周期d(i)整除, 則必有 .0)(niip注注: 當(dāng)狀態(tài)i的周期為d時(shí), 不一定成立.0)(diip試求狀態(tài)0的周期.例例2 若Markov鏈有狀態(tài)0,1,2,3和轉(zhuǎn)移概率矩陣05 . 005 . 0100001000010P解解: 狀態(tài)轉(zhuǎn)移可以用下圖表示試求狀態(tài)1的周期.練習(xí)練習(xí): 若Markov鏈有狀態(tài)1,2,3和轉(zhuǎn)移概率矩陣0105 . 005 . 00

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

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

7、對(duì)所有nN恒有 .0)(ndiip由引理3.1, 存在正整數(shù)N, 使得nN時(shí), 必有非負(fù)整數(shù)c1, c2,cm使 . 從而miiiscnd1 0)()()()(2211mmcsiicsiicsiindiipppp因?yàn)闋顟B(tài)空間有限, 對(duì)全部的狀態(tài)對(duì)(i,j), 求出N(i,j). 并取 , 則顯然對(duì)所有狀態(tài)i和j, 當(dāng)nN時(shí)有 .), (), (max), (jiNjimNji0)(nijp證證: 由于Markov鏈?zhǔn)遣豢杉s的, 過(guò)程的任兩個(gè)狀態(tài)i和j都是互達(dá)的, 于是m (與i和j有關(guān))使得 . 由推論3.1及鏈的非周期性知, 存在N, 使得當(dāng)nN時(shí), .0)(mijp0) 1(nmijp命題

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

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

10、例3.9 考慮整數(shù)點(diǎn)上的隨機(jī)游動(dòng). 向右移動(dòng)一格的概率為p, 向左移動(dòng)一格的概率為q=1-p. 從原點(diǎn)0出發(fā), 則一步轉(zhuǎn)移概率矩陣為:0000000000000000021012qpqpqpqpP所以, 2, 1, 02)2 (00) 12 (00nqpCppnnnnnn利用Stirling公式知, 當(dāng)n充分大時(shí)212!nnnen于是1,2121,1)4()2(00cpncpnnpqpnnn因此, 當(dāng)p=0.5時(shí) , 當(dāng)p0.5時(shí)1)(00nnp1)(00nnp即當(dāng)p=0.5時(shí)狀態(tài)0是常返的; 當(dāng)p0.5時(shí)0是瞬過(guò)的.定義定義 對(duì)常返狀態(tài)i我們定義Ti為首次返回狀態(tài)i的時(shí)刻, 即:稱作常返時(shí)常

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

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

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

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