应用数学基础 随机过程-2.ppt

1、马尔可夫过程,硕士研究生学位课程应用数学基础,主讲教师 段禅伦 2008年秋季学期,(演示文稿),(Markoff process),第四章 马尔可夫链,马尔可夫链是最简明的马尔可夫过程, 它是状态、时 间都是离散量的马尔可夫过程. 马尔可夫过程是随机过程中历史最悠久且充满活力的 一类随机过程.自20世纪初俄罗斯数学家A.A.MapkoB等人 开始研究马尔可夫过程以来,可以说久盛不衰. 它有极为 深厚的理论基础,如拓扑学、函数论、泛函分析、近世代 数和几何学; 又有广泛的应用空间,如近代物理、随机分 形、公共事业中的服务系统、电子信息、计算机技术等. 自然界很多现象遵从这样的演变规则:由时刻t

2、0系统或 过程所处的状态(现在)可以决定系统或过程在时刻tt0 所处的状态(将来),而无需借助于t0以前系统或过程所处 状态(过去)的历史资料. 如微分方程初值问题即属于此.,马尔可夫链的概念及转移概率,4.1 马尔可夫链的概念及转移概率 1.马尔可夫链的定义 设随机过程Xn,nT的参数集T=0,1,2,Xn可能 取值的全体组成的状态空间为I=i1,i2,i3,. 定义4.1 设有随机过程Xn,nT,若对于任意的整数n T和任意的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时,表示马尔可夫链具有平稳,马尔可夫链的

5、概念及转移概率,转移概率. 定义4.3 若对任意的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)是单位矩阵). 例

7、4.1 (一维随机游动) 设一醉汉Q(即一随机游动的质点), 在如右上图所示的 直线点集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,是一随机

8、过程, 状态空间就是I, 而且当Xn=i,iI为已知时,Xn+1所处的状态的概率分布只 与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,改变游动的概率规则,

9、可以 得到不同方式的随机游动和相 应的马氏链.如当把点1(及5)改 为吸收壁,Q一旦到达点1(5),则 将永远留在点1(5)上.此时相应,马尔可夫链的概念及转移概率,链的转移概率矩阵只须在上述矩阵P中将第一行改为(1,0, 0,0,0),第五行改为(0,0,0,0,1)即可. 例4.2 (排队模型) 设服务系统,由一个服务员和只可能容纳两个人的等候 室组成,见右下图.服务规则是: 先到先服务,后来者需在 等候室依次排队. 假定一个需 要服务的顾客到达系统时, 发 现系统内已有3个顾客(一个正 在接受服务, 两个在等候室排 队),则该顾客即离去. 设时间间隔t内将有一个顾客进 入系统的概率为q,

10、有一原来被服务的顾客离开系统(即服 务完毕)的概率为p.又设当t充分小时,在这时间间隔内,等候室,服务台,系统,离去者,随机 到达 者,马尔可夫链的概念及转移概率,多于一个顾客进入或离开系统实际上是不可能的.再设有 无顾客来到与服务是否完毕是相互独立的. 如何用马氏链描述这一服务系统? 设定XnX(nt),表示时间nt时系统内的顾客数,即 系统的状态.则Xn,n=0,1,2,是一随机过程,状态空间 I=0,1,2,3.由于当Xn=i,iI为已知时,Xn+1所处的状态 的概率分布只与Xn=i有关,而与时间nt以前所处的状态 无关,所以该随机过程是一个齐次马氏链. 怎样计算此马氏链的一步转移概率?

11、 记 p00为:在系统内没有顾客的条件下,经t后仍无顾客的 概率(显然p00是条件概率,以下与此同), p00=1-q.,马尔可夫链的概念及转移概率,p01为:在系统内没有顾客的条件下,经t后有一顾客进 入系统的概率, p01=q. p10为:系统内恰有一顾客正在接受服务的条件下,经t 后系统内无人进入的概率, 它等于在t间隔内顾客因服 务完毕而离去,且无人进入系统的概率, p10=p(1-q). p11为:系统内恰有一顾客的条件下,在t间隔内, 他因 服务完毕而离去,而另一顾客进入系统, 或者正在接受服 务的顾客将继续要求服务,且无人进入系统的概率,p11=pq +(1-p)(1-q). p

12、12为:正在接受服务的顾客将继续要求服务, 且另一顾 客进入系统的概率, p12=q(1-p). p13为:正在接受服务的顾客继续要求服务,且在t间隔,马尔可夫链的概念及转移概率,内有两个顾客进入系统的概率.由假设这种情况是不可能 发生的, p13=0. 考虑到系统内有一顾客正在接受服务,有一顾客正在排 队,在t间隔内顾客因服务完毕离去,但再无顾客进入;以 及系统内有一顾客正在接受服务,有两顾客正在排队, 在 t间隔内顾客因服务完毕离去, 但再无顾客进入的概率 相等,故有p21=p32=p(1-q). 又系统内有两顾客,其中一人正在接受服务,在t间隔 内,他因服务完毕而离去,而另一顾客进入系统

