随机过程Ch4_马尔可夫链

1、第四章 马尔可夫链14.1 马尔可夫链与转移概率 定义 设 X(t)，t T 为随机过程，若对任意正整数n及t1 t20，且条件分布PX(tn)xn|X(t1)=x1, X(tn-1)=xn-1= PX(tn) xn|X(tn-1)=xn-1，则称X(t)，t T 为马尔可夫过程。若t1,t2,tn-2表示过去，tn-1表示现在，tn表示将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与过去状态无关。24.1 马尔可夫链与转移概率常见马尔可夫过程通常有三类：(1)时间、状态都是离散的，称为马尔可夫链(2)时间连续、状态离散的，称为连续时间马尔可夫链(3)时间、状态都是连续的，称为

2、马尔可夫过程（时间离散、状态连续的马尔可夫过程，通常用泛函中二元函数的范数进行研究）3随机过程Xn，nT ，参数T=0, 1, 2, ,状态空间I=i0, i1, i2, 定义 若随机过程Xn，nT ，对任意nT和i0,i1,in+1 I，条件概率PXn+1=in+1|X0=i0,X1=i1,Xn=in = PXn+1=in+1|Xn=in， 则称Xn，nT 为马尔可夫链，简称马氏链。4.1 马尔可夫链与转移概率44.1 马尔可夫链与转移概率马尔可夫链的性质 PX0=i0, X1=i1, , Xn=in=PXn=in|X0=i0, X1=i1, , Xn-1=in-1 PX0=i0, X1=i

3、1, , Xn-1=in-1= PXn=in|Xn-1=in-1 PXn-1=in-1 |X0=i0,X1=i1,Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-2=PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-254.1 马尔可夫链与转移概率=PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX1=i1|X0=i0PX0=i0 马尔可夫链的统计特性完全由条件概率PXn+1=in+1|Xn=in确定。64.1 马尔可夫链与转移概率定义 称条件概率pij(n)= PXn+1=j|Xn

4、=i 为马尔可夫链Xn，nT 在时刻n的一步转移概率，简称转移概率，其中i,jI。定义 若对任意的i,jI，马尔可夫链Xn,nT 的转移概率pij(n)与n无关，则称马尔可夫链是齐次的，并记pij(n)为pij。齐次马尔可夫链具有平稳转移概率，状态空间I=1, 2, 3, ，一步转移概率为74.1 马尔可夫链与转移概率转移概率性质(1) (2) P称为随机矩阵8Markov过程状态为已知的条件下, 过程在时刻tt0所处状态的条件分布与过程在时刻t0之前所处的状态无关. 无后效性亦称马尔可夫性. 无后效性是说,在已知过程“现在”的条件下, 过程的“将来”与过程的“过去”无关,只与“现在”有关.如

5、何辨识马尔可夫过程?1.若X(t),tT是一独立随机过程,且对于n个t1,t2,tnT,随机变量X(t1),X(t2),X(tn)总体独立,则X(t),tT是马尔可夫过程. 因为由条件,随机事件X(t1)=x1,X(t2)=x2,X(tn)=xn,X(t)x相互独立,故有PX(t)x|X(t1)=x1,X(t2)=x2,X(tn)=xn=PX(t)x=PX(t)x|X(tn)=xn. 类似以上的讨论,还有9Markov过程2. 设状态空间I为实数集合R,Y(n),n1是独立随机序列,令X(1)=Y(1),X(n)= Y(k),则X(n),n1是马尔可夫过程.3. 若X(t),tT是一独立增量过

6、程, 且PX(0)=x0=1(是常数),则X(t),tT是马尔可夫过程.马尔可夫链的概念.泊松过程,维纳过程都是时间连续的马尔可夫过程.4. 马尔可夫过程Xn,nT的参数集T=0,1,2,状态集I=i1,i2,可以是0,1,2,或0,1,2,或0,1,2,n. 在以上设定下,称随机过程Xn,nT为马尔可夫链或马氏链,如果对于任意的整数nT和任意的i0,i1,in+1I,10Markov过程有PXn+1=in+1|X0=i0,X1=i1,X2=i2,Xn=in=PXn+1=in+1|Xn=in.5. 条件概率pij(m)=PXm+1=j|Xm=i称为马氏链Xn,nT在时刻m的一步转移概率. 条件

