第十七章馬氏鏈模型

1、第十七章 馬氏鏈模型§1 隨機(jī)過程的概念一個(gè)隨機(jī)試驗(yàn)的結(jié)果有多種可能性，在數(shù)學(xué)上用一個(gè)隨機(jī)變量（或隨機(jī)向量）來描述。在許多情況下，人們不僅需要對隨機(jī)現(xiàn)象進(jìn)行一次觀測，而且要進(jìn)行多次，甚至接連不斷地觀測它的變化過程。這就要研究無限多個(gè)，即一族隨機(jī)變量。隨機(jī)過程理論就是研究隨機(jī)現(xiàn)象變化過程的概率規(guī)律性的。定義1 設(shè)是一族隨機(jī)變量，是一個(gè)實(shí)數(shù)集合，若對任意實(shí)數(shù)是一個(gè)隨機(jī)變量，則稱為隨機(jī)過程。稱為參數(shù)集合，參數(shù)可以看作時(shí)間。的每一個(gè)可能取值稱為隨機(jī)過程的一個(gè)狀態(tài)。其全體可能取值所構(gòu)成的集合稱為狀態(tài)空間，記作。當(dāng)參數(shù)集合為非負(fù)整數(shù)集時(shí)，隨機(jī)過程又稱隨機(jī)序列。本章要介紹的馬爾可夫鏈就是一類特殊的

2、隨機(jī)序列。例1 在一條自動生產(chǎn)線上檢驗(yàn)產(chǎn)品質(zhì)量，每次取一個(gè)，“廢品”記為1，“合格品”記為0。以表示第次檢驗(yàn)結(jié)果，則是一個(gè)隨機(jī)變量。不斷檢驗(yàn)，得到一列隨機(jī)變量，記為。它是一個(gè)隨機(jī)序列，其狀態(tài)空間。例2 在個(gè)商店聯(lián)營出租照相機(jī)的業(yè)務(wù)中（顧客從其中一個(gè)商店租出，可以到個(gè)商店中的任意一個(gè)歸還），規(guī)定一天為一個(gè)時(shí)間單位，“”表示“第天開始營業(yè)時(shí)照相機(jī)在第個(gè)商店”，。則是一個(gè)隨機(jī)序列，其狀態(tài)空間。例3 統(tǒng)計(jì)某種商品在時(shí)刻的庫存量，對于不同的，得到一族隨機(jī)變量，是一個(gè)隨機(jī)過程，狀態(tài)空間，其中為最大庫存量。我們用一族分布函數(shù)來描述隨機(jī)過程的統(tǒng)計(jì)規(guī)律。一般地，一個(gè)隨機(jī)過程，對于任意正整數(shù)及中任意個(gè)元素相應(yīng)的隨

3、機(jī)變量的聯(lián)合分布函數(shù)記為 （1）由于及的任意性，（1）式給出了一族分布函數(shù)。記為稱它為隨機(jī)過程的有窮維分布函數(shù)族。它完整地描述了這一隨機(jī)過程的統(tǒng)計(jì)規(guī)律性。§2 馬爾可夫鏈2.1 馬爾可夫鏈的定義現(xiàn)實(shí)世界中有很多這樣的現(xiàn)象：某一系統(tǒng)在已知現(xiàn)在情況的條件下，系統(tǒng)未來時(shí)刻的情況只與現(xiàn)在有關(guān)，而與過去的歷史無直接關(guān)系。比如，研究一個(gè)商店的累計(jì)銷售額，如果現(xiàn)在時(shí)刻的累計(jì)銷售額已知，則未來某一時(shí)刻的累計(jì)銷售額與現(xiàn)在時(shí)刻以前的任一時(shí)刻累計(jì)銷售額無關(guān)。上節(jié)中的幾個(gè)例子也均屬此類。描述這類隨機(jī)現(xiàn)象的數(shù)學(xué)模型稱為馬氏模型。定義2 設(shè)是一個(gè)隨機(jī)序列，狀態(tài)空間為有限或可列集，對于任意的正整數(shù)，若，有 （2）

