10馬爾可夫鏈數(shù)學(xué)建模課件

馬爾可夫鏈建模法

馬爾可夫鏈基本理論和結(jié)論服務(wù)網(wǎng)點(diǎn)的設(shè)置問(wèn)題常染色體遺傳模型常染體隱性疾病模型馬爾可夫鏈的應(yīng)用預(yù)備知識(shí)：馬爾可夫鏈隨機(jī)過(guò)程：設(shè)是一族隨機(jī)變量，T是一個(gè)實(shí)數(shù)集合，若對(duì)任意的實(shí)數(shù)，是一個(gè)隨機(jī)變量，則稱為隨機(jī)過(guò)程。例一在一條生產(chǎn)線上檢驗(yàn)產(chǎn)品質(zhì)量，每次取一個(gè)，廢品記為1合格品記為0。以表示第n次檢驗(yàn)結(jié)果，則是一個(gè)隨機(jī)變量.不斷檢驗(yàn)，得到一系列隨機(jī)變量，記為它是一個(gè)隨機(jī)序列，其狀態(tài)空間為E={0，1}例二：在m個(gè)商店聯(lián)營(yíng)出租相機(jī)業(yè)務(wù)中（顧客從其中一個(gè)商店租出可以到m個(gè)商店中的任意一個(gè)歸還）規(guī)定一天為一個(gè)時(shí)間單位表示第t天開(kāi)始時(shí)照相機(jī)在第j個(gè)商店,j=1,2,…..m.則是一個(gè)隨機(jī)序列，其狀態(tài)空間為例3：某商店每月考察一次經(jīng)營(yíng)情況，其結(jié)果用銷路好或壞這兩種狀況中的一種表示。已知若果本月銷路好，下月任保只這種狀況的概率為0.5；如果本月銷路壞，下月轉(zhuǎn)變?yōu)殇N路好的概率為0.4，試分析假若開(kāi)始時(shí)商店處于銷路好的狀態(tài)，過(guò)若干月后能保持銷路好的概率有多大？如果開(kāi)始是處于銷路壞呢？E={1,2,…….m},n=0,1,2,………..稱為這個(gè)經(jīng)營(yíng)系統(tǒng)的狀態(tài)稱為無(wú)后效性，由此，更椐全概率公式容易得到如表所示，由數(shù)字變化規(guī)律可以看出開(kāi)始銷路好時(shí)狀態(tài)概率的變化n0123………10.50.450.4454/900.50.550.5555/9表2開(kāi)始銷路壞時(shí)的狀態(tài)概率的變化0123………n00.40.440.4444/910.60.560.5565/9馬爾可夫鏈的定義：設(shè)是一個(gè)隨機(jī)序列，狀態(tài)空間E為有限或可列對(duì)于任意的正整數(shù)m,n，若i,j,有則稱為一個(gè)馬爾可夫鏈馬氏鏈及其基本方程由狀態(tài)轉(zhuǎn)移的無(wú)后效性和全概率公式可以寫(xiě)出馬氏鏈的基本方程馬氏鏈至少包括一個(gè)吸收狀態(tài)，并且從每一個(gè)非吸收狀態(tài)出發(fā)，能以正的概率經(jīng)有限次轉(zhuǎn)移達(dá)到某個(gè)吸收狀態(tài)則稱此馬氏鏈為吸收鏈。定理2：正則鏈存在唯一的極限狀態(tài)概率引入狀態(tài)概率向量和轉(zhuǎn)移概率矩陣（7）則基本方程（3）可表為（8）（9）因此對(duì)于馬氏鏈模型最基本的問(wèn)題是：構(gòu)造狀態(tài)xn及寫(xiě)出轉(zhuǎn)移矩陣p，一旦有了P，則給定初始狀態(tài)a(0)就可以用（9）或（8）計(jì)算任意時(shí)間n的狀態(tài)概率a(n)定義1：一個(gè)有k個(gè)狀態(tài)的馬氏鏈，如果存在正整數(shù)N，使從任意狀態(tài)i經(jīng)N次轉(zhuǎn)移，都以大于0的概率達(dá)到狀態(tài)j(I,j=1,2,…k)稱此馬氏鏈為正則鏈。正則鏈。馬爾可夫鏈的應(yīng)用模型六：服務(wù)網(wǎng)點(diǎn)的設(shè)置問(wèn)題為適應(yīng)日益擴(kuò)大的旅游事業(yè)的需要，某城市的甲乙丙三個(gè)照相館組成一個(gè)聯(lián)營(yíng)部，聯(lián)合經(jīng)營(yíng)出租相機(jī)的業(yè)務(wù)。游客可由甲乙丙三處任一處租出相機(jī)，用完后，還到三處中的任一處即可。估計(jì)其轉(zhuǎn)移概率為：租相機(jī)處甲乙丙還相機(jī)處甲乙丙0.20.800.800.20.10.30.6今欲選擇其中之一附設(shè)相機(jī)維修點(diǎn)，請(qǐng)你設(shè)計(jì)一種方案。模型分析由于旅客還相機(jī)的情況只與該次租機(jī)地點(diǎn)有關(guān)，而與相機(jī)以前所處的點(diǎn)址無(wú)關(guān)。由（10）有，設(shè)極限概率為W即：解上列方程組可得：由計(jì)算看出，經(jīng)過(guò)長(zhǎng)期經(jīng)營(yíng)后，該聯(lián)營(yíng)部的每架照相機(jī)還到甲乙丙照相館的概率為17/41，16/41，8/41。由于還到甲的照相機(jī)的概率最大，因此維修點(diǎn)設(shè)在甲館較好。模型推廣：生物基因遺傳等方面的應(yīng)用?！?.3馬氏鏈模型隨著人類的進(jìn)化，為了揭示生命的奧秘，人們?cè)絹?lái)越注重遺傳學(xué)的研究，特別是遺傳特征的逐代傳播，已引起人們廣泛的注意。無(wú)論是人，還是動(dòng)、植物都會(huì)將本身的特征遺傳給下一代，這主要是因?yàn)楹蟠^承了雙親的基因，形成自己的基因?qū)?，由基因又確定了后代所表現(xiàn)的特征。本節(jié)將利用數(shù)學(xué)的馬氏鏈方法來(lái)建立相應(yīng)的遺傳模型等，并討論幾個(gè)簡(jiǎn)單而又有趣的實(shí)例。馬氏鏈（馬爾柯夫鏈）研究的是一類重要的隨機(jī)過(guò)程，研究對(duì)象的狀態(tài)s(t)是不確定的，它可能取K種狀態(tài)si(i=1,…,k)之一，有時(shí)甚至可取無(wú)窮多種狀態(tài)。在建模時(shí)，時(shí)間變量也被離散化，我們希望通過(guò)建立兩個(gè)相鄰時(shí)刻研究對(duì)象取各種狀態(tài)的概率之間的聯(lián)系來(lái)研究其變化規(guī)律，故馬氏鏈研究的也是一類狀態(tài)轉(zhuǎn)移問(wèn)題。例4.6設(shè)某商店經(jīng)營(yíng)情況可能有三種狀態(tài)：好（S1：利潤(rùn)豐厚）、一般（S2）和不好（S3：虧損）。根據(jù)統(tǒng)計(jì)資料，上月?tīng)顟B(tài)為Si，下月?tīng)顟B(tài)為Sj的概率為pij（i=1,2,3;j=1,2,3），0≤pij≤1例4.6中的關(guān)系既可用一轉(zhuǎn)移矩陣表示例4.7研究某一草原生態(tài)系統(tǒng)中物質(zhì)磷的循環(huán)，考慮土壤中含磷、牧草含磷、牛羊體內(nèi)含磷和流失于系統(tǒng)之外四種狀態(tài)，分別以S1，S2，S3和S4表示這四種狀態(tài)。以年為時(shí)間參數(shù)，一年內(nèi)如果土壤中的磷以0.4的概率被牧草生長(zhǎng)吸收，水土流失于系統(tǒng)外的概率為0.2；牧草中的含磷以0.6的概率被牛羊吃掉而轉(zhuǎn)換到牛羊體內(nèi)，0.1的概率隨牧草枯死腐敗歸還土壤；牛羊體中的磷以0.7的概率因糞便排泄而還歸土壤，又以自身0.1的比率因屠宰后投放市場(chǎng)而轉(zhuǎn)移到系統(tǒng)外。我們可以建立一個(gè)馬爾柯夫鏈來(lái)研究此生態(tài)系統(tǒng)問(wèn)題，其轉(zhuǎn)移概率列表于下：1000S4流失系統(tǒng)外0.10.200.7S3羊體含磷00.60.30.1S2牧草含磷0.200.40.4S1土壤含磷i時(shí)段狀態(tài)S4S3S2S1i+1時(shí)段狀態(tài)狀態(tài)轉(zhuǎn)移概率相應(yīng)的轉(zhuǎn)移矩陣為：且Sj+1=SjM馬氏鏈模型的性質(zhì)完全由其轉(zhuǎn)移矩陣決定，故研究馬氏鏈的數(shù)學(xué)工具是線性代數(shù)中有關(guān)矩陣的理論。首先，任一轉(zhuǎn)移矩陣的行向量均為概率向量，即有（1）（I,j=1,…,n）（2）（i=1,…,n）

