随机过程Ch4-马尔科夫链.pdf

第四章第四章 马尔可夫链马尔可夫链 2 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 定义定义 设设 { {X(t)，，t  T } }为随机过程，若对为随机过程，若对 任意正整数任意正整数n及及t10，，且条件分且条件分 布布P{X(tn) xn|X(t1)=x1,, X(tn- -1)=xn- -1}= P{X(tn)   xn|X(tn- -1)=xn- -1}，，则称则称{ {X(t)，，t  T } }为为马尔可夫过程马尔可夫过程 ☆☆若若t1,t2,,tn- -2表示过去，表示过去，tn- -1表示现在，表示现在，tn 表示将来，马尔可夫过程表明：在已知现表示将来，马尔可夫过程表明：在已知现 在状态的条件下，将来所处的状态与过去在状态的条件下，将来所处的状态与过去 状态无关状态无关 3 4.1 马尔可夫链与转移概率 马尔可夫过程通常分为三类：马尔可夫过程通常分为三类： (1)(1)时间、状态都是离散的，称为时间、状态都是离散的，称为马尔可马尔可 夫链夫链 (2)时间连续时间连续、、状态离散的，称为连续时间状态离散的，称为连续时间 马尔可夫链马尔可夫链 (3)时间、状态都是连续的，称为时间、状态都是连续的，称为马尔可夫马尔可夫 过程过程 4 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 随机过程随机过程{ {Xn，，n T } }，， 参数参数T={0, 1, 2, }, ,状态空间状态空间I={i0, i1, i2, } 定义定义 若随机过程若随机过程{ {Xn，，n T } }，对任意，对任意n T和和 i0,i1,,in+1  I，，条件概率条件概率 P{Xn+1=in+1|X0=i0,X1=i1,,Xn=in} = P{Xn+1=in+1|Xn=in}，， 则称则称{ {Xn，，n T } }为为马尔可夫链马尔可夫链，简称，简称马氏链马氏链。

5 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 马尔可夫链的马尔可夫链的性质性质 P{X0=i0, X1=i1, , Xn=in} =P{Xn=in|X0=i0, X1=i1, , Xn- -1=in- -1} P{X0=i0, X1=i1, , Xn- -1=in- -1} = P{Xn=in|Xn- -1=in- -1} P{Xn- -1=in- -1 |X0=i0,X1=i1,,Xn- -2=in- -2} P{X0=i0,X1=i1,,Xn- -2=in- -2} =P{Xn=in|Xn- -1=in- -1}P{Xn- -1=in- -1 |Xn- -2=in- -2} P{X0=i0,X1=i1,,Xn- -2=in- -2} 6 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 = =P{Xn=in|Xn- -1=in- -1}P{Xn- -1=in- -1 |Xn- -2=in- -2}  P{X1=i1|X0=i0}P{X0=i0} 马尔可夫链的统计特性完全由条件概率马尔可夫链的统计特性完全由条件概率 P{Xn+1=in+1|Xn=in}确定。

确定 7 4.1 马尔可夫链与转移概率 定义定义 称条件概率称条件概率pij(n)= P{Xn+1=j|Xn=i} 为为 马尔可夫链马尔可夫链{ {Xn，，n T } }在时刻在时刻n的的一步转一步转 移概率移概率，，简称简称转移概率转移概率，，其中其中i, ,j I 定义定义 若对任意的若对任意的i, ,j I，，马尔可夫链马尔可夫链 { {Xn,n T } }的转移概率的转移概率pij(n)与与n无关，则称无关，则称 马尔可夫链是齐次的马尔可夫链是齐次的，并记，并记pij(n)为为pij 齐次马尔可夫链具有平稳转移概率，齐次马尔可夫链具有平稳转移概率， 系统状态空间系统状态空间I={1, 2, 3, }，，系统状态的一系统状态的一 步步转移概率用转移矩阵转移概率用转移矩阵P表示表示 8 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 转移概率转移概率性质性质 (1) (2) 当转移矩阵当转移矩阵P满足（满足（1）、（）、（2）两性质时，则称）两性质时，则称 P为随机矩阵为随机矩阵 mnmmnnpppppppppP212222111211Ijipij,, 0IipIjij , 19 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 定义定义 称条件概率称条件概率 = P{Xm+n=j|Xm=i} 为为马尔可夫链马尔可夫链{ {Xn，，n T } }的的n步转移概步转移概 率率(i, ,j I, m 0, n 1)。