7、概率pij(k)(m)=PXm+k=j|Xm=i称为马氏链Xn,nT在时刻m的k步转移概率.6.马尔可夫链Xn,nT的转移概率pij(k)(m)具有性质: (1) pij(k)(m)0, i,jI; (2) pij(k)(m)=1, i,jI且规定pij(0)(m)=7. 如果对于任意的i,jI,马尔可夫链Xn,nT的转移概率只与i,j有关,而与时刻n无关,则称Xn,nT是时齐的或齐次的,并记pij(m)=pij.1, i=j,0, ij.11Markov过程8. 一步转移概率pij所排成的矩阵称为转移概率矩阵. 转移概率矩阵具有性质: (1) P(n)=PP(n-1); (2) P(n)=P

8、n.9. 切普曼-柯尔莫哥洛夫(Chapman-Kolmogorov)方程: 对于任意正整数s,t有 pij(s+t)(u+v)= pir(s)(u)prj(t)(v).10. 设Xn,nT为马尔可夫链,称 pj=PX0=j和pj(n)=PXn=j,jI为Xn,nT的初始概率和绝对概率, 并分别称pj,jI和pj(n),jI为Xn,nT的初始分布和绝对分布,简记为pj和pj(n).p11 p12 p1n p21 p22 p2n pn1 pn2 pnn P=12Markov过程称概率向量PT(n)=(p1(n),p2(n),), n0,为n时刻的绝对概率向量. 称PT(0)=(p1,p2,)为初

9、始概率向量. 对于任意jI和n1,绝对概率pj(n)具有性质: pj(n)= pi(n-1)pij.绝对概率向量具有性质: (1) PT(n)=PT(0)P(n); (2) PT(n)=PT(n-1)P.11.设Xn,nT为马尔可夫链,则对任意的i1,i2,inI和n1有 PX1=i1,X2=i2,Xn=in= .134.1 马尔可夫链与转移概率例4.1 赌博问题。甲乙二人进行一系列赌博，甲有a元，乙的赌本无限，每赌一局输者给赢者1元，没有和局，如果甲输光，再输则赌本为负。设在每一局中，甲赢的概率为p，输的概率为q=1-p。设Xn表示第n次赌博结束后甲的赌本，则Xn，n1是马尔科夫链，求Xn的

10、转移矩阵144.1 马尔可夫链与转移概率例4.1 无限制随机游动q p-1 0 1 i-1 i i+1 一步转移概率:154.1 马尔可夫链与转移概率n步转移概率:i经过k步进入j,向右移了x步,向左移了y步则164.1 马尔可夫链与转移概率例4.4 具有吸收壁和反射壁的随机游动状态空间1,2,3,4，1为吸收壁，4为反射壁 状态转移图 状态转移矩阵174.1 马尔可夫链与转移概率定义 称条件概率 = PXm+n=j|Xm=i 为马尔可夫链Xn，nT 的n步转移概率(i,jI, m0, n1)。n步转移矩阵其中 P(n)也为随机矩阵184.1 马尔可夫链与转移概率定理4.1 设Xn，nT 为马

11、尔可夫链，则对任意整数n0,0l0 (最大公约数greatest common divisor)如果d1，就称i为周期的，如果d=1，就称i为非周期的484.2 马尔可夫链的状态分类例4.6 设马尔可夫链的状态空间I=1,2,9，转移概率如下图 从状态1出发再返回状态1的可能步数为T=4,6,8,10, ，T的最大公约数为2，从而状态1的周期为2494.2 马尔可夫链的状态分类注(1)如果i有周期d，则对一切非零的n, n0 mod d，有 （若 ，则n=0 mod d ） (2)对充分大的n， （引理4.1）例题中当n=1时， 当n1时，504.2 马尔可夫链的状态分类例4.7 状态空间I=

