资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章,马尔可夫链,1,4.1,马尔可夫链与转移概率,定义,设,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,4.1,马尔可夫链与转移概率,马尔可夫过程通常分为三类:,(1)时间、状态都是离散的,称为,马尔可夫链,(2),时间连续,、,状态离散的,称为连续时间,马尔可夫链,(3),时间、状态都是连续的,称为,马尔可夫过程,3,4.1,马尔可夫链与转移概率,随机过程,X,n,,,n,T,,,参数,T,=0,1,2,状态空间,I,=,i,0,i,1,i,2,定义,若随机过程,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,4.1,马尔可夫链与转移概率,马尔可夫链的,性质,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,5,4.1,马尔可夫链与转移概率,=,=,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,确定。,6,4.1,马尔可夫链与转移概率,定义,称条件概率,p,ij,(,n,)=,P,X,n+,1,=,j,|X,n,=,i,为,马尔可夫链,X,n,,,n,T,在时刻,n,的,一步转移概率,,,简称,转移概率,,,其中,i,j,I,。,定义,若对任意的,i,j,I,,,马尔可夫链,X,n,n,T,的转移概率,p,ij,(,n,),与,n,无关,则称,马尔可夫链是齐次的,,并记,p,ij,(,n,),为,p,ij,。,齐次马尔可夫链具有平稳转移概率,,状态空间,I,=1,2,3,,,一步,转移概率为,7,4.1,马尔可夫链与转移概率,转移概率,性质,(1),(2),P,称为随机矩阵,8,4.1,马尔可夫链与转移概率,定义,称条件概率,=,P,X,m+n,=,j,|X,m,=,i,为,马尔可夫链,X,n,,,n,T,的,n,步转移概率,(,i,j,I,m,0,n,1)。,n,步转移矩阵,其中,P,(,n,),也为,随机矩阵,9,4.1,马尔可夫链与转移概率,定理4.1,设,X,n,,,n,T,为,马尔可夫链,则对任意整数,n,0,0,l,0,(最大公约数,greatest common divisor),如果,d,1,,就称,i,为周期的,,如果,d,=1,,就称,i,为非周期的,30,4.2,马尔可夫链的状态分类,例4.6,设马尔可夫链的,状态空间,I,=1,2,9,,转移概率如下图,从状态1出发再返回状态1的可能步数为,T,=4,6,8,10,,,T,的,最大公约数为2,从而,状态1的周期为2,31,4.2,马尔可夫链的状态分类,注(1)如果,i,有周期,d,,,则对一切非零的,n,n,0(mod,d,),,有,(,若 ,则,n,=0(mod,d,),),(2)对充分大的,n,,(,引理4.1),例题中当,n,=1,时,,当,n,1,时,,32,4.2,马尔可夫链的状态分类,例4.7,状态空间,I,=1,2,3,4,,转移概率如图,,,状态2和状态3有相同的周期,d,=2,,但状态2和状态3有显著的区别。当状态2转移到状态3后,再不能返回到状态2,状态3总能返回到状态3。这就要引入,常返性,概念。,33,4.2,马尔可夫链的状态分类,由,i,出发经,n,步首次到达,j,的概率(首达概率),规定,由,i,出发经有限步终于到达,j,的概率,34,4.2,马尔可夫链的状态分类,若,f,ii,=1,,称状态,i,为,常返的,;,若,f,ii,1,,称状态,i,为,非常返的,i,为非常返,则以概率1,-,f,ii,不返回到,i,i,为常返,则,构成一概率分布,,期望值,表示由,i,出发再返回到,i,的平均返回时间,定义,35,4.2,马尔可夫链的状态分类,若,i,,,则称常返态,i,为正常返的;,若,i,=,,,则称常返态,i,为零常返的,,非周期的正常返态称为遍历状态。,首达概率 与,n,步转移概率 有如下关系式,定理4.4 对任意状态,i,j,及1,n,,,有,定义,36,4.2,马尔可夫链的状态分类,证,37,4.2,马尔可夫链的状态分类,引理4.2,周期的等价定义,G.C.D,=G.C.D,例4.8,设马尔可夫链的状态空间,I,=1,2,3,,转移概率矩阵为,求从状态1出发经,n,步转移首次到达各状态的概率,38,4.2,马尔可夫链的状态分类,解 状态转移图如下,首达概率为,39,4.2,马尔可夫链的状态分类,同理可得,40,4.2,马尔可夫链的状态分类,以下讨论常返性的判别与性质,数列的母函数与卷积,a,n,n,0,为实数列,母函数,b,n,n,0,为实数列,母函数,则,a,n,与,b,n,的卷积,的母函数,41,4.2 马尔可夫链的状态分类,定理4.5,状态,i,常返的充要条件为,如,i,非常返,则,证:规定 ,则由定理4.4,42,4.2 马尔可夫链的状态分类,43,4.2 马尔可夫链的状态分类,对0,s,1,44,4.2 马尔可夫链的状态分类,45,4.2 马尔可夫链的状态分类,定理4.7,设,i,常返且有周期为,d,,,则,其中,i,为,i,的平均返回时间,当,i,=,时,推论,设,i,常返,则,(1),i,零常返,(2),i,遍历,46,4.2 马尔可夫链的状态分类,证(1),i,零常返,,i,=,,,由定理4.7,知,,对,d,的非整数倍数的,n,,,从而子序列,i,是零常返的,47,4.2 马尔可夫链的状态分类,(2),子序列,所以,d,=1,,从而,i,为非周期的,,i,是遍历的,i,是遍历的,,d,=1,,i,0,使,状态,i,与状态,j,互通,,,i,j,:,i,j,且,j,i,定理4.8,可达关系与互通关系都具有传递性,即,(1)若,i,j,,,j,k,,,则,i,k,(2)若,i,j,,,j,k,,,则,i,k,49,4.2 马尔可夫链的状态分类,证(1),i,j,,存在,l,0,,使,j,k,,,存在,m,0,,使,由,C-K,方程,所以,i,k,(2)由(1)直接推出,50,4.2 马尔可夫链的状态分类,定理4.8,如,i,j,,则,(1),i,与,j,同为常返或非常返,如为常返,则它们同为正常返或零常返,(2),i,与,j,有相同的周期,51,4.2 马尔可夫链的状态分类,例4.9,设马氏链,X,n,的状态空间为,I,=0,1,2,,,转移概率为,考察状态0的类型,52,4.2 马尔可夫链的状态分类,可得出,0,为正常返的,由于 ,所以,0,的周期为,d,=1,0,为非周期的,从而为遍历状态,对于其它状态,i,由于,i,0,所以也是遍历的,53,4.2 马尔可夫链的状态分类,例4.10,对无限制随机游动,由斯特林近似公式,可推出,(1)当且仅当,p,=,q,=1/2,时,4,pq,=1,54,4.2 马尔可夫链的状态分类,状态,i,是常返的,状态,i,是零常返的,55,4.2 马尔可夫链的状态分类,(2)当且仅当,p,q,,4,pq,1,状态,i,是非常返的,56,状态分类,周期性,d,i,常返性,f,ii,正常返,i,1,非周期,d,i,=1,遍历,非常返,f,ii,1,零常返,i,=,常返,f,ii,=1,57,4.3,遍历性,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,本章小结,马尔可夫链的定义,一步及,K,步转移概率,初始概率及绝对概率,状态分类,遍历性,平稳分布,典型例题,91,
展开阅读全文