17第十七章馬氏鏈模型

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

2、隨機序列。本章要介紹的馬爾可夫鏈就是一類特殊的隨機序列。例1在一條自動生產(chǎn)線上檢驗產(chǎn)品質(zhì)量，每次取一個，“廢品”記為1，“合格品” 記為0。以表示第n次檢驗結(jié)果，則是一個隨機變量。不斷檢驗，得到一列隨機 變量,&2，L ，記為&,n = 1,2,L 。它是一個隨機序列，其狀態(tài)空間E = 0,1。例2?在m個商店聯(lián)營出租照相機的業(yè)務中（顧客從其中一個商店租出，可以到m 個商店中的任意一個歸還），規(guī)定一天為一個時間單位，“孔=J ”表示“第t天開始營 業(yè)時照相機在第/個商店”，j = 1,2L ,m。則&,n = 1,2L 是一個隨機序列，其狀 態(tài)空間 E = 1,2,L , m。例3統(tǒng)計某種商品

3、在t時刻的庫存量，對于不同的t，得到一族隨機變量，& , t e0,+8）是一個隨機過程，狀態(tài)空間E = 0, R ，其中R為最大庫存量。t 一 ，一.一,我們用一族分布函數(shù)來描述隨機過程的統(tǒng)計規(guī)律。一般地，一個隨機過程& , t e T，對于任意正整數(shù)n及T中任意n個元素t ,L ,t相應的隨機變量& ,L ,&t1 nt1tn的聯(lián)合分布函數(shù)記為 TOC o 1-5 h z F（尤,L ,x ） = P& x ,L ,& x （1）t1L tn 1nt11tnn由于n及ti（i = 1,L ,n）的任意性，（1）式給出了一族分布函數(shù)。記為Ft Lt （氣,x）,七 e T,i = 1,L ,

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

5、i e E（k = 1,L ,n -1），有 k TOC o 1-5 h z P電+廣川9 = *廣-1,L ,&1 = = P9+廣川9 =i則稱& ,n = 1,2L 為一個馬爾可夫鏈（簡稱馬氏鏈），（2）式稱為馬氏性。事實上， n可以證明若等式（2）對于m = 1成立，則它對于任意的正整數(shù)m也成立。因此，只要當m = 1時（2）式成立，就可以稱隨機序列&,n = 1,2L 具有馬氏性， 即& ,n = 1,2L 是一個馬爾可夫鏈。n定義3設(shè)& ,n = 1,2L 是一個馬氏鏈。如果等式（2）右邊的條件概率與n無 關(guān)，即nP&= j |& = i = p （m）（3）則稱& , n = 1

6、,2L 為時齊的馬氏鏈。稱p （m）為系統(tǒng)由狀態(tài)i經(jīng)過m個時間間隔（或 nijm步）轉(zhuǎn)移到狀態(tài)j的轉(zhuǎn)移概率。（3）稱為時齊性，它的含義是：系統(tǒng)由狀態(tài)到狀態(tài) j的轉(zhuǎn)移概率只依賴于時間間隔的長短，與起始的時刻無關(guān)。本章介紹的馬氏鏈假定都 是時齊的，因此省略“時齊”二字。2.2轉(zhuǎn)移概率矩陣及柯爾莫哥洛夫定理對于一個馬爾可夫鏈&，n = 1,2,L ，稱以m步轉(zhuǎn)移概率p（m）為元素的矩陣 P（m） = * （m）為馬爾可夫鏈的m步轉(zhuǎn)移矩陣。當m = 1時，記P（1） = P稱為馬爾可 夫鏈的一步轉(zhuǎn)移矩陣，或簡稱轉(zhuǎn)移矩陣。它們具有下列三個基本性質(zhì)：對一切 i, j e E，0 p (m) 1；對一切 i

7、 e E， p(m) = 1；jeE,、，一 .八小、公A當= j（iii）對一切 i, J e E，p （0） =8 = $ 當.j 。當實際問題可以用馬爾可夫鏈來描述時，首先要確定它的狀態(tài)空間及參數(shù)集合，然 后確定它的一步轉(zhuǎn)移概率。關(guān)于這一概率的確定，可以由問題的內(nèi)在規(guī)律得到，也可以 由過去經(jīng)驗給出，還可以根據(jù)觀測數(shù)據(jù)來估計。例4某計算機機房的一臺計算機經(jīng)常出故障，研究者每隔15分鐘觀察一次計算 機的運行狀態(tài)，收集了 24小時的數(shù)據(jù)（共作97次觀察）。用1表示正常狀態(tài)，用0表 示不正常狀態(tài)，所得的數(shù)據(jù)序列如下：1110010011111110011110111111001111111110

