10第四章马尔可夫链.ppt

第四章 马尔可夫链 马尔可夫链定义 一步转移概率及多步转移概率 初始概率及绝对概率 Chapman-Kolmogorov（C-K）方程 遍历的马尔可夫链及平稳分布 马尔可夫链状态分类 时间、状态都是离散的马尔可夫过程，称为马尔可夫链。 例如：天气预报 质点的随机游动 例如：在某数字通信系统中传递0，1两种信号，且传递需要经过若干级。因为系统中有噪声，各级将造成错误，若某级输入0，1信号后，其输出不产生错误的概率为p，产生错误的概率为1-p，则该级的输入输出状态构成了一个两个状态的马氏链。 马尔可夫链定义 马尔可夫链的状态分类 周期、非周期 常返、非常返 其中，常返分为正常返、零常返 非周期的正常返称为遍历状态 到达和互通 状态空间的分解 (1) 解: 显然遍历 设马尔可夫链的状态空间I={1,2,3,4,5,6,7,8,9}，状态转移图如下图 观察状态1 定义4.6 如集合{n: n≥1,pii(n)0}非空，则称该集合的最大公约数d=d(i)=G.C.D{n:pii(n)0}为状态i的周期。如d1就称i为周期的，如d=1就称i为非周期的。 由定义知,当n不能被d整除时,pii(n)=0 引理4.1 如i的周期为d，则存在正整数M，对一切n≥M，有pii(nd)0。 例题:设有4个状态的马尔可夫链,它的一步转移概率矩阵为: 画出其状态传递图,该过程是否具有周期性? 解: 所有状态周期为2 状态转移图 状态2和3具有相同的周期,但是状态2,3有区别.为此引入常返性的概念。 首中概率 它表示质点由i出发，经n步首次到达j 的概率，表示为 同时我们令 表示质点由i出发，经有限步终于到达j 的概率。 定义4.7 称状态i为常返的，如fii=1；称状态i为非常返的，如fii1。 对于常返态i，由定义知{fii(n),n≥1}构成一概率分布，此分布的期望值 表示由i出发再返回的i的平均返回时间。 定义4.8 如ui∞，则称常返态i为正常返的；如ui= ∞，则称常返态i为零常返的。 定理4.4 对任意的状态i,j以及 , 有： C-K方程与定理4.4都是马尔可夫链的关键公式,因为他们都可以把 分解成较低步的转移概率之和的形式. C-K方程 证明： 定义：到达 如果对状态i和j存在某个n （n≥ 1），使得pij(n)0,即由状态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的状态互通。 定义： 马尔可夫链称为不可约的，如果其状态空间不可约。 * * 设有随机过程{Xn,n∈T}，若对于任意的整数n∈T和任意的i0,i1, …,in+1∈I，条件概率满足 则称{Xn,n∈T}为马尔可夫链，简称马氏链 将来的状态只与当前状态有关，与过去状态无关 为了描述马尔可夫链（n+1）维分布率，最重要的是条件概率P{Xn+1=in+1|Xn=in}. 它表示在时刻n取in值的条件下，下一时刻n+1取值为in+1的概率（一步转移概率） 定义4.2 称条件概率 为马尔可夫链{Xn,n∈T}在时刻n的一步转移概率，其中i,j∈I，简称转移概率。 定义4.3 若对任意的i,j∈I，马尔可夫链{Xn,n∈T}的转移