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

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

2、Markov鏈是不可約的. 否則, 這個Markov鏈就被稱為是可約的,注: 引入可約/不可約概念是為了以后研究狀態(tài)的周期,進一步是為了研究轉移概率的極限性質,則顯然1, 2和3, 4, 5是狀態(tài)在互達意義下的兩個等價類. 因此, 這個Markov鏈是可約的. 比如其中一個子鏈為,例3.6 若Markov鏈有轉移概率矩陣,給出這個Markov鏈狀態(tài)的等價類, 并且試給出其n步轉移概率矩陣,練習: 若Markov鏈有轉移概率矩陣,答: 等價類為: 1, 4, 2, 5和3. 其中3為吸收態(tài),用Mathematica軟件計算知,所以,定義3.5 設i為Markov鏈的一個狀態(tài), 使 的所有正整數(shù)n

3、 (n1)的最大公約數(shù), 稱為狀態(tài)i的周期, 記作d(i) 或 di . 如果對所有n1, 都有 , 則約定周期為; d(i)=1的狀態(tài)i稱為是非周期的,推論: 如果n不能被周期d(i)整除, 則必有,注: 當狀態(tài)i的周期為d時, 不一定成立,解: 狀態(tài)轉移可以用下圖表示,用數(shù)學歸納法不難求出,所以 d(0) = 2,解: 狀態(tài)轉移可以用下圖表示,所以 d(1) = 2. 您能求出狀態(tài)2的周期嗎,命題3.2 如果ij, 則 di = dj,證: 設m1, n1,使得 , 則,因此, m+n同時能被di及dj整除. 對于任意的s1,即: m+s+n也能被dj整除. 因此, s能被dj整除. 從而

4、dj整除的 最大公因子di. 根據(jù)對稱性, di也整除dj , 所以 di = dj,滿足 , 則,引理3.1 設m2, 正整數(shù)s1, s2, sm的最大公因子為d, 則存在正整數(shù)N, 使得nN時, 必有非負整數(shù)c1, c2,cm使,我們引入狀態(tài)周期概念的目的，是為了研究狀態(tài)轉移矩陣的極限性質，即當n時P(n)的極限，這個矩陣可以反映出Markov鏈在平穩(wěn)狀態(tài)時的特征。因此，下面我們將討論周期的基本性質，為此先給出一個數(shù)論中的結論,推論3.1 設狀態(tài)i的周期為di. 如果 , 則存在整數(shù)N, 使得對所有nN恒有,證: 這時存在正整數(shù)s1, s2, sm, 使得它們的最大公因子為d, 且,命題3

5、.3 如果狀態(tài)i有周期d, 則存在整數(shù)N, 使得對所有nN恒有,由引理3.1, 存在正整數(shù)N, 使得nN時, 必有非負整數(shù)c1, c2,cm使 . 從而,因為狀態(tài)空間有限, 對全部的狀態(tài)對(i,j), 求出N(i,j). 并取 , 則顯然對所有狀態(tài)i和j, 當nN時有,證: 由于Markov鏈是不可約的, 過程的任兩個狀態(tài)i和j都是互達的, 于是m (與i和j有關)使得 . 由推論3.1及鏈的非周期性知, 存在N, 使得當nN時,命題3.4 設P為一個不可約、非周期、有限狀態(tài)Markov鏈的轉移矩陣, 則必存在N, 使得當nN時, P(n)的所有元素都大于0,常返與瞬過,定義： 則 表示從狀態(tài)

6、i出發(fā)在第n次轉移時首次到達狀態(tài)j的概率,定義： 則 表示從狀態(tài)i出發(fā)在第n次轉移時首次回到狀態(tài)i的概率,定義： 則 表示從狀態(tài)i出發(fā)最終到達狀態(tài)j的概率,定義3.5 如果 fii = 1, 則稱狀態(tài)i是常返的. 否則, 即fii1, 稱狀態(tài)i為非常返的或瞬過的,注: 如果狀態(tài)i是常返的, 那么從狀態(tài)i出發(fā)經(jīng)過有限步轉移后最后又回到i的概率為1,定義： 表示在0時刻從狀態(tài)i出發(fā)首次到達狀態(tài)j的所需要轉移的步數(shù), 即 如果 , 則,補充,我們有 , 因此,注: 上式告訴我們?yōu)槭裁磃ii=1表示常返,證,由過程的Markov性, 一旦回到i, 過程以后的發(fā)展只依賴當前, 因此從i出發(fā)至少回到i兩次

7、的概率是 , 依此類推. 用隨機變量K表示過程返回i的次數(shù), 則,于是K的條件期望為,顯然,下面我們將證明,令 , 則 , 于是,因此,推論3.2 如果i是常返的, 且ij, 則i也是常返的,證: 由ij知存在m,n使 和 , 于是對任何正整數(shù) s 0, 有,因此,例3.9 考慮整數(shù)點上的隨機游動. 向右移動一格的概率為p, 向左移動一格的概率為q=1-p. 從原點0出發(fā), 則一步轉移概率矩陣為,所以,利用Stirling公式知, 當n充分大時,于是,因此, 當p=0.5時 , 當p0.5時,即當p=0.5時狀態(tài)0是常返的; 當p0.5時0是瞬過的,定義 對常返狀態(tài)i我們定義Ti為首次返回狀態(tài)

8、i的時刻, 即: 稱作常返時. 記 , 則有 , 所以是首次返回i的期望步數(shù), 叫作狀態(tài)i的平均常返時,定義 一個常返狀態(tài)i當且僅當i=時稱為是零常返的, 當且僅當i時稱為正常返的,課外作業(yè): Page 58, Ex 9 Page 59, Ex 11, 14 其中14(1) 的矩陣改為,根據(jù)轉移矩陣的不同結構，馬氏鏈可以分為多個不同的類型，這里，我們只簡單介紹其中常見而又較為重要的兩類：正則鏈與吸收鏈,定義C1. 對于馬氏鏈，若存在一正整數(shù)k，使其轉移矩陣M的k次冪Mk 0（每一分量均大于0），則稱此馬爾鏈為一正則鏈(regular chain,補充：正則鏈與吸收鏈,定理C1. 若A為正則鏈的

9、轉移矩陣，則必有： (1) ，其中W為任一分量均大于零的隨機矩陣； (2) W的所有行向量均相同,定理C2. 記定理 C1中W的行向量為=(1, m)，則： (1) 對任意隨機向 量x，有 ； (2) 是P的不動點向量,即P=, P的不動點向量是唯一的,定義C2. 狀態(tài)Si 稱為馬氏鏈的吸收狀態(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即 為一吸收鏈,定理C3. 吸收鏈的基矩陣B中的每個元素，表示過程從一個非吸

10、收狀態(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ī)定，當其中一方的得分達 到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,S 0 S 1 S