《第四章马尔可夫链讲稿精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章马尔可夫链讲稿精选文档.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章马马尔尔可夫可夫链讲链讲稿稿本讲稿第一页，共十八页计算公式计算公式显然有显然有 定义定义 设设 为一马氏链，对任一状态为一马氏链，对任一状态i i与与j j，称，称经有限步（迟早）到达状态经有限步（迟早）到达状态j j的概率。的概率。为为自状态自状态i出发出发定义定义 如果如果 ，则称状态，则称状态i i是常返的。如果是常返的。如果 ，则称状，则称状态态i i是非常返的（或称为瞬时的）。如果马尔可夫链的任一状是非常返的（或称为瞬时的）。如果马尔可夫链的任一状态都是常返的，则称此链为常返马尔可夫链。态都是常返的，则称此链为常返马尔可夫链。本讲稿第二页，共十八页定义定义 设设i是一常返
2、态，则从是一常返态，则从i出发可经过出发可经过n 步首次返回步首次返回i，在在 的条件下的条件下 的分布列为的分布列为12nP由数学期望的定义，可得由数学期望的定义，可得 称称 为状态为状态i的平均返回时间。的平均返回时间。定义定义 设设i是常返态，如果是常返态，如果 ，则称状态，则称状态i是正常返态；是正常返态；如果如果 ,则称状态则称状态i是零常返态。是零常返态。如果状态如果状态i是非周期且正常返的，则称状态是非周期且正常返的，则称状态i是遍历的。是遍历的。本讲稿第三页，共十八页定理定理 对任何状态，有 证明：因为 本讲稿第四页，共十八页定理定理 状态状态i是是常返（常返（）的充要条件为）
3、的充要条件为系：系：如果状态如果状态i是非常返的充要条件是是非常返的充要条件是系：系：如果如果i是常返态，则是常返态，则（1）i零常返当且仅当零常返当且仅当（2）i遍历当且仅当遍历当且仅当定理：定理：设设i为常返状态，为常返状态，有周期有周期 ,则则此时有此时有本讲稿第五页，共十八页马氏状态分类图马氏状态分类图 状态分类判别法：状态分类判别法：（1）i非常返非常返（2）i零常返零常返且且（4）i遍历遍历 且（3）i正常返正常返本讲稿第六页，共十八页二、马氏链中的状态关系二、马氏链中的状态关系定义定义（可达）：（可达）：如果对于状态如果对于状态 i和和 j,总存在某个总存在某个 ，使得使得 ，则
4、称自，则称自i状态经过状态经过n步步可可以到以到达达j状态，状态，并记为并记为反之，若对所有的反之，若对所有的 有有 ，则自，则自i状态不可以到达状态不可以到达j状态，并记为状态，并记为可达具有传递性，即若 ,则证明:由 知，存在 使得再由C-K方程可知，因此1.可达与互通可达与互通本讲稿第七页，共十八页 例例 设一两状态设一两状态 马氏链具有以下转移概率矩阵马氏链具有以下转移概率矩阵 解：要讨论这一马氏链两个状态的可达性，可先求出它的 n步转移概率矩阵。由于对于所有的n,，故状态“1”不能到达状态“0”；而存在n使得故状态“0”可以到达状态“1”。讨论其状态的可达特性。讨论其状态的可达特性。
5、注：此题画状态转移图更直观本讲稿第八页，共十八页定义定义（互通）：（互通）：若自状态i可达状态j，同时自状态j也可达状态i，则称状态和状态互通，记为 互通是一种等价关系，即满足：（1）若 ，则 ,自返性（2）若 ，则 ，对称性（3）若 ，则 ，传递性我们把任何两个互通的状态归为一类。然后定义：定义定义 若Markov链只存在一个类，就称它是不可约的；否则称为可约的。本讲稿第九页，共十八页例例 无限制的随机游走问题。考虑一个质点在直线上作随机游走如果在某一时刻质点位于i,则下一步质点将以概率 向前游走一步到达i+1处，或以概率 向后游走一步到达i-1处。现规定，这一质点只能“向前”或“向后”游走
6、一步，并且经过一个单位时间它必须“向前”或“向后”游走。讨论其状态的互通性。解：如果以 表示n时刻质点的位置，则 是一个随机过程。而且，当 时，等在时刻n后质点所处的状态仅与 有关，而与质点在时刻n以前是如何到达i的无关故它是一个齐次马尔可夫链。状态空间 ，一步转移概率为从而一步转移概率矩阵为本讲稿第十页，共十八页 下面求n步转移概率 如在n次转移的结果是从i到j,n次转移中恰好向前游走m次，向后游走k次，则有 联立上两式求解可得 根据概率法则，不难求得n步转移概率为 其中 时，反映了在n，i，j之间存在的一种约束关系。由于对于满足要求的n，i，j，所以无限制的随机游走中的各个状态是互通的。本
7、讲稿第十一页，共十八页 引理1 对任意i和j，若 ，则存在正数 、及正整数l、m，使对任一正整数n，有、定理定理 若 ，则（1）i与j同为常返或同为非常返；（2）若i与j常返，则i与j同为正常返或同为零常返；（3）i与j或同为非周期的，或同为周期的且有相同的周期。本讲稿第十二页，共十八页定理定理的充要条件是证明：充分性：若 ，则根据到达的定义，总存在某个 ，使所以这样 ，至少有一个为正（不为0），所以必要性：若，则由至少有一个使，故 表示自状态i出发，在有限步内迟早要返回状态i的概率，是在0与1之间的一个数。本讲稿第十三页，共十八页三、状态空间分解三、状态空间分解 定义定义 设 ，若从V中任一
8、状态出发不能到达V外的任一状态，则称V为闭集。显然，对一切 和 有 若V中仅含有单个状态，则此闭集称为吸收态。它构成了一个较小的闭集。而整个空间构成一个较大的闭集。除了整个状态空间外，没有别的闭集的马尔可夫链称为不可约的马尔可夫链。此时整个空间的所有状态皆是相通的。闭集内任一状态，不论转移多少步，都不能转移到闭集之外的状态上去，即随着时间的推移，闭集内任一状态只能在闭集内部的状态之间转移。定理定理 马尔可夫链的所有常返状态构成的集合是一闭集。本讲稿第十四页，共十八页有限状有限状态态分解定理分解定理本讲稿第十五页，共十八页定理（分解定理）定理（分解定理）状态空间E必可分解为 其中N是全体非常返态组成的集合，是互不相交的常返态闭集组成。而且（1）对每一确定的k,内任意两状态相通；（2）与 ()中的状态之间不相通；本讲稿第十六页，共十八页例例 设齐次马氏链 的状态空间 ，其一步转移概率矩阵如下，试对该空间进行分解。解：根据一步转移概率矩阵，可画出如图所示的状态转移图。由图可知，而当 时，所以 ，可见状态1为正常返，且周期 。含有状态1的常返闭集为本讲稿第十七页，共十八页 同理，因为 ，在 时，所以可见状态6为正常返，且是非周期的。含有状态6的常返闭集为 状态2，6为遍历状态.由于 ，在 时，所以 。可见状态4为非常返。故本讲稿第十八页，共十八页