[工學(xué)]馬爾科夫鏈例題整理

《[工學(xué)]馬爾科夫鏈例題整理》由會員分享，可在線閱讀，更多相關(guān)《[工學(xué)]馬爾科夫鏈例題整理（61頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、若 表示質(zhì)點(diǎn)在時刻n所處的位置，分析它的 概率特性。,例1,直線上帶吸收壁的隨機(jī)游動（醉漢游動）,設(shè)一質(zhì)點(diǎn)在線段1，5 上隨機(jī)游動，每秒鐘發(fā)生一次隨機(jī)游動，移動的規(guī)則是：,（1）若移動前在2，3，4處，則均以概率 向左或向右 移動一單位； （2）若移動前在1，5處，則以概率1停留在原處。,質(zhì)點(diǎn)在1，5兩點(diǎn)被“吸收”,前言：馬爾可夫過程的描述分類,,,,首頁,無記憶性,未來處于某狀態(tài)的概率特性只與現(xiàn)在狀態(tài)有關(guān)，而與以前的狀態(tài)無關(guān)，這種特性叫無記憶性（無后效性）。,例4 布朗運(yùn)動,若 表示質(zhì)點(diǎn)在時刻n所處的位置，求 一步轉(zhuǎn)移概率。,引例,例1 直線上帶吸收壁的隨機(jī)游動（醉漢游動）,設(shè)一

2、質(zhì)點(diǎn)在線段1，5 上隨機(jī)游動，每秒鐘發(fā)生一次隨機(jī)游動，移動的規(guī)則是：,（1）若移動前在2，3，4處，則均以概率 向左或向右 移動一單位； （2）若移動前在1，5處，則以概率1停留在原處。,質(zhì)點(diǎn)在1，5兩點(diǎn)被“吸收”,一步轉(zhuǎn)移概率矩陣的計算,,,首頁,有兩個吸收壁的隨機(jī)游動,其一步轉(zhuǎn)移矩陣為,狀態(tài)空間I=1，2，3，4，5，,參數(shù)集T=1，2，3，，,例2帶有反射壁的隨機(jī)游動,設(shè)隨機(jī)游動的狀態(tài)空間I = 0，1，2，，移動的規(guī)則是： （1）若移動前在0處，則下一步以概率p向右移動一個單位，以概率q停留在原處（p+q=1）； （2）若移動前在其它點(diǎn)處，則均以概率p向右移動一個單位，以概率q向

3、左移動一個單位。,設(shè) 表示在時刻n質(zhì)點(diǎn)的位置， 則 ， 是一個齊次馬氏鏈，寫出其一步轉(zhuǎn)移概率。,,,首頁,,,,首頁,,,首頁,例3一個圓周上共有N格（按順時針排列），一個質(zhì)點(diǎn)在該圓周上作隨機(jī)游動，移動的規(guī)則是：質(zhì)點(diǎn)總是以概率p順時針游動一格， 以概率 逆時針游動一格。試求轉(zhuǎn)移概率矩陣。,,,首頁,4一個質(zhì)點(diǎn)在全直線的整數(shù)點(diǎn)上作隨機(jī)游動，移動的規(guī)則是：以概率p從i移到i-1，以概率q從i移到i+1，以概率r停留在i，且 ，試求轉(zhuǎn)移概率矩陣。,,,首頁,5設(shè)袋中有a個球，球?yàn)楹谏幕虬咨模耠S機(jī)地從袋中取一個球，然后放回一個不同顏色的球。若在袋里有k

4、個白球，則稱系統(tǒng)處于狀態(tài)k，試用馬爾可夫鏈描述這個模型（稱為愛倫菲斯特模型），并求轉(zhuǎn)移概率矩陣。,解 這是一個齊次馬氏鏈，其狀態(tài)空間為,I=0，1，2，，a,一步轉(zhuǎn)移矩陣是,,,首頁,練習(xí)題 扔一顆色子，若前n次扔出的點(diǎn)數(shù)的最大值為j，就說 試問 是否為馬氏鏈？求一步轉(zhuǎn)移概率矩陣。,I=1，2，3，4，5，6,,,首頁,,,例1,甲、乙兩人進(jìn)行比賽，設(shè)每局比賽中甲勝的概率是p，乙勝的概率是q，和局的概率是 ，（ ）。設(shè)每局比賽后，勝者記“+1”分，負(fù)者記“1”分，和局不記分。當(dāng)兩人中有一人獲得2分結(jié)束比賽。以 表示比賽至第n局時甲獲得的分?jǐn)?shù)。,（1）寫出狀態(tài)空間；,（3）問

