马尔科夫模型ppt(2012).ppt

1、马尔可夫过程,马尔可夫个人简介,马尔可夫（18561922），苏联数学家。切比雪夫的学生。在概率论、数论、函数逼近论和微分方程等方面卓有成就。 马尔可夫是彼得堡数学学派的代表人物。以数论和概率论方面的工作著称。他的主要著作有概率演算等。在数论方面，他研究了连分数和二次不定式理论 ，解决了许多难题 。在概率论中，他发展了矩法，扩大了大数律和中心极限定理的应用范围。马尔可夫最重要的工作是在19061912年间，提出并研究了一种能用数学分析方法研究自然过程的一般图式马尔可夫链。同时开创了对一种无后效性的随机过程马尔可夫过程的研究。马尔可夫经多次观察试验发现，一个系统的状态转换过程中第n次转换获得的状

2、态常决定于前一次（第（n-1）次）试验的结果。马尔可夫进行深入研究后指出：对于一个系统，由一个状态转至另一个状态的转换过程中，存在着转移概率，并且这种转移概率可以依据其紧接的前一种状态推算出来，与该系统的原始状态和此次转移前的马尔可夫过程无关。目前，马尔可夫链理论与方法已经被广泛应用于自然科学、工程技术和公用事业中,第一节 马尔可夫过程及其概率分布,一、马尔可夫过程的概念,二、马尔可夫过程的概率分布,三、应用举例,四、小结,一、马尔可夫过程的概念,1. 马尔可夫性(无后效性),马尔可夫性或无后效性.,即: 过程“将来”的情况与“过去”的情况是无关的.,2. 马尔可夫过程的定义,具有马尔可夫性的

3、随机过程称为马尔可夫过程.,用分布函数表述马尔可夫过程,恰有,或写成,并称此过程为马尔可夫过程.,3. 马尔可夫链的定义,时间和状态都是离散的马尔可夫过程称为马尔 可夫链,简记为,研究时间和状态都是离散的随机序列,二、马尔可夫过程的概率分布,1. 用分布律描述马尔可夫性,有,称条件概率,说明: 转移概率具有特点,2. 转移概率,由转移概率组成的矩阵,称为马氏链的转移概率矩阵.,此矩阵的每一行元素之和等于1.,它是随机矩阵.,3. 平稳性,有关时, 称转移概率具有平稳性.,同时也称此链是齐次的或时齐的.,称为马氏链的n步转移概率,一步转移概率,特别的, 当 k=1 时,一步转移概率矩阵,的状态,

4、记为P,三、应用举例,证明,由独立增量过程的定义知,即有,例1,马尔可夫过程.,说明:,泊松过程是时间连续状态离散的马氏过程.,泊松过程,泊松过程的定义（1）,泊松过程的定义（2）,设每一级的传真率为 p, 误码率为 q=1-p.,设一个单位时间传输一级,只传输数字0和1的串联系统 ( 传输系统),如图:,分析:,例2,而与时刻 n 以前所处的状态无关.,所以它是一个马氏链, 且是齐次的.,一步转移概率,一步转移概率矩阵,例3 一维随机游动,游动的概率规则,1/3的概率向左或向右移动一格, 或以1/3的概率留,在原处;,如果Q现在位于点 i (1 i 5),则下一时刻各以,以概率1移动到2(或

5、4)这一点上.,如果Q现在位于1(或5)这点上, 则下一时刻就,1和5这两点称为反射壁.,上面这种游动称为带有两个反射壁的随机游动.,模拟方法:产生均匀分布的随机数序列132322 11122,其中1表示左移;2表示不动;3表示右移.,理论分析:,状态空间就是I.,而与时刻 n 以前所处的状态无关.,所以它是一个马氏链, 且是齐次的.,一步转移概率,说明:,相应链的转移概率矩阵只须把P 中第1行改为,改变游动的概率规则, 就可得到不同方式的,随机游动和相应的马氏链. 如果把点 1 改为吸收壁,一步转移概率矩阵,例4.,某计算机房的一台计算机经常出故障,研究者 每隔15分钟观察一次计算机运行状态

