随机过程 第三章 马尔科夫连资料课件.ppt

1,第三章 马尔可夫链,马尔可夫链定义一步转移概率及多步转移概率初始概率及绝对概率Chapman-Kolmogorov方程马尔可夫链状态分类遍历的马尔可夫链及平稳分布,2,马尔可夫过程,将来的状态只与当前状态有关，与过去状态无关，即无后效性,3,马尔可夫链定义,定义：设有随机过程Xn,nT，若对于任意的整数nT和任意的 i0,i1, ,in+1I，条件概率满足,则称Xn,nT为马尔可夫链，简称马氏链,时间和状态都离散的马尔可夫过程称为马尔可夫链,4,定义称条件概率为马尔可夫链Xn,nT在时刻n的一步转移概率，其中i,jI，简称转移概率。,定义若对任意的i,jI，马尔可夫链Xn,nT的转移概率与n无关，则称马尔可夫链是齐次马尔可夫链。我们只讨论齐次马氏链。,5,设P表示一步转移概率所组成的矩阵，则,称为系统状态的一步转移概率矩阵，它具有如下性质：,满足上述两个性质的矩阵称为随机矩阵。,6,例：(0-1传输系统)如图所示，只传输数字0和1的串联系统中，设每一级的传真率为p，误码率为q=1-p。并设一个单位时间传输一级，X0是第一级的输入，Xn是第n级的输出(n1)，那么Xn,n=0,1,2是一随机过程，状态空间I=0,1，而且当Xn=i为已知时，Xn+1所处的状态的概率分布只与Xn=i有关，而与时刻n以前所处的状态无关，所以它是一个马氏链，而且还是齐次的。,7,例：一维随机游动。设一醉汉Q(或看作一随机游动的 质点)在直线上的点集I=1,2,3,4,5作随机游动，游动的概率规则是：如果Q现在位于点i(1i5)，则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；如果Q现在处于1(或5)这一点上，则下一时刻就以概率1移动到2(或4)这点上，1和5这两点称为反射壁，这种游动称为带有两个反射壁的随机游动。,8,例：排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成。服务规则为：先到先服务，后来者需在等候室依次排队，假设一个需要服务的顾客到达系统时发现系统内已有3个顾客，则该顾客立即离去。 设时间间隔t内有一个顾客进入系统的概率为q，有一接受服务的顾客离开系统(即服务完毕)的概率为p,又设当t充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的，再设有无顾客来到与服务是否完毕是相互独立的。,9,例：生灭链观察某生物群落，以Xn表示在时刻n群体的数目，设为i个数量单位，如在时刻n+1增加到i+1个数量单位的概率为bi，减灭到i-1个数量单位的概率为ai，保持不变的概率为ri=1- ai - bi ，则Xn，n=0为齐次马尔科夫链，其转移概率为,10,定义称条件概率为马尔可夫链Xn,nT的n步转移概率，并称,为马尔可夫链的n步转移矩阵。规定,例题,设马尔可夫链Xn,nT有状态空间I=0,1，其一步转移概率矩阵为,求 和两步转移概率矩阵P(2),11,定理设Xn,nT为马尔可夫链，则对任意整数n0，0ln和i,jI，n步转移概率 具有下列性质：,Chapman-Kolmogorov方程,12,定义：称 为时刻n马尔可夫链的绝对概率；称 为马尔可夫链的绝对分布；称 为n时刻的绝对概率向量。,定义：称 为马尔可夫链的初始分布；称 为马尔可夫链的初始分布；称 为马尔可夫链的初始概率向量。,13,定理设Xn,nT为马尔可夫链，则对任意jI和n1，绝对概率pj(n)具有下列性质：,14,定理设Xn,nT为马尔可夫链，则对任意i1, ,inI和n1，有,证明,15,例：某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机的运行状态，收集了24个小时的数(共作97次观察)，用1表示正常状态，用0表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111 设Xn为第n(n=1,2,97)个时段的计算机状态，可以认为它是一个齐次马氏链. 求 (1)一步转移概率矩阵; (2)已知计算机在某一时段(15分钟)的状态为0，问在此条件下，从此时段起，该计算机能连续正常工作45分钟(3个时段)的条件概率.,16,例题：天气预报问题1设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨、今日有雨，明日有雨的概率为0.5；昨日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为0.2。若星期一、星期二均下雨，求星期四下雨的概率。,17,例题：天气预报问题2设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨、今日有雨，明日有雨的概率为0.5；昨日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为0.2。若星期一、星期二均下雨，求星期四下雨的概率。,例题：无限制随机游动设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动的概率为q=1-p，这种运动称为无限制随机游动。以Xn表示时刻n质点所处的位置，则Xn,nT是一个齐次马尔可夫链，求一步和k步转移概率。,例题：有吸收壁随机游动甲、乙进行赌博，甲有a元，乙有b元，每赌一局输家给赢家1元，没有和局，直到一人输光为止。设每一局甲赢的概率为p，输的概率为q=1-p，求甲输光的概率。,20,马尔可夫链的状态分类,周期、非周期常返、非常返正常返、零常返遍历状态,21,设马尔可夫链的状态空间I=1,2,3,4,5,6,7,8,9，状态间的概率转移图如下图,22,假设Xn,n0是齐次马尔可夫链，其状态空间I=0,1,2,3, ，转移概率是pij，i,jI，初始分布为pj,j I。,定义如集合n: n1,pii(n)0非空，则称该集合的最大公约数d=d(i)=G.C.Dn:pii(n)0为状态i的周期。,引理如i的周期为d，则存在正整数M，对一切nM，有pii(nd)0。,如d1就称i为周期的，如d=1就称i为非周期的。,如果i有周期D，则对一切非零的n0(mod(D)都有pii(n)=0。但这也并不是说对任意n有pii(nd)0。例如上图中状态1的d=2，但pii(2)=0。,23,例：状态转移概率图,状态的常返性,24,首中概率,它表示质点由i出发，经n步首次到达j 的概率,表示质点由i出发，经有限步终于到达j 的概率。,定义 称状态i为常返的，如fii=1；称状态i为非常返的，如fii1。,对于常返态i，由定义知fii(n),n1构成一概率分布,表示由i出发再返回i的平均返回时间。,25,定义如ui，则称常返态i为正常返的；如ui= ，则称常返态i为零常返的。非周期的正常返态称为遍历状态。,常返性的判别,含义：当i常返时，返回i的次数为无限多次；当i非常返时，返回的次数只能是有限多次。,26,27,28,状态空间的分解,定义：状态空间I的子集C称为闭集，如果对任意 及 都有,定义：闭集C称为不可约的，如果C的状态互通。,定义：马尔可夫链称为不可约的，如果其状态空间不可约。,29,30,3）D由全体非常返状态组成，自Cn中的状态不能到达D中的状态。,状态空间的分解定理：,任一马尔可夫链的状态空间I，可唯一的分解成有限个或可列个互不相交的子集D,C1,C2, 之和，使得,1） 每一Cn是常返态组成的不可约闭集；,2）Cn中的状态同类，或全是正常返，或全是零常返。 它们有相同的周期且fjk=1,j,kCn。,31,32,的渐进性质与平稳分布,33,34,35,定义称概率分布j,jI为马尔可夫链的平稳分布，若它满足,定理不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布，且此平稳分布就是极限分布 。,推论1：有限状态的不可约非周期马氏链必存在平稳分布。,推论2： 若所有状态是非常返或零常返的，则不存在平稳分布。,36,例题若马尔可夫链有三状态，其概率转移矩阵为,问此马尔可夫链是否遍历，若遍历求其平稳分布。,例：马尔科夫连的状态空间为1,2,3,4,5,6,7，其转移概率矩阵为,37,作业：4.1 4.6 4.12,