13、,或者正在 接受服务的顾客将继续要求服务,且再无人进入系统的概 率为:p22=pq+(1-p)(1-q). 类似地,系统内有两顾客, 正在接受服务的顾客将继续,马尔可夫链的概念及转移概率,要求服务,且另一顾客进入系统的概率为:p23=q(1-p). 而且,显然有:当|i-j|2时,pij=0. p33为:系统内有三位顾客, 或者一人将离去另一人将进 入系统; 或者无人离开的概率, p33=pq+(1-p). 于是得该马氏链的一步转移概率矩阵: P= . 在实际问题中,一步转移概率矩阵通常可通过统计试验 确定.下面是一实例. 例4.3 某计算机机房的一台计算机经常出故障,研究者每,0 1 2 3

14、,(1-q) q 0 0 p(1-q) pq+(1-p)(1-q) q(1-p) 0 0 p(1-q) 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

15、=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.,1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111.,0 1 0 4/13 9/13 1 9/35 26/35,P=,马尔可夫链的概念及转移概率,定理4.1 设Xn,nT是马尔可夫链,则对任意整数n0

16、, 0ln和i,jI,n步转移概率pij(n)具有下列性质: (1) pij(n)= pik(l )pkj(n-l ); (2) pij(n)= ; (3) P(n)=PP(n-1); (4) P(n)=Pn. 证明:(1)利用条件概率公式及马尔可夫性,有 pij(n)=PXm+n=j|Xm=i= = ,马尔可夫链的概念及转移概率,= PXm+n=j|Xm+l =kPXm+l =k|Xm =i = pkj(n-l )(m+l )pik(l )(m)= pik(l )pkj(n-l ). (2)在(1)中,令l =1,k=k1,得 pij(n)= ; 这是一个递推公式,递推可得 pij(n)=

17、. (3)在(1)中,令l =1,利用矩阵乘法可证. (4)由(3),利用归纳法可证. 定理4.1中的(1)式,称切普曼-柯尔莫哥洛夫(Chapman-,马尔可夫链的概念及转移概率,Kolmogorov)方程, 这一方程一般简称为C-K方程,它在 马尔可夫链的转移概率计算中起着重要的作用. 而(2) 式说明n步转移概率完全由一步转移概率决定.(4)式说 明齐次马尔可夫链的n步转移概率矩阵是一步转移概率 矩阵的n次方. 定义4.5 设Xn,nT是马尔可夫链,称 pj=PX0=j和pj(n)=PXn=j, jI 为Xn,nT的初始概率和绝对概率,并分别称 pj,jI和pj(n),jI 为Xn,nT

18、的初始分布和绝对分布,简记为 pj和pj(n). 称概率向量PT(n)=(p1(n),p2(n),)(n0)为n时刻的,马尔可夫链的概念及转移概率,绝对概率向量, 而称 PT(0)=(p1,p2,) 为初始概率向量. 例4.4(接例4.3) 若计算机在前一段(15分钟)的状态为0, 问从本时段起,此计算机能连续正常工作一小时(4个时 段)的概率是多少? 解:由题意,前一时段的状态为0,就是初始分布p0(0)=PX0 =0=1. 于是计算机能正常工作4个时段的概率为: PX0=0,X1=1,X2=1,X3=1,X4=1 =p0(0)p01(1)p11(1)p11(1)p11(1) = 0.28.

19、,马尔可夫链的概念及转移概率,关于切普曼-柯莫哥洛夫(Chapman-Kolmogorov)方程 设Xn,nT是一齐次马氏链,则对任意的i,jI及T 中n0,0ln有 Pij(n)= Pik(l )Pkj(n-l ). 这一方程基于这样的事实:“从某时刻所处的状态i(即X =i)出发, 经过时段n转移到状态j(即X=j)”这一事件可分 解成“从X=i出发, 先经时段l 转移到中间状k(kI),再从 k经时段转n-l 移到状态j”.如下图所示: 后一阶段的状态转移与前一阶段的状 态转移独立, 所以两个阶段的转移概率 是相乘的关系. 但经过l 步到达的状态 k不受任何限制,因而要对全部的k求和.,

