马尔科夫模型简介

第一节马尔可夫过程及其概率分布一、马尔可夫过程的概念二、马尔可夫过程的概率分布三、应用举例四、小结一、马尔可夫过程的概念1.马尔可夫性(无后效性)所处的状态为已知的在时刻系统过程或0)(t所处状态的条件分布与过程在时刻条件下0,tt特性称为之前所处的状态无关的与过程在时刻0t马尔可夫性或无后效性.即:过程“将来”的情况与“过去”的情况是无关的.2.马尔可夫过程的定义具有马尔可夫性的随机过程称为马尔可夫过程.用分布函数表述马尔可夫过程,}),({:的状态空间随机过程设TttXI,个数值的任意如果对时间nt,,3,21Ttntttin恰有})(,,)(,)(|)({112211nnnnxtXxtXxtXxtXP},)(|)({11RxxtXxtXPnnnnn下的条件分布函数在条件iinxtXtX)()(下的条件分布函数在条件11)()(nnnxtXtX或写成),,,;,,,|,(121121|11nnnnttttttxxxtxFnn),,|,(11|1nnnntttxtxFnn.}),({性具马尔可夫性或无后效这时称过程TttX并称此过程为马尔可夫过程.3.马尔可夫链的定义时间和状态都是离散的马尔可夫过程称为马尔可夫链,}.,2,1,0),({nnXXn简记为研究时间和状态都是离散的随机序列.},,,(21RaaaIi状态空间为二、马尔可夫过程的概率分布},,2,1,0),({nnXXn1.用分布律描述马尔可夫性;0,21mtttrnr和对任意的正整数,,,iiTmnmt有1122{|,,,,}rrmnjtititimiPXaXaXaXaXa,}|{imjnmaXaXP.Iai其中称条件概率}|{),(imjnmijaXaXPnmmPnmami在时刻条件下处于状态为马氏链在时刻,.的转移概率转移到状态ja说明:转移概率具有特点.,2,1,1),(1jijinmmP2.转移概率由转移概率组成的矩阵)),((),(nmmPnmmPij称为马氏链的转移概率矩阵.此矩阵的每一行元素之和等于1.它是随机矩阵.3.平稳性njinmmPij及时间间距只与当转移概率,),(有关时,称转移概率具有平稳性.同时也称此链是齐次的或时齐的.),(),(,nPnmmPijij记此时.}|{)(imjnmijaXaXPnP称为马氏链的n步转移概率.))(()(步转移概率矩阵为nnPnPij一步转移概率}.|()1(1imjmijijaXaXPPp特别的,当k=1时,一步转移概率矩阵的状态1mX的状态mXiaaa21jaaa21ijiijjppppppppp211222111211)1(P记为P)1(P三、应用举例,0)0(,}0),({XttX且是独立增量过程设.}0),({是一个马尔可夫过程证明　ttX证明由独立增量过程的定义知,,2,,2,1,01时当njtttnnj.)()()0()(1相互独立与增量nnjtXtXXtX,)(0)0(11nnxtXX与根据条件即有.)()(1相互独立与nnjxtXtX例1.2,,2,1),()(相互独立与此时njtXtXjn是一个即具有无后效性这表明}0),({,)(ttXtX马尔可夫过程.说明:泊松过程是时间连续状态离散的马氏过程;维纳过程是时间状态都连续的马氏过程.设每一级的传真率为p,误码率为q=1-p.设一个单位时间传输一级,只传输数字0和1的串联系统(传输系统)0X11X2X1nXnnX2如图:是第一级的输入0X)1(nnXn级的输出是第分析:,},2,1,0,{是一随机过程nXn,}1,0{I状态空间例210,,为已知时且当IiiXn,1有关所处的状态分布只与iXXnn而与时刻n以前所处的状态无关.所以它是一个马氏链,且是齐次的.一步转移概率1,0,,,}|{1ji,ijqijpiXjXPpnnij一步转移概率矩阵pqqp10P10例3一维随机游动.21,}5,4,3,2,1{等时刻发生游动秒秒、并且仅仅在上作随机游动在如图所示直线的点集　　一随机游动的质点I12345游动的概率规则1/3的概率向左或向右移动一格,或以1/3的概率留在原处;如果Q现在位于点i(1i5),则下一时刻各以12345以概率1移动到2(或4)这一点上.如果Q现在位于1(或5)这点上,则下一时刻就1和5这两点称为反射壁.上面这种游动称为带有两个反射壁的随机游动.12345模拟方法:产生均匀分布的随机数序列13232211122…,其中1表示左移;2表示不动;3表示右移.理论分析:.的位置时表示时刻以QnXn.},2,1,0,{是一随机过程则nXn状态空间就是I.,,为已知时且当IiiXn,1有关所处的状态分布只与iXXnn而与时刻n以前所处的状态无关.所以它是一个马氏链,且是齐次的.一步转移概率}|{1iXjXPpnnij.21,04,52,1,151,1,,1,31jjijiiiiij或010003/13/13/10003/13/13/10003/13/13/10001054321P54321说明:相应链的转移概率矩阵只须把P中第1行改为改变游动的概率规则,就可得到不同方式的随机游动和相应的马氏链.如果把点1改为吸收壁,).0,0,0,0,1(一步转移概率矩阵?55,35,15.}1,{.)10(,1,0.,21,31,于多少日为雨天的概率各等月日为晴天月问天日为晴月又已知的一步转移概率矩阵试写出马氏链或天状态表示第表示雨天状态以表示晴天状态以为逆事件任一天晴或雨是互晴天转雨天的概率为雨天转晴天的概率为设任意相继的两天中nXnXnn解为逆事件且雨天转由于任一天晴或雨是互转移概率矩阵分别为故一步转移概率和一步,21,31晴天转雨天的概率为晴天的概率为例41,0,210,0,211,1,320,1,311jijijijiiXjXPnn323121211010P又由于181118712712510102P,6003.03997.05995.04005.010104P又由于日为雨天的概率为月日为晴天月故55,15.5995.0)4(01P日为晴天的概率为月日为晴天月故35,15,4167.0125)2(00P某计算机房的一台计算机经常出故障,研究者每隔15分钟观察一次计算机运行状态,收集了24小时的数据(共作97次观察).用1表示正常状态,用0表示不正常状态,所得的数据序列如下:1110010011111110011110111111001111111110001101101分析,)97,,2,1(个时段的计算机状态为第设nnXn状态空间:I={0,1}.例511101101101011110111011110111111001101111110011196次状态转移的情况:;8,00次;18,01次因此,一步转移概率可用频率近似地表示为:,2681888}0|0{100nnXXPp,261818818}0|1{101nnXXPp,7018521818}1|0{110nnXXPp.7052521852}1|1{111nnXXPp;18,10次.52,11次以下研究齐次马氏链的有限维分布.:1的一维分布马氏链在任意时刻Tn.,2,1,},{)(jIaaXPnpjjnj特点:1.1)(jjnp,}{}|{}{100iiijnjnaXPaXaXPaXP.,2,1),()0()(1iijijjnppnp即用行向量表示为)()0()(nPpnp一维分布由初始分布和转移概率矩阵决定由以上讨论知,转移概率决定了马氏链的运动的统计规律.因此,确定马氏链的任意n步转移概率成为马氏链理论中的重要问题之一.四、小结齐次马氏链、平稳性的概念.一步转移概率矩阵的计算.一步转移概率}.|()1(1imjmijijaXaXPPp一步转移概率矩阵)).(()1(nPPij第二节多步转移概率的确定一、C-K方程三、应用举例四、小结二、多步转移概率的确定一、C-K方程},)({1TnnX设是一齐次马氏链,则对任意的有,,1Tvu.,2,1,),()()(1kkjikijjivpuPvuP切普曼-柯尔莫哥洛夫方程(简称C-K方程)说明C-K方程基于下列事实:.)(,,”转移到状态经时段出发所处的状态“从时刻jjiavusXavuas这一事件可分解成:转移到中间状态先经时段出发“从uasXi,)(”等事转移到状态经时段在从jkkavaka),2,1(件的和事件.tosusvusiakaja如下图所示:证明,1TsIak和先固定由条件概率定义和乘法定理得})(|)(,)({ikjasXausXavusXP})(,)(|)({})(|)({ikjikasXausXavusXPasXausXP).()(vPuPkjik(马氏性和齐次性),,2,1,)(构成一划分”因事件组“kausXk所以})(|)({)(ijijasXavusXPvuP1)(,)({kjusXavusXP}.)(|ikasXa考虑到马氏性和齐次性,即得C-K方程.C-K方程也可写成矩阵形式:).()()(vPuPvuP二、多步转移概率的确定利用C-K方程我们容易确定n步转移概率.得递推关系:,1,1,)()()(nvuvPuPvuP令中在),1()1()1()(nPPnPPnP().nPnP从而可得马氏链的n步转移概率是一步转移概率的n次方,链的有限维分布可由初始分布和一步转移概率完全确定.结论步转移概率矩阵为一马氏链是具有三个状态的齐次设,0,nXn}.1{)2(};1,0{)1(:,2,1,0,31}{)0(2200XPXXPiiXPpi求初始分布,4143041214104143P解(1)先求出2步转移概率矩阵:例1.411691631632116516116585)2(2PP02{0,1}PXX}0|1{}0{020XXPXP)2()0(010pp,485165311(2)(2)p}1{2XP001111221(0)(2)(0)(2)(0)(2)pppppp.2411)16921165(31在传输系统中,真率与三级求系统二级传输后的传设,9.0)1(p传输后的误码率;,}1{)0()2(01XPp设初始分布.1}0{)0(00XPp系统经n级传输后输出为1,问原发字符也是1的概率是多少?例210解先求出n步转移概率矩阵.,1010pqqpP因为有相异的特征值qp21,1所以可将P表示成对角阵,0010021qp11)(HHHHPnnn则.)(2121,)(2121)(2121,)(21211010nnnnqpqpqpqp率与三级系统二级传输后的传真当,9.0)1(p传输后的误码率分别为:,820.0)1.09.0(2121)2()2(20011PP;244.0)1.09.0(2121)2()3(30110PP