1、马尔可夫性马尔可夫性与与马尔可夫链马尔可夫链 2马尔可夫链马尔可夫链 定义：定义：设设 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表示将来，马尔可夫过程表明：在已知表示将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与现在状态的条件下，将来所处的状态与过去状态无关。过去状态无关
2、。3马尔可夫链马尔可夫链 马尔可夫过程通常分为三类：马尔可夫过程通常分为三类：(1)(1)时间、状态都是离散的，称为时间、状态都是离散的，称为马尔可马尔可夫链夫链(2)时间连续时间连续、状态离散的，称为连续时间状态离散的，称为连续时间马尔可夫链马尔可夫链(3)时间、状态都是连续的，称为时间、状态都是连续的，称为马尔可夫马尔可夫过程过程4随机过程随机过程 Xn，n T ，参数参数T=0,1,2,状态空间状态空间I=i0,i1,i2,定义定义1 若随机过程若随机过程 Xn，n T ，对任，对任意意n T和和i0,i1,in+1 I，条件概率条件概率PXn+1=in+1|X0=i0,X1=i1,Xn
3、=in =PXn+1=in+1|Xn=in，则称则称 Xn，n T 为马尔可夫链，简称马为马尔可夫链，简称马氏链。氏链。5 定义定义2 称条件概率称条件概率pij(n)=PXn+1=j|Xn=i 为为马尔可夫链马尔可夫链 Xn，n T 在时刻在时刻n的一步转的一步转移概率，移概率，简称简称转移概率转移概率，其中其中i,j I。定义定义3 若对任意的若对任意的i,j I，马尔可夫链马尔可夫链 Xn,n T 的转移概率的转移概率pij(n)与与n无关，则称无关，则称马尔可夫链是齐次的，并记马尔可夫链是齐次的，并记pij(n)为为pij。齐次马尔可夫链具有平稳转移概率，齐次马尔可夫链具有平稳转移概率
4、，状态空间状态空间I=1,2,3,，一步一步转移概率为转移概率为6 转移概率转移概率性质性质(1)(2)P称为一步称为一步转移概率转移概率矩阵矩阵 mnmmnnpppppppppP101111000100Ijipij,0IipIjij,17说明：二、基本性质二、基本性质性质性质1设0,nXn为马氏链，其状态空间为I，则,110nniXiXiXP=0iXP|011iXiXP|1122iXiXP|11nnnniXiXPnXXX,10的联合分布可由初始分布及转移概率所决定，即有,110nniXiXiXPniiiiiinpppip11120)(8则性质性质2设0,nXn为马氏链，其状态空间为I，表明,
5、|11mnmnnnnniXiXiXP|11nnnniXiXP一个马氏链，如果按相反方向的时间排列，所成的序列也是一个马氏链。9性质性质3设0,nXn为马氏链，其状态空间为I，表明若已知现在，则过去与未来是独立的。若nrs0，则在rriX的条件下，有|,rrssnniXiXiXP=|rrnniXiXP|rrssiXiXP10则性质性质4设0,nXn为马氏链，其状态空间为I，表明若已知现在，则过去同时对将来各时刻的状态都不产生影响。,|,0011iXiXiXiXPnnmnmnnn=|,11nnmnmnnniXiXiXP特别,|00iXiXiXPnnmnmn=|nnmnmniXiXP11则性质性质5
6、设0,nXn为马氏链，其状态空间为I，表明马氏链的子链也是马氏链对任意给定的n个整数，nkkk210，有,|1111kkkkkkiXiXiXPnnnn=|11nnnnkkkkiXiXP12 马尔可夫链的性质马尔可夫链的性质 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,
7、X1=i1,Xn-2=in-213=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2 PX1=i1|X0=i0PX0=i0 马尔可夫链的统计特性完全由条件概率马尔可夫链的统计特性完全由条件概率PXn+1=in+1|Xn=in确定。确定。14 定义定义4 称条件概率称条件概率 =PXm+n=j|Xm=i 为为马尔可夫链马尔可夫链 Xn，n T 的的n步转移概步转移概率率(i,j I,m 0,n 1)。n步转移矩阵步转移矩阵其中其中 nijp nijnpP)(IjippIjnijnij ,1,015 定理定理1 设设 Xn，n T 为为马尔可夫链，则马尔可夫链，则对任意整数
8、对任意整数n 0,0 l0,使使 状态状态i与状态与状态j互通互通，ij：ij且且ji 定理定理3 可达关系与互通关系都具有传可达关系与互通关系都具有传递性，即递性，即(1)若若ij，jk，则则ik(2)若若i j，j k，则则i k0 nijp26 证证(1)ij，存在，存在l 0，使使 jk，存在存在m 0，使使由由C-K方程方程所以所以ik(2)由由(1)直接推出直接推出0 lijp0 mjkp0 smjklijmsklismlikppppp27 Xn,n 0是离散马尔可夫链，是离散马尔可夫链，pij为转移为转移概率，概率，i,j I，I=0,1,2,为状态空间，为状态空间，pj,j I
9、为为初始分布初始分布 定义定义4.6 状态状态i的周期的周期d：d=G.C.Dn:0 (最大公约数最大公约数greatest common divisor)如果如果d1，就称就称i为周期的，为周期的，如果如果d=1，就称就称i为非周期的为非周期的)(niip28例例4.3 状态空间状态空间I=1,2,3,4，转移概率如图转移概率如图，状态状态2和状态和状态3有相同的周期有相同的周期d=2，但状态但状态2和状态和状态3有显著的区别。当状态有显著的区别。当状态2转移到转移到状态状态3后，再不能返回到状态后，再不能返回到状态2，状态，状态3总总能返回到状态能返回到状态3。这就要引入常返性概念。这就要
10、引入常返性概念。2341211112129 由由i出发经出发经n步首次到达步首次到达j的概率的概率(首达概率首达概率)规定规定 由由i出发经有限步终于到达出发经有限步终于到达j的概率的概率00 ijf1|,11,niXjXnvjXPfmnmvmnij 1nnijijff30 若若fii=1，称状态称状态i为常返的；为常返的；若若fii1，称状态称状态i为非常返的为非常返的 i为非常返，则以概率为非常返，则以概率1-fii不返回到不返回到i i为常返，则为常返，则 构成一概率分布，构成一概率分布，期望值期望值 表示由表示由i出发再返回出发再返回到到i的平均返回时间的平均返回时间 1nniiinf
11、 11,1nnnnffiiii定义定义731 若若 i，则称常返态则称常返态i为正常返的，为正常返的，若若 I=，则称常返态则称常返态i为零常返的，为零常返的，非周期的正常返态称为遍历状态。非周期的正常返态称为遍历状态。首达概率首达概率 与与n步转移概率步转移概率 有如下有如下关系式关系式定理定理4 对任意状态对任意状态i,j及及1 n，有有nijfnijp nkkjjknnkknjjknijpfpfpijij01定义定义832证证)0(,|,11,11,|,11,|001010100 ijnkkjjknnkkknjjkvnkkvnnknkvnnijfpffpiXjXkvjXPjXkvjXiXjXPiXjXjXkvjXPiXjXPpijij33 定理定理5 状态状态i常返的充要条件为常返的充要条件为如如i非常返，则非常返，则 0nniipiinniifp 11034 定理定理6 如如ij，则，则(1)i与与j同为常返或非常返，如为常返，则同为常返或非常返，如为常返，则它们同为正常返或零常返它们同为正常返或零常返(2)i与与j有相同的周期有相同的周期
