刘次华《随机过程及其应用（第三版）》 马尔科夫链.ppt

《刘次华《随机过程及其应用（第三版）》 马尔科夫链.ppt》由会员分享，可在线阅读，更多相关《刘次华《随机过程及其应用（第三版）》 马尔科夫链.ppt（46页珍藏版）》请在三一办公上搜索。

1、7 马尔可夫链,内容提要,马尔可夫链的概念及转移概率马尔可夫链的状态分类状态空间的分解 pij(n)的渐近性质与平稳分布,马尔可夫过程的四种类型,马尔可夫链时间、状态都离散马尔可夫序列时间离散、状态连续纯不连续马尔可夫过程时间连续、状态离散连续马尔可夫过程（或扩散过程）时间、状态都连续,7.1 马尔可夫链的概念及转移概率,定义 设有随机过程 Xn,n T，若对于任意的整数n T 和任意的 i0,i1,in+1 I，条件概率满足则称 Xn,n T 为马尔可夫链，简称马氏链。,马氏性（无后效性）,马尔可夫链的统计特性完全由以下条件概率所决定：,转移概率,pij(n)不仅与状态 i,j 有关，而且与

2、时刻 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 为马尔可夫链，则对

3、于任意整数n 0,0 l n 和 i,j I，n 步转移概率 具有下列性质：,初始概率和绝对概率,初始概率：,绝对概率：,初始分布：,绝对分布：,绝对概率向量：,初始概率向量：,绝对概率 pj(n)的性质,定理 设 Xn,n T 为马尔可夫链，则对于任意整数n 1 和 j I，绝对概率 pj(n)具有下列性质：,有限维概率分布,定理 设 Xn,n T 是马尔可夫链，则对任意 n 1和 i1,in I，有,马尔可夫链的有限维分布完全由它的初始概率和一步转移概率所决定。,马尔可夫链的几个简单例子,例 二进制对称信道模型是常用于表征通信系统的错误产生机制的离散无记忆信道模型。假设某级信道输入0,1数

4、字信号后，其输出正确的概率为p，产生错误的概率为q，则该级信道输入状态和输出状态构成一个两状态的齐次马尔可夫链。,一步转移概率矩阵：,二步转移概率矩阵：,例（例4.4）具有吸收壁和反射壁的随机游动,设质点在线段1,4上作随机游动。假设它只能在时刻 nT 发生移动，且只能停留在1,2,3,4点上。当质点转移到2,3点时，它以1/3的概率向左或向右移动一格，或停留在原处。当质点移动到点1时，它以概率1停留在原处。当质点移动到点4时，它以概率1移动到点3。若以Xn 表示质点在时刻 n 所处的位置，则 Xn,n T 是一个齐次马尔可夫链。,描述马氏链的三种方式,（1）状态转移图,（2）转移概率矩阵,（

5、3）函数表达式,吸收壁,反射壁,pij=f(i,j),例 设 Xn,nT 是一个马尔可夫链，其状态空间 I=a,b,c，转移矩阵为,求：,解：,二步转移概率矩阵：,7.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，对一

6、切 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，有,周期的等价定义,例（例4.8）设马尔可夫链的

7、状态空间 I=1,2,3，其转移概率矩阵为,求从状态1出发经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

8、k。,定理2 若 i j,则（1）i 与 j 同为常返或非常返；（2）i 与 j 同为正常返或零常返；（3）i 与 j 有相同的周期。,传递性,互通关系的状态是同一类型,例（例4.9）设马氏链的状态空间 I=0,1,2,，其转移概率为,分析各状态的类型。,解：,先考查状态0，,可见状态0为正常返，且是非周期，因而是遍历的。因为 i 0，故 i 也是遍历的。,7.3 状态空间的分解,定义 状态空间 I 的子集 C，若对于任意 i C 及 k C 都有 pik=0，则称子集 C 为（随机）闭集。若闭集 C 的状态互通，则称 C 为不可约的。若马氏链 Xn 的状态空间是不可约的，则称该马氏链为不可约