20、t,o,i,k,j,:,l,n- l,n,马尔可夫链的概念及转移概率,例4.5 设Xn,n0是具有3个状态0,1,2的齐次马氏链,一 步转移概率矩阵如右所示: 初始分布pi(0)=PX0=i=1/3,i=0,1,2. 试求(1) PX0=0,X2=1; (2) PX2=1. 解: 先求出二步转移概率矩阵(如右下): 于是有 (1) PX0=0,X2=1 =PX0=0PX2=1|X0=0 =p0(0)p01(2)=(1/3)(5/16)=5/48; (2) p1(2)=PX2=1 =p0(0)p01(2)+p1(0)p11(2)+p2(0)p21(2) =(1/3)(5/16+1/2+9/16)

21、=11/24.,0 1 2 0 0 ,0 1 2,0 1 2 5/8 5/16 1/16 5/16 1/2 3/16 3/16 9/16 1/4,P2=,0 1 2,马尔可夫链的概念及转移概率,定理4.2 设Xn,nT为马尔可夫链,则对任意jI和n 1,绝对概率pj(n)具有下列性质: (1) pj(n)= pipij(n); (2) pj(n)= pi(n-1)pij ; (3) PT(n)=PT(0)P(n); (4) PT(n)=PT(n-1)P. 证明:(1) pj(n)=PXn=j= PX0=i,Xn=j = PX0=i,Xn=j|X0=iPX0=i= pipij(n). (2) p

22、j(n)=PXn=j= PXn=j,Xn-1=i,马尔可夫链的概念及转移概率,= PXn=j|Xn-1=iPXn-1=i = pi(n-1)pij. (3)与(4)式是(1)与(2)式的矩阵形式,显然成立. 定理4.3 设Xn,nT为马尔可夫链,则对任意i1,in I和n1,有 PX1=i1,Xn=in= . 证明: 由条件概率公式及马氏性,有 PX1=i1,Xn=in=P X0=i,X1=i1,Xn=in = PX0=i,X1=i1,Xn=in= PX0=iPX1=i1| X0=iPXn=in|X0=i,X1=i1,Xn-1=in-1,马尔可夫链的概念及转移概率,= PX0=iPX1=i1|

23、X0=iPXn=in|Xn-1=in-1 = . 定理4.2表明, 绝对概率pj(n)也具有类似于n步转移概 率的性质.定理4.3则进一步说明,马尔可夫链的有限维 分布完全由它的初始概率和一步转移概率所决定.因此 只要知道初始概率和一步转移概率,就可以描述马尔可 夫链的统计特性. 3.马尔可夫链的应用举例 在讨论马尔可夫链的应用之前, 再对定理4.3的马尔可 夫过程的概率意义,做一必要的说明.,马尔可夫链的概念及转移概率,对于齐次马尔可夫链Xn,nT, 其有限维分布函数由 它的初始分布和一步转移概率惟一确定. 因为: PX1=i1,X2=i2,Xn=in =P X0=i0,X1=i1,X2=i

24、2,Xn=in = PX0=i0,X1=i1,X2=i2,Xn=in = PX0=i0PX1=i1|X0=i0PXn=in|X0=i0,Xn-1=in-1 = PX0=i0PX1=i1|X0=i0PXn=in|Xn-1=in-1 = . 反之,若一个随机变量序列Xn,nT的有限维分布由上 式给出,其中pi,iI为一概率分布, pij为转移概率,则 Xn,nT是一马尔可夫链(即具有马尔可夫性), (pij)是 其转移概率矩阵, pi是其初始分布.,马尔可夫链的应用举例,例4.6 (无限制随机游动) 设质点在数轴上移动,每次移动一格, 向右移动的概率 为p,向左移动的概率q=1-p(这种运动称无限

25、制随机游动). 以Xn表示时刻n质点所处的位置, 则Xn,nT是一个齐次 马尔可夫链.试写出Xn,nT的一步和k步转移概率. 解:Xn,nT的状态空间I=0,1,2,其一步转移 概率矩阵为: 设在第k步转移中向右移了x 步,向左移了y步,且经过k步转 移状态从i进入j,则 ,从而x= ,y= .由于x,y只能,P=, q 0 p 0 0 q 0 p ,x+y=k x-y=j-i,马尔可夫链的应用举例,取整数,所以k(j-i)必为偶数. 考虑到在k步中哪x步 向右,哪y步向左是任意的,选取的方法有 种,故有 pij(k)= . 例4.7 (赌徒输光问题) 两赌徒甲、乙进行一系列赌博.赌徒甲有a元