這樣的矩陣被稱為隨機(jī)矩陣。常染色體遺傳模型

下面給出雙親體基因型的所有可能的結(jié)合，以及其后代形成每種基因型的概率，如表所示。

在常染色體遺傳中，后代從每個(gè)親體的基因?qū)χ懈骼^承一個(gè)基因，形成自己的基因時(shí)，基因?qū)σ卜Q為基因型。如果我們所考慮的遺傳特征是由兩個(gè)基因A和a控制的，（A、a為表示兩類基因的符號(hào)）那么就有三種基因?qū)?，記為AA，Aa，aa。

1000aa010Aa0001AA后代基因型aa－aaAa－aaAa－AaAA－aaAA－AaAA－AA父體——母體的基因型雙親隨機(jī)結(jié)合的較一般模型相對(duì)比較復(fù)雜，這些我們僅研究一個(gè)較簡(jiǎn)單的特例。例4.8農(nóng)場(chǎng)的植物園中某種植物的基因型為AA,Aa和aa。農(nóng)場(chǎng)計(jì)劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過(guò)若干年后，這種植物的任一代的三種基因型分布情況如何？（a）假設(shè)：令n=0,1,2,…。（i）設(shè)an,bn和cn分別表示第n代植物中，基因型為AA,Aa和aa的植物占植物總數(shù)的百分比。令x(n)為第n代植物的基因型分布：當(dāng)n=0時(shí)表示植物基因型的初始分布（即培育開(kāi)始時(shí)的分布）例4.8農(nóng)場(chǎng)的植物園中某種植物的基因型為AA,Aa和aa。農(nóng)場(chǎng)計(jì)劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過(guò)若干年后，這種植物的任一代的三種基因型分布情況如何？（b）建模根據(jù)假設(shè)(ii)，先考慮第n代中的AA型。由于第n－1代的AA型與AA型結(jié)合。后代全部是AA型；第n－1代的Aa型與AA型結(jié)合，后代是AA型的可能性為1/2，而第n－1代的aa型與AA型結(jié)合，后代不可能是AA型。因此當(dāng)n=1,2…時(shí)即類似可推出cn=0

