概率論與隨機(jī)過程：第6章 7馬氏鏈4學(xué)時

1、 馬爾可夫鏈及其概率分布引言引言考慮離散型的n維r.v. ，把 所有可能取值記為 或1，2，3，.，如果 相互獨(dú)立，且 的d.l已知，則 的聯(lián)合d.l為),(21nXXXnXXX,21,21nxxxnXXX,21, 2 , 1, kXk),(21nXXX nkikiniiknxXPxXxXxXP121,21nXXX,21若 不相互獨(dú)立，要得到其聯(lián)合d.l可由乘法公式計(jì)算：若 0,121121 niniixXxXxXP有 ,|,|,1212131212112121312121 nnniniiiniiiiiiiniixXxXxXxXPxXxXxXPxXxXPxXPxXxXxXP設(shè)想，若|,|112

2、11121 kkkkikikikiiikxXxXPxXxXxXxXP則問題可以相對化簡。稱為Markov性。一般用分布函數(shù)定義為：設(shè)隨機(jī)過程X X(t t),t tT T，狀態(tài)空間為，若對于t t 的任意n個值t t1 1t t2 2t tn n,n n3,有 則稱過程X(t),tT具有馬爾可夫性，或稱 X(t),tT為馬爾可夫過程。 112211)(,)(,)()( nnnnxtXxtXxtXxtXP RxxtXxtXPnnnnn ,)(|)(11數(shù)數(shù)。的的條條件件分分布布函函下下布布函函數(shù)數(shù)等等于于在在條條件件的的條條件件分分條條件件下下，即即在在)()()(1, 2 , 1,)(11nn

3、nniitXxtXtXnixtX );|,(),;,|,(11|121121|1121 nnnnttnnnntttttxtxFtttxxxtxFnnnn或或 直觀上，過程（或系統(tǒng)）在時刻t0所處的狀態(tài)為已知的條件下,過程在時刻tt0所處狀態(tài)的條件分布與過程在時刻t0之前所處的狀態(tài)無關(guān)。無后效性。 即已知過程現(xiàn)在的條件下，其將來不依賴于過去。 1,000,0XttXXtt例 ：設(shè)是獨(dú)立增量過程，且 證明：是一個馬爾可夫過程。121,nnTntttt證：對 中任意 個數(shù)值 1111( )|,nnnnP X txX txX tx 112211110,0,( ),0nnnnnnX tXx X tXxP

4、 X tX txxX tXx 1111( )|0nnnnnnP X tX txxX tXx ,0X tt 由定義知，是一個馬爾可夫過程。 11( )|nnnnP X txX tx只與此值有關(guān)，與其它增量獨(dú)立由上例知，泊松過程泊松過程是時間連續(xù)狀態(tài)離散的馬氏過程， 維納過程維納過程是時間狀態(tài)都連續(xù)的馬氏過程。一、馬爾可夫鏈及其概率分布的定義 狀態(tài)和時間參數(shù)都是離散的馬爾可夫過程稱為馬爾可夫鏈，或馬氏鏈。 記為Xn=X(n),n=0,1，2，,記鏈的狀態(tài)空間為a1，a2，aiR .在鏈的情況，馬爾可夫性通常用分布率表示。 1.1.馬氏鏈的定義馬氏鏈的定義 imjmnimitititjmnaXaXP

5、aXaXaXaXaXPrr |,2211其中a., 稱Xn,n=0,1，2，為馬氏鏈。定義定義1 1若對于任意的正整數(shù)n，r和任意的 有有, 2 , 1 , 0,021nTnmmtmtttir 則稱Xn,n0為馬氏鏈。 nnnninininiiinaXaXPaXaXaXaXP |,12011101有有 定義定義2 2設(shè)Xn,n0,其狀態(tài)空間為,若對于任意的正整數(shù)n和任意的 110,nniiiiaaaa,稱為馬氏鏈在時刻m系統(tǒng)處于狀態(tài)ai的條件下，在時刻m+n轉(zhuǎn)移到狀態(tài)aj的轉(zhuǎn)移概率。 imjnmnijaXaXPmP |)()(例.記從數(shù)1,2, ,N中任取一數(shù)為X0 0，當(dāng)n1時，記從數(shù)1,2

6、, ,Xn n-1-1中任取一數(shù)為Xn n,證明Xn n,n=0，1，2,是一個馬氏鏈。證：Xn n,n=0，1，2,的狀態(tài)空間=i,1iN, ,110 xiiiinnn 及對任意的 nnnnnnnnnnnnniXiXPiiiiiiXiXiXiXP |10,1111110011可見,Xn n,n=0，1，2,是一個馬氏鏈。 2 2轉(zhuǎn)移概率的性質(zhì)轉(zhuǎn)移概率的性質(zhì) (1)(1) Pij (n)(m)0； , 2 , 1, 1)()2(1)( imPjnij 事實(shí)上，因?yàn)殒溤趍時刻從狀態(tài)ai i出發(fā)，到m+n時刻必然轉(zhuǎn)移到a1 1，a2 2，狀態(tài)中的一個，從而 11)(|)(jimjnmjnijaXa

7、XPmP . 1| imjnmjaXaXP2. .定義定義若對任意的正整數(shù)m,n及任意的ai，aj，有 mPnPijij)1()1( 即馬氏鏈Xn,n0的轉(zhuǎn)移概率Pij (1)(n)與n無關(guān)，則稱轉(zhuǎn)移概率具有平穩(wěn)性，這時，馬爾可夫鏈稱為是齊次的。 imjmijijaXaXPmpp |1)1(稱為馬氏鏈的一步轉(zhuǎn)移概率；齊次馬爾可夫鏈及一步轉(zhuǎn)移概率齊次馬爾可夫鏈及一步轉(zhuǎn)移概率 )1()1(ijpPP ijiiijjjpppapppapppaaaaP2122221211211121 稱為馬氏鏈的一步轉(zhuǎn)移概率矩陣；其中列為Xm的狀態(tài)，行為Xm+1的狀態(tài)。則稱Xn,n0為(齊次)馬氏鏈。 nnnnnnn

8、niXiXPiXiXiXiXP |,11210011有 定義定義2 2設(shè)Xn,n0,其狀態(tài)空間為E,若對于任意的正整數(shù)m,n和任意的 110,nniiiiE, mPnPijij)1()1( 例（01傳輸系統(tǒng)）在一個n級數(shù)字傳輸系統(tǒng)中，設(shè)每一級的傳真率為p，誤碼率為q=1-p，并設(shè)一個單位時間傳輸一級，X0是第一級的輸入, Xn是第n級的輸出（n1）,那么Xn n, n=0，1，2,是一隨機(jī)過程，狀態(tài)空間=0,1.0 0 1 1p1-p X0 X1 Xn-1 Xn0 0 1 1p1-p0 0 1 1p1-p 當(dāng)Xn=i, i為已知時，Xn+1n+1所處的狀態(tài)的概率分布只與Xn n=i 有關(guān)，而與

9、時刻n以前所處的狀態(tài)無關(guān)，所以它是一個馬氏鏈。且一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為 pqqpPjiijqijpiXjXPpnnij1 , 0,|1,且是齊次馬氏鏈.例例(一維隨機(jī)游動)設(shè)一醉漢Q（或看作一隨機(jī)游動的質(zhì)點(diǎn)），在如圖所示直線的點(diǎn)集I1，2，3，4，5上作游動，僅僅在1秒、2秒等時刻發(fā)生游動。游動的概率規(guī)則是：如果Q現(xiàn)在位于點(diǎn)i (1i 5)，則下一時刻各以1/3的概率向左或向右移動一格，或以1/3的概率留在原處；如果Q現(xiàn)在位于1（或5）這點(diǎn)上，則下一時刻就以概率1移動到2（或4）點(diǎn)上。1和5這兩點(diǎn)稱為反射壁。上面這種游動稱為帶有兩個反射壁的隨機(jī)游動。 1 2 3 4 5 若以Xn

10、 n表示時刻n時Q的位置，不同的位置就是Xn n的不同狀態(tài)，那么Xn n,n=0，1,2,是一隨機(jī)過程，狀態(tài)空間就是I，而且當(dāng)Xn n=i,iI為已知時,Xn n+1+1所處的狀態(tài)的概率分布只與Xn n=i有關(guān)，而與Q在時刻n以前如何到達(dá)i是完全無關(guān)的，所以Xn n,n=0，1,2, 是一馬氏鏈，且是齊次的。它的一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為 2|04, 52, 11, 51 , 1, 131|1ijjijiiiijiXjXPpnnij或或 如果把1這一點(diǎn)改為吸收壁，即Q一旦到達(dá)1，就永遠(yuǎn)留在點(diǎn)1上。此時，相應(yīng)鏈的轉(zhuǎn)移概率矩陣只須把P中第1橫行改為（1，0，0，0，0）?？傊?，改變游動的

11、概率規(guī)則，就可得到不同方式的游動和相應(yīng)的馬氏鏈。 010003/13/13/10003/13/13/10003/13/13/1000105432154321P 例例4 4：排隊(duì)模型排隊(duì)模型 設(shè)服務(wù)系統(tǒng)由一個服務(wù)員和只可以容納兩個人設(shè)服務(wù)系統(tǒng)由一個服務(wù)員和只可以容納兩個人的等候室組成。服務(wù)規(guī)則為：先到先服務(wù)，后來者的等候室組成。服務(wù)規(guī)則為：先到先服務(wù)，后來者需在等候室依次排隊(duì)，假設(shè)一個需要服務(wù)的顧客到需在等候室依次排隊(duì)，假設(shè)一個需要服務(wù)的顧客到達(dá)系統(tǒng)時發(fā)現(xiàn)系統(tǒng)內(nèi)已有達(dá)系統(tǒng)時發(fā)現(xiàn)系統(tǒng)內(nèi)已有3 3個顧客，則該顧客立即離個顧客，則該顧客立即離去。去。 設(shè)時間間隔設(shè)時間間隔tt內(nèi)有一個顧客進(jìn)入系統(tǒng)的概率

12、為內(nèi)有一個顧客進(jìn)入系統(tǒng)的概率為q q，有一接受服務(wù)的顧客離開系統(tǒng)，有一接受服務(wù)的顧客離開系統(tǒng)( (即服務(wù)完畢即服務(wù)完畢) )的概的概率為率為p,p,又設(shè)當(dāng)又設(shè)當(dāng)tt充分小時，在這時間間隔內(nèi)多于一充分小時，在這時間間隔內(nèi)多于一個顧客進(jìn)入或離開系統(tǒng)實(shí)際上是不可能的，再設(shè)有個顧客進(jìn)入或離開系統(tǒng)實(shí)際上是不可能的，再設(shè)有無顧客來到與服務(wù)是否完畢是相互獨(dú)立的。無顧客來到與服務(wù)是否完畢是相互獨(dú)立的。等候室服務(wù)臺系統(tǒng)隨機(jī)到達(dá)者離去者用馬氏鏈來描述這個服務(wù)系統(tǒng)：用馬氏鏈來描述這個服務(wù)系統(tǒng)： 設(shè)設(shè)X Xn n=X(nt)=X(nt)表示時刻表示時刻ntnt時系統(tǒng)內(nèi)的顧客數(shù)，時系統(tǒng)內(nèi)的顧客數(shù)，即系統(tǒng)的狀態(tài)。即系統(tǒng)的

13、狀態(tài)。XXn n,n,n=0,1,2=0,1,2是一隨機(jī)過程，狀態(tài)是一隨機(jī)過程，狀態(tài)空間空間I=0,1,2,3,I=0,1,2,3,且如前例的分析可知，它是一個齊且如前例的分析可知，它是一個齊次馬氏鏈，它的一步轉(zhuǎn)移概率矩陣為：次馬氏鏈，它的一步轉(zhuǎn)移概率矩陣為： 0 1 2 301001(1)(1)(1)(1)020(1)(1)(1)(1)300(1)(1)qqpqpqpqqpPpqpqpqqppqpqp等候室服務(wù)臺系統(tǒng)隨機(jī)到達(dá)者離去者 例例 有甲、乙兩袋球，開始時有甲、乙兩袋球，開始時, ,甲袋有甲袋有3 3只球只球, ,乙袋有乙袋有2 2只球；只球；以后以后, ,每次任取一袋每次任取一袋,

14、,并從袋中取出一球放入另一袋并從袋中取出一球放入另一袋( (若袋中無若袋中無球則不取球則不取) )。X Xn n表示第表示第n n次抽取后甲袋的球數(shù)次抽取后甲袋的球數(shù),n=1,2,. ,n=1,2,. XXn n,n,n=1,2,=1,2,是一隨機(jī)過程，狀態(tài)空間是一隨機(jī)過程，狀態(tài)空間I=0,1,2,3,4,5,I=0,1,2,3,4,5,當(dāng)當(dāng)X Xn n=i=i時，時，X Xn+1n+1=j=j的概率只與的概率只與i i有關(guān)，與有關(guān)，與n n時刻之前如何取到時刻之前如何取到i i值是值是無關(guān)的，無關(guān)的，這是一馬氏鏈，且是齊次的這是一馬氏鏈，且是齊次的, , 一步轉(zhuǎn)移概率矩陣為：一步轉(zhuǎn)移概率矩陣

15、為：112211221122112211221122 0 1 2 34 5000000000100002000030000400005P甲乙 定義定義3 3 稱條件概率 為馬爾可夫鏈在時刻m處于狀態(tài)ai i的條件下，在時刻m+n步轉(zhuǎn)移到狀態(tài)aj j的n步轉(zhuǎn)移概率，簡稱為轉(zhuǎn)移概率。 imjnmnijaXaXPmP |)()(例 設(shè)Xn,n=0，1，2,是獨(dú)立同分布的隨機(jī)變量列,記Xn可能取值的全體為I=i,i 1,則Xn為馬氏鏈，并求其一步轉(zhuǎn)移概率。解 對任意的n及 Iiiiinn 110, 110011,| nnnnnniXPiXiXiXP所以Xn為馬氏鏈。 IiqiXPin ,記記由于Xn,

16、 n=0，1，2,獨(dú)立同分布，因而 nnnniXiXP |11 |111iXjXPqjXPiXjXPmmjnnn 所以Xn為齊次馬氏鏈。其一步轉(zhuǎn)移概率P: .,Ijiqpjij /例3 排隊(duì)模型設(shè)服務(wù)系統(tǒng)由一個服務(wù)員和只可以容納兩個人的等候室組成，見圖73。服務(wù)規(guī)則是：先到先服務(wù)，后來者需在等候室依次排隊(duì)。假定一個需要服務(wù)的顧客到達(dá)系統(tǒng)時發(fā)現(xiàn)系統(tǒng)內(nèi)已有3個顧客（一個正在接受服務(wù)，兩個在等候室排隊(duì)）則該顧客即離去。設(shè)時間間隔t內(nèi)將有一個顧客進(jìn)入系統(tǒng)的概率為q，有一原來被服務(wù)的顧客離開系統(tǒng)（即服務(wù)完畢）的概率為p。又設(shè)當(dāng)t充分小時，在這時間間隔內(nèi)多于一個顧客進(jìn)入或離開系統(tǒng)實(shí)際上是不可能的。再設(shè)有無

17、顧客來到與服務(wù)是否完畢是相互獨(dú)立的?，F(xiàn)用馬氏鏈來描述這個服務(wù)系統(tǒng)。 隨機(jī)到達(dá)者等候室服務(wù)臺系 統(tǒng)離去者設(shè)P表示一步轉(zhuǎn)移概率Pij所組成的矩陣，則 稱P為一步轉(zhuǎn)移概率矩陣，它具有如下性質(zhì) （1） （2） （2）式中對j求和是對狀態(tài)空間I的所有可能的狀態(tài)進(jìn)行的。此性質(zhì)說明，一步轉(zhuǎn)移概率矩陣中任一行元素之和為1。 表示時刻 時，系統(tǒng)內(nèi)的顧客數(shù)，即系統(tǒng)的狀態(tài)。xn, n=0，1，2,是一隨機(jī)過程，狀態(tài)空間I0，1，2，3，而且仿照例1、例2的分析，可知它是一個齊次馬氏鏈。下面來計(jì)算此馬氏鏈的一步轉(zhuǎn)移概率。 p00在系統(tǒng)內(nèi)沒有顧客的條件下，以 后仍沒有顧客的概率（此處是條件概率，以下同），p00=1-q

18、. p01系統(tǒng)內(nèi)沒有顧客的條件下, 經(jīng) 后有一顧客進(jìn)入系統(tǒng)的概率, p01=q.)(tnXXn p10系統(tǒng)內(nèi)恰有一顧客正在接受服務(wù)的條件下，經(jīng) 后系統(tǒng)內(nèi)無人的概率，它等于在 間隔內(nèi)顧客因服務(wù)完畢而離去，且無人進(jìn)入系統(tǒng)的概率，p10=p(1-q).p11系統(tǒng)內(nèi)恰有一顧客的條件下，在 間隔內(nèi)，他因服務(wù)完畢而離去，而另一顧客進(jìn)入系統(tǒng)，或者正在接受服務(wù)的顧客將繼續(xù)要求服務(wù)，且無人進(jìn)入系統(tǒng)的概率，這p11pq(1-p) (1-q). p12正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且另一個顧客進(jìn)入系統(tǒng)的概率，p12=q(1-p). p13正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且在 間隔內(nèi)有兩個顧客進(jìn)入系統(tǒng)的概率。由假設(shè)

19、，后者實(shí)際上是不可能發(fā)生的，p13=0. 類似地，有p21= p32 = p(1-q), p22 = pq+(1-p) (1-q), p23=q(1-p), pij= 0( | i-j |2 ).p33或者一人將離去且另一人將進(jìn)入系統(tǒng)，或者無人離開系統(tǒng)的概率，p33= pq+(1-p). 于是該馬氏鏈的一步轉(zhuǎn)移概率矩陣為 )1 ()1 (00)1 ()1)(1 ()1 (00)1 ()1)(1 ()1 (00)1 (3210ppqqppqqppqqppqqppqqpqqp例4 某計(jì)算機(jī)機(jī)房的一臺計(jì)算機(jī)經(jīng)常出故障，研究者每隔15分鐘觀察一次計(jì)算機(jī)的運(yùn)行狀態(tài)，收集了24小時的數(shù)據(jù)（共作97次觀察）

20、，用1表示正常狀態(tài)，用0表示不正常狀態(tài)，所得的數(shù)據(jù)序列如下：1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111設(shè)Xn為第n (n=1,2,97)個時段的計(jì)算機(jī)狀態(tài)，可以認(rèn)為它是一個齊次馬氏鏈，狀態(tài)空間I=0,1, 96次狀態(tài)轉(zhuǎn)移的情況是： 00，8次，01，18次； 10，18次，11，52次。因此，一步轉(zhuǎn)移概率可用頻率近似地表示為 ,26818880|0100 nnXXPp,70185218181|0110 nnXXPp,2618188180|110

21、1 nnXXPp,70525218521|1111 nnXXPp 3.3.多步轉(zhuǎn)移概率及C-K方程 若Xn為齊次馬氏鏈，則對任意非負(fù)整數(shù)m，任意正整數(shù)n,及 jiaa , 無無關(guān)關(guān)。與與有有maXaXPimjnm | imjnmaXaXP |證明： imjmnjmnjmaXaXaXaXPn |,1111而而 imjmnjmnjmimaXPaXaXaXaXPn |,1111 jjjjijimjjjjijimnnpppaXPpppaXP12111211 12111,11|,nnjjjimjmnjmnjmaXaXaXaXP因此，馬氏鏈的齊次性可寫為 imjnmimjnmaXaXPaXaXP 2211

22、| 無無關(guān)關(guān)。與與所所以以maXaXPimjnm | )()(2)(1)(2)(22)(21)(1)(12)(11)()(nijnininjnnnjnnnijnppppppppppP為馬爾可夫鏈的n步轉(zhuǎn)移概率矩陣。. 1, 0)()( xanijnijjpp其中定理定理 設(shè)Xn，n=0,1,為馬氏鏈，則對于任意的正整數(shù)k,m，有 rkrjmirkmijppp)()()(此方程稱為Chapman-kolmogorov(切普曼柯爾莫哥洛夫)方程,簡稱C-K方程.證： injkmnkmijaXaXPp |)( rinjkmnrmnaXaXaXP|, 既:“從Xn=ai出發(fā)，經(jīng)時刻m轉(zhuǎn)移到中間狀態(tài)ar

23、,再從ar經(jīng)k時段轉(zhuǎn)移到aj狀態(tài)”這樣一些事件的和事件。 rinjkmnrmninaXPaXaXaXP, rinkrjmirinaXPppaXP)()( rkrjmirpp)()( 如果把轉(zhuǎn)移概率寫成矩陣的形式，那么CK方程具有以下簡單的形式 P P(m+k(m+k) )=P P(m)(m)P P(k)(k) m, k0 特別地，P P(n)(n)=P Pn n, n步轉(zhuǎn)移概率由一步轉(zhuǎn)移概率完全決定。例 求帶有兩個反射壁的一維隨機(jī)游動的兩步轉(zhuǎn)移概率矩陣。 010003/13/13/10003/13/13/10003/13/13/100010010003/13/13/10003/13/13/10

24、003/13/13/100010)2(2PP解：解： 3/13/13/1009/19/59/29/109/19/29/39/29/109/19/29/59/1003/13/13/1例 甲乙進(jìn)行某種比賽，設(shè)每局比賽中甲勝的概率為p，乙勝的概率為q，平局的概率為r，p+q+r=1，每局比賽后勝負(fù)平分別得2，-1，0分，當(dāng)兩人中有一人得到2分時結(jié)束，Xn，n1表示比賽至n局時甲獲分?jǐn)?shù)，則Xn為馬氏鏈，求(1)狀態(tài)空間，(2)兩步轉(zhuǎn)移概率矩陣(3)問甲獲1分情況下，最多再賽兩局可結(jié)束比賽的概率。解 (1)E=-2，-1，0，1，221012100000000000000121012)2( prqprq

25、prqP 10000202220220000122222222)2(prppqrrqqpprpqrrqqppqpqrpqPP(3)prppp )2(12例 在n級0-1傳輸系統(tǒng)中，設(shè)p=0.9，求系統(tǒng)二級傳輸后的傳真率與三級傳輸后的誤碼率.解 先求出n步轉(zhuǎn)移概率矩陣P P(n)(n)=P Pn n。 pqqpP有相異特征值1=1，2=p-q ,由線性代數(shù)知識，可將矩陣P表示為對角陣 qp0010021 的相似矩陣。 具體做法是：求出 1 ,2對應(yīng)的特征向量 2/12/1,2/12/111ee 2/12/12/12/1,21eeH令令則PHH-1。于是，容易算得 nnnnnnqpqpqpqpHH

26、P)(2121)(2121)(2121)(212110101 由上式可知，當(dāng)p=0.9時，系統(tǒng)經(jīng)二級傳輸后的傳真率 與三級傳輸后的誤碼率分別為 820. 0)1 . 09 . 0(21212)2(00)2(11 PP244. 0)1 . 09 . 0(21213)3(01)3(10 PP 對于只有兩個狀態(tài)的馬氏鏈，一步轉(zhuǎn)移概率矩陣一 般可表示為： 1,0 ,11 babbaaP利用類似的方法，可得n步轉(zhuǎn)移概率矩陣為 bbaababaababbappppPPnnnnnnn)1(11010)(11)(10)(01)(00 n=1,2,. 定義定義 稱條件概率 1, 0,|)( nmxaaaXaXP

27、Pjiimjnmnij 為馬氏鏈Xn,n0的n步轉(zhuǎn)移概率，并稱由Pij(n)組成的矩陣 稱Xn的分布qj(n)=PXn=j, jE 為Xn,n=0,1,的絕對分布，初始分布和任一時刻 n的絕對分布可用向量表示 q(0)=(q1 1(0),q2 2(0), ) q(n)=(q1 1(n),q2 2(n), ) 定義 設(shè)Xn n,n=0,1,為馬爾可夫鏈，稱X0 0的分布 qj j(0)=PX0 0=j, jE=1,2為Xn n,n=0,1,的 初始分布.，顯然 11)(jjnq 四、有限維分布(及遍歷性) 1有限維分布 設(shè)馬氏鏈Xn,n0,狀態(tài)空間，n步轉(zhuǎn)移概率矩陣P(n)(n). (1)一維分

28、布 , |100 inniXjXPiXPjXP由全概公式, 2 , 1,)0()(1)( jpqnqinijij或 一維分布可用行向量表示q q(n)=(q1(n),q2(n),qj(n),), 利用矩陣的乘法：q(n)= q(0)P(n)(n) 說明馬氏鏈在任一時刻n的一維分布由初始分布與n步 轉(zhuǎn)移概率矩陣確定。 (2)n維分布 對任意n個時刻 0t1 1t2 20, 則稱自狀態(tài)i可達(dá)狀態(tài)j，記為ij。 若 n n 1 1， 則則稱自狀態(tài)i不可達(dá)狀態(tài)j，記為ij。 若ij，ji,稱i,j是相通的，記為)(nijP0)( nijPji 性質(zhì)TH (傳遞性)設(shè)i,j,kE,若ik,kj,則ij。

29、證明)(nijP分析：要證 n n 1,1,使 0，用定義及C-K方程,ki , 0,)(11 nikpn 使又, jk , 0,)(22 nkjpn 使則, 0)()()()()(212121 nkjnikEsnsjnisnnijppppp所以i j 。推論(相通具有傳遞性)若 ，則jkki,ji 定義設(shè),jiCiCjEjEC 均有則稱C是E中的一個閉集。直觀上：判斷是否是閉集的方法：證明“” 顯然成立；TH 設(shè)CE, 則C為閉集 , 0, jipCjCi 有“” 分析：只要證, 0, 1)( njipCjCin 有用歸納法證明當(dāng)n=1時，由已知pij=0，設(shè)0)1( nijp，則由C-K方

30、程ECEij0)1()1()1()( CssjnisCssjnisEssjnisnijppppppp定理成立。例馬爾可夫鏈閉集的性質(zhì)： TH 若 是馬氏鏈的n步轉(zhuǎn)移概率矩陣，C是E中的一個閉集，則 構(gòu)成一隨機(jī)矩陣。)()(nijpCjipnij ,),()(意義證明Cjipnij ,10)1()(EipCiEjnij ,1,)2()(,10)()()()( CjnijCjnijCjnijEjnijppppCipCjnij ,1)(定義 設(shè)馬爾可夫鏈的狀態(tài)空間為E，若除E外不存在其它的閉集，則稱此鏈?zhǔn)遣豢煞只虿豢杉s的，否則，稱為可分或可約的。 引理1 設(shè)DE,則包含D的所有閉集的交仍是閉集且是包

