馬爾科夫鏈例題整理.ppt

《馬爾科夫鏈例題整理.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《馬爾科夫鏈例題整理.ppt（61頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

若表示質(zhì)點(diǎn)在時(shí)刻n所處的位置，分析它的概率特性。,例1,直線上帶吸收壁的隨機(jī)游動(dòng)（醉漢游動(dòng)）,設(shè)一質(zhì)點(diǎn)在線段[1，5]上隨機(jī)游動(dòng)，每秒鐘發(fā)生一次隨機(jī)游動(dòng)，移動(dòng)的規(guī)則是：,（1）若移動(dòng)前在2，3，4處，則均以概率向左或向右移動(dòng)一單位；（2）若移動(dòng)前在1，5處，則以概率1停留在原處。,質(zhì)點(diǎn)在1，5兩點(diǎn)被“吸收”,前言：馬爾可夫過(guò)程的描述分類(lèi),,,,首頁(yè),無(wú)記憶性,未來(lái)處于某狀態(tài)的概率特性只與現(xiàn)在狀態(tài)有關(guān)，而與以前的狀態(tài)無(wú)關(guān)，這種特性叫無(wú)記憶性（無(wú)后效性）。,例4布朗運(yùn)動(dòng),若表示質(zhì)點(diǎn)在時(shí)刻n所處的位置，求一步轉(zhuǎn)移概率。,引例,例1直線上帶吸收壁的隨機(jī)游動(dòng)（醉漢游動(dòng)）,設(shè)一質(zhì)點(diǎn)在線段[1，5]上隨機(jī)游動(dòng)，每秒鐘發(fā)生一次隨機(jī)游動(dòng)，移動(dòng)的規(guī)則是：,（1）若移動(dòng)前在2，3，4處，則均以概率向左或向右移動(dòng)一單位；（2）若移動(dòng)前在1，5處，則以概率1停留在原處。,質(zhì)點(diǎn)在1，5兩點(diǎn)被“吸收”,一步轉(zhuǎn)移概率矩陣的計(jì)算,,,首頁(yè),有兩個(gè)吸收壁的隨機(jī)游動(dòng),其一步轉(zhuǎn)移矩陣為,狀態(tài)空間I={1，2，3，4，5}，,參數(shù)集T={1，2，3，………}，,例2．帶有反射壁的隨機(jī)游動(dòng),設(shè)隨機(jī)游動(dòng)的狀態(tài)空間I={0，1，2，…}，移動(dòng)的規(guī)則是：（1）若移動(dòng)前在0處，則下一步以概率p向右移動(dòng)一個(gè)單位，以概率q停留在原處（p+q=1）；（2）若移動(dòng)前在其它點(diǎn)處，則均以概率p向右移動(dòng)一個(gè)單位，以概率q向左移動(dòng)一個(gè)單位。,設(shè)表示在時(shí)刻n質(zhì)點(diǎn)的位置，則{，}是一個(gè)齊次馬氏鏈，寫(xiě)出其一步轉(zhuǎn)移概率。,,,首頁(yè),,,,首頁(yè),,,首頁(yè),例3．一個(gè)圓周上共有N格（按順時(shí)針排列），一個(gè)質(zhì)點(diǎn)在該圓周上作隨機(jī)游動(dòng)，移動(dòng)的規(guī)則是：質(zhì)點(diǎn)總是以概率p順時(shí)針游動(dòng)一格，以概率逆時(shí)針游動(dòng)一格。試求轉(zhuǎn)移概率矩陣。,,,首頁(yè),4．一個(gè)質(zhì)點(diǎn)在全直線的整數(shù)點(diǎn)上作隨機(jī)游動(dòng)，移動(dòng)的規(guī)則是：以概率p從i移到i-1，以概率q從i移到i+1，以概率r停留在i，且，試求轉(zhuǎn)移概率矩陣。,,,首頁(yè),5．設(shè)袋中有a個(gè)球，球?yàn)楹谏幕虬咨?，今隨機(jī)地從袋中取一個(gè)球，然后放回一個(gè)不同顏色的球。若在袋里有k個(gè)白球，則稱(chēng)系統(tǒng)處于狀態(tài)k，試用馬爾可夫鏈描述這個(gè)模型（稱(chēng)為愛(ài)倫菲斯特模型），并求轉(zhuǎn)移概率矩陣。,解這是一個(gè)齊次馬氏鏈，其狀態(tài)空間為,I={0，1，2，…，a},一步轉(zhuǎn)移矩陣是,,,首頁(yè),練習(xí)題．扔一顆色子，若前n次扔出的點(diǎn)數(shù)的最大值為j，就說(shuō)試問(wèn)是否為馬氏鏈？求一步轉(zhuǎn)移概率矩陣。,I={1，2，3，4，5，6},,,首頁(yè),,,例1,甲、乙兩人進(jìn)行比賽，設(shè)每局比賽中甲勝的概率是p，乙勝的概率是q，和局的概率是，（）。設(shè)每局比賽后，勝者記“+1”分，負(fù)者記“—1”分，和局不記分。當(dāng)兩人中有一人獲得2分結(jié)束比賽。以表示比賽至第n局時(shí)甲獲得的分?jǐn)?shù)。,（1）寫(xiě)出狀態(tài)空間；,（3）問(wèn)在甲獲得1分的情況下，再賽二局可以結(jié)束比賽的概率是多少？,首頁(yè),解,（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)移概率矩陣,首頁(yè),（2）二步轉(zhuǎn)移概率矩陣,首頁(yè),（3）,從而結(jié)束比賽的概率；,從而結(jié)束比賽的概率。,所以題中所求概率為,首頁(yè),分析,例2賭徒輸光問(wèn)題,賭徒甲有資本a元，賭徒乙有資本b元，兩人進(jìn)行賭博，每賭一局輸者給贏者1元，沒(méi)有和局，直賭至兩人中有一人輸光為止。設(shè)在每一局中，甲獲勝的概率為p，乙獲勝的概率為，求甲輸光的概率。,這個(gè)問(wèn)題實(shí)質(zhì)上是帶有兩個(gè)吸收壁的隨機(jī)游動(dòng)。從甲的角度看，他初始時(shí)刻處于a，每次移動(dòng)一格，向右移（即贏1元）的概率為p，向左移（即輸1元）的概率為q。如果一旦到達(dá)0（即甲輸光）或a+b（即乙輸光）這個(gè)游動(dòng)就停止。這時(shí)的狀態(tài)空間為{0，1，2，…，c}，c=a+b，?，F(xiàn)在的問(wèn)題是求質(zhì)點(diǎn)從a出發(fā)到達(dá)0狀態(tài)先于到達(dá)c狀態(tài)的概率。,首頁(yè),考慮質(zhì)點(diǎn)從j出發(fā)移動(dòng)一步后的情況,解,同理,根據(jù)全概率公式有,這一方程實(shí)質(zhì)上是一差分方程，它的邊界條件是,首頁(yè),于是,,,設(shè),則可得到兩個(gè)相鄰差分間的遞推關(guān)系,于是,欲求,先求,需討論r,首頁(yè),當(dāng),,,而,兩式相比,首頁(yè),故,,,當(dāng),而,因此,故,首頁(yè),用同樣的方法可以求得乙先輸光的概率,由以上計(jì)算結(jié)果可知,首頁(yè),例3排隊(duì)問(wèn)題,顧客到服務(wù)臺(tái)排隊(duì)等候服務(wù)，在每一個(gè)服務(wù)周期中只要服務(wù)臺(tái)前有顧客在等待，就要對(duì)排在前面的一位提供服務(wù)，若服務(wù)臺(tái)前無(wú)顧客時(shí)就不能實(shí)施服務(wù)。,則有,求其轉(zhuǎn)移矩陣,在第n周期已有一個(gè)顧客在服務(wù)，到第n+1周期已服務(wù)完畢,解,,,先求出轉(zhuǎn)移概率,首頁(yè),所以轉(zhuǎn)移矩陣為,,,首頁(yè),,,證,定理4.3馬爾科夫鏈的有限維分布：,練習(xí)：馬氏鏈的狀態(tài)空間I={1，2，3}，初始概率為,例4,市場(chǎng)占有率預(yù)測(cè),設(shè)某地有1600戶居民，某產(chǎn)品只有甲、乙、丙3廠家在該地銷(xiāo)售。經(jīng)調(diào)查，8月份買(mǎi)甲、乙、丙三廠的戶數(shù)分別為480，320，800。9月份里，原買(mǎi)甲的有48戶轉(zhuǎn)買(mǎi)乙產(chǎn)品，有96戶轉(zhuǎn)買(mǎi)丙產(chǎn)品；原買(mǎi)乙的有32戶轉(zhuǎn)買(mǎi)甲產(chǎn)品，有64戶轉(zhuǎn)買(mǎi)丙產(chǎn)品；原買(mǎi)丙的有64戶轉(zhuǎn)買(mǎi)甲產(chǎn)品，有32戶轉(zhuǎn)買(mǎi)乙產(chǎn)品。用狀態(tài)1、2、3分別表示甲、乙、丙三廠，試求,（1）轉(zhuǎn)移概率矩陣；（2）9月份市場(chǎng)占有率的分布；（3）12月份市場(chǎng)占有率的分布；,解,（1）E{1，2，3},狀態(tài)1、2、3分別表示甲、乙、丙的用戶,一步轉(zhuǎn)移概率矩陣為,（2）以1600除8月份甲，乙，丙的戶數(shù)，得初始概率分布（即初始市場(chǎng)占有率）,所以9月份市場(chǎng)占有率分布為,（3）12月份市場(chǎng)占有率分布為,,,例1,其一步轉(zhuǎn)移矩陣為,試研究各狀態(tài)間的關(guān)系，并畫(huà)出狀態(tài)傳遞圖。,解,先按一步轉(zhuǎn)移概率，畫(huà)出各狀態(tài)間的傳遞圖,首頁(yè),由圖可知,狀態(tài)0可到達(dá)狀態(tài)1，經(jīng)過(guò)狀態(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是一個(gè)閉集,而且I中沒(méi)有其它閉集,所以此馬氏鏈?zhǔn)遣豢杉s的。,首頁(yè),例2,其一步轉(zhuǎn)移矩陣為,試討論哪些狀態(tài)是吸收態(tài)、閉集及不可約鏈。,解,先按一步轉(zhuǎn)移概率，畫(huà)出各狀態(tài)間的傳遞圖,首頁(yè),,,,閉集，,,,由圖可知,狀態(tài)3為吸收態(tài),且,閉集，,閉集，,其中是不可約的。,又因狀態(tài)空間I有閉子集，,故此鏈為非不可約鏈。,首頁(yè),3．常返態(tài)與瞬時(shí)態(tài),則稱(chēng)狀態(tài)i為常返態(tài),則稱(chēng)狀態(tài)i為瞬時(shí)態(tài),注,“常返”一詞，有時(shí)又稱(chēng)“返回”、“常駐”或“持久”,“瞬時(shí)”也稱(chēng)“滑過(guò)”或“非常返”,定理4,定理5,定理6,如果i為常返態(tài)，且，則j也是常返態(tài)。,定理7,所有常返態(tài)構(gòu)成一個(gè)閉集,5．正常返態(tài)與零常返態(tài),平均返回時(shí)間,從狀態(tài)i出發(fā)，首次返回狀態(tài)i的平均時(shí)間,稱(chēng)為狀態(tài)i平均返回時(shí)間.,根據(jù)的值是有限或無(wú)限，可把常返態(tài)分為兩類(lèi)：,設(shè)i是常返態(tài)，,則稱(chēng)i為正常返態(tài)；,則稱(chēng)i為零常返態(tài)。,,,首頁(yè),,例,其一步轉(zhuǎn)移矩陣如下，是對(duì)I進(jìn)行分解。,I可分解為：C1={2，3,4}C2={5，6,7}兩個(gè)閉集及N={1}，即I=N+C1+C2,,用極限判斷狀態(tài)類(lèi)型的準(zhǔn)則,（2）i是零常返態(tài),（3）i是正常返態(tài),（1）i是瞬時(shí)態(tài),且,且,首頁(yè),例3,轉(zhuǎn)移矩陣,試對(duì)其狀態(tài)分類(lèi)。,解,按一步轉(zhuǎn)移概率，畫(huà)出各狀態(tài)間的傳遞圖,首頁(yè),從圖可知，此鏈的每一狀態(tài)都可到達(dá)另一狀態(tài)，即4個(gè)狀態(tài)都是相通的。,考慮狀態(tài)1是否常返，,于是狀態(tài)1是常返的。,又因?yàn)?所以狀態(tài)1是正常返的。,此鏈所有狀態(tài)都是正常返的。,三、狀態(tài)的周期與遍歷,1．周期狀態(tài),對(duì)于任意的，令,其中GCD表示最大公約數(shù),則稱(chēng)為周期態(tài)，,則稱(chēng)為非周期態(tài)。,定理11,2．遍歷狀態(tài),若狀態(tài)i是正常返且非周期，則稱(chēng)i為遍歷狀態(tài)。,例4,設(shè)馬氏鏈的狀態(tài)空間I={0,1,2,…}，轉(zhuǎn)移概率為,試討論各狀態(tài)的遍歷性。,解,根據(jù)轉(zhuǎn)移概率作出狀態(tài)傳遞圖,首頁(yè),從圖可知，對(duì)任一狀態(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)移矩陣為,解,試對(duì)其狀態(tài)分類(lèi)。,按一步轉(zhuǎn)移概率，畫(huà)出各狀態(tài)間的傳遞圖,它是有限狀態(tài)的馬氏鏈，故必有一個(gè)常返態(tài)，又鏈中四個(gè)狀態(tài)都是互通的。因此，所有狀態(tài)都是常返態(tài)，這是一個(gè)有限狀態(tài)不可約的馬氏鏈。,可繼續(xù)討論是否為正常返態(tài),可討論狀態(tài)1,狀態(tài)1是常返態(tài),狀態(tài)1是正常返態(tài),所以，全部狀態(tài)都是正常返態(tài),首頁(yè),例1,其一步轉(zhuǎn)移矩陣為,試證此鏈具有遍歷性，并求平穩(wěn)分布和各狀態(tài)的平均返回時(shí)間,解,由于,,,首頁(yè),所以,因此，該馬氏鏈具有遍歷性。,解得,所以馬氏鏈的平穩(wěn)分布為,各狀態(tài)的平均返回時(shí)間,例2,設(shè)有6個(gè)球（其中2個(gè)紅球，4個(gè)白球）分放于甲、乙兩個(gè)盒子中，每盒放3個(gè)，今每次從兩個(gè)盒中各任取一球并進(jìn)行交換，以表示開(kāi)始時(shí)甲盒中紅球的個(gè)數(shù)，（）表示經(jīng)n次交換后甲盒中的紅球數(shù)。,(1)求馬氏鏈{，}的轉(zhuǎn)移概率矩陣；,(2)證明{，}是遍歷的；,（3）求,（4）求,,,首頁(yè),解,其一步轉(zhuǎn)移矩陣為,甲,乙,紅球0白球3,紅球2白球1,紅球1白球2,紅球1白球2,紅球2白球1,紅球0白球3,,,由狀態(tài)傳遞圖,（2）由于它是一個(gè)有限馬氏鏈，故必有一個(gè)常返態(tài)，,又鏈中三個(gè)狀態(tài)0、1、2都相通，所以每個(gè)狀態(tài)都是常返態(tài)。所以是一個(gè)不可約的有限馬氏鏈，從而每個(gè)狀態(tài)都是正常返的。,所以此鏈為非周期的。,故此鏈?zhǔn)遣豢杉s非周期的正常返鏈，即此鏈?zhǔn)潜闅v的。,,,首頁(yè),也可以利用定理1證明遍歷性,首頁(yè),解之得,故得,,,首頁(yè),（4）,,,首頁(yè),例3,市場(chǎng)占有率預(yù)測(cè),設(shè)某地有1600戶居民，某產(chǎn)品只有甲、乙、丙3廠家在該地銷(xiāo)售。經(jīng)調(diào)查，8月份買(mǎi)甲、乙、丙三廠的戶數(shù)分別為480，320，800。9月份里，原買(mǎi)甲的有48戶轉(zhuǎn)買(mǎi)乙產(chǎn)品，有96戶轉(zhuǎn)買(mǎi)丙產(chǎn)品；原買(mǎi)乙的有32戶轉(zhuǎn)買(mǎi)甲產(chǎn)品，有64戶轉(zhuǎn)買(mǎi)丙產(chǎn)品；原買(mǎi)丙的有64戶轉(zhuǎn)買(mǎi)甲產(chǎn)品，有32戶轉(zhuǎn)買(mǎi)乙產(chǎn)品。用狀態(tài)1、2、3分別表示甲、乙、丙三廠，試求,（1）轉(zhuǎn)移概率矩陣；（2）9月份市場(chǎng)占有率的分布；（3）12月份市場(chǎng)占有率的分布；（4）當(dāng)顧客流如此長(zhǎng)期穩(wěn)定下去市場(chǎng)占有率的分布。（5）各狀態(tài)的平均返回時(shí)間,首頁(yè),解,（1）由題意得頻數(shù)轉(zhuǎn)移矩陣為,再用頻數(shù)估計(jì)概率，得轉(zhuǎn)移概率矩陣為,（2）以1600除以N中各行元素之和，得初始概率分布（即初始市場(chǎng)占有率）,,,首頁(yè),所以9月份市場(chǎng)占有率分布為,（3）12月份市場(chǎng)占有率分布為,,,首頁(yè),（4）由于該鏈不可約、非周期、狀態(tài)有限正常返的，所以是遍歷的。,解方程組,即得當(dāng)顧客流如此長(zhǎng)期穩(wěn)定下去是市場(chǎng)占有率的分布為,（5）,例4(書(shū)中69頁(yè)例4.18）,其一步轉(zhuǎn)移矩陣為,試并每個(gè)不可約閉集的平穩(wěn)分布,,,的平穩(wěn)分布得,狀態(tài)空間可分解為：C={2，3,4}D={5，6,7}兩個(gè)閉集，分別求對(duì)應(yīng)轉(zhuǎn)移概率矩陣,