Markov链的状态分类.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.2 Markov,链的状态分类,互达性和周期性,定义,3.3,设,i,和,j,是时齐的,Markov,链的两个状态,如果存在,n,0,使得,则称从状态,i,可达,状态,j,记作,i,j,.,反之,以,i j,表示从状态,i,不可达,状态,j,即对一切,n,0,.,若,i,j,且,j,i,则称状态,i,和,j,互达,(,相通,),记作,i,j,.,注,:,引入互达性概念是为了对状态进行分类,.,1,命题,3.1,互达性是等价关系,即满足,:,(1),自反性,:,i,i,;,(2),对称性,:,若,i,j,则,j,i,;,(3),传递性,:,若,i,k,且,k,j,则,i,j,.,证,:,(3),若,i,k,且,k,j,则存在整数,n,和,m,使得,:,由,Chapman-Kolmogorov,方程得,:,即,:,i,j.,类似可证,j,i.,2,在数学上,等价关系可以用于对集合进行分割,.,因此,我们也可以利用互达性对状态空间进行分类,并且这些类在互达关系下是等价类,.,定义,3.4,一个,Markov,链的状态空间,如果在互达性这一等价关系下都居于同一类,那么就称这个,Markov,链是,不可约,的,.,否则,这个,Markov,链就被称为是,可约,的,.,注,:,引入可约,/,不可约概念是为了以后研究状态的周期,进一步是为了研究转移概率的极限性质,.,3,则显然,1,2,和,3,4,5,是状态在互达意义下的两个等价类,.,因此,这个,Markov,链是可约的,.,比如其中一个子链为,:,例,3.6,若,Markov,链有转移概率矩阵,4,给出这个,Markov,链状态的等价类,并且试给出其,n,步转移概率矩阵,.,练习,:,若,Markov,链有转移概率矩阵,答,:,等价类为,:1,4,2,5,和,3.,其中,3,为吸收态,.,5,用,Mathematica,软件计算知,:,所以,6,7,定义,3.5,设,i,为,Markov,链的一个状态,使 的所有正整数,n,(,n,1),的最大公约数,称为状态,i,的,周期,记作,d,(,i,),或,d,i,.,如果对所有,n,1,都有,则约定周期为,;,d,(,i,)=1,的状态,i,称为是,非周期,的,.,推论,:,如果,n,不能被周期,d,(,i,),整除,则必有,.,注,:,当状态,i,的周期为,d,时,不一定成立,.,8,试求状态,0,的周期,.,例,3.7,若,Markov,链有状态,0,1,2,3,和转移概率矩阵,解,:,状态转移可以用下图表示,9,用数学归纳法不难求出,:,所以,d,(0)=2.,10,试求状态,1,的周期,.,练习,:,若,Markov,链有状态,1,2,3,和转移概率矩阵,解,:,状态转移可以用下图表示,11,所以,d,(1)=2.,您能求出状态,2,的周期吗,?,12,命题,3.2,如果,i,j,则,d,i,=,d,j,.,证,:,设,m,1,n,1,使得,则,因此,m,+,n,同时能被,d,i,及,d,j,整除,.,对于任意的,s,1,即,:,m+s+n,也能被,d,j,整除,.,因此,s,能被,d,j,整除,.,从而,d,j,整除的 最大公因子,d,i,.,根据对称性,d,i,也整除,d,j,所以,d,i,=,d,j,.,满足,则,13,引理,3.1,设,m,2,正整数,s,1,s,2,s,m,的最大公因子为,d,则存在正整数,N,使得,n,N,时,必有非负整数,c,1,c,2,c,m,使,.,我们引入状态周期概念的目的，是为了研究状态转移矩阵的极限性质，即当,n,时,P,(,n,),的极限，这个矩阵可以反映出,Markov,链在平稳状态时的特征。因此，下面我们将讨论周期的基本性质，为此先给出一个数论中的结论：,14,推论,3.1,设状态,i,的周期为,d,i,.,如果,则存在整数,N,使得对所有,n,N,恒有,证,:,这时存在,正整数,s,1,s,2,s,m,使得它们的最大公因子为,d,且,.,命题,3.3,如果状态,i,有周期,d,则存在整数,N,使得对所有,n,N,恒有,.,由引理,3.1,存在正整数,N,使得,n,N,时,必有非负整数,c,1,c,2,c,m,使,.,从而,15,因为状态空间有限,对全部的状态对,(,i,j,),求出,N,(,i,j,).,并取,则显然对所有状态,i,和,j,当,nN,时有,.,证,:,由于,Markov,链是不可约的,过程的任两个状态,i,和,j,都是互达的,于是,m,(,与,i,和,j,有关,),使得,.,由推论,3.1,及链的非周期性知,存在,N,使得当,n,N,时,.,命题,3.4,设,P,为一个不可约、非周期、有限状态,Markov,链的转移矩阵,则必存在,N,使得当,n,N,时,P,(,n,),的所有元素都大于,0.,16,显然这是一个不可约、非周期、有限状态的,Markov,链,.,例,3.8,若,Markov,链有转移概率矩阵,17,常返与瞬过,定义：,则 表示从状态,i,出发在第,n,次转移时首次到达状态,j,的概率。,定义：,则 表示从状态,i,出发在第,n,次转移时首次回到状态,i,的概率。,18,定义：,则 表示从状态,i,出发最终到达状态,j,的概率,.,性质：,当,i,j,时,则,i,j,f,ij,0.,定义,3.5,如果,f,ii,=1,则称状态,i,是,常返,的,.,否则,即,f,ii,0,有,因此,24,例,3.9,考虑整数点上的随机游动,.,向右移动一格的概率为,p,向左移动一格的概率为,q,=1-,p,.,从原点,0,出发,则一步转移概率矩阵为,:,25,所以,利用,Stirling,公式知,当,n,充分大时,于是,因此,当,p,=0.5,时,当,p,0.5,时,即当,p,=0.5,时状态,0,是常返的,;,当,p,0.5,时,0,是瞬过的,.,26,定义,对常返状态,i,我们定义,T,i,为首次返回状态,i,的时刻,即,:,称作,常返时,.,记,则有,所以是首次返回,i,的期望步数,叫作状态,i,的,平均常返时,.,定义,一个常返状态,i,当且仅当,i,=,时称为是,零常返,的,当且仅当,i,0,（每一分量均大于,0,），则称此马尔链为一,正则链,(regular chain),补充：正则链与吸收链,29,定理,C1,.,若,A,为正则链的转移矩阵，则必有：,(1),，其中,W,为任一分量均大于零的随机矩阵；,(2),W,的所有行向量均相同,定理,C2.,记定理,C1,中,W,的行向量为,=(,1,m,),，则：,(1),对任意随机向 量,x,，有 ；,(2),是,P,的不动点向量,即,P,=,P,的不动点向量是唯一的,30,定义,C2.,状态,S,i,称为马氏链的,吸收状态,，若转移矩阵,P,的第,i,行满足：,P,ii,=1,，,P,ij,=0 (ji),定义,C3.,马氏链被称为,吸收链,，若其满足：,(1),至少存在一个吸收状态；,(2),从任一状态出发，经有限步转移总可到达某一吸收 状态,根据定义,C3,，,例,3.1,中,X,n,即,为一吸收链,31,具有,r,个吸收状态，,m,r,个非吸收状态的吸收链，它的,m,m,转移矩阵,P,的标准形式为,其中,I,r,为,r,阶单位阵，,O,为,r,(,m-r,),零阵，,R,为,(,m,-,r,),r,矩阵，,Q,为,(,m,-,r,)(,m,-,r,),矩阵,令,B,=(,I,Q,),-1,，称,B,为,基矩阵,32,定理,C3.,吸收链的基矩阵,B,中的每个元素，表示过程从一个非吸收状态出发到达每个非吸收状态的平均转移次数,定理,C4.,设,N,=,BC,B,为吸收链的基矩阵,C,=(1,1,1),T,，则,N,的每个元素表示从非吸收状态出发，到达某个吸收状态被吸收之前的平均转移次数,定理,C5.,设,F,=,BR,=(,f,ij,),，其中,B,为吸收链的基矩阵，,R,为,T,中的子阵，则,f,ij,表示从非吸收状态,i,出发，被吸收状态,j,吸收的概率,33,例,C1.1,(,竞赛问题,),甲乙两队进行一场抢答竞赛，竞赛规则规定：开始时每队各记,2,分，抢答题开始后，如甲取胜则甲加,1,分而乙减,1,分，反之则乙加,1,分甲减,1,分,(,每题必需决出胜负,),规则还规定，当其中一方的得分达 到,4,分时，竞赛结束求：,(1),甲队获胜的概率有多大？,(2),竞赛从开始到结束，平均转移的次数为多少？,(3),甲获得,1,、,2,、,3,分的平均次数是多少？,34,设甲取胜一题的概率为,p,(0,p,1),，,p,与两队的实力有关甲队得分有,5,种可能，即,0,，,1,，,2,，,3,，,4,我们分别记为状态,S,0,，,S,1,，,S,2,，,S,3,，,S,4,，其中,S,0,和,S,4,是吸收状态，,S,1,，,S,2,和,S,3,是非吸收状态过程以,S,2,作为初始状态根据甲队赢得,1,分的概率为,p,，建立转移矩阵,P,：,S,0,S,1,S,2,S,3,S,4,35,将上式改记为标准形 式,T,：,其中,36,计算基矩阵,B,：,记,q,=1-,p,，则,37,因为,S,2,是初始状态，根据定理,C3,，甲队获分为,1,，,2,，,3,分的平均次数为,又,38,根据定理,C4,，以,S,2,为初始状态，甲队最终获胜的平均转移次数为,又因为,根据定理,C5,，甲队最后获胜的概率,。,39,练习,（例,3.1,）,：老鼠在迷宫里找奶酪问题,老鼠在遇到猫之前找到奶酪的概率,40,41,