顯然有（ii）第n代的分布與第n－1代的分布之間的關(guān)系是通過(guò)表5.2確定的。(4.2)(4.3)(4.4)將（4.2）、（4.3）、（4.4）式相加，得根據(jù)假設(shè)(I)，可遞推得出：對(duì)于(4.2)式.(4.3)式和(4.4)式，我們采用矩陣形式簡(jiǎn)記為其中（注：這里M為轉(zhuǎn)移矩陣的位置）

(4.5)由（4.5）式遞推，得(4.6)（4.6）式給出第n代基因型的分布與初始分布的關(guān)系。為了計(jì)算出Mn，我們將M對(duì)角化，即求出可逆矩陣P和對(duì)角庫(kù)D，使

M=PDP-1因而有

Mn=PDnP-1,n=1,2,…其中這里，，是矩陣M的三個(gè)特征值。對(duì)于(4.5)式中的M，易求得它的特征值和特征向量：=1，=1/2，=0因此所以

通過(guò)計(jì)算，P-1=P，因此有即所以有當(dāng)時(shí)，，所以從（4.7）式得到即在極限的情況下，培育的植物都是AA型。若在上述問(wèn)題中，不選用基因AA型的植物與每一植物結(jié)合，而是將具有相同基因型植物相結(jié)合，那么后代具有三種基因型的概率如表所示。11/40aa01/20Aa01/41AA后代基因型aa－aaAa－AaAA－AA父體——母體的基因型并且，其中M的特征值為通過(guò)計(jì)算，可以解出與、相對(duì)應(yīng)的兩個(gè)線性無(wú)關(guān)的特征向量e1和e2，及與相對(duì)應(yīng)的特征內(nèi)量e3：因此解得：當(dāng)時(shí)，，所以因此，如果用基因型相同的植物培育后代，在極限情況下，后代僅具有基因AA和aa。例4.9

