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

馬爾可夫鏈建模法

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

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

1000aa010Aa0001AA后代基因型aa－aaAa－aaAa－AaAA－aaAA－AaAA－AA父體——母體的基因型雙親隨機(jī)結(jié)合的較一般模型相對比較復(fù)雜，這些我們僅研究一個較簡單的特例。例4.8農(nóng)場的植物園中某種植物的基因型為AA,Aa和aa。農(nóng)場計劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過若干年后，這種植物的任一代的三種基因型分布情況如何？（a）假設(shè)：令n=0,1,2,…。（i）設(shè)an,bn和cn分別表示第n代植物中，基因型為AA,Aa和aa的植物占植物總數(shù)的百分比。令x(n)為第n代植物的基因型分布：當(dāng)n=0時表示植物基因型的初始分布（即培育開始時的分布）例4.8農(nóng)場的植物園中某種植物的基因型為AA,Aa和aa。農(nóng)場計劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過若干年后，這種植物的任一代的三種基因型分布情況如何？（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…時即類似可推出cn=0

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

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

M=PDP-1因而有

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

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

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

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

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

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

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

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

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

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

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

代雌雄結(jié)合是隨機(jī)的，那么第n代配偶的同胞對將等可能地為四種類型(A,AA),(A,Aa),(a,AA),(a,Aa)之一，對于其它類型的同胞對，我們可以進(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)過計算，矩陣M的特征值和特征向量為

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