1、a,1,3.2 Markov鏈的狀態(tài)分類,互達(dá)性和周期性,注: 引入互達(dá)性概念是為了對(duì)狀態(tài)進(jìn)行分類.,a,2,命題3.1 互達(dá)性是等價(jià)關(guān)系, 即滿足: (1) 自反性: ii ; (2) 對(duì)稱性: 若ij, 則ji ; (3) 傳遞性: 若ik 且kj, 則ij .,證: (3) 若ik 且kj, 則存在整數(shù)n和m使得:,由Chapman-Kolmogorov方程得:,即: ij. 類似可證ji.,a,3,在數(shù)學(xué)上, 等價(jià)關(guān)系可以用于對(duì)集合進(jìn)行分割. 因此, 我們也可以利用互達(dá)性對(duì)狀態(tài)空間進(jìn)行分類, 并且這些類在互達(dá)關(guān)系下是等價(jià)類.,定義3.4 一個(gè)Markov鏈的狀態(tài)空間, 如果在互達(dá)性這一

2、等價(jià)關(guān)系下都居于同一類, 那么就稱這個(gè)Markov鏈?zhǔn)遣豢杉s的. 否則, 這個(gè)Markov鏈就被稱為是可約的.,注: 引入可約/不可約概念是為了以后研究狀態(tài)的周期,進(jìn)一步是為了研究轉(zhuǎn)移概率的極限性質(zhì).,a,4,則顯然1, 2和3, 4, 5是狀態(tài)在互達(dá)意義下的兩個(gè)等價(jià)類. 因此, 這個(gè)Markov鏈?zhǔn)强杉s的. 比如其中一個(gè)子鏈為:,例3.6 若Markov鏈有轉(zhuǎn)移概率矩陣,a,5,給出這個(gè)Markov鏈狀態(tài)的等價(jià)類, 并且試給出其n步轉(zhuǎn)移概率矩陣.,練習(xí): 若Markov鏈有轉(zhuǎn)移概率矩陣,答: 等價(jià)類為: 1, 4, 2, 5和3. 其中3為吸收態(tài).,a,6,用Mathematica軟件計(jì)算知

3、:,所以,a,7,a,8,定義3.5 設(shè)i為Markov鏈的一個(gè)狀態(tài), 使 的所有正整數(shù)n (n1)的最大公約數(shù), 稱為狀態(tài)i的周期, 記作d(i) 或 di . 如果對(duì)所有n1, 都有 , 則約定周期為; d(i)=1的狀態(tài)i稱為是非周期的.,推論: 如果n不能被周期d(i)整除, 則必有 .,注: 當(dāng)狀態(tài)i的周期為d時(shí), 不一定成立.,a,9,解: 狀態(tài)轉(zhuǎn)移可以用下圖表示,a,10,用數(shù)學(xué)歸納法不難求出:,所以 d(0) = 2.,a,11,解: 狀態(tài)轉(zhuǎn)移可以用下圖表示,a,12,所以 d(1) = 2. 您能求出狀態(tài)2的周期嗎?,a,13,命題3.2 如果ij, 則 di = dj.,證

4、: 設(shè)m1, n1,使得 , 則,因此, m+n同時(shí)能被di及dj整除. 對(duì)于任意的s1,即: m+s+n也能被dj整除. 因此, s能被dj整除. 從而dj整除的 最大公因子di. 根據(jù)對(duì)稱性, di也整除dj , 所以 di = dj .,滿足 , 則,a,14,引理3.1 設(shè)m2, 正整數(shù)s1, s2, sm的最大公因子為d, 則存在正整數(shù)N, 使得nN時(shí), 必有非負(fù)整數(shù)c1, c2,cm使 .,我們引入狀態(tài)周期概念的目的，是為了研究狀態(tài)轉(zhuǎn)移矩陣的極限性質(zhì)，即當(dāng)n時(shí)P(n)的極限，這個(gè)矩陣可以反映出Markov鏈在平穩(wěn)狀態(tài)時(shí)的特征。因此，下面我們將討論周期的基本性質(zhì)，為此先給出一個(gè)數(shù)論中