常染體隱性疾病模型現(xiàn)在世界上已經(jīng)發(fā)現(xiàn)的遺傳病有將近4000種。在一般情況下，遺傳疾病和特殊的種族、部落及群體有關(guān)。例如，遺傳病庫(kù)利氏貧血癥的患者以居住在地中海沿岸為多，鐮狀網(wǎng)性貧血癥一般流行在黑人中，家族黑蒙性白癡癥則流行在東歐猶太人中間?；颊呓?jīng)常未到成年就痛苦地死去，而他們的父母則是疾病的病源。假若我們能識(shí)別這些疾病的隱性患者，并且規(guī)定兩個(gè)隱性患者不能結(jié)合（因?yàn)閮蓚€(gè)隱性病患者結(jié)合，他們的后代就可能成為顯性患者），那么未來(lái)的兒童，雖然有可能是隱性患者，但絕不會(huì)出現(xiàn)顯性特征，不會(huì)受到疾病的折磨。

現(xiàn)在，我們考慮在控制結(jié)合的情況下，如何確定后代中隱性患者的概率。

（a）假設(shè)（i）常染色體遺傳的正?；蛴洖锳，不正常基因記為a，并以AA，Aa，aa

分別表示正常人，隱性患者，顯性患者的基因型（ii）設(shè)an,bn分別表示第n代中基因型為

AA，Aa的人占總?cè)藬?shù)的百分比，記，n=1,2,…（這里不考慮aa型是因?yàn)檫@些人不可能成年并結(jié)婚）（iii）為使每個(gè)兒童至少有一個(gè)正常的父親或母親，因此隱性患者必須與正常人結(jié)合，其后代的基因型概率由下表給出：1/20Aa1/21AA后代基因型AA－AaAA－AA父母的基因型（b）建模由假設(shè)（iii），從第n－1代到第n代基因型分布的變化取決于方程所以，其中如果初始分布x(0)已知，那么第n代基因型分布為解將M對(duì)角化，即求出特征值及其所對(duì)應(yīng)的特征向量，得計(jì)算=(4.8)因?yàn)椋援?dāng)時(shí)，，隱性患者逐漸消失。從(4.8)式中可知每代隱性患者的概率是前一代隱性患者概率的1/2。

