第四章 马尔可夫链,,4.1 马尔可夫链与转移概率,定义 设 X(t)，t T 为随机过程，若对任意正整数n及t10，且条件分布 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表示将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与过去状态无关4.1 马尔可夫链与转移概率,常见马尔可夫过程通常有三类： (1)时间、状态都是离散的，称为马尔可夫链 (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 马尔可夫链与转移概率,4.1 马尔可夫链与转移概率,马尔可夫链的性质 PX0=i0, X1=i1, , Xn=in =PXn=in|X0=i0, X1=i1, , Xn-1=in-1 PX0=i0, X1=i1, , 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-2,4.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确定4.1 马尔可夫链与转移概率,定义 称条件概率pij(n)= PXn+1=j|Xn=i 为马尔可夫链Xn，nT 在时刻n的一步转移概率，简称转移概率，其中i,jI 定义 若对任意的i,jI，马尔可夫链Xn,nT 的转移概率pij(n)与n无关，则称马尔可夫链是齐次的，并记pij(n)为pij。
齐次马尔可夫链具有平稳转移概率， 状态空间I=1, 2, 3, ，一步转移概率为,4.1 马尔可夫链与转移概率,转移概率性质 (1) (2) P称为随机矩阵,4.1 马尔可夫链与转移概率,例4.1 赌博问题甲乙二人进行一系列赌博，甲有a元，乙的赌本无限，每赌一局输者给赢者1元，没有和局，如果甲输光，再输则赌本为负设在每一局中，甲赢的概率为p，输的概率为q=1-p设Xn表示第n次赌博结束后甲的赌本，则Xn，n1是马尔科夫链，求Xn的转移矩阵,,,4.1 马尔可夫链与转移概率,例4.1 无限制随机游动,,,,,,,q p,-1 0 1 i-1 i i+1,一步转移概率:,4.1 马尔可夫链与转移概率,n步转移概率: i经过k步进入j,向右移了x步,向左移了y步 则,4.1 马尔可夫链与转移概率,例4.4 具有吸收壁和反射壁的随机游动 状态空间1,2,3,4，1为吸收壁，4为反射壁 状态转移图 状态转移矩阵,4.1 马尔可夫链与转移概率,定义 称条件概率 = PXm+n=j|Xm=i 为马尔可夫链Xn，nT 的n步转移概率(i,jI, m0, n1)。
n步转移矩阵 其中 P(n)也为随机矩阵,4.1 马尔可夫链与转移概率,定理4.1 设Xn，nT 为马尔可夫链，则对任意整数n0,0l
4.1 马尔可夫链与转移概率,,定理4.3 设Xn，nT 为马尔可夫链，则对任意整数i1, i2,,inI和n1 ，有性质 证,4.1 马尔可夫链与转移概率,例4.2 赌徒输光问题 甲有赌资a元，乙有赌资b元，赌一局输者给赢者1元，无和局甲赢的概率为p， 乙赢的概率为q=1-p，求甲输光的概率 解 状态空间I=0,1,2,,c，c=a+b,,,,,,,q p,a-1 a a+1,,,0 a+b,4.1 马尔可夫链与转移概率,设ui表示甲从状态i出发转移到状态0的概率，求ua 显然u0 =1，uc =0(u0表示已知甲输光情形下甲输光的概率，uc表示已知乙输光情形下甲输光的概率) ui =pui+1 + qui-1 (i=1,2,,c-1) （甲在状态i下输光：甲赢一局后输光或甲输一局后输光）,4.1 马尔可夫链与转移概率,,4.1 马尔可夫链与转移概率,,4.1 马尔可夫链与转移概率,,4.1 马尔可夫链与转移概率,,4.1 马尔可夫链与转移概率,例4.3 天气预报问题 RR表示连续两天有雨，记为状态0 NR表示第1天无雨第2天有雨，记为状态1 RN表示第1天有雨第2天无雨，记为状态2 NN表示连续两天无雨，记为状态3 p00=PR今R明| R昨R今=PR明| R昨R今=0.7 p01=PN今R明| R昨R今=0 p02=PR今N明| R昨R今= PN明| R昨R今=0.3 p03=PN今N明| R昨R今=0,4.1 马尔可夫链与转移概率,类似地得到其他转移概率， 于是转移概率矩阵为 若星期一、星期二均下雨，求星期四下雨的概率,4.1 马尔可夫链与转移概率,星期四下雨的情形如右， 星期四下雨的概率 2步转移概率矩阵为,4.2 马尔可夫链的状态分类,Xn, n0是离散马尔可夫链，pij为转移概率，i, jI，I=0,1,2,为状态空间，pj,jI为初始分布 定义4.3 状态i的周期d： d=G.C.Dn: 0 (最大公约数greatest common divisor) 如果d1，就称i为周期的， 如果d=1，就称i为非周期的,4.2 马尔可夫链的状态分类,例4.6 设马尔可夫链的状态空间I=1,2,,9，转移概率如下图 从状态1出发再返回状态1的可能步数为T=4,6,8,10, ，T的最大公约数为2，从而状态1的周期为2,4.2 马尔可夫链的状态分类,注(1)如果i有周期d，则对一切非零的n, n0 mod d，有 （若 ，则n=0 mod d ） (2)对充分大的n， （引理4.1） 例题中当n=1时， 当n1时，,4.2 马尔可夫链的状态分类,例4.7 状态空间I=1,2,3,4，转移概率如图， 状态2和状态3有相同的周期d=2，但状态2和状态3有显著的区别。
当状态2转移到状态3后，再不能返回到状态2，状态3总能返回到状态3这就要引入常返性概念4.2 马尔可夫链的状态分类,由i出发经n步首次到达j的概率(首达概率) 规定 由i出发经有限步终于到达j的概率,4.2 马尔可夫链的状态分类,若fii=1，称状态i为常返的； 若fii<1，称状态i为非常返的 i为非常返，则以概率1- fii不返回到i i为常返，则 构成一概率分布， 期望值 表示由i出发再返回到i的平均返回时间,定义,4.2 马尔可夫链的状态分类,若i <，则称常返态i为正常返的; 若 i =，则称常返态i为零常返的， 非周期的正常返态称为遍历状态 例：判断下面马氏链各状态的类型,定义,设i为常返,4.2 马尔可夫链的状态分类,引理4.2 周期的等价定义 G.C.D =G.C.D 例4.8 设马尔可夫链的状态空间I=1,2,3，转移概率矩阵为 求从状态1出发经n 步转移首次到达各状态的概率,4.2 马尔可夫链的状态分类,解 状态转移图如下 ，首达概率为,4.2 马尔可夫链的状态分类,同理可得,4.2 马尔可夫链的状态分类,首达概率 与n步转移概率 有如下关系式 定理4.4 对任意状态i, j及1 n <，有,4.2 马尔可夫链的状态分类,证,P(A,B|C)= P(B|A,C) P(A|C),,,,,,,,,,例：已知马氏链转移图如下，求从状态1出发再返回1的n步转移概率，n=1,2,,8,,,,4.2 马尔可夫链的状态分类,定理4.5 状态i常返的充要条件为 如i非常返，则,以下讨论常返性的判别与性质,4.2 马尔可夫链的状态分类,数列的母函数与卷积 an,n0为实数列，母函数 bn,n0为实数列，母函数 则an与bn的卷积 的母函数,4.2 马尔可夫链的状态分类,定理4.5 状态i常返的充要条件为 如i非常返，则 证: 规定 ，则由定理4.4,4.2 马尔可夫链的状态分类,,4.2 马尔可夫链的状态分类,对0s<1,4.2 马尔可夫链的状态分类,,,,,,,,4.2 马尔可夫链的状态分类,定理4.7 设i常返且有周期为d，则 其中i为i的平均返回时间，当i=时 推论 设i常返，则 (1) i零常返 (2) i遍历,,例：已知马氏链转移图如下，求从状态1出发再返回1的n步转移概率，n=1,2,,8,,,,,,,,,,,,,,,,,,,,,,4.2 马尔可夫链的状态分类,证(1) i零常返， i=，由定理4.7知， 对d的非整数倍数的n， 从而子序列 i是零常返的,4.2 马尔可夫链的状态分类,(2) 子序列 所以d=1，从而i为非周期的，i是遍历的 i是遍历的，d=1，i<，,4.2 马尔可夫链的状态分类,例4.10 对无限制随机游动 由斯特林近似公式 可推出 (1)当且仅当p=q=1/2时，4pq=1,4.2 马尔可夫链的状态分类,状态i是常返的 状态i是零常返的,,,4.2 马尔可夫链的状态分类,(2)当且仅当pq，4pq<1 状态i是非常返的,,4.1 马尔可夫链与转移概率,例4.1 无限制随机游动,,,,,,,p,-1 0 1 i-1 i i+1,一步转移概率:,,,,,,,,,,p,p,p,q,q,q,q,状态的可达与互通 状态i可达状态j，ij：存在n0,使 状态i与状态j互通，ij：ij且ji 定理4.8 可达关系与互通关系都具有传递性，即 (1)若ij ，jk，则ik (2)若i j ，j k，则i k,4.3 状态空间的分解,4.2 马尔可夫链的状态分类,证 (1)ij ，存在l 0，使 jk，存在m 0，使 由C-K方程 所以ik (2)由(1)直接推出,4.2 马尔可夫链的状态分类,定理4.9 如ij，则 (1) i与j同为常返或非常返，如为常返，则它们同为正常返或零常返 (2) i与j有相同的周期,4.。