6、,收集了24小 时的数据 (共作97次观察) . 用1表示正常状态, 用0 表示不正常状态, 所得的数据序列如下:,1110010011111110011110111111001111111110001101101,分析,状态空间: I=0, 1.,例5,111011011010111101110111101111110011011111100111,96 次状态转移的情况:,因此, 一步转移概率可用频率近似地表示为:,以下研究齐次马氏链的有限维分布.,特点:,用行向量表示为,一维分布由初始分布和 转移概率矩阵决定,由以上讨论知,转移概率决定了马氏链的运动的统计规律. 因此, 确定马氏链的任意

7、n步转移概率成为马氏链理论中的重要问题之一.,第二节 多步转移概率的确定,一、C-K 方程,三、应用举例,四、小结,二、多步转移概率的确定,一、C-K 方程,是一齐次马氏链, 则对任意的,切普曼-柯尔莫哥洛夫方程(简称C -K方程),说明,C-K 方程基于下列事实:,这一事件可分解成:,件的和事件.,如下图所示:,C-K 方程也可写成矩阵形式:,二、多步转移概率的确定,利用 C-K 方程我们容易确定 n 步转移概率.,得递推关系:,从而可得,马氏链的n步转移概率是一步转移概率的 n 次 方,链的有限维分布可由初始分布和一步转移概率完全确定.,结论,某计算机房的一台计算机经常出故障,研究者 每隔

8、15分钟观察一次计算机运行状态,收集了24小 时的数据 (共作97次观察) . 用1表示正常状态, 用0 表示不正常状态, 所得的数据序列如下:,1110010011111110011110111111001111111110001101101,分析,状态空间: I=0, 1.,例5,111011011010111101110111101111110011011111100111,96 次状态转移的情况:,因此, 一步转移概率可用频率近似地表示为:,在上述 传输系统中,若,传输后的误码率;,系统经 n 级传输后输出为 1, 问原发字符也是 1 的 概率是多少?,进一步，,解,先求出 n 步转移

9、概率矩阵.,有相异的特征值,所以可将 P 表示成对角阵,传输后的误码率分别为:,(2) 根据贝叶斯公式, 当系统经 n 级传输后输出为 1, 原发字符也是 1 的概率为:,说明,n步转移概率矩阵为,矩阵一般可表示为:,对于只有两个状态的马氏链, 一步转移概率,四、小结,切普曼-柯尔莫哥洛夫方程 (简称 C K 方程),马氏链的n 步转移概率是一步转移概率的n 次 方, 链的有限维分布可由初始分布和一步移概率完全确定.,由 C K 方程可得,第三节 遍历性,一、遍历性的概念,三、应用举例,四、小结,二、(有限链)遍历性的充分条件,一、遍历性的概念,对于一般的两个状态的马氏链, 由上节内容可知,意

10、义,对固定的状态j,不管链在某一时刻的什么状,态 i出发, 通过长时间的转移到达状态 j 的概率都趋,定义,则称此链具有遍历性.,二、(有限链)遍历性的充分条件,说明,2. 极限分布转化为了求解方程组.,3. 在定理的条件下马氏链的极限分布是平稳分布.,试说明带有两个反射壁的随机游动是遍历的, 并求其极限分布(平稳分布).,解,例1,三、应用举例,无零元,链是遍历的,代入最后一个方程 (归一条件), 得唯一解,所以极限分布为,这个分布表明,经过长时间游动之后, 醉汉 Q 位于点 2 (或 3 或 4 ) 的概率约为 3/11, 位于点 1 (或 5) 的概率约为 1/11.,设一马氏链的一步转

11、移概率阵为,试讨论它的遍历性.,解,例2,表明,此链不具遍历性.,(有限链) 遍历性的充分条件,例1. 设时刻n人的健康状态Xn 的取值如下：Xn=1 健康, Xn=2 疾病，,死亡为第3种状态，记Xn=3,模型一：健康与疾病,设投保时处于健康状态，预测 p(n), n=1,2,不论初始状态如何，最终都要转到状态3 ； 一旦p1(k)= a2(k)=0, p3(k)=1, 则对于nk, p1(n)=0， p2(n)=0, p3(n)=1, 即从状态3不会转移到其它状态.,该链是具有一个吸收态3的齐次马氏链,模型二：钢琴销售的存贮策略,钢琴销售量很小，商店的库存量不大以免积压资金.,一家商店根据