5、的結(jié)論：,a,15,推論3.1 設(shè)狀態(tài)i的周期為di. 如果 , 則存在整數(shù)N, 使得對(duì)所有nN恒有,證: 這時(shí)存在正整數(shù)s1, s2, sm, 使得它們的最大公因子為d, 且 .,命題3.3 如果狀態(tài)i有周期d, 則存在整數(shù)N, 使得對(duì)所有nN恒有 .,由引理3.1, 存在正整數(shù)N, 使得nN時(shí), 必有非負(fù)整數(shù)c1, c2,cm使 . 從而,a,16,因?yàn)闋顟B(tài)空間有限, 對(duì)全部的狀態(tài)對(duì)(i,j), 求出N(i,j). 并取 , 則顯然對(duì)所有狀態(tài)i和j, 當(dāng)nN時(shí)有 .,證: 由于Markov鏈?zhǔn)遣豢杉s的, 過(guò)程的任兩個(gè)狀態(tài)i和j都是互達(dá)的, 于是m (與i和j有關(guān))使得 . 由推論3.1及鏈

6、的非周期性知, 存在N, 使得當(dāng)nN時(shí), .,命題3.4 設(shè)P為一個(gè)不可約、非周期、有限狀態(tài)Markov鏈的轉(zhuǎn)移矩陣, 則必存在N, 使得當(dāng)nN時(shí), P(n)的所有元素都大于0.,a,17,a,18,常返與瞬過(guò),定義： 則 表示從狀態(tài)i出發(fā)在第n次轉(zhuǎn)移時(shí)首次到達(dá)狀態(tài)j的概率。,定義： 則 表示從狀態(tài)i出發(fā)在第n次轉(zhuǎn)移時(shí)首次回到狀態(tài)i的概率。,a,19,定義： 則 表示從狀態(tài)i出發(fā)最終到達(dá)狀態(tài)j的概率.,定義3.5 如果 fii = 1, 則稱狀態(tài)i是常返的. 否則, 即fii 0, 有,因此,a,25,例3.9 考慮整數(shù)點(diǎn)上的隨機(jī)游動(dòng). 向右移動(dòng)一格的概率為p, 向左移動(dòng)一格的概率為q=1-p

7、. 從原點(diǎn)0出發(fā), 則一步轉(zhuǎn)移概率矩陣為:,a,26,所以,利用Stirling公式知, 當(dāng)n充分大時(shí),于是,因此, 當(dāng)p=0.5時(shí) , 當(dāng)p0.5時(shí),即當(dāng)p=0.5時(shí)狀態(tài)0是常返的; 當(dāng)p0.5時(shí)0是瞬過(guò)的.,a,27,定義 對(duì)常返狀態(tài)i我們定義Ti為首次返回狀態(tài)i的時(shí)刻, 即: 稱作常返時(shí). 記 , 則有 , 所以是首次返回i的期望步數(shù), 叫作狀態(tài)i的平均常返時(shí).,定義 一個(gè)常返狀態(tài)i當(dāng)且僅當(dāng)i=時(shí)稱為是零常返的, 當(dāng)且僅當(dāng)i0（每一分量均大于0），則稱此馬爾鏈為一正則鏈(regular chain),補(bǔ)充：正則鏈與吸收鏈,a,30,定理C1. 若A為正則鏈的轉(zhuǎn)移矩陣，則必有： (1) ，

8、其中W為任一分量均大于零的隨機(jī)矩陣； (2) W的所有行向量均相同,定理C2. 記定理 C1中W的行向量為=(1, m)，則： (1) 對(duì)任意隨機(jī)向 量x，有 ； (2) 是P的不動(dòng)點(diǎn)向量,即P=, P的不動(dòng)點(diǎn)向量是唯一的,a,31,定義C2. 狀態(tài)Si 稱為馬氏鏈的吸收狀態(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即 為一吸收鏈,a,32,a,33,定理C3. 吸收鏈的基矩陣B中的每個(gè)元素，表示過(guò)程從一個(gè)非

9、吸收狀態(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吸收的概率,a,34,例C1.1 (競(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)其中一方的得分達(dá) 到4分時(shí)，競(jìng)賽結(jié)束求： (1) 甲隊(duì)獲勝的概率有多大？ (2) 競(jìng)賽從開(kāi)始到結(jié)束，平均轉(zhuǎn)移的次數(shù)為多少？ (3) 甲獲得1、2、3分的平均次數(shù)是多少？,a,35,設(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：,S 0 S 1 S 2 S 3 S 4,a,36,將上式改記為標(biāo)準(zhǔn)形 式T：,其中,a,37,計(jì)算基矩陣B：,記q=