26、,赌徒乙有 b元,每赌一局输者给赢者1元,没有和局,直到两人中有 一人输光为止. 设在每一局中,甲赢的概率为p,输的概 率为q=1-p,求甲输光的概率. 解: 与例4.1带有两个反射壁的一维随机游动相比, 这个 问题实质上是带有两个吸收壁的随机游动,其状态空间 I=0,1,2,c(c=a+b). 所以问题是要求质点从a点出,pxqy, k+(j-i)为偶数 0, k+(j-i)为奇数,马尔可夫链的应用举例,发到达0状态先于到达c状态的概率. 解: 设ui表示甲从状态i出发转移到状态0的概率,我们的 任务是计算ua. 由于0和c是 吸收状态,故u0=1, uc=0.由 条件概率公式:ui=pui

27、+1+qui-1,i=1,2,c-1.(此式的含 义是:甲从有a元开始赌博到输光的概率等于“他接下去 赢了一局(概率为p),处于状态i+1后再输光”; 和“他接 下去输了一局(概率为q), 处于状态i-1后再输光”这两 个事件的和事件的概率.) 由于p+q=1,所以ui=pui+1+qui-1,i=1,2,c-1实质上 是一个差分方程: ui+1-ui=r(ui-ui-1),i=1,2,c-1.,o,a-1,a,a+1,a+b,q,p,马尔可夫链的应用举例,其中r=q/p,其边界条件为u0=1,uc=0. 如果r=1,即p=q=1/2, 此时ui+1-ui=ui-ui-1,令i=1,2, ,c

28、-1及u1=u0+,则有 u2=u1+=u0+2, u3=u2+=u0+3, ui=ui-1+=u0+i, uc=uc-1+=u0+c. 将u0=1,uc=0代入最后一式,得参数=-1/c. 于是有 ui=1-i/c, i=1,2,c-1. 令i=a,求得甲输光的概率: ua=1- a/c= . 此结果,马尔可夫链的应用举例,表明,在p=q的情况下(即甲、乙每局比赛中输赢等可能) 甲输光的概率与乙的赌本b成正比, 换言之,赌本小(对 方赌本大)者输光的可能性大. 由于甲、乙的地位是对称的,故乙输光的概率为 ub= . ua+ub=1,表明甲、乙中必有一人要输光,赌博迟早要结束. 如果r1,即p

29、q的情况,由ui+1-ui=r(ui-ui-1),i=1, 2,c-1式得 uc-uk= r(ui-ui-1)= ri(u1-u0) =(u1-1) .,马尔可夫链的应用举例,令k=0,由于uc=0,有: 1=(1-u1) ,即(1-u1)= . 代入uc-uk=(u1-1) 得 uk= ,k=1,2,c-1. 令k=a,得甲输光的概率: ua= . 由对称性,乙输光的概率为: ub= ,其中r1=p/q. 由于ua+ub=1,因而在r1时,即pq时, 两个人中也总 有一个人要输光.,马尔可夫链的应用举例,例4.8 (天气预报问题) 设昨日、今日都下雨,明日有雨的概率为0.7;昨日无雨, 今日

30、有雨,明日有雨的概率为0.5;昨日有雨,今日无雨,明 日有雨的概率为0.4;昨日、今日都无雨,明日有雨的概率 为0.2. 若星期一、星期二均下雨,求星期四下雨的概率. 解: 设昨日、今日连续两天有雨称为状态0(RR), 昨日无 雨、今日有雨称为状态1(NR), 昨日有雨、今日无雨称 为状态2(RN), 昨日、今日无雨称为状态3(NN),于是天 气预报模型可看作一个四状态的马尔可夫链,其转移概 率为(解述中的R、N分别代表有雨和无雨): p00=PR今R明|R昨R今=P连续三天有雨 =R明|R昨R今=0.7,马尔可夫链的应用举例,p01=PN今R明|R昨R今=0(不可能事件), p02=PR今N

31、明|R昨R今=PN明|R昨R今=1-0.7=0.3, p03=PN今N明|R昨R今=0(不可能事件); 类似地,有: p10=0.5, p11=0, p12=0.5, p13=0; p20=0, p21=0.4, p22=0, p23=0.6; p30=0, p31=0.2, p32=0, p33=0.8. 并得该问题的一步转移概率矩阵: P= = ;,p00 p01 p02 p03 p10 p11 p12 p03 p20 p21 p22 p23 p30 p31 p32 p33,0.7 0 0.3 0 0.5 0 0.5 0 0 0.4 0 0.6 0 0.2 0 0.8,马尔可夫链的应用举例