12、经验估计，平均每周的钢琴需求为1架.,存贮策略：每周末检查库存量，仅当库存量为零时，才订购3架供下周销售；否则，不订购.,估计在这种策略下失去销售机会的可能性有多大，以及每周的平均销售量是多少.,背景与问题,问题分析,顾客的到来相互独立，需求量近似服从波松分布，其参数由需求均值为每周1架确定，由此计算需求概率.,存贮策略是周末库存量为零时订购3架 周末的库存量可能是0, 1, 2, 3，周初的库存量可能是1, 2, 3.,用马氏链描述不同需求导致的周初库存状态的变化.,动态过程中每周销售量不同，失去销售机会（需求超过库存）的概率不同.,可按稳态情况（时间充分长以后）计算失去销售机会的概率和每周

13、的平均销售量.,模型假设,钢琴每周需求量服从波松分布，平均每周1架.,存贮策略：当周末库存量为零时，订购3架，周初到货；否则，不订购.,以每周初的库存量作为状态变量，状态转移具有无后效性.,在稳态情况下计算失去销售机会的概率和每周的平均销售量, 作为该存贮策略的评价指标.,模型建立,Dn第n周需求量，均值为1的波松分布,Sn第n周初库存量(状态变量 ),状态转移规律,状态转移阵, ,模型建立,马氏链的基本方程,已知初始状态，可预测第n周初库存量Sn=i 的概率,n, 状态概率,第n周失去销售机会的概率,n充分大时,模型求解,从长期看，失去销售机会的可能性大约 10%。,1. 估计失去销售机会的

14、可能性,存贮策略的评价指标,模型求解,第n周平均售量,从长期看，每周的平均销售量为 0.857(架),n充分大时,思考：为什么每周的平均销售量略小于平均需求量?,2. 估计每周的平均销售量,存贮策略的评价指标,每周平均需求量1架,敏感性分析,当平均需求在每周1 (架) 附近波动时，最终结果有多大变化。,设Dn服从均值的波松分布,状态转移阵,第n周(n充分大)失去销售机会的概率,当平均需求(=1.0)增长(或减少)10%时，,失去销售机会的概率P将增长(或减少)约15% 。,钢琴销售的存贮策略,存贮策略(周末库存为0则订购3架, 否则不订购)已定,计算两个指标(失去销售的概率和每周平均销售量).

15、,问题：给出最优准则及最优存贮策略。,动态随机存贮策略是马氏链的典型应用.,关键是在无后效性的前提下恰当地定义系统的状态变量(本例是每周初的库存量).,模型三 基因遗传,背景,生物的外部表征由内部相应的基因决定.,基因分优势基因d 和劣势基因r 两种.,每种外部表征由两个基因决定, 每个基因可以是d, r 中的任一个. 形成3种基因类型：dd 优种D, dr 混种H, rr 劣种R.,基因类型为优种和混种, 外部表征呈优势；基因类型为劣种, 外部表征呈劣势.,生物繁殖时后代随机地（等概率地）继承父、母的各一个基因，形成它的两个基因. 父母的基因类型决定后代基因类型的概率.,完全优势基因遗传,父