5、在甲獲得1分的情況下，再賽二局可以結(jié)束比賽的概率是多少？,首頁,解,（1）,記甲獲得“負(fù)2分”為狀態(tài)1，獲得“負(fù)1分”為狀態(tài)2，獲得“0分”為狀態(tài)3，獲得“正1分”為狀態(tài)4，獲得“正2分”為狀態(tài)5，則狀態(tài)空間為,一步轉(zhuǎn)移概率矩陣,首頁,（2）二步轉(zhuǎn)移概率矩陣,首頁,（3）,從而結(jié)束比賽的概率；,從而結(jié)束比賽的概率。,所以題中所求概率為,首頁,分析,例2 賭徒輸光問題,賭徒甲有資本a元，賭徒乙有資本b元，兩人進(jìn)行賭博，每賭一局輸者給贏者1元，沒有和局，直賭至兩人中有一人輸光為止。設(shè)在每一局中，甲獲勝的概率為p，乙獲勝的概率為 ，求甲輸光的概率。,這個問題實(shí)質(zhì)上是帶有兩個吸收壁的隨機(jī)游動。

6、從甲的角度看，他初始時刻處于a，每次移動一格，向右移（即贏1元）的概率為p，向左移（即輸1元）的概率為q。如果一旦到達(dá)0（即甲輸光）或a + b（即乙輸光）這個游動就停止。這時的狀態(tài)空間為0，1，2，，c，c = a + b，。現(xiàn)在的問題是求質(zhì)點(diǎn)從a出發(fā)到達(dá)0狀態(tài)先于到達(dá)c狀態(tài)的概率。,首頁,考慮質(zhì)點(diǎn)從j出發(fā)移動一步后的情況,解,同理,根據(jù)全概率公式有,這一方程實(shí)質(zhì)上是一差分方程，它的邊界條件是,首頁,于是,,,設(shè),則可得到兩個相鄰差分間的遞推關(guān)系,于是,欲求,先求,需討論 r,首頁,當(dāng),,,而,兩式相比,首頁,故,,,當(dāng),而,因此,故,首頁,用同樣的方法可以求得乙先輸光的概率,由以上計算結(jié)果

7、可知,首頁,例3 排隊問題,顧客到服務(wù)臺排隊等候服務(wù)，在每一個服務(wù)周期中只要服務(wù)臺前有顧客在等待，就要對排在前面的一位提供服務(wù)，若服務(wù)臺前無顧客時就不能實(shí)施服務(wù)。,則有,求其轉(zhuǎn)移矩陣,在第n周期已有一個 顧客在服務(wù)，到第n+1 周期已服務(wù)完畢,解,,,先求出轉(zhuǎn)移概率,首頁,所以轉(zhuǎn)移矩陣為,,,首頁,,,證,定理4.3 馬爾科夫鏈的有限維分布：,練習(xí)：馬氏鏈的狀態(tài)空間I=1，2，3，初始概率為,例4,市場占有率預(yù)測,設(shè)某地有1600戶居民，某產(chǎn)品只有甲、乙、丙3廠家在該地銷售。經(jīng)調(diào)查，8月份買甲、乙、丙三廠的戶數(shù)分別為480，320，800。9月份里，原買甲的有48戶轉(zhuǎn)買乙產(chǎn)品，有96戶轉(zhuǎn)買丙產(chǎn)

8、品；原買乙的有32戶轉(zhuǎn)買甲產(chǎn)品，有64戶轉(zhuǎn)買丙產(chǎn)品；原買丙的有64戶轉(zhuǎn)買甲產(chǎn)品，有32戶轉(zhuǎn)買乙產(chǎn)品。用狀態(tài)1、2、3分別表示甲、乙、丙三廠，試求,（1）轉(zhuǎn)移概率矩陣； （2）9月份市場占有率的分布； （3）12月份市場占有率的分布；,解,（1）E1，2，3,狀態(tài)1、2、3分別表示甲、乙、丙的用戶,一步轉(zhuǎn)移概率矩陣為,（2）以1600除8月份甲，乙，丙的戶數(shù)，得初始概率分布（即初始市場占有率）,所以9月份市場占有率分布為,（3）12月份市場占有率分布為,,,例1,其一步轉(zhuǎn)移矩陣為,試研究各狀態(tài)間的關(guān)系，并畫出狀態(tài)傳遞圖。,解,先按一步轉(zhuǎn)移概率，畫出各狀態(tài)間的傳遞圖,首頁,由圖可知,狀態(tài)0可到達(dá)狀