32、,和两步转移概率矩阵: P(2)=PP= . 星期四下雨,意味着过程所处的状态为0(RR;RR)或1(RR, NR),故星期一、星期二连续下雨,星期四下雨的概率为 p=p00(2)+p01(2)=0.49+0.12=0.61. 例4.9 在例4.1中,设质点在线段1,4上作具有一个吸收 壁1和一个反射壁4的随机运动, 且假设它只能在时刻n T发生移动,若以Xn表示质点在时刻n所处的位置, 则 Xn,nT是一个齐次马尔可夫过程, 其转移概率矩阵,0.49 0.12 0.21 0.18 0.35 0.20 0.15 0.30 0.20 0.12 0.20 0.48 0.10 0.16 0.10 0

33、.64,马尔可夫链的应用举例,为: P= 各状态之间的转移关系及相应的转移概率如上图所示. 例4.10 (生灭链) 观察某种生物群体,以Xn表示在时刻n群体的数目,设为 i个数量单位, 如在时刻n+1增生到i+1个数量单位的概 率为bi,减少到i-1个数量单位的概率为ai,保持不变的 概率为ri=1-(ai+bi), 则Xn,n0为齐次马尔可夫链, I=0,1,2,其转移概率为: pij= 称此马氏链为生灭链.,1 0 0 0 1/3 1/3 1/3 0 0 1/3 1/3 1/3 0 0 1 0,1,2,3,4,1/3,1/3,1/3,1,1/3,1,1/3,1/3,bi, j=i+1, r

34、i, i=j, ai, j=i-1,(a0=0).,马尔可夫链的状态分类,4.2 马尔可夫链的状态分类 1.状态的分类 假设Xn,n0是齐次马尔可夫链,其状态空间I=0,1, 2,转移概率是pij,i,jI,初始分布为pj,jI.如 何依概率性质对状态进行分类呢? 例4.11 设马尔可夫链的状态空间I=1,2,9, 状态间 的转移概率如右图所示. 由图可见:自状态1出发, 再返回状态1的可能步数 (时刻)为:T=4,6,8,10, ,T的最大公约数为2,但2 T,即由1出发经2步不能 返回1. 这个2,即状态1的周期.,1,3,7,8,9,2,6,5,4,1,1,1,1,1,1,1,1/3,1

35、,2/3,马尔可夫链的状态分类,定义4.6 若集合n|n1,pii(n)0非空, 则称该集合的 最大公约数d=d(i)=GCDn|n1,pii(n)0为状态i的周 期. 若d1,则称i是周期的;若d=1,则称i为非周期的. 由定义4.6知,如果i有周期d,则对一切非零的 n0(mod d) 都有pii(n)=0. 但这并不是说,对任意的nd,有 pii(nd)0. 这在例4.11中已经看到: 状态1的周期d=2,而p11(2)=0. 但是,以下结论成立: 引理4.1 若状态i的周期为d,则存在正整数M,对一切nM, 有:pii(nd)0. 证明: 设n|n1,pii(n)0=n1,n2,令,马

36、尔可夫链的状态分类,tk=GCDn1,n2,nk 则t1t2d1,故存在正整数N,使得tN=tN+1=d, 因此,d=GCDn1,n2,nN.从而存在正整数M,对一切n M,成立 nd= knk, k为正整数. 于是,当nM时 pii(nd)= = 0. 在例4.11中,n|pii(n)0=4,6,8,10,t1t2=d= 2,N=2; nd=2n=41+62即n=21+32,对1与2的各 种正整数组合,可以验证:当M=7,n7时,恒有p11(2n)0.,马尔可夫链的状态分类,例4.12 设I=1,2,3,4, 转移概率如图: 考虑图中的状态2和3:易见状态2与3有 相同的周期d=2. 但是,

37、从状态3出发,经2步必定返回到 3;而状态2则不然:当2转移到3后,便再也不能返回到2. 为区别例4.12中的状态2和3,需要引入概念常返性. 首达概率 记fij(n)=PXm+vj,1vn-1,Xm+n=j|Xm=i,n1且 fij(0)=0. 表示质点由i出发,经n步首次到达j的概率,称首达概率. 显然,由马氏性和齐次性知,等式右端与m无关, 即首 达概率也可以这样定义(由i出发在时刻n首次转移到j): fij(n)=PXn=j,Xkj,k=1,2,n-1|X0=i,fij(0)=0.,1,2,3,4,1,1,1,1/2,1/2,马尔可夫链的状态分类,记fij= fij(n),表示质点由i

38、出发迟早转移到j的概率. 定义4.7 称状态i为常返的,如果fii=1; 称状态i为非常返 (或滑过)的,如果fii1. 可见,若i是非常返态,则由i出发将以正概率1-fii永远 不再返回到i; 若i是常返的,则上述现象不会发生. 对 常返态i,fii(n),n1构成一概率分布.该分布的期望 值i= nfii(n),表示由i出发再返回到i的平均返回时 间. 定义4.8 若i,则称常返态i为正常返的; 若i=, 则称常返态i为零常返的; 非周期的正常返态称为遍历 状态. 对任意正整数n,首达概率与n步转移概率有下述关系:,马尔可夫链的状态分类,定理4.4 对任意状态i,j及1n有 pij(n)=