16、母基因类型决定后代各种基因类型的概率,3种基因类型：dd优种D, dr混种H, rr劣种R,完全优势基因遗传,P(DDH)=P(dddd,dr)=P(ddd)P(ddr),P(RHH)=P(rrdr,dr)=P(rdr)P(rdr),=11/2=1/2,=1/21/2=1/4,随机繁殖,设群体中雄性、雌性的比例相等，基因类型的分布相同（记作D:H:R）,每一雄性个体以D:H:R的概率与一雌性个体交配，其后代随机地继承它们的各一个基因,设初始一代基因类型比例D:H:R =a:2b:c （a+2b+c=1), 记p=a+b, q=b+c, 则群体中优势基因和劣势基因比例 d:r=p:q (p+q=

17、1),假设,建模,状态Xn=1,2,3 第n代的一个体属于D, H, R,状态概率 ai(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”,随机繁殖,近亲繁殖,在一对父母的大量后代中, 雄雌随机配对繁殖，讨论一系列后代的基因类型的演变过程。,状态定义为配对的基因类型组合,Xn=1,2,3,4,5,6配对基因组合

18、为DD,RR,DH,DR,HH,HR,状态转移概率,马氏链模型,I,0,R,Q,状态1(DD), 2(RR)是吸收态，马氏链是吸收链不论初始如何，经若干代近亲繁殖，将全变为优种或劣种.,计算从任一非吸收态出发，平均经过几代被吸收态吸收。,纯种(优种和劣种)的某些品质不如混种，近亲繁殖下大约56代就需重新选种.,近亲繁殖,模型四 等级结构,社会系统中需要适当且稳定的等级结构.,描述等级结构的演变过程，预测未来的结构.,确定为达到某个理想结构应采取的策略.,引起等级结构变化的因素：,系统内部等级间的转移：提升和降级.,系统内外的交流：调入和退出(退休、调离等).,用马氏链模型描述确定性的转移问题

19、(将转移比例视为概率),基本模型,a(t)等级结构,等级 i=1,2,k（如助教、讲师、教授）,数量分布 n(t)=(n1(t), n2(t), nk(t) ni(t) t 年属于等级i 的人数， t =0,1,比例分布 a(t)=(a1(t), a2(t), ak(t),转移矩阵 Q=pijkk, pij 是每年从i 转至j 的比例,基本模型,基本模型, 基本模型,基本模型,等级结构a(t) 状态概率,P转移概率矩阵,用调入比例进行稳定控制,问题：给定Q, 哪些等级结构可以用合适的调入比例保持不变,用调入比例进行稳定控制,a*,稳定域B,可行域A,例 大学教师(助教、讲师、教授)等级 i=1

20、,2,3，已知每年转移比例,用调入比例进行稳定控制,研究稳定域B的结构,用调入比例进行稳定控制,稳定域B是k维空间中以 si 为顶点的凸多面体,研究稳定域B的结构,用调入比例进行稳定控制,例,S1,稳定域B是以si为顶点的三角形,用调入比例进行动态调节,问题：给定Q和初始结构 a(0), 求一系列的调入比例 r, 使尽快达到或接近理想结构,逐步法：对于Q和 a(0), 求 r使 a(1)尽量接近 a*, 再将 a(1)作为新的a(0), 继续下去。,模型,例,用调入比例进行动态调节,求r 使a(1)尽量接近a*,r(t), a(t) 的计算结果,a(7)已接近a*,观察r(t)的特点,用调入比

21、例进行动态调节,等 级 结 构,等级结构的演变、预测和控制在社会系统中有广泛应用.,讨论总人数和内部转移比例不变情况下, 用调入比例控制级结构的变化.,建立等级结构演变过程的基本方程, 预测未来结构.,讨论各种推广情况：总人数按照一定比例增长；调入比例有界；调入比例固定而用内部转移比例控制级结构的变化.,可以用来预测具有等时间隔（如一年）的时刻点上各类人员的分布状况。 它是根据历史数据，预测等时间间隔点上的各类人员分布状况。此方法的基本思想上根据过去人员变动的规律，推测未来人员变动的趋势。步骤如下： 根据历史数据推算各类人员的转移率，迁出转移率的转移矩阵； 统计作为初始时刻点的各类人员分布状况

22、； 建立马尔科夫模型，预测未来各类人员供给状况； 使用马尔科夫模型进行人力资源供给预测的关键是确定出人员转移率矩阵表，而在实际预测时，由于受各种因素的影响，人员转移率是很难准确确定出来的，往往都是一种大致的估计，因此会影响到预测结果的准确性。 编辑本段马尔可夫模型假设在给定时期内从低一层次向高一层次的转移人数，或从某一类型向另一类型转移的人数是起始时刻低层次总人数或某一类型总人数的一个比例，这个比例称为人员转移率。,可以用来预测具有等时间隔（如一年）的时刻点上各类人员的分布状况。 它是根据历史数据，预测等时间间隔点上的各类人员分布状况。此方法的基本思想上根据过去人员变动的规律，推测未来人员变动

23、的趋势。步骤如下： 根据历史数据推算各类人员的转移率，迁出转移率的转移矩阵； 统计作为初始时刻点的各类人员分布状况； 建立马尔科夫模型，预测未来各类人员供给状况； 使用马尔科夫模型进行人力资源供给预测的关键是确定出人员转移率矩阵表，而在实际预测时，由于受各种因素的影响，人员转移率是很难准确确定出来的，往往都是一种大致的估计，因此会影响到预测结果的准确性。 编辑本段马尔可夫模型假设在给定时期内从低一层次向高一层次的转移人数，或从某一类型向另一类型转移的人数是起始时刻低层次总人数或某一类型总人数的一个比例，这个比例称为人员转移率。,11.5 资金流通,背景,各地区之间资金每年按一定比例相互流通.,各地区每年有资金流出并不再回来.,银行