4、則稱為一個(gè)馬爾可夫鏈（簡稱馬氏鏈），（2）式稱為馬氏性。事實(shí)上，可以證明若等式（2）對于成立，則它對于任意的正整數(shù)也成立。因此，只要當(dāng)時(shí)（2）式成立，就可以稱隨機(jī)序列具有馬氏性，即是一個(gè)馬爾可夫鏈。定義3 設(shè)是一個(gè)馬氏鏈。如果等式（2）右邊的條件概率與無關(guān)，即 （3）則稱為時(shí)齊的馬氏鏈。稱為系統(tǒng)由狀態(tài)經(jīng)過個(gè)時(shí)間間隔（或步）轉(zhuǎn)移到狀態(tài)的轉(zhuǎn)移概率。（3）稱為時(shí)齊性。它的含義是：系統(tǒng)由狀態(tài)到狀態(tài)的轉(zhuǎn)移概率只依賴于時(shí)間間隔的長短，與起始的時(shí)刻無關(guān)。本章介紹的馬氏鏈假定都是時(shí)齊的，因此省略“時(shí)齊”二字。2.2 轉(zhuǎn)移概率矩陣及柯爾莫哥洛夫定理對于一個(gè)馬爾可夫鏈，稱以步轉(zhuǎn)移概率為元素的矩陣為馬爾可夫鏈的步轉(zhuǎn)

5、移矩陣。當(dāng)時(shí)，記稱為馬爾可夫鏈的一步轉(zhuǎn)移矩陣，或簡稱轉(zhuǎn)移矩陣。它們具有下列三個(gè)基本性質(zhì)：（i）對一切，；（ii）對一切，；（iii）對一切，。當(dāng)實(shí)際問題可以用馬爾可夫鏈來描述時(shí)，首先要確定它的狀態(tài)空間及參數(shù)集合，然后確定它的一步轉(zhuǎn)移概率。關(guān)于這一概率的確定，可以由問題的內(nèi)在規(guī)律得到，也可以由過去經(jīng)驗(yàn)給出，還可以根據(jù)觀測數(shù)據(jù)來估計(jì)。例4 某計(jì)算機(jī)機(jī)房的一臺計(jì)算機(jī)經(jīng)常出故障，研究者每隔15分鐘觀察一次計(jì)算機(jī)的運(yùn)行狀態(tài)，收集了24小時(shí)的數(shù)據(jù)（共作97次觀察）。用1表示正常狀態(tài)，用0表示不正常狀態(tài)，所得的數(shù)據(jù)序列如下：111001001111111001111011111100111111111000

