中国科学院：随机过程讲义：中科院随机过程讲义第4章

第四章 离散时间 Markov 链 4.1 定义和一些例子 在一些物理学、生物学、经济学等许多学科中，都有如下行为的系统：该系统 是与时间有关的一个系统，如果已知系统在现在的状态， 则此系统的过去所处的 状态与将来所处状态是 （条件） 独立的，这个特性称为Markov 性。本节我们考 虑状态空间为离散的，用表示状态，参数集S jiii ,,, 10 或L T为离散的（一般表 示时间），。 {}L,2,1,0=T 定义 4.1.1：一个离散时间随机过程 { }0, ≥nX n 称为 Markov 链，若对任意状态序 列 {} Sjiiii n ? ? ,,,, 110 L )(),,,( 11111001 iXjXPiXiXiXiXjXP nnnnnn ======== +??+ L。 记)( 1 1, iXjXPP nn nn ij === + + ，Sji ∈,称为在时的一步转移概率（one step transition probabilities）。固定，转移概率，可以看成某个矩阵的第i行 n n 1, +nn ij P j列 元素，把该矩阵记为，即)(nP ( ) Sji nn ij PnP ∈ + = , 1, )(，它有可能是无穷维的。称 为在时刻的一步转移概率矩阵。一般来说转移概率依赖于时刻，此时 称该Markov链是非齐次的 (inhomogenous)。但是，一个重要的情形是粒子在时 刻s处于状态i，在时刻处于状态 )(nP n 1, +nn ij P n ts + j与在初始时刻0=s处于状态i，在时刻t 处于状态j这两个过程是一样的。 定义 4.1.2：Markov链{称为齐次 Markov链或称为有平稳转移概率的 Markov链若它一步转移概率， }0, ≥nX n 1, +nn ij P Tn∈ Sji ∈,不依赖于n。 对于齐次Markov链，由于一步转移概率不依赖于，因此记 1, +nn ij P n )( 1 1, iXjXPPP nn nn ijij ==== + + ，此时一步转移概率矩阵为( ) Sji ij PP ∈ = , 。以下不 1 特别指明，所讨论的均为齐次 Markov 链。以SiiXPp i ∈== ),( 0 记Markov链 的初始分布（）。 {0, ≥nX n } 1= ∑ ∈Si i p 定理 4.1.1：1).，1,0 =≥ ∑ ∈Sj ijij PP Sji ∈? , 2). nn iiiiiiinn PPPpiXiXiXP 121100 ),,( 1100 ? ==== LL 例4.1.1：直线上的随机游动。假设从原点开始，粒子以p的概率向前迈一步， 以q的概率向后迈一步，以r的概率在原地不动，1=++ rqp。表示时刻 的位置，则为齐次Markov链。状态空间 n X n n X { }LL ,2,1,0,1,2, ??=S，一步转移概 率 1,0,,, 1,1, >?==== ?+ jiPqPrPpP ijiiiiii ，Sji ∈? ,。这是无限制随机游动。 4.2 步转移概率矩阵 n 设状态空间为，一步转移概率为S P，初始分布为SiiXPp i ∈== ),( 0 的齐次 Markov链{}，令0, ≥nX n ( ) ( ) 2, 0 )( ≥====== + niXjXPiXjXPP nmmn n ij ，表示 经过个时刻，链从状态i转移到状态n j的概率，称为步转移概率。令 ，定义如下矩阵 n ? ? ? ≠ = = ji ji P ij 若 若 ,0 ,1 )0( Sji ∈, ( ) Sji ij PP ∈ = , )0()0( ，( ) Sji ij PPP ∈ == , )1( ， ，2≥n ( ) Sji n ij n PP ∈ = , )()( （n步转移概率矩阵）。 定理 4.2.1：1). ( ) SjPpjXP si n ijin ∈?== ∑ ∈ , )( 2). (Chapman-Kolmogorov relation) ∑ ∈ + = Sk n kj m ik mn ij PPP )()()( ，Sji ∈, 2 考虑矩阵乘法，上式可写成 )()()( mnmn PPP ?= + 因此有 1, )( ≥= nPP nn 例4.2.1：考虑两个状态的Markov链{ }0, ≥nX n ，一步转移概率为 ? ? ? ? ? ? ? ? ? ? = qq pp P 1 1 1 0 10 则 ? ? ? ? ? ? ? ? ? ? + ?? + ? ? ? ? ? ? ? ? + == qq pp qp qp pq pq qp PP n nn )1(1 )( 4.3 状态空间的分解 定义 4.3.1：称状态i可到达（accessible）j，记为ji →，若存在使得； 若 0≥n 0 )( > n ij P ijji →→ ,，则称ji,是相通的（communicate），记为ji ?。 相通关系是一个等价关系，即满足： 1) 自反性：； ii ? 2) 对称性：ji ?，则ij ?； 3) 传递性：，则kjji ?? , ki ?。 两个状态若是相通的就称他们是处于同一类。Markov 链的所有状态按相通 关 系 分割成不同的等价类，两个等价类要么不相交，要么重合。 定义 4.3.2：一个状态集合C称为是闭集，若0= ij P对CjCi ??∈? ,。一旦粒子进 入某个闭集，就永远停留在此闭集中。一个Markov链称为不可约（irreducible） 若除整个状态空间外无别的闭集。 3 定理 4.3.1：Mrakov 链不可约 ?所有状态之间是相通的。 证明：?显然。?（反证法）若存在两状态ji,不是相通的，不妨设ji → / 。令 {i → }kkC =，则首先；其次对Cj? 0,, =??∈? kl PClCk。因此为一个闭集， 而这与Mrakov链不可约矛盾。 C 例4.3.1：若Markov链一步转移概率矩阵为 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 1 2/12/1 1 2/12/1 4/34/1 5 4 3 2 1 54321 P {}2,1 ,{在相通意义下为两个等价类，此链是可约的。 }5,4,3 定义 4.3.3：记{ }0,1gcd)( )( >≥= n ii Pnnid，这里表示最大公因子（greatest common divisor），若，称为周期的（periodic），且周期为；否则称 为非周期的（aperiodic）。 gcd 1)( >id i )(id 由定义立即可知，若n不是的倍数，则。 )(id 0 )( = n ii P 定理 4.3.2：若 ji ? ，则 。 )()( jdid = 证明：由于ji ?，故使得。于是。若有s使得 ，则。由于 nm,? 0,0 )()( >> n ji m ij PP 0 )( > +mn jj P 0 )( > s ii P 0 )( > ++ smn jj P mnjd +)(，smnjd ++)(，因此sjd )(，进而 )()( idjd。同理有)()( jdid，故)()( jdid =。 定理 4.3.3：存在正整数 使得对所有的 恒有 。 N Nn> 0 ))(( > ind ii P 证明依赖于一个数论知识：若个正整数互素，则存在正整数使得 对所有的都存在非负整数使得。对状态i，若 k k nnn L,, 21 N Nn> k aaa L,, 21 ∑ = = k i ii nan 1 4 0, )()()( 21 > k n ii n ii n ii PPP L，则 )( , )( , )( 21 id n id n id n k L互素，故存在正整数使得对所有的 都存在非负整数使得，且。 N Nn> k aaa L,, 21 ∑ = = k i ii naind 1 )( 0 ))(( > ind ii P 定理4.3.3的一个直接推论是：若 ，存在正整数 使得对所有的 恒有 。 0 )( > m ji P N Nn> 0 ))(( > + indm ji P 定理 4.3.4：设 P 为不可约、 非周期、 有限状态 Markov 链的一步转移概率矩阵， 则存在正整数 使得当 时， 步转移概率矩阵N Nn> n )(n P 的所有元素都大于 0。 4.4 常返与瞬过 在事件{上引入一个重要的概率，表示从 出发在 步转移时首次 到达 }iX = 0 )(n ij f i n j 的概率。用式子表示即是 )1,1,,(,0 0 )()0( iXnkjXjXPff kn n ijij =?=≠=== L。 令，它表示从i出发最终转入到状态 ∑ ∞ = = 1 )( n n ijij ff j的概率。再引入一重要随机变 量{}1,,:min 0 ≥=== nXiXn nij jτ，因此( )iXnPf ij n ij === 0 )( τ。 定理 4.4.1： SjiPfP n l ln jj l ij n ij ∈?= ∑ = ? ,, 1 )()()( 证： 5 ∑ ∑ ∑ ∑ ∑ = ? = = ? = = = ===== =≠≠===== ====== ==== === n l ln jj l ij n l lnij n l llnij n l ijnij n l nij n n ij Pf jXjXPiXlP jXjXjXiXjXPiXlP iXljXPiXlP iXjXlP iXjXPP 1 )()( 1 0 1 1100 1 00 1 0 0 )( )()( ),,,()( ),()( ),( )( τ τ ττ τ L 推论 4.4.1：0>?→ ij fji。 定义 4.4.1： 若，称状态i为常返的 (recurrent)；若1= ii f 1< ii f，则称状态i为瞬 过的 (transient)。 如果状态 i为常返的， 系统无穷次返回状态 的概率为 1； 如果状态 i为瞬过， 系统无穷次返回状态 i的概率为 0。 i 定理 4.4.2：状态 i为常返的 ；状态 为瞬过。 ∞=? ∑ ∞ =1 )( n n ii P i ∞<? ∑ ∞ =1 )( n n ii P 证：分别引入序列{ }0, )( ≥nP n ij 和{ }1, )( ≥nf n ij 的形式上的母函数 ∑∑ ∞ = ∞ = +== 1 )( 0 )( )( n nn ijij n nn ijij sPsPsP δ， ∑ ∞ = = 1 )( )( n nn ijij sfsF 于是 6 )()( )( 10 )()( 1 )()( 1 )()( 11 )()( sPsF sPsf sPsf sPf sPfsP jjijij l n n n jj ll ijij l ln ln ln jj ll ijij l n ln ln jj l ijij n n n l ln jj l ijijij += += += += += ∑∑ ∑∑ ∑∑ ∑∑ ∞ = ∞ = ∞ = ? ∞ = ? ∞ = ∞ = ? ∞ == ? δ δ δ δ δ 令，则ji = )(1 1 )( sF sP ii ii ? =。故 iiii s ii s n n ii fsF sPP ? = ? == ? ? → → ∞ = ∑ 1 1 )(lim1 1 )(lim 1 1 0 )( 。 推论 4.4.2：若状态 j 是非常返即瞬过的，则对任意 Si∈ ， ，此时 。 ∞< ∑ ∞ =0 )( n n ij P 0lim )( = ∞→ n ij n P 对于常返态i，进一步来研究它的平均常返时间：。 ∑ ∞ = ?== 1 )( n n iiiii fnEτμ 定义 4.4.2：若∞< i μ，则称为正常返 (positive recurrent)；若i ∞= i μ则称i为零 常返 (null recurrent)；一个正常返非周期状态称为遍历态 (ergodic state)。 定理 4.4.3：若 i为常返，则 i为零常返 。 0lim )( =? ∞→ n ii n P 推论 4.4.3：若状态 j 是零常返的，则对任意 Si∈ ，。 0lim )( = ∞→ n ij n P 证明：由于，于是，先固定，令 ∑∑∑ +== ? = ? +≤= n ml l ij m l ln jj l ij n l ln jj l ij n ij fPfPfP 1 )( 1 )()( 1 )()()( m ∞→n 有。由于0 1 )()( → ∑ = ? m l ln jj l ij Pf ∑ ∞ = = 1 )( n n ijij ff 1≤，故再令∞→m时，，故 。 0 1 )( → ∑ ∞ +=ml l ij f 0lim )( = ∞→ n ij n P 7 定理 4.4.4：若 遍历态，则i i n ii n P μ 1 lim )( = ∞→ ；若 是周期为 的正常返态，则i d i nd ii n d P μ = ∞→ )( lim 。 证明：由于 )(1 1 )( sF sP ii ii ? =，故 )(1 1 )()1( sF s sPs ii ii ? ? =?，两边令，则左边 ? →1s )(0 )( 0 0 )( 1 0 0 )( 1 0 0 )( 11 lim 1 limlimlim limlimlim)()1(lim n ii n k n n ii k k n n k n nn ii sk k n n k n nn ii ks n n n nn ii s ii s P k P s sP s sP s sP sPs ∞→ = ∞→ = = →∞→ = = ∞→→ ∞ = ∞ = →→ = + == ==? ∑ ∑ ∑ ∑ ∑ ∑ ∑ ? ??? 右边 iii s ii s sFsF s μ 1 )( 1 lim )(1 1 lim 11 = ′ = ? ? ?? →→ ，因此 i n ii n P μ 1 lim )( = ∞→ 。 定理 4.4.5：若状态 是遍历的，则对任意j Si∈ ， j ij n ij n f P μ = ∞→ )( lim 。 定理 4.4.6：若 j 常返且 ij → ，则 1= ij f。 证明：反证，若，则从出发经过有限步，不能到达1< ij f i j的概率为， 由于 01 >? ij f ij →，故从j出发，将以某个正概率经过有限步不能回到j，故。矛 盾！ 1< jj f 综上，可得： i瞬过 ； ∞<? ∑ ∞ =1 )( n n ii P i零常返 且 ； ∞=? ∑ ∞ =1 )( n n ii P 0lim )( = ∞→ n ii n P i正常返 且 ； ∞=? ∑ ∞ =1 )( n n ii P 0lim )( _____ > ∞→ n ii n P 8 i遍历 且∞=? ∑ ∞ =1 )( n n ii P 0 1 lim )( >= ∞→ i n ii n P μ 。 定理 4.4.7：若 ji ? ， 则 它们或同为瞬过或同为常返； 当同为常返时或同为零常 返或同为正常返。 例4.4.1：Markov链，状态空间为 n X { }4,3,2,1=S，一步转移矩阵为 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 0001 1000 0100 4 1 4 1 4 1 4 1 P 非周期不可约Markov链，由于1状态4,0, 4 1 )( 11 )4( 11 )3( 11 )2( 11 )1( 11 >===== nfffff n ， 故1状态常返且 2 5 1 =μ故为正常返，1状态为遍历，因而所有状态是遍历的。 下面给出不可约链是否常返的判别方法。 定理 4.4.8：设不可约 Markov 链 ，状态空间为 n X { }L2,1,0=S ，一步转移矩阵 为 P 。则 常返 n X ?下列方程组没有非零的有界解： L,2,1, 1 == ∑ ∞ = izPz j jiji 4.5 平稳分布与极限分布 定义 4.5.1：设为Markov链，状态空间为，一步转移概率矩阵为 n X S P，若实 数{}Si i ∈,π满足： 1) Si i ∈≥ ,0π且； 1= ∑ ∈Si i π 2) ，即SiP Sj jiji ∈= ∑ ∈ ,ππ ππ =P，这里( ) S ππππ L 21 ,= 则称{}Si i ∈,π为Markov链的平稳分布。 n X 下面考察非周期不可约Markov链，由上一节推论4.4.2，推论4.4.3及定理4.4.5， 4.4.6知： 9 Si j j P j n ij n ∈? ? ? ? ? ? > = ∞→ 为正常返， 为零常返或瞬过 0 1 ,0 lim )( μ 。 定义 4.5.2：若步转移概率极限n )(n ij P )(0 1 lim )( iP j n ij n 不依赖≥= ∞→ μ 为Markov链的 极限分布。 n X 定理 4.5.1：非周期不可约 Markov 链是正常返链的充要条件是它存在平稳分布， 且此时平稳分布就是极限分布。 证明：注意：由上一节定理4.4.7，非周期不可约Markov链的状态要么全是瞬过， 要么全是零常返，要么全是正常返，极限分布 j n ij n P μ 1 lim )( = ∞→ 存在。 充分性。若有平稳分布)(? { }Si i ∈,π，则 ∑ ∈ = Si n ijij P )( ππ。令，由于∞→n Si i ∈≥ ,0π且，极限与求和可交换，故1= ∑ ∈Si i π j Si j i Si n iji n j P μμ πππ 11 lim )( === ∑∑ ∈∈ ∞→ 。由于1= ∑ ∈Si 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 ij PPPPP 0 )1( 0 )1()( ∞→n，有 ∑ = ≥ N k kj kj P 0 11 μμ ， 再令，有∞→N jP k kj kj ?≥ ∑ ∞ = , 11 0 μμ 。必对任意成立等号，若不然，则由于j 1 1 0 ≤ ∑ ∞ =j j μ ，保证以下求和可以交换次序。 ∑∑∑∑∑∑ ∞ = ∞ = ∞ = ∞ = ∞ = ∞ = ==> 000000 1111 k k kj kj k jk kj k j j PP μμμμ ，矛盾！这样jP k kj kj ?= ∑ ∞ = , 11 0 μμ ，故 ∑ ∞ = = 0 )( 11 k n kj kj P μμ ，令有∞→n ∑ ∞ = = 0 111 k jkj μμμ ，故1 1 0 = ∑ ∞ =k k μ ， ? ? ? ? ? ? ? ? ? ? ∈Sj j , 1 μ 为平 10 稳分布。 推论 4.5.1：非周期不可约正常返 Markov 链的平稳分布是唯一的。 例4.5.1：（带一个弹性壁的随机游动）设Markov链状态空间为， 一步转移矩阵为 n X {}L,2,1,0=S P，其中L2,1,0, 1, == + ipP ii ，L,2,1, 1, == ? iqP ii ，， 。 qP = 00 0,1 >=+ pqqp 此链为非周期不可约Markov链。先决定何时常返。由上一节定理4.4.8，考察 L3,2,, 1121 =+== +? ipzqzzpzz iii 或 L3,2),(, 11112 =?=?=? ?+ izz p q zzz p q zz iiii 由此L,2,1, 11 = ? ? ? ? ? ? ? ? =? + iz p q zz i ii ，故L,2,1, 1 1 1 = ? ? ? ? ? ? ? ? ? ? = iz p q p q z i i 若qp >，{为有界非零解，此时链非常返；若} i z qp ≤，{ } i z无界，即方程组无 有界非零的解，此时链常返。 进一步判断是正常返还是零常返。考察何时具有平稳分布。 L2,1,, 11100 =+=+= +? jqpqq jjj ππππππ 当qp =时，不存在平稳分布，此时链为零常返；当qp <时，平稳分布为 L2,1,0,1 = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?= j q p q p j j π，此时链为正常返。 定理 4.5.2：有限非周期不可约 Markov 链必是正常返链。 4.6 分支过程（branching process） 考虑某个群体，其一个个体繁衍下一代的子女数是随机的，可能是等， 有一定的概率分布，若用表示一个个体繁衍下一代的子女数，则是随机变量， L2,1,0 J J 11 设分布为。假定各代个体的繁衍能力相同且是独立的繁 衍下一代，表示第0代祖先的数目，一般假定为1，以表示第代中个体 数目，称为分支过程。以表示第代中第i个个体繁衍下一代数目， 独立同分布，共同分布为的分布，则 L2,1,0),( === kkJPp k 0 X n X n 0, ≥nX n i J n i J J ∑ = + =+++= n n X i iXn JJJJX 1 211 L 这样若给定则的分布就确定了，与无关，故为Markov 链，状态空间 n X 1+n X 11 , ?n XX L 0, ≥nX n { }L2,1,0=S，一步转移概率 () 0, 1 1 >? ? ? ? ? ? ===== ∑ = + ijJPiXjXPP i k knnij ，1 00 =P。 令1,)( 0 ≤= ∑ ∞ = ssps l l l φ为的母函数，定义J ss =)( 0 φ，)()( 1 ss φφ =， ()1,)()( 1 ≥= ? nss nn φφφ，显然( ) ( ))()()( sss nmmnmn φφφφφ == + 。 定理 4.6.1：)(s n φ 为 的母函数。 n X 证明：归纳法。设)(s n φ为的母函数，考虑的母函数记为。 n X 1+n X )( 1 sg n+ [] () 1)()( )()()( )()()( )()()()( ),()()( 1 010 0010 00 100 1 00 1 0 11 1 ≤== ==== ===== ======= ===== + ∞ == ∞ = ∑ ∞ = ∞ == ∞ = ∞ = ∞ == ∞ = ∞ = + ∞ = ∞ = + ∞ = ++ ∑∏∑ ∑∑∑∑ ∑∑ ∑∑∑ ∑∑∑ = sss siXPEsiXP EsiXPsjJPiXP siXPjJPsiXPiXjXP siXjXPsjXPsg nn i i n i k J i n J i n j j i k k i n ji j n i k k ji j nnn ji j nn j j nn k i k k φφφ φ 对于分支过程，我们主要关心的是，种群灭绝概率，以表示，则 q 12 {} {} )0(lim)0(lim0lim0 11 n n n n n l l n n n XPXPXPq φ ∞→∞→ = ∞→ ∞ = === ? ? ? ? ? ? ? ? == ? ? ? ? ? ? ? ? == UU （注意{}{ }00 1 =?= +ll XX） 1 0 =p，种群不能发端；种群永不消亡。故以下假定。这时 ，故 0 0 =p 10 0 << p 0)( 1 1 >=′ ∑ ∞ = ? k k k kspsφ )(sφ在上单调非降。故 ]1,0[ 1)0()0()0(0 10 ≤≤≤≤=< n p φφφ L 序列)0( n φ单调非降有上界必有极限，故)0(lim0 0 n n qp φ ∞→ =≤<。另一方面 ()0()0( 1 nn φφφ = + ，令有∞→n )(qq φ=，故为方程q ss =)(φ的一个正根。近一 步有 定理 4.6.2：对于分支过程 ，设 n X 10 0 << p ， ，则 ∑ ∞ = == 1k k kpEJμ 1) 灭绝概率 是方程q ss =)(φ 的最小正根； 2) 11 =?≤ qμ 。 证明：1)设x为方程ss =)(φ的任意正根，由于)(sφ在上单调非降，故]1,0[ xx =≤ )()0( φφ，由归纳法立得x n ≤)0(φ，令∞→n有xq n n ≤= ∞→ )0(limφ。 2) 令10, )( )( 1 10 ≤<+== ∑ ∞ = ? ssp s p s s sf k k k φ ，则1)1(,)0( =∞= ff， 1)1(,)0( ?=′?∞=′ μff，，故0)( >′′ sf )(sf ′严格增。当1≤μ时，在， 恒为负，此时严格减，由 10 << s )(sf ′ )(sf 1)1( =f，在(0,1)中，从而方程1)( >sf ss =)(φ的 解不能在(0,1)内，故。若1=q 1>μ，由连续函数介值定理必有使得 。在，单调降，在，单调增。由，， 于是有使得，即 10 << x 0)( =′ xf ),0( x )(sf )1,(x )(sf 1)1( =f 1)( <xf ),0( 0 xs ∈ 1)( 0 =sf 00 )( ss =φ，故10 0 <≤< sq。 13