31、含D的最小閉集。成為D的閉包，記為D證明設(shè) 是包含D的所有閉集,)(,指標(biāo)SsFs SssFF FjFi ,Fj 0,0sFjs 使00,ssFFi 而是閉集0 ijpF是閉集，且是含D的最小閉集。 引理2 設(shè) jE,則:kjkjj 證明 (1)設(shè):kjkjF 若F不是閉集，則,skFsFk 使但jk,所以js,從而sF,矛！(2)F最?。悍醋C 若G是含j的閉集，GF，則 kjjkFGk 而,從而 kF,矛！ F最小。(先證其是閉集)EGFjk 馬爾可夫鏈不可約它的每一狀態(tài)可由其它任一狀態(tài)到達(dá)。(任兩狀態(tài)相通)。定理證明 “” 反證ijijEji 使若, ji 則,E集中閉是從而 j與鏈不可約

32、矛！“”只要證E是最小閉集,Ej 任取kjjkEk , jk jE E是最小閉集例，例P84二、狀態(tài)的分類定義1,:min,0 njXiXnTEjinij定義稱Tij為自狀態(tài)i出發(fā)，首次到達(dá)狀態(tài)j的步數(shù)或時刻。記jjnsjjjjijnijnspppf121111)( |0)(iXnTPfijnij 稱為自狀態(tài)i出發(fā)，經(jīng)n步首次到達(dá)狀態(tài)j的概率。引理證明 由定義|0)(iXnTPfijnij 而|1, 2 , 1,|00iXnkjXjXiXnTknij 11111111220111101111)(1211|,nsjjjjjjijnnnnsjjnsjjnnnnijsnsspppjXjXPjXjXP

33、iXjXPiXjXjXjXPf., 0)(0nijfiXP則用上式右端定義若 定義 記 1)(nnijijff表示從i出發(fā)經(jīng)有限步(遲早)到達(dá)狀態(tài)j的概率。 引理 關(guān)于 有ijnijff,)(|)2(;0)1(0)(iXTPfffijijijnij 101)(|nijnnijijiXnTPff| )(010iXTPiXnTPijnij 引理 有, 1, nEji nllnjjlijnijpfp1)()()()1()0( jjp直觀意義：證明見書。推論)0(,)0(0)()(10)()()( ijnlljjlnijnlljjlnijnijfpfpfp定理0 ijfji證明 “”，若ji 由定義，

34、, 0, 1)( nijpn使即：01)()()( nllnjjlijnijpfp0,1,)(000 lijfnll使從而，. 0)(0 lijijff“”, 0, 10)( nijijfnf使則，若而，0)()( nijnijfpji 推論0, 0 jiijffji且書例P86定理 設(shè)A=系統(tǒng)無窮多次到達(dá)j Am=系統(tǒng)至少m多次到達(dá)j， 并記：,|)(,|00iXAPmQiXAPQmijij 則.1, 01, 1 jjjjjjffQ證明 由已知, 2 , 1,11 mmmmAAmAA且從而，|lim)(lim|00iXAPmQiXAPQmmijmij | ),(|)1(0101iXAkTPi

35、XAPmQkmijmij 而，系統(tǒng)有限次返回j)|, 1,1 ,(01iXjXnmjXkjXPkknk 使個且至少有 )|, 1,1 ,(01iXjXnmjXkjXPknkk 使個且至少有 ,1,|, 1)|,1 ,(001jXkjXiXjXnmPiXjXkjXPkknkk 使個至少有|, 1)|,1 ,(01jXjXnmPiXjXkjXPkknkk 使個至少有 首達(dá)j)()(1)(mQfmQfjjijjjkkij 從而，mjjijjjmjjijjjjjijjjijijffQffmQffmQfmQ)()1()()1()()1(1 于是，.1, 01, 1)(lim)(lim jjjjmjjmj

36、jmjjfffmQQ推論.1, 01, jjjjijijfffQ定義 當(dāng)fij=1時， 為一分布律，則, 2 , 1,)( nfnij)(1nijnijfn 表示從i出發(fā)首次到達(dá)j的平均時間或步長，特別的，jj表示 從j出發(fā)再回到j(luò)的平均時間或步長，稱為狀態(tài)j的平均返回時間，簡記為j。定義(1)若fjj=1，則稱狀態(tài)j是常返狀態(tài)，或j是常返的；(2)若j是常返的，且 jj+ ，則稱j是正常返的，或積極常返的；(3)若j是常返的，且 jj=+ ，則稱j是零常返的，或消極常返的；(4)若fjj1,則稱狀態(tài)j是周期的，j有周期d，記為d(j).0:)( njjpn0:)( njjpn若d(j)=1,則稱狀態(tài)j是非周期的。若 j是正常返的,又是非周期的，則稱j是遍歷的。周期狀態(tài)的性質(zhì)：若0:)( njjpn非空，則有0,)3()2( njjnjjpp