markov模型学习教程.pptx

本PPT的主要内容一、Markov数学模型建立的背景二、Markov数学模型建模的过程三、Markov数学模型应用介绍第1页/共48页一、Markov数学模型建立的背景1.Markov数学模型的建立者马尔可夫 安德烈马尔可夫，1856年6月14日生于梁赞，1922年7月20日卒于圣彼得堡。1874年入圣彼得堡大学，受P.L.切比雪夫思想影响很深。1878年毕业，并以用连分数求微分方程的积分一文获金质奖章。两年后，取得硕士学位，并任圣彼得堡大学副教授。1884年取得物理-数学博士学位，1886 年任该校教授。1896被选为圣彼得堡科学院院士。1905年被授予功勋教授号。第2页/共48页一、Markov数学模型建立的背景1.Markov数学模型的建立者马尔可夫 马尔可夫是彼得堡数学学派的代表人物。以数论和概率论方面的工作著称。他的主要著作有概率演算等。在数论方面，他研究了连分数和二次不定式理论，解决了许多难题。在概率论中，他发展了矩法，扩大了大数律和中心极限定理的应用范围。马尔可夫最重要的工作是在19061912年间，提出并研究了一种能用数学分析方法研究自然过程的一般图式马尔可夫链。同时开创了对一种无后效性的随机过程马尔可夫过程的研究。马尔可夫经多次观察试验发现，一个系统的状态转换过程中第n次转换获得的状态常决定于前一次（第（n-1）次）试验的结果。马尔可夫进行深入研究后指出：对于一个系统，由一个状态转至另一个状态的转换过程中，存在着转移概率，并且这种转移概率可以依据其紧接的前一种状态推算出来，与该系统的原始状态和此次转移前的马尔可夫过程无关。目前，马尔可夫链理论与方法已经被广泛应用于自然科学、工程技术和公用 事业中。第3页/共48页一、Markov数学模型建立的背景2.Markov链的原理简介 马尔可夫链是具有马尔科夫性质的随机变量X_1,X_2,X_3.的一个数列。这些变量的范围，即它们所有可能取值的集合，被称为“状态空间”，而X_n的值则是在时间n的状态。如果X_n+1对于过去状态的条件概率分布仅是X_n的一个函数，则 P(X_n+1=x|X_1=x_1,X_2=x_2,.,X_n=x_n)=P(X_n+1=x|X_n=x_n).这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。第4页/共48页一、Markov数学模型建立的背景3.Markov链的理论发展 马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码（著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码）。马尔可夫链也有众多的生物学应用，特别是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。第5页/共48页一、Markov数学模型建立的背景 4.Markov数学模型可行性 世界上的一切事物都在随时间而变化，譬如某一地区气候指标气温和湿度的变化；体血液循环，心脏搏动每次的血压与排血量；神经细胞兴奋或抑制的传递；生物世代交替过程中遗传性状的表现所有变化着的事物表现状态可能是数值的、非数值的、连续的、离散的。在这种情况下，我们需建立一种研究的是一类重要的随机过程，研究对象的状 态s(t)是不确定的，它可能 取K种 状态si(i=1,k)之一，有时甚至可取无穷多种状态的模型，而这种模型就是Markov数学模型。在建模时，时间变量也被离散化，我们希望通过建立两个相邻时刻研究对象取各种状态的概率之间的联系来研究其变化规律，故马氏链研究的也是一类状态转移问题。第6页/共48页 过程(或系统)在时刻t t0 0所处的状态为已知的条件下，过程在时刻tttt0 0所处状态的条件分布与过程在时刻t t0 0之前所处的状态无关。通俗地说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。二、二、Markov数学模型建模的过程数学模型建模的过程马尔可夫性马尔可夫性(无后效性无后效性)用分布函数表述马尔可夫性：用分布函数表述马尔可夫性：1 1、MarkovMarkov链的定义链的定义第7页/共48页定义 设随机过程 的状态空间为：若对任意的 ，及 有则称 为离散时间、离散状态的马尔可夫过程，或简称为马尔可夫链。第8页/共48页【例】细胞分裂实验第9页/共48页 设 是马尔可夫链，对任意的 ，计算 的联合分布律2、转移概率、转移概率 乘法公式乘法公式乘法公式乘法公式 马氏性马氏性 即马尔可夫链 的有限维分布完全由初始分布 和 条件概率 确定.马氏性马氏性第10页/共48页 当 固定时，一步转移概率 实质上就是在 的条件下，随机变量 的条件分布律，所以条件分布律满足：定义1 1 设 是马尔可夫链，记称 为马尔可夫链 在时刻 时的一步转移概率。第11页/共48页 定义2 2 设 是马尔可夫链，若其一步转移概率 与时间 无关，即则称 为齐次马尔可夫链，称 为从状态 转移到状态 的一步转移概率.若马尔科夫链 的状态空间是有限集，则称 为有限状态的马尔科夫链；若马尔科夫链 的状态空间是可列集，则称 为可列状态的马尔科夫链.第12页/共48页矩阵的每一行都矩阵的每一行都是一条件分布律是一条件分布律 记 .称 为齐次马尔可夫链的初始分布.齐次马尔科夫链的有限维分布族完全由其一步转移概率矩阵 和初始分布 确定.则称矩阵 为齐次马尔科夫链的一步转移概率矩阵.定义3 3 设 是齐次马尔可夫链，其一步转移概率为 ，记第13页/共48页例1(1(一个简单的疾病死亡模型)3、马氏链的例子、马氏链的例子第14页/共48页马氏链的基本方程马氏链的基本方程基本方程第15页/共48页马氏链的两个重要类型马氏链的两个重要类型 1.正则链 从任一状态出发经有限次转移能以正概率到达另外任一状态。w 稳态概率第16页/共48页马氏链的两个重要类型马氏链的两个重要类型 2.吸收链 存在吸收状态（一旦到达就不会离开的状态i,pii=1）,且从任一非吸收状态出发经有限次转移能以正概率到达吸收状态。有r个吸收状态的吸收链的转移概率阵标准形式R有非零元素yi 从第 i 个非吸收状态出发，被某个吸收状态吸收前的平均转移次数。第17页/共48页正则链与吸收链相关定义定义2 对于马氏链，若存在一正整 数K，使其转移矩阵 的K次幂MK0（每一分量均大 于0），则称此马尔链为一正则（regular）链。定理2 若A为正则链的转移矩阵，则必有：（1）当 时，其中W为一分量均大于零 的随机矩阵。（2）W的所有行向量均相同。第18页/共48页定理3 记定理 2中的随机矩阵W的行向量为V=(v1,vn),则：（1）对任意随机向 量x，有（2）V是A的不动点向量,即VA=V,A的不动点向量是唯一的。定义3 状态Si 称为马氏链的吸收状态，若转移矩阵的 第i 行满足：Pii=1，Pij=0（ji）定义4 马氏链被称为 吸收链，若其满足以下两个条件：（1）至少存在一个吸收状态。（2）从任一状态出发,经有限步转移总可到达某一吸收 状态“随机”第19页/共48页具有r个吸收状态，nr个非吸收状态的吸收链，它的nn转移矩阵的标准形式为 （注：非标准形式可经对状态重新编号 ）其中Ir为r 阶单位阵，O为rs零阵，R为sr 矩阵，S为ss矩阵。令上式中的子阵Sn表达了以任何非吸收状态作为初始状态，经过n步转移后，处于s个非吸收状态的概率。在吸收链中，令F=(IS)-1，称F为基矩阵。第20页/共48页定理4 吸收链的基矩 阵F中的每个元素，表示从一个非吸收 状态出发，过程到达每个非吸收状态的平均转移次 数。定理5 设N=FC，F为吸收链的基矩阵，C=(1,1,1)T，则N 的每个元素表示从非吸收状态出发，到达某个吸收 状态被吸收之前的平均转移次数。定理6 设B=FR=（bij），其中F为吸收链的基矩阵，R为T中 的子阵，则bij表示从非吸收状 态i出发，被吸收状态 j 吸收的概率。第21页/共48页例4.8 农场的植物园中某种植物的基因型 为AA,Aa和aa。农场计划采用 AA型的植物与每种基因型植物相结合的方案培育植物后代。那么经过若干年后，这种植物的任一代的三种基因型分布情况如何？（a）假设：令n=0,1,2,。（i）设an,bn和cn分别表示第n代植物中，基因型 为AA,Aa和aa的植物占植物总数的百分比 。令x(n)为第n代植物的基因型分布：当n=0时表示植物基因型的初始分布（即培育开始时的分布）例2 农场的植物园中某种植物的基因型 为AA,Aa和aa。农场计划采用 AA型的植物与每种基因型植物相结合的方案培育植物后代。那么经过若干年后，这种植物的任一代的三种基因型分布情况如何？三、三、Markov数学模型应用介绍数学模型应用介绍第22页/共48页（b）建模根据假设(ii)，先考虑第n代中的AA型。由于第n1代的AA型与AA型结合。后代全部是AA型；第n1代的Aa型与AA型结合，后代是AA型的可能性为 1/2，而 第n1代的aa型与AA型结合，后代不可能 是AA型。因此当n=1,2时即类似可推出cn=0 显然有（ii）第n代的分布与 第n1代的分布之间的关系是确定的。(2.2)(2.3)(2.4)第23页/共48页将（）、（）、（）式相加，得根据假设(I)，可递推得出：对于(2.2)式(2.3)式和(2.4)式，我们采用矩阵形式简记为其中（注：这里M为转移矩阵的位置）(2.5)第24页/共48页由（）式递推，得(2.6)（2.6）式给出第n代基因型的分布与初始分布的关系。为了计算出Mn，我们将M对角化，即求出可逆矩 阵P和对角库D，使 M=PDP-1因而有 Mn=PDnP-1,n=1,2,其中这里 ，是矩 阵M的三个特征值。对于(2.5)式中的M，易求得它的特征值和特征向量：=1，=1/2，=0第25页/共48页因此所以 通过计算，P-1=P，因此有第26页/共48页即第27页/共48页所以有当时，所以从（4.7）式得到即在极限的情况下，培育的植物都 是AA型。若在上述问题中，不选用基 因AA型的植物与每一植物结合，而是将具有相同基因型植物相结合，那么后代具有三种基因型的概率如 表所示。11/40aa01/20Aa01/41AA后代基因型aaaaAaAaAAAA父体母体的基因型第28页/共48页并且，其中M的特征值为通过计算，可以解出与 、相对应的两个线性无关的特征向量e1和e2，及与相对应的特征内 量e3：因此第29页/共48页解得：当 时，所以因此，如果用基因 型相同的植物培育 后代，在极限情况 下，后代仅具有基 因 A A和 a a。第30页/共48页例3 常染体隐性疾病模型现在世界上已经发现的遗传病有将 近4000种。在一般情况下，遗传疾病和特殊的种族、部落及群体 有关。例如，遗传病库利氏贫血症的患者以居住在 地中海沿岸为多，镰状网性贫血症一般流行在黑人中，家族黑蒙性白痴症则流行在东欧犹太人中间。患者经常未到成年就痛苦地死去，而他们的父母则 是疾病的病源。假若我们能识别这些疾病的隐性患 者，并且规定两个隐性患者不能结合（因为两个隐 性病患者结合，他们的后代就可能成为显性患者），那么未来的儿童，虽然有可能是隐性患者，但绝不 会出现显性特征，不会受到疾病的折磨。第31页/共48页现在，我们考虑在控制结合的情况下，如何确定后代中隐性患者的概率。（a）假设（i）常染色体遗传的正常基因记 为A，不 正常基因记 为a，并以 AA，Aa，aa 分别表示正常人，隐性患者，显性患 者的基因型（ii）设an,bn分别表示第n代中基因型为 AA，Aa的人占总人数的百分比，记 ，n=1,2,（这里 不考 虑aa型是因 为这些人不可能成年并结婚）（iii）为使每个儿童至少有一个正常的父 亲或母亲，因此隐性患者必须与正常 人结合，其后代的基因型概率由 下表 给出：1/20Aa1/21AA后代基因型AAAaAAAA父母的基因型第32页/共48页（b）建模由假设（iii），从第n1代到第n代基因型分布的变化取决于方程所以，其中如果初始分 布x(0)已知，那么 第n代基因型分布为解解 将将M对角化，即求出特征值及其所对应的特征向量，得对角化，即求出特征值及其所对应的特征向量，得第33页/共48页计算 =(3.8)因为，所以当 时，隐性患者逐渐消失。从(3.8)式中可知每代隐性患者的概率是前一代隐性患者概率的1/2。(3.9)第34页/共48页（c）模型讨论研究在随机结合的情况下，隐性患者的变化是很有意思的，但随机结合导致了非线性化问题，超出了本章范围，然而用其它技巧，在随机结合的情况下可以 把（）式改写为(3.10)下面给会出数值例子：某地区有10%的黑人是镰状网性盆血症隐性患者，如果控制结合，根据（3.9）式可知下一代（大约27年）的隐性患者将减少到5%；如果随机结合，根据（3.10）式，可以预言下一代人中 有9.5%是隐性患者，并且可计算出大约每出生400个黑人孩子，其中有一个是显性患者。第35页/共48页（近亲繁殖）近亲繁殖是指父母双方有一个或两个共同的祖先，一般追踪到四代，即至少有相同的曾祖父（母）或外曾祖父（母）。为简单起见，我们来考察一对表兄妹（或堂兄妹）结婚的情况，其中代表男性，代表女性。设曾祖父有某基因 对A1A2，曾祖母有某基因 对A3A4，容易求得：祖父母取 得A1的概率为 1/2，故祖父母同 有A1基因的概率为1/4；父母同有A1基因的概率为 1/16，而子女从父母那里获得基因对A1A1的概率为 1/64，而获得相同基因对（称为基因纯合子）A1A1，A2A2，A3A3或A4A4之一的概率为 1/16,此概率被称为表兄 妹(或堂兄妹)结婚(表亲)的近交系数。类似可求得半堂亲（只有一个共同祖先）的近交系数 为1/32，从表亲（父母为表亲）的近交系数 为1/64；非近亲结婚不可能发生重复取某祖先的一对基因对中的某一基因作为自己的基因对的情况，故近交系数 为0。第36页/共48页（群体的近交系数）设某群体中存在近亲婚配现象，称各种近交系数的数学期望为该群体的近交系数。例如，某村镇共有2000对婚配关系，其中有59对表亲，22对半堂亲 和28对从表亲，则该村镇的近亲系数为 现在，我们来研究近亲结 婚会产生什么结果。设某基因对由 A、a两种基因组成，出 现A的概率为p，出现a的概率为q=1-p。在随机交配群体中，其子女 为AA、Aa及aa型的概率分别 为p2、2pq及q2。对近交系数 为F的群体，根据条件概率公式，后代出 现aa型基因对的概率为第37页/共48页比较存在近亲交配的群体与不允许近亲交配 (F=0)的群体，令 若a为某种隐性疾病的基因，易见，在近交群体中，后代产 生遗传病（aa型）的概率增大了，且F越大，后代患遗传病 的概率也越大。同样，后代出现AA型基因对的概率 为p2+Fpq。Aa型不可能 是共同祖先同一基因的重复，故其出现的概率为2pq(1-F)。第38页/共48页例如，苯丙酮尿症是一种隐性基因纯合子 aa型疾病（a为隐性疾病基因），隐性基因出现的频率 ，求表兄妹结婚及非近亲结婚的子女中患有苯丙酮尿症的概率。由前，表兄妹结婚的近交系数为 1/16,故其子女发生该疾病的概率为而对禁止近亲结婚的群体，子女发生该疾病的概率为q2=10-4。表兄妹（或堂兄妹）结婚使子女发生该疾病的概率增大了大 约倍，由此可见，为了提高全民族的身体素质，近亲结婚是应当 禁止的。第39页/共48页例4 X链遗传模型的一个实例X链遗传是指另一种遗传方式：雄性具有一个基 因A或a，雌性具有两个基 因AA，或Aa，或aa。其遗传规律是雄性后代以相等概率得到母体两个基因中的一个，雌性后代从父体中得到一个基因，并从母体的两个基因中等可能地得到一个。下面，研究 与X链遗传有关的近亲繁殖过程。（a）假设（i）从一对雌雄结合开始,在它们的后代 中,任选雌雄各一 个成配偶,然后在它们产生的后代中任选两个结成配 偶,如此继续下去,(在家畜、家禽饲养中常见这种现 象)（ii）父体与母体的基因型组成同胞对，同胞对的形式有 (A,AA),(A,Aa),(A,aa),(a,AA),(a,Aa),(a,aa)6种。初始一 对雌雄的同胞对，是这六种类型中的任一种，其后代的 基因型如下表所示。第40页/共48页（iii）在每一代中，配偶的同胞对也是六种类型之一，并 有确定的概率。为计算这些概率 ,设an,bn,cn,dn,en,fn 分别是第n代中配偶的同胞对 为(A,AA)，(A,Aa)，(A,aa),(a,AA),(a,Aa),(a,aa)型的概率，n=0,1,。令（iv）如果第n1代配偶的同胞对是（A,Aa）型，那么它 们的雄性后代将等可能地得到基 因A和a，它们的雌 性后代的基因型将等可能地 是AA或Aa。又由于 第n 代雌雄结合是随机的，那么 第n代配偶的同胞对将等 可能地为四种类型(A,AA),(A,Aa),(a,AA),(a,Aa)之一，对于其它类型的同胞对，我们可以进行同样分析，因此有11/20000aa01/2111/20Aa00001/21AA11/2011/20a01/2101/21AA后代基因型(a,aa)(a,Aa)(a,AA)(A,aa)(A,Aa)(A,AA)父体母体的基因型(4.11)第41页/共48页其中从（）式中易得经过计算，矩阵 M的特征值和特征向量为，第42页/共48页,M对角化，则有(4.12)第43页/共48页 其中：第44页/共48页第45页/共48页当 时因此，当 时，（4.12）式中第46页/共48页即因此，在极限情况下所有同胞对或者是（A,AA）型，或者是（a,aa）型。如果初始的父母体同胞对 是（A,Aa）型，即b0=1，而a0=c0=d0=e0=f0=0，于是，当时即同胞对是(A,AA)型的概率是2/3，是(a,aa)型的概率为1/3。第47页/共48页感谢您的观看！第48页/共48页