第六章 马氏链模型--华东理工大学数学建模课件.ppt

第六章 马氏链模型,6.1,健康与疾病,6.2,钢琴销售的存贮策略,6.3,基因遗传,6.4,等级结构,第九章 马氏链模型,在经济预测中，常常需要由经济系统的近期状态（,t=t,0,）及过去的状态（,t=t,0,-1,t,0,-2,t,0,-k,）去预测以后的状态（,t=t,0,+1,t,0,+2,）。若某一经济系统的变化过程仅与该经济系统的近期状态有关，而与过去状态无关，即该经济系统在,t,0,+1,时的状态仅与,t,0,时的状态有关而与,t,0,以前的状态无关，则称这种特性为,无后效性,或,马尔可夫性,。,具有无后效性的随机时间序列称为,马尔可夫过程,或,马尔可夫链,。,马尔可夫过程,可数马氏链,(,指变化仅仅发生在一些离散时刻的具有马氏性的一类随机过程,),连续时间马氏过程,(,指变化发生是随时间的连续变化而变化,具有马氏性的一类随机过程,),一、可数马氏链模型,仅考虑系统只有有限个状态（,I=,1,，,2,，,，,k,）的情形。,记,n,时刻系统的状态为,X,n,，,记,X,n,=i,的概率为,a,i,(n,)(,状态概率,),。从,X,n,=i,变到,X,n+1,=j,的概率记为,p,ij,(n,)(,状态转移概率,),。如果对一切,I,jI,，,p,ij,(n,),都与,n,无关，相应的马氏链称为,时齐马氏链,。,时齐马氏链,记,p,ij,(n,)=,p,ij,，由马氏性和全概率公式得基本方程为,则基本方程写成向量形式可表示为,显然，,P,的每一元素均为非负，且其行和为,1,。（,称,P,矩阵为随机矩阵,）,这里，一旦有了,P,，那么给定初始状态概率,a(0),，就可计算任意时间,n,的状态概率。,相关定义和相关定理,Def1.,一个有,k,个状态的马氏链如果存在正整数,N,，使从任意状态,i,经,N,次转移都以大于零的概率到达状态,j,（,i,j,=1,2,k,）,则称为,正则链,。,TH1.,若马氏链的转移矩阵为,P,，则它是正则链的充要条件是：存在正整数,n,，使得,P,n,的每个元素均为正。,Def2.,一个概率分布 称为马氏链的,平稳分布,，如果,记 上式可表示为向量形式,Def3.,如果记 的元素为 ，,为,极限分布,。,TH3.,对于正则链，设 是其极限分布，则,Def4.,设,iI,，若,p,ii,=1,称,i,是,吸收态,。如果马氏链至少包含一个吸收态，并且从每个非吸收态出发能以正的概率经有限次转移到达某个吸收状态，那么这个马氏链称为,吸收链,。,行之和为,1,转移矩阵,r,个吸收状态，,k-r,个非吸收状态,TH4.,对于吸收链的标准形式，是可逆矩阵，且其逆矩阵可表示为形式,且,(I-Q),-1,的第,j,行之和是从第,j,个非吸收状态出发被某个吸收状态吸收的平均转移次数。,设,i,是非吸收态，,j,是吸收态，记,TH5.,Def5.,对,i,，,j,，若存在非负整数,n,，使，则称自状态,i,可达状态,j,。,若，则称状态,i,是常返的；,若，则称状态,i,是非常返的。,TH6.,对,i,，,j,，若状态,j,是非常返的，则,可数马氏链的应用,定编定岗问题,仓库管理模型,物种保护问题,二、连续时间马氏过程模型,1,、生物群体的增长模型,2,、传染病的流行模型,1,、生物群体的增长模型,关于生物群体增长的常微分方程模型中有两大缺点：,它假定了群体数目是时间的连续函数，而不是时间的整值函数；,它假定了群体的增长是确定性的，从而得出了,“,在初始条件不变时，到时刻,t,时，群体含量永远相同,”,的结果。,模型一、纯生过程模型,对于某个生物群体，设在,t,时刻群体的数量为,X(t,),，,X(t,),为一随机变量，并作如下假设。,模型假设,如果在,t,时刻群体数量为,x,（,x=0,1,2,.,），则在时间段（,t,t+t,）内，群体数量增加一个的概率为,t+0(t),。,群体数目在（,t,t+t,）增加两个或两个以上的概率为,0(t,）。,群体数目在（,t,t+t,）内不发生变化的概率为,1-,t+0(t),）。,（以上模型适合于一个微生物群体在良好环境下的增长情况）,模型建立,用,p,x,(t,),表示,t,时刻群体数目为,x,的概率，即,p,x,(t,)=,p(X(t,)=x),则有,p,x,(t+t,)=(1-,x,t),p,x,(t,)+,x-1,p,x-1,(t)t+0t,移项整理得,其初始条件为,其中 是初始时间生物群体的数目。,（下面假定 ）,补充假设,增长率,x,为,x,的线性函数，即,模型求解,此时，方程化为,注意到当,x=1,时,由此，可得递推关系式,从初始条件,马氏链模型,系统在每个时期所处的状态是随机的,从一时期到下时期的状态按一定概率转移,下时期状态只取决于本时期状态和转移概率,已知现在，将来与过去无关（无后效性）,描述一类重要的,随机动态,系统（过程）的模型,马氏链,(Markov Chain),时间、状态均为离散的随机转移过程,通过有实际背景的例子介绍马氏链的基本概念和性质,例,1.,人的健康状况分为健康和疾病两种状态，设对特定年龄段的人，今年健康、明年保持健康状态的概率为,0.8,而今年患病、明年转为健康状态的概率为,0.7,，,11.1,健康与疾病,人的健康状态随着时间的推移会随机地发生转变,保险公司要对投保人未来的健康状态作出估计,以制订保险金和理赔金的数额,若某人投保时健康,问,10,年后他仍处于健康状态的概率,X,n,+1,只取决于,X,n,和,p,ij,与,X,n,-1,无关,状态,与,状态转移,状态转移具有无后效性,1,2,0.8,0.2,0.3,0.7,n,0,a,2,(,n,)0,a,1,(,n,)1,设投保时健康,给定,a,(0),预测,a,(,n,),n,=1,2,设投保时疾病,a,2,(,n,)1,a,1,(,n,)0,n,时状态概率趋于稳定值，稳定值与初始状态无关,3,0.778,0.222,7/9,2/9,0.7 0.77 0.777,0.3 0.33 0.333,7/9,2/9,状态,与,状态转移,1,2,0.8,0.2,0.3,0.7,1,0.8,0.2,2,0.78,0.22,1,2,3,0.1,0.02,1,0.8,0.25,0.18,0.65,例,2.,健康和疾病状态同上，,X,n,=1,健康,X,n,=2,疾病,p,11,=0.8,p,12,=0.18,p,13,=0.02,死亡为第,3,种状态，记,X,n,=3,健康与疾病,p,21,=0.65,p,22,=0.25,p,23,=0.1,p,31,=0,p,32,=0,p,33,=1,n,0 1 2 3,a,2,(,n,)0 0.18 0.189 0.1835,a,3,(,n,)0 0.02 0.054 0.0880,a,1,(,n,)1 0.8 0.757 0.7285,设投保时处于健康状态，预测,a,(,n,),n,=1,2,不论初始状态如何，最终都要转到状态,3,；,一旦,a,1,(,k,)=,a,2,(,k,)=0,a,3,(,k,)=1,则对于,nk,a,1,(,n,)=0,，,a,2,(,n,)=0,a,3,(,n,)=1,即从状态,3,不会转移到其它状态。,状态,与,状态转移,0,0,1,50,0.1293,0.0326,0.8381,马氏链的基本方程,基本方程,马氏链的两个重要类型,1.,正则链,从任一状态出发经有限次转移能以正概率到达另外任一状态（如例,1,）。,w,稳态概率,马氏链的两个重要类型,2.,吸收链,存在吸收状态（一旦到达就不会离开的状态,i,p,ii,=1,）,且,从任一非吸收状态出发经有限次转移能以正概率到达吸收状态（如例,2,）。,有,r,个吸收状态的吸收链的转移概率阵标准形式,R,有非零元素,y,i,从第,i,个非吸收状态出发，被某个吸收状态吸收前的平均转移次数。,11.2,钢琴销售的存贮策略,钢琴销售量很小，商店的库存量不大以免积压资金,一家商店根据经验估计，平均每周的钢琴需求为,1,架,存贮策略,：每周末检查库存量，仅当库存量为零时，才订购,3,架供下周销售；否则，不订购。,估计在这种策略下失去销售机会的可能性有多大，以及每周的平均销售量是多少。,背景与问题,问题分析,顾客的到来相互独立，需求量近似服从波松分布，其参数由需求均值为每周,1,架确定，由此计算需求概率,存贮策略是周末库存量为零时订购,3,架,周末的库存量可能是,0,1,2,3,，周初的库存量可能是,1,2,3,。,用马氏链描述不同需求导致的周初库存状态的变化。,动态过程中每周销售量不同，失去销售机会（需求超过库存）的概率不同。,可按稳态情况（时间充分长以后）计算失去销售机会的概率和每周的平均销售量。,模型假设,钢琴每周需求量服从波松分布，均值为每周,1,架,存贮策略,：当周末库存量为零时，订购,3,架，周初到货；否则，不订购。,以每周初的库存量作为状态变量，状态转移具有无后效性。,在稳态情况下计算该存贮策略失去销售机会的概率，和每周的平均销售量。,模型建立,D,n,第,n,周需求量,，,均值为,1,的波松分布,S,n,第,n,周初库存量,(,状态变量,),状态转移规律,D,n,0 1 2 3 3,P,0.368 0.368 0.184 0.061 0.019,状态转移阵,模型建立,状态概率,马氏链的基本方程,正则链,稳态概率分布,w,满足,wP,=w,已知初始状态，可预测第,n,周初库存量,S,n,=i,的概率,n,状态概率,第,n,周失去销售机会的概率,n,充分大时,模型求解,从长期看，失去销售机会的可能性大约,10%,。,1.,估计在这种策略下失去销售机会的可能性,D,0 1 2 3 3,P,0.368 0.368 0.184 0.061 0.019,模型求解,第,n,周平均售量,从长期看，每周的平均销售量为,0.857(,架,),n,充分大时,需求不超过存量,销售需求,需求超过存量,销售存量,思考：为什么这个数值略小于每周平均需求量,1(,架,),?,2.,估计这种策略下每周的平均销售量,敏感性分析,当平均需求在每周,1(,架,),附近波动时，最终结果有多大变化。,设,D,n,服从均值为,的波松分布,状态转移阵,0.8,0.9,1.0,1.1,1.2,P,0.073,0.089,0.105,0.122,0.139,第,n,周,(,n,充分大,),失去销售机会的概率,当平均需求增长（或减少）,10%,时，失去销售机会的概率将增长（或减少）约,12%,。,11.3,基因遗传,背景,生物的外部表征由内部相应的基因决定。,基因分优势基因,d,和劣势基因,r,两种。,每种外部表征由两个基因决定，每个基因可以是,d,r,中的任一个。形成,3,种基因类型：,dd,优种,D,dr,混种,H,rr,劣种,R,。,基因类型为优种和混种,外部表征呈优势；基因类型为劣种,外部表征呈劣势,。,生物繁殖时后代随机地（等概率地）继承父、母的各一个基因，形成它的两个基因。父母的基因类型决定后代基因类型的概率,完全优势基因遗传,父母基因类型决定后代各种基因类型的概率,父母基因类型组合,后代各种,基因类型,的概率,DD,RR,DH,DR,HH,HR,D,R,H,1,0,0,0,0,1,1/2,1/2,0,0,1,0,1/4,1/2,1/4,0,1/2,1/2,3,种基因类型：,dd,优种,D,dr,混种,H,rr,劣种,R,完全优势基因遗传,P,(,D,DH,)=,P,(,dd,dd,dr,)=,P,(,d,dd,),P,(,d,dr,),P,(,R,HH,)=,P,(,rr,dr,dr,)=,P,(,r,dr,),P,(,r,dr,),=11/2=,1/2,=1/21/2=,1/4,随机繁殖,设群体中雄性、雌性的比例相等，基因类型的分布相同（记作,D,:,H,:,R,）,每一雄性个体以,D,:,H,:,R,的概率与一雌性个体交配，其后代随机地继承它们的各一个基因,设初始一代基因类型比例,D,:,H,:,R,=,a,:2,b,:,c,（,a+2b+c=,1),记,p=a+b,q=b+c,则,群体中优势基因和劣势基因比例,d,:,r=p,:,q,(,p+q,=1),。,假设,建模,状态,X,n,=1,2,3,第,n,代的一个体属于,D,H,R,状态概率,a,i,(,n,),第,n,代的一个体属于状态,i,(=1,2,3),的概率。,讨论基因类型的演变情况,基因比例,d:r=p:q,转移概率矩阵,状态转移概率,随机繁殖,马氏链模型,自然界中通常,p=q,=1/2,稳态分布,D,:,H,:,R,=1/4:1/2:1/4,基因类型为,D,和,H,优势表征,绿色，,基因类型为,R,劣势表征,黄色。,解释,“,豆科植物的茎，绿色,:,黄色,=3:1,”,(,D+H,):,R,=3:1,随机繁殖,近亲繁殖,在一对父母的大量后代中,雄雌随机配对繁殖，讨论一系列后代的基因类型的演变过程。,状态定义为配对的基因类型组合,X,n,=1,2,3,4,5,6,配对基因组合为,DD,RR,DH,DR,HH,HR,状态转移概率,马氏链模型,I,0,R,Q,状态,1(,DD,),2(,RR,),是吸收态，马氏链是吸收链,不论初始如何，经若干代近亲繁殖，将全变为优种或劣种,.,计算从任一非吸收态出发，平均经过几代被吸收态吸收。,纯种,(,优种和劣种,),的某些品质不如混种，近亲繁殖下大约,56,代就需重新选种,.,近亲繁殖,11.4,等级结构,社会系统中的等级结构，适当、稳定结构的意义,描述等级结构的演变过程，预测未来的结构；,确定为达到某个理想结构应采取的策略。,引起等级结构变化的因素：,系统内部等级间的转移：提升和降级；,系统内外的交流：调入和退出,(,退休、调离等,).,用马氏链模型描述确定性转移问题,转移比例视为概率,基本模型,a,(,t,),等级结构,等级,i,=1,2,k,（,如助教、讲师、教授）,数量分布,n,(,t,)=(,n,1,(,t,),n,2,(,t,),n,k,(,t,),n,i,(,t,),t,年属于等级,i,的人数，,t,=0,1,比例分布,a,(,t,)=(,a,1,(,t,),a,2,(,t,),a,k,(,t,),转移矩阵,Q,=,p,ij,k,k,p,ij,是每年从,i,转至,j,的比例,基本模型,基本模型,基本模型,基本模型,等级结构,a,(,t,),状态概率,P,转移概率矩阵,用调入比例进行稳定控制,问题：给定,Q,哪些等级结构可以用合适的调入比例保持不变,a,为稳定结构,用调入比例进行稳定控制,求稳定结构,a,=(,a,1,a,2,a,3,),(,a,1,+,a,2,+,a,3,=1),(0.5,0.5,0),a,2,=,a,1,a,3,=1.5,a,2,(0,0.4,0.6),a,*,稳定域,B,B,(0,0,1),(0,1,0),(1,0,0),A,可行域,A,例 大学教师,(,助教、讲师、教授,),等级,i,=1,2,3,，,已知每年转移比例,用调入比例进行稳定控制,研究稳定域,B,的结构,寻求,a,aQ,的,另一种形式,用调入比例进行稳定控制,稳定域是,k,维空间中以,s,i,为顶点的凸多面体,研究稳定域,B,的结构,用调入比例进行稳定控制,例,(0,1,0),(1,0,0),(0,0,1),0.286,0.286,S,1,S,2,S,3,B,稳定域,B,是以,s,i,为顶点的三角形,用调入比例进行,动态,调节,问题：给定,Q,和初始结构,a,(0),求一系列的调入比例,r,使尽快达到或接近理想结构,逐步法：对于,Q,和,a,(0),求,r,使,a,(1),尽量接近,a,*,再将,a,(1),作为新的,a,(0),继续下去。,模型,例,(0,1,0),(1,0,0),(0,0,1),a,(0),0.286,0.286,a,*,a,(1),用调入比例进行,动态,调节,求,r,使,a,(1),尽量接近,a,*,7,4,2,3,5,6,0.639,0.361,0,0.165,0.165,0.670,0.747,0.253,0,0.207,0.207,0.586,0.827,0.173,0,0.235,0.235,0.531,0.883,0.117,0,0.253,0.253,0.495,0.922,0.078,0,0.264,0.264,0.472,0.949,0.051,0,0.272,0.272,0.457,r,(,t,),a,(,t,),的计算结果,a,(7),已接近,a,*,观察,r,(,t,),的特点,用调入比例进行,动态,调节,1,0.5,0.5,0,0.1,0.1,0.8,r,(,t,),a,(,t,),t,