1、1第四章第四章 马尔可夫链马尔可夫链v马尔可夫链定义马尔可夫链定义v一步转移概率及多步转移概率一步转移概率及多步转移概率vChapman-Kolmogorov方程方程v初始概率及绝对概率初始概率及绝对概率v马尔可夫链状态分类马尔可夫链状态分类v遍历的马尔可夫链及平稳分布遍历的马尔可夫链及平稳分布24.1 马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率一、马尔可夫链的概念一、马尔可夫链的概念 nT，n，aaXnXnttXaaItXn, 2 , 1 , 0, 2 , 1 , 0,)(, 2 , 1 , 0,2121即参数空间为：移可列个时刻发生状态转且过程只在之一，则所能取的状态必为所处状态
2、记为：在每一时刻而的状态空间为假定马尔可夫过程3即条件概率满足：时刻以前的状态无关过程在而与时刻的状态有关只与过程在的概率时刻处在任一状态在定义：若过程,)(. 1mmakmtXkmimkmmmkmimikmiimimikmaXaXPaXaXaXaXP/,/1111简称马氏链。为马尔可夫链则称此随机过程，nXn0,42、马氏链的转移概率、马氏链的转移概率kmmpaXaXPijimjkm,/kmmpakmkamijji,：状态的转移概率，记为转移到时刻步，在状态经时刻处于为马氏链在iajamkm称条件概率称条件概率氏链。下面我们仅讨论齐次马次的，无关，则称马氏链为齐与若有关，与一般均为正整数mk
3、mmpkmjikmmpkmjiijij,53、一步转移概率及矩阵、一步转移概率及矩阵即得一步转移概率在上面转移概率中，取1k/1,1imjmijijaXaXPmmpp构成的矩阵由所有的一步转移概率ijp称为马氏链的一步转移概率矩阵称为马氏链的一步转移概率矩阵nnppppppP21222112116IjaiijjiijijIapIaapp1)2(,0) 1 (具有性质：矩阵称为随机矩阵。性质的、，满足和为即矩阵中任一行元素之个状态是必然事件，转移到状态空间的某一即从) 2() 1 (1ia74.多步转移概率的确定多步转移概率的确定 npnpnpnpnpnpnP：naXaXPnmmpnpnnknn
4、imjnmijij2222111211/,) 1 (步转移概率矩阵为对应的步转移概率：即得时、在转移概率中取：，nP即也满足性质也为随机矩阵)( IanpIaanpiIaijjiijj. 1)2(,. 0) 1 (8通常我们还规定：通常我们还规定： jijimmppijijij01,0(2)、切普曼、切普曼柯尔莫哥洛夫方程柯尔莫哥洛夫方程 （Chapman-Kolmogorov） IarjirijjinrknpkpnpI，aan，nX)(, 00,有：整数则对任意的为齐次马氏链定理：设方程。简称柯尔莫哥洛夫方程，此乃有名的切普曼kc knPkPnP或9ramjaiakmnm直观解释对照图10
5、imIarkmimjnmrkmimimIajnmrkmimimjnmimimjnmijaXPaXaXaXPaXaXPaXPaXaXaXPaXPaXaXPaXaXPnprr,/,/马尔可夫性有：证明：利用概率公式及11 knpkpaXaXPaXaXPrjIairrkmjnmIaimrkmrr/用矩阵形式表示为： knPkPnPnPnPnPPPPnPPPPnnPPn，Pk)()2() 1 ()3(3) 1 () 1 ()2(2) 1()(132为任意整数时有：一般当时：时有：则在上式取 表明一步转移概率是最基本的，它确定了马氏链的状态转移的统计规律。125、初始概率与绝对概率、初始概率与绝对概率
6、。和为和分布和绝对分布，简记为马氏链的初始和绝对概率，并分别称为马氏链的初始概率和，和分别称为马尔可夫链定义：设)()0(),(),0()()()0(,0,) 1 (0nppIanpIapIaaXPnpaXPpnXjjjjjjjjnjjjn写成向量形式:),(,),(),()(),0(,),0(),0()0(2121npnpnpnpppppjj13(2) 绝对概率与初始概率的关系绝对概率与初始概率的关系)()0()()()0()() 1 (nPpnpnppnpIaijiij或具有性质：，绝对概率和意的为马尔可夫链，则对任定理：设)(10,npnIanXjjnPnpnppnpnpIaijiji)
7、1()()1()()2(或1a2a01nnja14)()0(/,)() 1 (000nppaXaXPaXPaXaXPaXPnpijIaiijnIaiIajnijnjiii证： 表明表明n时刻的绝对概率分布完全由初始分布时刻的绝对概率分布完全由初始分布和和n步转移概率所确定。步转移概率所确定。 IaijiinjnIainIajninjnjiiipnPaXaXaXPaXaXPaXPnp) 1(/,)2(11115（3）马氏链的有限维分布）马氏链的有限维分布 IaiiiiiiniiiiininnnnpppaXaXaXPnIaaa，nX1121210,1,0,21有：和则对任意的为齐次马氏链定理：设I
8、aiiiiiiiiniiiniiiiiIaiiniiIainiiinnnnininppppaXaXaXaXPaXaXaXPaXaXPaXPaXaXaXUPaXaXaXP121111121121)0(,/,/,1101020101021证：16nnnnnniiiiiiniiiiiiiiniippaXaXaXaXPpppaXaXaXP：11002111001002110/,)2()0(,) 1 (推论总结：1）齐次马氏链多步转移概率可由一步转移概率确定； nPnP)(2) 绝对概率可由初始概率及n步转移概率确定Iaijijinppnp)()0()(3)有限维分布可完全由初始概率及一步转移概率确定。
9、17为随机游动。则称有相同的分布，令变量序列，且是整数值独立随机例：随机游动，设0,0210210nXXnnkkn是时齐马氏链。随机游动，随机游动是质点的位置，则表示在时刻，于是次移动的长度为整数间质点移动一次，第，每隔一个单位时为运动的质点，初始位置上作点在直线上的整数格点随机游动可以解释为质0,0,000nXnXnXkXnnnkknk18111100110011110010,/,1nnnnnnnnniXiXiXPiXiXiXPiXiXiXiXPiii，n和整数对任意的.,121101100101100nnnnnnnnniiPiiiiiPiiiiiP111/nnnnnnniiPiXiXP同理
10、：ijnnnijpijPiXjXPp1/一步转移概率为：19是一随机过程。时质点的位置，则表示时刻若以格到达向左移一或以概率右移动一格到达向，则下一步质点以概率如某一时刻质点位于，点在直线上作随机游动无限制的随机游动：质例0,111.nXnX，ipq，ipinn，I21012 其状态空间为：齐次马氏链。为随机游动，它是一个则次向左移动一格第，次向右移动一格第令nknnkXkk01,1几种特殊的随机游动20IjiijpIipqppp：iiiiii, 1, 110 ,01,1,一步转移概率为)(npnij步转移概率下面求它的次，则次，向左次转移中向右如果，次转移的结果是从，而向右的概率为，向左的概
11、率为可能已知每次转移只有两种21mmnjinpq，ijmmnmm) 1(121212,221ijnmijnm2112121)(,mnCmmnijnmm：是任意的，选取方法为步向左步向右，哪步中哪偶数，且在必须是只能取整数，所以由于为奇数为偶数为奇数为偶数nnqpCnpijnijnqpCnpnnnniimmmnij0,)(0,)(22112222例 带一个吸收壁的随机游动它的一步转移概率为：，即非负整数集合，其状态空间为：，这样的状态称为吸收态停留在这个零状态了，时，就点一旦到达仅作一点改变，即当质其规律如上例，这里动质点在直线上作随机游, 2 , 1 , 00,IXnIiiIjiijppIii
12、qpppiiiiii, 1, 1, 110, 1001,1,1iip充要条件是注：状态为吸收状态的23pqpqP000001210210一步转移矩阵为：矩阵为：吸收状态，则一步转移两状态为，其中状态空间为动。若随机游动的带两个吸收壁的随机游例aaI0, 2 , 1 , 024100000000000000000001pqqpqPajpjpppaiiijpaiqpaippajjaaiiiiii0001111, 1, 1011110001,1,25用此模型可描述赌徒输光问题用此模型可描述赌徒输光问题，求甲输光的概率。，输的概率为的概率为甲赢光为止。设在每一局中局，直到两人中一个输者一元，没有和元，
13、每赌一局输者给赢赌徒乙有元，列赌博，赌徒甲有两赌徒甲、乙进行一系pqpba1解：这是带两个吸收壁的随机游动，其状态空间为：状态的概率。状态先于到达出发到达点，现在问题是求质点从，cabaccI0, 2 , 1 , 026，由全概率公式：，是吸收状态，故和，由于即要计算的概率，出发转移到状态表示甲从状态设01000caiuucuiu1i1ii0bapq 11, 2 , 1,11ciqupuuiii和事件的概率。后再输光”这两事件的处于状态）去输了一局（概率为后再输光”和“他接下），处于状态概率为“他接下去赢了一局（等于元开始赌到输光的概率含义为：甲从有11iqipi27程式实质上是一个差分方由于
14、) 1 ( , 1 qp 21, 2 , 111ciuuruuiiii 30, 10cuu，pqr边界条件为其中cuuuiuuuuuuuuciuuuurcciiiiii010101201112, 1, 2 , 1)2(1令等差数列式：由的情况，先讨论281, 2 , 11ciciuic，uuc1100得代入最后一式将baau，b，qp，b故乙输光的概率为：由于甲、乙地位对称、性大，即赌本小者输光的可能成正比赌本甲输光的概率与乙的情况下在表明babca：uaia1,求得甲输光的概率为令赌博迟早要结束。人要输光，表明甲、乙中必有一由于1bauu29 )4(1121110111rrruuuruuru
15、uqprckckiickiiikc式得：由的情况。，即现讨论cccrrurruuuk11111111, 0, 0110有由于令30 ccbbccaacckkrrrurrruakckrrru1,11, 2 , 1,14得甲输光的概率令式得代入!, 1光两人中总有一个人要输由bauu31104,103,102,101)0(4 , 3 , 2 , 1, 2 , 1 , 0, 4 , 3 , 2 , 1pInXnXnn，若间为：为齐次马氏链，状态空次抛球后拿球人标号。表示如图示，抛球规律标号为四人相互抛一球，人的：例(1)已知开始第一人拿球，经三次传球后又回到 第一人的概率；(2)开始第一人拿球，经三
16、次传球后又回到第一 人的概率；(3)经三次传球后第一人拿球的概率；(4)经三次传球后，又回开始拿球人的概率。32 031313121021031310312102101P1342 9491319161316131319194916131613122PP33 92277277277187911879127727792277187911879133PP911/1)3() 1 (0311XXPp901911011/111, 1)2(03030XXPXPXXP34512771049110327710291101)3()0(1)3()3(14131iiippXPp45892104911039210291
17、101)3()0(,)4(414130iiiiippiXiXP35。，传输错误的概率为：为：设每步传输正确的概率需经过若干个级每个数字的传输的通信系统和例：传输数字10110910qp，pqqpPI，nX，nXnn101 , 00,：其一步转移概率矩阵为且状态链是一两状态的齐次马氏则步传输出的数字表示第以传输后的误码率；真率与三级求系统二级传输后的传设，p9 . 0) 1 (3610)0(1)0()2(0001XPp，XPp设初始分布又已知系统经n级传输后输出为1,问原字符也是1的概率是多少?qppqqpPPnPnn21, 1)(有相异的特征根：由于步转移概率矩阵解：先求出由线性代数知识,可将
18、P表示成对角阵37qp0010021212121212121ee，对应的特征向量：即求出21212121,21eeH令：38nnnnnnnqpqpqpqpHHHHPHHP2121,21212121,212110111于是则244. 01 . 09 . 02121)3()3(820. 01 . 09 . 02121)2()2(9 . 0) 1 (3011020011ppppp别为：三级传输后的误码率分的传真率与时，系统经二级传输后当39的概率为：，原发字符也是输出为级传输后知系统经根据贝叶斯公式，当已11)2(n nnnnnqpqpnppnppnppXPXXpXPXXP121)0()()0(01
19、1/111/1111010111000一般可表示为：一步转移概率矩阵氏莲对于只有两个状态的马，401,0 ,1110babbaaP利用类似的方法,可得n步转移概率矩阵为 bbaababaababbanpnpnpnpPnPnoooon1110)(1111 对齐次马尔可夫链,虽然一步转移概率能够完全决定马尔可夫链的统计规律，但仍有许多理论上和实际上的问题需要我们作进一步的讨论。414.2 马尔可夫链的状态分类马尔可夫链的状态分类一一.状态的分类状态的分类态进行分类。我们依赖概率性质对状，初始分布为：，转移概率为空间是齐次马氏链，其状态假设IjpIjipInXjijn),0(, 2 , 1 , 00
20、,中，情况要复杂得多。周期。但在随机性运动即声响元素的最大公约数，也是中这其中。的集合，则单位：分钟响时刻表示，若令分钟发生音乐声响的钟例如每隔有时会呈现出周期性周期：确定性机械运动TTT30,60,30, 0)(30,. 142图所示：状态间的转移规律如下。空间例如：设马氏链的状态9 , 2 , 1I 给出如下定义：受确定性问题的启发，的最大公约数。，是，而但，虽然，对正数的可能步数再返回状态出发从状态由图易见12202022,12,10, 8 , 6 , 41,1,1111nnnppTT3132430. 01,3 ,2 ,ndpMnMdnpnndinddddid，i，iiii有对一切一定有
21、对任何的，当然这并不意味着回到状态步，系统是不可能来说，除非经对则说明的周期若为状态由定义可知 0, 1.01npnnDCGdnpnniiii：状态的周期，记为：该集合的最大公约数为非空，则称，：定义：如集合。是周期的，周期为状态非周期的。对上例来说为，则称为周期的；如，称通常，如21,11idid，则称无周期。，其周期，即若对任意，不定义为空集的：注：对于使0)(10)(, 1npninpnniiii44 是否两个具有相同周期的状态所表现出来的性质基本一致呢?下例可说明并非如此。，状态转移图如下：例：设4 , 3 , 2 , 1I。后，它再也不能返回到转移到状态则不然，当，而状态出发经两步必
22、定返回到，但由状态的周期都为与状态由图可知232233232，。，我们引入常返性概念为了区别这样两种状态45简称首达概率。的概率，步首次到达状态出发，经为自状态，而称：，：即的时刻。出发首次进入状态状态为从，称随机变量、定义：对任意两个状态首达概率jniniXjXnvjXPnTPnfnjXiXnTjiTjimnmvmijijnmmijij1/11)(1,min. 246 jijiiiiijivnijnnpppiXnvjXjXPnft112111/11 ,00作出发时刻，则无关。所以，如果以刻知，首达概率与出发时注：由齐次马氏链性质的条件概率。出发经有限步可达，表示从出发，迟早要到达状态它表示从
23、状态，即的条件概率经有穷步后终达状态的条件下，氏链位于状态另一个重要概念是：马jijiTPnfffjiijnijijij1)(47不复返了。有限多次，然后就一去只返回链以概率是非常返时，；当无穷次返回态时，链以概率为常返出发，当直观解释，若链从状态常返iiiii11”“。非常返的，如为；称状态为常返的，如定义：称状态常返性概念11. 3iiiififi下：马氏链的状态转移图如例.212121213231148 也为常返的。，即状态，2121)2( ,21)(, 0) 1 (212222122221nnnnnffnnff为非常返的；即状态故，由图知：对一切400)(4444,f,nfn 也为非常
24、返的；即状态，故31321032)1 (333333f,nn,ff 为常返的；即状态，11212121212) 1 (1111111111fffff49 。出发返回的平均返步数表示了从状态的数学期望知概率分布，且由构成一从定义知，对常返状态iTnTPnfnnfiiiiiiiii)(, 2 , 1,给出如下定义：不同情形，为了区分有限与无穷的遍历状态。非周期的正常返态称为为零常返的。则称常返态反之，如为正常返的；，则称常返态定义：如iiii50 321232122111112221111nnnnnnnfnnf如上例，故它们都是遍历状态。，又因其周期都是都是正常返态与状态故状态1,2151的关系。
25、与)()(. 4npnfijij)()()(,1,1knpkfnpnjinkjjijij有：及定理：对任意状态i0knjj)()(, 11 ,/, 11 ,/, 11 ,/)(100101knpkfjXkvjXiXjXPiXjXkvjXPiXjXjXkvjXPiXjXPnpnkjjijkvnknkvnknkvonij证：52 率之和的形式。分解成较低步的转移概可以把的关键性公式，它们方程及此定理是马氏链npkcij11)()()()(1)0(nkjjijijijjjknpkfnpnfnkp，取0)(1.0)(.nfnnDCGnpnDCGiiii，：周期的等价定义：53000,321332211
26、qppqqpP，I转移的矩阵为：间例：设马氏链的状态空1p2p3p2q3q1q的概率。步转移首次到达各状态出发经求从状态n10, 12,1,2,)(1313131121mmnppqmmnqqpqnfmm540, 12,1,2,)(1212121131mmnqqpmmnppqpnfmm同理：1, 121,210)(321231321321312312132111mmnqqpqqppqppmmnppqqqqppn，nfmmmm55判别常返状态及性质如何用常返性的判别及其性质二)(.npij 111,100iiiiniiiiniiffnpifnpi则非常返如为常返的充要条件为：定理：状态 sFsPn
27、fnpfpiiiiiiii与的母函数为与，再设证：规定0)0(, 1)0(561)()()()()(1nknpkfnpnfnpiinkiiiiijij的关系有：与由1)()(1)()(00sskfsFsskpsPkkiikkii有：求和并对两边乘以于是对1,10ns，sn57)(11)()()(1)(sFsPsPsFsP，故即)()()()()()()()()(01111sPsFsknpskfsknpskfsknpkfsnpknkniikkiiknkniikkiinniikiinnii58 0100)()(lim1)(1)()(100)(niisniiNnniiiinpsPNssPsnpsPs
28、npNsnp，则有再令，不减，故在上式中先令时，由于当有：正整数与给定的，故对任意的因为01)()(limniiiisfnfsF类似地可证得：59命题得证！则若即可得：再根据常返状态的定义两边令在000)(111)(11)(1)(11)(niiiiiinniiiinp，ffnpnp，ssFsP60下面解释这个定理的结论：的次数表示马氏链状态位于，若iiXiXnnnnn001 首先令随机变量)(/11/0000000000npiXiXPiXPiXEiXEiXEniinnnnnnnn而的平均次数。返回出发再实际上表示了马氏链从可见iinpnii0)(61。穷极限的平均次数将有一个有非常返时，则返回
29、为而当状态的次数将无限地增加；下去时，返回续为常返且过程无限地继定理式告诉我，若状态iifiiii11是非常返的。则状态若是常返的；则状态若结论：i，npi，npniinii00)()2()() 1 (62面的定理。可以不加证明地给出下零常返还是遍历的呢判断它是为常返时，如何进一步对于确知状态?i0,)(limiiiiiindidndpd，i时当的平均返回时间为其中则常返且有周期定理：设状态01)(lim) 2(0)(lim) 1 (iiiniinnpinpii为遍历状态；为零常返为常返，则设状态由此定理立即得推论：63 0lim0)(,mod00lim) 1 (npnpdndndndpiii
30、niiiiini，故必然有整除时不能被周期而当，由为零常返则如证：.0)(lim, 0)(lim矛盾则由是正常返，而反之，若iiiniindndpinp 为正常返态。，即则说明；反之，若，由上面定理得为遍历，即如inpnpdiiiiiniiin0, 01lim01lim1)2(64为遍历的。即为非周期正常返态，故状态比较得与定理式且iiddndpndpiiiniiin1)(lim1)(lim状态分类判别法状态分类判别法状态分类判别法常返态正常返零常返非常返态)(0 nnpiinnpii0 0niinp 0niinp65三三.状态之间的关系状态之间的关系(可达、互通可达、互通)。且，如果互通，并
31、记为与；称状态，使如果存在某个，并记作可达状态定义：称状态ijjijijinpnjijiij0)(0。则如果；则即如果关系都具有传递性定理：可达关系与互通kikjjikikjji,66kimlmplpmplpmlpkcmpmkjlpljiIrjkijrkirikjkij, 10)()()()()(:0)(10)(1且方程由，使，即存在，使，即存在证： 将可达关系的证明,正向用一次，反向用一次，就可得出互通关系的传递性。67互通关系的状态是同一类型.有相同的周期。与同为正常返或零常返；为常返，则它们同为常返或非常返，如与则定理：如果jijij，i)2() 1 ( 00)()()()()(0)(,
32、 0)(1niinjjiiijiijijjjiijnpmnkpnpmpnpkpmnkpkcnkpmpmkji方程，有于是，对任意正整数，使与，故存在正整数证：因为68 也是常返的；因此，状态更有，故则为常返若j，npmnkpnpinjjnjjnii000)(,或同为有限。为无穷相互控制，所以它们同与有类似地0000)()()()(njjniinjjniijjiinpnpnpmnkpnpmnkp，69 为常返的；即，为常返，则若inpnpjniinjj00 也非常返，反之也真；故为非常返，则由若jnpnpinjjnii00也为零常返。为零常返，则若同理也是零常返的。再由为零常返，则若ij，jnp
33、npmnkpnpijjnjjiiiin0)(lim)(0)(lim70 。，故也能证得：；由对称性，则应有的周期为即状态的最大公约数：整除，设集能被整除，所以整除又能被既能被故而，有的，则对任一使的周期证明：设jiijjijjjiiiijjiijjidddddddjnpnndmknmkdmkpnpmknpnnpdi00, 00)(1)2(71础。这是分解状态空间的基态具有相同的性质此定理说明：相通的状.Iippp，Iiii,21,21,2121001,00转移概率为：，间为例：设马氏链的状态空21212121212121210722111101000000000011122121,21)(,81212121)3(,412121)2(,21) 1 (, 0 xxxxnxnfnffffnnnnnnnnn进一步常返故一般有由上图易知考查状态73 状态进行判别即可。的的识别，只需对最简单此例说明，对互通状态也是遍历的。，故烦，但由定理知，因较求的，对其它状态非周期的，因而是遍历，所以它是为正常返状态，由于可见iinfifii0021) 1 (000
