北大随机过程课件：第 2 章 第 4 讲 马尔可夫链渐进分析

马尔可夫链的渐进分析（续三）马尔可夫链的例子：例1设有一个三状态{0,1,2}的马尔可夫链，它的一步转移概率矩阵是⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=5.03.02.03.04.03.01.04.05.0P例2设有一个无穷状态{0,1,2,3,……},的齐次马尔可夫链，它的一步转移概率是001122100000100000100000100000jjpppppppp−⎡⎤⎢⎥−⎢⎥⎢⎥−⎢⎥⎢⎥⎢⎥−⎢⎥⎣⎦LLLL例3无限随机游动例4设有一个具有一个弹性壁的随机游动，它的状态空间是{0,1,2,3,}，0是弹性壁例5艾伦菲斯特（Ehrenfest）模型例6设有一个具有两个吸收壁的随机游动，它的状态空间是{-2,-1,0,1,2},-2和2为吸收态。问题：状态分析：常返态、非常返态，状态空间的分解，闭集渐进分析平稳分布：平稳分布存在的条件；平稳分布的特性；确定平稳分布的方法；过渡分析：到达常返态的概率、进入时间的分布与期望状态转移概率的渐进性和平稳分布定理1设有一个有限状态的马尔可夫链，若存在一个正整数m，使得对状态空间的任何状态i,j有0)(mjip，则π=∞→)(limnnP。极限矩阵π的性质：矩阵有相同的行矢量，每一列元素都相同。pππ=推论1：π的行矢量满足下列关系：=ππp，1=∑iiππ给出状态的极限分布：()(1)()limlimlimnnnnnn+→∞→∞→∞====πppppπp，=ππpiijjipππ=∑归一化条件，1=∑iiπ矩阵π是唯一的推论2：系统稳定后状态的概率（渐进状态）与初始状态无关，稳态分布为π的行矢量系统稳定后处于状态j的概率：00()0()000()(/)()()lim()lim()()()nninijinnijnniijijijPjPjiPiPPiPjPPiPiPiξξξξξξξπξπξπ→∞→∞===============∑∑∑∑∑jnjinnnpjPπξ===∞→∞→)(lim}{lim初始状态概率分布[]000(0),(1)()Wpppnξξξ====L稳态分布W=ππ的行矢量马尔可夫链的稳态渐进分析举例例1设有一个三状态{0,1,2}的马尔可夫链，它的一步转移概率矩阵是⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=5.03.02.03.04.03.01.04.05.0P，求它的极限分布。解：按照稳态分布的存在定理进行判断，三状态{0,1,2}的马尔可夫链存在稳态解。设极限分布是()210ππππ=，它满足方程Pππ=，即15.03.01.03.04.04.02.03.05.0210221012100210=++=++=++=++πππππππππππππππ则极限分布是()⎟⎠⎞⎜⎝⎛==6218,6223,6221210ππππ判断稳态解的存在性，并求马尔科夫链的稳态解例2设有一个无穷状态{0,1,2,3,},的齐次马尔可夫链，它的一步转移概率是，01000001211011232202210j,1,0,(0,1),1,0,(0,2),1,0,(0,3),1,0,(0,)iiijjjjjipppppipppppipppppipppppij+==−=≠==−=≠==−=≠==−=≠LL求状态0的特性。解：001122100000100000100000100000jjpppppppp−⎡⎤⎢⎥−⎢⎥⎢⎥−⎢⎥⎢⎥⎢⎥−⎢⎥⎣⎦LLLL所有的状态之间是相同的，状态空间是一个不可约闭集。所有状态或全部是常返，或全部是非常返的分析0状态的常返特性求)(00nf0)1(001pf−=10010)2(00)1(pppppf−=−=12102101210)(00)1(−−−−−−=−=nnnnnnpppppppppppfLLL12101)(001−−=−=∑nnnknppppfL迟早返回0状态的概率是()12101)(0000lim1lim−−∞→=∞→−==∑nnnnknnppppffL0状态是常返的条件是()0lim1210=−−∞→nnnppppL这等价于∞=∑∞=01lnnnp如果L,2,1,0,)1/(1==+−nepnn，则有，∑∑∞=∞=∞=+=00111lnnnnnp，这个链是常返的。如果L,2,1,0,2)1/(1==+−nepnn，则有，∑∑∞=∞=∞+=020)1(11lnnnnnp，这个链是非常返的。它迟早返回零状态的概率是8070.0)2exp(131211exp1)1(1exp1220200=−−=⎭⎬⎫⎩⎨⎧⎥⎦⎤⎢⎣⎡+++−−=⎭⎬⎫⎩⎨⎧+−−=∑∞=πLnnf结论：0状态是常返的条件是()0lim1210=−−∞→nnnppppL分析0状态的常返特性，研究从0状态出发，返回0状态的概率。例3无限制随机游动的0状态常返行为的分析解：它的一步转移概率是，⎪⎩⎪⎨⎧−+≠===−+1,1,011iijifpqpppjiiiii无限制随机游动各状态都相通，则所有状态或全部是常返的或全部是非常返的。研究状态0的常返和非常返的性质：可以计算()001nnf∞=∑。如果()001nnf∞=∑小于1，则0状态是非常返的，如果()001nnf∞=∑等于1，则0状态是常返的。也可以计算∑∞=1)(00nnp。如果∑∞=1)(00nnp是有限的，则0状态是非常返的，如果∑∞=1)(00nnp是无限的，则0状态是常返的。引用研究随机游动的矩生成函数：返回原点的概率()001nnf∞=∑：2()114Vzpqz=−−2121(1)1,1/2(1)1,1/2nnnnvVzpqvVzpq∞=∞========≠≠∑∑返回原点的概率之和∑∞=1)(00nnp：21()14Uzpqz=−2121(1),1/2(1),1/2nnnnuUzpquUzpq∞=∞====∞====∞≠≠∑∑结论：p=1/2，零状态是常返的，p≠1/2零状态是非常返的。分析0状态的常返特性，研究从0状态出发，返回0状态的概率。例4设有一个具有一个弹性壁的随机游动，它的状态空间是{0,1,2,3,}，0是弹性壁试分析各个状态的特性。解：状态之间的转移概率是，)1,0(,0)1,1,0(,0),3,2,1(,),2,1,0(,00011≠=−+≠≠======−+kpjjkjpqpjqpjppkkjjjjjLLLL绘出状态转移图:定义到达稳态后系统处于状态j的概率是)(jπ，系统有平衡方程：)1()0(ππqp=LLLLLL)1()()3()2()2()1(+===jqjpqpqpππππππ平衡方程分析：系统的稳态状态方程组：)0()1()0()0(ππππqqqp+=+即，)1()0(ππqp=对于状态L,2,1有LLLLLL)1()1()()()1()3()2()2()0()2()1()1(−++=++=++=+jpjqjqjppqqppqqpππππππππππππ将上述方程进行整理，即得平衡方程：)1()0(ππqp=LLLLLL)1()()3()2()2()1(+===jqjpqpqpππππππ进一步得到递推关系，)0()1(ππqp=LLLLLL)0()1()()0()2()3()0()1()2(32πππππππππjqpjqpjqpqpqpqp⎟⎟⎠⎞⎜⎜⎝⎛=−=⎟⎟⎠⎞⎜⎜⎝⎛==⎟⎟⎠⎞⎜⎜⎝⎛==考虑到所有状态概率的和为1，有1)0()0()(000=⎟⎟⎠⎞⎜⎜⎝⎛⋅=⎟⎟⎠⎞⎜⎜⎝⎛=∑∑∑∞=∞=∞=jjjjjqpqpjπππ若qp，即2/1p∑∞=⎟⎟⎠⎞⎜⎜⎝⎛⋅0jjqp收敛，qp−=1)0(π，随机游动是常返的。若qp≥，即2/1≥p∑∞=⎟⎟⎠⎞⎜⎜⎝⎛⋅0jjqp不收敛，随机游动是非常返的，无极限分布。分析状态的一步转移概率，系统状态的特性，建立稳态概率的方程，求出稳态解。例5艾伦菲斯特（Ehrenfest）模型。一个坛子装有c个球，它们或是红色的或是黑色的。从坛子随机地摸出一个球并换入另一个颜色的球，经过n次摸换，把坛子中的黑球数定义为系统的状态,试分析各个状态的特性。解：设系统处于状态i，坛子中有i个黑球，则以概率ci摸出一个黑球，使坛子里变成i-1个黑球；以概率cic−摸出一个红球，使坛子里变成i+1个黑球。当系统处于状态i时，它转移到状态i-1的概率是ci，它转移到状态i+1的概率是cic−。⎪⎪⎩⎪⎪⎨⎧−=−===+−1,,2,1,0,,,3,2,1,11cicicpcicipiiiiLL系统的状态转移图：系统中各个状态是相通的，它是一个不可约的马尔科夫链，它的稳态分布存在。建立达到稳定状态后，系统的稳态方程是:()()()())1(1)()2(2)()1(1)1(1)1(1)1(1)()()0(0)2(2)1(1)1(1)1(1)0(0−⋅−−=⋅−⋅−−+⋅=−⋅−+−⋅−−−⋅−−++⋅+=⋅+⋅−⋅−+⋅=⋅+⋅−=−cccccccccccccccccccccjcjcjcjjcjjcjccccccccccππππππππππππππππLLLLLLLLL)2(2)1(1)1(1)0(0ππππ⋅=⋅−=−cccccc)()1(1)1(1)(cccjcjjcjcππππ⋅=−⋅+⋅+=⋅−LLL进一步得到递推关系:())0()1(1)()0(1)(1j)1()0(2)0(121)1(21)2()0(1)0()1(πππππππππππππ⋅⎟⎟⎠⎞⎜⎜⎝⎛=−⋅=⋅⎟⎟⎠⎞⎜⎜⎝⎛+=⋅+−=+⋅⎟⎟⎠⎞⎜⎜⎝⎛=⋅⋅−=⋅−=⋅⎟⎟⎠⎞⎜⎜⎝⎛=⋅=cccccjcjjcjccccccLLLLLL根据归一化条件，有⎟⎟⎠⎞⎜⎜⎝⎛==⋅=⎟⎟⎠⎞⎜⎜⎝⎛=⋅⎟⎟⎠⎞⎜⎜⎝⎛==−===∑∑∑jcjjcjcjccccjcjcj21)(2)0(2)0()0(0()(1000ππππππ分析状态的一步转移概率，系统状态的特性，建立稳态概率的方程，求出稳态解。例6天体物理中，质点进入和离开某一体积的马尔可夫链的状态分析。例7用动态平衡的观点解释艾伦菲斯特模型的平稳分布。（略）非常返状态的分析所要研究的问题：从任意一个状态出发，进入特定的常返状态的概率；以及进入这个常返状态所需时间的概率分布。系统状态的描述：设{}(),0,1,2,nnξ=L是一个齐次马尔可夫链，它的状态空间是I,状态空间按照各个状态的性质分成几个互不相交的常返态类{}L,2,1,=kAk，以及所有的非常返态所组成的子集cI，有ccccIIIIAAAAII∪==∪∪∪=LL2121其中cI是所有常返状态的集合。问题1、吸收概率吸收概率的定义：从某个状态i出发，进入某个常返状态子集kA的概率{}iAPk/，这个概率称作状态kA对于状态i的吸收概率。如果kAi∈，则{}1/=iAPk；如果kjAij≠∈,，则{}0/=iAPk；吸收概率方程组：{}{}//,ckkijkijcjIjAPAipPAjpiI∈∈=+∈∑∑。问题2、吸收时间吸收时间的定义：常返态对于状态i的吸收时间iT，指从某个起始状态i，进入常返状态的时间，是一个随机变量。iT的分析：iT的概率：令{}{},0,1,kiiAkPTnPTnn====∑L，是随机过程从状态i出发，经过n步进入常返状态类的概率。如果ciI∈，则{}0,01iiTPT===；如果有无穷多个非常返状态，随机过程可能永远停留在非常返状态中。iT的概率的递推方程：(1)(1)(),,0,cciijcjInniijjcjIPpiIPpPniI∈+∈=∈=⋅∈∑∑iT与吸收概率的关系：{}{}0lim{/}NiikNnkPTnPTPAi→∞===∞=∑∑{/}kkPAi∑是随机过程从非常返状态i出发，迟早进入常返状态的概率；如果该随机过程有无限多个非常返状态，迟早进入常返状态的概率可能小于1。1{/}kkPAi−∑是随机过程从非常返状态i出发,永远停留在非常返状态的概率.iT的数学期望：如果随机过程从非常返状态i出发，{}1iPT∞=，计算iT的数学期望。分析：吸收时间iT的数学期望为：{}()1niinETnP∞==∑，因为：(1)(),0cnniijjjIPpPn+