39、 fij(k)pjj(n-k)= fij(n-k)pjj(k). 证明: pij(n)=PXn=j|X0=i = PXvj,1vk-1,Xk=j,Xn=j|X0=i(k为首达) = PXn=j|X0=i,Xvj,1vk-1,Xk=jPXvj, 1vk-1,Xk=j|X0=i = pjj(n-k)fij(k)= fij(k)pjj(n-k). C-K方程及定理4.4中等式是马氏链的关键公式,它们可 以把pii(n)分解成较低步的转移概率之和的形式.,马尔可夫链的状态分类,例4.13 设I=1,2,3,4,其一步转移概率 矩阵如右所示. 试对其状态进行分类, 确定哪些状态是常返态,并确定其周期.

40、解: 状态传递图为: 从图中易见,对一切n1,f44(n)=0, 即 f44=01. 因而知状态4是非常返的. 又,f33(1)=2/3且当n2时,f33(n)=0.所以f33=2/31.从 而知状态3也是非常返态. 由f11=f11(1)+f11(2)=1/2+1/2=1(P2的(1,1)=1/2); 及 f22=f22(1)+f22(2)+=0+1/2+1/22+=(1/2)/(1-1/2)=1 知,状态1和状态2是常返态. 从1=11/2+21/2=3/2+,2=10+21/2+31/22+,P=,1/2 1/2 0 0 1 0 0 0 0 1/3 2/3 0 1/2 0 1/2 0,1

41、,2,4,3,1,1/2,1/2,1/2,1/2,1/3,2/3,马尔可夫链的状态分类,=3+,可见常返态1和2是正常返态;而且由于其周期 都为1因而是非周期的,所以状态1和状态2还是遍历态. 为什么2=3? 因为:当记 f(n)=21/2+31/22+41/23+51/24+61/25+n1/2n-1, g(n)=1/2+1/22+1/23+1/24+1/25+1/2n-1时, 有 f(n)-g(n)=1/2+(1/2)f(n)-n/2n-1. 即f(n)=1+2g(n)-n/2n-1并当n+时,g(n)=1,f(n)=3. 由定理4.4可以推出状态周期的等价定义: 引理4.2 GCDn|n

42、1,pii(n)0=GCDn|n1,fii(n)0. 证明: 令 d=GCDn|n1,pii(n)0, t=GCDn|n1,fii(n)0 由定义,容易知pii(n)fii(n), 故n|n1,pii(n)0,马尔可夫链的状态分类,n|n1,fii(n)0, 从而1dt. 若t=1,则d=t=1.若t1,需要证明dt.为此只需证明t 是n|pii(n)0的公约数即可. 换言之,如若n0(mod t),则必有pii(n)=0. 由t的定义 及定理4.4中公式知,对一切nt,都有 pii(n)= fij(k)pii(n-k)=0(fij(k)=0). 今假设当n=mt+r,m=0,1,2,N-1时

43、,pii(n)=0, 则由定 理4.4、以及注意到如若n0(mod t),则fii(n)=0,我们 有: pii(Nt+r)=fii(t)pii(N-1)t+r+fii(2t)pii(N-2)t+r+ fii(Nt)pii(r)=0, 由归纳法,即知dt. 综上所述,证得d=t.,马尔可夫链的状态分类,例4.14 设马尔可夫链的状态空间I=1,2,3,其转移概率 矩阵如右所示.求从状态1出发,经n步 转移到达各状态的概率. 解: 使用fij(n)定义式计算,比较简单. 特别通过状态转移图进行计算,显得 直接简明. 运用归纳法,我们得: f12(n)= 同理可得: f13(n)= f11(n)=

44、,P=,0 P1 q1 q2 0 p2 p3 q3 0,1,2,3,(q1p3)m-1q1q3,n=2m,m1,(q1p3)mp1, n=2m+1,m0.,(p1q2)mp1p2,n=2m,m1,(p1q2)mq1,n=2m+1,m0.,p1(p2q3)m-1q2+q1(q3p2)m-1p3,n=2m,m1,p1(p2q3)m-1p2p3+q1(q3p2)m-1q3q2,n=2m+1,m1.,0, n=1,q1,P1,q2,p2,p3,q3,对“状态的分类”的小结,齐次马氏链的状态分类 1.称d=d(i)=GCDn:n1,pii(n)0为状态i的周期. (1) d1,称状态i为周期的; (2)

