应用随机过程.ppt
第5章 Markov链,5.1 基本概念,直观意义：,1 . Markov链的定义,定义5.1：,定义5.2：,定义5.3：,2 . 转移概率,注：有定义5.1知,转移矩阵的性质：,定义5.4：,3 . Markov链的例子,例5.1：,带有两个吸收壁的随机游动：,此时,是一齐次马氏链,状态空间为,为两个吸收状态,它的一步转移,概率为：,例5.2：,它的一步转移概率矩阵为：,例5.3：,例5.4：,例5.5：,4. n步转移概率 C-K方程,定义5.5（n步转移概率）,定理5.1: (Chapman-Kolmogorov方程，简称C-K方程),例5.6：,例5.7: (隐Markov模型）,或者为正面或者为反面.在任何给定时刻只有一枚硬,呈现，但是有时硬币可能被替换而不改变其正反面.,硬币M和W分别具有转移概率,在任何给定时刻硬币被替换的概率为30%,替换完成时，硬币的状态不变. 这一Markov链有4个状态，分别 记为1:UM; 2:DM; 3:UW; 4:DW.状态1、3表示正面 U,状态2、4表示反面D转移矩阵为44的矩阵.我们,可以计算转移概率,比如,首先,(无转移),而后,(无转移).因此转移概率为,其他转移概率类似可得，转移方式为,转移概率矩阵为,例5.8:,带有两个反射壁的随机游动：,此时,是一齐次马氏链,状态空间为,为两个反射状态,求它的一步转,移概率。,作业1：,作业2:,5.3 状态的分类及性质,引入：,定义5.7,注：,定理5.3：,注：,定义5.8:,例1：,定义5.9 (周期性),规定：,例2 (书5.14),注1：,注2：,定理5.4：,证明：板书。,注: 当两个状态的周期相同时，有时其状态之间 有显著差异。,如：,定义5.10: (常返性),注2：,注3：,注1：,例3,定义5.11,例4,引理5.1 （ ）,定理5.5,引理5.2,定理5.6,作业1：,闭集及状态空间的分解定理,闭集：,相关性质：,任何两个状态均互通,所有常返态构成一个闭集,在不可约马氏链中,所有状态具有相同的状态 类型.,状态空间分解定理：,定理5.7：,例5,例6：,作业1：,周期链分解定理：,定理5.8：,5.4 极限定理与不变分布,5.4.1 极限定理,例8（书例5.17）(0-1传输系统）,45,46,对d的非整数倍数的m，,i是零常返的,47,(2), i是遍历的，d=1，i < ，,子序列,所以d=1，从而i为非周期的，i是遍历的,定理5.10,结论：,(a)所有非常返状态组成的集合不可能是闭集;,(b)没有零常返状态;,(c)必有正常返状态;,(d)不可约有限马氏链只有正常返态;,(e)状态空间可以分解为:,其中：每个,均是由正常返状态,组成的有限不可约闭集，,是非常返态集。,51,注1： 有限状态的马氏链，不可能全是非常返状态， 也不可能含有零常返状态，从而不可约的有限状态 的马氏链必为正常返的。,证 设S=0,1,N，如S全是非常返状态，则对任意 i, jI，知,故,矛盾。,如S含有零常返状态 i，则C=j:ij是有限不可约闭集,，由定理知，C中均为零常返状态，知,52,由引理知,所以,53,注2: 如马氏链有一个零常返状态，则必有无限多个,证 设i为零常返状态，则C=j:ij是不可约闭集，C,中均为零常返状态，故C不能是有限集。否则,零常返状态。,54,称概率分布j , jI为马尔可夫链,的平稳分布（不变分布），若,5.4.2不变分布 (平稳分布)与极限分布,定义5.12,一、不变分布 (平稳分布),55,注：,(1) 若初始概率分布 pj , jI 是平稳分布，则,(2) 对平稳分布j , jI，有,矩阵形式 = 其中 =(j)， ( ),pj = pj(1)= pj(2) = = pj(n),56,二、遍历性的概念与极限分布,对于一般的两个状态的马氏链, 由上节内容可知,意义,对固定的状态j,不管链在某一时刻的什么状,态 i出发, 通过长时间的转移到达状态 j 的概率都趋,定义5.13,58,或定义,则称此链具有遍历性.,定理5.13,60,定理 不可约非周期马尔可夫链是正常返的充要条件 是存在平稳分布，且此平稳分布就是极限分布,61,推论3 若j , jI是马尔可夫链的平稳分布，则,所取的值与初始状态的分布无关。,证：由于：,故,62,即，经过无穷次转移后处于,状态的概率与初始,状态无关，与初始状态的分布也无关。,63,解 因为马尔可夫链是不可约非周期有限,状态的，所以平稳分布存在，设,则 = P，1+2+3=1. 即,各状态的平均返回时间为, =(1, 2, 3 ),64,例2 设马尔可夫链转移概率矩阵为,求每一个不可约闭集的平稳分布。,65,解 从状态转移图看出，状态空间可分解为,两个不可约常返闭集 C1=2,3,4 和 C2=5,6,7，,一个非常返集 N=1。,在常返集上求平稳分布：,66,在C1上，对应的转移概率矩阵为,C1上的平稳分布为：0, 0.4, 0.2, 0.4, 0, 0, 0,同理可求得 C2 上的平稳分布为,0, 0, 0, 0, 1/3, 1/3, 1/3,67,三、(有限链)遍历性的充分条件,68,说明,2. 极限分布转化为了求解方程组.,3. 在定理的条件下马氏链的极限分布是平稳分布.,69,试说明带有两个反射壁的随机游动是遍历的, 并求其极限分布(平稳分布).,解,例3,四、应用举例,70,无零元,链是遍历的,71,代入最后一个方程 (归一条件), 得唯一解,72,所以极限分布为,这个分布表明,经过长时间游动之后, 醉汉 Q 位于点 2 (或 3 或 4 ) 的概率约为 3/11, 位于点 1 (或 5) 的概率约为 1/11.,73,设一马氏链的一步转移概率阵为,试讨论它的遍历性.,解,例4,74,表明,此链不具遍历性.,75,五、小结,遍历性的概念,则称此链具有遍历性.,76,(有限链) 遍历性的充分条件,作业1：,作业2：书习题5.7,78,第七节 连续时间马尔可夫链,定义7.1 设随机过程X(t)，t 0 ，状态空间,及非负整数 i1,i2, ,in+1 ，有,PX(tn+1)=in+1|X(t1)=i1, X(t2)=i2, X(tn)=in,则称X(t)，t 0 为连续时间马尔可夫链。,I=0,1,2,，若对任意,0t1< t2<<tn+1,=PX(tn+1)=in+1|X(tn)=in，,79,转移概率：在s时刻处于状态i，经过时间t后,转移到状态j的概率,pij(s,t)= PX(s+t)=j|X(s)=i,定义7.2 齐次转移概率(与起始时刻 s 无关，只,与时间间隔 t 有关),pij(s,t)=pij(t),此时有转移概率矩阵P(t)=(pij(t) ，i, jI，t 0.,80,记 i 为过程在状态转移之前停留在状态i的时间，,则对s, t 0 有,(1),(2) i 服从指数分布,证：(1) 事实上,81,82,(2) 设i的分布函数为F(x), (x0),则生存函数,由此可推出G(x)为指数函数，G(x)=e-x,则F(x)=1-G(x)=1- e-x为指数分布函数。,G(x)=1-F(x),83,过程在状态转移之前处于状态i的时间i服从指数分布 (1)当i=时， 状态i的停留时间i 超过x的概率为0，则称状态i为瞬时状态； (2)当i=0时， 状态i的停留时间i 超过x的概率为1，则称状态i为吸收状态。,84,定理7.1 齐次马尔可夫过程的转移概率具有下列性质： (1) pij(t)0; (2) (3) 证 由概率的定义，(1)(2)显然成立，下证(3),85,86,注： 此为转移概率的正则性条件。,87,例1 证明泊松过程X(t),t0为连续时间齐次马尔可夫链。 证 先证泊松过程的马尔可夫性。 泊松过程是独立增量过程，且X(0)=0，对任意0<t1< t2<< tn< tn+1有,88,另一方面,即泊松过程是一个连续时间马尔可夫链,89,再证齐次性。当ji时， 当j<i时,因增量只取非负整数值,故 pij(s,t)=0， 所以 转移概率与s无关，泊松过程具有齐次性。,第六节 马氏链模型,6.1 基本应用实例 6.2 健康与疾病 6.3 钢琴销售的存储策略,马氏链模型,系统在每个时期所处的状态是随机的,从一时期到下时期的状态按一定概率转移,下时期状态只取决于本时期状态和转移概率 已知现在，将来与过去无关（无后效性）,描述一类重要的随机动态系统（过程）的模型,马氏链 (Markov Chain) 时间、状态均为离散的随机转移过程,92,某计算机房的一台计算机经常出故障,研究者 每隔15分钟观察一次计算机运行状态,收集了24小 时的数据 (共作97次观察) . 用1表示正常状态, 用0 表示不正常状态, 所得的数据序列如下:试求一步转移概率矩阵。,1110010011111110011110111111001111111110001101101,分析,状态空间: I=0, 1.,例1,111011011010111101110111101111110011011111100111,6.1 基本应用实例,93,96 次状态转移的情况:,因此, 一步转移概率可用频率近似地表示为:,94,特点:,用行向量表示为,一维分布由初始分布和 转移概率矩阵决定,95,由以上讨论知,转移概率决定了马氏链的运动的统计规律. 因此, 确定马氏链的任意n步转移概率成为马氏链理论中的重要问题之一.,96,设每一级的传真率为 p, 误码率为 q=1-p.,设一个单位时间传输一级,只传输数字0和1的串联系统 ( 传输系统),如图:,分析:,例2,97,而与时刻 n 以前所处的状态无关.,所以它是一个马氏链, 且是齐次的.,一步转移概率,一步转移概率矩阵,98,在 传输系统中,传输后的误码率;,系统经 n 级传输后输出为 1, 问原发字符也是 1 的 概率是多少?,99,解,先求出 n 步转移概率矩阵.,有相异的特征值,所以可将 P 表示成对角阵,100,传输后的误码率分别为:,101,(2) 根据贝叶斯公式, 当系统经 n 级传输后输出为 1, 原发字符也是 1 的概率为:,102,说明,n步转移概率矩阵为,矩阵一般可表示为:,对于只有两个状态的马氏链, 一步转移概率,通过有实际背景的例子介绍马氏链的基本概念和性质,例1. 人的健康状况分为健康和疾病两种状态，设对特定年龄段的人，今年健康、明年保持健康状态的概率为0.8, 而今年患病、明年转为健康状态的概率为0.7，,6.2 健康与疾病,人的健康状态随着时间的推移会随机地发生转变,保险公司要对投保人未来的健康状态作出估计, 以制订保险金和理赔金的数额,若某人投保时健康, 问10年后他仍处于健康状态的概率,Xn+1只取决于Xn和pij, 与Xn-1, 无关,状态与状态转移,状态转移具有无后效性,设投保时健康,给定a(0), 预测 a(n), n=1,2,设投保时疾病,n时状态概率趋于稳定值，稳定值与初始状态无关,状态与状态转移,例2. 健康和疾病状态同上，Xn=1 健康, Xn=2 疾病,p11=0.8, p12=0.18, p13=0.02,死亡为第3种状态，记Xn=3,健康与疾病,p21=0.65, p22=0.25, p23=0.1,p31=0, p32=0, p33=1,设投保时处于健康状态，预测 a(n), n=1,2,不论初始状态如何，最终都要转到状态3 ； 一旦a1(k)= a2(k)=0, a3(k)=1, 则对于nk, a1(n)=0， a2(n)=0, a3(n)=1, 即从状态3不会转移到其它状态。,状态与状态转移,马氏链的基本方程,基本方程,马氏链的两个重要类型,1. 正则链 从任一状态出发经有限次转移能以正概率到达另外任一状态（如例1）。,w 稳态概率,马氏链的两个重要类型,2. 吸收链 存在吸收状态（一旦到达就不会离开的状态i, pii=1）,且从任一非吸收状态出发经有限次转移能以正概率到达吸收状态（如例2）。,6.3 钢琴销售的存贮策略,钢琴销售量很小，商店的库存量不大以免积压资金,一家商店根据经验估计，平均每周的钢琴需求为1架,存贮策略：每周末检查库存量，仅当库存量为零时，才订购3架供下周销售；否则，不订购。,估计在这种策略下失去销售机会的可能性有多大，以及每周的平均销售量是多少。,背景与问题,问题分析,顾客的到来相互独立，需求量近似服从泊松分布，其参数由需求均值为每周1架确定，由此计算需求概率,存贮策略是周末库存量为零时订购3架 周末的库存量可能是0, 1, 2, 3，周初的库存量可能是1, 2, 3。,用马氏链描述不同需求导致的周初库存状态的变化。,动态过程中每周销售量不同，失去销售机会（需求超过库存）的概率不同。,可按稳态情况（时间充分长以后）计算失去销售机会的概率和每周的平均销售量。,模型假设,钢琴每周需求量服从泊松分布，均值为每周1架,存贮策略：当周末库存量为零时，订购3架，周初到货；否则，不订购。,以每周初的库存量作为状态变量，状态转移具有无后效性。,在稳态情况下计算该存贮策略失去销售机会的概率，和每周的平均销售量。,模型建立,Dn第n周需求量，均值为1的泊松分布,Sn第n周初库存量(状态变量 ),状态转移规律,状态转移阵, ,模型建立,状态概率,马氏链的基本方程,已知初始状态，可预测第n周初库存量Sn=i 的概率,n, 状态概率,第n周失去销售机会的概率,n充分大时,模型求解,从长期看，失去销售机会的可能性大约 10%。,1. 估计在这种策略下失去销售机会的可能性,模型求解,第n周平均售量,从长期看，每周的平均销售量为 0.857(架),n充分大时,思考：为什么这个数值略小于每周平均需求量1(架) ?,2. 估计这种策略下每周的平均销售量,敏感性分析,当平均需求在每周1 (架) 附近波动时，最终结果有多大变化。,设Dn服从均值为的泊松分布,状态转移阵,第n周(n充分大)失去销售机会的概率,当平均需求增长（或减少）10%时，失去销售机会的概率将增长（或减少）约12% 。,期末复习要点：,1.上极限、下极限的定义及含义，理解事件序列的极限的表达方式。 2.熟悉常见的分布函数。 3.掌握矩母函数与特征函数的定义和性质，会求一些函数的矩母函数和特征函数。 4.条件概率与条件期望的求法及性质， 如：EX=EE(X|Y), E(X|X)=X,第一章,期末复习要点：,1.理解会求随机过程的均值函数、方差函数、(自)协方差函数、 (自)相关函数、 互协方差函数、互相关函数。 2.理解(严、宽)平稳过程的定义，会判断随机过程是否为平稳过程。 3.会用定义判定平稳过程是否有遍历性(均值遍历性及协方差遍历性) 。,第二章,期末复习要点：,1.Poisson过程的定义，理解其含义。 2.会求Poisson过程的一些相关的概率。 3.理解Poisson过程时间间隔序列Xn,第n次事件发生的时刻Tn相关定理。 4.非齐次Poisson过程与齐次Poisson的关系定理，非齐次Poisson的相关概率计算。,第三章,期末复习要点：,1.理解Markov链的定义，理解其数学含义，会求相应的概率。 2.会求一步转移概率及一步转移概率矩阵。 3.会求n步转移概率，会证明C-K方程(离散时间及连续时间) 。 4.会求状态的周期，会判定状态的常返性(正常反、零常返和非常返)(方法1，方法2) 。,第五章,法2：,法1：,期末复习要点：,5.理解的关系。 6.会将状态进行分类 7.会判别平稳分布（不变分布）,会求平稳分布,及Markov链的遍历性.,第五章,
