第六章 马尔可夫链.ppt

* * * * * * * * * * * * * * * * * 军用PKI体系结构及其关键技术 * 西安电子科技大学通信工程学院 * 军用PKI体系结构及其关键技术 * 西安电子科技大学通信工程学院 * 军用PKI体系结构及其关键技术 * 西安电子科技大学通信工程学院 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 一、极限定理 第三节 极限定理及平稳分布 记 则，如i是常返的，当 时为正常返的。 当 时为零常返的。 推论2：如i是遍历的(正常返的并且是非周期的)，则 一、极限定理 第三节 极限定理及平稳分布 记 则，如i是常返的，当 时为正常返的。 当 时为零常返的。 1，若j为非常返或零常返的，则 有 2，若j为常返的且周期为d，则 有 推论3（遍历性定理） 一、极限定理 第三节 极限定理及平稳分布 记 则，如i是常返的，当 时为正常返的。 当 时为零常返的。 推论5：有限状态的马尔可夫链，不可能全为非常返状态，也不可能有零常返状态。从而不可约的有限马尔可夫链的状态全为正常返的。 一、极限定理 第三节 极限定理及平稳分布 记 则，如i是常返的，当 时为正常返的。 当 时为零常返的。 推论6：若马尔可夫链有一个零常返态，则必有无限个零常返态。 状态性质判别法 i非常返 i零常返 i正常返 i遍历的 i正常返 i正常返且非周期 （即遍历） i正常返且周期为d 第三节 极限定理及平稳分布 例 设马氏链的状态空间I = {0,1,2,…}，转移概率为 试讨论各状态的遍历性。 第三节 极限定理及平稳分布 解 根据转移概率作出状态传递图 … 1/2 1/2 1/2 1/2 1/2 1/2 0 1 2 1/2 3 1/2 第三节 极限定理及平稳分布 从图可知，对任一状态 都有 ， 故由定理可知，I 中的所以状态都是相通的， 因此只需考虑状态0是否正常返即可。 … 故 从而0是常返态。 又因为 所以状态0为正常返。 又由于 故状态0为非周期的 从而状态0是遍历的。 故所有状态i都是遍历的。 因此只需考虑状态0是否正常返即可。 第三节 极限定理及平稳分布 二、平稳分布与极限分布 1，定义：设pij是马尔可夫链{Xn, n≥1}的转移概率。若 概率分布{pj, j ≥0}满足 则称{pj, j ≥0}为{Xn, n≥1}的平稳分布。记 第三节 极限定理及平稳分布 则平稳分布可表示为如下矩阵形式 显然有 即 若马尔可夫链{Xn, n≥0}的初始分布pj=P{X0=j}是平稳分布，则对任意的n，有 即Xn与X0有相同的 分布，这说明过程{Xn, n≥0}是平 稳过程。这也是称分布pj=P{X0=j} 为平稳分布的原因。 二、平稳分布与极限分布 第三节 极限定理及平稳分布 2，定义：若马尔可夫链是遍历的（即所有状态相通且均为周期为1的正常返态），则极限 称为马尔可夫链的极限分布。显然此时 二、平稳分布与极限分布 第三节 极限定理及平稳分布 定理：一个不可约非周期的马尔可夫链属于下列两种情况之一： 1，状态或全是滑过的（非常返的）或全是零常返的。此时对一切的 i, j 有 二、平稳分布与极限分布 第三节 极限定理及平稳分布 因而不存在平稳分布。 2，状态全是正常返态。即 此时 是平稳分布，且不存在任何其它的平稳分布。此时极限分布 即是平稳分布。 只证2，若马尔可夫链是遍历的,则 存在，且 下证 是平稳分布， 证明：（1）显然 二、平稳分布与极限分布 第三节 极限定理及平稳分布 利用C-K方程 从而 是平稳分布。 二、平稳分布与极限分布 第三节 极限定理及平稳分布 再证 是惟一的平稳