隨機(jī)過程 馬爾科夫過程課件

第四章

馬爾可夫鏈

隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率定義設(shè){X(t)，t

T

}為隨機(jī)過程，若對(duì)任意正整數(shù)n及t1<t2<

<tn，P{X(t1)=x1,

,X(tn-1)=xn-1}>0，且條件分布P{X(tn)

xn|X(t1)=x1,

,X(tn-1)=xn-1}=P{X(tn)

xn|X(tn-1)=xn-1}，則稱{X(t)，t

T

}為馬爾可夫過程?！钊魌1,t2,,tn-2表示過去，tn-1表示現(xiàn)在，tn表示將來，馬爾可夫過程表明：在已知現(xiàn)在狀態(tài)的條件下，將來所處的狀態(tài)與過去狀態(tài)無關(guān)。2隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率馬爾可夫過程通常分為三類：(1)時(shí)間、狀態(tài)都是離散的，稱為馬爾可夫鏈(2)時(shí)間連續(xù)、狀態(tài)離散的，稱為連續(xù)時(shí)間馬爾可夫鏈(3)時(shí)間、狀態(tài)都是連續(xù)的，稱為馬爾可夫過程3隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率隨機(jī)過程{Xn，n

T

}，參數(shù)T={0,1,2,

},狀態(tài)空間I={i0,i1,i2,

}

定義若隨機(jī)過程{Xn，n

T

}，對(duì)任意n

T和i0,i1,

,in+1

I，條件概率P{Xn+1=in+1|X0=i0,X1=i1,

,Xn=in}=P{Xn+1=in+1|Xn=in}，則稱{Xn，n

T

}為馬爾可夫鏈，簡(jiǎn)稱馬氏鏈。4隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率馬爾可夫鏈的性質(zhì)P{X0=i0,X1=i1,

,Xn=in}=P{Xn=in|X0=i0,X1=i1,

,Xn-1=in-1}

P{X0=i0,X1=i1,

,Xn-1=in-1}=P{Xn=in|Xn-1=in-1}

P{Xn-1=in-1|X0=i0,X1=i1,

,Xn-2=in-2}

P{X0=i0,X1=i1,

,Xn-2=in-2}=P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|Xn-2=in-2}

P{X0=i0,X1=i1,

,Xn-2=in-2}5隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率=

=P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|Xn-2=in-2}

P{X1=i1|X0=i0}P{X0=i0}

馬爾可夫鏈的統(tǒng)計(jì)特性完全由條件概率P{Xn+1=in+1|Xn=in}確定。6隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率定義稱條件概率pij(n)=P{Xn+1=j|Xn=i}為馬爾可夫鏈{Xn，n

T

}在時(shí)刻n的一步轉(zhuǎn)移概率，簡(jiǎn)稱轉(zhuǎn)移概率，其中i,j

I。定義

若對(duì)任意的i,j

I，馬爾可夫鏈{Xn,n

T

}的轉(zhuǎn)移概率pij(n)與n無關(guān)，則稱馬爾可夫鏈?zhǔn)驱R次的，并記pij(n)為pij。齊次馬爾可夫鏈具有平穩(wěn)轉(zhuǎn)移概率，狀態(tài)空間I={1,2,3,

}，一步轉(zhuǎn)移概率為7隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率轉(zhuǎn)移概率性質(zhì)(1)

(2)

P稱為隨機(jī)矩陣8隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率定義稱條件概率

=P{Xm+n=j|Xm=i}為馬爾可夫鏈{Xn，n

T

}的n步轉(zhuǎn)移概率(i,j

I,m0,n1)。n步轉(zhuǎn)移矩陣其中

P(n)也為隨機(jī)矩陣9隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率定理4.1設(shè){Xn，n

T

}為馬爾可夫鏈，則對(duì)任意整數(shù)n

0,0

l<n和i,j

I，n步轉(zhuǎn)移概率具有性質(zhì)(1)

(2)

(3)

P(n)=PP(n-1)(4)

P(n)=Pn10隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率證(1)11隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率(2)在(1)中令l=1,k=k1,得由此可遞推出公式(3)矩陣乘法(4)由(3)推出說明：(1)此為C-K方程(切普曼-柯爾莫哥洛夫)(2)n步轉(zhuǎn)移概率由一步轉(zhuǎn)移概率確定，

