第四章 马尔可夫链

第四章马尔可夫链随机过程在不同时刻下的状态之间一般具有某种关系，马尔可夫（Markov ）过程就是 描述一类状态之间具有某种特殊统计联系的随机过程.Markov过程在近代物理学、生物学、 管理科学、信息处理与数字计算方法等领域都有重要的应用.按其状态和时间参数是连续的 或离散的，它可分为三类：（1）时间、状态都是离散的Markov过程，称为Markov链；（2） 时间连续、状态离散的Markov过程，称为连续时间的Markov链；（3）时间、状态都连续 的Markov过程.本章主要讨论Markov链，有关连续时间的Markov链的相关理论将在下章 讨论.4.1马尔可夫链的概念和例子独立随机试验模型最直接的推广就是 Markov链模型，早在1906年俄国数学家Markov对它进行研究而得名，以后Kolmogorov、Feller、Doob等数学家发展了这一 理论.4.1 .1 Markov链的定义假设Markov过程Xn g T的参数集T是离散时间集合，即T = 0,1,2, ，相应X可能取值的全体组成的状态空间是离散状态集/ = i ,i,i , . n0 12 定义4.1设有一随机过程Xn,n g T，若对于任意整数n g T和任意i0,i,七g I， 条件概率满足P X = i I X = i , X = i, , X = i = P X = i I X = i n+1 n+10 0 11n nn+1n+1n n则称X , n g T为离散时间的Markov链，简称Markov链（Markov chains）或马氏链. 从定义可以看出：Markov链具有Markov性（即无后效性），如果把时刻n看作现在，那么，n +1是将来的时刻，而0,1,2, ,n-1是过去的时刻.Markov性表示在确切知道系统 现在状态的条件下，系统将来的状况与过去的状况无关，而且Markov链的统计特征完全由 条件概率P乂+1 = in+11 乂广in所决定.因此，如何确定这个条件概率，是研究Markov链 理论和应用中十分重要的问题之一.4.1.2转移概率定义4.2称条件概率p （n） = P Xn+1 = j I Xn= i（4.1）为Markov链Xn, n g T在时刻n的一步转移概率，其中i, j g I，简称转移概率 （transition probability）.一般地，转移概率p （n）不仅仅与状态i, j有关，而且与时刻n有关，如果p （n）不依 赖时刻n时，则称Markov链具有平稳转移概率.定义4.3若对任意i, j e I，Markov链X, n g T的转移概率pn）与n无关，贝1称Markov链是齐次的（或称时齐的）（time - homogeneous），并记p （n）为p .下面只讨论齐次Markov链，并且通常将“齐次”两字省去.定义4.4设P表示一步转移概率P所组成的矩阵，且状态空间I = 1,2, ，则ijP11P12. P1nP - p p . p 21222nI称为系统状态的一步转移概率矩阵(transition、.probability matrix），它具有性质：（1）p。 0, i, j g I ；（2）Sp - 1,i g I.jeI（2）式说明一步转移概率矩阵中任一行元素之和为1，通常称满足性质（1）（2）的矩阵为随机矩阵.定义4.5称条件概率（4.2）p：n) PX j I X i,i, j g I,m 0,n 1为Markov链X , n g T的n步转移概率，并称P（ n）=（p：n）为Markov链X , n g T的 n步转移矩阵.其中pjn） 0, S pjn） -1，即P（n）也是一个随机矩阵.jeI特别地，当n -1时，p；i）= p。，此时，一步转移矩阵P（1）= P.我们还规定Markov链n步转移概率满足重要的Chapman - Kolmogorov方程（简称C - K方程）。定理4.1设X , n g T为Markov链，则对于任意整数n 1,0 l 0)为时刻 n 的绝对概率向量，称 PT (0) = (p, p2,)为初始概率向量.定理4.2设Xn, n e T为.Markov链，则对于任意j e I和n 1，绝对概率具有下面的性质：(1) p (n) =Z ppjn)；(2) p (n) = p (n 1)pieI(4.6)(4.7)证明(1)pj (n) = P X=j = Z P X 0 = i, X=jieI=2 PX = j l X = iPX = i = E p p(nieIieI(2)p.(n) = PXn = j = 2PXn=j,Xn 1 = ii eI2 PX = j l X = iPX= i = 2 p (n-1)pieIieI(4.6)式表明n时刻的绝对概率分布完全由初始分布和n步转移概率所确定，(4.7)式 表明n时刻的绝对概率分布完全由n-1时刻的绝对概率分布和一步转移概率所确定.更一般地，Markov链的有限维分布完全由初始分布和一步转移概率所确定.定理4.3设Xn, n e T为Markov链，则对于任意 ,七e I和n 1，有(4.8)PX = i, X =i = Zp.p. .p.11n n .了 i ii1in-1inieI.证明 利用全概率公式和Markov性P X广 V -，Xn= d= P X = i, X = i,X = i ieI=2 PX0 = i, X1 = iU,X = i X0 = iPX1 = i1l X0 = iPX=i i X 0 = i,X 1 = i J=i l X = i ( Markov 性)= PX0 = iPX1 = i l X0 = iPX=p.p.p. .p.i % 队 i i .r 1 12 n-1 n ieI4.1.4 Markov链的一些简单例子例4.1直线上无限制的随机游动(random walk)考虑在直线作随机运动的质点，每次移动一格，向右移动的概率为p，向左移动的概 率为q = 1 - p，这种运动称为无限制随机游动，以X.表示时刻n质点所处的位置，则 Xn,n e T是一个齐次Markov链，写出它的一步和k步转移概率.解Xn,n e T的状态空间I = 0, 1,2, ，一步转移概率矩阵为p00p.j设在第k步转移中向右移动了 %步，向左移动了 y步，且经过k步转移状态从i进入j，则k +(j - i)k (j - i)因此x = -，y = -由于兀y都只能整数，所以k 土 (j - i)必须是偶数，于是pj)=1Cxpxqy, k + (j - i)为偶数 k0,k + (j - i)为奇数例4.2带有一个吸收壁(absorbing barrier)的随机游动考虑随机游动，但状态空间为I = 0,1,2, ，而且一旦当X计=0后，X+1就停留在0这个状态上，这样的状态称为吸收状态，则Xn,n = 0,1,2, 也是一个齐次Markov链，p = p,i ,i+10是状态空间的端点(壁)，例4.3带有两个吸收壁的随机游动它的一步转移概率为p, i-1 = q = 1 - p ,i Z1; P00 = 1-因此，这一随机游动为带有一个吸收壁的随机游动赌徒输光问题p = p,p = q = 1 p ,1 i a 1; p = pi ,i+1i ,i100aa 0为齐次 iii inMarkov链，状态空间 I = 0,1,2, ，转移概率 p = r , p = b，r + b =1; p = b，000 01000ii+1ip = r, p = a (i 1)其中 a ,b 0,a + r + b = 1.称这种Markov链为生灭链ii i ii-1ii ii i i例4.7设Markov链乂昨,n 0的状态空间/ = 1,2,3，一步转移矩阵为34P = 13 V30 1/40 )133/4 )初始分布为P (0) = “p2,p3)=f 111)4,2,4)计算 P X1 = 2, X2Pt (2) = Pt (0) P 2 =F16 7/36 U/487/1616 3613; 48却6 13/3631/48 /f 113 230=,I576 576=21 X0 =1,PX0=3,X1 = 2, X2 = 1，并求出它的绝对分布.解P X1 = 2, X 2 = 21 X 0 = 1 = P X1 = 21 X 0 = 1P X 2 = 21 X 0 = 1, X1 = 2,.3 1 1=P X1 = 21 X 0 = 1P X 2 = 21 X1 = 2 = p12 p22 =彳 x -=-PX = 3,X = 2,X = 1 = p p p =-Lx!x! = -!-0123 32 214 4 348X2的绝对分布(绝对概率向量i例4.8(应用实例)设有一只传输数字0和1的串联系统.设每一级的传真率(输出数 字与输入数字相同的概率)为0.9，误码率为0.1.假定每隔一个单位时间传输一级，X。是第一级的输入，X1是第一级的输出，Xn是第n级的输出，心E ,n 0是齐次Markov链，状态空间I = 0,1，步转移概率矩阵为P=f 0.9 0.1系统经六级传输后的误码率P1与p1(6).假定初始分布p=Z，求已知系统经n级传输后的输出为1而原发出字符 也是1的概率P X 0 = 11 X = 1先求出n步转移概率矩阵为P( n)(1 12 + 2 X 程1 - - X 0.8n 2 21 - - X 0.8n2 211一 + 2 2X 0.8n(1) 有六步转移概率矩阵P (6)得到误码率P01 (6) = P10(6) = 2 - 2 X 0.86 = 0.369 容易看出，当n T8时，误码率P01(n) = P10(n) = | 2 x 0.8 2.当 n = 16时，误码率 高达47.2% .这表明，即使传输数字0和1之间的简单信号，经过级传输后效果与不考虑输 入信号时相差无几.(2) 由于事件X0= 0,X=1构成样本空间的一个划分，因此，由Bayes公式P X 0 = 01 X1=1=P X. = 1P X = 11 X. = 1P X 0 = 0P X = 1|0 X 0 = 0+P X 0 =01P X = 11 X 0 = 1P1(0) p11( n)p (0) p (n) + p (0) p (n)0011111 1-+-2一二x 0.8n + x2 2)1 -X 2 nn、X 0.8n)T1A-+ - X 0.8n2 2)=L +L X 0.8n2 2这表明，在串联传输系统中，经多级传输后得到的信号可信度很低.4.2马尔可夫链的状态分类对齐次Markov链代表的系统进行研究时通常要讨论两类问题：一是瞬态分析，二是稳 态分析.瞬态分析是讨论在某一固定时刻n时系统的概率特性，即求n步转移概率或绝对概率；稳态分析是讨论当n T8 (或n充分大)后系统的概率特性，即n-s时，p (n)的极 ij限是否存在，若存在又与状态的关系如何，极限概率是否能构成概率分布等要解决这些问 题，就需要对状态进行分类，本节将对齐次Markov链进行状态分类，有关状态空间的分解 理论将在下节讨论.4.2.1常返态与非常返态假设Xn,n 0是齐次Markov链，其状态空间I = 0,1,2, ，转移概率p,i, j e I，初始分布p , i e I.我们按其概率特性对状态进行分类. i 定义4.8 Xn, n 0是齐次Markov链，如果存在正整数n，使p?) 0，则称状态i可到达状态j，记为i - j.反之，对一切正整数n，pjn) = 0，称状态i不能到达状态j， 记i j .如果i j, j i，则称状态i和j是相通状态(communicating state)，记i f j.相通是一种等价关系，即（自返性）i f i ；（对称性）若i f j，则j f i ；（1）（2）(3)（传递性）若i j，且j k，则i f k.定义4.9如集合（n: n 1, p,） 0非空，则称该集合的 最大公约数（greatestcommondivisor )d = d(i) = G - C - D n: p(n) 0ii为状态i的周期，如d 1就称i为周期的（periodic ），如果d = 1就称i为非周期的.定理4.4如i的周期为d，则存在正整数M，对一切n M，有p（nd） 0定义4.10设（Xn 0是齐次Markov链，其状态空间I = （0,1,2, 对i, j g I，令T = min n: X0 = i, X = j, n 1(4.9)称T为从状态i出发首次到达状态j的时刻，或称自i到j首达时（first - hitting - time）. ij显然，U一个随机变量，它的取值是系统从状态，出发，使Xn=j的最小正整数n ,如果这样的n不存在，就规定气=8f(n)= P T = n I X = i, n = 1,2,它表示系统自状态i出发，经过n步首次到达j的(条件)概率.显然，j = P T = n I X0 = i= P X = j, X 丰 j,k = 1,2,，n - 1I X0 = i定义4.11令（4.10）又令f = fjn）= P T 3 1 X 0 = J，则fj表示系统自状态i出发（在有限时间内） n=1迟早达到状态j的概率.显然，0 fjn） f 1，有p（n）= X f 11）p 曲） ij ij jj l=1（4.11）证明 p(n)= P(X = j I X0 = i = P(T n, X = j I X0 = i= p(T = l, X = j I X = il=1= Xp(T = 11 X0 = i.P(X = j IT = l,X0 = il=1= fj)PX广顶 IX广 i, X 1 丰顶，X 1 丰顶,Xjj* l=1=j 1 Xl=f( i)p xij nl=1j = f( l)P( n-l) ij jjl =1(4.11)的直观概率意义是：Markov链从状态i出发经过n步转移到j的概率，就是从i出 发经过l (l n)步转移首次到达j ,再从j出发，经过n -1步转移又回到j (其中 l = 1,2, ,n)这样一些事件的和事件的概率.定义4.12如果七=1，则称状态j是常返的(recurrent)；如果七 1iiiiiiii iik =0两边乘以sn，并对n 1求和，若记 P(n)和f(n)的母函数分别为P ( s )和F ( s)，因此iiiiP (s) -1 = P (s) F (s)注意到当0 s 1时，F(s) f. 1，因此 iiP (s) = 1,0 s 11 - F (s)显然，对任意的正整数N都有 P(n)sn P(s) p(n),0 s 1iiiin=0n=0且当s个1时P(s)不减，在上式中先令s个1，再令N T8，得到lim P (s)=s T1 P (n) iin=0同理可得lim F （s） = f （n） = f . s T1 iiiin=0定理得证.4.2.2正常返与零常返常返态又可以进一步分为正常返与零常返状态.设i是一个常返状态，则从i出发可以经过n步（n = 1,2,）首次返回i，气在X。= i条件下的分布列为Tii12 n pf iif ii fin） 由数学期望的定义七=ET = nf（ n），称目1为状态i的平均返回时间.n=1定义4.13设i是一个常返状态，如果R 0.n* ii Pi下面我们不加证明地总结出关于状态分类的判别法:（2）（1）i 非常返= p（n） 3 0 f 0 = f = 1 且 p 0i（4.12）（4.13）（4.14）（4.15）（4.16）（4.17）（4.18）II n=1定理4 .9如果i I j，则(1) i和和j或同为常返态，或同为非常返态;(2) 在常返的情形，i和j或同为正常返态，或同为零常返态;(3) i和j或同为非周期的，或同为周期的且有相同的周期.证明(1)由i I j，按照可达定义，必存在正整数Z和n，使得pj) = a 0, p(n) =。 0由CK方程，总有p(l +m+n) p()p(m)p(n) = a。p(m)p(n+m+l) p(n)p(m)p(l) = a。p(m)jjji ii ijii将上式两边对m从1到8求和得到工 p (l+m+n) 邮工 p (m)ii jjm=1m=1，工 p (n+m+1) a。 p (m)jj iim = 1m =1它们同为无穷或同为有限，因此，i与j同为常返态或同可见工p(k)和工p(k)相互控制iijjk=1k=1为非常返态.(2 )由(1)有 lim p(l+m+n) a。lim p(m)， lim p(n+m+l) a。lim p(m) mT8 mT8 jj mT8 jjmT8 可见lim p(k)与limp(k)同为0或同为正，因此，i与j在常返的情况下同为零常返态或同为 k T8 k T8 jj正常返态.(3)由于pQ+n) pj)p(n) =a。 0，因此，状态i的周期匕整除l + n.再设S是使得Pj 0的任意正整数，由C-K方程得所以，t整除l + s + n，从而t整除s.由于s是使得Pj) 0的任意正整数，因此，.是正整数集n: n 1, pj) 0的公约数.若记状态j的周期为t，则有t t，同理，由对称性 1， ji jj ii j i j则i与j都是周期的，且有相同的周期；若匕=1，则i与j同为非周期的.定理4.9表明：相通的状态具有相同的状态.定理4 .10如果j是常返态，且j i，则i必是常返态，且f =1证明如果f 1，则自状态i出发经过任意有限步都不能到达j的概率为1- j 0，又j i，因此，自状态j出发经过有限步不能返回j的概率1-七是正的，即七 1，使得f jn） 0, 1=1从而P (n) = 2 f (l) p (n-l) f (n) p (0) = f (n) 0ij ij jj ij jj ijl =1因此，i j，故i j，且i为常返态.定理4.10表明：常返态能到达的状态仍是常返态.例4.9设Markov链X,n = 0的状态空间I = 0121，转移概率为p00 = 2p 考察状态的遍历性.解先画出状态传递图1i ,i+1考察状态。，有=If =Vf =12 004 008f00E 土 =， =E n 2 3n = 1n = 11、002:可见0为正常返态，又由于p（1）二、 0，它是非周期的，因此是遍历的.对于其它状态i，求f（n）比较麻烦，但是，0，因此，都是遍历的.ii例4.10 （续例46）设Markov链Xnn = ，1，为生灭链，其中X0 = ，a ，(i 1) b 0(i 0).证明：如果咒=3，则X 所有状态是常返的.b b .bnk=11 2 k证明显然，所有状态都是相通的，因此，只需验证状态0是常返即可.定义T = minn: X = j对固定的状态k，记u(i) = PT T PT T I X = i,0 i ki 0 k 0 k 0则由全概率公式u(i) = bu(i +1) + a u(i -1) + ru (i),0 i k.iii因此，由上式得u (i +1) u (i) = a u (i) u (i 1)=气气 1 u (i 1) u (i 2)bb b.a31 u (1) u (0)bb .bi i11令 P = 1, P = a1a2 气0 i bb b1 2 iu (。)= 1，则有u (i) - u (i +1) =p ,1-u (1)两边求和(注意到u(k) = 0)，得到1 = 1-u(1)k1 pi i=0因此u (i) = ku(j)-u(j + 1) = k P./k p.jJ=1J=1因为气平f气8，由题设及上式，得到P u s= limP 11 0 = lim 区 p /k P j = lim1- kj=0T b. 0，则它是常返链.由于状态的常返性与初始分布无关，因此，假设X 0 = 1不影响结论的一般性.例4.11 (续例4.1)直线上无限制随机游动.考察状态的常返性. 显然所有状态都是相通的，由例4.1知，对于状态0，有(2 n)!,、P(2n) = Cn (pq)n = (pq)n002n n! n!，/ n 匚由Stirling公式n! r - I J2丸n，可知).2 兀.2n (pq) nP (2 n) R00(4 pq)nP (2 n+1) = 000由p + q = 1，知4pq 1，等号当且仅当p = q = 1时成立，所以当p = q = 2， p00)=3，且p0n)T 0(n T 8).由状态分类判别法知，状态0是零 n=1常返态，由于所有状态都相通，此时所有状态都是零常返的.当p丰q时，4pq 1,p(n) 1这说明从闭集内任一状态，无论转移多少步，都不能转移到闭集之外的状态上去，即随 着时间的推移，闭集内任一状态只能在闭集内部的状态之间转移显然，一个Markov链的整个状态空间是一个闭集，且是最大的闭集；如果p = 1，则ii称状态i是吸收态，吸收态i构成的单点集i是最小的闭集.定理4 .11 Markov链所有常返状态构成的集合是一闭集.证明先证如果i是常返的，且i T j，则有i j.用反证法，如果ji，由于i T j，于是i到达j后就不能返回i，这与i是常返态矛盾，从而i j.由定理4.9,当i是常返态，且i j，则j是常返态，因此，自常返态出发所能到达的 状态必定是常返态，也就是说，常返态不可能转移到非常返态上去，因此，常返态组成的集 合是一闭集.定理4.12 (分解定理)任一Markov链的状态空间I可唯一地分解为有限或可列个互 不相交的子集D, C, ,的和，使得（1）每个Cn是常返态组成的不可约闭集；（2）每个C中的状态同类，或全是正常返，或全是零常返，若是周期的，它们有相同的周n期，且 fjk=, j, k e Cn ；（3）D是由全体非常返状态组成，自Cn中的状态不能到达D中的状态.证明 记C为全体常返态所成的集合，D = I - C为非常返状态全体，将C按互通关系 进行分解，则I = D C C2U U U其中每个Cn是由常返态组成的不可约闭集，由定理4.9知Cn中的状态同类型，显然，Cn中 的状态不能到达D中状态.我们称C为基本常返闭集.分解定理中集D不一定是闭集，但如果I是有限集，则D 一 n定是非闭集.因此，如果质点最初自某一非常返状态出发，则它可能就一直在D中运动，也 有可能在某时刻离开D转移到某个基本常返闭集匕中，一旦质点进入匕后，它将永远在 此C中运动.显然，不可约的Morkov链，或者没有非常返状态，或者没有常返状态，在只有常返状 态不可约的Markov链中，所有状态是相通的.对于不可约Markov链，若它的所有状态是 非常返的，则称为不可约非常返链；若它的所有状态是常返的，则称为不可约常返链 下面我们不加证明地给出不可约常返链的一个判别法.定理4.13不可约链是常返的充分必要条件是下列方程组没有非零有界解：Z =党 PZ.,i = 1,2,（4.19）j=例4.12设Markov链X ,n = 0,1, 的状态空间I = 1,2,3,4,5，一步转移概率矩阵1/2 012 0012n1/2 0：100P =0 0100，将状态空间进行分解.10000L0 1000 J解先画出状态传递图图4-212依题意知3是吸收态，因此，3是闭集，1，4,1，4,3,1，2,3,4都是闭集，其中3 和1,4是不可约的，又I含有闭子集，因此，乂尸=0,1, 不是不可约链.状态5、2是非常返态，因此P = 2,5 3 1,4UU001000 )000001000010例 4.13设I = 1,2,3,4,5,6，转移矩阵为P=131301/300 ，10000010120001妇试分解此链，并指出各状态的常返性和周期性.因为f=1, f（n）= 0,n丰3，因此日=nf（n）= 3，可见1是正常返态且周期为3, 1111111n=1含1的基本常返闭集为q = k ：1 - k = 1,3,5，从而状态3和5是正常返且周期为3.同理状态6正常返，p*） = 2 0，周期为1，即非周期，含6的基本常返闭集为C = k :6 - k = 2,6，可见2和6是遍历状态.由于f=：；f（n） = 0,n丰L因此，f =工f（n） = ：L故4非常返，非周期.4434444443n = 1综上 I = D C1 C 2 = 4 1,3,5 2,6例4.14 （续例4.2）带有一个吸收壁的随机游动.状态空间I = 0,1,2, 可分解为D = 1,2, , C = 0.状态0是正常返，非周期的，C 是闭集，C中状态不能到达D，因此，I不是不可约的，状态1不是常返的.事实上，若1 是常返的，由1 0,就有0 1，这是不可能的，于是1,2, 为非常返集.于是I可分解为I = 0 1,2, 例4.15 （续例4.4）带有一个反射壁的随机游动.该Markov链的状态空间为I = 0,1,2, ，一步转移概率为P 1 = p, i = 0,1,2, , P 1 = q =1 - p, i =1,2,Pg。= q（。 p q，则Z 为非零有界解，此时链非常返.i若p q，Zi无界，没有非零解，此时链常返的.4.4遍历定理和平稳分布4.4.1遍历定理实际应用中常常要研究当n很大时p,（）的性质，我们所关心的是两个问题.一是limp（n） jn s j是否存在，二是其极限是否与起始状态i有关，在Markov链的理论中，有关这一问题的定理是遍历定理.定义4.16设Markov链X., n = 0,1, 的状态空间为I，若对一切i, j e I，存在不依赖于i的极限lim p（n）= p，则称Markov链具有遍历性.n8 jj上式的直观概率意义是：具有遍历性的Markov链看做一个系统，系统不论从哪一个状 态i出发，当转移步数充分大后，转移到状态j的概率都接近于p,.，换句话说，经过足够长的时间后，系统达到平稳状态.定理4.14如果状态j非常返或零常返，则对一切i，有lim p (n) = 0ijms J(4.20)证明若状态j非常返，则 Pj s，因此，当n TS时，Pj t 0，n = 1又由定理4.5知p(n) = fi)p(n-l)，对N n，我们有l=1f (l) p (n-l) f (l) p (n -l) + f (l)p (n) =f (l) p (n-l )+ ij ij jj ij jj ij jjl =1l=N+1l =1j l=N+1令n T3，上式右端第一项因P(n-l) T 0而趋于0，再令N T8，jj第二项因 fjk) 1也k =1趋于0，因此 limp(n) = 0ijn Ts J若j为零常返态，也有P(n)T 0，同上所证可得命题的结论.jj推论1如果Markov链状态个数有限，则不可能全是非常返状态，也不可能含有零常 返状态，从而不可约的有限Markov链必是正常返的.证明 设I = 0,1,2, , N，如全是非常返态，则对任意i, j e I，由定理4.14，lim p(n) = 0.因此，当n TS时，有1 =芸p(n) T 0，这就产生矛盾，因此，有限Markov i.ijnTs J cj = 0链的状态不可能全是非常返的.其次，如果含有零常返态i，则C = j: i t j是不可约集，它是有限集，且所有状态为零常返态，于是，再由由定理4.14,当n Ts时，有1 = p (n) t 0，这也导致矛盾， ijjeC因此，I中不可能含有零常返态.因此，不可约有限Markov链必是正常返的.推论2如果Markov链有一个零常返态，则必有无穷多个零常返态.证明 设i为零常返态，则C = j: i t j是不可约集，其状态全是零常返态，因此，C不可能是有限集，否则与推论1矛盾.定理4.15如果j为非周期的正常返态(即遍历态)，则有1li p(n)fn tsij P j ij证明 因为j为非周期的正常返态，由状态分类判别法(4.21)lim p (n)= n* ij又由定理 4.5 知p(n) = f(I)p (-l)l=1取 1 n n，则有 p(n) = ijl=1f (l) p (n-l) +ij jji=n+if (l) p (n-l),ij jj因此0 p (n) - f (l) p (n-l)= jjijijl =1 f (l) p (n-l) f (l).l=n+1l=n+1得到0 lim p (n) 一 f (l) lim p (n-l) n T3 j司 n3 jl =1f (l) ijl=n+10 lim p (n)- f (lf (l) ijl=1 ij R jl=n得到0 lim p (n) - f ijijnT3l = 11 c(l) 0nT3 ij Rj(4.22)我们称也R .为极限分布(limiting distribution).4.4.2平稳分布定义4.17设Mark。0链X心0的转移概率矩阵为尸=(j如果非负数列切jij满足(! - j i&p,j=0,1, jI jii=0(4.23)则称兀.，j E I为Markov链X , n 0的平稳分布(stationary distribution ).对于平稳分布兀, j e /，有jPki )P = 兀 P(2)司k kjk=0一般地，丸=丸 p(n),n = 1,2,Ji=0J如果Markov链的初始分布为PX0 .= i = pi = 0,1,2,，且恰好是平稳分布，则对 于任意非负整数n，有P X = j = P X = i, X = j = P X = iP X，二 j I X = ii=i= P.pm）= f , j = 0,1,2i=即Xn的分布（Markov链X”,n 0在时刻.n的绝对分布）也是平稳分布，且正好是初始分布 p .这说明绝对分布不随时间而改变，这正是平稳分布名称中“平稳”二字的由来 i定理4.16非周期不可约常返链是正常返的充分必要条件是它存在平稳分布，而且这个 如 j, j e J平稳分布就是极限分布证明 充分性.若存在平稳分布兀，即丸j =丸p（n）i ij i=0由于气 0,气=1，极限号与和号可以交换，两边令n s，得到 i=0兀=lim男兀p（n）=尤兀（imp3）=尤兀（1小）=土j n i ij - 、s ij _ i . j Ri=0i=0i=0因为兀i = 1，于是至少存在一个兀k i=0即1/日k 0，由状态分类的定义知，k为正常返，从而整个链是正常返的，而且所有的兀j = 0j必要性.设链是正常返的，于是lim p（ n）= n is寸 目 j由C K方程知 P(m+n)=ijP (m) p (n) p (m) p (n)ik kjik kjk=0k=0令m is，得到再令Nis，得到1 _Rj)Rj此式只能成为等式.事实上，若对某个j成立严格不等式，对j = 0,1,2,求和得i z 1 I，=0R jj=01 k=0p(n)R kj )k=4仔k=0 k pj) j =0)这就导致矛盾.上式中第一个不等号是由于1 = p (n) zp (n) ikikk=0k=0先令 n is，得到 12 Cim p$)= ，再令 N is，得 1 2 k = 0 T8k=0 * kk=0 * k1 寸1因为对一切J都只能成立等式=p (n)令 n is，得= J_ (im p (n)=Rj k=0 Rk nis 肉R jk =0 Rk 可 1 k=0 Rk)即 =1.因此，极限分布,j E /就是平稳分布.k=0 R kR j推论1有限状态的不可约非周期Markov链必存在平稳分布.证明 由定理4.14的推论1，此Markov链只有正常返态，再由定理4.16知必存在平 稳分布.证毕推论2若不可约Markov链的所有状态是非常返或零常返的，则不存在平稳分布.i=0证明 用反证法.假设丸是平稳分布，则有七= pjn）.又由定理4.14，lim p (n) =0.显然乙ns J =0=0 ,与平稳分布兀j T矛盾.J=0推论3若切j j e /是不可约非周期Marko.链的平稳分