45、 d=1,称状态i为非周期的. 事实. (1)若i有周期d,则对一切非零的n0(mod d)都 有pii(n)=0, 但并非对任意nd,有pii(nd)0; (2)若i的周期为d,则存在正整数M,对一切nM, 有pii(nd)0. 首达概率 fij(n)=PXn=j,Xkj,k=1,2,n-1|X0=i,fij(0)=0. 及 过程由i出发,经有限步迟早到达j的概率 fij= fij(n).,对“状态的分类”的小结,2.当fii=1时,称状态i是常返的;当fii1时,称状态i是 非常返的. 事实. (1)若i是非常返态,则由i出发将以正概率1-fii 永远不再返回到i;对常返态此现象不会发生;

46、 (2)对常返态i,fii(n),n1构成一概率分布,该 分布的期望值i= nfii(n),表示过程由i出 发再返回到i的平均返回时间. 3.设状态i为常返态,若i,则称常返态i是正常返 的;若i=,则称常返态i是零常返的; 非周期的正 常返态称为遍历状态. 事实.(1)对任意i,jI,n1有pij(n)= fij(k)pjj(n-k). (2)GCDn|n1,pii(n)0=GCDn|n1,fii(n)0.,对“状态的分类”的小结,非常返态 状态 零常返态 常返态 是周期的 正常返态 是非周期的 遍历态 为什么要对马尔可夫链的状态进行分类? 对齐次马氏链代表的系统进行研究时要讨论两个问题:

47、(1)在某一固定时刻n时的概率特性即求n步转移概率或 绝对概率pj(n)=PXn=j(称瞬态分析); (2)当n后系统的概率特性, 即n时,pij(n)的极 限是否存在, 若存在又与状态的关系如何,极限概率能否 构成概率分布. 解决此类问题需要对状态(状态空间)进行分类(分解).,马尔可夫链的状态分类,2.常返性的判断及其性质 以下讨论如何用pij(n)来判别常返态和常返态的性质. 设an,n0是实数序列,考虑an,n0的母函数 A(s)= ansn. 显然,若an,n0有界,则对一切|s|1,A(s)收敛.进而 如果an,n0与bn,n0的母函数分别是A(s)和B(s), 且对一切|s|1收

48、敛,则an,n0与bn,n0的卷积 Cn= anbn-k,n=0,1,2, 的母函数C(s)=A(s)B(s). 定理4.5 状态i常返的充要条件是 pii(n)=.,马尔可夫链的状态分类,如i非常返,则 pii(n)= . 证明: 规定 pii(0)=1, fii(0)=0. 由定理4.4知 pii(n)= pii(k)fii(n-k),n1. 两边同乘sn,并对n1求和.记pii(n)与fii(n)的母函 数分别为P(s)和F(s),与段比较,得 P(s)-1=P(s)F(s). 注意到0s1时, F(s)fii1. 因此 P(s)= ,0s1.,马尔可夫链的状态分类,考虑到对任意正整数N

49、都有 pii(n)snP(s) pii(n),0s1 且当s1时P(s)不减,故在上式中可先取s1,再令N ,便有 lim P(s)= pii(n). 同理可得 lim F(s)= fii(n)=fii. 于是,在式中,令s1,即有定理4.5的结论(对常返和 非常返). 定理4.5表示,当i常返时,返回i的次数是无限多次; 当 i非常返时,返回i的次数只能有限多次. 为了进一步深化刻画该特性,以下给出超限概率的概念.,s1,s1,马尔可夫链的状态分类,超限概率 gij=P有无限多个n使Xn=j|X0=i Pi有无限多个n使Xn=j =Pi (Xn=j). 引理4.3 对任意状态i,有 gij=

50、 证明: 令Ak=e|至少有k个n使Xn(e)=j,易见Ak+1 Ak. 并 有 lim Pi(Ak)=gij. 另一方面Pi(Ak+1)=Pi (Xvj,0vm,Xm=j且至少有 k个n使Xm+n=j)= Pi(Xvj,0vm,Xm=j)Pj(至少有,fij, 若j是常返态, 0, 若j是非常返态.,k,马尔可夫链的状态分类,k个n使Xn=j)= fij(m)Pj(Ak)=fijPj(Ak). 由i的任意性, 反复迭代式并注意到Pj(A1)=fjj, 有 Pi(Ak+1)=fijfjj Pj(Ak-1)=fij(fjj )k. 令k,由式及式,便有 gij= 由以上引理4.3,得: 定理4.

