应用随机过程--第五章(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,函,*,第,5,章,Markov,链,5.1,基本概念,直观意义,：,1.Markov,链的定义,1,函,定义,5.1,：,2,函数与极限,定义,5.2,：,定义,5.3,：,2.,转移概率,3,函数与极限,注,：,有定义,5.1,知,4,函数与极限,5,函数与极限,转移矩阵的性质：,定义,5.4,：,6,函数与极限,3.,Markov,链的例子,例,5.1,：,7,函数与极限,带有,两,个吸收壁的随机游动：,此时,是一齐次马氏链,状态空间为,为两个吸收状态,它的一步转移,概率为：,例,5.2,：,8,函数与极限,它的,一步转移概率,矩阵,为：,9,函数与极限,例,5.3,：,10,函数与极限,例,5.4,：,11,函数与极限,例,5.5,：,12,函数与极限,13,函数与极限,4.n,步转移概率,C-K,方程,定义,5.5,（,n,步转移概率）,14,函数与极限,定理,5.1:(Chapman-Kolmogorov,方程，简称,C-K,方程,),15,函数与极限,例,5.6,：,16,函数与极限,例,5.7,:(,隐,Markov,模型）,或者为正面或者为反面,.,在任何给定时刻只有一枚硬,呈现，但是有时硬币可能被替换而不改变其正反面,.,硬币,M,和,W,分别具有转移概率,在任何给定时刻硬币被替换的概率为,30%,替换完成时，,硬币的状态不变,.,这一,Markov,链有,4,个状态，分别,记为,1:UM;2:DM;3:UW;4:DW.,状态,1,、,3,表示正面,U,状态,2,、,4,表示反面,D,转移矩阵为,4,4,的矩阵,.,我们,17,函数与极限,可以计算转移概率,比如,首先,(,无转移,),而后,(,无转移,).,因此转移概率为,其他转移概率类似可得，转移方式为,转移概率矩阵为,18,函数与极限,例,5.8,:,19,函数与极限,带有,两,个,反射,壁的随机游动：,此时,是一齐次马氏链,状态空间为,为两个,反射,状态,求,它的一步转,移,概率,。,作业,1,：,20,函数与极限,作业,2:,21,函数与极限,5.3,状态的分类及性质,引入：,22,函数与极限,定义,5.7,注：,定理,5.3,：,23,函数与极限,注：,定义,5.8:,例,1,：,24,函数与极限,定义,5.9 (,周期性,),规定：,例,2 (,书,5.14),注,1,：,注,2,：,25,函数与极限,定理,5.4,：,证明：板书。,注,:,当两个状态的周期相同时，有时其状态之间,有显著差异。,如：,26,函数与极限,定义,5.10:(,常返性,),27,函数与极限,注,2,：,注,3,：,注,1,：,28,函数与极限,例,3,定义,5.11,29,函数与极限,例,4,30,函数与极限,引理,5.1,（）,31,函数与极限,定理,5.5,32,函数与极限,引理,5.2,定理,5.6,33,函数与极限,作业,1,：,34,函数与极限,闭集及状态空间的分解定理,闭集：,35,函数与极限,相关性质：,任何两个状态均互通,所有常返态构成一个闭集,在不可约马氏链中,所有状态具有相同的状态,类型,.,36,函数与极限,状态空间分解定理：,定理,5.7,：,37,函数与极限,例,5,38,函数与极限,例,6,：,39,函数与极限,作业,1,：,40,函数与极限,周期链分解定理：,定理,5.8,：,41,函数与极限,5.4,极限定理与不变分布,5.4.1,极限,定理,42,函数与极限,例,8,（书例,5.17,）,(0-1,传输系统）,43,函数与极限,44,函数与极限,45,推论,设,i,常返，则,(1),i,零常返,(2),i,遍历,定理,5.9,设,i,常返且有周期为,d,，,则,其中,i,为,i,的平均返回时间,.,当,i,=,时,函数与极限,46,证,:(1),i,零常返,i,=,由定理,5.9,知，,对,d,的非整数倍数的,m,，,从而子序列,i,是零常返的,函数与极限,47,(2),i,是遍历的，,d,=1，,i,，,子序列,所以,d,=1，,从而,i,为非周期的，,i,是遍历的,函数与极限,定理,5.10,结论：,48,函数与极限,49,函数与极限,(a),所有非常返状态组成的集合不可能是闭集,;,(b),没有零常返状态,;,(c),必有正常返状态,;,(d),不可约有限马氏链只有正常返态,;,(e),状态空间可以分解为,:,其中：每个,均是由正常返状态,组成的有限不可约闭集，,是非常返态集。,50,函数与极限,51,注,1,：,有限状态的马氏链，不可能全是非常返状态，,也不可能含有零常返状态，从而不可约的有限状态,的马氏链必为正常返的。,证,设,S,=0,1,N,，,如,S,全是非常返状态,，则对任意,i,j,I,，,知,故,矛盾。,如,S,含有零常返状态,i,，,则,C,=,j,:,i,j,是有限不可约闭集,，由定理知，,C,中均为零常返状态，知,函数与极限,52,由引理知,所以,函数与极限,53,注,2:,如马氏链有一个零常返状态，则必有无限多个,证,设,i,为零常返状态,，,则,C,=,j,:,i,j,是不可约闭集，,C,中均为零常返状态，故,C,不能是有限集。否则,零常返状态。,函数与极限,54,称概率分布,j,j,I,为马尔可夫链,的平稳分布（不变分布），若,设,X,n,n,0,是齐次马尔可夫链，状态空间为,I,，,转移,概率为,p,ij,5.4.2,不变分布,(,平稳分布,),与极限分布,定义,5.12,一、,不变分布,(,平稳分布,),函数与极限,55,注：,(1)若初始概率分布,p,j,j,I,是平稳分布，则,(2)对平稳分布,j,j,I,，,有,矩阵形式,=,其中,=(,j,)，(,),p,j,=,p,j,(1)=,p,j,(2)=,=,p,j,(,n,),函数与极限,56,二、遍历性的概念与极限分布,对于一般的两个状态的马氏链,由上节内容可知,意义,对固定的状态,j,不管链在某一时刻的什么,状,态,i,出发,通过长时间的转移到达状态,j,的概率都趋,函数与极限,定义,5.13,57,函数与极限,58,或定义,则称此链具有,遍历性,.,函数与极限,定理,5.13,59,函数与极限,60,定理,不可约非周期马尔可夫链是正常返的充要条件,是存在平稳分布，且此平稳分布就是极限分布,推论2,若不可约马尔可夫链的所有状态是非常返或,零常返，则不存在平稳分布,.,推论1,有限状态的不可约非周期马尔可夫链必存在,平稳分布。,函数与极限,61,推论3,若,j,j,I,是马尔可夫链的平稳分布，则,所取的值与初始状态的分布无关。,证：由于：,故,函数与极限,62,例,1,设马尔可夫链的转移概率矩阵为,求马尔可夫链的平稳分布及各状态的,平均返回时间。,即，经过无穷次转移后处于,状态的概率与初始,状态无关，与初始状态的分布也无关。,函数与极限,63,解,因为马尔可夫链是不可约非周期有限,状态的，所以平稳分布存在，设,则,=,P，,1,+,2,+,3,=1,.,即,各状态的平均返回时间为,=(,1,2,3,),函数与极限,64,例,2,设马尔可夫链转移概率矩阵为,求每一个不可约闭集的平稳分布。,函数与极限,65,解 从状态转移图看出，状态空间可分解为,两个不可约常返闭集,C,1,=2,3,4,和,C,2,=5,6,7，,一个非常返集,N,=1。,在常返集上求平稳分布：,函数与极限,66,在,C,1,上，对应的转移概率矩阵为,C,1,上的平稳分布为：0,0.4,0.2,0.4,0,0,0,同理可求得,C,2,上的平稳分布为,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,77,函数与极限,78,第七节,连续时间马尔可夫链,定义,7.1,设,随机过程,X,(,t,)，,t,0,，状态空间,及非负,整数,i,1,i,2,i,n,+1,，,有,P,X,(,t,n,+1,),=,i,n,+1,|X,(,t,1,)=,i,1,X,(,t,2,)=,i,2,X,(,t,n,)=,i,n,则称,X,(,t,)，,t,0,为,连续时间马尔可夫链,。,I,=0,1,2,，,若对任意,0,t,1,t,2,t,n+1,=,P,X,(,t,n+1,),=,i,n+1,X,(,t,n,)=,i,n,，,函数与极限,79,转移概率,：在,s,时刻处于状态,i,，经过时间,t,后,转移到状态,j,的,概率,p,ij,(,s,t,)=,P,X,(,s,+,t,),=,j,|X,(,s,)=,i,定义,7.2,齐次,转移概率,(与起始时刻,s,无关，只,与时间间隔,t,有关),p,ij,(,s,t,)=,p,ij,(,t,),此时,有转移概率矩阵,P,(,t,)=(,p,ij,(,t,),),，,i,j,I,，,t,0.,函数与极限,80,记,i,为过程在状态转移之前停留在状态,i,的时间，,则对,s,t,0,有,(1),(2),i,服从指数分布,证,：(1)事实上,s,s+t,0,i,i,i,i,t,i,函数与极限,81,函数与极限,82,(2)设,i,的分布函数为,F,(,x,),(,x,0),则生存函数,由此可推出,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),p,ij,(,t,),0;,(2),(3),证,由概率的定义，(1)(2)显然成立，下证(3),函数与极限,85,函数与极限,86,注：,此为转移概率的正则性条件。,函数与极限,87,例,1,证明泊松过程,X,(,t,),t,0,为连续时间齐次马尔可夫链。,证 先证,泊松过程,的,马尔可夫性。,泊松过程是独立增量过程，且,X,(0)=0，,对任意0,t,1,t,2,t,n,t,n,+1,有,函数与极限,88,另一方面,即泊松过程是一个连续时间马尔可夫链,函数与极限,89,再证齐次性。,当,j,i,时，,当,j,k,a,1,(,n,)=0,，,a,2,(,n,)=0,a,3,(,n,)=1,即从状态,3,不会转移到其它状态。,状态,与,状态转移,0,0,1,50,0.1293,0.0326,0.8381,107,函数与极限,马氏链的基本方程,基本方程,108,函数与极限,马氏链的两个重要类型,1.,正则链,从任一状态出发经有限次转移能以正概率到达另外任一状态（如例,1,）。,w,稳态概率,109,函数与极限,马氏链的两个重要类型,2.,吸收链,存在吸收状态（一旦到达就不会离开的状态,i,p,ii,=1,）,且,从任一非吸收状态出发经有限次转移能以正概率到达吸收状态（如例,2,）。,110,函数与极限,6.3,钢琴销售的存贮策略,钢琴销售量很小，商店的库存量不大以免积压资金,一家商店根据经验估计，平均每周的钢琴需求为,1,架,存贮策略,：每周末检查库存量，仅当库存量为零时，才订购,3,架供下周销售；否则，不订购。,估计在这种策略下失去销售机会的可能性有多大，以及每周的平均销售量是多少。,背景与问题,111,函数与极限,问题分析,顾客的到来相互独立，需求量近似服从泊松分布，其参数由需求均值为每周,1,架确定，由此计算需求概率,存贮策略是周末库存量为零时订购,3,架,周末的库存量可能是,0,1,2,3,，周初的库存量可能是,1,2,3,。,用马氏链描述不同需求导致的周初库存状态的变化。,动态过程中每周销售量不同，失去销售机会（需求超过库存）的概率不同。,可按稳态情况（时间充分长以后）计算失去销售机会的概率和每周的平均销售量。,112,函数与极限,模型假设,钢琴每周需求量服从泊松分布，均值为每周,1,架,存贮策略,：当周末库存量为零时，订购,3,架，周初到货；否则，不订购。,以每周初的库存量作为状态变量，状态转移具有无后效性。,在稳态情况下计算该存贮策略失去销售机会的概率，和每周的平均销售量。,113,函数与极限,模型建立,D,n,第,n,周需求量，均值为,1,的泊松分布,S,n,第,n,周初库存量,(,状态变量,),状态转移规律,D,n,0 1 2 3 3,P,0.368 0368 0.184 0.061 0.019,状态转移阵,114,模型建立,状态概率,马氏链的基本方程,正则链,稳态概率分布,w,满足,wP=w,已知初始状态，可预测第,n,周初库存量,S,n,=i,的概率,n,状态概率,115,函数与极限,第,n,周失去销售机会的概率,n,充分大时,模型求解,从长期看，失去销售机会的可能性大约,10%,。,1.,估计在这种策略下失去销售机会的可能性,D,0 1 2 3 3,P,0.368 0.368 0.184 0.061 0.019,116,函数与极限,模型求解,第,n,周平均售量,从长期看，每周的平均销售量为,0.857(,架,),n,充分大时,需求不超过存量,销售需求,需求超过存量,销售存量,思考：为什么这个数值略小于每周平均需求量,1(,架,)?,2.,估计这种策略下每周的平均销售量,117,函数与极限,敏感性分析,当平均需求在每周,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%,。,118,函数与极限,期末复习要点：,1.,上极限、下极限的定义及含义，理解事件序列的极限的表达方式。,2.,熟悉常见的分布函数。,3.,掌握矩母函数与特征函数的定义和性质，会求一些函数的矩母函数和特征函数。,4.,条件概率与条件期望的求法及性质，,如：,EX=EE(X|Y),E(X|X)=X,第一章,119,函数与极限,期末复习要点：,1.,理解会求随机过程的均值函数、方差函数、,(,自,),协方差函数、,(,自,),相关函数、,互协方差函数、互相关函数。,2.,理解,(,严、宽,),平稳过程的定义，会判断随机过程是否为平稳过程。,3.,会用定义判定平稳过程是否有遍历性,(,均值遍历性及协方差遍历性,),。,第二章,120,函数与极限,期末复习要点：,1.Poisson,过程的定义，理解其含义。,2.,会求,Poisson,过程的一些相关的概率。,3.,理解,Poisson,过程时间间隔序列,Xn,第,n,次事件发生的时刻,Tn,相关定理。,4.,非齐次,Poisson,过程与齐次,Poisson,的关系定理，非齐次,Poisson,的相关概率计算。,第三章,121,函数与极限,期末复习要点：,1.,理解,Markov,链的定义，理解其数学含义，会求相应的概率。,2.,会求一步转移概率及一步转移概率矩阵。,3.,会求,n,步转移概率，会证明,C-K,方程,(,离散时间及连续时间,),。,4.,会求状态的周期，会判定状态的常返性,(,正常反、零常返和非常返,)(,方法,1,，方法,2),。,第五章,122,函数与极限,法,2,：,法,1,：,123,函数与极限,期末复习要点：,5.,理解的关系。,6.,会将状态进行分类,7.,会判别平稳分布（不变分布）,会求平稳分布,及,Markov,链的遍历性,.,第五章,124,函数与极限,