n步轉(zhuǎn)移概率矩陣由一步轉(zhuǎn)移概率矩陣確定(n次冪)12隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率初始概率絕對(duì)概率初始分布絕對(duì)分布初始概率向量絕對(duì)概率向量定義13隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率

設(shè){Xn，n

T

}為馬爾可夫鏈，則對(duì)任意整數(shù)j

I和n

1

，絕對(duì)概率pj(n)具有性質(zhì)(1)

(2)

(3)PT(n)=PT(0)P(n)(4)PT(n)=PT(n-1)P定理4.214隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率證(1)

15隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率(2)(3)(4)為(1)(2)的矩陣表示。16隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率

定理4.3設(shè){Xn，n

T

}為馬爾可夫鏈，則對(duì)任意整數(shù)i1,i2,

,in

I和n

1

，有性質(zhì)證17隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率例4.1無限制隨機(jī)游動(dòng)qp-1

0

1i-1i

i+1一步轉(zhuǎn)移概率:18隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率n步轉(zhuǎn)移概率:i經(jīng)過k步進(jìn)入j,向右移了x步,向左移了y步則19隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率例4.2賭徒輸光問題甲有賭資a元，乙有賭資b元，賭一局輸者給贏者1元，無和局。甲贏的概率為p，乙贏的概率為q=1-p，求甲輸光的概率。解狀態(tài)空間I={0,1,2,

,c}，c=a+bqpa-1a

a+10a+b20隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率設(shè)ui表示甲從狀態(tài)i出發(fā)轉(zhuǎn)移到狀態(tài)0的概率，求ua顯然u0

=1，uc=0(u0表示已知甲輸光情形下甲輸光的概率，uc表示已知乙輸光情形下甲輸光的概率)ui=pui+1

+qui-1

(i=1,2,

,c-1)（甲在狀態(tài)i下輸光：甲贏一局后輸光或甲輸一局后輸光）21隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率

22隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率

23隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率24隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率

25隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率例4.3天氣預(yù)報(bào)問題

RR表示連續(xù)兩天有雨，記為狀態(tài)0NR表示第1天無雨第2天有雨，記為狀態(tài)1RN表示第1天有雨第2天無雨，記為狀態(tài)2NN表示連續(xù)兩天無雨，記為狀態(tài)3p00=P{R今R明|R昨R今}=P{R明|R昨R今}=0.7p01=P{N今R明|R昨R今}=0p02=P{R今N明|R昨R今}=P{N明|R昨R今}=0.3p03=P{N今N明|R昨R今}=026隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率類似地得到其他轉(zhuǎn)移概率，于是轉(zhuǎn)移概率矩陣為若星期一、星期二均下雨，求星期四下雨的概率27隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率星期四下雨的情形如右，星期四下雨的概率2步轉(zhuǎn)移概率矩陣為一二三四RRRR00RRNR0128隨機(jī)過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率例4.4具有吸收壁和反射壁的隨機(jī)游動(dòng)狀態(tài)空間{1,2,3,4}，1為吸收壁，4為反射壁狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移矩陣29隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類{Xn,n

0}是離散馬爾可夫鏈，pij為轉(zhuǎn)移概率，i,j

I，I={0,1,2,}為狀態(tài)空間，{pj,j

I}為初始分布定義4.3