12、1,2,3,4，转移概率如图， 状态2和状态3有相同的周期d=2，但状态2和状态3有显著的区别。当状态2转移到状态3后，再不能返回到状态2，状态3总能返回到状态3。这就要引入常返性概念。514.2 马尔可夫链的状态分类由i出发经n步首次到达j的概率(首达概率)规定由i出发经有限步终于到达j的概率524.2 马尔可夫链的状态分类 若fii=1，称状态i为常返的； 若fii1，称状态i为非常返的i为非常返，则以概率1- fii不返回到ii为常返，则 构成一概率分布，期望值 表示由i出发再返回到i的平均返回时间定义534.2 马尔可夫链的状态分类 若i ，则称常返态i为正常返的; 若 i =，则称常

13、返态i为零常返的， 非周期的正常返态称为遍历状态。例：判断下面马氏链各状态的类型定义设i为常返544.2 马尔可夫链的状态分类引理4.2 周期的等价定义G.C.D =G.C.D例4.8 设马尔可夫链的状态空间I=1,2,3，转移概率矩阵为 求从状态1出发经n 步转移首次到达各状态的概率554.2 马尔可夫链的状态分类解 状态转移图如下 ，首达概率为 564.2 马尔可夫链的状态分类同理可得574.2 马尔可夫链的状态分类首达概率 与n步转移概率 有如下关系式定理4.4 对任意状态i, j及1 n ，有584.2 马尔可夫链的状态分类证P(A,B|C)= P(B|A,C) P(A|C)59123

14、11例：已知马氏链转移图如下，求从状态1出发再返回1的n步转移概率，n=1,2,8604.2 马尔可夫链的状态分类定理4.5 状态i常返的充要条件为如i非常返，则以下讨论常返性的判别与性质614.2 马尔可夫链的状态分类数列的母函数与卷积an,n0为实数列，母函数bn,n0为实数列，母函数则an与bn的卷积的母函数624.2 马尔可夫链的状态分类定理4.5 状态i常返的充要条件为如i非常返，则证: 规定 ，则由定理4.4634.2 马尔可夫链的状态分类644.2 马尔可夫链的状态分类对0s1654.2 马尔可夫链的状态分类664.2 马尔可夫链的状态分类定理4.7 设i常返且有周期为d，则其中

15、i为i的平均返回时间，当i=时推论 设i常返，则(1) i零常返(2) i遍历6712311例：已知马氏链转移图如下，求从状态1出发再返回1的n步转移概率，n=1,2,8684.2 马尔可夫链的状态分类证(1)i零常返， i=，由定理4.7知，对d的非整数倍数的n， 从而子序列 i是零常返的694.2 马尔可夫链的状态分类(2) 子序列所以d=1，从而i为非周期的，i是遍历的i是遍历的，d=1，i，704.2 马尔可夫链的状态分类例4.10 对无限制随机游动由斯特林近似公式可推出(1)当且仅当p=q=1/2时，4pq=1714.2 马尔可夫链的状态分类状态i是常返的状态i是零常返的724.2

16、马尔可夫链的状态分类(2)当且仅当pq，4pq0,使状态i与状态j互通，ij：ij且ji 定理4.8 可达关系与互通关系都具有传递性，即(1)若ij ，jk，则ik(2)若i j ，j k，则i k4.3 状态空间的分解754.2 马尔可夫链的状态分类证 (1)ij ，存在l 0，使 jk，存在m 0，使由C-K方程所以ik(2)由(1)直接推出764.2 马尔可夫链的状态分类定理4.9 如ij，则 (1) i与j同为常返或非常返，如为常返，则它们同为正常返或零常返(2) i与j有相同的周期774.2 马尔可夫链的状态分类 例4.9 设马氏链Xn的状态空间为 I=0,1,2,，转移概率为考察状