9、態(tài)1，經(jīng)過狀態(tài)1又可到達(dá)狀態(tài)2；反之，從狀態(tài)2出發(fā)經(jīng)狀態(tài)1也可到達(dá)狀態(tài)0。,因此，狀態(tài)空間I的各狀態(tài)都是互通的。,又由于I 的任意狀態(tài)i (i = 0，1，2)不能到達(dá)I 以外的任何狀態(tài)，,所以I是一個閉集,而且I 中沒有其它閉集,所以此馬氏鏈?zhǔn)遣豢杉s的。,首頁,例2,其一步轉(zhuǎn)移矩陣為,試討論哪些狀態(tài)是吸收態(tài)、閉集及不可約鏈。,解,先按一步轉(zhuǎn)移概率，畫出各狀態(tài)間的傳遞圖,首頁,,,,閉集，,,,由圖可知,狀態(tài)3為吸收態(tài),且,閉集，,閉集，,其中 是不可約的。,又因狀態(tài)空間I有閉子集，,故此鏈為非不可約鏈。,首頁,3常返態(tài)與瞬時態(tài),則稱狀態(tài)i為常返態(tài),則稱狀態(tài)i為瞬時態(tài),注,“常返”一詞

10、，有時又稱“返回”、“常駐”或“持久”,“瞬時”也稱“滑過” 或“非常返”,定理4,定理5,定理6,如果i為常返態(tài)，且 ，則j也是常返態(tài)。,定理7,所有常返態(tài)構(gòu)成一個閉集,5正常返態(tài)與零常返態(tài),平均返回時間,從狀態(tài)i出發(fā)，首次返回狀態(tài)i的平均時間,稱為狀態(tài)i平均返回時間.,根據(jù)的值是有限或無限，可把常返態(tài)分為兩類：,設(shè)i是常返態(tài)，,則稱i為正常返態(tài)；,則稱i為零常返態(tài)。,,,首頁,,例,其一步轉(zhuǎn)移矩陣如下，是對I進(jìn)行分解。,I可分解為：C1=2，3, 4 C2=5，6,7 兩個閉集及N=1 ，即I=N+ C1+ C2,,用極限判斷狀態(tài)類型的準(zhǔn)則,（2）i是零常返態(tài),（3）i是正常返態(tài),（

11、1）i是瞬時態(tài),且,且,首頁,例3,轉(zhuǎn)移矩陣,試對其狀態(tài)分類。,解,按一步轉(zhuǎn)移概率， 畫出各狀態(tài)間的傳遞圖,首頁,從圖可知，此鏈的每一狀態(tài)都可到達(dá)另一狀態(tài)，即4個狀態(tài)都是相通的。,考慮狀態(tài)1是否常返，,于是狀態(tài)1是常返的。,又因?yàn)?所以狀態(tài)1是正常返的。,此鏈所有狀態(tài)都是正常返的。,三、狀態(tài)的周期與遍歷,1周期狀態(tài),對于任意的 ，令,其中GCD表示最大公約數(shù),則稱 為周期態(tài)，,則稱 為非周期態(tài)。,定理11,2遍歷狀態(tài),若狀態(tài)i是正常返且非周期，則稱i為遍歷狀態(tài)。,例4,設(shè)馬氏鏈的狀態(tài)空間I = 0,1,2,，轉(zhuǎn)移概率為,試討論各狀態(tài)的遍歷性。,解,根據(jù)轉(zhuǎn)移概率作出狀態(tài)傳遞圖,首頁,從圖