51、6 状态i常返,当且仅当gii=1; 若状态i非常返,则 gii=0. 对于常返态i,如何判别它是遍历的或零常返的呢? 定理4.7 设i常返且有周期d,则lim pij(nd)= ,其中i,fij, 若fjj=1, 0, 若fjj1.,n,马尔可夫链的状态分类,为i的平均返回时间.当i 为时, =0. 推论 设i常返,则 (1)i零常返 lim pii(n)=0; (2)i遍历 lim pii(n)= 0. 证明:(1)若i零常返,由定理4.7知lim pii(nd)=0.但当n 0(mod d)时,pii(n)=0.故lim pii(n)=0.反之若lim pii(n) =0,而i是正常返,

52、则由定理4.7得lim pii(nd)0. 矛盾. (2)设lim pii(n)= 0,这说明i为正常返且lim pii(nd) = .与定理4.7比较得d=1.故i遍历. 反之,由定理4.7 即知.,n,n,n,n,n,n,n,n,定理证明参见毛用才,胡奇英 随机过程定理5.3.2,P112-113,马尔可夫链的状态分类,可达与互通 称状态i可达状态j,记为ij,如果存在n0使pij(n) 0; 称状态i与状态j互通,记为i j,如果ij且ji. 定理4.8 可达关系与互通关系都具有传递性,即 (1) 若ij,jk,则ik; (2) 若i j,j k,则i k. 证明: (1)设ij,则存在

53、s1,有pij(s)0;设jk,则存 在t1,有pjk(t)0. 由C-K方程 pik(s+t)= pil(s)pl k(t)pij(s)pjk(t)0. 注意到s+t1,故有ik. (2)将可达关系的证明,正向用一次,反向再用一次 就是对互通关系传递性的证明.,(因而互通关系是等价关系),马尔可夫链的状态分类,互通关系具有相同的类型 定理4.9 若i j,则 (1)i与j同为常返态或非常返态,若为常返态,则 它们同为正常返态或零常返态; (2)i与j有相同的周期. 证明:(1)设i j,则由可达定义知,存在l 1和n1,使有 pij(l )=0, pji(n)=0. 由C-K方程,知有 pi

54、i(l +m+n)pij(l )pjj(m)pji(n)=pjj(m), pjj(n+m+l)pji(n)pii(m)pij(l )=pii(m). 将以上两式的两边关于m从1到求和,得,马尔可夫链的状态分类,Pii(l +m+n) Pjj(m); Pjj(l +m+n) Pii(m). 可见, Pii(k)与Pjj(k)相互控制,所以它们同为无穷或同为有限.由定理4.5知,i,j同为常返或同为非常返. 对与两式的两边分别关于m取极限,又有 lim Pii(l +m+n)lim Pjj(m); lim Pjj(l +m+n)lim Pii(m). 可见,lim Pii(k)与lim Pjj(k

55、)同为零或同为正. 由定理 4.7的推论知,i,j同为零常返或同为正常返.,m,m,m,m,m,m,马尔可夫链的状态分类,(2)仍令pij(l )=0, pji(n)=0. 设i的周期为d,j的周期为t. 由(1)证中的式知,对 任一使pjj(m)0的m,必有pii(l +m+n)0,从而d除尽l +m+ n, 但 pii(l +n)pij(l )pji(n)=0. 所以d也能除尽l +n.于是d就可除尽m,此说dt.利用 式,类似可证dt. 因而得d=t. 例4.15 设马氏链Xn的状态空间I=0,1,2,转移概 率为p00=1/2,pi,i+1=1/2, pi0=1/2,iI. 考察状态0

56、的常返性、周期性和遍历性.,1,0,2,3,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,马尔可夫链的状态分类,解: 由题图知: f00(1)=1/2, f00(2)=(1/2)(1/2)=1/4, f00(3)=(1/2)(1/2)(1/2)=1/8, 一般,有 f00(n)=1/(2n). 故 f00= 1/(2n)=1, 0= n2-n. 可见0为正常 返状态; 由于f00(1)=1/20, 所以0是非周期的; 因 而是遍历的. 对其它状态i求fii(n)比较烦琐.但利用定理4.9,由i 0 即知i也是遍历的. 换言之对互通状态的识别,只需对最简单的状态进行判 断即可. 例1.16 设Xn为生灭链(例4.10),其中X0=1,ai0(i1),马尔可夫链的状态分类,bi0(i0).如果 =, 则Xn的所有状态都是常返的. 解: 实际上Xn的状态是互通的.所以我们只需验证状态 0是常返的. 定义:j=minn|Xn=j. 对固定的状态k,记 U(i)=Pi(0k)P(0k|X0=i), 0ik. 则由条件概率公式 U(i)=biU(i+1)+aiU(i-1)+riU(i), 0ik. 因为ri=1-ai-bi,故而上