1、第五章第五章 马尔可夫过程马尔可夫过程马尔可夫过程是前苏联数学家马尔可夫过程是前苏联数学家A.A.Markov首先提出首先提出和研究的一类随机过程和研究的一类随机过程.经过世界各国几代数学家的相继努力经过世界各国几代数学家的相继努力,至今已成为内至今已成为内容十分丰富容十分丰富,理论上相当完整理论上相当完整,应用也十分广泛的一门应用也十分广泛的一门数学分支数学分支.它的应用领域涉及计算机、通讯、自动控制、随机它的应用领域涉及计算机、通讯、自动控制、随机服务、可靠性、生物、经济、管理、气象、物理、服务、可靠性、生物、经济、管理、气象、物理、化学等化学等.马尔可夫马尔可夫 (1856年6月14日1
2、922年7月20日）马尔可夫对数学的最大贡献是在概率论领域作出的十九世纪后二十年，他主要是沿着切比雪夫开创的方向，致力于独立随机变量和古典极值理论的研究，从而改进和完善了大数定律和中心极限定理 二十世纪初，他的兴趣转移到相依随机变量序列的研究上来，从而创立了以他命名的著名概率模型马尔可夫链王梓坤王梓坤院士(1929年)江西吉安人,1952年大学毕业后，被分派到天津南开大学数学系任教,曾任北京师范大学校长,是一位对我国科学和教育事业作出卓越贡献的数学家和教育家，也是我国概率论研究的先驱和学术带头人之一。 1954年，他以优异的成绩考取了赴苏研究生。踏进世界著名学府莫斯科大学，在这个学府世界概率论
3、的奠基人柯尔莫哥洛柯尔莫哥洛夫夫(Kolmogorov)院士正领导看一个强有力的概率研究集团。柯尔莫高洛夫慧眼识英才，非常信赖这位由中国选派的年轻人的能力，把他选作自己的研究生，去攻概率论的中心问题随机过程理论。 当时中国近代数学才刚刚起步，大学也没有概率课程。此时苏联的概率论水平已届于世界最前列。王梓坤也根本不知道什么是概率，可他的研究方向又恰恰被定为概率论， 著有概率论基础及其应用、随机过程论、生灭过程与马尔科夫链等9部数学著作 马尔可夫过程的定义马尔可夫过程的定义马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类转移概率的稳定性能
4、转移概率的稳定性能本章主要内容本章主要内容一一马尔可夫过程的定义马尔可夫过程的定义1马尔可夫性马尔可夫性通俗地说，通俗地说，就是在知道过程现在的条件下，其就是在知道过程现在的条件下，其将来的条件分布不依赖于过去，将来的条件分布不依赖于过去，则称则称),(TttX具有具有马尔可夫（马尔可夫（Markov)性。性。定义定义设设),(TttX是一个随机过程，如果是一个随机过程，如果),(TttX在在t0时刻所处的状态为已知，它在时刻所处的状态为已知，它在时刻时刻0tt 所处状态的条件分布与其在所处状态的条件分布与其在 t0 之前之前 所处的状态无关。所处的状态无关。0tt现在0tt将来0tt过去2.
5、 马尔可夫过程马尔可夫过程定义定义 设设),(TttX的状态空间为S,122,nntttT 如果对( ),1,2,1iiiX txxSin在条件下)(ntX的条件分布函数恰好等于11()nnX tx在条件下的条件分布函数,即11221111( ),( ),()( )(,)()nnnnnnnnnP X txP X txX txX txX txXRtxx( ),X t tT马尔则称为可夫过程.3.马尔可夫链马尔可夫链定义定义 参数集和状态空间都是离散的马尔可夫过程参数集和状态空间都是离散的马尔可夫过程称为马尔可夫链。称为马尔可夫链。注注 只讨论马尔可夫链的状态空间为有限或可列无限只讨论马尔可夫链的
6、状态空间为有限或可列无限.则马尔可夫性可表示为则马尔可夫性可表示为12122, , ,nnntttT i iiS 对11111122()( ),( )( )(),),nnnnnnnnnP X tiP X tixX tiX tiRX tiX ti有特别特别对取对取T=0,1,2,的马尔可夫链，记为的马尔可夫链，记为0),(nnX或0,nXn此时的马尔可夫性为此时的马尔可夫性为011, , ,nni iiS 对有0111(1)(1)(0),(1( )( ),nnnnP X niPXiXiX niXX niin10110111,),()nnnnnnnnXP XiP XXiXiiXii或今后今后,记记
7、1,2,3,0,1,2,ST,0nXn 马尔可夫链记为马氏链也称,或系统二二 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布1. 转移概率转移概率定义定义 设0,nXn是马尔可夫链,称条件概率,0nXnni(它表示系统在 时处于状态的条件下经过k步转移,于n+k时到达状态j的条件概率).( )( )(,0,)1kijn knpnP Xj Xi jS nik,0nXn 为在在n时的时的k步转移概率步转移概率.( )( )kijipnj称以为第 行第 列元素的矩阵)()()()(npnkijkP,0nXn 为系统在n时的k步转移概率矩阵步转移概率矩阵.( )( )ijnp nP记为特
8、别特别 当当k=1时，时，(1)( )ijnpn 为系统在 时的一步转移概率,(1)(1)( )( )ijnpnP为系统的一步转移概率矩阵( )ijpn记为定义定义 称可数维的矩阵称可数维的矩阵)(ijpP 为随机矩阵，如果为随机矩阵，如果0,(, )1,()ijijjpi jpi显然，显然，0,nXn在在n时的时的k步转移概率矩阵步转移概率矩阵)()(nkP是一随机是一随机矩阵矩阵.特别特别k时，约定时，约定(0)1,00ijijijpi jS nij(0)( )I.Pn 此时为单位矩阵. Chapman-kolmogorov方程方程定理定理 (C-K方程方程)()( )()( )( )()
9、,0, ,k mkmijilljlpnpn pnkn m ki jS或矩阵形式或矩阵形式)()()()()()(knnnmkmkPPP（解决了（解决了k步转移概率与一步转移概率间的关系）步转移概率与一步转移概率间的关系）证明证明()( )k mijn k mnpnP Xj Xi ,()n kmnln kPXjliXX ,)()n k mnn klPXj XliX,)()n k mnnlkPXj XiXl )(,)(nn k mnnn klkPXiP Xj XXlXil )()nn k mn kn klPXiPllXXj X ( )()( )()kmilljlpn pnk系统在系统在n 时从状态
10、时从状态i的出发的出发,经过经过k+m步转移步转移,于于n+k+m时到达状态时到达状态j,可以先在可以先在n时从状态时从状态i出发，经过出发，经过k步转移步转移于于n+k时到达某种中间状态时到达某种中间状态l,再在再在n+k时从中间状态时从中间状态l出出发经过发经过m步转移于步转移于n+k+m时到达最终状态时到达最终状态j,而中间状而中间状态态l要取遍整个状态空间要取遍整个状态空间S.C-K方程的直观意义：方程的直观意义：定理定理 马尔可夫链的马尔可夫链的k 步转移概率由步转移概率由 其一步转移概率其一步转移概率 所完全确定所完全确定.若取若取m=1,则由则由C-K方程的矩阵形式方程的矩阵形式
11、:)()()()()()(knnnmkmkPPP得得(1)( )(1)( )( )()kknnnkPPP(1)( )(1)()knnknkPPP( )(1)(1)()nnnknkPPPP分量形式分量形式11 212(1)( )( )(1)()kkkijijj jj jjjjpnpnpnpnk ( ,0)n k ( ,0, ,)n ki jS1）初始分布）初始分布(0)0(),iqP XiiS称为马尔可夫链为马尔可夫链的的初始分布初始分布3.马尔可夫链马尔可夫链 的分布的分布0,nXn称称 第第i个分量个分量为为)0(iq的的(行行)向量向量)0(q为马尔可夫链为马尔可夫链的的初始分布向量初始分
12、布向量. 即即)()0()0(iqq2）有限维分布）有限维分布定理定理 马尔可夫链马尔可夫链0,nXn的的有限维分布有限维分布由其由其初始初始分布分布和和一步转移概率一步转移概率所完全确定所完全确定.证明证明12121, 0, , , ,nnnttt i ii iS 对1212,ntttnP Xi XiXi12120,(),ntnittPXi XiXiiX12201,(),nttitnPXi XXiiXi12012(,)ntttniPXi XiXiXi121110200,()()()tttiXiXiPP XXiiP XiXi11110(,)nntnttnXiP XiXiXi12100121()
13、()()tttiXiXiPP XiP Xi Xi11()nntntnP Xi Xi112111 21(0)11(0)( )().nninntttttiii iiiniqpptpt又因为马尔可夫链的又因为马尔可夫链的k步转移概率由一步转移概率所步转移概率由一步转移概率所完全确定完全确定.所以马尔可夫链的有限维分布由其所以马尔可夫链的有限维分布由其初始分布初始分布和和一步转移概率一步转移概率所完全确定所完全确定.3）绝对分布）绝对分布( )(),0,njnqP XjnjS称为马尔可夫链为马尔可夫链 的的绝对分布绝对分布0,nXn称称 第第j个分量为个分量为)(njq的的(行行)向量向量)0(q为马
14、尔可夫链为马尔可夫链0,nXn的的绝对分布向量绝对分布向量. 即即)()()(njnqq绝对分布、初始分布和绝对分布、初始分布和n步转移概率有如下关系：步转移概率有如下关系：( )(0)( )(0)0, ,nnjiijiqqpni jS或矩阵形式或矩阵形式)0()()0()(nnPqq( )()njnqP Xj(0)( )(0)0, ,niijiqpni jS0(),)niPXiXj0(,)niPXi Xj0(,)niP Xi Xj00()()niP XiP Xj Xi4.齐次马尔可夫链齐次马尔可夫链定义定义,0nXn 设是一马尔可夫链是一马尔可夫链,如果其一步转移如果其一步转移概率概率)(n
15、pij恒与起始时刻恒与起始时刻n无关，记为无关，记为ijp,0nXn 则称为为齐次齐次(时间其次或时齐时间其次或时齐)马尔可夫链马尔可夫链.否则，称为非齐次马尔可夫链否则，称为非齐次马尔可夫链.为方便，一般假定时间起点为零即为方便，一般假定时间起点为零即显然对齐次马尔可夫链，显然对齐次马尔可夫链，k步转移概率也与起始步转移概率也与起始时刻时刻n无关记为无关记为( )kijp( )0(),0kijkpP Xj Xii jS k相应的相应的k步与一步转移概率矩阵分别记为步与一步转移概率矩阵分别记为(k)PP与定理定理 ( )( )(0)(1),0;(2),0;(3) ,0kkkknkkXnPPqq
16、P的有限维分布由其初始分布和一的有限维分布由其初始分布和一步转移概率所完全确定步转移概率所完全确定例例(天气预报问题天气预报问题) 如果明天是否有雨仅与今天的如果明天是否有雨仅与今天的天气天气(是否有雨是否有雨)有关，而与过去的天气无关有关，而与过去的天气无关. 并设并设今天下雨、明天有雨的概率为今天下雨、明天有雨的概率为a，今天无雨而明天有雨的概率为今天无雨而明天有雨的概率为b，又假设，又假设有雨称为有雨称为0状态天气，无雨称为状态天气，无雨称为1状态天气状态天气. Xn表示时刻表示时刻n时的天气状态，则时的天气状态，则0,nXn是以1 , 0S为状态空间的齐次马尔可夫链.其一步转移概率矩阵
17、为其一步转移概率矩阵为bbaa11P. .马尔可夫链举例马尔可夫链举例 例例2(有限制随机游动问题有限制随机游动问题) 设质点只能在设质点只能在0，1，2，a中的各点上作随机中的各点上作随机 游动，移动规则如下：游动，移动规则如下：11,2,1ia（）移动前处; 1, 0,rqprqp0000,0,1p rprii+1i-1pqr010p0r20i （ ）移动前处3ia（ ）移动前处a-1aqaar,0,1aaaaq rqr设设Xn表示质点在表示质点在n时刻所处的位置，则时刻所处的位置，则其一步转移概率矩阵为,00,1, nXnSa是以为状态空间的齐次马尔可夫链.aarqprqprqprqpr
18、000000000000000000000000P例例3 设一个坛子中装有设一个坛子中装有m个球，它们或是红色的，或个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个是黑色的，从坛子中随机的摸出一球，并换入一个相反颜色的球相反颜色的球.其其一步转移概率矩阵为一步转移概率矩阵为01000001010000000202000001010000010mmmmmmmmmP,0nXn 是以, 1 , 0mS为状态空间的齐次马尔可夫链为状态空间的齐次马尔可夫链.设经过设经过n次摸换次摸换,坛中黑球数为坛中黑球数为Xn,则则例例 设0,nXn是具有三个状态0，1，2的齐次马尔可夫链，其一步
19、转移概率矩阵为3104411142431044P初始分布初始分布, 2 , 1 , 0,31)0(iqi试求：022(1) (0,1);(2) (1).P XXP X解解020201(0,1)(0(10)P XXP XP XX（）)(2)0113p(2)01p其中为一个两步转移概率，在两步转移概率矩阵中是第一行第二列的元素.22PP（ ）5181 65131 621 63911 611 6645(2)01516p02(0,1)P XX1553 1648(0)(2)21(2)(1)iiiP Xqp(2)(2)(2)0111211()3ppp1 519()3 162161124作业作业 设0,nXn是状态空间为a,b,c的齐次马氏链.其一步转移概率矩阵为1112442103332055P712345602(1) ,(2) ,nnP Xb Xc Xa Xc Xa Xc Xb XcP Xc Xb求
