7马尔可夫链.ppt

7马尔可夫链.ppt

《7马尔可夫链.ppt》由会员分享，可在线阅读，更多相关《7马尔可夫链.ppt（39页珍藏版）》请在冰点文库上搜索。

马尔可夫链,马尔可夫链的概念及转移概率马尔可夫链的状态分类状态空间的分解遍历性与平稳分布,马尔可夫过程的四种类型,马尔可夫链时间、状态都离散马尔可夫序列时间离散、状态连续纯不连续马尔可夫过程时间连续、状态离散连续马尔可夫过程（或扩散过程）时间、状态都连续,1马尔可夫链的概念及转移概率,定义设有随机过程Xn,nT，若对于任意的整数nT和任意的i0,i1,in+1I，条件概率满足则称Xn,nT为马尔可夫链，简称马氏链。

马氏性（无后效性）,马尔可夫链的统计特性由以下条件概率所决定：

马尔可夫链的n+1维联合概率分布：

转移概率,pij（n）不仅与状态i,j有关，而且与时刻n有关。

当pij（n）与时刻n无关时，表示马尔可夫链具有平稳转移概率。

定义称条件概率为马尔可夫链Xn,nT在时刻n的一步转移概率，其中i,jI，简称为转移概率。

齐次马尔可夫链,定义若对任意的i,jI，马尔可夫链Xn,nT的转移概率pij（n）与时刻n无关，则称马尔可夫链是齐次的，并记为pij（n）为pij。

一步转移概率矩阵,性质：

（随机矩阵）,n步转移概率,定义称条件概率为马尔可夫链Xn,nT的n步转移概率，并称为马尔可夫链的n步转移矩阵。

规定：

n步转移概率的性质,定理设Xn,nT为马尔可夫链，则对于任意整数n0,0ln和i,jI，n步转移概率具有下列性质：

初始概率和绝对概率,初始概率：

绝对概率：

初始分布：

绝对分布：

绝对概率向量：

初始概率向量：

绝对概率pj（n）的性质,定理设Xn,nT为马尔可夫链，则对于任意整数n1和jI，绝对概率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,nT是一个齐次马尔可夫链。

描述马氏链的三种方式,

（1）状态转移图,

（2）转移概率矩阵,（3）函数表达式,pij=f（i,j）,解：

二步转移概率矩阵：

2马尔可夫链的状态分类,设Xn,n0是齐次马尔可夫链，其状态空间I=0,1,2,，转移概率是pij，i,jI，初始分布为Pj,jI。

（1）状态的周期性,定义如集合n:

n1,pii（n）0非空，则称该集合的最大公约数d=d（i）=G.C.Dn:

pii（n）0为状态i的周期。

如d1就称i为周期的；如d=1就称i为非周期的。

定理如果状态i的周期为d，则存在正整数M，对一切nM，有pii（nd）0。

（2）状态的常返性,首中概率状态i经n步首次到达状态j的概率：

系统从状态i出发，经有限步迟早会（首次）到达状态j的概率：

常返性的定义,称期望值为状态i的平均返回时间。

若fii=1，则称状态i是常返的；若fii1，则称状态i是非常返的（或滑过的）。

若i，则称常返态i是正常返的；若i=，则称常返态i是零常返的。

非周期的正常返态称为遍历态。

与的关系,上式可用来求从状态i经n步首次到达状态j的概率：

定理对任意状态i,jI及1n，有,周期的等价定义,常返性的判别（根据pij（n）,定理

（1）状态i常返的充要条件为,状态i非常返的充要条件为,

（2）若状态i是常返态，则i是零常返,i是遍历态,（3）若i是周期为d的常返态，则,若i是非常返态，则,马氏链状态分类图,状态分类的判别,（3）可达关系与互通关系,定义

（1）若存在n0,使得pij（n）0，则称自状态i可达状态j，并记为ij。

（2）若ij,且ji,则称状态i与状态j互通，并记为ij。

定理1若ij,且jk,则ik。

若ij,且jk,则ik。

定理2若ij,则

（1）i与j同为常返或非常返；

（2）i与j同为正常返或零常返；（3）i与j有相同的周期。

传递性,互通关系的状态是同一类型,例4设马尔可夫链的状态空间I=0,1,2,，其转移概率为,分析各状态的类型。

解：

先考查状态0，,可见状态0是非周期的，因而状态0也是遍历的。

由归纳法可知，,（根据pij（n）来判断）,状态0为常返态,状态0为正常返态,因为其它i0，故所有i也是遍历的。

3状态空间的分解,定义状态空间I的子集C，若对于任意iC及kC都有pik=0，则称子集C为（随机）闭集。

若闭集C的状态互通，则称C为不可约的。

若马氏链Xn的状态空间是不可约的，则称该马氏链为不可约。

闭集的充要条件,状态i为吸收态（pii=1）单点集i是闭集。

定理C是闭集的充要条件是：

对于任意iC及kC都有pik（n）=0,n1。

例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,kCn.（jk）,例6设状态空间I=1,2,6，转移矩阵为试分解此链，并指出各状态的常返性及周期性。

随机矩阵,定义若矩阵（aij）的元素非负且对每个i都有，则称矩阵（aij）为随机矩阵。

显然，k步转移矩阵是随机矩阵。

定理设C是I的一个闭子集，又是C上所得的k步转移子矩阵，则G仍是随机矩阵。

几个结论,若马氏链有一个零常返态，则必有无限多个零常返态。

有限状态的马氏链，不可能含有零常返态，也不可能全是非常返态。

不可约的有限状态马氏链必为正常返态。

4遍历性与平稳分布,的极限：

定义设齐次马氏链Xn,n0的状态空间为I，若对于一切i,jI，存在不依赖于i的极限，则称该马氏链具有遍历性，并称pj为状态j的稳态概率。

遍历性,平稳分布,定义称绝对概率分布j,jI为马氏链的平稳分布，若它满足,j与时间推移n无关。

在任意时刻，系统处于同一状态的概率是相同的。

平稳分布的判别,定理不可约、非周期马氏链是正常返的充要条件：

存在平稳分布j,jI，且此平稳分布就是极限分布,推论1不可约、非周期、有限状态的马氏链必存在平稳分布。

推论2若不可约马氏链的所有状态是非常返或零常返的，则不存在平稳分布。

推论3若j,jI是不可约非周期马氏链的平稳分布，则,遍历性平稳分布,例7（例4.16）设马尔可夫链的转移概率矩阵为P，求马氏链的平稳分布及各状态的平均返回时间。

解：

因为该马氏链是不可约的非周期有限状态，所以存在平稳分布。

各状态的平均返回时间分别为：

平稳分布为：