第四章离散时间 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