馬爾科夫鏈例題整理.ppt

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

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