17、态0的类型784.2 马尔可夫链的状态分类 可得出0为正常返的由于 ，所以0的周期为d=10为非周期的，从而为遍历状态对于其它状态i,由于i0,所以也是遍历的 794.3 状态空间的分解定义 状态空间I 的子集C称为闭集，如对任意iC及kC都有pik=0; 闭集C称为不可约的，如C的状态互通； 马氏链Xn称为不可约的，如其状态空间不可约引理4.4 C是闭集的充要条件为对iC及kC都有804.3 状态空间的分解证 充分性显然成立必要性（数学归纳法）设C为闭集，由定义当n=1时结论成立设n=m时， ，iC及kC ，则注：如pii=1，称状态i为吸收的，等价于 单点集i为闭集。814.3 状态空间的

18、分解 例4.11 设马氏链Xn的状态空间为 I=1, 2, 3, 4, 5，转移概率矩阵为状态3是吸收的，故3是闭集，1,4，1,3,4，1,2,3,4都是闭集，其中3，1,4是不可约的。I含有闭子集，故Xn不是不可约的链。824.3 状态空间的分解 例4.12 无限制随机游动为不可约马氏链，各状态的周期为2，当p=q=1/2时，是零常返的，当pq时，是非常返的。834.3 状态空间的分解定理4.10 任一马氏链的状态空间I，可唯一地分解成有限个或可列个互不相交的子集D,C1,C2,之和，使得：(1)每一Cn是常返态组成的不可约闭集；(2)Cn中的状态同类型，或全是正常返，或全是零常返，它们有

19、相同的周期，且fij=1，i,jCn；(3)D由全体非常返态组成，自Cn中状态不能到达D中的状态。844.3 状态空间的分解 例4.13 马氏链的状态空间I =1,2,3,4,5,6,状态转移矩阵为分解此链并指出各状态的常返性及周期性。854.3 状态空间的分解解 由状态转移图知可见1为正常返状态且周期为3，含1的基本常返闭集为 C1=k:1k=1,3,5，从而状态3及5也为正常返状态且周期为3。同理可知6为正常返状态，6=3/2，周期为1。含6的基本常返闭集为 C2=k:6k =2,6，可见2，6为遍历状态。864.3 状态空间的分解 于是I可分解为 I=DC1C2 =41,3,52,6定义

20、4.10 称矩阵A=(aij)为随机矩阵，若显然k步转移矩阵 为随机矩阵。874.3 状态空间的分解引理4.5 设C为闭集，G是C上所得的k步转移子矩阵，则G仍是随机矩阵。证 任取iC，由引理4.4有从而且 ，故 是随机矩阵。884.3 状态空间的分解注：对I的一个闭子集，可考虑C上的原马氏链的子马氏链，其状态空间为C，转移矩阵为G=(pij)，i,jC是原马氏链的转移矩阵为P=(pij)，i,jI的子矩阵。894.3 状态空间的分解定理4.11 周期为d的不可约马氏链，其状态空间C可唯一地分解为d个互不相交的子集之和，即 且使得自Gr中任一状态出发，经一步转移必进入Gr+1中(Gd = G0

21、)。注：任取一状态i，对每一r=0,1,d-1定义集9012311例：已知马氏链转移图如下，求从状态1出发再返回1的n步转移概率，n=1,2,8914.3 状态空间的分解 例4.14 设不可约马氏链的状态空间为C=1, 2, 3, 4, 5, 6，转移矩阵为924.3 状态空间的分解934.3 状态空间的分解由状态转移图可知各状态的周期d=3,固定状态i=1，令故C=G0G1G2 =1,4,63,52944.3 状态空间的分解定理4.12 设Xn,n0是周期为d的不可约马氏链，则在定理4.11的结论下有(1)如只在0,d,2d,上考虑Xn，即得一新马氏链Xnd ，其转移矩阵 ，对此新链，每一Gr是不可约闭集，且Gr中的状态