第四章马尔可夫链

.,第四章马尔可夫链,马尔可夫链定义一步转移概率及多步转移概率初始概率及绝对概率Chapman-Kolmogorov（C-K）方程遍历的马尔可夫链及平稳分布马尔可夫链状态分类,.,时间、状态都是离散的马尔可夫过程，称为马尔可夫链。例如：天气预报质点的随机游动,.,例如：在某数字通信系统中传递0，1两种信号，且传递需要经过若干级。因为系统中有噪声，各级将造成错误，若某级输入0，1信号后，其输出不产生错误的概率为p，产生错误的概率为1-p，则该级的输入输出状态构成了一个两个状态的马氏链。,.,马尔可夫链定义,设有随机过程Xn,nT，若对于任意的整数nT和任意的i0,i1,in+1I，条件概率满足,则称Xn,nT为马尔可夫链，简称马氏链,将来的状态只与当前状态有关，与过去状态无关,.,为了描述马尔可夫链（n+1）维分布率，最重要的是条件概率PXn+1=in+1|Xn=in.它表示在时刻n取in值的条件下，下一时刻n+1取值为in+1的概率（一步转移概率）,.,定义4.2称条件概率为马尔可夫链Xn,nT在时刻n的一步转移概率，其中i,jI，简称转移概率。,定义4.3若对任意的i,jI，马尔可夫链Xn,nT的转移概率与n无关，则称马尔可夫链是齐次马尔可夫链。我们只讨论齐次马氏链。并将记为,.,设P表示一步转移概率所组成的矩阵，则,称为系统状态的一步转移概率矩阵，它具有如下性质：,满足上述两个性质的矩阵成为随机矩阵,.,定义4.4称条件概率为马尔可夫链Xn,nT的n步转移概率，并称,为马尔可夫链的n步转移矩阵。规定,.,例题,设马尔可夫链Xn,nT有状态空间I=0,1，其一步转移概率矩阵为,求和两步转移概率矩阵P(2),.,解：,.,结论：n步转移矩阵,.,定理4.1设Xn,nT为马尔可夫链，则对任意整数n0，0L0非空，则称该集合的最大公约数d=d(i)=G.C.Dn:pii(n)0为状态i的周期。如d1就称i为周期的，如d=1就称i为非周期的。由定义知,当n不能被d整除时,pii(n)=0,引理4.1如i的周期为d，则存在正整数M，对一切nM，有pii(nd)0。,.,例题:设有4个状态的马尔可夫链,它的一步转移概率矩阵为:画出其状态传递图,该过程是否具有周期性?解:,.,所有状态周期为2,.,状态转移图,状态2和3具有相同的周期,但是状态2,3有区别.为此引入常返性的概念。,.,首中概率,它表示质点由i出发，经n步首次到达j的概率，表示为,同时我们令表示质点由i出发，经有限步终于到达j的概率。,.,定义4.7称状态i为常返的，如fii=1；称状态i为非常返的(滑过态)，如fii1。,对于常返态i，由定义知fii(n),n1构成一概率分布，此分布的期望值,表示由i出发再返回的i的平均返回时间。,.,定义4.8如ui0,即由状态i出发，经过n次转移以正的概率达到状态j，则称自状态i可到达状态j,并记为。反之如果状态i不能到达j，记为例如：无限制的随机游动中，每个状态都能够到达任何其它状态。当时在带有吸收壁的随机游动中，吸收状态却不同到达其他状态。,.,定义：互通有两个状态i和j，如果由状态i可以到达状态j,且由状态j也可以到达状态i，则称状态i，j互通。记为：定理:如果由状态i可以到达j状态,由j状态可以到达k状态,则由i状态可以到达k状态。证明：,.,状态i特性（常返和非常返）的判断准则：定理4.5(证明见P53)状态i常返的充要条件为：,状态i非常返的充要条件为：,.,零常返和正常返的判断准则：定理4.7以及推论状态i常返，则：（1）零常返（2）正常返,其中，周期为d时候,非周期时,（遍历）,(非周期的正常返称为遍历状态),.,定理4.9如果状态i,j互通，则：（1）i和j同为常返或非常返。如为常返，同为正常返或零常返。（2）i和j有相同的周期。,.,判断各状态的性质（从常返和周期性两方面）,.,解：,.,状态空间的分解,定义：状态空间I的子集C称为闭集，如果对任意及都有,定义：闭集C称为不可约的，如果C的状态互通。,定义：马尔可夫链称为不可约的，如果其状态空间不可约。,.,如果单个状态构成一个闭集，则称这个闭集为吸收态。它是比较小的闭集。（1）闭集意味着质点一旦进入闭集中，将永远留在该闭集中。（2）一个大的闭集可以包含几个小的闭集。,.,问：找出该马氏链中所有闭集，马氏链是否不可约？,例题4.11设马氏链Xn的状态空间I=1,2,3,4,5,转移矩阵为:,.,状态空间的分解定理：任一马尔可夫链的状态空间I，可唯一的分解成有限个或可列个互不相交的子集D,C1,C2,之和，使得每一Cn是常返态组成的不可约闭集；Cn中的状态同类，或全是正常返，或全是零常返。它们有相同的周期且fjk=1,j,kCn。D由全体非常返状态组成，自Cn中的状态不能到达D中的状态。,.,例题4.13.设I=1,2,6,转移矩阵为:试分解此链并指出各状态的常返性及周期性.,.,.,推论：(1)不可约的有限马尔可夫链必为正常返的(P63推论1)。(2)有限状态的不可约非周期马尔可夫链