第5讲-离散参数Markov链及其应用.ppt

第5讲：离散参数Markov链及其应用 5.1 离散参数Markov链的基本概念 5.2 离散参数Markov链的状态分类 5.3 离散参数Markov链的极限定理与平稳分布 5.4 离散参数Markov链的应用 例3：在重复独立贝努里实验中，每次实验有两种状态{0,1}，设{Xn}表示第n次实验中出现的结果，且P(Xn=1)=p， P(Xn=0)=q, 则{Xn}是MC，求n步转移概率矩阵？ 5.2 离散参数Markov链的状态分类 {Xn，n?0}是离散齐次MC，pij为转移概率，i, j?I，I={0,1,2,?}为状态空间 定义 状态i的周期d： d=gcd{n: 0} (最大公约数greatest common divisor) 如果d1，就称i为周期的， 如果d=1，就称i为非周期的 注1：互通关系满足：自反性、对称性、传递性，即互通是一种等价关系。 注2：按互通关系是等价关系，可以把状态空间 I 划分为若干个不相交的集合（或者说等价类），并称之为状态类。若两个状态互通，则这两个状态属于同一类。任意两个类或不相交或者相同。 注3：互通的两个状态必有相同的状态类型。 5.3 离散参数Markov链的极限定理与平稳分布 遍历链 若对一切的 存在，则称该 Markov链具有遍历性，此链又称为遍历链。 注： Markov链具有遍历性说明，不论从哪个状态出发，经过充分大的转移步数后，到达状态j的概率接近正常数pj。 平稳分布 设Markov链 具有转移矩阵 ，若存在一 概率分布 ，满足 则称 为该Markov链的平稳分布 注1： 注2：若MC具有平稳分布且平稳分布为初始状态的概率分布，则MC为平稳过程。 5.4 离散参数Markov链的应用 例：P138 首达概率 与n步转移概率 有如下关系式 定理5.3 对任意状态i, j及1? n ?，有 例 设马尔可夫链的状态空间I={1,2,3}，转移概率矩阵为 求从状态1出发经n 步转移首次到达各状态的概率 解 状态转移图如下 ，首达概率为 同理可得 定理5.4 状态i常返的充要条件为 如i非常返，当且仅当 常返性的判别与性质 定理5.5 设i常返且有周期为d，则 其中?i为i的平均返回时间，当?i=?时 推论 设i是常返状态，则 (1) i零常返 (2) i遍历 （1）判别是否常返态 （2）判别是否零常返态、正常返有（非）周期 状态的可达与互通 存在n0, 使 称状态i可达状态j，i?j; 状态i与状态j 互通，i?j：i?j且j?i 定理5.6 可达关系与互通关系都具有传递性，即 (1)若i?j ，j?k，则i?k (2)若i ? j ，j ? k，则i ? k 定理5.7 如i?j，则 (1) i与j同为常返或非常返，如为常返，则 它们同为正常返或零常返 (2) i与j有相同的周期 * * 简称马氏过程。 已知“现在”的条件下，“过去”与“将来”是独立的。 马氏性 （无后效性） 5.1 离散参数Markov链的基本概念 即 则称此马氏链为齐次马氏链（即关于时间为齐次） 初始分布 例1： 无限制随机游动 设质点在数轴上移动，每次移动一个点，向右移 动的概率为p，向左移动的概率为q，原地不动的 概率为r，这种运动无限制的随机游动。以Xn表示 质点在时刻n所处的位置，则{Xn，n?T }是一个 齐次马尔科夫链，试写出它的一步转移概率。 例2 不可越壁的随机游动 设一质点在线段[1，5 ]上随机游动，状态空间I={1，2，3，4，5}，每秒钟发生一次随机游动，移动的规则是： （1）若移动前在2，3，4处，则均以概率1/3向左 或向右移动一单位，或停留在原处； （2）若移动前在1处，则以概率1移到2处； （3）若移动前在5处，则以概率1移到4处。 试写出一步转移矩阵. 分析 故 1 2 3 4 5 其一步转移矩阵为 若将移动规则改为 （1）若移动前在2，3，4处，则均以概率1/2向左或向右 移动一单位； （2）若移动前在1，5处，则以概率1停留在原处。 因为质点在1，5两点被“吸收”， 故称 有两个吸收