隨機過程 馬爾科夫過程課件

第四章

馬爾可夫鏈

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

T

}為隨機過程，若對任意正整數(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

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

T

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

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

}

定義若隨機過程{Xn，n

T

}，對任意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

}為馬爾可夫鏈，簡稱馬氏鏈。4隨機過程馬爾科夫過程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隨機過程馬爾科夫過程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)計特性完全由條件概率P{Xn+1=in+1|Xn=in}確定。6隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率定義稱條件概率pij(n)=P{Xn+1=j|Xn=i}為馬爾可夫鏈{Xn，n

T

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

I。定義

若對任意的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隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率轉(zhuǎn)移概率性質(zhì)(1)

(2)

P稱為隨機矩陣8隨機過程馬爾科夫過程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)也為隨機矩陣9隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率定理4.1設(shè){Xn，n

T

}為馬爾可夫鏈，則對任意整數(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隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率證(1)11隨機過程馬爾科夫過程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隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率初始概率絕對概率初始分布絕對分布初始概率向量絕對概率向量定義13隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率

設(shè){Xn，n

T

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

I和n

1

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

(2)

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

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

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

T

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

,in

I和n

1

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

0

1i-1i

i+1一步轉(zhuǎn)移概率:18隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率n步轉(zhuǎn)移概率:i經(jīng)過k步進入j,向右移了x步,向左移了y步則19隨機過程馬爾科夫過程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隨機過程馬爾科夫過程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隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率

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

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

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

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隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率類似地得到其他轉(zhuǎn)移概率，于是轉(zhuǎn)移概率矩陣為若星期一、星期二均下雨，求星期四下雨的概率27隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率星期四下雨的情形如右，星期四下雨的概率2步轉(zhuǎn)移概率矩陣為一二三四RRRR00RRNR0128隨機過程馬爾科夫過程4.1馬爾可夫鏈與轉(zhuǎn)移概率例4.4具有吸收壁和反射壁的隨機游動狀態(tài)空間{1,2,3,4}，1為吸收壁，4為反射壁狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移矩陣29隨機過程馬爾科夫過程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隨機過程馬爾科夫過程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隨機過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類注(1)如果i有周期d，則對一切非零的n,n0(modd)，有（若，則n=0(modd)）(2)對充分大的n，（引理4.1）例題中當(dāng)n=1時，當(dāng)n>1時，32隨機過程馬爾科夫過程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隨機過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類由i出發(fā)經(jīng)n步首次到達j的概率(首達概率)規(guī)定由i出發(fā)經(jīng)有限步終于到達j的概率34隨機過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類若fii=1，稱狀態(tài)i為常返的；若fii<1，稱狀態(tài)i為非常返的i為非常返，則以概率1-

fii不返回到ii為常返，則

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

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

i<

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

i=

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

n<

，有定義36隨機過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類證37隨機過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類引理4.2周期的等價定義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)移首次到達各狀態(tài)的概率38隨機過程馬爾科夫過程4.2馬爾可夫鏈的狀態(tài)分類解狀態(tài)轉(zhuǎn)移圖如下，首達概率為

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

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

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

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

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

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

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

i=

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

i零常返，

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

從而子序列

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

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

i是遍歷的，d=1，

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

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

j：i

j且j

i

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

j，j

k，則i

k(2)若i

j，j

k，則i

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

j，存在l>0，使j

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

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

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

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

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

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

0,所以也是遍歷的

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