《应用数学基础随机过程-2》由会员分享，可在线阅读，更多相关《应用数学基础随机过程-2（152页珍藏版）》请在金锄头文库上搜索。
1、马尔可夫过程,硕士研究生学位课程应用数学基础,主讲教师 段禅伦2008年秋季学期,(演示文稿),(Markoff process),第四章 马尔可夫链,马尔可夫链是最简明的马尔可夫过程, 它是状态、时 间都是离散量的马尔可夫过程.马尔可夫过程是随机过程中历史最悠久且充满活力的 一类随机过程.自20世纪初俄罗斯数学家A.A.MapkoB等人 开始研究马尔可夫过程以来,可以说久盛不衰. 它有极为 深厚的理论基础,如拓扑学、函数论、泛函分析、近世代 数和几何学; 又有广泛的应用空间,如近代物理、随机分 形、公共事业中的服务系统、电子信息、计算机技术等.自然界很多现象遵从这样的演变规则:由时刻t0系统
2、或 过程所处的状态(现在)可以决定系统或过程在时刻tt0 所处的状态(将来),而无需借助于t0以前系统或过程所处 状态(过去)的历史资料. 如微分方程初值问题即属于此.,马尔可夫链的概念及转移概率,4.1 马尔可夫链的概念及转移概率 1.马尔可夫链的定义设随机过程Xn,nT的参数集T=0,1,2,Xn可能 取值的全体组成的状态空间为I=i1,i2,i3,. 定义4.1 设有随机过程Xn,nT,若对于任意的整数nT和任意的i0,i1,in+1I,条件概率满足PXn+1=in+1|X0=i0,X1=i1,Xn=in=PXn+1=in+1|Xn=in (4.1)则称Xn,nT为马尔可夫链,简称马氏链
3、. (4.1)是马尔可夫链的马氏性(也称无后效性)的数学表达 式.利用积事件的概率及上述定义知:,马尔可夫链的概念及转移概率,PX0=i0,X1=i1,Xn=in=PXn=in|X0=i0,X1=i1,Xn-1=in-1PX0=i0,X1=i1,Xn-1=in-1=PXn=in|Xn-1=in-1PX0=i0,X1=i1,Xn-1=in-1=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2PX1=i1|X0=i0PX0=i0.即马尔可夫链的统计特性完全由条件概率PXn+1=in+1|Xn=in 所决定. 如何确定这个条件概率,是马尔可夫链理论和应 用中的重要问题之一.,
4、马尔可夫链的概念及转移概率,2.转移概率条件概率PXn+1=j|Xn=i的直观含义是:系统在时刻n处 于状态i的条件下,在时刻n+1系统处于状态j的概率.这相 当于随机游动的质点在时刻n处于状态i的条件下,下一步 转移到状态j的概率. 记此条件概率为pij(n),其严格定义 是: 定义4.2 称条件概率pij(n)=PXn+1=j|Xn=i为马尔可夫链Xn,nT在时刻n的一步转移概率,简称为转移概率,其中i,jI. 一般, 转移概率pij(n)不仅与状态i,j有关,而且与时刻 n有关.当pij(n)不依赖时刻n时,表示马尔可夫链具有平稳,马尔可夫链的概念及转移概率,转移概率. 定义4.3 若对
5、任意的i,jI, 马尔可夫链Xn,nT的转移概率pij(n)与时间n无关,则称马尔可夫链是齐次的,(亦称是时齐的,即具有平稳转移概率)并记pij(n)为pij. 下面只讨论齐次马尔可夫链,并将齐次两字省略.设P为一步转移概率pij所组成的矩阵,状态空间I=1,2, ,则P=称为系统状态的一步转移概率矩阵. 一步转移概率矩阵具有性质:,p11 p12 p1n p21 p22 p2n pi1 pi2 pin ,马尔可夫链的概念及转移概率,(1) pij0, i,jI;(2) pij=1, iI. (2)式中对j求和,是对状态空间I的所有可能状态进行的, 此性质说明一步转移概率矩阵中任一行元素之和为
6、1. 通 常称满足(1)、(2)性质的矩阵为随机矩阵. 为进一步讨论马尔可夫链的统计性质, 还须了解n步转 移概率,初始概率和绝对概率的概念. 定义4.4 称条件概率pij(n)=PXm+n=j|Xm=i,i,jI,m0,n1为马尔可夫链Xn,nT的n步转移概率,并称P(n)=(pij(n)为马尔可夫链的n步转移矩阵,其中pij(n)0, pij(n)=,马尔可夫链的概念及转移概率,1,即P(n)也是随机矩阵.当n=1时,pij(1)=pij,此时一步转移矩阵P(1)=P. 此外规 定pij(0)= (P(0)是单位矩阵). 例4.1 (一维随机游动)设一醉汉Q(即一随机游动的质点), 在如右
7、上图所示的 直线点集I=1,2,3,4,5作随机游动,并且仅仅在1秒,2秒 等时刻发生游动.游动的概率规则是:如果Q现在位于点 i(1i5), 则下一时刻各以1/3的概率向左或向右移动 一格,或以1/3的概率留在原处; 如果Q现在位于点1(或5) 上,则下一时刻就以概率1移动到点2(或4)上.点1与5称为 反射壁.并称上述这种游动为带有两个反射壁的随机游动.若以Xn表示时刻n时Q的位置, 不同的位置就是Xn的不同,0,ij,1,i=j .,1,2,3,4,5,马尔可夫链的概念及转移概率,状态,则Xn,n=0,1,2,是一随机过程, 状态空间就是I, 而且当Xn=i,iI为已知时,Xn+1所处的
8、状态的概率分布只 与Xn=i有关,而与Q在时刻n以前,如何到达i是完全无关的, 所以Xn,n=0,1,2,是一马氏链,而且还是齐次的.这一 齐次马氏链的一步转移概率和一步转移概率矩阵分别为:pij=PXn+1=j|Xn=i=P= .,1/3,j=i-1,i,i+1,1i5,1,i=1,j=2或i=5,j=4,0,|j-i|2.,1 2 3 4 5,1 0 1 0 0 0 2 1/3 1/3 1/3 0 0 3 0 1/3 1/3 1/3 0 4 0 0 1/3 1/3 1/3 5 0 0 0 1 0,改变游动的概率规则,可以 得到不同方式的随机游动和相 应的马氏链.如当把点1(及5)改 为吸收
9、壁,Q一旦到达点1(5),则 将永远留在点1(5)上.此时相应,马尔可夫链的概念及转移概率,链的转移概率矩阵只须在上述矩阵P中将第一行改为(1,0, 0,0,0),第五行改为(0,0,0,0,1)即可. 例4.2 (排队模型)设服务系统,由一个服务员和只可能容纳两个人的等候 室组成,见右下图.服务规则是: 先到先服务,后来者需在 等候室依次排队. 假定一个需 要服务的顾客到达系统时, 发 现系统内已有3个顾客(一个正 在接受服务, 两个在等候室排 队),则该顾客即离去. 设时间间隔t内将有一个顾客进 入系统的概率为q,有一原来被服务的顾客离开系统(即服 务完毕)的概率为p.又设当t充分小时,在
10、这时间间隔内,等候室,服务台,系统,离去者,随机 到达 者,马尔可夫链的概念及转移概率,多于一个顾客进入或离开系统实际上是不可能的.再设有 无顾客来到与服务是否完毕是相互独立的. 如何用马氏链描述这一服务系统?设定XnX(nt),表示时间nt时系统内的顾客数,即 系统的状态.则Xn,n=0,1,2,是一随机过程,状态空间 I=0,1,2,3.由于当Xn=i,iI为已知时,Xn+1所处的状态 的概率分布只与Xn=i有关,而与时间nt以前所处的状态 无关,所以该随机过程是一个齐次马氏链. 怎样计算此马氏链的一步转移概率? 记p00为:在系统内没有顾客的条件下,经t后仍无顾客的 概率(显然p00是条
11、件概率,以下与此同), p00=1-q.,马尔可夫链的概念及转移概率,p01为:在系统内没有顾客的条件下,经t后有一顾客进 入系统的概率, p01=q.p10为:系统内恰有一顾客正在接受服务的条件下,经t 后系统内无人进入的概率, 它等于在t间隔内顾客因服 务完毕而离去,且无人进入系统的概率, p10=p(1-q). p11为:系统内恰有一顾客的条件下,在t间隔内, 他因 服务完毕而离去,而另一顾客进入系统, 或者正在接受服 务的顾客将继续要求服务,且无人进入系统的概率,p11=pq +(1-p)(1-q).p12为:正在接受服务的顾客将继续要求服务, 且另一顾 客进入系统的概率, p12=q
12、(1-p).p13为:正在接受服务的顾客继续要求服务,且在t间隔,马尔可夫链的概念及转移概率,内有两个顾客进入系统的概率.由假设这种情况是不可能 发生的, p13=0.考虑到系统内有一顾客正在接受服务,有一顾客正在排 队,在t间隔内顾客因服务完毕离去,但再无顾客进入;以 及系统内有一顾客正在接受服务,有两顾客正在排队, 在 t间隔内顾客因服务完毕离去, 但再无顾客进入的概率 相等,故有p21=p32=p(1-q). 又系统内有两顾客,其中一人正在接受服务,在t间隔 内,他因服务完毕而离去,而另一顾客进入系统,或者正在 接受服务的顾客将继续要求服务,且再无人进入系统的概 率为:p22=pq+(1
13、-p)(1-q).类似地,系统内有两顾客, 正在接受服务的顾客将继续,马尔可夫链的概念及转移概率,要求服务,且另一顾客进入系统的概率为:p23=q(1-p).而且,显然有:当|i-j|2时,pij=0.p33为:系统内有三位顾客, 或者一人将离去另一人将进 入系统; 或者无人离开的概率, p33=pq+(1-p). 于是得该马氏链的一步转移概率矩阵:P= .在实际问题中,一步转移概率矩阵通常可通过统计试验 确定.下面是一实例. 例4.3 某计算机机房的一台计算机经常出故障,研究者每,0 1 2 3,(1-q) q 0 0p(1-q) pq+(1-p)(1-q) q(1-p) 00 p(1-q)
14、 pq+(1-p)(1-q) q(1-p)0 0 p(1-q) pq+(1-p),0 1 2 3,马尔可夫链的概念及转移概率,隔15分钟观察一次计算机的运行状态,收集了24小时的数 据(共做97次观察).用1表示正常状态,0表示不正常状态, 所得的数据序列为:设Xn为第n(n=1,2,97)次观测的计算机状态,可以认 为它是一个齐次马氏链,状态空间I=0,1.96次状态转移 的情况是: 00,8次;01,18次;10,18次;11,52次. 因此,一步转移概率可用频率近似地表示为:p00=PXn+1=0|Xn=08/(8+18)=4/13, p01=PXn+1=1|Xn=018/(8+18)=9/13,p10=PXn+1=0|Xn=118/(18+52)=9/35,p11=PXn+1=1|Xn=152/(18+52)=26/35.,