n步转移矩阵步转移矩阵 如果其中如果其中 P(n)也为也为随机矩阵随机矩阵 )(n ijp)(n ijnpP IjippIjn ijn ij ,, 1,0)()( jijipnPPppnijijij,1,00,,1)0()1()1(时，规定时，规定当当时时当当10 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 定理定理4.1 设设{ {Xn，，n T } }为为马尔可夫链，马尔可夫链， 则对任意整数则对任意整数n 0,0 l0} (最大公约数最大公约数greatest common divisor) 如果如果d>1，，就称就称i为周期的，为周期的， 如果如果d=1，，就称就称i为非周期的为非周期的 )(niip31 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 例例4.6 设马尔可夫链的设马尔可夫链的状态空间状态空间 I={1,2,,9}，，转移概率如下图转移概率如下图 从状态从状态1出发再返回状态出发再返回状态1的可能步数为的可能步数为 T={4,6,8,10, }，，T的的最大公约数为最大公约数为2，， 从而从而状态状态1的周期为的周期为2 8956723413132111 11 11132 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 注注(1)如果如果i有周期有周期d，，则对一切非零的则对一切非零的n, , n 0( mod (d))，，有有 .这也不意味这也不意味 对任意对任意nd，有，有 。

(2)对对充分大的充分大的n，， （（引理引理4.1）） 例题中当例题中当n=1时，时， 当当n>1时，时， 0)(niip()0 iindp0)(ndiip0)(ndiip0)2()( iiiippnd33 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 例例4.7 状态空间状态空间I={1,2,3,4}，，转移概率如图转移概率如图，， 状态状态2和状态和状态3有相同的周期有相同的周期d=2，，但状态但状态 2和状态和状态3有显著的区别当状态有显著的区别当状态2转移到转移到 状态状态3后，再不能返回到状态后，再不能返回到状态2，状态，状态3总总 能返回到状态能返回到状态3这就要引入常返性概念这就要引入常返性概念 2 3 41211112134 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 由由i出发经出发经n步首次到达步首次到达j的概率的概率(首达概率首达概率) 规定规定 由由i出发经有限步终于到达出发经有限步终于到达j的概率的概率 0)0( ijf1 }|, 11 ,{)( niXjXnvjXPfmnmvmnij1)(nn ijijff1)0(iif35 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 若若fii=1，，称状态称状态i为为常返的常返的；； 若若fii0, 使使 称状态称状态i可达可达状态状态j，， ij; 状态状态i与状态与状态j互通互通，，ij：：ij且且ji 定理定理4.8 可达关系与互通关系都具有传递性，可达关系与互通关系都具有传递性， 即即 (1)若若ij ，，jk，，则则ik (2)若若i  j ，，j  k，，则则i  k 0)(n ijp50 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 证证 (1)ij ，存在，存在l >0，，使使 jk，，存在存在m >0，，使使 由由C-K方程方程 所以所以ik (2)由由(1)直接推出直接推出 0)(l ijp0)(m jkp0)()()()()(sm jkl ijm skl isml ikppppp51 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 定理定理4.9 如如ij，则，则 (1) i与与j同为常返或非常返，如为常返，则它同为常返或非常返，如为常返，则它 们同为正常返或零常返们同为正常返或零常返 (2) i与与j有相同的周期有相同的周期 52 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 例例4.9 设马氏链设马氏链{Xn}的状态空间为的状态空间为 I={0,1,2,}，，转移概率为转移概率为 考察状态考察状态0的类型的类型 Iipppiii,21,21,2101,00123021212121212121 2153 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 可得出可得出0为正常返的为正常返的 由于由于 ，所以，所以0的周期为的周期为d=1 0为非周期的，从而为遍历状态为非周期的，从而为遍历状态 对于其它状态对于其它状态i,由于由于i0,所以也是遍历的所以也是遍历的 2210, 121,2181 21 21 21,41 21 21,2111)( 000100)( 00)3( 00)2( 00)1( 00nn nnnnnnnnffffff 为常返状态为常返状态故故021)1( 00p54 55 56 57 4.3 状态空间的分解状态空间的分解 58 周期性di 常返性fii 正常返正常返μi1 非周期di=1 遍历遍历 非常返非常返fii<1 零常返零常返μi=∞ 常返常返fii=1 ( )1limn iinip( )lim0n iinp ( )1n ii np 59 4.3 状态空间的分解 定义定义4.9 马氏链状态空间马氏链状态空间I 的子集的子集C，，如对任意如对任意i C 及及k C都有都有pik=0，子集，子集C称为称为闭集闭集; 如如C的状态互通，闭集的状态互通，闭集C称为称为不可约的不可约的；； 如马氏链状态空间不可约，则马氏链如马氏链状态空间不可约，则马氏链{Xn}称称 为为不可约的不可约的。

引理引理4.4 C是闭集的充要条件为对是闭集的充要条件为对i C及及 k C都有都有 0, 0)(npn ik61 4.3 4.3 状态空间的分解状态空间的分解 例例4.11 设马氏链设马氏链{Xn}的状态空间为的状态空间为 I={1, 2, 3, 4, 5}，，转移概率矩阵为转移概率矩阵为 状态状态3是吸收的，故是吸收的，故{3}是闭集，是闭集，{1,4}，， {1,3,4}，，{1,2,3,4}都是闭集，其中都是闭集，。