马尔可夫链ppt课件.ppt

(第七章)马尔可夫链,马尔可夫链的概念及转移概率马尔可夫链的状态分类状态空间的分解遍历性与平稳分布,马尔可夫过程的四种类型,马尔可夫链时间、状态都离散马尔可夫序列时间离散、状态连续纯不连续马尔可夫过程时间连续、状态离散连续马尔可夫过程（或扩散过程）时间、状态都连续,1 马尔可夫链的概念及转移概率,定义 设有随机过程 Xn , n T ， 若对于任意的整数n T 和任意的 i0, i1, , in+1 I ，条件概率满足则称 Xn , n T 为马尔可夫链，简称马氏链。,马氏性（无后效性）,马尔可夫链的统计特性由以下条件概率所决定：,马尔可夫链的 n+1 维联合概率分布：,转移概率,ij(n) 不仅与状态 i , j 有关，而且与时刻 n 有关。当 pij(n) 与时刻 n 无关时，表示马尔可夫链具有平稳转移概率。,定义 称条件概率为马尔可夫链 Xn , n T 在时刻 n 的一步转移概率，其中 i , j I ，简称为转移概率。,齐次马尔可夫链,定义 若对任意的 i , j I ，马尔可夫链 Xn , n T 的转移概率 pij(n) 与时刻 n 无关，则称马尔可夫链是齐次的，并记为 pij (n) 为 pij 。,一步转移概率矩阵,性质：,（随机矩阵）,n 步转移概率,定义 称条件概率为马尔可夫链 Xn , n T 的 n 步转移概率，并称为马尔可夫链的 n 步转移矩阵。,规定：,n 步转移概率 的性质,定理 设 Xn , n T 为马尔可夫链，则对于任意整数n 0, 0 l n 和 i , j I ，n 步转移概率 具有下列性质：,初始概率和绝对概率,初始概率：,绝对概率：,初始分布：,绝对分布：,绝对概率向量：,初始概率向量：,绝对概率 pj(n) 的性质,定理 设 Xn , n T 为马尔可夫链，则对于任意整数n 1 和 j I ，绝对概率 pj (n) 具有下列性质：,马尔可夫链的几个简单例子,例1 二进制对称信道模型是常用于表征通信系统的错误产生机制的离散无记忆信道模型。假设某级信道输入0, 1数字信号后，其输出正确的概率为p，产生错误的概率为q，则该级信道输入状态和输出状态构成一个两状态的齐次马尔可夫链。,一步转移概率矩阵：,二步转移概率矩阵：,例2 具有吸收壁和反射壁的随机游动,设质点在线段1,4上作随机游动。假设它只能在时刻 nT 发生移动，且只能停留在1,2,3,4点上。当质点转移到2,3点时，它以1/3的概率向左或向右移动一格，或停留在原处。当质点移动到点1时，它以概率1停留在原处。当质点移动到点4时，它以概率1移动到点3。若以Xn 表示质点在时刻 n 所处的位置，则 Xn , n T 是一个齐次马尔可夫链。,描述马氏链的三种方式,（1）状态转移图,（2）转移概率矩阵,（3）函数表达式,pij = f ( i , j ),解：,二步转移概率矩阵：,2 马尔可夫链的状态分类,设 Xn , n 0 是齐次马尔可夫链，其状态空间 I = 0, 1, 2, ，转移概率是 pij ， i , j I ，初始分布为 Pj , j I 。,（1）状态的周期性,定义 如集合 n : n 1, pii(n) 0 非空，则称该集合的最大公约数 d = d(i) = G.C.D n : pii(n) 0 为状态 i 的周期。如 d 1 就称 i 为周期的；如 d = 1 就称 i 为非周期的。,定理 如果状态 i 的周期为d ，则存在正整数 M，对一切 n M ，有 pii(nd) 0 。,（2）状态的常返性,首中概率状态 i 经 n 步首次到达状态 j 的概率：,系统从状态 i 出发，经有限步迟早会（首次）到达状态 j 的概率：,常返性的定义,称期望值 为状态 i 的平均返回时间。,若 fii = 1，则称状态 i 是常返的；若 fii 1，则称状态 i 是非常返的（或滑过的）。,若 i ，则称常返态 i 是正常返的；若 i = ，则称常返态 i 是零常返的。非周期的正常返态称为遍历态。,与 的关系,上式可用来求从状态 i 经 n 步首次到达状态 j 的概率：,定理 对任意状态 i , j I 及 1 n ，有,周期的等价定义,常返性的判别(根据pij(n),定理 （1）状态 i 常返的充要条件为,状态 i 非常返的充要条件为,（2）若状态 i 是常返态，则 i 是零常返 ,i 是遍历态 ,（3）若 i 是周期为 d 的常返态，则,若 i 是非常返态，则,马氏链状态分类图,状态分类的判别,（3）可达关系与互通关系,定义 （1）若存在 n 0, 使得 pij(n) 0 ，则称自状态 i 可达状态 j ，并记为 i j 。（2）若 i j , 且 j i , 则称状态 i 与状态 j 互通，并记为 i j 。,定理1 若 i j , 且 j k , 则 i k 。若 i j , 且 j k , 则 i k 。,定理2 若 i j , 则（1）i 与 j 同为常返或非常返；（2）i 与 j 同为正常返或零常返；（3）i 与 j 有相同的周期。,传递性,互通关系的状态是同一类型,例4 设马尔可夫链的状态空间 I = 0, 1, 2, ，其转移概率为,分析各状态的类型。,解：,先考查状态0，,可见状态0是非周期的，因而状态0也是遍历的。,由归纳法可知，,(根据pij(n)来判断), 状态0为常返态, 状态0为正常返态,因为 其它i 0 ，故所有 i 也是遍历的。,3 状态空间的分解,定义 状态空间 I 的子集 C，若对于任意 i C 及 k C 都有 pik = 0 ，则称子集 C 为（随机）闭集。若闭集 C 的状态互通，则称 C 为不可约的。若马氏链 Xn 的状态空间是不可约的，则称该马氏链为不可约。,闭集的充要条件,状态 i 为吸收态（pii = 1） 单点集 i 是闭集。,定理 C 是闭集的充要条件是：对于任意 i C 及 k C 都有 pik(n) = 0 , n 1。,例5 设马氏链 Xn 的状态空间 I = 1, 2, 3, 4, 5 ，转移矩阵为试分析其闭集及不可约性。, 3 , 1, 4 , 1, 4, 3, 1, 4, 2, 3 都是闭集；其中 3 和 1, 4 是不可约闭集；,状态空间的分解,称 Cn 是基本常返闭集,定理 任一马氏链的状态空间 I ，可唯一地分解成若干个互不相交的子集 D, C1, C2, 之和，使得(1) D 由全体非常返态组成；(2) 每个 Cn 是常返态组成的不可约闭集；(3) Cn 中的状态同类（全为正常返或零常返），它们有相同的周期，且 fjk = 1，j, k Cn . ( j k ),例6 设状态空间 I = 1, 2, , 6 ，转移矩阵为试分解此链，并指出各状态的常返性及周期性。,随机矩阵,定义 若矩阵 (a ij ) 的元素非负且对每个 i 都有 ，则称矩阵 (a ij ) 为随机矩阵。显然，k 步转移矩阵 是随机矩阵。,定理 设 C 是 I 的一个闭子集，又 是 C 上所得的 k 步转移子矩阵，则 G 仍是随机矩阵。,几个结论,若马氏链有一个零常返态，则必有无限多个零常返态。有限状态的马氏链，不可能含有零常返态，也不可能全是非常返态。不可约的有限状态马氏链必为正常返态。,4 遍历性与平稳分布,的极限：,定义 设齐次马氏链 Xn , n 0 的状态空间为 I ，若对于一切 i , j I ，存在不依赖于 i 的极限，则称该马氏链具有遍历性，并称 pj 为状态 j 的稳态概率。,遍历性,平稳分布,定义 称绝对概率分布 j , j I 为马氏链的平稳分布，若它满足,j 与时间推移n无关。在任意时刻，系统处于同一状态的概率是相同的。,平稳分布的判别,定理 不可约、非周期马氏链是正常返的充要条件：存在平稳分布 j , j I ，且此平稳分布就是极限分布,推论1 不可约、非周期、有限状态的马氏链必存在平稳分布。,推论2 若不可约马氏链的所有状态是非常返或零常返的，则不存在平稳分布。,推论3 若 j , j I 是不可约非周期马氏链的平稳分布，则,遍历性 平稳分布,例7 （例4.16）设马尔可夫链的转移概率矩阵为P，求马氏链的平稳分布及各状态的平均返回时间。,解：,因为该马氏链是不可约的非周期有限状态，所以存在平稳分布。,各状态的平均返回时间分别为：,平稳分布为：,