中科院随机过程讲义4

第四章离散时间Markov链4.1定义和一些例子在一些物理学、生物学、经济学等许多学科中，都有如下行为的系统：该系统是与时间有关的一个系统，如果已知系统在现在的状态，则此系统的过去所处的状态与将来所处状态是（条件）独立的，这个特性称为Markov性。本节我们考虑状态空间为离散的，用表示状态，参数集Sjiii,,,10或LT为离散的（一般表示时间），。{}L,2,1,0=T定义4.1.1：一个离散时间随机过程{}0,≥nXn称为Markov链，若对任意状态序列{}Sjiiiin⊂−,,,,110L)(),,,(11111001iXjXPiXiXiXiXjXPnnnnnn========+−−+L。记)(11,iXjXPPnnnnij===++，Sji∈,称为在时的一步转移概率（onesteptransitionprobabilities）。固定，转移概率，可以看成某个矩阵的第i行nn1,+nnijPj列元素，把该矩阵记为，即)(nP()SjinnijPnP∈+=,1,)(，它有可能是无穷维的。称为在时刻的一步转移概率矩阵。一般来说转移概率依赖于时刻，此时称该Markov链是非齐次的(inhomogenous)。但是，一个重要的情形是粒子在时刻s处于状态i，在时刻处于状态)(nPn1,+nnijPnts+j与在初始时刻0=s处于状态i，在时刻t处于状态j这两个过程是一样的。定义4.1.2：Markov链{称为齐次Markov链或称为有平稳转移概率的Markov链若它一步转移概率，}0,≥nXn1,+nnijPTn∈Sji∈,不依赖于n。对于齐次Markov链，由于一步转移概率不依赖于，因此记1,+nnijPn)(11,iXjXPPPnnnnijij====++，此时一步转移概率矩阵为()SjiijPP∈=,。以下不1特别指明，所讨论的均为齐次Markov链。以SiiXPpi∈==),(0记Markov链的初始分布（）。{0,≥nXn}1=∑∈Siip定理4.1.1：1).，1,0=≥∑∈SjijijPPSji∈∀,2).nniiiiiiinnPPPpiXiXiXP121100),,(1100−====LL例4.1.1：直线上的随机游动。假设从原点开始，粒子以p的概率向前迈一步，以q的概率向后迈一步，以r的概率在原地不动，1=++rqp。表示时刻的位置，则为齐次Markov链。状态空间nXnnX{}LL,2,1,0,1,2,−−=S，一步转移概率1,0,,,1,1,−====−+jiPqPrPpPijiiiiii，Sji∈∀,。这是无限制随机游动。4.2步转移概率矩阵n设状态空间为，一步转移概率为SP，初始分布为SiiXPpi∈==),(0的齐次Markov链{}，令0,≥nXn()()2,0)(≥======+niXjXPiXjXPPnmmnnij，表示经过个时刻，链从状态i转移到状态nj的概率，称为步转移概率。令，定义如下矩阵n⎩⎨⎧≠==jijiPij若若,0,1)0(Sji∈,()SjiijPP∈=,)0()0(，()SjiijPPP∈==,)1(，，2≥n()SjinijnPP∈=,)()(（n步转移概率矩阵）。定理4.2.1：1).()SjPpjXPsinijin∈∀==∑∈,)(2).(Chapman-Kolmogorovrelation)∑∈+=SknkjmikmnijPPP)()()(，Sji∈,2考虑矩阵乘法，上式可写成)()()(mnmnPPP⋅=+因此有1,)(≥=nPPnn例4.2.1：考虑两个状态的Markov链{}0,≥nXn，一步转移概率为⎟⎟⎠⎞⎜⎜⎝⎛−−=qqppP111010则⎟⎟⎠⎞⎜⎜⎝⎛−−+−−+⎟⎟⎠⎞⎜⎜⎝⎛+==qqppqpqppqpqqpPPnnn)1(1)(4.3状态空间的分解定义4.3.1：称状态i可到达（accessible）j，记为ji→，若存在使得；若0≥n0)(nijPijji→→,，则称ji,是相通的（communicate），记为ji↔。相通关系是一个等价关系，即满足：1)自反性：；ii↔2)对称性：ji↔，则ij↔；3)传递性：，则kjji↔↔,ki↔。两个状态若是相通的就称他们是处于同一类。Markov链的所有状态按相通关系分割成不同的等价类，两个等价类要么不相交，要么重合。定义4.3.2：一个状态集合C称为是闭集，若0=ijP对CjCi∉∀∈∀,。一旦粒子进入某个闭集，就永远停留在此闭集中。一个Markov链称为不可约（irreducible）若除整个状态空间外无别的闭集。3定理4.3.1：Mrakov链不可约⇔所有状态之间是相通的。证明：⇐显然。⇒（反证法）若存在两状态ji,不是相通的，不妨设ji→/。令{i→}kkC=，则首先；其次对Cj∉0,,=∉∀∈∀klPClCk。因此为一个闭集，而这与Mrakov链不可约矛盾。C例4.3.1：若Markov链一步转移概率矩阵为⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎝⎛=12/12/112/12/14/34/15432154321P{}2,1,{在相通意义下为两个等价类，此链是可约的。}5,4,3定义4.3.3：记{}0,1gcd)()(≥=niiPnnid，这里表示最大公因子（greatestcommondivisor），若，称为周期的（periodic），且周期为；否则称为非周期的（aperiodic）。gcd1)(idi)(id由定义立即可知，若n不是的倍数，则。)(id0)(=niiP定理4.3.2：若ji↔，则。)()(jdid=证明：由于ji↔，故使得。于是。若有s使得，则。由于nm,∃0,0)()(njimijPP0)(+mnjjP0)(siiP0)(++smnjjPmnjd+)(，smnjd++)(，因此sjd)(，进而)()(idjd。同理有)()(jdid，故)()(jdid=。定理4.3.3：存在正整数使得对所有的恒有。NNn0))((indiiP证明依赖于一个数论知识：若个正整数互素，则存在正整数使得对所有的都存在非负整数使得。对状态i，若kknnnL,,21NNnkaaaL,,21∑==kiiinan140,)()()(21kniiniiniiPPPL，则)(,)(,)(21idnidnidnkL互素，故存在正整数使得对所有的都存在非负整数使得，且。NNnkaaaL,,21∑==kiiinaind1)(0))((indiiP定理4.3.3的一个直接推论是：若，存在正整数使得对所有的恒有。0)(mjiPNNn0))((+indmjiP定理4.3.4：设P为不可约、非周期、有限状态Markov链的一步转移概率矩阵，则存在正整数使得当时，步转移概率矩阵NNnn)(nP的所有元素都大于0。4.4常返与瞬过在事件{上引入一个重要的概率，表示从出发在步转移时首次到达}iX=0)(nijfinj的概率。用式子表示即是)1,1,,(,00)()0(iXnkjXjXPffknnijij=−=≠===L。令，它表示从i出发最终转入到状态∑∞==1)(nnijijffj的概率。再引入一重要随机变量{}1,,:min0≥===nXiXnnijjτ，因此()iXnPfijnij===0)(τ。定理4.4.1：SjiPfPnllnjjlijnij∈∀=∑=−,,1)()()(证：5∑∑∑∑∑=−==−=========≠≠==================nllnjjlijnllnijnlllnijnlijnijnlnijnnijPfjXjXPiXlPjXjXjXiXjXPiXlPiXljXPiXlPiXjXlPiXjXPP1)()(1011100100100)()()(),,,()(),()(),()(τττττL推论4.4.1：0⇔→ijfji。定义4.4.1：若，称状态i为常返的(recurrent)；若1=iif1iif，则称状态i为瞬过的(transient)。如果状态i为常返的，系统无穷次返回状态的概率为1；如果状态i为瞬过，系统无穷次返回状态i的概率为0。i定理4.4.2：状态i为常返的；状态为瞬过。∞=⇔∑∞=1)(nniiPi∞⇔∑∞=1)(nniiP证：分别引入序列{}0,)(≥nPnij和{}1,)(≥nfnij的形式上的母函数∑∑∞=∞=+==1)(0)()(nnnijijnnnijijsPsPsPδ，∑∞==1)()(nnnijijsfsF于是6)()()(10)()(1)()(1)()(11)()(sPsFsPsfsPsfsPfsPfsPjjijijlnnnjjllijijllnlnlnjjllijijlnlnlnjjlijijnnnllnjjlijijij+=+=+=+=+=∑∑∑∑∑∑∑∑∞=∞=∞=−∞=−∞=∞=−∞==−δδδδδ令，则ji=)(11)(sFsPiiii−=。故iiiisiisnniifsFsPP−=−==−−→→∞=∑11)(lim11)(lim110)(。推论4.4.2：若状态j是非常返即瞬过的，则对任意Si∈，，此时。∞∑∞=0)(nnijP0lim)(=∞→nijnP对于常返态i，进一步来研究它的平均常返时间：。∑∞=⋅==1)(nniiiiifnEτµ定义4.4.2：若∞iµ，则称为正常返(positiverecurrent)；若i∞=iµ则称i为零常返(nullrecurrent)；一个正常返非周期状态称为遍历态(ergodicstate)。定理4.4.3：若i为常返，则i为零常返。0lim)(=⇔∞→niinP推论4.4.3：若状态j是零常返的，则对任意Si∈，。0lim)(=∞→nijnP证明：由于，于是，先固定，令∑∑∑+==−=−+≤=nmllijmllnjjlijnllnjjlijnijfPfPfP1)(1)()(1)()()(m∞→n有。由于01)()(→∑=−mllnjjlijPf∑∞==1)(nnijijff1≤，故再令∞→m时，，故。01)(→∑∞+=mllijf0lim)(=∞→nijnP7定理4.4.4：若遍历态，则iiniinPµ1lim)(=∞→；若是周期为的正常返态，则idindiindPµ=∞→)(lim。证明：由于)(11)(sFsPiiii−=，故)(11)()1(sFssPsiiii−−=−，两边令，则左边−→1s)(0)(00)(100)(100)(11lim1limlimlimlimlimlim)()1(limniinknniikknnknnniiskknnknnniiksnnnnniisiisPkPssPssPssPsPs∞→=∞→==→∞→==∞→→∞=∞=→→=+====−∑∑∑∑∑∑∑−−−−右边iiisiissFsFsµ1)(1lim)(11lim11=′=−−−−→→，因此iniinPµ1lim)(=∞→。定理4.4.5：若状态是遍历的，则对任意jSi∈，jijnijnfPµ=∞→)(lim。定理4.4.6：若j常返且ij→，则1=ijf。证明：反证，若，则从出发经过有限步，不能到达1ijfij的概率为，由于01−ijfij→，故从j出发，将以某个正概率经过有限步不能回到j，故。矛盾！1jjf综上，可得：i瞬过；∞⇔∑∞=1)(nniiPi零常返且；∞=⇔∑∞=1)(nniiP0lim)(=∞→niinPi正常返且；∞=⇔∑∞=1)(nniiP0lim)(_____∞→niinP8i遍历且∞=⇔∑∞=1)(nniiP01lim)(=∞→iniinPµ。定理4.4.7：若ji↔，则它们或同为瞬过或同为常返；当同为常返时或同为零常返或同为正常返。例4.4.1：Markov链，状态空间为nX{}4,3,2,1=S，一步转移矩阵为⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎝⎛=00011000010041414141P非周期不可约Markov链，由于1状态4,0,41)(11)4(11)3(11)2(11)1(11=====nfffffn，故1状态常