版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
數(shù)理統(tǒng)計與隨機過程馬爾科夫鏈第一頁,共三十四頁,2022年,8月28日第十一章馬爾可夫鏈本章首先從隨機過程在不同時刻狀態(tài)之間的特殊的統(tǒng)計聯(lián)系,引入馬爾可夫(Markoff)過程的概念。然后,對馬爾可夫鏈(狀態(tài)、時間都是離散的馬爾可夫過程)的兩個基本問題,即轉移概率的確定以及遍歷性問題作不同程度的研究和介紹。馬爾可夫過程的理論在近代物理、生物學、管理科學、經濟、信息處理以及數(shù)字計算方法等方面都有重要應用。第二頁,共三十四頁,2022年,8月28日§11.1馬爾可夫過程及其概率分布在物理學中,很多確定性現(xiàn)象遵從如下演變原則:由時刻t0系統(tǒng)或過程所處的狀態(tài),可以決定系統(tǒng)或過程在時刻t>t0所處的狀態(tài),而無需借助于t0以前系統(tǒng)或過程所處狀態(tài)的歷史資料。如微分方程問題所描繪的物理過程就屬于這類確定性現(xiàn)象。把上述原則延伸到隨機現(xiàn)象,即當一物理系統(tǒng)或過程遵循的是某種統(tǒng)計規(guī)律時,可仿照上面的原則,引入以下的馬爾可夫性或無后效性:過程(或系統(tǒng))在時刻t0所處的狀態(tài)為已知的條件下,過程在時刻t>t0所處狀態(tài)的條件分布與過程在t0之前所處的狀態(tài)無關。通俗地說,就是在已經知道過程“現(xiàn)在”的條件下,其“將來”不依賴于“過去”。第三頁,共三十四頁,2022年,8月28日
現(xiàn)用分布函數(shù)來表述馬爾可夫性.設隨機過程{X(t),t∈T}的狀態(tài)空間為I。如果對時間t的任意n個數(shù)值t1<t2<…<tn,
n≥3,ti
∈T,在條件X(ti)=xi,xi∈I,i=1,2,…,n-1下,X(tn)的條件分布函數(shù)恰等于在條件X(tn-1)=xn-1下X(tn)的條件分布函數(shù)則稱過程{X(t),t∈T}具有馬爾可夫性或無后效性,并稱此過程為馬爾可夫過程。(1.1)第四頁,共三十四頁,2022年,8月28日例1設{X(t),t
≥0}是獨立增量過程,且X(0)=0,證明{X(t),t
≥0}是一個馬爾可夫過程。證由(1.1)式知,只要證明在已知X(tn-1)=xn-1的條件下X(tn)與X(tj),j=1,2,…,n-2相互獨立即可?,F(xiàn)由獨立增量過程的定義知道,當0<tj<tn-1<tn,j=1,2,…,n-2時,增量X(tj)-X(0)與X(tn)-X(tn-1)相互獨立。根據(jù)條件X(0)=0和X(tn-1)=xn-1,即有X(tj)與X(tn)-X(tn-1)相互獨立。再由第三章§4定理知,此時X(tn)與X(tj),j=1,2,…,n-2相互獨立。這表明X(t)具有后無效性,即{X(t),t
≥0}是一個馬爾可夫過程?!跤缮侠?,泊松過程是時間連續(xù)狀態(tài)離散的馬氏過程;維納過程是時間狀態(tài)都連續(xù)的馬氏過程。第五頁,共三十四頁,2022年,8月28日時間和狀態(tài)都是離散的馬爾可夫過程稱為馬爾可夫鏈,簡稱馬氏鏈,記為{Xn=X(n),n=0,1,2,…},它可以看作在時間集T1={0,1,2,…}上對離散狀態(tài)的馬氏過程相繼觀察的結果.我們約定記鏈的狀態(tài)空間I={a1,a2,…},ai∈R。在鏈的情形,馬爾可夫性通常用條件分布律來表示,即對任意的正整數(shù)n,r和0≤t1<t2<…<tr<m;m,n∈T1,有(1.2)其中ai∈I。記上式右端為Pij(m,m+n),我們稱條件概率
Pij(m,m+n)=P{Xm+n=aj∣Xm=ai}為馬氏鏈在時刻m處于狀態(tài)ai條件下,在時刻m+n轉移到狀態(tài)aj的轉移概率。(1.3)第六頁,共三十四頁,2022年,8月28日
由于鏈在時刻m從任何一狀態(tài)ai出發(fā),到另一時刻m+n,必然轉移到a1,a2,…諸狀態(tài)中的某一個,所以(1.4)由轉移概率組成的矩陣P(m,m+n)=(Pij(m,m+n))稱為馬氏鏈的轉移概率矩陣。由(1.4)式知,此矩陣的每一行元之和等于1。當轉移概率Pij(m,m+n)只與i,j及時間間距n有關時,把它記為Pij(n),即
Pij(m,m+n)=Pij(n)并稱此轉移概率具有平穩(wěn)性。同時也稱此鏈是齊次的或時齊的。以下我們限于討論齊次馬氏鏈。第七頁,共三十四頁,2022年,8月28日在馬氏鏈為齊次的情形下,由(1.3)式定義的轉移概率Pij(n)=P{Xm+n=aj∣Xm=ai}稱為馬氏鏈的n步轉移概率,P(n)=(Pij(n))為n步轉移概率矩陣。在以下的討論中特別重要的是一步轉移概率Pij=Pij(1)=P{Xm+1=aj∣Xm=ai}或由它們組成的一步轉移概率矩陣在上述矩陣的左側和上邊標上狀態(tài)a1,a2,…是為了顯示Pij是由狀態(tài)ai經一步轉移到狀態(tài)aj的概率。第八頁,共三十四頁,2022年,8月28日例2
(0-1傳輸系統(tǒng))在如下圖只傳傳輸數(shù)字0和1的串聯(lián)系統(tǒng)中,設每一級的傳真率(輸出與輸入數(shù)字相同的概率稱為系統(tǒng)的傳真率,相反情形稱為誤碼率)為p,誤碼率為q=1-p,并設一個單位時間傳輸一級,X0是第一級的輸入,Xn是第n級的輸出(n≥1),那么{Xn,n=0,1,2,…}是一隨機過程,狀態(tài)空間I={0,1},而且當Xn=i,i∈I為已知時,Xn+1所處的狀態(tài)的概率分布只與Xn=i
有關,而與時刻n以前所處的狀態(tài)無關,所以它是一個馬氏鏈,而且還是齊次的。它的一步轉移概率和一步轉移概率分別為和第九頁,共三十四頁,2022年,8月28日例2
一維隨機游動設一醉漢Q在如下圖所示直線的點集I={1,2,3,4,5}上作隨機游動,且僅在1秒、2秒等時刻發(fā)生游動。游動的概率規(guī)則是:如果Q現(xiàn)在位于點i(1<i<5),則下一時刻各以1/3的概率向左或向右移動一格,或以1/3的概率留在原處;如果Q現(xiàn)在位于1(或5)這點上,則下一時刻就以概率1移動到2(或4)這一點上。1和5這兩點稱為反射壁。上面這種游動稱為帶有兩個反射壁的隨機游動。第十頁,共三十四頁,2022年,8月28日若以Xn表示時刻n時Q的位置,不同的位置就是Xn的不同狀態(tài),那么{Xn
,n=0,1,2…}是一隨機過程,狀態(tài)空間就是I,而且Xn=i,i∈I為已知時,Xn+1所處的狀態(tài)的概率分布只與Xn=i
有關,而與Q在時刻n以前如何達到i是完全無關的,所以{Xn
,n=0,1,2…}是一馬氏鏈,而且還是齊次的,它的一步轉移概率和一步轉移概率矩陣分別為010001/31/31/30001/31/31/30001/31/31/3000101
234512345和P=第十一頁,共三十四頁,2022年,8月28日如果把1這一點改為吸收壁,即是說Q一旦到達1這一點,則就永遠留在點1上,此時,相應鏈的轉移概率矩陣只須把P中的第一橫行改為(1,0,0,0,0)。總之,改變游動的概率規(guī)則,就可得到不同方式的隨機游動和相應的馬式鏈。隨機游動的思想在數(shù)值計算方法方面有重要應用。例4排隊模型設服務系統(tǒng)由一個服務員和只可以容納兩個人的等候室組成,見圖11-3。服務規(guī)則是:先到先服務,后來者首先需在等候室。假定一顧客到達系統(tǒng)時發(fā)現(xiàn)系統(tǒng)內已有3個顧客(一個正在接受服務,兩個在等候室排隊),則該顧客即離去。設時間間隔Δt內有一個顧客進入系統(tǒng)的概率為q,有一原來被服務的顧客離開系統(tǒng)(即服務完畢)的概率為p。又設當Δt充分小時,在這時間間隔內多于一個顧客進入或離開系統(tǒng)實際上是不可能的。再設有無顧客來到與服務是否完畢是相互獨立。現(xiàn)用馬氏鏈來描述這個服務系統(tǒng)。第十二頁,共三十四頁,2022年,8月28日圖11-3
設Xn=X(nΔt)表示時刻nΔt
時系統(tǒng)內的顧客數(shù),即系統(tǒng)的狀態(tài),{Xn
,n=0,1,2…}是一隨機過程,狀態(tài)空間I={0,1,2,3},可知它是一個齊次馬氏鏈。下面來計算此馬氏鏈的一步轉移概率。
p00—在系統(tǒng)內沒有顧客的條件下,經Δt后仍沒有顧客的概率(此處是條件概率,以下同)p00=1-q.
p01---在系統(tǒng)內沒有顧客的條件下,經Δt
后有一顧客進入系統(tǒng)的概率,p01=q.
p10---系統(tǒng)內恰有一個顧客正在接受服務的條件下,經Δt后系統(tǒng)內無人的概率,它等于在Δt
間隔內顧客因服務完畢而離去,且無人進入系統(tǒng)的概率,p10=p(1-q)第十三頁,共三十四頁,2022年,8月28日
p11—系統(tǒng)內恰有1個顧客的條件下,在Δt間隔內,他因服務完畢而離去,而另一顧客進入系統(tǒng),或者正在接受服務的顧客將繼續(xù)要求服務,且無人進入系統(tǒng)的概率。p11=pq+(1-p)(1-q).p12
—正在接受服務的顧客繼續(xù)要求服務,且另一個顧客進入系統(tǒng)的概率p12=q(1-p).p13
—正在接受服務的顧客繼續(xù)要求服務,且在Δt
間隔內有兩個顧客進入系統(tǒng)的概率,由假設,后者實際上是不可能發(fā)生的,p13=0.
類似地,有p21=p32=p(1-q),p22=pq+(1-p)(1-q),p23=q(1-p),pij=0(|i-j|≥2).p33
—一人因服務完畢而離去且另一人將進入系統(tǒng),或者無人離開系統(tǒng)的概率,p33=pq+(1-p)第十四頁,共三十四頁,2022年,8月28日
于是該馬氏鏈的一步轉移概率矩陣為
在實際問題中,一步轉移概率通??赏ㄟ^統(tǒng)計試驗確定,下面看一實例。例5
計算機機房的一臺計算機經常出故障,研究者每隔15分鐘觀察一次計算機的運行狀態(tài),收集了24小時的數(shù)據(jù)(共作97次觀察)。用1表示正常狀態(tài),用0表示不正常狀態(tài),所得的數(shù)據(jù)序列如下:第十五頁,共三十四頁,2022年,8月28日設Xn為第n(n=1,2…,97)個時段的計算機狀態(tài),可以認為它是一個馬氏鏈,狀態(tài)空間I={0,1}.96次狀態(tài)轉移的情況是:0→0,8次;0→1,18次;
1→0,18次;1→1,52次.因此,一步轉移概率可用頻率近似地表示為第十六頁,共三十四頁,2022年,8月28日例6(續(xù)例5)
若計算機在前一段(15分鐘)的狀態(tài)為0,問在此條件下從此時段起此計算機能連續(xù)正常工作3刻鐘(3個時段)的概率為多少?解
由題意,某一時段的狀態(tài)為0就是初始狀態(tài)為0,即X0=0。由乘法公式、馬氏性和齊次性得,所求條件概率為第十七頁,共三十四頁,2022年,8月28日接著,我們來研究齊次馬氏鏈的有限維分布。首先,記稱它為馬氏鏈的初始分布。再看馬氏鏈在任意時刻n∈T1的一維分布:顯然,應有由全概率公式即(1.6)(1.7)一維分布(1.6)也可用行向量表示成
p(n)=(p1(n),p2(n),…pj(n),…)這樣,利用矩陣乘法(I是可列無限集時,仍用有限階矩陣乘法的規(guī)則確定矩陣之積的元),(1.7)式可寫成
p(n)=p(0)P(n)此式表明,馬氏鏈在任一時刻n∈T1時的一維分布由初始分布p(0)和n
步轉移概率矩陣所確定。(1.6)′(1.7)′第十八頁,共三十四頁,2022年,8月28日
又,對于任意n個時刻t1<t2<…<tn,ti∈T1
以及狀態(tài),馬氏鏈的n維分布:(1.8)由此,并結合(1.7)或(1.7)′可知:齊次馬氏鏈的有限維分布同樣完全由初始分布和轉移概率確定??傊?,轉移概率決定了馬氏鏈的統(tǒng)計規(guī)律。因此,確定馬氏鏈的任意n步轉移概率就成為馬氏鏈理論中的重要問題之一。第十九頁,共三十四頁,2022年,8月28日
§11.2多步轉移概率的確定為了確定齊次馬氏鏈的n步轉移概率Pij(n),首先介紹Pij(n)所滿足的基本方程。設{X(n),n∈T1}是一齊次馬氏鏈,則對任意的u,v∈T1,有方程(2.1)就是著名的切普曼-柯莫哥洛夫(Chapman-Kolmogorov)方程,簡稱C-K方程。
C-K方程基于下述事實,即“從時刻s所處的狀態(tài)ai,即X(s)=ai出發(fā),經時段u+v轉移到狀態(tài)aj
,即X(s+u+v)=aj”這一事件可分解成“從X(s)=ai
出發(fā),先經時段u轉移到中間狀態(tài)ak(k,=1,2…),再從ak經時段v轉移到狀態(tài)aj”這樣一些事件和事件(見圖11-4)。第二十頁,共三十四頁,2022年,8月28日圖11-4
方程(2.1)的證明如下:先固定ak∈I
和s∈T1,由條件概率定義和乘法定理,有(2.2)第二十一頁,共三十四頁,2022年,8月28日又由于事件組“X(s+u)=ak”,k=1,2,…構成一劃分,故有將(2.2)式代入上式,即得所要證明的C-K方程。
C-K方程也可寫成矩陣形式:
P(u+v)=P(u)P(v)(2.1)′
利用C-K方程我們容易確定n步轉移概率。事實上,在(2.1)′式中令u=1,v=n-1,得遞推關系:
P(n)=P(1)P(n-1)=PP(n-1),從而可得P(n)=Pn.(2.3)就是說,對齊次馬氏鏈而言,n步轉移概率矩陣是一步轉移概率矩陣的n次方。進而可知,齊次馬氏鏈的有限維分布可由初始與一步轉移概率完全確定。第二十二頁,共三十四頁,2022年,8月28日例1
設{Xn,n≥0}是具有三個狀態(tài)0,1,2的齊次馬氏鏈,一步轉移概率矩陣為初始分布pi(0)=P{X0=i}=1/3,i=0,1,2.試求:(i)P{X0=0,X2=1};(ii)P{X2=1}解先求出二步轉移概率矩陣于是(i)(ii)由(1.7)式,第二十三頁,共三十四頁,2022年,8月28日例2在§1例2中,(i)設p=0.9,求系統(tǒng)二級傳輸后的傳真率與三級傳輸后的誤碼率;(ii)設初始分布P1
(0)=P{X0
=1}=α,P0
(0)=P{X0
=0}=1-α
,又已知系統(tǒng)經n級傳輸后輸出為1,問原發(fā)字符也是1的概率是多少?解先求出n步轉移概率矩陣P(n)=Pn。由于有相異的特征值λ1=1,λ2=p-q,由線形代數(shù)知識,可將P表示成對角陣的相似矩陣。具體做法是:求出λ1,λ2對應的特征相量(q=1-p)(q=1-p)第二十四頁,共三十四頁,2022年,8月28日令則(2.4)
(i)由(2.4)式可知,當p=0.9時,系統(tǒng)經二級傳輸后的傳真率與三級傳輸?shù)恼`碼率分別為
(ii)根據(jù)貝葉斯公式,當已知系統(tǒng)經n級傳輸后輸出為1,原發(fā)字符也是1的概率為第二十五頁,共三十四頁,2022年,8月28日對于只有兩個狀態(tài)的馬氏鏈,一步轉移概率矩陣一般可表示為:利用類似于例2的方法,可得n步轉移概率矩陣為第二十六頁,共三十四頁,2022年,8月28日§11.3遍歷性對于一般的兩個狀態(tài)的馬氏鏈,由(2.5)式可知,當0<a,b<1時,pij(n)有極限上述極限的意義:對固定的狀態(tài)j,不管鏈在某一時刻從什么狀態(tài)(i=0或1)出發(fā),通過長時間的轉移,到達狀態(tài)j的概率都趨近于
j。這就是所謂的遍歷性。又由于
0+
1=1,所以(
0,
1)=構成一分布律,稱它為鏈的極限分布。另外,如若我們能用其他簡便的方法直接由一步轉移概率求得極限分布,則反過來,當n>>1時就可得到n步轉移概率的近似值:pij(n)≈
j
第二十七頁,共三十四頁,2022年,8月28日一般,設齊次馬氏鏈的狀態(tài)空間為I,若對于所有ai,aj∈I,轉移概率Pij(n)存在極限或則稱此鏈具有遍歷性,又若,則同時稱為鏈的極限分布。齊次馬氏鏈在什么條件下才具有遍歷性?如何求出它的極限分布?這問題在理論上已經完滿解決,下面僅就只有有限個狀態(tài)的鏈,即有限鏈的遍歷性給出一個充分條件。第二十八頁,共三十四頁,2022年,8月28日定理
設齊次馬氏鏈{Xn
,n≥1}的狀態(tài)空間為I={a1
,a2
,…,aN},P是它的一步轉移概率矩陣,如果存在整數(shù)m,使對任意的ai
,aj∈I,都有
Pij(m)>0,i,j=1,2,…,N,(3.1)則此鏈具有遍歷性,且有極限分布=(1,
2,…,N),它是方程組
=P或即(3.2)的滿足條件(3.3)的唯一解。
依照定理,為證有限鏈是遍歷的,只需要找一正整數(shù)m,使m步轉移概率矩陣Pm無零元。而求極限分布的問題,化為求解方程組(3.2)的問題。注意,方程組(3.2)中僅N-1個未知數(shù)是獨立的,而唯一解可用歸一條件確定。第二十九頁,共三十四頁,2022年,8月28日在定理的條件下,馬氏鏈的極限分布又是平穩(wěn)分布。意即,若用作為鏈的初始分布,即p(0)=,則鏈在任一時刻n∈T1的分布p(n)永遠與一致。事實上,有
p(n)=p(0)p(n)=
pn
=
pn-1
=…=
p=例1
試說明§1例2中,帶有兩個放射壁的隨機游動是遍歷的,并求其極限分布(平穩(wěn)分布)。解為簡便計,以符號“×”代表轉移概率矩陣的正元素,于是,由§1例2中的一步轉移概率矩陣P,得第三十頁,共三十四頁,2022年,8月28日即P(4)無零元。由定理,鏈是遍歷的。再根據(jù)(3.2)和(3.3)式,寫
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度嬰幼兒游泳館加盟服務合同4篇
- 二零二五年度實木地板翻新與保養(yǎng)服務合同4篇
- 2025年代理協(xié)議示范文本-辦公文具代理合同
- 2025版別墅區(qū)物業(yè)委托經營管理服務標準范本3篇
- 二零二五年度公司股權激勵計劃后續(xù)管理與跟蹤合同2篇
- 2025年中國雙面羊絨大衣行業(yè)市場調研分析及投資戰(zhàn)略咨詢報告
- 2025年度海洋科學研究中心研究員聘用合同
- 2025年度交通行業(yè)短期運輸司機勞動合同
- 二零二五年度消防安全員消防技術咨詢服務聘用合同
- 二零二五年度農業(yè)科技推廣勞務合同執(zhí)行與效果評估
- 第三單元名著導讀《經典常談》知識清單 統(tǒng)編版語文八年級下冊
- 第十七章-阿法芙·I·梅勒斯的轉變理論
- 焊接機器人在汽車制造中應用案例分析報告
- 合成生物學在生物技術中的應用
- 中醫(yī)門診病歷
- 廣西華銀鋁業(yè)財務分析報告
- 無違法犯罪記錄證明申請表(個人)
- 大學生勞動教育PPT完整全套教學課件
- 繼電保護原理應用及配置課件
- 《殺死一只知更鳥》讀書分享PPT
- 蓋洛普Q12解讀和實施完整版
評論
0/150
提交評論