狀態(tài)i的周期d：d=G.C.D{n:>0}(最大公約數(shù)greatestcommondivisor)如果d>1，就稱i為周期的，如果d=1，就稱i為非周期的30隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類例4.6設(shè)馬爾可夫鏈的狀態(tài)空間I={1,2,,9}，轉(zhuǎn)移概率如下圖從狀態(tài)1出發(fā)再返回狀態(tài)1的可能步數(shù)為T={4,6,8,10,}，T的最大公約數(shù)為2，從而狀態(tài)1的周期為231隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類注(1)如果i有周期d，則對(duì)一切非零的n,n0(modd)，有（若，則n=0(modd)）(2)對(duì)充分大的n，（引理4.1）例題中當(dāng)n=1時(shí)，當(dāng)n>1時(shí)，32隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類例4.7狀態(tài)空間I={1,2,3,4}，轉(zhuǎn)移概率如圖，狀態(tài)2和狀態(tài)3有相同的周期d=2，但狀態(tài)2和狀態(tài)3有顯著的區(qū)別。當(dāng)狀態(tài)2轉(zhuǎn)移到狀態(tài)3后，再不能返回到狀態(tài)2，狀態(tài)3總能返回到狀態(tài)3。這就要引入常返性概念。33隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類由i出發(fā)經(jīng)n步首次到達(dá)j的概率(首達(dá)概率)規(guī)定由i出發(fā)經(jīng)有限步終于到達(dá)j的概率34隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類若fii=1，稱狀態(tài)i為常返的；若fii<1，稱狀態(tài)i為非常返的i為非常返，則以概率1-

fii不返回到ii為常返，則

構(gòu)成一概率分布，期望值

表示由i出發(fā)再返回到i的平均返回時(shí)間定義35隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類若

i<

，則稱常返態(tài)i為正常返的;若

i=

，則稱常返態(tài)i為零常返的，非周期的正常返態(tài)稱為遍歷狀態(tài)。首達(dá)概率與n步轉(zhuǎn)移概率有如下關(guān)系式定理4.4對(duì)任意狀態(tài)i,j及1

n<

，有定義36隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類證37隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類引理4.2周期的等價(jià)定義G.C.D=G.C.D例4.8設(shè)馬爾可夫鏈的狀態(tài)空間I={1,2,3}，轉(zhuǎn)移概率矩陣為求從狀態(tài)1出發(fā)經(jīng)n步轉(zhuǎn)移首次到達(dá)各狀態(tài)的概率38隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類解狀態(tài)轉(zhuǎn)移圖如下，首達(dá)概率為

39隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類同理可得40隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類以下討論常返性的判別與性質(zhì)數(shù)列的母函數(shù)與卷積{an,n

0}為實(shí)數(shù)列，母函數(shù){bn,n

0}為實(shí)數(shù)列，母函數(shù)則{an}與{bn}的卷積的母函數(shù)41隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類定理4.5狀態(tài)i常返的充要條件為如i非常返，則證:規(guī)定，則由定理4.442隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類

43隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類對(duì)0

s<144隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類

45隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類定理4.7設(shè)i常返且有周期為d，則其中

i為i的平均返回時(shí)間，當(dāng)

i=

時(shí)推論設(shè)i常返，則(1)i零常返(2)i遍歷46隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類證(1)

i零常返，

i=，由定理4.7知，對(duì)d的非整數(shù)倍數(shù)的n，

從而子序列

i是零常返的47隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類(2)

子序列所以d=1，從而i為非周期的，i是遍歷的

i是遍歷的，d=1，

i<，48隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類狀態(tài)的可達(dá)與互通狀態(tài)i可達(dá)狀態(tài)j，i

j：存在n>0,使?fàn)顟B(tài)i與狀態(tài)j互通，i

j：i

j且j

i

定理4.8可達(dá)關(guān)系與互通關(guān)系都具有傳遞性，即(1)若i

j，j

k，則i

k(2)若i

j，j

k，則i

k49隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類證(1)i

j，存在l>0，使j

k，存在m>0，使由C-K方程所以i

k(2)由(1)直接推出50隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類定理4.8如i

j，則(1)i與j同為常返或非常返，如為常返，則它們同為正常返或零常返(2)i與j有相同的周期51隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類

例4.9設(shè)馬氏鏈{Xn}的狀態(tài)空間為I={0,1,2,

}，轉(zhuǎn)移概率為考察狀態(tài)0的類型52隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類

可得出0為正常返的由于，所以0的周期為d=10為非周期的，從而為遍歷狀態(tài)對(duì)于其它狀態(tài)i,由于i

0,所以也是遍歷的

53隨機(jī)過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類例4.10對(duì)無限制隨機(jī)游動(dòng)由斯特林近似公式可推出(1)當(dāng)且僅當(dāng)p=q=1/2時(shí)，4