第三章 马尔可夫链.doc

第三章 马尔可夫链一、马尔可夫链的概念马尔可夫过程是一类有重要应用意义的随机过程，它具有如下特征：随机过程将来所处的状态仅与现在所处的状态有关，而与过去曾处于什么状态无关。马尔可夫过程按其状态和时间参数是离散还是连续的可以分成三类（1） 时间和状态都是离散的马尔可夫过程，称为马尔可夫链。（2） 时间连续、状态离散的马尔可夫过程，称为连续时间的马尔可夫链。（3） 时间和状态都连续的马尔可夫过程。本章介绍马尔可夫链定义1 设为随机序列，其状态空间为，如果对任意正整数n及任意n+2个状态，有 则称此随机序列为马尔可夫链。若将时刻n称为现在，将时刻n+1称为将来，而把0，1，2，n-1称为过去。定义中的等式便可通俗解释为：在已知 现在所处的状态条件下，将来所要达到的状态与过去所经历的状态无关，这一特性常称为马尔可夫的无后效性。例1一个n级数字传输系统，每一级的输入和输出信号只取0或1两个值，每一级的输出是下一级的输入；并假定当一级输入为0时，其输出为0和为1的概率分别为p和1-p;当输入为1时，其输出为1和0的概率分别为p和1-p（见图）令Xn表示第n级输出，则 Xn,n0便为一个马尔可夫链。例2从1，2，N数字中任取一个数，记为X0；再从1，2，X0数字中任取一个数，记为X1；再从1，2，X1中任取一个数，记为X2；依此类推，在1，2，Xn-1中任取一个数，记为Xn。可以证明 Xn,n0为马尔可夫链。事实上， Xn,n0的状态空间为I=1，2，N，对任意正整数n，取n+1个状态,由题意可知故 Xn,n0为马尔可夫链。二、转移概率由马尔可夫链的无后效性和乘法公式有由此可见，马尔可夫链的统计特性完全由条件概率所确定，所以如何确定这个条件概率就显得非常重要，我们把这个条件概率称为一步转移概率。一般一步转移概率为，它表示系统在时刻n处于状态的条件下，到时刻n+1转移到状态的概率，记为。定义2 称条件概率 为马尔可夫链在时刻n的一步转移概率。一般，转移概率不仅与状态有关，而且与时刻n有关，但当它与时刻n无关时，表示马尔可夫链具有平稳转移概率，即与起点无关，此时我们称马尔可夫链是齐次的。定义3 如果对任意的，马尔可夫链的转移概率与n无关，则称为齐次马尔可夫链，并记。下面我们只讨论齐次马尔可夫链。设P为一步转移概率所组成的矩阵，状态空间，称P为马尔可夫链的一步转移概率矩阵。转移概率矩阵具有下面性质（1），（2），称具有上面两条性质的矩阵为随机矩阵。下面给出n步转移概率的概念定义4 称条件概率 ，为马尔可夫链的n步转移概率，并称 P(n) 为马尔可夫链的n步转移概率矩阵。其中。当n=1时，规定，即为单位矩阵。切普曼-柯尔莫哥洛夫方程定理1 设为马尔可夫链，则对任意正整数n，和状态，n步转移概率具有下列性质（1）（切普曼柯尔莫哥洛夫方程）（2）（3）（4）证明 （1）利用全概率公式和马尔可夫性，有（1）式是关于转移概率的一个重要结果，切普曼-柯尔莫哥洛夫方程（简称为C-K方程），直观上可以作如下解释：马尔可夫链 Xn,n0在时刻m处于状态，经过n步，即在时刻m+n转移到状态的过程可以视为它在时刻m处于状态，先经过步，即在时刻遍历所有状态，然后再经过步，即在时刻m+n转到状态的转移过程（见下图）C-K方程的矩阵形式为 当时，即为（3），再利用归纳法可证（4）在（1）中令，得 这是一个递推公式，逐步递推可证（2）例3（随机游动）设质点在线段上做随机游动。（见图）。每隔一秒钟移动一步。当质点处于O点时，必然要以概率1向右移动一步至1点；当质点处于4点时，下一步必然以概率1向左移动一步至3点；当质点处于其它点时，下一步便均分别以概率 向左、向右或停留在原地不动。令Xn表示n次移动后质点所处的位置。显然， Xn,n0为一齐次马尔可夫链，其状态空间为I=0，1，2，3，4试求 Xn,n0的一步和二步转移概率矩阵：解：按题意可知同样可求得其它转移概率等等。于是便得一步转移概率矩阵 二步转移概率矩阵便为齐次马尔可夫链的有限维分布1. 一维分布定义5 设为齐次马尔可夫链，其状态空间为I，称下列一组概率 ，为的初始分布，称为初始概率。将其写成向量形式为 ，称为初始概率向量。定义6 设为齐次马尔可夫链，其状态空间为I，称下列一组概率 ，为的绝对分布，称为绝对概率。将其写成向量形式为 ，称为绝对概率向量。定理2 设为齐次马尔可夫链，则对任意和，绝对概率具有下列性质（1）（2）（3）（4）证明 (1) （2）（3）（4）式是（1）（2）的矩阵形式。2n维分布定理3 设为齐次马尔可夫链，对任意和，则马尔可夫链的n维分布有 此式证明利用了乘法公式和马尔可夫的无后效性。（见教材P45）此式表明齐次马尔可夫链的有限维分布同样可由其初始分布和转移概率而确定。例4 某计算机经常出故障。现每隔15分钟观察一次此计算机的状态，共收集97次观察结果。用1表示工作正常，用0表示工作不正常，所测得数据如下： 令Xn表示第n个时间段计算机的状态。显然 Xn,n0为齐次马尔可夫链。其状态空间为I=0，1。由统计的结果可得转移情况如下：利用频率代替概率的原理，可得转移概率 即得其转移概率矩阵为 假定初始分布为 则此计算机能连续工作四个时间段（即一小时）的概率便为书上例题例1 无限制随机游动设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动的概率为q=1-p，这种运动称为无限制随机游动，以表示质点在时刻n所处的位置，则是一个齐次马尔可夫链，试写出它的一步转移概率矩阵和k步转移概率。解 显然状态空间为，一步转移概率矩阵为设质点在步转移过程中向右移了步，向左移了步，并且经过步转移状态从进入，则 解出 ，由于是正整数，所以必须是偶数，又在步转移中哪步向右哪步向左是任意的，于是 例2 赌徒输光问题两赌徒甲、乙进行一系列赌博，甲有元，乙有元，每赌一局输者给赢者1元，没有和局，直到两人中有一人输光为止，设在每一局中，甲赢的概率为，输的概率为，求甲输光的概率。这个问题实际上是带有两个吸收壁的随机游动，状态空间为，求质点从状态出发到达状态0先于到达状态c的概率。解 设表示甲从状态出发转移到状态0的概率，现要计算。由于0和c是吸收状态，故 由全概率公式 即 ，所以 这是一个差分方程，下面只讨论的情况，此时 令 ，则，即 ，所以 ， 由于甲、乙的地位是对等的，同样可计算出乙输光的概率为 上式表明甲输光的概率与乙的赌本成正比，所以赌本小者输光的可能性大（输赢等可能的情况下），又，表明必有一人要输光，赌博迟早要结束。例3 天气预报问题设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨、今日有雨，明日有雨的概率为0.5；昨日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日都无雨，明日有雨的概率为0.2；若星期一、星期二均下雨，求星期四下雨的概率。解 设昨日、今日都有雨称为状态0（记为RR），昨日无雨、今日有雨称为状态1（记为NR），昨日有雨、今日无雨称为状态2（记为RN），昨日、今日都无雨称为状态3（记为NN），于是此问题可看作是一个4状态的马尔可夫链，求现在处于状态0的条件下将来处于状态0或1的两部转移概率，下面求出一步概率转移矩阵（不可能事件）（不可能事件）（不可能事件）（不可能事件）同样方法可求出 ，所以一步转移概率矩阵为所以星期一、星期二均下雨，星期四又下雨的概率为 =0.49+0.12=0.61例4 带有吸收壁和反射壁的随机游动设质点在线段