马尔可夫链原理及应用实例探讨

马尔可夫链原理及应用实例探讨祝学衍吉林大学地球科学学院（130061）Email:[e-mail]摘要：马尔可夫链原理复杂，应用广泛。本文从其最原始的数学定义出发，逐步讨论它的转移概率矩阵，切普曼－柯尔莫哥洛夫方程（C－K方程），初始概率分布及在时刻的概率分布，并以城市公交客运量的预测模型为例佐证。m关键词：马尔可夫链；应用实例；客运量1引言马尔可夫过程是研究得相当深入，而且还在蓬勃发展的随机过程。随着现代科学技术的发展，很多在应用中出现的马氏过程模型的研究受到越来越多的重视。它的原始模型马尔可夫链，由俄国数学家A.A.马尔可夫于1907年提出。在现实世界中，有很多过程都是马尔可夫过程，本文拟从其最原始的数学定义出发，逐步讨论它的转移概率矩阵，切普曼－柯尔莫哥洛夫方程（C－K方程），初始概率分布及在时刻的概率分布，详尽阐述它的公式所表达的意义和应用的方法，并利用姜华平、陈海泳等人调查的城市客运量数据建立了独立的城市公交客运量的预测模型。m2随机过程[1]设随机试验的样本空间，T是一个数集（），如果对于每一个t，都有一个定义在样本空间上的随机变量EΩ(,T⊆−∞+∞)T∈Ω(),,Xtωω∈Ω，则称依赖于t的一族随机变量(){},,XttTω∈为随机过程或随机函数，简记为(){},XttT∈或()Xt，其中称为参数，称为参数集。tT当{}0,1,2,T=L，{}1,2,T=L，{},2,1,0,1,2,T=−−LL时，(){},XttT∈称为随机序列或时间序列。3马尔可夫过程马尔可夫过程是下述这样的一种过程[2]：在已经时刻系统所处状态的条件下，在时刻以后系统到达的情况与时刻以前系统所处的状态无关，完全取决于时刻系统所处的0t0t0t0t1状态。这个特性称为无后效性，也称为“马尔可夫性”。马尔可夫过程数学定义如下[3]：设(){},XttT∈为随机过程，如果对于任意正整数及，n12ntttL()()(){}112211,,,nnXtxXtxXtxP−−===L0，并且其条件分布为()()()(){}()(){},,,11221111PXtxXtxXtxXtxnnnnPXtxXtxnnnn≤===−−=≤=−−L则称(){},XttT∈为马尔可夫过程，或称该过程具有马尔可夫性。按照时间和状态的离散、连续情况马尔可夫过程可分为三类[2]：(1)时间与状态（空间）都离散的过程，称为马尔可夫链；(2)时间连续与状态（空间）离散的过程，称为连续时间的马尔可夫过链；(3)时间与状态（空间）都连续的马尔可夫过程。4马尔可夫链[1]4.1马尔可夫链的数学定义设随机序列(){},0,1,2,Xnn=L满足如下条件：(1)对于每一个()，n0,1,2,n=L()Xn取整数或它的子集(记为I)；(2)对于任意个非负整数1r+()1212,,,0rrnnnmnnnm≤LL和任意正整数，以及状态，有k12,,,,riiiijI∈L()()()(){}1122,,,,rrXniXniXniXmiP====L0，且()()()()(){}()(){}1122,,,,rrXmkjXniXniXniXmiPXmkjXmiP+=====+==L=，则称随机序列(){},0,1,2,Xnn=L为马尔可夫链，也称为随机序列(){},0,1,2,Xnn=L具有马尔可夫性或无后效性。条件概率()(){}PXmkjXmi+==称为马尔可夫链(){},0,1,2,Xnn=L在时刻从状态出发，在时刻mimk+转移到状态的转移概率，记作j(),ijpmmk+，即2()()(){},ijpmmkPXmkjXmi+=+==上述定义中，I叫做马尔可夫链(){},0,1,2,Xnn=L的状态空间。4.2转移概率矩阵因为马尔可夫链在时刻从任意一个状态m()iiI∈出发，到时刻mk+一定转移到状态空间I中的某一状态，所以转移概率(),ijpmmk+一定满足()()j,0,,,0,1,2,,1,2,.ijijIpmmkpmmkijImk∈1,++=∈==∑LL≥，由转移概率(),ijpmmk+为元素构成的矩阵称为马尔可夫链的k步转移概率矩阵，记为，即(),mmkΡ+r()()(),,ijmmkpmmkΡ+=+r。在转移概率矩阵中，每一行元素的和都等于1。如果k步转移概率(,ij)pmmk+不依赖于时刻，则称m(){},0,1,2,Xnn=L为齐次马尔可夫链或时齐马尔可夫链。此时，它的状态转移概率仅依赖于转移出发的状态i，转移步数和转移最后到达的状态kj，而与转移时刻无关，记为m()ijpk，即()()()(){},,,,0,1,2,,1,2,.ijijpkpmmkPXmkjXmiijImk=+=+==∈==LL于是步转移概率矩阵可记为k()kΡr，即()()()ijkpkΡ=r，通常规定(){100ijijijijpδ=≠==，，，且有()()j01,,,0,1,2,,1,ijijIpkpkijImk∈=∈==∑LL≥，2,.当转移步数时，称为一步转移概率，简记为1k=()1ijpijp，即()()(){}11,,,0,ijijppPXmjXmiijIm==+==∈=L1,2,如果马尔可夫链具有有限状态空间{}1,2,,IN=L，则以一步转移概率ijp为元素可以构成一个阶矩阵，记为，即NΡr3()1112121222121NNNNNNppppppppp⎡⎤⎢⎥⎢⎥Ρ=Ρ=⎢⎥⎢⎥⎣⎦LrrLMMMML如果马尔可夫链具有无限状态空间{}1,2,,I=L，仍然用Ρr表示以ijp为元素的矩阵，有()111221221pppp⎡⎤⎢⎥Ρ=Ρ=⎢⎥⎢⎥⎣⎦LrrLMM把矩阵称为一步转移概率矩阵。显然，矩阵ΡrΡr的所有元素都是非负的，且每一行元素的和都等于1。4.3切普曼－柯尔莫哥洛夫方程（Chapman－Kolmogrov方程）设(){},0,1,2,Xnn=L是齐次马尔可夫链，状态空间为I，则对于任意正整数，有,kl()()(),ijissjsIpklpkplijI∈+=∈∑，，此式称为切普曼－柯尔莫哥洛夫方程，简称C－K方程。C－K方程表明，“从状态i出发经kl+步转移到状态j”这一事件，可以分解为“从状态i出发经k步转移到达中间状态()ssI∈，再从出发经l步转移到状态sj”这样一些事件的并。对于不同的中间状态(ssI)∈，这样的事件是互不相容的。将C－K方程表示成矩阵的形式，得()()()klklΡ+=ΡΡrrr。在上式中，取，得。1kl==()()()()221111Ρ=Ρ+=ΡΡ=ΡΡ=Ρrrrrrrrr.若取，得。1,2kl==()()()()2331212Ρ=Ρ+=ΡΡ=ΡΡ=Ρrrrrrr一般地，有这表明齐次马尔可夫链的步转移概率矩阵等于k个一步转移概率矩阵的乘积，因此步转移概率可由一步转移概率得到。(),1,2,kkkΡ=Ρ=rrLkk4.4初始概率分布及时刻的概率分布m设(){},0,1,2,Xnn=L是马尔可夫链，状态空间为I。在初始时刻（）状态0n=()0X4的概率分布(){}0,jPXjpjI==∈，称为马尔可夫链(){},0,1,2,Xnn=L的初始概率分布，记作()()120,,,,jpppppj==∈ururLLI。在时刻（）状态mnm=()Xm的概率分布(){}(),,jPXmjpmjIm==∈≥0，称为马尔可夫链(){},0,1,2,Xnn=L在时刻的概率分布，记作m()()()()()12,,,,jpmpmpmpmj=∈urLLI，特别地，在时刻0m=的概率分布就是初始概率分布，可记作(){}()00jjPXjppjI,===∈。时刻的概率分布满足条件m()()j01,,0,1,2,jjIpmpmjIm∈=∈=∑L≥，。设(){},0,1,2,Xnn=L为齐次马尔可夫链。如果已知在时刻的概率分布m()()jpmjI∈及一步转移概率(),ijpijI∈，则知在时刻1m+的概率分布是()()1,jiijiIpmpmpjIm∈+=∈,0∑≥如果已经初始概率分布()jpjI∈及步转移概率m()(),,ijpmijIm∈≥1，则在时刻的概率分布为m()(),,jiijiIpmppmjIm∈=∈∑≥1①如果齐次马尔可夫链的状态空间为{}1,2,,IN=L，Ρr是一步转移概率矩阵，则①式可以表示为()()()()()1212,,,,,mNNpmpmpmpppm=Ρ1rLL≥，记()()120,,Nppppp==ururL，()()()()()12,,Npmpmpmpm=urL，则①式又可以表示为()mpmp=Ρururr②5应用实例——城市公交客运量的预测模型姜华平、陈海泳对某城市2002年居民各种出行方式所占比率的分布做了调查[4]，结果见表1。表1某城市2002年居民出行方式比率分布表出行方式公交车自行车步行其他比率19%14%56%11%与2001年相比，本时期（2002年）各个出行方式之间的变化转移情况如表2所示。表2某城市2001年至2002年居民出行方式转移概率表公交车自行车步行其他公交车90%4%2%4%自行车7%86%1%6%步行8%7%80%5%其他10%2%3%85%2001率概移转2002假设2006年该城市居民平均每天出行的总人次数468N=∑万人次，试预测2006年该城市公交的平均日客运量U。令代表2002年，代表2003年，0n=1n=2n=代表2004年，3n=代表2005年，n=4代表2006年，依次递推。又令(){},0,1,2,3,4Xnn=表示该城市居民自2002年到2006年的各年度出行方式，显然这是一个齐次马尔可夫链。它的初始概率分布为()()1234,,,0.19,0.14,0.56,0.11ppppp==ur其中1234,,,pppp分别代表该城市居民2002年乘坐公交车，骑自行车，步行，选择其他交通工具的出行次数频率。它的一步转移概率矩阵为：()0.900.040.020.040.070.860.010.0610.080.070.800.050.100.020.030.85⎡⎤⎢⎥⎢⎥Ρ=Ρ=⎢⎥⎢⎥⎣⎦rr6的概率分布，满足②式：()()()()()()4123444,4,4,4pppppp==ururrΡ利用MATLAB计算得出：()()()()()()()()123444,4,4,40.69750.12070.05730.12450.22500.57010.03760.16740.19,0.14,0.56,0.110.24510.18130.42670.14690.28950.07860.07810.55380.3331,0.2129,0.2637,0.1903ppppp=⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦=ur则该城市2006年公交的平均日客运量为：()()144680.3331155.8908156UNp==×=∑≅（万人次）参考文献：[1]高文森，潘伟．大学数学——随机数学[M]．北京：高等教育出版社，2004：271－302．[2]景毅，王世称，苑清扬．马尔可夫过程在地质学中的应用[M]．北京：地质出版社，1986：1－94．[3]刘次华．随机过程[M]．第二版．武汉：华中科技大学出版社，2001：1－34，56－119．[4]姜华平、陈海泳．城市公交客运量的预测模型研究[J]．统计与决策，2005，12：30－32．DISCUSSIONOFPRINCIPLEANDEXAMPLESOFAPPLICATIONONMARKOVCHAINXueYanZHUCollegeofE