8、001101101111011011010111101110111101111110011011111100111解 設(shè)Xn（n = 1L ,97）為第n個時段的計算機狀態(tài)，可以認為它是一個時齊馬氏 鏈，狀態(tài)空間E = 0,1編寫如下Matlab程序：a1=1110010011111110011110111111001111111110001101101;a2=111011011010111101110111101111110011011111100111;a=a1 a2;f00=length(findstr(00,a)f01=length(findstr(01,a)f10=length(fi

9、ndstr(10,a)f11=length(findstr(11,a)或者把上述數(shù)據(jù)序列保存到純文本文件data1.txt中，存放在Matlab下的 work子目錄中，編寫程序如下：clc,clearformat ratfid=fopen(data1.txt,r);a=;while (feof(fid)a=a fgetl(fid);endfor i=0:1for j=0:1s=int2str(i),int2str(j);f(i+1,j+1)=length(findstr(s,a);endendfs=sum(f);for i=1:2f(i,:)=f(i,:)/fs(i);end f求得96次狀態(tài)

10、轉(zhuǎn)移的情況是：0 0, 8 次；0 1 , 18 次；1 0 , 18 次；1 1, 52 次，因此，一步轉(zhuǎn)移概率可用頻率近似地表示為P0= P Xn+1848 +18 = 13P01=P Xn+1P10= P Xn+1=1IX = 0工=9=0 8 +18 = 1318_9_=1缶 +52 = 35= 0 IXnP11= P X= 1IX例5設(shè)一隨機系統(tǒng)狀態(tài)空間E =43 2 1 4 3 1 1 2 321 2 3 4 4 3 3 1 1133212224423 2 3 1 1 2 4 3 1nn+15226=1 18 + 52 = 351,2,3,4，記錄觀測系統(tǒng)所處狀態(tài)如下:估計轉(zhuǎn)移概率

11、P.。若該系統(tǒng)可用馬氏模型描述，估計轉(zhuǎn)移概率P.。解首先將不同類型的轉(zhuǎn)移數(shù)七統(tǒng)計出來分類記入表1。1234行和n1441111023242113442111401427n是由狀態(tài)，到狀態(tài)j的轉(zhuǎn)移次數(shù)，各類轉(zhuǎn)移總和zz n等于觀測數(shù)據(jù)中馬氏JI j鏈處于各種狀態(tài)次數(shù)總和減1,而行和氣是系統(tǒng)從狀態(tài)i轉(zhuǎn)移到其它狀態(tài)的次數(shù)，則 n的估計值P =-。計算得 j nJiY2 /52 /5 1/10 1/10 /3/112 /11 4 /11 2 /1仁P=84 /11 4 /11 2 /11 1/118 1) 個單位處各立一個彈性壁。一個質(zhì)點在數(shù)軸右半部從距原點兩個單位處開始隨機徘徊。 每次分別以概率P(

12、0 V p V 1)和q(q = 1- p)向右和向左移動一個單位；若在+1處，則 以概率P反射到2，以概率q停在原處；在s處，則以概率q反射到s-1，以概率p停 在原處。設(shè)J表示徘徊n步后的質(zhì)點位置。&,n = 1,2L 是一個馬爾可夫鏈，其狀 態(tài)空間E = 1,2,L ,s，寫出轉(zhuǎn)移矩陣P。解 P&4, =i = 祝，當i = 2當i豐2P1 j的,時= p, 當J = 1S,時當J =迎，2時其它泰psi =二,當 j = s 時 sJ機當J = s -1泌當j-i = 1時P. =，q 當 j i = 1 時(，=2,3,L , s U機1)因此，P為一個s階方陣，即p0L00/q0p

13、L00 8，0P =，q0L00 88LLLLLL80，一00q0p880000qP /定理1 (柯爾莫哥洛夫一開普曼定理)設(shè)& ,n = 1,2L 是一個馬爾可夫鏈，其 狀態(tài)空間E = 1,2,L ，則對任意正整數(shù)m,n有p (n + m) = p (n) p (m)jik kjkeE其中的i, j e E。定理2設(shè)P是一個馬氏鏈轉(zhuǎn)移矩陣(P的行向量是概率向量)，P(0)是初始分布 行向量，則第n步的概率分布為P (n) = P,n。一，-例7若顧客的購買是無記憶的，即已知現(xiàn)在顧客購買情況，未來顧客的購買情況 不受過去購買歷史的影響，而只與現(xiàn)在購買情況有關(guān)?，F(xiàn)在市場上供應A、B、C三個 不同

14、廠家生產(chǎn)的50克袋裝味精，用“& = 1 ”、 & = 2 ”、 & = 3 ”分別表示“顧客 第n次購買A、B、C廠的味精”。顯然，電,n = 1,2L 是一個馬氏鏈。若已知第一 次顧客購買三個廠味精的概率依次為0.2, 0.4, 0.4。又知道一般顧客購買的傾向由表2 給出。求顧客第四次購買各家味精的概率。表2下次購買ABC上次A0.80.10.1購買B0.50.10.4C0.50.30.2解第一次購買的概率分布為P (1)=虹2 0.4 0.4 TOC o 1-5 h z D80.10.1/c0 1c ,8 HYPERLINK l bookmark13 o Current Documen

15、t 轉(zhuǎn)移矩陣P = 0.50.10.4805。.30.28則顧客第四次購買各家味精的概率為P (4) = P (1) P3 = 10.7004 0.136 0.1636。2.3轉(zhuǎn)移概率的漸近性質(zhì)一極限概率分布現(xiàn)在我們考慮，隨n的增大0.5/0.38D5轉(zhuǎn)移矩陣P = 0，i, j = 1,2L，N則此鏈具有遍歷性；且有極限分布丸=(氣,L ,丸它是方程組N丸=丸尸或即丸，=R p ，j = 1,L ，Ni=1 的滿足條件N丸0，乙丸=1的唯一解。jj =1 j例9根據(jù)例7中給出的一般顧客購買三種味精傾向的轉(zhuǎn)移矩陣，預測經(jīng)過長期的 多次購買之后，顧客的購買傾向如何？解 這個馬氏鏈的轉(zhuǎn)移矩陣滿足定

16、理4的條件，可以求出其極限概率分布。為此，解下列方程組：祁=0.8 p + 0.5p + 0.5 pA 1123演 2 = 0.1 p1 + 0.1p 2 + 0.3p3 *3 = 0.1 p1 + 0.4 p2 + 0.2 p3 3+ P2+ p3 = 1編寫如下的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)移矩陣P的轉(zhuǎn)置矩陣Pt的特征值1對應的特征(概率)向量，求得極 限概率。編寫程序如下：clc,clear p=0

17、.8 0.1 0.1;0.5 0.1 0.4;0.5 0.3 0.2;p=sym(p);x,y=eig(p) y=diag(y);y=double(y);ind=find(y=max(y);p=x(:,ind)/sum(x(:,ind)5 求得P1 =-1113P28484這說明，無論第一次顧客購買的情況如何，經(jīng)過長期多次購買以后，A廠產(chǎn)的味511 13精占有市場的號，B，C兩廠產(chǎn)品分別占有市場的37，37。784 842.4吸收鏈馬氏鏈還有一種重要類型一吸收鏈。若馬氏鏈的轉(zhuǎn)移矩陣為12341 p3 0.3 0 0.4/_ 2 Q.2 0.3 0.2 0.3第一300.3 0.3 0.4884

18、 0001 8P的最后一行表示的是，當轉(zhuǎn)移到狀態(tài)4時，將停留在狀態(tài)4,狀態(tài)4稱為吸收狀態(tài)。如果馬氏鏈至少含有一個吸收狀態(tài)，并且從每一個非吸收狀態(tài)出發(fā)，都可以到達某 個吸收狀態(tài)，那么這個馬氏鏈被稱為吸收鏈。具有r個吸收狀態(tài)，s（s = n - r）個非吸收狀態(tài)的吸收鏈，它的nxn轉(zhuǎn)移矩陣的標 準形式為O/8YP = , r S /其中I為r階單位陣，O為r x s零陣，R為s x r矩陣，S為s x s矩陣。從（4）得Pn沮%8=Q Sn /（5）式中的子陣Sn表示以任何非吸收狀態(tài)作為初始狀態(tài)，經(jīng)過n步轉(zhuǎn)移后，處于s個 非吸收狀態(tài)的概率。（4）（5）在吸收鏈中，令F = （I - S）-1，則F

19、稱為基矩陣。對于具有標準形式（即（4）式）轉(zhuǎn)移矩陣的吸收鏈，可以證明以下定理：定理5吸收鏈的基矩陣F中的每個元素，表示從一個非吸收狀態(tài)出發(fā)，過程到達 每個非吸收狀態(tài)的平均轉(zhuǎn)移次數(shù)。定理6設(shè)N = FC，F(xiàn)為吸收鏈的基矩陣，C = 1 1 L 1L，則N的每個 元素表示從非吸收狀態(tài)出發(fā)，到達某個吸收狀態(tài)被吸收之前的平均轉(zhuǎn)移次數(shù)。定理7設(shè)B = FR =（七），其中F為吸收鏈的基矩陣，R為（4）式中的子陣， 則匕表示從非吸收狀態(tài)i出發(fā)，被吸收狀態(tài)j吸收的概率。例10智力競賽問題 甲、乙兩隊進行智力競賽。競賽規(guī)則規(guī)定：競賽開始時， 甲、乙兩隊各記2分，在搶答問題時，如果甲隊贏得1分，那么甲隊的總分將

20、增加1 分，同時乙隊總分將減少1分。當甲（或乙）隊總分達到4分時，競賽結(jié)束，甲（或乙） 獲勝。根據(jù)隊員的智力水平，知道甲隊贏得1分的概率為P，失去1分的概率為1- P，求：（i）甲隊獲勝的概率是多少？（ii）競賽從開始到結(jié)束，分數(shù)轉(zhuǎn)移的平均次數(shù) 是多少？ （iii）甲隊獲得1、2、3分的平均次數(shù)是多少？分析 甲隊得分有5種可能，即0、1、2、3、4,分別記為狀態(tài)a , a , a , a , a，01234其中a和a是吸收狀態(tài)，a , a和a是非吸收狀態(tài)。過程是以a作為初始狀態(tài)。根據(jù)041232甲隊贏得1分的概率為P，建立轉(zhuǎn)移矩陣：將（6）式改記為標準形式：Y P = , 2其中計算a0aia

21、2a3a4aY10000/0，a1- f-p0p0Uooi af010pOco2a3f f001-0coPooa4f0000項p =丫_ p0/Y 0P0/:00*coS = -p000%k 0PTko1-PR =p2Ypq f(6)F = (I S)t3, q l2pq,仃0000其中0= 1O因為。2是初始狀態(tài)，根據(jù)定理5,甲隊獲得1,2,3分的平均次數(shù)為q1- 2pq1l-2pqY pq p p2 /j/ N=FC=7，f q p 乂 1 2pq, Q2 q 翼尹 = t + 22 2 1+ Ipr1- 2pq2根據(jù)定理6,以氣為初始狀態(tài)，競賽從開始到結(jié)束分數(shù)轉(zhuǎn)移的平均次數(shù)為一。21-

22、2pqp3 /COP2 00- pq)p孚又因為Vpq)p B = FR = 1: l-2pq： p 2根據(jù)定理7,甲隊最后獲勝的概率b = 。221 一 2pqMatlab程序如下： syms p q r=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馬爾可夫鏈的應用應用馬爾可夫鏈的計算方法進行馬爾可夫分析，主要目的是根據(jù)某些變量現(xiàn)在的情 況及其變動趨向，來預測它在未來某特定區(qū)間可能產(chǎn)生的變動，作為提供某種決策的依 據(jù)。例1

23、1(服務網(wǎng)點的設(shè)置問題)為適應日益擴大的旅游事業(yè)的需要，某城市的甲、 乙、丙三個照相館組成一個聯(lián)營部，聯(lián)合經(jīng)營出租相機的業(yè)務。游客可由甲、乙、丙三 處任何一處租出相機，用完后，還在三處中任意一處即可。估計其轉(zhuǎn)移概率如表3所示。表3還相機處甲乙丙甲0.20.80租相機處乙0.800.2丙0.10.30.6今欲選擇其中之一附設(shè)相機維修點，問該點設(shè)在哪一個照相館為最好？解由于旅客還相機的情況只與該次租機地點有關(guān)，而與相機以前所在的店址無 關(guān)，所以可用Xn表示相機第n次被租時所在的店址;“ 乂尸1”、“ 乂尸2，二“ 乂尸3 ” 分別表示相機第n次被租用時在甲、乙、丙館。則Xn,= 1,2L 是一個馬

24、爾可夫鏈， 其轉(zhuǎn)移矩陣P由上表給出?？紤]維修點的設(shè)置地點問題，實際上要計算這一馬爾可夫 鏈的極限概率分布。轉(zhuǎn)移矩陣滿足定理4的條件，極限概率存在，解方程組呷=0.2 p + 0.8 p + 0.1pA 1123義=0.8 p1 + 0.3p3制 3 = 0.2 p2 + 0.6p3。+ p2 + p3 = 117168得極限概率 p1 = 41，p2 = 41，p3 = 41。由計算看出，經(jīng)過長期經(jīng)營后，該聯(lián)營部的每架照相機還到甲、乙、丙照相館的概 率分別為H、四、魚。由于還到甲館的照相機較多，因此維修點設(shè)在甲館較好。但 41 41 41由于還到乙館的相機與還到甲館的相差不多，若是乙的其它因素更為有利的話，比如， 交通較甲方便，便于零配件的運輸