从而可知级数∑Pm与∑p0同时收敛或发散故,j的常返与否是相同的 例5.22(二值链) 0<a,b<1 直观上可以想到状态0和1均是常返态下面证明此结论 利用归纳法我们可以得到 b1-a),(a+b-1y(1-a-(1-a) 2-(a+b)(1-b1-a)2-(a+b)(-(1-b) 故p( (a+b-1) 2-(a+b)2-(a+b) 由于0<ab<1,就有lp)= >0.从而∑P=∞,故0为常返态同 样状态1也是常返态 例5.23在简单随机徘徊中考虑状态0.此时 ),P 2np q 用 Stirling公式:n~√2rne(其中当lmn=1时,我们记an~b),我们可得 pq pe 因此∑m收敛当且仅当∑P n-收敛,又因为4y≤1,且等号成立当且仅当 P=q=,于是∑m=∞当且仅当P=q=·也就是说,当且只当在简单随机徘徊 为对称时,状态0是常返的 例5.24(Z上的对称随机徘徊)记Z为d维整数格点组成的集合.每一个格点有d个方 向,故各有2d个邻点.在 Markov链已知处在某一个格点的条件下,以相同的条件概率(即各以概率——), 在下一个时刻转移到它的任意一个邻点,这样的 Markov链称为Z上的对称随机徘徊.显见各个点的常返 性与暂态性是一样的下面我们考察原点的情形.显然p0)=0 对于正整数m,把m个不同的元素分成/个组,使第j组恰有k,个元素(k1+…+k=m)的不 106
106 从而可知级数år r pii ( ) 与år r p jj ( ) 同时收敛或发散. 故i, j 的常返与否是相同的 例５．２２ (二值链) P (0 , 1) 1 1 < < ÷ ÷ ø ö ç ç è æ - - = a b b b a a ． 直观上可以想到状态 0 和 1 均是常返态. 下面证明此结论. 利用归纳法我们可以得到 ÷ ÷ ø ö ç ç è æ - - - - - - - + + - +÷ ÷ ø ö ç ç è æ - - - - - + = = b b a a a b a b b a b a a b n n n (1 ) 1 1 (1 ) 2 ( ) ( 1) 1 1 1 1 2 ( ) ( ) 1 P P ． 故 n n a b a b a a b b p ( 1) 2 ( ) 1 2 ( ) ( ) 1 00 + - - + - + - + - = ． 由于0 < a,b < 1，就有 0 2 ( ) 1 lim ( ) 00 > - + - = ®¥ a b b p n n ．从而 å = ¥ ¥ =1 ( ) 00 n n p , 故 0 为常返态. 同 样状态 1 也是常返态. 例５．２３ 在简单随机徘徊中考虑状态 0. 此时 0 ( 0,1,2, ) (2 1) p00 n+ = n = L ， ( 1,2, ) 2 (2 ) p00 n = C n n p n q n n = L ． 用 Stirling 公式： n!～ n n n e + - 2 1 2p （其中当lim =1 ®¥ n n n b a 时，我们记an ～bn），我们可得 (2 ) 00 n p ～ n pq n p (4 ) ． 因此 å ¥ =1 ( ) 00 n n p 收敛当且仅当 å ¥ =1 (4 ) n n n pq p 收敛．又因为 4 pq £ 1 ，且等号成立当且仅当 2 1 p = q = ，于是å = ¥ ¥ =1 ( ) 00 n n p 当且仅当 2 1 p = q = . 也就是说，当且只当在简单随机徘徊 为对称时，状态 0 是常返的. * 例５．２４ ( d Z 上的对称随机徘徊) 记 d Z 为 d 维整数格点组成的集合. 每一个格点有 d 个方 向, 故各有 2d 个邻点. 在 Markov 链已知处在某一个格点的条件下, 以相同的条件概率(即各以概率 2d 1 ), 在下一个时刻转移到它的任意一个邻点, 这样的 Markov 链称为 d Z 上的对称随机徘徊. 显见各个点的常返 性与暂态性是一样的. 下面我们考察原点的情形. 显然 0 (2 1) 00 = n- p . 对于正整数m ，把m 个不同的元素分成 l 个组, 使第 j 组恰有 j k 个元素( k1 +L+ kl = m )的不
同分法的数目记为C,那么,由归纳法可得C“=CCb 于是 p=∑P∩向第个坐标方向两侧独立地各走步) k1)2…(k!)2 2n∑Ic 这样,当d=2时,用罗Ckm-k12=C2n及 Stirling公式,我们有 )2 而当d≥3时我们利用下面的引理 引理5.25在n→∞时有近似关系 max k=n 2 (此引理可用 Stirling公式证明) 利用引理5.25,就得到 C “] n"e"√2mn ≈常数 可见 J=∞(d≤2) (d≥3) 即:对于Zd上的对称简单随机徘徊,当d≤2时,一切状态都是常返态.而当d≥3时,一切状态 都是暂态.这个结论在直观上是很清楚的,在d大时,能去的地方多了,回返的可能性就小了 因为常返态能以概率为1地返回,直观地看,从常返态i能到达的状态j,必须以概率为 返回i,而返回i后又可达j,看来似乎j总能返回自己,即j也应是常返态.另一方面,常 返态既能以概率为1地返回一次,就能返回第二次,从而能返回∞次.即若状态i为常返 态,则 Markov链无穷次返回状态i的概率为1.而若状态j为暂态,则 Markov链以正概率 不能返回,从而无穷次返回状态j的概率为0.下段将致力于证明这两个结论 2.2常返性再访与 Markov链的基本结构 设随机变量7,表示 Markov链5n访问状态j的次数,即把5n作为下标n≥1的随机序
107 同分法的数目记为 k kl C m , , 1 L ． 那么，由归纳法可得 ! ! ! 1 , , 2 1 1 1 l k m k k m k k m k k m C l C C L L = - L = . 于是 ( { ) 1 1 ( ) 00 å+ + = = = k k n d i i n d p P i k L I 向第 个坐标方向两侧独立地各走 步） å+ + = = k k n k k k k n n d d d d C L L 1 1 , 1 , , , 2 2 ) 2 1 ( å+ + = = k k n n d k kd d n 1 L L 2 2 2 1 ) 2 1 ( ( !) ( !) (2 )! å+ + = = k k n n k k n n n n d d d C C L L 1 1 , , 2 2 2 ] 1 [ 2 1 . 这样, 当d = 2 时, 用 n n k n k n k Cn C2 , 2 å[ ] = £ - 及 Stirling 公式, 我们有 n p C n n n n × = » p 1 ( ) 4 1 2 2 2 ( ) 00 . 而当d ³ 3时我们利用下面的引理． 引理５．２５ 在n ® ¥ 时有近似关系 d n d n n k k n k n d C d C i i , , , , 1 1 max L L » å= = , n C n n n × » p 1 2 1 2 2 ． ? (此引理可用 Stirling 公式证明)． 利用引理５．２５， 就得到 n n n n n C d p 2 2 ( ) 00 1 2 1 £ [max ] , , 1 1 d d i i k k n k n C L å= = d n d n n Cn d n 1 1 ,L, p » d d n d n n n n d n e d n n e n d n [( ) 2 ] 1 2 p p p - - » 2 1 d n » 常数 ． 可见 å ¥ = î í ì < ¥ ³ = ¥ £ 0 ( ) 00 ( 3) ( 2) n n d d p . 即: 对于 d Z 上的对称简单随机徘徊, 当 d £ 2 时, 一切状态都是常返态. 而当 d ³ 3时, 一切状态 都是暂态. 这个结论在直观上是很清楚的, 在 d 大时， 能去的地方多了, 回返的可能性就小了. 因为常返态能以概率为 1 地返回, 直观地看, 从常返态i 能到达的状态 j ,必须以概率为 1 返回i , 而返回i 后又可达 j , 看来似乎 j 总能返回自己, 即 j 也应是常返态. 另一方面, 常 返态既能以概率为 1 地返回一次, 就能返回第二次,… ,从而能返回¥ 次．即若状态i 为常返 态，则 Markov 链无穷次返回状态 i 的概率为 1. 而若状态 j 为暂态，则 Markov 链以正概率 不能返回, 从而无穷次返回状态 j 的概率为 0. 下段将致力于证明这两个结论. 2. 2 常返性再访与 Markov 链的基本结构 设随机变量h j 表示 Markov 链 n x 访问状态 j 的次数, 即把 n x 作为下标n ³1的随机序
列时,在此序列中总共取到状态j的次数(若在此序列中j被取到了∞次,则我们认为 7=∞所以7,是一个可以取值∞的非负整值随机变量)按定义就有 f=P(T,21k0= 定理5.26 (1)若j为常返态,则 P(,=咪50=1)=f(i∈S) 特别是在=j时,有P(=50= )若/为暂态,w肌k。=0Jn(∈S) 证明(1)按T,取值的不同,把要考虑的事件划分为互不相容的事件之并,利用 Markov 性及全概率公式,我们得到 P(n2=0)=∑P(n≥m=.50=1P(T,=k P(≥=15≠,(1<k,50=1P(T=k=1) P(,≥帐k=P(T=k=1=∑P(2n-1=nP(T=k0=) k=1 ls=/∑P(T=k0=1)=fP(,≥m-lk= 反复使用上式,就可推出 P(,≥啡k=)= f, p(2l0=n=ffn(n21 由于j为常返态,即fn=1,令n→∞就得到 P(T=∞0=)=fnMi∈S (2)由于η,为非负整值随机变量,与普通的期望类似地有条件期望公式 E(n|0=D)=∑P(n≥h 故由(1)中的推导及Jn<1(因为假定暂态j为暂态)可推出
108 列时, 在此序列中总共取到状态 j 的次数 (若在此序列中 j 被取到了¥ 次，则我们认为 h j = ¥ . 所以h j 是一个可以取值¥ 的非负整值随机变量). 按定义就有 ( 1 ) 0 f P i ij = hj ³ x = ． 定理 5. ２６ (1) 若 j 为常返态，则 ( ) ( ) P h j = ¥x0 = i = f ij "i Î S . 特别是在i = j 时, 有P(hj = ¥x0 = j) =1 . (2) 若 j 为暂态，则 ( ) 1 ( ) 0 i S f f E i jj ij j " Î - h x = = . 证明 （1）按T j 取值的不同，把要考虑的事件划分为互不相容的事件之并, 利用 Markov 性及全概率公式, 我们得到 å ¥ = ³ = = ³ = = = = 1 0 0 0 ( ) ( , ) ( ) k j j j j P h nx i P h nT k x i P T k x i å ¥ = = ³ = ¹ < = = = 1 0 0 ( , ,( ), ) ( ) k j k l j P h nx j x j l k x i P T k x i ( 1 ) ( ) ( 1 ) ( ) ( ) ( 1 ) ( ) 0 1 0 0 1 0 0 1 0 P n j P T k i f P n j P n j P T k i P n j P T k i ij j k j j k j j k j k j = ³ - = = = = ³ - = = ³ = = = = ³ - = = = å å å ¥ = ¥ = ¥ = h x x h x h x x h x x 反复使用上式，就可推出 1 0 2 0 ( ) [ ] ( 1 ) [ ] - - ³ = = ³ = = n j ij jj n j ij jj P h nx i f f P h x j f f (n ³ 1)． 由于 j 为常返态，即 = 1 jj f ，令n ® ¥就得到 P(hj = ¥x 0 = i) = f ij "i Î S （2）由于h j 为非负整值随机变量，与普通的期望类似地有条件期望公式 å ¥ = = = ³ = 1 0 0 ( ) ( ) n j j E h x i P h n x i ． 故由（1）中的推导及 < 1 jj f (因为假定暂态 j 为暂态) 可推出
E(|=1=∑/Un vi∈S 推论5.27(常返与暂态的另一个等价条件) (1)状态/为常返态,当且仅当P(,=叫==1 (2)状态j为暂态当且仅当,P(==50==0 证(2)由定理5.26得 P(,=叫50=)=0分E(=<分f≠1,即j为暂态 注1这个推论就是说,在条件概率P(50=j)下,事件n,=∞的条件概率只能为 0或1,也称为对于此事件"条件0-1律"成立 注2]推论5.27清楚地说明了常返态与暂态的含义.对于 Markov链,常返态是由它 出发能∞次返回的状态,而随着时间的发展,暂态将逐渐消失.所以,在对用 Markov链描 述的模型作稳态设计时,暂态是不予考虑的这正说明了为什么区分常返态与暂态是十分重 要的 定理5.28若i常返,且i→j,则f=fn=1,从而j也常返 证明记m= inf p/>0.由于i为常返态故 1=P(=∞|50=l) =P(5m0=j,有∞个n使5mn=1|50=1)+P(m≠,有∞个n使5m+n=l|50=1) ≤P(m=1,有∞个n使5m+=150=1)+P(m≠八50=1) ≤pP(T<150=)+(1-P) )(1-P(7<∞|0=)≤1. 因此 fn=P(T<∞50=)=1 于是存在n使fn”>0,从而p/≥f>0,即j→1.由命题5.21得j的常返性 上面得到的关于状态为常返(或暂态)的条件,从概念的含义看是很清楚的.但是很难 用于实际判断.比较起来,用命题5.16来判断状态j是否常返常更为可行 闭∑p/的概率含义)记 1(若En=j) 1()=10(其它情形)
109 i S f f E i f f jj ij n n j ij jj " Î - = = å = ¥ = - 1 ( ) [ ] 1 1 0 h x ． 推论５．２７ (常返与暂态的另一个等价条件) (1) 状态 j 为常返态, 当且仅当, P(hj = ¥x0 = j) =1； (2) 状态 j 为暂态, 当且仅当, P(hj = ¥x0 = j) = 0. 证(2) 由定理 5．２６得 P(h j = ¥x0 = j) = 0 Û E(hj x0 = j) < ¥ Û f jj ¹1, 即 j 为暂态. [注 1] 这个推论就是说, 在条件概率 ( | ) 0 P × x = j 下, 事件 h j = ¥ 的条件概率只能为 0 或 1, 也称为对于此事件＂条件 0-1 律＂成立. [注 2] 推论５．２７清楚地说明了常返态与暂态的含义．对于 Markov 链, 常返态是由它 出发能¥ 次返回的状态, 而随着时间的发展, 暂态将逐渐消失. 所以, 在对用 Markov 链描 述的模型作稳态设计时, 暂态是不予考虑的. 这正说明了为什么区分常返态与暂态是十分重 要的. 定理 5. ２８ 若i 常返，且i ® j , 则 = = 1 ji jj f f , 从而 j 也常返. 证明 记 inf 0 ( ) 0 = > m m m pij . 由于i 为常返态, 故 1 ( | ) 0 P i = hi = ¥ x = ( , | ) 0 0 0 P j n i i = xm = 有¥个 使x m +n = x = ( , | ) 0 0 0 P j n i i + xm ¹ 有¥个 使xm +n = x = ( , | ) 0 0 0 P j n i i £ x m = 有¥个 使x m +n = x = ( | ) 0 0 P j i + xm ¹ x = ( | ) (1 ) ( ) 0 ( ) 0 m0 i ij m £ pij P T < ¥ x = j + - p p P m = 1- ij (1- ( ) 0 ( | )) 0 T j i < ¥ x = £ 1． 因此 ( | ) 1 f ji = P Ti < ¥ x 0 = j = . 于是存在n 使 0 ( ) > n ji f , 从而 0 ( ) ( ) ³ > n ji n ji p f , 即 j ® i . 由命题 5．２１得 j 的常返性. 上面得到的关于状态为常返（或暂态）的条件, 从概念的含义看是很清楚的. 但是很难 用于实际判断. 比较起来，用命题５．１６来判断状态 j 是否常返常更为可行. [注] (å ¥ =1 ( ) n n p jj 的概率含义) 记 î í ì = = 其它情形） 若 0 ( 1 ( ) ( ) { } j I n j n x x ．
那么n=∑ln(n)因此 形=j)=∑E(Ln(n)=1)=E(T Markov链的基本结构 定义5.28(状态的互通性)两个互相可达的,j称为是互通的,记为i4>j 命题5.29在常返态间,互通性是等价关系,即它满足 (1)自反性:i←i (2)对称性:若ij,则i>j; (3)传递性:若i(j,且jk,则i>k 证明我们只须证明传递性.设i分j,则存在整数n,使得P>0,又由于 j分k,故存在整数m,使得P>0.因此由 Chapman-Kolmogorov方程得到 pk+=∑p)p1m)2pp>0 故i→>k.同理可证,k→>i,从而有i>k 注与多数课本不同的是,在本书中我们只对常返态考虑等价性,原因在于对于暂态 果i不可能有i→i.也就是说,只在常返态间,互通性才是自返的,即i→>i.只有此时它 才可能是一个数学上的等价关系 Markov链的状态,除暂态外,可利用互通这个等价关系划分成不同的等价类,即把互 通的常返状态归入同一类中,称为一个常返类.而把所有的暂态状态,通通放到一个“另类” 中,不再加以细分.单个状态k是一个常返类的充要要条件为,pk=1,此时k为吸收态 定义5.30(状态闭集与不可约性) 状态的集合A称为闭集,如果对于任意状态i∈A,满足∑P=1.显见状态空间(即 全体状态)是一个闭集如果除此以外再也没有其它非空闭集,则称此 Markov链为不可约 的 显见,一个常返类是闭集,而且它不含更小的闭集 简单随机徘徊的所有状态都在同一等价类,故它是一个不可约 Markov链.而两端为0 和N的吸收壁随机徘徊,吸收状态0和N分别都是一个单点常返类,它们是仅有的真闭集(即 除状态空间以外的闭集),此 Markov链是可约的 命题5.31(状态分解定理)(1) Markov链的状态空间S可唯一分解为 S=TUH1∪H2∪…, 其中T为暂态的全体,而H为等价常返类 (2)若Mkov链的初分布集中在某个常返类Hk上,则此 Markov链概率为1地永 远在此常返类中,也就是说,它也可以看成状态空间为Hk的不可约 Markov链 110
110 那么 å ¥ = = 1 { } ( ) n j j n h I x . 因此 å å ¥ = ¥ = = = = 1 0 1 ( ) ( ) n n n n jj p P x jx j ( ( ) ) ( ) 0 1 { } 0 E I i E i j n = å j n = = = ¥ = x x h x ． Markov 链的基本结构 定义５．２８（状态的互通性） 两个互相可达的i, j 称为是互通的，记为i « j . 命题 5．２９ 在常返态间, 互通性是等价关系, 即它满足 （１） 自反性：i « i ； （２）对称性：若i « j ，则i « j ； （３）传递性：若i « j ，且 j « k ，则i « k ． 证明 我们只须证明传递性. 设 i « j ，则存在整数 n，使得 0 ( ) > n pij , 又由于 j « k ，故存在整数 m，使得 0 ( ) > m p jk . 因此 由 Chapman-Kolmogorov 方程得到 0 ( ) ( ) ( ) ( ) ( ) = å ³ > Î + m jk n ij r S m rk n ir m n pik p p p p ． 故i ® k . 同理可证，k ® i ，从而有i « k . 注 与多数课本不同的是， 在本书中我们只对常返态考虑等价性, 原因在于对于暂态 果i 不可能有i ® i ．也就是说, 只在常返态间, 互通性才是自返的，即 i ® i . 只有此时它 才可能是一个数学上的等价关系. Markov 链的状态, 除暂态外, 可利用互通这个等价关系划分成不同的等价类，即把互 通的常返状态归入同一类中, 称为一个常返类．而把所有的暂态状态, 通通放到一个“另类” 中, 不再加以细分. 单个状态k 是一个常返类的充要要条件为，pkk = 1，此时k 为吸收态． 定义５．３０ (状态闭集与不可约性) 状态的集合 A 称为闭集, 如果对于任意状态i Î A，满足 åÎ = j A ij p 1. 显见状态空间 (即 全体状态) 是一个闭集. 如果除此以外再也没有其它非空闭集, 则称此 Markov 链为不可约 的. 显见, 一个常返类是闭集, 而且它不含更小的闭集. 简单随机徘徊的所有状态都在同一等价类，故它是一个不可约 Markov 链. 而两端为 0 和 N 的吸收壁随机徘徊，吸收状态 0 和 N 分别都是一个单点常返类, 它们是仅有的真闭集(即 除状态空间以外的闭集), 此 Markov 链是可约的. 命题 5．３１（状态分解定理） （１）Markov 链的状态空间 S 可唯一分解为： S = T U H1 U H2 UL， 其中 T 为暂态的全体，而Hi 为等价常返类. （２）若 Markov 链的初分布集中在某个常返类 Hk 上， 则此 Markov 链概率为 1 地永 远在此常返类中，也就是说，它也可以看成状态空间为 Hk 的不可约 Markov 链．