,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,马尔可夫性与马尔可夫链,马尔可夫性与马尔可夫链,2,马尔可夫链,定义：设,X,(,t,)，,t,T,为随机过程，若对任意正整数,n,及,t,1,t,2,0，,且条件分布,P,X,(,t,n,),x,n,|X,(,t,1,)=,x,1,X,(,t,n,-,1,)=,x,n,-,1,=,P,X,(,t,n,),x,n,|X,(,t,n,-,1,)=,x,n,-,1,，,则称,X,(,t,)，,t,T,为,马尔可夫过程,。,若,t,1,t,2,t,n,-,2,表示过去，,t,n,-,1,表示现在，,t,n,表示将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与过去状态无关。,2马尔可夫链定义：设 X(t)，t T 为随机,3,马尔可夫链,马尔可夫过程通常分为三类：,(1)时间、状态都是离散的，称为,马尔可夫链,(2),时间连续,、,状态离散的，称为连续时间,马尔可夫链,(3),时间、状态都是连续的，称为,马尔可夫过程,3马尔可夫链马尔可夫过程通常分为三类：,4,随机过程,X,n,，,n,T,，,参数,T,=0,1,2,状态空间,I,=,i,0,i,1,i,2,定义,1,若随机过程,X,n,，,n,T,，对任意,n,T,和,i,0,i,1,i,n,+1,I,，,条件概率,P,X,n,+1,=,i,n,+1,|X,0,=,i,0,X,1,=,i,1,X,n,=,i,n,=,P,X,n,+1,=,i,n,+1,|X,n,=,i,n,，,则称,X,n,，,n,T,为马尔可夫链，简称马氏链。,4随机过程Xn，nT，,5,定义2 称条件概率,p,ij,(,n,)=,P,X,n+,1,=,j,|X,n,=,i,为,马尔可夫链,X,n,，,n,T,在时刻,n,的一步转移概率，,简称,转移概率,，,其中,i,j,I,。,定义3,若对任意的,i,j,I,，,马尔可夫链,X,n,n,T,的转移概率,p,ij,(,n,),与,n,无关，则称,马尔可夫链是齐次的，并记,p,ij,(,n,),为,p,ij,。,齐次马尔可夫链具有平稳转移概率，,状态空间,I,=1,2,3,，,一步,转移概率为,5定义2 称条件概率pij(n)=PXn+1=j|X,6,转移概率,性质,(1),(2),P,称为一步,转移概率,矩阵,6,7,说明：,二、基本性质,性质,1,的联合分布可由初始分布及转移概率所决定，即有,7说明：二、基本性质性质1的联合分布可由初始分布及转移概率所,8,则,性质,2,表明,一个马氏链，如果按相反方向的时间排列，所成的序列也是一个马氏链。,8则性质2表明一个马氏链，如果按相反方向的时间排列，所成的序,9,性质,3,表明,若已知现在，则过去与未来是独立的。,9性质3表明若已知现在，则过去与未来是独立的。,10,则,性质,4,表明,若已知现在，则过去同时对将来各时刻的状态都不产生影响。,特别,10则性质4表明若已知现在，则过去同时对将来各时刻的状态都不,11,则,性质,5,表明,马氏链的子链也是马氏链,11则性质5表明马氏链的子链也是马氏链,12,马尔可夫链的性质,P,X,0,=,i,0,X,1,=,i,1,X,n,=,i,n,=,P,X,n,=,i,n,|X,0,=,i,0,X,1,=,i,1,X,n,-,1,=,i,n,-,1,P,X,0,=,i,0,X,1,=,i,1,X,n,-,1,=,i,n,-,1,=,P,X,n,=,i,n,|X,n,-,1,=,i,n,-,1,P,X,n,-,1,=,i,n,-,1,|,X,0,=,i,0,X,1,=,i,1,X,n,-,2,=,i,n,-,2,P,X,0,=,i,0,X,1,=,i,1,X,n,-,2,=,i,n,-,2,=,P,X,n,=,i,n,|X,n,-,1,=,i,n,-,1,P,X,n,-,1,=,i,n,-,1,|,X,n,-,2,=,i,n,-,2,P,X,0,=,i,0,X,1,=,i,1,X,n,-,2,=,i,n,-,2,12马尔可夫链的性质,13,=,=,P,X,n,=,i,n,|X,n,-,1,=,i,n,-,1,P,X,n,-,1,=,i,n,-,1,|,X,n,-,2,=,i,n,-,2,P,X,1,=,i,1,|,X,0,=,i,0,P,X,0,=,i,0,马尔可夫链的统计特性完全由条件概率,P,X,n+1,=,i,n+1,|X,n,=,i,n,确定。,13=,14,定义4 称条件概率,=,P,X,m+n,=,j,|X,m,=,i,为,马尔可夫链,X,n,，,n,T,的,n,步转移概率,(,i,j,I,m,0,n,1)。,n,步转移矩阵,其中,14定义4 称条件概率 =PXm+n=j|X,15,定理1 设,X,n,，,n,T,为,马尔可夫链，则对任意整数,n,0,0,l,0,使,状态,i,与状态,j,互通,，,i,j,：,i,j,且,j,i,定理,3,可达关系与互通关系都具有传递性，即,(1)若,i,j,，,j,k,，,则,i,k,(2)若,i,j,，,j,k,，,则,i,k,25 状态的可达与互通,26,证(1),i,j,，存在,l,0，,使,j,k,，,存在,m,0，,使,由,C-K,方程,所以,i,k,(2)由(1)直接推出,26证(1)ij，存在l 0，使,27,X,n,n,0,是离散马尔可夫链，,p,ij,为转移概率，,i,j,I,，,I,=0,1,2,为状态空间，,p,j,j,I,为,初始分布,定义,4.6,状态,i,的周期,d,：,d,=G.C.D,n,:0,(最大公约数,greatest common divisor),如果,d,1，,就称,i,为周期的，,如果,d,=1，,就称,i,为非周期的,27Xn,n0是离散马尔可夫链，pij为转移概率，i,28,例4.,3,状态空间,I,=1,2,3,4，,转移概率如图,，,状态2和状态3有相同的周期,d,=2，,但状态2和状态3有显著的区别。当状态2转移到状态3后，再不能返回到状态2，状态3总能返回到状态3。这就要引入常返性概念。,28例4.3 状态空间I=1,2,3,4，转移概率如图,29,由,i,出发经,n,步首次到达,j,的概率(首达概率),规定,由,i,出发经有限步终于到达,j,的概率,29由i出发经n步首次到达j的概率(首达概率),30,若,f,ii,=1，,称状态,i,为常返的；,若,f,ii,1，,称状态,i,为非常返的,i,为非常返，则以概率1,-,f,ii,不返回到,i,i,为常返，则,构成一概率分布，,期望值,表示由,i,出发再返回到,i,的平均返回时间,定义7,30 若fii=1，称状态i为常返的；定义7,31,若,i,，,则称常返态,i,为正常返的，,若,I,=,，,则称常返态,i,为零常返的，,非周期的正常返态称为遍历状态。,首达概率 与,n,步转移概率 有如下关系式,定理4 对任意状态,i,j,及1,n,，,有,定义8,31 若i，则称常返态i为正常返的，定义8,32,证,32证,33,定理5 状态,i,常返的充要条件为,如,i,非常返，则,33定理5 状态i常返的充要条件为,34,定理,6,如,i,j,，则,(1),i,与,j,同为常返或非常返，如为常返，则它们同为正常返或零常返,(2),i,与,j,有相同的周期,34定理6 如ij，则,