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