9、。,闭集的充要条件,状态 i 为吸收态（pii=1）单点集 i 是闭集。,定理 C 是闭集的充要条件是：对于任意 i C 及 k C 都有 pik(n)=0,n 1。,例（例4.11）设马氏链 Xn 的状态空间 I=1,2,3,4,5，转移矩阵为P，试分析其闭集及不可约性。,状态 3为吸收态，故 3 是闭集；1,4，1,4,3，1,4,2,3 都是闭集；3 和 1,4 是不可约闭集；因为 I 含有闭子集，故马氏链 Xn 不是不可约链。,分解1按照常返性和互通性进行,定理 任一马氏链的状态空间 I，可唯一地分解成有限个或可列个互不相交的子集 D,C1,C2,之和，使得（1）每个 Cn 是常返态组

10、成的不可约闭集；（2）Cn 中的状态同类（全为正常返或零常返），它们有相同的周期，且 fjk=1，j,k Cn；（3）D 由全体非常返态组成。自 Cn 中的状态不能到达 D 中的状态。,称Cn 是基本常返闭集,例（例4.13）设状态空间 I=1,2,6，转移矩阵为P，试分解此链并指出各状态的常返性及周期性。,随机矩阵,定义 若矩阵(a ij)的元素非负且对每个 i 都有，则称矩阵(a ij)为随机矩阵。显然，k 步转移矩阵 是随机矩阵。,定理 设 C 是闭集，又 是 C 上所得的 k 步转移子矩阵，则 G 仍是随机矩阵。,分解2对周期的不可约马氏链的分解,定理 周期为 d 的不可约马氏链，其状

11、态空间 C 可唯一地分解为 d 个互不相交的子集之和，即且使得自 Gr 中任一状态出发，经一步转移必进入 Gr+1 中（其中 Gd=G0）。,例（例4.14）设不可约马氏链的状态空间 C=1,2,3,4,5,6，转移矩阵为P，试对其状态空间进行分解。,周期性不可约马氏链的子链,定理 设 Xn,n 0 是周期为 d 的不可约马氏链，（1）若只在时刻 0,d,2d,上考虑 Xn，即得一新马氏链（子链），其转移矩阵，对此新链，每一子状态空间 Gr 是非周期的不可约闭集；（2）若原马氏链 Xn 常返，则子链 Xnd 也常返。,例（例4.15）设 Xn 是例4.14中的马氏链，已知 d=3，则 X3n,

12、n 0 的转移矩阵为,7.4 pij(n)的渐近性质与平稳分布,是否存在？是否与 i 有关？,对于转移概率 pij(n)的极限,（1）pij(n)的渐近性质,推论1 有限状态的马氏链，不可能全是非常返态，也不可能含有零常返态；不可约的有限马氏链必为正常返的。,定理 若 j 非常返或零常返，则,推论2 若马氏链有一个零常返态，则必有无限多个零常返态。,fij(r)的定义,自状态 i 出发，在时刻 n=r(mod(d)首次到达 j 的概率记为：,显然，,正常返态的渐近性,定理 若 j 正常返，周期为 d，则对任意 i 及 0 r d1，有,推论 对于不可约、周期为 d 的正常返马氏链，其状态空间为

13、 C，则对任意 i,j C，有,常返或到达的平均次数,定理 对于任意状态 i,j，有,推论 若 Xn 不可约常返，则对任意 i,j，有,（2）平稳分布,定义 称绝对概率分布 j,j I 为齐次马氏链的平稳分布，若它满足,平稳分布,定理 不可约非周期马氏链是正常返的充要条件：存在平稳分布，且此平稳分布就是极限分布,推论1 有限状态的不可约非周期马氏链必存在平稳分布。,推论2 若不可约马氏链的所有状态是非常返或零常返的，则不存在平稳分布。,推论3 若 j,j I 是不可约非周期马氏链的平稳分布，则,例（例4.16）设马尔可夫链的转移概率矩阵为P，求马氏链的平稳分布及各状态的平均返回时间。,解：,因为该马氏链是不可约的非周期有限状态，所以存在平稳分布。,各状态的平均返回时间分别为：,平稳分布为：,