(4.9)（c）模型討論研究在隨機(jī)結(jié)合的情況下，隱性患者的變化是很有意思的，但隨機(jī)結(jié)合導(dǎo)致了非線性化問(wèn)題，超出了本章范圍，然而用其它技巧，在隨機(jī)結(jié)合的情況下可以把（4.9）式改寫(xiě)為(4.10)下面給會(huì)出數(shù)值例子：某地區(qū)有10%的黑人是鐮狀網(wǎng)性盆血癥隱性患者，如果控制結(jié)合，根據(jù)（4.9）式可知下一代（大約27年）的隱性患者將減少到5%；如果隨機(jī)結(jié)合，根據(jù)（4.10）式，可以預(yù)言下一代人中有9.5%是隱性患者，并且可計(jì)算出大約每出生400個(gè)黑人孩子，其中有一個(gè)是顯性患者。（近親繁殖）近親繁殖是指父母雙方有一個(gè)或兩個(gè)共同的祖先，一般追蹤到四代，即至少有相同的曾祖父（母）或外曾祖父（母）。為簡(jiǎn)單起見(jiàn)，我們來(lái)考察一對(duì)表兄妹（或堂兄妹）結(jié)婚的情況，其中□代表男性，○代表女性。設(shè)曾祖父有某基因?qū)1A2，曾祖母有某基因?qū)3A4，容易求得：祖父母取得A1的概率為1/2，故祖父母同有A1基因的概率為1/4；父母同有A1基因的概率為1/16，而子女從父母那里獲得基因?qū)1A1的概率為1/64，而獲得相同基因?qū)ΓǚQ為基因純合子）A1A1，A2A2，A3A3或A4A4之一的概率為1/16,此概率被稱為表兄妹(或堂兄妹)結(jié)婚(表親)的近交系數(shù)。類似可求得半堂親（只有一個(gè)共同祖先）的近交系數(shù)為1/32，從表親（父母為表親）的近交系數(shù)為1/64；非近親結(jié)婚不可能發(fā)生重復(fù)取某祖先的一對(duì)基因?qū)χ械哪骋换蜃鳛樽约旱幕驅(qū)Φ那闆r，故近交系數(shù)為0。（群體的近交系數(shù)）設(shè)某群體中存在近親婚配現(xiàn)象，稱各種近交系數(shù)的數(shù)學(xué)期望為該群體的近交系數(shù)。例如，某村鎮(zhèn)共有2000對(duì)婚配關(guān)系，其中有59對(duì)表親，22對(duì)半堂親和28對(duì)從表親，則該村鎮(zhèn)的近親系數(shù)為現(xiàn)在，我們來(lái)研究近親結(jié)婚會(huì)產(chǎn)生什么結(jié)果。設(shè)某基因?qū)τ葾、a兩種基因組成，出現(xiàn)A的概率為p，出現(xiàn)a的概率為q=1-p。在隨機(jī)交配群體中，其子女為AA、Aa及aa型的概率分別為p2、2pq及q2。對(duì)近交系數(shù)為F的群體，根據(jù)條件概率公式，后代出現(xiàn)aa型基因?qū)Φ母怕蕿楸容^存在近親交配的群體與不允許近親交配(F=0)的群體，令若a為某種隱性疾病的基因，易見(jiàn)，在近交群體中，后代產(chǎn)生遺傳?。╝a型）的概率增大了，且F越大，后代患遺傳病的概率也越大。同樣，后代出現(xiàn)AA型基因?qū)Φ母怕蕿閜2+Fpq。Aa型不可能是共同祖先同一基因的重復(fù)，故其出現(xiàn)的概率為2pq(1-F)。例如，苯丙酮尿癥是一種隱性基因純合子aa型疾病（a為隱性疾病基因），隱性基因出現(xiàn)的頻率，求表兄妹結(jié)婚及非近親結(jié)婚的子女中患有苯丙酮尿癥的概率。由前，表兄妹結(jié)婚的近交系數(shù)為1/16,故其子女發(fā)生該疾病的概率為而對(duì)禁止近親結(jié)婚的群體，子女發(fā)生該疾病的概率為q2=10-4。表兄妹（或堂兄妹）結(jié)婚使子女發(fā)生該疾病的概率增大了大約7.19倍，由此可見(jiàn)，為了提高全民族的身體素質(zhì)，近親結(jié)婚是應(yīng)當(dāng)禁止的。例4.10

X—鏈遺傳模型的一個(gè)實(shí)例X—鏈遺傳是指另一種遺傳方式：雄性具有一個(gè)基因A或a，雌性具有兩個(gè)基因AA，或Aa，或aa。其遺傳規(guī)律是雄性后代以相等概率得到母體兩個(gè)基因中的一個(gè)，雌性后代從父體中得到一個(gè)基因，并從母體的兩個(gè)基因中等可能地得到一個(gè)。下面，研究與X—鏈遺傳有關(guān)的近親繁殖過(guò)程。（a）假設(shè)（i）從一對(duì)雌雄結(jié)合開(kāi)始,在它們的后代中,任選雌雄各一個(gè)成配偶,然后在它們產(chǎn)生的后代中任選兩個(gè)結(jié)成配偶,如此繼續(xù)下去,(在家畜、家禽飼養(yǎng)中常見(jiàn)這種現(xiàn)象)（ii）父體與母體的基因型組成同胞對(duì)，同胞對(duì)的形式有