12、可知，對任一狀態(tài) 都有 ，,故由定理可知，I 中的所以狀態(tài)都是相通的，,因此只需考慮狀態(tài)0是否正常返即可。,,故,從而0是常返態(tài)。,又因?yàn)?所以狀態(tài)0為正常返。,又由于,故狀態(tài)0為非周期的,從而狀態(tài)0是遍歷的。,故所有狀態(tài)i都是遍歷的。,例5設(shè)馬氏鏈的狀態(tài)空間I=1，2，3，4，其一步轉(zhuǎn)移矩陣為,解,試對其狀態(tài)分類。,按一步轉(zhuǎn)移概率，畫出各狀態(tài)間的傳遞圖,它是有限狀態(tài)的馬氏鏈，故必有一個常返態(tài)，又鏈中四個狀態(tài)都是互通的。因此，所有狀態(tài)都是常返態(tài)，這是一個有限狀態(tài)不可約的馬氏鏈。,可繼續(xù)討論是否為正常返態(tài),可討論狀態(tài)1,狀態(tài)1是常返態(tài),狀態(tài)1是正常返態(tài),所以，全部狀態(tài)都是正常返態(tài),首頁

13、,例1,其一步轉(zhuǎn)移矩陣為,試證此鏈具有遍歷性，并求平穩(wěn)分布和各狀態(tài)的平均返回時間,解,由于,,,首頁,所以,因此，該馬氏鏈具有遍歷性。,解得,所以馬氏鏈的平穩(wěn)分布為,各狀態(tài)的平均返回時間,例2,設(shè)有6個球（其中2個紅球，4個白球）分放于甲、乙兩個盒子中，每盒放3個，今每次從兩個盒中各任取一球并進(jìn)行交換，以 表示開始時甲盒中紅球的個數(shù)， （ ）表示經(jīng)n次交換后甲盒中的紅球數(shù)。,( 1 ) 求馬氏鏈 ， 的轉(zhuǎn)移概率矩陣；,( 2 ) 證明 ， 是遍歷的；,（3）求,（4）求,,,首頁,解,其一步轉(zhuǎn)移矩陣為,甲,乙,紅球0 白球3,紅球2 白球1,紅球1 白球2,紅球1 白球2,

14、紅球2 白球1,紅球0 白球3,,,由狀態(tài)傳遞圖,（2）由于它是一個有限馬氏鏈，故必有一個常返態(tài)，,又鏈中三個狀態(tài)0、1、2都相通，所以每個狀態(tài)都是常返態(tài)。 所以是一個不可約的有限馬氏鏈，從而每個狀態(tài)都是正常返的。,所以此鏈為非周期的。,故此鏈?zhǔn)遣豢杉s非周期的正常返鏈，即此鏈?zhǔn)潜闅v的。,,,首頁,也可以利用定理1證明遍歷性,首頁,解之得,故得,,,首頁,（4）,,,首頁,例3,市場占有率預(yù)測,設(shè)某地有1600戶居民，某產(chǎn)品只有甲、乙、丙3廠家在該地銷售。經(jīng)調(diào)查，8月份買甲、乙、丙三廠的戶數(shù)分別為480，320，800。9月份里，原買甲的有48戶轉(zhuǎn)買乙產(chǎn)品，有96戶轉(zhuǎn)買丙產(chǎn)品；原買乙的有32戶轉(zhuǎn)

15、買甲產(chǎn)品，有64戶轉(zhuǎn)買丙產(chǎn)品；原買丙的有64戶轉(zhuǎn)買甲產(chǎn)品，有32戶轉(zhuǎn)買乙產(chǎn)品。用狀態(tài)1、2、3分別表示甲、乙、丙三廠，試求,（1）轉(zhuǎn)移概率矩陣； （2）9月份市場占有率的分布； （3）12月份市場占有率的分布； （4）當(dāng)顧客流如此長期穩(wěn)定下去市場占有率的分布。 （5）各狀態(tài)的平均返回時間,首頁,解,（1） 由題意得頻數(shù)轉(zhuǎn)移矩陣為,再用頻數(shù)估計概率，得轉(zhuǎn)移概率矩陣為,（2）以1600除以N中各行元素之和，得初始概率分布（即初始市場占有率）,,,首頁,所以9月份市場占有率分布為,（3）12月份市場占有率分布為,,,首頁,（4）由于該鏈不可約、非周期、狀態(tài)有限正常返的，所以是遍歷的。,解方程組,即得當(dāng)顧客流如此長期穩(wěn)定下去是市場占有率的分布為,（5）,例4 (書中69頁例4.18）,其一步轉(zhuǎn)移矩陣為,試并每個不可約閉集的平穩(wěn)分布,,,的平穩(wěn)分布得,狀態(tài)空間可分解為：C=2，3, 4 D=5，6,7 兩個閉集，分別求對應(yīng)轉(zhuǎn)移概率矩陣,