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

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

3、在t時(shí)刻的庫(kù)存量，對(duì)于不同的t，得到一族隨機(jī)變量，& , t e0,+8）是一個(gè)隨機(jī)過(guò)程，狀態(tài)空間E = 0, R ，其中R為最大庫(kù)存量。t 一 ，一.一,我們用一族分布函數(shù)來(lái)描述隨機(jī)過(guò)程的統(tǒng)計(jì)規(guī)律。一般地，一個(gè)隨機(jī)過(guò)程& , t e T，對(duì)于任意正整數(shù)n及T中任意n個(gè)元素t ,L ,t相應(yīng)的隨機(jī)變量& ,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稱它為隨機(jī)過(guò)程& ,t e T的有窮維分布函數(shù)族。它完整地描述了這一隨機(jī)過(guò)程的統(tǒng)計(jì) 規(guī)律性。t2馬爾可夫鏈2.1馬爾可夫鏈的定義現(xiàn)實(shí)世界中有很多這樣的現(xiàn)象：某一系統(tǒng)在已知現(xiàn)在情況 的條件下，系統(tǒng)未來(lái)時(shí)刻的情況只與現(xiàn)在有關(guān)，而與過(guò)去的歷史無(wú)直接關(guān)系。比如，研究一個(gè)商店的累計(jì)銷售額， 如果現(xiàn)在時(shí)刻的累計(jì)銷售額已知，則未來(lái)某一時(shí)刻的累計(jì)銷售額與現(xiàn)在時(shí)刻以前的任一 時(shí)刻累計(jì)銷售額無(wú)關(guān)。上節(jié)中的幾個(gè)例子也均屬此類。描述這類隨機(jī)現(xiàn)象的數(shù)學(xué)模型稱 為馬氏模型。定義2設(shè)&n,n = 1,2,L 是一個(gè)隨機(jī)序列，狀態(tài)空間E為有限或可列集，對(duì)于任 意的正整數(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 為一個(gè)馬爾可夫鏈（簡(jiǎn)稱馬氏鏈），（2）式稱為馬氏性。事實(shí)上， n可以證明若等式（2）對(duì)于m = 1成立，則它對(duì)于任意的正整數(shù)m也成立。因此，只要當(dāng)m = 1時(shí)（2）式成立，就可以稱隨機(jī)序列&,n = 1,2L 具有馬氏性， 即& ,n = 1,2L 是一個(gè)馬爾可夫鏈。n定義3設(shè)& ,n = 1,2L 是一個(gè)馬氏鏈。如果等式（2）右邊的條件概率與n無(wú) 關(guān)，即nP&= j |& = i = p （m）（3）則稱& , n = 1

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

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

8、001101101111011011010111101110111101111110011011111100111解 設(shè)Xn（n = 1L ,97）為第n個(gè)時(shí)段的計(jì)算機(jī)狀態(tài)，可以認(rèn)為它是一個(gè)時(shí)齊馬氏 鏈，狀態(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è)一隨機(jī)系統(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，記錄觀測(cè)系統(tǒng)所處狀態(tài)如下:估計(jì)轉(zhuǎn)移概率

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

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

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

14、廠家生產(chǎn)的50克袋裝味精，用“& = 1 ”、 & = 2 ”、 & = 3 ”分別表示“顧客 第n次購(gòu)買A、B、C廠的味精”。顯然，電,n = 1,2L 是一個(gè)馬氏鏈。若已知第一 次顧客購(gòu)買三個(gè)廠味精的概率依次為0.2, 0.4, 0.4。又知道一般顧客購(gòu)買的傾向由表2 給出。求顧客第四次購(gòu)買各家味精的概率。表2下次購(gòu)買ABC上次A0.80.10.1購(gòu)買B0.50.10.4C0.50.30.2解第一次購(gòu)買的概率分布為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則顧客第四次購(gòu)買各家味精的概率為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中給出的一般顧客購(gòu)買三種味精傾向的轉(zhuǎn)移矩陣，預(yù)測(cè)經(jīng)過(guò)長(zhǎng)期的 多次購(gòu)買之后，顧客的購(gòu)買傾向如何？解 這個(gè)馬氏鏈的轉(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對(duì)應(yīng)的特征(概率)向量，求得極 限概率。編寫程序如下：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這說(shuō)明，無(wú)論第一次顧客購(gòu)買的情況如何，經(jīng)過(guò)長(zhǎng)期多次購(gòu)買以后，A廠產(chǎn)的味511 13精占有市場(chǎng)的號(hào)，B，C兩廠產(chǎn)品分別占有市場(chǎng)的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的最后一行表示的是，當(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è)馬氏鏈被稱為吸收鏈。具有r個(gè)吸收狀態(tài)，s（s = n - r）個(gè)非吸收狀態(tài)的吸收鏈，它的nxn轉(zhuǎn)移矩陣的標(biāo) 準(zhǔ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)過(guò)n步轉(zhuǎn)移后，處于s個(gè) 非吸收狀態(tài)的概率。（4）（5）在吸收鏈中，令F = （I - S）-1，則F

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

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

21、2a3a4aY10000/0，a1- f-p0p0Uooi af010pOco2a3f f001-0coPooa4f0000項(xiàng)p =丫_ p0/Y 0P0/:00*coS = -p000%k 0PTko1-PR =p2Ypq f(6)F = (I S)t3, q l2pq,仃0000其中0= 1O因?yàn)椤?是初始狀態(tài)，根據(jù)定理5,甲隊(duì)獲得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)，競(jìng)賽從開始到結(jié)束分?jǐn)?shù)轉(zhuǎn)移的平均次數(shù)為一。21-

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

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

24、爾可夫鏈， 其轉(zhuǎn)移矩陣P由上表給出。考慮維修點(diǎn)的設(shè)置地點(diǎn)問(wèn)題，實(shí)際上要計(jì)算這一馬爾可夫 鏈的極限概率分布。轉(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ì)算看出，經(jīng)過(guò)長(zhǎng)期經(jīng)營(yíng)后，該聯(lián)營(yíng)部的每架照相機(jī)還到甲、乙、丙照相館的概 率分別為H、四、魚。由于還到甲館的照相機(jī)較多，因此維修點(diǎn)設(shè)在甲館較好。但 41 41 41由于還到乙館的相機(jī)與還到甲館的相差不多，若是乙的其它因素更為有利的話，比如， 交通較甲方便，便于零配件的運(yùn)輸