(A,AA),(A,Aa),(A,aa),(a,AA),(a,Aa),(a,aa)6種。初始一對(duì)雌雄的同胞對(duì)，是這六種類型中的任一種，其后代的基因型如下表所示。（iii）在每一代中，配偶的同胞對(duì)也是六種類型之一，并有確定的概率。為計(jì)算這些概率,設(shè)an,bn,cn,dn,en,fn

分別是第n代中配偶的同胞對(duì)為(A,AA)，(A,Aa)，(A,aa),(a,AA),(a,Aa),(a,aa)型的概率，n=0,1,…。令（iv）如果第n－1代配偶的同胞對(duì)是（A,Aa）型，那么它們的雄性后代將等可能地得到基因A和a，它們的雌性后代的基因型將等可能地是AA或Aa。又由于第n

代雌雄結(jié)合是隨機(jī)的，那么第n代配偶的同胞對(duì)將等可能地為四種類型(A,AA),(A,Aa),(a,AA),(a,Aa)之一，對(duì)于其它類型的同胞對(duì)，我們可以進(jìn)行同樣分析，因此有11/20000aa01/2111/20Aa00001/21AA11/2011/20a01/2101/21AA后代基因型(a,aa)(a,Aa)(a,AA)(A,aa)(A,Aa)(A,AA)父體——母體的基因型(4.11)其中從（4.11）式中易得經(jīng)過(guò)計(jì)算，矩陣M的特征值和特征向量為

，，，，，,M對(duì)角化，則有(4.12)其中：當(dāng)時(shí)因此，當(dāng)時(shí)，（4.12）式中即因此，在極限情況下所有同胞對(duì)或者是（A,AA）型，或者是（a,aa）型。如果初始的父母體同胞對(duì)是（A,Aa）型，即b0=1，而a0=c0=d0=e0=f0=0，于是，當(dāng)時(shí)即同胞對(duì)是(A,AA)型的概率是2/3，是(a,aa)型的概率為1/3。（正則鏈與吸收鏈）根據(jù)轉(zhuǎn)移矩陣的不同結(jié)構(gòu)，馬氏鏈可以分為多個(gè)不同的類型，這里，我們只簡(jiǎn)單介紹其中常見(jiàn)而又較為重要的兩類：正則鏈與吸收鏈。定義2對(duì)于馬氏鏈，若存在一正整數(shù)K，使其轉(zhuǎn)移矩陣的K次冪MK>0（每一分量均大于0），則稱此馬爾鏈為一正則（regular）鏈。定理2若A為正則鏈的轉(zhuǎn)移矩陣，則必有：（1）當(dāng)時(shí)，，其中W為一分量均大于零的隨機(jī)矩陣。（2）W的所有行向量均相同。定理3記定理2中的隨機(jī)矩陣W的行向量為V=(v1,…,vn),則：（1）對(duì)任意隨機(jī)向量x，有（2）V是A的不動(dòng)點(diǎn)向量,即VA=V,A的不動(dòng)點(diǎn)向量是唯一的。定義3狀態(tài)Si稱為馬氏鏈的吸收狀態(tài)，若轉(zhuǎn)移矩陣的第i行滿足：Pii=1，Pij=0（j≠i）定義4馬氏鏈被稱為吸收鏈，若其滿足以下兩個(gè)條件：（1）至少存在一個(gè)吸收狀態(tài)。（2）從任一狀態(tài)出發(fā),經(jīng)有限步轉(zhuǎn)移總可到達(dá)某一吸收狀態(tài)根據(jù)定義3，例4.7中狀態(tài)S4即為一吸收鏈具有r個(gè)吸收狀態(tài)，n－r個(gè)非吸收狀態(tài)的吸收鏈，它的n×n