1、3.2 Markov鏈的狀態(tài)分類,互達(dá)性和周期性,注: 引入互達(dá)性概念是為了對(duì)狀態(tài)進(jìn)行分類.,命題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.,在數(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á)性這一等價(jià)關(guān)系下都居于同一類,

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

3、狀態(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í), 不一定成立.,解: 狀態(tài)轉(zhuǎn)移可以用下圖表示,用數(shù)學(xué)歸納法不難求出:,所以 d(0) = 2.,解: 狀態(tài)轉(zhuǎn)移可以用下圖表示,所以 d(1) = 2. 您能求出狀態(tài)2的周期嗎?,命題3.2 如果ij, 則 di = dj.,證: 設(shè)m1, n1,使得 , 則,因此, m+n同時(shí)能被di及dj整除. 對(duì)于任意的s1,即: m+s+n也能被

4、dj整除. 因此, s能被dj整除. 從而dj整除的 最大公因子di. 根據(jù)對(duì)稱性, di也整除dj , 所以 di = dj .,滿足 , 則,引理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ù)論中的結(jié)論：,推論3.1 設(shè)狀態(tài)i的周期為di. 如果 , 則存在整數(shù)N, 使得對(duì)所有nN恒有,證: 這時(shí)存在正整數(shù)s1, s

5、2, sm, 使得它們的最大公因子為d, 且 .,命題3.3 如果狀態(tài)i有周期d, 則存在整數(shù)N, 使得對(duì)所有nN恒有 .,由引理3.1, 存在正整數(shù)N, 使得nN時(shí), 必有非負(fù)整數(shù)c1, c2,cm使 . 從而,因?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的, 過程的任兩個(gè)狀態(tài)i和j都是互達(dá)的, 于是m (與i和j有關(guān))使得 . 由推論3.1及鏈的非周期性知, 存在N, 使得當(dāng)nN時(shí), .,命題3.4 設(shè)P為一個(gè)不可約、非周期、有限狀態(tài)Markov鏈的轉(zhuǎn)移矩陣, 則必存在N, 使得當(dāng)n

6、N時(shí), P(n)的所有元素都大于0.,常返與瞬過,定義： 則 表示從狀態(tài)i出發(fā)在第n次轉(zhuǎn)移時(shí)首次到達(dá)狀態(tài)j的概率。,定義： 則 表示從狀態(tài)i出發(fā)在第n次轉(zhuǎn)移時(shí)首次回到狀態(tài)i的概率。,定義： 則 表示從狀態(tài)i出發(fā)最終到達(dá)狀態(tài)j的概率.,定義3.5 如果 fii = 1, 則稱狀態(tài)i是常返的. 否則, 即fii1, 稱狀態(tài)i為非常返的或瞬過的.,注: 如果狀態(tài)i是常返的, 那么從狀態(tài)i出發(fā)經(jīng)過有限步轉(zhuǎn)移后最后又回到i的概率為1.,定義： 表示在0時(shí)刻從狀態(tài)i出發(fā)首次到達(dá)狀態(tài)j的所需要轉(zhuǎn)移的步數(shù), 即 如果 , 則,補(bǔ)充:,我們有 , 因此,注: 上式告訴我們?yōu)槭裁磃ii=1表示常返.,證:,由過程

7、的Markov性, 一旦回到i, 過程以后的發(fā)展只依賴當(dāng)前, 因此從i出發(fā)至少回到i兩次的概率是 , 依此類推. 用隨機(jī)變量K表示過程返回i的次數(shù), 則,于是K的條件期望為:,顯然,下面我們將證明:,令 , 則 , 于是,因此,推論3.2 如果i是常返的, 且ij, 則i也是常返的.,證: 由ij知存在m,n使 和 , 于是對(duì)任何正整數(shù) s 0, 有,因此,例3.9 考慮整數(shù)點(diǎn)上的隨機(jī)游動(dòng). 向右移動(dòng)一格的概率為p, 向左移動(dòng)一格的概率為q=1-p. 從原點(diǎn)0出發(fā), 則一步轉(zhuǎn)移概率矩陣為:,所以,利用Stirling公式知, 當(dāng)n充分大時(shí),于是,因此, 當(dāng)p=0.5時(shí) , 當(dāng)p0.5時(shí),即當(dāng)p

8、=0.5時(shí)狀態(tài)0是常返的; 當(dāng)p0.5時(shí)0是瞬過的.,定義 對(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)i時(shí)稱為正常返的.,課外作業(yè): Page 58, Ex 9 Page 59, Ex 11, 14 其中14(1) 的矩陣改為:,根據(jù)轉(zhuǎn)移矩陣的不同結(jié)構(gòu)，馬氏鏈可以分為多個(gè)不同的類型，這里，我們只簡(jiǎn)單介紹其中常見而又較為重要的兩類：正則鏈與吸收鏈,定義C1. 對(duì)于馬氏鏈，若存在一正整數(shù)k，使其轉(zhuǎn)移矩陣M的k次冪Mk 0（每一分量均大于0

9、），則稱此馬爾鏈為一正則鏈(regular chain),補(bǔ)充：正則鏈與吸收鏈,定理C1. 若A為正則鏈的轉(zhuǎn)移矩陣，則必有： (1) ，其中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)向量是唯一的,定義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á)某一吸收 狀

10、態(tài),根據(jù)定義C3，例3.1中Xn即 為一吸收鏈,定理C3. 吸收鏈的基矩陣B中的每個(gè)元素，表示過程從一個(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中的子陣，則fij表示從非吸收狀態(tài)i出發(fā)，被吸收狀態(tài) j吸收的概率,例C1.1 (競(jìng)賽問題) 甲乙兩隊(duì)進(jìn)行一場(chǎng)搶答競(jìng)賽，競(jìng)賽規(guī)則規(guī)定：開始時(shí)每隊(duì)各記2分，搶答題開始后，如甲取勝則甲加1分而乙減1分，反之則乙加1分甲減1分 (每題必需決出勝負(fù) )規(guī)則還規(guī)定，當(dāng)其中一方的得分達(dá) 到4分時(shí)，競(jìng)賽結(jié)束求： (1) 甲隊(duì)獲勝的概率有多大？ (2) 競(jìng)賽從開始到結(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)過程以S2作為初始狀態(tài)根據(jù)甲隊(duì)贏得1分的概率為p，建立轉(zhuǎn)移矩陣P：,S 0 S 1 S 2