马尔可夫链

(第七章)马尔可夫链马尔可夫链的概念及转移概率马尔可夫链的状态分类状态空间的分解遍历性与平稳分布马尔可夫过程的四种类型马尔可夫链时间、状态都离散马尔可夫序列时间离散、状态连续纯不连续马尔可夫过程时间连续、状态离散连续马尔可夫过程（或扩散过程）时间、状态都连续1马尔可夫链的概念及转移概率[定义]设有随机过程{Xn,nT}，若对于任意的整数nT和任意的i0,i1,…,in+1I，条件概率满足则称{Xn,nT}为马尔可夫链，简称马氏链。}{},,,{11110011nnnnnnnniXiXPiXiXiXiXP马氏性（无后效性）马尔可夫链的统计特性由以下条件概率所决定：}{},,,{11110011nnnnnnnniXiXPiXiXiXiXP}{}{}{}{},,,{}{},,,{},,,{00001122111111110011111100111100iXPiXiXPiXiXPiXiXPiXiXiXPiXiXPiXiXiXPiXiXiXiXPnnnnnnnnnnnnnnnnnnnn}{11nnnniXiXP},,,{1100nniXiXiXP马尔可夫链的n+1维联合概率分布：转移概率pij(n)不仅与状态i,j有关，而且与时刻n有关。当pij(n)与时刻n无关时，表示马尔可夫链具有平稳转移概率。[定义]称条件概率为马尔可夫链{Xn,nT}在时刻n的一步转移概率，其中i,jI，简称为转移概率。}{)(1iXjXPnpnnij齐次马尔可夫链[定义]若对任意的i,jI，马尔可夫链{Xn,nT}的转移概率pij(n)与时刻n无关，则称马尔可夫链是齐次的，并记为pij(n)为pij。一步转移概率矩阵性质：nnpppppp2222111211PIipIjipIjijij,1)2(,,0)1(（随机矩阵）n步转移概率[定义]称条件概率为马尔可夫链{Xn,nT}的n步转移概率，并称为马尔可夫链的n步转移矩阵。)1,0,,(},{)(nmIjiiXjXPpmnmnij)()(nijnpP规定：jijipij,1,0)0(n步转移概率的性质)(nijp[定理]设{Xn,nT}为马尔可夫链，则对于任意整数n0,0ln和i,jI，n步转移概率具有下列性质：)(nijpIklnkjliknijppp)()()()1(IkjkkkikIknijnnpppp112111)()2()1()()3(nnPPPnnPP)()4(C-K方程初始概率和绝对概率初始概率：)(},{0IjjXPpj绝对概率：)(},{)(IjjXPnpnj初始分布：},{}{Ijppjj绝对分布：},)({)}({Ijnpnpjj绝对概率向量：)0(,),(),()(21nnpnpnTP初始概率向量：,,)0(21ppTP绝对概率pj(n)的性质[定理]设{Xn,nT}为马尔可夫链，则对于任意整数n1和jI，绝对概率pj(n)具有下列性质：PPPPPP)1()()3()0()()3()1()()2()()1()()(nnnpnpnpppnpTTnTTIiijijIinijij马尔可夫链的几个简单例子[例1]二进制对称信道模型——是常用于表征通信系统的错误产生机制的离散无记忆信道模型。假设某级信道输入0,1数字信号后，其输出正确的概率为p，产生错误的概率为q，则该级信道输入状态和输出状态构成一个两状态的齐次马尔可夫链。0011ppqq一步转移概率矩阵：)1,0,(,,jijiqjippijpqqpP二步转移概率矩阵：22222)2(22qppqpqqpPP[例2]具有吸收壁和反射壁的随机游动设质点在线段[1,4]上作随机游动。假设它只能在时刻nT发生移动，且只能停留在1,2,3,4点上。当质点转移到2,3点时，它以1/3的概率向左或向右移动一格，或停留在原处。当质点移动到点1时，它以概率1停留在原处。当质点移动到点4时，它以概率1移动到点3。若以Xn表示质点在时刻n所处的位置，则{Xn,nT}是一个齐次马尔可夫链。描述马氏链的三种方式（1）状态转移图（2）转移概率矩阵（3）函数表达式01003/13/13/1003/13/13/10001P④①②③11/31/31/31/31/31/31吸收壁反射壁pij=f(i,j)[例3]设{Xn,nT}是一个马尔可夫链，其状态空间I={a,b,c}，转移矩阵为05/25/33/103/24/14/12/1P求：}{)2(};,,,{)1(204321bXcXPcXcXaXcXbXPnn},,,{)1(04321cXcXaXcXbXP}{/}{}{}{}{}{0001122334cXPcXPcXbXPbXcXPcXaXPaXcXPcbbccaacPPPP50152315341}{/},,,,{043210cXPcXaXcXbXcXP05/25/33/103/24/14/12/1P解：}{)2(2bXcXPnn二步转移概率矩阵：901720330176110315824540930172)2(PP61)2(bcP2马尔可夫链的状态分类设{Xn,n0}是齐次马尔可夫链，其状态空间I={0,1,2,…}，转移概率是pij，i,jI，初始分布为{Pj,jI}。786951112/31/3111111234（1）状态的周期性[定义]如集合{n:n1,pii(n)0}非空，则称该集合的最大公约数d=d(i)=G.C.D{n:pii(n)0}为状态i的周期。如d1就称i为周期的；如d=1就称i为非周期的。[定理]如果状态i的周期为d，则存在正整数M，对一切nM，有pii(nd)0。（2）状态的常返性首中概率——状态i经n步首次到达状态j的概率：1},11,,{)(niXnvjXjXPfmvmnmnij0)0(ijf系统从状态i出发，经有限步迟早会（首次）到达状态j的概率：1)(nnijijff10)(ijnijff常返性的定义2)称期望值为状态i的平均返回时间。1)(nniiifn1)若fii=1，则称状态i是常返的；若fii1，则称状态i是非常返的（或滑过的）。3)若i，则称常返态i是正常返的；若i=，则称常返态i是零常返的。4)非周期的正常返态称为遍历态。与的关系上式可用来求从状态i经n步首次到达状态j的概率：)(nijp)(nijf[定理]对任意状态i,jI及1n，有nkkjjknijnkknjjkijnijpfpfp0)()(1)()()(11)()()()(nkknjjkijnijnijpfpf周期的等价定义}0,1:{..}0,1:{..)()(niiniifnnDCGpnnDCG常返性的判别(根据pij(n))[定理]（1）状态i常返的充要条件为0)(nniip状态i非常返的充要条件为iinniifp110)(（2）若状态i是常返态，则i是零常返0)(limniinpi是遍历态01)(liminiinp（3）若i是周期为d的常返态，则indiindp)(lim0)(limniinp若i是非常返态，则马氏链状态分类图状态空间周期态非周期态常返态非常返态正常返态零常返态遍历态状态分类的判别0)(nniip常返态非常返态零常返态正常返态转移概率pij(n)首中概率fij(n)0)(nniip11)(iinniiff1)(inniinf11)(iinniiff0lim)(niinp0lim)(niinp1)(inniinf（3）可达关系与互通关系[定义]（1）若存在n0,使得pij(n)0，则称自状态i可达状态j，并记为ij。（2）若ij,且ji,则称状态i与状态j互通，并记为ij。[定理1]若ij,且jk,则ik。若ij,且jk,则ik。[定理2]若ij,则（1）i与j同为常返或非常返；（2）i与j同为正常返或零常返；（3）i与j有相同的周期。传递性互通关系的状态是同一类型[例4]设马尔可夫链的状态空间I={0,1,2,…}，其转移概率为分析各状态的类型。,1)0(00p解：Iipppiii,21,21,2101,00先考查状态0，,21)1(00p,210)(00npnn可见状态0是非周期的，因而状态0也是遍历的。,21)(00np021)(00limnnp由归纳法可知，(根据pij(n)来判断),21)2(00p状态0为常返态状态0为正常返态因为其它i0，故所有i也是遍历的。3状态空间的分解[定义]状态空间I的子集C，若对于任意iC及kC都有pik=0，则称子集C为（随机）闭集。若闭集C的状态互通，则称C为不可约的。若马氏链{Xn}的状态空间是不可约的，则称该马氏链为不可约。闭集的充要条件状态i为吸收态（pii=1）单点集{i}是闭集。[定理]C是闭集的充要条件是：对于任意iC及kC都有pik(n)=0,n1。[例5]设马氏链{Xn}的状态空间I={1,2,3,4,5}，转移矩阵为试分析其闭集及不可约性。000100000100100005.005.005.0005.0P④①②③1/21/21/211/211⑤{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,kCn.(jk)21CCDI[例6]设状态空间I={1,2,…,6}，转移矩阵为试分解此链，并指出各状态的常返性及周期性。2/10002/10000001003/103/13/1010000100000000100P}6,2{}5,3,1{}4{21CCDI2121102G0011000101G随机矩阵[定义]若矩阵(aij)的元素非负且对每个i都有，则称矩阵(aij)为随机矩阵。显然，k步转移矩阵是随机矩阵。)()(kijkpP1jija[定理]设C是I的一个闭子集，又是C上所得的k步转移子矩阵，则G仍是随机矩阵。Cjipkij,,)(G几个结论若马氏链有一个零常返态，则必有无限多个零常返态。有限状态的马氏链，不可能含有零常返态，也不可能全是非常返态。不可约的有限状态马氏链必为正常返态。4遍历性与平稳分布为周期正常返不确定，为遍历态，为非常返或零常返jjjpjnijn1,0)(lim)(nijp的极限：[定义]设齐次马氏链{Xn,n0}的状态空间为I，若对于一切i,jI，存在不依赖于i的极限，则称该马氏链具有遍历性，并称pj为状态j的稳态概率。遍历性)0()(limjnijnppj1不