6、1101101111011011010111101110111101111110011011111100111解 設(shè)為第個(gè)時(shí)段的計(jì)算機(jī)狀態(tài)，可以認(rèn)為它是一個(gè)時(shí)齊馬氏鏈，狀態(tài)空間，編寫如下Matlab程序：a1='1110010011111110011110111111001111111110001101101'a2='111011011010111101110111101111110011011111100111'a=a1 a2;f00=length(findstr('00',a)f01=length(findstr('01',a

7、)f10=length(findstr('10',a)f11=length(findstr('11',a)求得96次狀態(tài)轉(zhuǎn)移的情況是：，8次； ，18次；，18次； ，52次，因此，一步轉(zhuǎn)移概率可用頻率近似地表示為例5 設(shè)一隨機(jī)系統(tǒng)狀態(tài)空間，記錄觀測系統(tǒng)所處狀態(tài)如下：4 3 2 1 4 3 1 1 2 32 1 2 3 4 4 3 3 1 11 3 3 2 1 2 2 2 4 42 3 2 3 1 1 2 4 3 1若該系統(tǒng)可用馬氏模型描述，估計(jì)轉(zhuǎn)移概率。解 首先將不同類型的轉(zhuǎn)移數(shù)統(tǒng)計(jì)出來分類記入下表轉(zhuǎn)移數(shù)1 2 3 4行和12344 4 1 13 2 4 24

8、 4 2 10 1 4 21011117各類轉(zhuǎn)移總和等于觀測數(shù)據(jù)中馬氏鏈處于各種狀態(tài)次數(shù)總和減1，而行和是系統(tǒng)從狀態(tài)轉(zhuǎn)移到其它狀態(tài)的次數(shù)，是由狀態(tài)到狀態(tài)的轉(zhuǎn)移次數(shù)，則的估計(jì)值。計(jì)算得Matlab計(jì)算程序如下：format ratclca=4 3 2 1 4 3 1 1 2 3 . 2 1 2 3 4 4 3 3 1 1 . 1 3 3 2 1 2 2 2 4 4 . 2 3 2 3 1 1 2 4 3 1;for i=1:4 for j=1:4 f(i,j)=length(findstr(i j,a); endendfni=(sum(f')'for i=1:4 p(i,:)=f

9、(i,:)/ni(i);endp例6（帶有反射壁的隨機(jī)徘徊）如果在原點(diǎn)右邊距離原點(diǎn)一個(gè)單位及距原點(diǎn)個(gè)單位處各立一個(gè)彈性壁。一個(gè)質(zhì)點(diǎn)在數(shù)軸右半部從距原點(diǎn)兩個(gè)單位處開始隨機(jī)徘徊。每次分別以概率和向右和向左移動一個(gè)單位；若在+1處，則以概率反射到2，以概率停在原處；在處，則以概率反射到，以概率停在原處。設(shè)表示徘徊步后的質(zhì)點(diǎn)位置。是一個(gè)馬爾可夫鏈，其狀態(tài)空間，寫出轉(zhuǎn)移矩陣。解 因此，為一個(gè)階方陣，即 。定理1 （柯爾莫哥洛夫開普曼定理）設(shè)是一個(gè)馬爾可夫鏈，其狀態(tài)空間，則對任意正整數(shù)有 其中的。定理2 設(shè)是一個(gè)馬氏鏈轉(zhuǎn)移矩陣（的行向量是概率向量），是初始分布行向量，則第步的概率分布為。例7 若顧客的購買

10、是無記憶的，即已知現(xiàn)在顧客購買情況，未來顧客的購買情況不受過去購買歷史的影響，而只與現(xiàn)在購買情況有關(guān)?，F(xiàn)在市場上供應(yīng)三個(gè)不同廠家生產(chǎn)的50克袋狀味精，用“”、“”、“”分別表示“顧客第次購買廠的味精”。顯然，是一個(gè)馬氏鏈。若已知第一次顧客購買三個(gè)廠味精的概率依次為0.2，0.4，0.4。又知道一般顧客購買的傾向由表2給出。求顧客第四次購買各家味精的概率。表2下 次 購 買上次購買 0.8 0.50.5 0.10.10.3 0.1 0.4 0.2解 第一次購買的概率分布為 轉(zhuǎn)移矩陣 則顧客第四次購買各家味精的概率為。2.3 轉(zhuǎn)移概率的漸近性質(zhì)極限概率分布現(xiàn)在我們考慮，隨的增大，是否會趨于某一固定

11、向量？先考慮一個(gè)簡單例子：轉(zhuǎn)移矩陣，當(dāng)時(shí)，又若取，則，為矩陣的對應(yīng)于特征值的特征（概率）向量，也稱為的不動點(diǎn)向量。哪些轉(zhuǎn)移矩陣具有不動點(diǎn)向量？為此我們給出正則矩陣的概念。定義一個(gè)馬氏鏈的轉(zhuǎn)移矩陣是正則的，當(dāng)且僅當(dāng)存在正整數(shù)，使的每一元素都是正數(shù)。定理若是一個(gè)馬氏鏈的正則陣，那么：（i）有唯一的不動點(diǎn)向量，的每個(gè)分量為正。（ii）的次冪（為正整數(shù)）隨的增加趨于矩陣，的每一行向量均等于不動點(diǎn)向量。例8 信息的傳播 一條新聞在等人中間傳播，傳播的方式是傳給，傳給，如此繼續(xù)下去，每次傳播都是由傳給。每次傳播消息的失真概率是，即將消息傳給時(shí)，傳錯(cuò)的概率是，這樣經(jīng)過長時(shí)間傳播，第個(gè)人得知消息時(shí)，消息的真實(shí)

12、程度如何？設(shè)整個(gè)傳播過程為隨機(jī)轉(zhuǎn)移過程，消息經(jīng)過一次傳播失真的概率為，轉(zhuǎn)移矩陣 是正則矩陣。又設(shè)是初始分布，則消息經(jīng)過次傳播后，其可靠程度的概率分布為。一般地，設(shè)時(shí)齊馬氏鏈的狀態(tài)空間為，如果對于所有，轉(zhuǎn)移概率存在極限 ，（不依賴于）或 ，則稱此鏈具有遍歷性。又若，則同時(shí)稱為鏈的極限分布。下面就有限鏈的遍歷性給出一個(gè)充分條件。定理4 設(shè)時(shí)齊（齊次）馬氏鏈的狀態(tài)空間為，是它的一步轉(zhuǎn)移概率矩陣，如果存在正整數(shù)，使對任意的，都有，則此鏈具有遍歷性；且有極限分布，它是方程組 或即 ，的滿足條件，的唯一解。例9 根據(jù)例7中給出的一般顧客購買三種味精傾向的轉(zhuǎn)移矩陣，預(yù)測經(jīng)過長期的多次購買之后，顧客的購買傾向

13、如何？解 這個(gè)馬氏鏈的轉(zhuǎn)移矩陣滿足定理4的條件，可以求出其極限概率分布。為此，解下列方程組：編寫如下的Matlab程序：format ratp=0.8 0.1 0.1;0.5 0.1 0.4;0.5 0.3 0.2;a=p'-eye(3);ones(1,3);b=zeros(3,1);1;p_limit=ab或者利用求轉(zhuǎn)移矩陣的轉(zhuǎn)置矩陣的特征值1對應(yīng)的特征(概率)向量，求得極限概率。編寫程序如下：p=0.8 0.1 0.1;0.5 0.1 0.4;0.5 0.3 0.2;p=sym(p');x,y=eig(p)for i=1:3 x(:,i)=x(:,i)/sum(x(:,i)

14、;endx求得，。這說明，無論第一次顧客購買的情況如何，經(jīng)過長期多次購買以后，廠產(chǎn)的味精占有市場的，兩廠產(chǎn)品分別占有市場的，。2.4 吸收鏈馬氏鏈還有一種重要類型吸收鏈。若馬氏鏈的轉(zhuǎn)移矩陣為，的最后一行表示的是，當(dāng)轉(zhuǎn)移到狀態(tài)4時(shí)，將停留在狀態(tài)4，狀態(tài)4稱為吸收狀態(tài)。如果馬氏鏈至少含有一個(gè)吸收狀態(tài)，并且從每一個(gè)非吸收狀態(tài)出發(fā)，都可以到達(dá)某個(gè)吸收狀態(tài)，那么這個(gè)馬氏鏈被稱為吸收鏈。具有個(gè)吸收狀態(tài)，個(gè)非吸收狀態(tài)的吸收鏈，它的轉(zhuǎn)移矩陣的標(biāo)準(zhǔn)形式為 （4）其中為階單位陣，為零陣，為矩陣，為矩陣。從（4）得 （5）（5）式中的子陣表示以任何非吸收狀態(tài)作為初始狀態(tài)，經(jīng)過步轉(zhuǎn)移后，處于個(gè)非吸收狀態(tài)的概率。在吸收

15、鏈中，令，則稱為基矩陣。對于具有標(biāo)準(zhǔn)形式（即(4)式）轉(zhuǎn)移矩陣的吸收鏈，可以證明以下定理：定理5 吸收鏈的基矩陣中的每個(gè)元素，表示從一個(gè)非吸收狀態(tài)出發(fā)，過程到達(dá)每個(gè)非吸收狀態(tài)的平均轉(zhuǎn)移次數(shù)。定理6 設(shè)，為吸收鏈的基矩陣，則的每個(gè)元素表示從非吸收狀態(tài)出發(fā)，到達(dá)某個(gè)吸收狀態(tài)被吸收之前的平均轉(zhuǎn)移次數(shù)。定理7 設(shè)，其中為吸收鏈的基矩陣，為（4）式中的子陣，則表示從非吸收狀態(tài)出發(fā)，被吸收狀態(tài)吸收的概率。例10 智力競賽問題 甲、乙兩隊(duì)進(jìn)行智力競賽。競賽規(guī)則規(guī)定：競賽開始時(shí)，甲、乙兩隊(duì)各記2分，在搶答問題時(shí)，如果甲隊(duì)贏得1分，那么甲隊(duì)的總分將增加1分，同時(shí)乙隊(duì)總分將減少1分。當(dāng)甲（或乙）隊(duì)總分達(dá)到4分時(shí)，

16、競賽結(jié)束，甲（或乙）獲勝。根據(jù)隊(duì)員的智力水平，知道甲隊(duì)贏得1分的概率為，失去1分的概率為，求：（i）甲隊(duì)獲勝的概率是多少？（ii）競賽從開始到結(jié)束，分?jǐn)?shù)轉(zhuǎn)移的平均次數(shù)是多少？（iii）甲隊(duì)獲得1、2、3分的平均次數(shù)是多少？分析 甲隊(duì)得分有5種可能，即0、1、2、3、4，分別記為狀態(tài)，其中和是吸收狀態(tài)，和是非吸收狀態(tài)。過程是以作為初始狀態(tài)。根據(jù)甲隊(duì)贏得1分的概率為，建立轉(zhuǎn)移矩陣： （6）將（6）式改記為標(biāo)準(zhǔn)形式：其中，計(jì)算 其中。因?yàn)槭浅跏紶顟B(tài)，根據(jù)定理5，甲隊(duì)獲得1，2，3分的平均次數(shù)為，。又 根據(jù)定理6，以為初始狀態(tài)，甲隊(duì)最終獲勝的分?jǐn)?shù)轉(zhuǎn)移的平均次數(shù)為。又因?yàn)楦鶕?jù)定理7，甲隊(duì)最后獲勝的概率。

