第三章 马尔可夫链
- 格式：doc
- 大小：396.00 KB
- 文档页数：19
第三章 马尔可夫链
一、马尔可夫链的概念
马尔可夫过程是一类有重要应用意义的随机过程，它具有如下特征：随机过程‘将来’所处的状态仅与‘现在’所处的状态有关，而与‘过去’曾处于什么状态无关。
马尔可夫过程按其状态和时间参数是离散还是连续的可以分成三类
（1） 时间和状态都是离散的马尔可夫过程，称为马尔可夫链。
（2） 时间连续、状态离散的马尔可夫过程，称为连续时间的马尔可夫链。
（3） 时间和状态都连续的马尔可夫过程。
本章介绍马尔可夫链
定义1 设}0,{nXn为随机序列，其状态空间为},,,{210iiiI，如果对任意正整数n及任意n+2个状态Iiiiin1210,,,,，有
},,,{110011nnnniXiXiXiXP
}{11nnnniXiXP
则称此随机序列}0,{nXn为马尔可夫链。
若将时刻n称为‘现在’，将时刻n+1称为‘将来’，而把0，1，2，……，n-1称为‘过去’。定义中的等式便可通俗解释为：在已知}0,{nXn ‘现在’所处的状态条件下，‘将来’所要达到的状态与‘过去’所经历的状态无关，这一特性常称为马尔可夫的无后效性。
例1．一个n级数字传输系统，每一级的输入和输出信号只取0或1两个值，每一级的输出是下一级的输入；并假定当一级输入为0时，其输出为0和为1的概率分别为p和1-p;当输入为1时，其输出为1和0的概率分别为p和1-p（见图）
令Xn表示第n级输出，则{ Xn,n≥0}便为一个马尔可夫链。
例2．从1，2，……，N数字中任取一个数，记为X0；再从1，2，……，X0数字中任取一个数，记为X1；再从1，2，……，X1中任取一个数，记为X2；依此类推，在1，2，……，Xn-1中任取一个数，记为Xn。可以证明{ Xn,n≥0}为马尔可夫链。
事实上，{ Xn,n≥0}的状态空间为I={1，2，……，N}，对任意正整数n，取n+1个状态Iiiiin,,,,210,由题意可知
故{ Xn,n≥0}为马尔可夫链。
二、转移概率
由马尔可夫链的无后效性和乘法公式有
},,,{1100nniXiXiXP
},,,{},,,{111100111100•nnnnnniXiXiXPiXiXiXiXP
},,,{}{11110011•nnnnnniXiXiXPiXiXP
}{}{}{}{000011221111iXPiXiXPiXiXPiXiXPnnnnnnnn
由此可见，马尔可夫链的统计特性完全由条件概率
}{11nnnniXiXP所确定，所以如何确定这个条件概率就显得非常重要，我们把这个条件概率称为一步转移概率。一般一步转移概率为}{1iXjXPnn，它表示系统在时刻n处于状态i的条件下，到时刻n+1转移到状态j的概率，记为)(npij。
定义2 称条件概率 }{)(1iXjXPnpnnij为马尔可夫链}0,{nXn在时刻n的一步转移概率。
一般，转移概率)(npij不仅与状态ji,有关，而且与时刻n有关，但当它与时刻n无关时，表示马尔可夫链具有平稳转移概率，即与起点无关，此时我们称马尔可夫链是齐次的。
定义3 如果对任意的Iji,，马尔可夫链的转移概率)(npij与n无关，则称}0,{nXn为齐次马尔可夫链，并记ijijpnp)(。
下面我们只讨论齐次马尔可夫链。
设P为一步转移概率ijp所组成的矩阵，状态空间},2,1{I，称
Pnnpppppp2222111211
为马尔可夫链的一步转移概率矩阵。
转移概率矩阵具有下面性质
（1）0ijp，Iji, （2）1Ijijp，Ii
称具有上面两条性质的矩阵为随机矩阵。
下面给出n步转移概率的概念
定义4 称条件概率
}{)(iXjXPpmnmnij，1,0,,nmIji
为马尔可夫链的n步转移概率，并称
P(n) )()(nijp
为马尔可夫链的n步转移概率矩阵。其中1,0)()(Ijnijnijpp。
当n=1时，PP)1(，规定
jijipij,1,0)0(，即)0(P为单位矩阵。
切普曼--柯尔莫哥洛夫方程
定理1 设}0,{nXn为马尔可夫链，则对任意正整数n，nl0，和状态Iji,，n步转移概率具有下列性质
（1）Iklnkjliknijppp)()()(（切普曼—柯尔莫哥洛夫方程）
（2）IkjkkkikIknijnnpppp112111)(
（3）)1n(n)(PPP
（4）n)n(PP 证明 （1）利用全概率公式和马尔可夫性，有
},)({}{)(iXjXkXPiXjXPpmnmIklmmnmnij
}),({iXjXkXPmIknmlm
IkmnmlmiXjXkXP},{
IkmnmlmmiXPjXkXiXP}{},,{
IkmlmmnmmlmmiXPkXiXjXPiXkXPiXP}{},{}{}{
IklmnmmlmkXjXPiXkXP}{}{
Iklnkjliklmpmp)()()()(Iklnkjlikpp)()(
（1）式是关于转移概率的一个重要结果，切普曼-柯尔莫哥洛夫方程（简称为C-K方程），直观上可以作如下解释：马尔可夫链{ Xn,n≥0}在时刻m处于状态i，经过n步，即在时刻m+n转移到状态j的过程可以视为它在时刻m处于状态i，先经过l步，即在时刻lm遍历所有状态),2,1(kk，然后再经过ln步，即在时刻m+n转到状态j的转移过程（见下图）
C-K方程的矩阵形式为 )()()n(PPPlnl
当1l时，即为（3）)1n(n)(PPP，再利用归纳法可证（4）
在（1）中令1,1kkl，得 Iknjkiknijppp)1()(11这是一个递推公式，逐步递推可证（2）
例3（随机游动）
设质点在线段上做随机游动。（见图）。每隔一秒钟移动一步。当质点处于‘O’点时，必然要以概率1向右移动一步至‘1’点；当质点处于‘4’点时，下一步必然以概率1向左移动一步至‘3’点；当质点处于其它点时，下一步便均分别以概率 向左、向右或停留在原地不动。
令Xn表示n次移动后质点所处的位置。显然，{ Xn,n≥0}为一齐次马尔可夫链，
其状态空间为I={0，1，2，3，4}
试求{ Xn,n≥0}的一步和二步转移概率矩阵：
解：按题意可知
同样可求得其它转移概率
等等。
于是便得一步转移概率矩阵
二步转移概率矩阵便为
齐次马尔可夫链的有限维分布
1. 一维分布
定义5 设}0,{nXn为齐次马尔可夫链，其状态空间为I，称下列一组概率
}{)0(0jXPpj，Ij
为}0,{nXn的初始分布，)0(jp称为初始概率。将其写成向量形式为
)),0(,),0(),0((0P21TNppp）（，称为初始概率向量。 定义6 设}0,{nXn为齐次马尔可夫链，其状态空间为I，称下列一组概率
}{)(jXPnpnj，Ij
为}0,{nXn的绝对分布，)(npj称为绝对概率。将其写成向量形式为
)),(,),(),((nP21TnpnpnpN）（，称为绝对概率向量。
定理2 设}0,{nXn为齐次马尔可夫链，则对任意Ij和1n，绝对概率具有下列性质
（1）Iinijijppnp)()0()(
（2）Iiijijpnpnp)1()(
（3）)n(TTP)0(P)n(P
（4）P)1n(P)n(PTT
证明 (1) }{)(jXPnpnjIinjXiXP},{0
IinijiIinppiXjXPiXP)(00)0(}{}{
（2）}{)(jXPnpnjIinnjXiXP},{1
IiijiIinnnpnpiXjXPiXP)1(}{}{11
（3）（4）式是（1）（2）的矩阵形式。
2．n维分布 定理3 设}0,{nXn为齐次马尔可夫链，对任意Iiiin,,,21和1n，则马尔可夫链的n维分布有
IiiiiiiiinnnnppppiXiXiXP1211)0(},,,{2211
此式证明利用了乘法公式和马尔可夫的无后效性。（见教材P45）
此式表明齐次马尔可夫链的有限维分布同样可由其初始分布和转移概率而确定。
例4． 某计算机经常出故障。现每隔15分钟观察一次此计算机的状态，共收集97次观察结果。用‘1’表示工作正常，用‘0’表示工作不正常，所测得数据如下：
令Xn表示第n个时间段计算机的状态。显然{ Xn,n≥0}为齐次马尔可夫链。其状态空间为I={0，1}。由统计的结果可得转移情况如下：
利用频率‘代替’概率的原理，可得转移概率
即得其转移概率矩阵为
假定初始分布为
则此计算机能连续工作四个时间段（即一小时）的概率便为
书上例题
例1 无限制随机游动
设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动的概率为q=1-p，这种运动称为无限制随机游动，以nX表示质点在时刻n所处的位置，则}0,{nXn是一个齐次马尔可夫链，试写出它的一步转移概率矩阵和k步转移概率。
解 显然状态空间为},2,1,0{I，一步转移概率矩阵为
pqpq0000P
设质点在k步转移过程中向右移了x步，向左移了y步，并且经过k步转移状态从i进入j，则
ijyxkyx
解出 2)(ijkx，2)(ijky
由于yx,是正整数，所以)(ijk必须是偶数，又在k步转移中哪x步向右哪y步向左是任意的，于是
