第四章离散时间 Markov链 41定义和一些例子 在一些物理学、生物学、经济学等许多学科中,都有如下行为的系统:该系统 是与时间有关的一个系统,如果已知系统在现在的状态,则此系统的过去所处的 状态与将来所处状态是(条件)独立的,这个特性称为 Markov性。本节我们考 虑状态空间S为离散的,用0,l1,…或i,表示状态,参数集T为离散的(一般表 示时间),T={012,…}。 定义411:一个离散时间随机过程{Xnn≥0称为 Markov链,若对任意状态序 列{0,1…in,l,jcS P(xm=X6=0,x1=1,…Xm=bn,xn=D)=P(Xm=Xn= 记P“=P(X2=Xn=1),b,j∈S称为在n时的一步转移概率( one step transition probabilities固定n,转移概率P,可以看成某个矩阵的第i行j列 元素,把该矩阵记为P(m),即P(m)=(P)s,它有可能是无穷维的。P(m)称 为在时刻n的一步转移概率矩阵。一般来说转移概率P"“依赖于时刻n,此时 称该 Markov链是非齐次的( (inhomogenous。但是,一个重要的情形是粒子在时 刻s处于状态i,在时刻s+t处于状态j与在初始时刻s=0处于状态i,在时刻t 处于状态j这两个过程是一样的 定义4.12: Markov链{xn,n≥0}称为齐次 Markov链或称为有平稳转移概率的 Markov链若它一步转移概率Pn,n∈Ti,j∈S不依赖于n 对于齐次 Markov链,由于一步转移概率Pn不依赖于n,因此记 P=P"=P(xn=小x=D),此时一步转移概率矩阵为P=(P)以下不
第四章 离散时间 Markov 链 4.1 定义和一些例子 在一些物理学、生物学、经济学等许多学科中，都有如下行为的系统：该系统 是与时间有关的一个系统，如果已知系统在现在的状态，则此系统的过去所处的 状态与将来所处状态是（条件）独立的，这个特性称为 Markov 性。本节我们考 虑状态空间 S 为离散的，用i0 ,i1 ,L或i, j 表示状态，参数集T 为离散的（一般表 示时间），T = { } 0,1,2,L 。 定义 4.1.1：一个离散时间随机过程{X n , n ≥ 0}称为 Markov 链，若对任意状态序 列{ } i0 ,i1 ,Lin−1 ,i, j ⊂ S ( , , , ) ( ) 1 0 0 1 1 1 1 1 P X j X i X i X i X i P X j X i n+ = = = L n− = n− n = = n+ = n = 。 记 ( ) 1 , 1 P P X j X i n n n n ij = + = = + ，i, j ∈ S 称为在 时的一步转移概率（one step transition probabilities）。固定 ，转移概率 ，可以看成某个矩阵的第i 行 n n n,n+1 Pij j 列 元素，把该矩阵记为 P(n)，即 ( )i j S n n P n Pij ∈ + = , , 1 ( ) ，它有可能是无穷维的。 称 为在时刻 的一步转移概率矩阵。一般来说转移概率 依赖于时刻 ，此时 称该 Markov 链是非齐次的(inhomogenous)。但是，一个重要的情形是粒子在时 刻s 处于状态i ，在时刻 处于状态 P(n) n n,n+1 Pij n s + t j 与在初始时刻s = 0 处于状态i ，在时刻t 处于状态 j 这两个过程是一样的。 定义 4.1.2：Markov 链{ 称为齐次 Markov 链或称为有平稳转移概率的 Markov 链若它一步转移概率 ， X n , n ≥ 0} n,n+1 Pij n∈T i, j ∈ S 不依赖于n 。 对于齐次 Markov 链，由于一步转移概率 Pij n,n+1 不依赖于 n ，因此记 ( ) 1 , 1 P P P X j X i n n n n ij = ij = + = = + ，此时一步转移概率矩阵为 ( )i j S P Pij ∈ = , 。以下不 1
特别指明,所讨论的均为齐次 Markov链。以p1=P(X=1),l∈S记 Markov链 xn,n≥0}的初始分布(∑P,=1)。 定理411:1)P20∑P=1,,j∈S )P(X=l0,X1=1…Xn=)=PPPh2…P 例4.1.1:直线上的随机游动。假设从原点开始,粒子以p的概率向前迈一步, 以q的概率向后迈一步,以r的概率在原地不动,p+q+r=1。X,表示n时刻 的位置,则Xn为齐次 Markov链。状态空间S={…-2,-10.2,…},一步转移概 P=pP=r,P1=q,P=0.}->1,V,j∈S。这是无限制随机游动。 42n步转移概率矩阵 设状态空间为S,一步转移概率为P,初始分布为p,=P(X。=D,i∈S的齐次 Markov链{xn20,令Pm0=P(xm=儿xm=)=P(xn=X0=)n2,表示 经过n个时刻,链从状态i转移到状态j的概率,称为n步转移概率。令 1,若i=j -0,若i /∈S,定义如下矩阵P0=Vp)s,P0=P=(P) n≥2,P=(")s(n步转移概率矩阵 定理421:1).P(Xn=小=∑pP,v∈S ).(Chapman-Kolmogorov relation) P=∑PP”,i,j∈S k∈S
特别指明，所讨论的均为齐次 Markov 链。以 pi = P(X 0 = i),i∈ S 记 Markov 链 {X n , n ≥ 0}的初始分布（∑ =1）。 i∈S pi 定理 4.1.1：1). ≥ 0,∑ =1， j∈S Pij Pij ∀i, j ∈ S 2). n n n n pi Pi i Pi i Pi i P X i X i X i 0 0 1 1 2 1 ( , , ) 0 0 1 1 − = = L = = L 例 4.1.1：直线上的随机游动。假设从原点开始，粒子以 p 的概率向前迈一步， 以q 的概率向后迈一步，以r 的概率在原地不动， p + q + r =1。 表示 时刻 的位置，则 为齐次 Markov 链。状态空间 X n n X n S = {L,−2,−1,0,1,2,L}，一步转移概 率 , , , 0, 1 Pi,i+1 = p Pii = r Pi,i−1 = q Pij = i − j > ，∀i, j ∈ S 。这是无限制随机游动。 4.2 n 步转移概率矩阵 设状态空间为 S ，一步转移概率为 P ，初始分布为 pi = P(X 0 = i),i∈ S 的齐次 Markov 链{ } X n , n ≥ 0 ，令 ( ) ( ), 2 0 ( ) P = P X n+m = j X m = i = P X n = j X = i n ≥ n ij ，表示 经过 n 个时刻，链从状态 i 转移到状态 j 的概率，称为 步转移概率。令 ，定义如下矩阵 n ⎩ ⎨ ⎧ ≠ = = i j i j Pij 若 若 0, 1, (0) i, j ∈ S ( )i j S P Pij ∈ = , (0) (0) ， ( )i j S P P Pij ∈ = = , (1) ， n ≥ 2 ， ( )i j S n ij n P P ∈ = , ( ) ( ) （n 步转移概率矩阵）。 定理 4.2.1：1). P(X j) p P j S i s n n = = ∑ i ij ∀ ∈ ∈ , ( ) 2). (Chapman-Kolmogorov relation) ∑∈ + = k S n kj m ik n m Pij P P ( ) ( ) ( ) ，i, j ∈ S 2
考虑矩阵乘法,上式可写成 因此有 Pm=Pn,n≥ 例421:考虑两个状态的 Markov链{Xn,n≥0},一步转移概率为 0 P=0(1-PP m)=P= 1(qP1(-p-q)"(p-p pt q 43状态空间的分解 定义43.1:称状态i可到达( accessible)j,记为i→j,若存在n20使得Pm>0; 若i→jj→i,则称i,j是相通的( communicate),记为ij。 相通关系是一个等价关系,即满足: 1)自反性:i>i 2)对称性:ij,则j>i; 3)传递性:ijj台k,则i←>k。 两个状态若是相通的就称他们是处于同一类。 Markov链的所有状态按相通关系 分割成不同的等价类,两个等价类要么不相交,要么重合 定义432:一个状态集合C称为是闭集,若P=0对vi∈C,vC。一旦粒子进 入某个闭集,就永远停留在此闭集中。一个 Markov链称为不可约( irreducible) 若除整个状态空间外无别的闭集
考虑矩阵乘法，上式可写成 (n m) (n) (m) P = P ⋅ P + 因此有 , 1 ( ) P = P n ≥ n n 例 4.2.1：考虑两个状态的 Markov 链{X n , n ≥ 0}，一步转移概率为 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − = − q q P p p 1 1 1 0 0 1 则 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − + − − +⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + = = q q p p p q p q q p q p p q P P n n n 1 (1 ) ( ) 4.3 状态空间的分解 定义 4.3.1：称状态i 可到达（accessible）j ，记为i → j ，若存在 使得 ； 若 n ≥ 0 0 ( ) > n Pij i → j, j → i ，则称i, j 是相通的（communicate），记为i ↔ j 。 相通关系是一个等价关系，即满足： 1) 自反性：i ↔ i ； 2) 对称性：i ↔ j ，则 j ↔ i ； 3) 传递性：i ↔ j, j ↔ k ，则i ↔ k 。 两个状态若是相通的就称他们是处于同一类。Markov 链的所有状态按相通关系 分割成不同的等价类，两个等价类要么不相交，要么重合。 定义 4.3.2：一个状态集合C 称为是闭集，若 Pij = 0对∀i∈C,∀j ∉C 。一旦粒子进 入某个闭集，就永远停留在此闭集中。一个 Markov 链称为不可约（irreducible） 若除整个状态空间外无别的闭集。 3
定理43.1: Mrakov链不可约所有状态之间是相通的 证明:←显然。→(反证法)若存在两状态,不是相通的,不妨设i办j。令 C={k→k},则首先jC;其次对vk∈C,MeC,P=0。因此C为一个闭集, 而这与 Mrakov链不可约矛盾。 例431:若 Markov链一步转移概率矩阵为 1(1/43/4 2|1/21/2 P 1/21/2 2},34,5}在相通意义下为两个等价类,此链是可约的 定义43:1记d()=gd21r0>0,这里gcd表示最大公因子( greatest common divisor),若d(i)>1,称i为周期的( periodic),且周期为d(i);否则称 为非周期的( aperiodic)。 由定义立即可知,若n不是d()的倍数,则P=0 定理43.2:若i)j,则d()=d()。 证明:由于j,故彐m,n使得Pm>0,P)>0。于是Pm>0。若有s使得 P”>0,则Pm”>0。由于dO+m,dOn+m+s,因此d(,进而 dOd()。同理有dO)l(),故d()=d() 定理43.3:存在正整数N使得对所有的n>N恒有Pm0)>0 证明依赖于一个数论知识:若k个正整数n1,n2…n4互素,则存在正整数N使得 对所有的n>N都存在非负整数a1,a2,…a使得n=∑an。对状态i,若
定理 4.3.1：Mrakov 链不可约⇔ 所有状态之间是相通的。 证明：⇐显然。⇒（反证法）若存在两状态i, j 不是相通的，不妨设i →/ j 。令 C = {k i → k}，则首先 j ∉C ；其次对∀k ∈C,∀l ∉C, Pkl = 0。因此 为一个闭集， 而这与 Mrakov 链不可约矛盾。 C 例 4.3.1：若 Markov 链一步转移概率矩阵为 ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = 1 1/ 2 1/ 2 1 1/ 2 1/ 2 1/ 4 3 / 4 5 4 3 2 1 1 2 3 4 5 P { } 1,2 ,{3,4,5}在相通意义下为两个等价类，此链是可约的。 定义 4.3.3：记 ( ) gcd{ 1, 0} ( ) = ≥ > n n n Pii d i ，这里 表示最大公因子（greatest common divisor），若 ，称 为周期的（periodic），且周期为 ；否则称 为非周期的（aperiodic）。 gcd d(i) >1 i d(i) 由定义立即可知，若n 不是d(i) 的倍数，则 Pii (n) = 0 。 定理 4.3.2：若i ↔ j ，则d(i) = d( j) 。 证明：由于i ↔ j ，故 使得 。于是 。若有 s 使得 ，则 。由于 ∃m, n 0, 0 ( ) ( ) > > n ji m Pij P 0 ( ) > n+m Pjj 0 ( ) > s Pii 0 ( ) > n+m+s Pjj d( j) n + m ， d( j) n + m + s ，因此 d( j)s ，进而 d( j) d(i) 。同理有d(i) d( j) ，故d(i) = d( j) 。 定理 4.3.3：存在正整数 N 使得对所有的n > N 恒有 Pii (nd (i)) > 0。 证明依赖于一个数论知识：若 个正整数 互素，则存在正整数 使得 对所有的 都存在非负整数 使得 。对状态 i ，若 k n n Lnk , , 1 2 N n > N a a Lak , , 1 2 ∑= = k i n aini 1 4
Pa),pPn)…,P(n)>0,则B, 互素,故存在正整数N使得对所有的 d(dd(o d(o n>N都存在非负整数a1,a2,…a使得md()=∑a,n,且Pm>0。 定理433的一个直接推论是:若P如m)>0,存在正整数N使得对所有的 n>N恒有P(m+m()>0 定理4.3.4:设P为不可约、非周期、有限状态 Markov链的一步转移概率矩阵, 则存在正整数N使得当n>N时,n步转移概率矩阵P的所有元素都大于0 44常返与瞬过 在事件{X=上引入一个重要的概率∫,表示从出发在n步转移时首次 到达j的概率。用式子表示即是 f0=0,=P(X,=j,Xk≠,k=1…n-1X0=0。 令∫=∑Jm,它表示从出发最终转入到状态j的概率。再引入一重要随机变 量r=min:x=1,Xn=1,n≥21,因此/=P(n=nx0=) 定理441 fPm-),vi,j∈S
, 0 ( ) ( ) ( ) 1 2 > nk ii n ii n Pii P LP ，则 ( ) , ( ) , ( ) 1 2 d i n d i n d i n L k 互素，故存在正整数 使得对所有的 都存在非负整数 使得 ，且 。 N n > N a a Lak , , 1 2 ∑= = k i aini nd i 1 ( ) 0 ( ( )) > nd i Pii 定理 4.3.3 的一个直接推论是：若 ，存在正整数 使得对所有的 恒有 。 0 ( ) > m Pji N n > N 0 ( ( )) > m+nd i Pji 定理 4.3.4：设 P 为不可约、非周期、有限状态 Markov 链的一步转移概率矩阵， 则存在正整数 N 使得当n > N 时，n 步转移概率矩阵 (n) P 的所有元素都大于 0。 4.4 常返与瞬过 在事件{ 上引入一个重要的概率 ，表示从 出发在 步转移时首次 到达 X0 = i} (n) ij f i n j 的概率。用式子表示即是 0, ( , , 1, 1 ) 0 (0) ( ) f f P X j X j k n X i n k n ij = ij = = ≠ = L − = 。 令 ∑ ，它表示从i 出发最终转入到状态 ∞ = = 1 ( ) n n ij ij f f j 的概率。再引入一重要随机变 量τ ij = min{ } n : X 0 = i, X n = j, n ≥1 ，因此 f P( n X i) ij n ij = = 0 = ( ) τ 。 定理 4.4.1： P f P i j S n l n l jj l ij n ij = ∑ ∀ ∈ = − , , 1 ( ) ( ) ( ) 证： 5
pin=P(X=jXo=i) ∑P(xn=l,Xn=儿X0=1 (=1=0x,==1 ∑P(xn=lX6=)P(Xn=儿X ≠jX1=j ∑P(n=Xo=P( 推论44.1:i→j台∫>0 定义441:若fn=1,称状态i为常返的 (recurrent;若f<1,则称状态i为瞬 过的 transien) 如果状态i为常返的,系统无穷次返回状态i的概率为1;如果状态i为瞬过, 系统无穷次返回状态i的概率为0 定理442:状态i为常返的台∑P=∞;状态为瞬过台∑<∞。 证:分别引入序列{P,n≥0和{r,n≥的形式上的母函数 P(s)= P("s”=+∑P"s",F2(s)=∑∫ 于是
∑ ∑ ∑ ∑ ∑ = − = = − = = = = = = = = = = = = = ≠ ≠ = = = = = = = = = = = = = = n l n l jj l ij n l ij n l n l ij n l l n l ij n ij n l ij n n n ij f P P l X i P X j X j P l X i P X j X i X j X j X j P l X i P X j l X i P l X j X i P P X j X i 1 ( ) ( ) 1 0 1 0 0 1 1 1 0 0 1 0 0 ( ) ( ) ( ) ( ) ( , , , ) ( ) ( , ) ( , ) ( ) τ τ τ τ τ L 推论 4.4.1：i → j ⇔ fij > 0。 定义 4.4.1： 若 fii =1，称状态i 为常返的(recurrent)；若 fii <1，则称状态i 为瞬 过的(transient)。 如果状态i 为常返的，系统无穷次返回状态 的概率为 1；如果状态i 为瞬过， 系统无穷次返回状态i 的概率为 0。 i 定理 4.4.2：状态i 为常返的⇔ ∑ = ∞ ；状态 为瞬过 。 ∞ =1 ( ) n n Pii i ⇔ ∑ < ∞ ∞ =1 ( ) n n Pii 证：分别引入序列{ , 0} ( ) P n ≥ n ij 和{ , 1} ( ) f n ≥ n ij 的形式上的母函数 ∑ ∑ ∞ = ∞ = = = + 1 ( ) 0 ( ) ( ) n n n ij ij n n n ij ij P s P s δ P s ， ∑ ∞ = = 1 ( ) ( ) n n n ij ij F s f s 于是 6
P(s)=+∑∑f 6+∑∑ 6+∑/(s∑P =δn+∑fms∑Psn 6+F(s)P(s) 令i=j,则P(s) 1-()故 EPim=lim P (S)=1-lim F, (S)l-fu s→1 推论42:若状态j是非常返即瞬过的,则对任意i∈S,∑P<∞,此时 lim pm)=0 对于常返态,进一步来研究它的平均常返时间:H1=E1=∑n/m 定义44.2:若1<∞,则称i为正常返( positive recurrent);若A1=∞则称i为零 常返 lull recurrent);一个正常返非周期状态称为遍历态 ergodic state)。 定理44.3:若i为常返,则i为零常返台limP=0 推论44.3:若状态j是零常返的,则对任意i∈S, lim P=0。 证明:由于P=∑fP"≤∑fPm+∑f0,于是,先固定m,令n→∞ 有∑p-0→0。由于=∑∫”sl,故再令m→∞时,∑/→0,故 limP)=0
( ) ( ) ( ) 1 0 ( ) ( ) 1 ( ) ( ) 1 ( ) ( ) 1 1 ( ) ( ) F s P s f s P s f s P s f P s P s f P s ij ij jj l n n n jj l l ij ij l n l n l n l jj l l ij ij l n n l n l jj l ij ij n n n l n l jj l ij ij ij = + = + = + = + = + ∑ ∑ ∑ ∑ ∑∑ ∑∑ ∞ = ∞ = ∞ = − ∞ = − ∞ = ∞ = − ∞ = = − δ δ δ δ δ 令i = j ，则 1 ( ) 1 ( ) F s P s ii ii − = 。故 ii ii s ii s n n ii F s f P P s − = − = = − − → → ∞ = ∑ 1 1 1 lim ( ) 1 lim ( ) 1 1 0 ( ) 。 推论 4.4.2：若状态 j 是非常返即瞬过的，则对任意i ∈ S ， ，此时 。 ∑ < ∞ ∞ =0 ( ) n n Pij lim 0 ( ) = →∞ n ij n P 对于常返态i ，进一步来研究它的平均常返时间： ∑ 。 ∞ = = = ⋅ 1 ( ) n n i ii ii µ Eτ n f 定义 4.4.2：若µ i < ∞，则称i 为正常返(positive recurrent)；若µ i = ∞ 则称i 为零 常返(null recurrent)；一个正常返非周期状态称为遍历态(ergodic state)。 定理 4.4.3：若i 为常返，则i 为零常返 lim 0。 ( ) ⇔ = →∞ n ii n P 推论 4.4.3：若状态 j 是零常返的，则对任意i ∈ S ，lim ( ) = 0。 →∞ n ij n P 证明：由于 ∑ ∑ ∑ ，于是，先固定 ，令 = = + − = − = ≤ + n l m l ij m l n l jj l ij n l n l jj l ij n ij P f P f P f 1 ( ) 1 ( ) ( ) 1 ( ) ( ) ( ) m n → ∞ 有 0。由于 1 ∑ ( ) ( ) → = − m l n l jj l fij P ∑ ∞ = = 1 ( ) n n ij ij f f ≤1，故再令 m → ∞ 时， ，故 。 0 1 ∑ ( ) → ∞ l=m+ l ij f lim 0 ( ) = →∞ n ij n P 7
定理444:若i遍历态,则limP(=-;若i是周期为d的正常返态,则 lim p 证明:由于P2()=1-F()酸(1-s)()≈1-s 1-F(s两边令s→1,则左边 lim(1-s)P(s)=lir n) lim p(n) k+1 右边im1-5 =im 1-Fn(s)x→rFn(s)1 ,因此imP(m)1 定理45:若状态/是遍历的,则对任意/∈,lmP=. 定理4.4.6:若j常返且j→i,则f=1。 证明:反证,若f0, 由于j→i,故从j出发,将以某个正概率经过有限步不能回到j,故∫0
定理 4.4.4：若 i 遍历态，则 i n ii n P µ 1 lim ( ) = →∞ ；若 i 是周期为 d 的正常返态，则 i nd ii n d P µ = →∞ ( ) lim 。 证明：由于 1 ( ) 1 ( ) F s P s ii ii − = ，故 1 ( ) 1 (1 ) ( ) F s s s P s ii ii − − − = ，两边令s →1− ，则左边 0 ( ) ( ) 0 0 ( ) 1 0 0 ( ) 1 0 0 ( ) 1 1 lim 1 lim lim lim lim(1 ) ( ) lim lim lim n ii n k n n ii k k n n k n n n ii k s k n n k n n n ii s k n n n n n ii s ii s P k P s P s s P s s P s s P s →∞ = →∞ = = →∞ → = = → →∞ ∞ = ∞ = → → = + = = − = = ∑ ∑ ∑ ∑ ∑ ∑ ∑ − − − − 右边 ii i s ii s F s F s s µ 1 ( ) 1 lim 1 ( ) 1 lim 1 1 = ′ = − − → − → − ，因此 i n ii n P µ 1 lim ( ) = →∞ 。 定理 4.4.5：若状态 j 是遍历的，则对任意i ∈ S ， j n ij ij n f P µ = →∞ ( ) lim 。 定理 4.4.6：若 j 常返且 j → i ，则 fij =1。 证明：反证，若 fij 0 j → i ，故从 j 出发，将以某个正概率经过有限步不能回到 j ，故 。矛 盾！ f jj →∞ n ii n P 8
i遍历台∑P=∞且limP=->0 定理447:若i>j,则它们或同为瞬过或同为常返;当同为常返时或同为零常 返或同为正常返 例441: Markov链Xn,状态空间为S=12,34},一步转移矩阵为 4 44 P 0 1—4000 01 非周期不可约 Markov链,由于1状态f 4m=)=f1,fm=0,n>4 故1状态常返且A1=5故为正常返,1状态为遍历,因而所有状态是遍历的。 下面给出不可约链是否常返的判别方法。 定理44.8:设不可约 Markov链Xn,状态空间为S={012},一步转移矩阵 为P。则X常返台下列方程组没有非零的有界解: ∑P 45平稳分布与极限分布 定义45.1:设X为 Markov链,状态空间为S,一步转移概率矩阵为P,若实 数{z,i∈S}满足: 1)兀1≥0,i∈S且∑x,=1; 2)x=∑xP1∈S,即m=x,这里x=(x,x2…不到 则称{x1,l∈S}为 Markov链Xn的平稳分布 下面考察非周期不可约 Markov链,由上一节推论442,推论443及定理445, 44.6知
i 遍历⇔ ∑ = ∞ 且 ∞ =1 ( ) n n Pii 0 1 lim ( ) = > →∞ i n ii n P µ 。 定理 4.4.7：若i ↔ j ，则它们或同为瞬过或同为常返；当同为常返时或同为零常 返或同为正常返。 例 4.4.1：Markov 链 X n ，状态空间为S = {1,2,3,4}，一步转移矩阵为 ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = 1 0 0 0 0 0 0 1 0 0 1 0 4 1 4 1 4 1 4 1 P 非周期不可约 Markov 链，由于 1 状态 , 0, 4 4 1 ( ) 11 (4) 11 (3) 11 (2) 11 (1) f11 = = f = f = f f = n > n ， 故 1 状态常返且 2 5 µ1 = 故为正常返，1 状态为遍历，因而所有状态是遍历的。 下面给出不可约链是否常返的判别方法。 定理 4.4.8：设不可约 Markov 链 X n ，状态空间为S = {0,1,2L}，一步转移矩阵 为 P 。则 X n 常返⇔ 下列方程组没有非零的有界解： , 1,2,L 1 = ∑ = ∞ = z P z i j i ij j 4.5 平稳分布与极限分布 定义 4.5.1：设 X n 为 Markov 链，状态空间为S ，一步转移概率矩阵为 P ，若实 数{π i ,i∈ S}满足： 1) π i ≥ 0,i ∈S 且∑ =1； i∈S π i 2) P i S ，即 j S i = ∑ j ji ∈ ∈ π π , πP = π ，这里 ( ) S π = π 1 ,π 2 Lπ 则称{π i ,i∈ S}为 Markov 链 X n 的平稳分布。 下面考察非周期不可约Markov链，由上一节推论4.4.2，推论4.4.3及定理4.4.5， 4.4.6 知： 9
0,j为零常返或瞬过 lim p(m)=1 >0,j为正常返 vi∈S 定义452:若n步转移概率P极限limP=-≥0不依赖)为 Markov链Xn的 极限分布。 定理4.51:非周期不可约 Markov链是正常返链的充要条件是它存在平稳分布, 且此时平稳分布就是极限分布。 证明:注意:由上一节定理44.7,非周期不可约 Markov链的状态要么全是瞬过, 要么全是零常返,要么全是正常返,极限分布mP=1存在。 充分性(=)。若有平稳分布{x1∈S},则x1=∑xP。令n→,由于 r,≥0.i∈S且∑兀=1,极限与求和可交換,故 r,=im∑xP=∑ 。由于∑x,=1,故至少有一个>0,故状 态k是正常返,这样所有状态都为正常返 必要性(→)。设链是正常返的,于是1imp)=1>0。不妨设状态S为无穷。 由CK关系,P=∑PknP≥∑PP,两端令n→,有≥∑P 再令N→∞,有1≥S1Pn,。必对任意j成立等号,若不然,则由于 ≤1,保证以下求和可以交换次序 2∑14 S>YIP=> P 矛盾!这样一 P,vj,故 k=o Alk n→) 有1=∑11,故∑ Ak A J∈s}为平
i S j j P j n ij n ∀ ∈ ⎪ ⎩ ⎪ ⎨ ⎧ > = →∞ ， 为正常返 为零常返或瞬过 0 1 0, lim ( ) µ 。 定义4.5.2：若n 步转移概率 Pij (n) 极限 0( ) 1 lim ( ) P i j n ij n = ≥ 不依赖 →∞ µ 为Markov链 的 极限分布。 X n 定理 4.5.1：非周期不可约 Markov 链是正常返链的充要条件是它存在平稳分布， 且此时平稳分布就是极限分布。 证明：注意：由上一节定理 4.4.7，非周期不可约 Markov 链的状态要么全是瞬过， 要么全是零常返，要么全是正常返，极限分布 j n ij n P µ 1 lim ( ) = →∞ 存在。 充分性 (⇐) 。若有平稳分布 {π i ,i∈ S} ，则 ∑∈ = i S n j iPij ( ) π π 。令 n → ∞ ，由于 π i ≥ 0,i ∈ S 且 ∑ =1 ，极限与求和可交换，故 i∈S π i S j i j i i S n i ij n j P µ µ π π π 1 1 lim ( ) = ∑ = ∑ = ∈ ∈ →∞ 。由于∑ =1 i∈S π i ，故至少有一个 0 1 > µ k ，故状 态k 是正常返，这样所有状态都为正常返。 必要性(⇒) 。设链是正常返的，于是 0 1 lim ( ) = > →∞ j n ij n P µ 。不妨设状态 为无穷。 由 C—K 关系， ，两端令 S ∑ ∑= − ∞ = − = ≥ N k kj n ik k kj n ik n Pij P P P P 0 ( 1) 0 ( ) ( 1) n → ∞，有 ∑= ≥ N k kj j k P 0 1 1 µ µ ， 再令 N → ∞ ，有 P j k kj j k ≥ ∑ ∀ ∞ = , 1 1 µ 0 µ 。必对任意 j 成立等号，若不然，则由于 1 1 0 ∑ ≤ ∞ j= µ j ，保证以下求和可以交换次序。 ∑ ∑∑ ∑∑ ∑ ∞ = ∞ = ∞ = ∞ = ∞ = ∞ = > = = 0 0 0 0 0 0 1 1 1 1 k j k k kj j k k kj j j k P P µ µ µ µ ，矛盾！这样 P j k kj j k = ∑ ∀ ∞ = , 1 1 µ 0 µ ，故 ∑ ∞ = = 0 1 1 ( ) k n kj j k P µ µ ，令n → ∞有 ∑ ∞ = = 0 1 1 1 µ j k µ k µ j ，故 1 1 0 ∑ = ∞ k = µ k ， ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ j ∈ S j , 1 µ 为平 10