17、Matlab程序如下：syms p qr=q,0;0,0;0,p;s=0,p,0;q,0,p;0,q,0;f=(eye(3)-s)(-1);f=simple(f)n=f*ones(3,1);n=simple(n)b=f*r;b=simple(b)§3 馬爾可夫鏈的應(yīng)用應(yīng)用馬爾可夫鏈的計(jì)算方法進(jìn)行馬爾可夫分析，主要目的是根據(jù)某些變量現(xiàn)在的情況及其變動趨向，來預(yù)測它在未來某特定區(qū)間可能產(chǎn)生的變動，作為提供某種決策的依據(jù)。例11（服務(wù)網(wǎng)點(diǎn)的設(shè)置問題）為適應(yīng)日益擴(kuò)大的旅游事業(yè)的需要，某城市的甲、乙、丙三個(gè)照相館組成一個(gè)聯(lián)營部，聯(lián)合經(jīng)營出租相機(jī)的業(yè)務(wù)。游客可由甲、乙、丙三處任何一處租出相機(jī)，用

18、完后，還在三處中任意一處即可。估計(jì)其轉(zhuǎn)移概率如表3所示：還 相 機(jī) 處甲乙丙租相機(jī)處甲乙丙0.20.80.10.800.300.20.6今欲選擇其中之一附設(shè)相機(jī)維修點(diǎn)，問該點(diǎn)設(shè)在哪一個(gè)照相館為最好？解 由于旅客還相機(jī)的情況只與該次租機(jī)地點(diǎn)有關(guān)，而與相機(jī)以前所在的店址無關(guān)，所以可用表示相機(jī)第次被租時(shí)所在的店址；“”、“”、“”分別表示相機(jī)第次被租用時(shí)在甲、乙、丙館。則是一個(gè)馬爾可夫鏈，其轉(zhuǎn)移矩陣由表3給出?？紤]維修點(diǎn)的設(shè)置地點(diǎn)問題，實(shí)際上要計(jì)算這一馬爾可夫鏈的極限概率分布。轉(zhuǎn)移矩陣滿足定理4的條件，極限概率存在，解方程組 得極限概率，。由計(jì)算看出，經(jīng)過長期經(jīng)營后，該聯(lián)營部的每架照相機(jī)還到甲、乙、丙照相館的概率分別為、。由于還到甲館的照相機(jī)較多，因此維修點(diǎn)設(shè)在甲館較好。但由于還到乙館的相機(jī)與還到甲館的相差不多，若是乙的其它因素更為有利的話，比如，交通較甲方便，便于零配件的運(yùn)輸，電力供應(yīng)穩(wěn)定等等，亦可考慮設(shè)在乙館。習(xí) 題 十 七1. 在英國，工黨成員的第二代加入工黨的概率為0.5，加入保守黨的概率為0.4，加入自由黨的概率為0.1。而保守黨成員的第二代加入保守黨的概率為0.7，加入工黨的概率為