第五章马尔科夫过程复习

第五章马尔可夫过程一马尔可夫过程的定义1．马尔可夫性通俗地说，就是在知道过程现在的条件下，其将来的条件分布不依赖于过去，则称}),({TttX具有马尔可夫（Markov)性。定义设}),({TttX是一个随机过程，如果}),({TttX在t0时刻所处的状态为已知，它在时刻0tt所处状态的条件分布与其在t0之前所处的状态无关。0tt现在0tt将来0tt过去2.马尔可夫过程定义设}),({TttX的状态空间为S,122,,nntttT如果对(),,1,2,,1iiiXtxxSin在条件下)(ntX的条件分布函数恰好等于11()nnXtx在条件下的条件分布函数,即11221111(),(),,()(()((,))())nnnnnnnnnPXtxPXtxXtxXtxXtxXRtxx{(),}XttT马尔则称为可夫过程.3.马尔可夫链定义参数集和状态空间都是离散的马尔可夫过程称为马尔可夫链。注只讨论马尔可夫链的状态空间为有限或可列无限.则马尔可夫性可表示为12122,,,,,,nnntttTiiiS对11111122()(),((())(()()),),,nnnnnnnnnPXtiPXtixXtiXtiRXtiXti有特别对取T={0,1,2,···}的马尔可夫链，记为}0),({nnX或}0,{nXn此时的马尔可夫性为011,,,,,nniiiS对有0111(1))(1)(0),(1(()(())),,nnnnPXniPXiXiXniXXniin10110111,),,(()nnnnnnnnXPXiPXXiXiiXii或今后,记{1,2,3,},{0,1,2,}ST{,0}nXn马尔可夫链记为马氏链也称,或系统二马尔可夫链的转移概率与概率分布1.转移概率定义设}0,{nXn是马尔可夫链,称条件概率{,0}nXnni(它表示系统在时处于状态的条件下经过k步转移,于n+k时到达状态j的条件概率).()()(,,,0,)1kijnknpnPXjXijSnik@{,0}nXn为在n时的k步转移概率.()()kijipnj称以为第行底列元素的矩阵))(()()()(npnkijkP{,0}nXn为系统在n时的k步转移概率矩阵.()()ijnpnP记为特别当k=1时，(1)()ijnpn为系统在时的一步转移概率,(1)(1)()(())ijnpnP为系统的一步转移概率矩阵()ijpn记为定义称可数维的矩阵)(ijpP为随机矩阵，如果0,(,)1,()ijijjpijpi显然，}0,{nXn在n时的k步转移概率矩阵)()(nkP是一随机矩阵.特别k＝０时，约定(0)1,,,00ijijijpijSnij(0)()I.Pn此时为单位矩阵２.Chapman-kolmogorov方程定理(C-K方程)()()()()()(),,,0,,kmkmijilljlpnpnpnknmkijS或矩阵形式)()()()()()(knnnmkmkPPP（解决了k步转移概率与一步转移概率间的关系）C-K方程的直观意义：系统在n时从状态i的出发,经过k+m步转移,于n+k+m时到达状态j,可以先在n时从状态i出发，经过k步转移于n+k时到达某种中间状态l,再在n+k时从中间状态l出发经过m步转移于n+k+m时到达最终状态j,而中间状态l要取遍整个状态空间S.定理马尔可夫链的k步转移概率由其一步转移概率所完全确定.1）初始分布(0)0(),iqPXiiS称@为马尔可夫链的初始分布3.马尔可夫链的分布}0,{nXn称第i个分量为)0(iq的(行)向量)0(q为马尔可夫链的初始分布向量.即)()0()0(iqq2）有限维分布定理马尔可夫链}0,{nXn的有限维分布由其初始分布和一步转移概率所完全确定.3.齐次马尔可夫链定义{,0}nXn设是一马尔可夫链,如果其一步转移概率)(npij恒与起始时刻n无关，记为ijp{,0}nXn则称为齐次(时间其次或时齐)马尔可夫链.否则，称为非齐次马尔可夫链.为方便，一般假定时间起点为零．即显然对齐次马尔可夫链，k步转移概率也与起始时刻n无关．记为()kijp()0(),,0kijkpPXjXiijSk相应的k步与一步转移概率矩阵分别记为(k)PP与定理()()(0)(1),0;(2),0;(3){,0}kkkknkkXnPPqqP的有限维分布由其初始分布和一步转移概率所完全确定例不可越壁的随机游动设一质点在线段[1，5]上随机游动，状态空间I={1，2，3，4，5}，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在2，3，4处，则均以概率1/3向左或向右移动一单位，或停留在原处；（2）若移动前在1处，则以概率1移到2处；（3）若移动前在5处，则以概率1移到4处。用nX表示在时刻n质点的位置，则{nX，0n}是一个有限齐次马氏链，试写出一步转移矩阵.分析555453525145444342413534333231252423222115141312111pppppppppppppppppppppppppP01000313131000313131000313131000101P故12345例甲、乙两人进行比赛，设每局比赛中甲胜的概率是p，乙胜的概率是q，和局的概率是r,（p+q+r=1）。设每局比赛后，胜者记“+1”分，负者记“-1”分，和局不记分。当两人中有一人获得2分结束比赛。以表示比赛至第n局时甲获得的分数。nX（1）写出状态空间；（2）求2P；（3）问在甲获得1分的情况下，再赛二局可以结束比赛的概率是多少？解（1）记甲获得“负2分”为状态1，获得“负1分”为状态2，获得“0分”为状态3，获得“正1分”为状态4，获得“正2分”为状态5，则状态空间为}54321{，，，，I一步转移概率矩阵10000000000000011prqprqprqP（2）二步转移概率矩阵212PP100002022202000012222222rpppqrqrqpprpqrrqqpprpqrrpq（3）在2P中)2(45p是在甲得1分的情况下经二步转移至2分从而结束比赛的概率；)2(41p是在甲得1分的情况下经二步转移至—2分（即乙得2分）从而结束比赛的概率。所以题中所求概率为)2(45p)2(41p)1(0)(rprpp例设}0,{nXn是具有三个状态0，1，2的齐次马尔可夫链，其一步转移概率矩阵为3104411142431044P初始分布,2,1,0,31)0(iqi试求：022(1)(0,1);(2)(1).PXXPX解020201(0,1)(0(10)PXXPXPXX（）)(2)0113p(2)01p其中为一个两步转移概率，在两步转移概率矩阵中是第一行第二列的元素.22PP（）Q518165131621639116116645(2)01516p02(0,1)PXX15531648(0)(2)21(2)(1)iiiPXqp(2)(2)(2)0111211()3ppp1519()3162161124,000,0XttXXtt例：设是独立增量过程，且证明：是一个马尔可夫过程。121,nnTntttt证：对中任意个数值1111()|,,nnnnPXtxXtxXtx1121211112120,(),(),nnnnnnnnXtXxXtXtxxPXtXtxxXtXtxxL111111()()|0nnnnnnnnnnPXtXtxxPXtXtxxXtXx,0Xtt由定义知，是一个马尔可夫过程。证毕！11()|nnnnPXtxXtx•由上例知，泊松过程是时间连续状态离散的马氏过程，•维纳过程是时间状态都连续的马氏过程。{(),0}1.((1.54)0.8(0.55)0.1,(0.98)1.3,(1.50)1)WttP2例：设是一个维纳过程，求。((1.54)(1.50)0.2(1.50)1)P((1.54)0.8(1.50)1)PWW((1.54)0.8(0.55)0.1,(0.98)1.3,(1.50)1)P解：((1.54)(1.50)0.2)PWW0.20()(1)0.1587.0.04Markov链的状态分类与判别定义称状态iE为吸收态，若pii=1.定义对i,jE，若存在nN，使，则称自状态i出发可达状态j，记为ij.如果ij且ji，则称i,j相通，记为ij.定理相通是一种等价关系,即满足(1)自返性ii;(2)对称性ij,则ji;(3)传递性ij,jk则ik.定义若一Markov链的任意两个状态都相通，则称为不可约链。定义令Tij=min{n:X0=i,Xn=j,n1}，称为系统在0时刻从状态i出发，首次到达状态j的时间，简称为首达时.且规定,若右边为空集，则Tij=∞.定义令}|11,,{}|{00iXnkjXjXPiXnTPfknijnij1nnijijff表示0时刻从状态i出发，经n步转移后首次到达状态j的概率，称为n步首达概率；由i出发，经过有限步首次到达状态j的概率为定义若fii=1，则称状态i为常返态;若fii1，则称状态i为瞬时态（非常返态）。定义如果fij=1,记则表示从i出发到达j的平均转移时间.特别，称为从状态i出发，返回状态i的平均返回时间.若∞，称i为正常返态；若=∞，称i为零常返状态.()01()nijijijnETXinfijiiiiii引理对任意i,jE及n1，有()()()1nnmnmijijjjmpfp上式也称为M.C从状态i首次到达状态j的分解式，简称首达分解式。推论.ji0fij定理.0f0fjijiij且i为瞬时态()0.niinp定理()0.niinp推论有限状态马氏链的状态空间至少有一个常返态。定理常返态全体构成一个闭集。定义设CE，若对任意的iC，和任意的jC,及任意的nT，pij(n)=0，则称C为E的闭集。i为常返态定理设马氏链的状态空间为E，(1)对任意i,jE，若ij，则它们同为常返态或瞬时态；而且当i,j是常返态时，i,j同为正常返态或同为零常返态；(2)不可约的有限齐次马氏链的状态都是正常返的。定义如果集合{n:n≥1,0}≠φ，称该数集的最大公约数d(i)为状态i的周期.若d(i)1，称i为周期的，若d(i)=1，称i为非周期的.niip定义若状态i为正常返态的且非周期的，则称i为遍历状态.定义称Markov链是遍历的,如果所有状态都是遍历态.小结相通、闭集、不可约状态常返瞬时正常返、零常返周期、非周期遍历定理设马氏链的状态空间为E，i,jE，（1）若iE是一个周期态，且ij，则j也是周期态，且di=dj；（2）若此链不可约，且对iE有pii0，则此链是非周期链。常返非常返状态正常返零常返周期非周期遍历态1iif1iifiiii1id1id状态空间分解定理01,,ijkkf