马尔科夫模型简介PPT课件

1、一、马尔可夫过程的概念 1. 马尔可夫性马尔可夫性(无后效性无后效性)所所处处的的状状态态为为已已知知的的在在时时刻刻系系统统过过程程或或0)(t所所处处状状态态的的条条件件分分布布与与过过程程在在时时刻刻条条件件下下0,tt 特特性性称称为为之之前前所所处处的的状状态态无无关关的的与与过过程程在在时时刻刻0t马尔可夫性马尔可夫性或或无后效性无后效性.即: 过程“将来”的情况与“过去”的情况是无关的.第1页/共54页2. 马尔可夫过程的定义马尔可夫过程的定义具有马尔可夫性的随机过程称为具有马尔可夫性的随机过程称为马尔可夫过程马尔可夫过程.用分布函数表述马尔可夫过程,),(:的状态空间的状态空间

2、随机过程随机过程设设TttXI ,个数值个数值的任意的任意如果对时间如果对时间nt, 3,21Ttntttin 恰有)(,)(,)(|)(112211 nnnnxtXxtXxtXxtXP ,)(|)(11RxxtXxtXPnnnnn 下的条件分布函数下的条件分布函数在条件在条件iinxtXtX )()(下下的的条条件件分分布布函函数数在在条条件件11)()( nnnxtXtX第2页/共54页或写成),;,|,(121121|11 nnnnttttttxxxtxFnn),|,(11|1 nnnntttxtxFnn.),(性性具马尔可夫性或无后效具马尔可夫性或无后效这时称过程这时称过程TttX 并

3、称此过程为为马尔可夫过程马尔可夫过程.3. 马尔可夫链的定义马尔可夫链的定义 时间和状态都是离散的马尔可夫过程称为时间和状态都是离散的马尔可夫过程称为马尔马尔可夫链可夫链, ., 2 , 1 , 0),( nnXXn简记为简记为第3页/共54页研究时间和状态都是离散的随机序列.,(21RaaaIi 状态空间为状态空间为二、马尔可夫过程的概率分布, 2, 1 , 0),( nnXXn1. 用分布律描述马尔可夫性用分布律描述马尔可夫性;0,21mtttrnr 和和对任意的正整数对任意的正整数,iiTmnmt 有1122|,rrm njtititimiP XaXa XaXaXa , |imjnmaX

4、aXP . Iai 其中其中第4页/共54页称条件概率称条件概率 |),(imjnmijaXaXPnmmP nmami 在时刻在时刻条件下条件下处于状态处于状态为马氏链在时刻为马氏链在时刻,.的转移概率的转移概率转移到状态转移到状态ja说明: 转移概率具有特点 ., 2 , 1, 1),(1 jijinmmP2. 转移概率转移概率由转移概率组成的矩阵),(),(nmmPnmmPij 称为马氏链的转移概率矩阵转移概率矩阵.此矩阵的每一行元素之和等于1.它是随机矩阵.第5页/共54页3. 平稳性平稳性njinmmPij及时间间距及时间间距只与只与当转移概率当转移概率,),( 有关时有关时, 称转移

5、概率具有平稳性称转移概率具有平稳性.同时也称此链是同时也称此链是齐次的齐次的或或时齐的时齐的.),(),(,nPnmmPijij 记记此时此时 . |)(imjnmijaXaXPnP 称为马氏链的n步转移概率.)()(步转移概率矩阵步转移概率矩阵为为nnPnPij 第6页/共54页一步转移概率一步转移概率.|()1(1imjmijijaXaXPPp 特别的, 当 k=1 时,一步转移概率一步转移概率矩阵矩阵的状态的状态1 mX的状态mXiaaa21jaaa21 ijiijjppppppppp211222111211)1(P 记为P)1(P第7页/共54页三、应用举例, 0)0(,0),( Xt

6、tX且且是独立增量过程是独立增量过程设设.0),(是一个马尔可夫过程是一个马尔可夫过程证明证明 ttX证明证明由独立增量过程的定义知,2, 2 , 1,01时时当当 njtttnnj.)()()0()(1相互独立相互独立与与增量增量 nnjtXtXXtX,)(0)0(11 nnxtXX与与根据条件根据条件即有.)()(1相互独立相互独立与与 nnjxtXtX例例1第8页/共54页.2, 2 , 1),()(相互独立相互独立与与此时此时 njtXtXjn是一个是一个即即具有无后效性具有无后效性这表明这表明0),(,)( ttXtX马尔可夫过程.说明说明:泊松过程是时间连续状态离散的马氏过程;维纳

7、过程是时间状态都连续的马氏过程.第9页/共54页设每一级的传真率为 p, 误码率为 q=1-p.设一个单位时间传输一级,只传输数字0和1的串联系统 ( 传输系统)0X11X2X1 nXnnX2如图:是第一级的输入是第一级的输入0X)1( nnXn级的输出级的输出是第是第分析:, 2 , 1 , 0,是是一一随随机机过过程程 nXn,1, 0 I状态空间状态空间例例210 第10页/共54页,为已知时为已知时且当且当IiiXn ,1有关有关所处的状态分布只与所处的状态分布只与iXXnn 而与时刻 n 以前所处的状态无关.所以它是一个马氏链, 且是齐次的. 一步转移概率1 , 0,|1 ji,ij

8、qijpiXjXPpnnij一步转移概率矩阵 pqqp10 P10第11页/共54页例例3 一维随机游动.21,5 , 4 , 3 , 2 , 1等时刻发生游动等时刻发生游动秒秒秒、秒、并且仅仅在并且仅仅在上作随机游动上作随机游动在如图所示直线的点集在如图所示直线的点集一随机游动的质点一随机游动的质点 I12345游动的概率规则1/3的概率向左或向右移动一格, 或以1/3的概率留在原处; 如果Q现在位于点 i (1 i 5),则下一时刻各以第12页/共54页12345以概率1移动到2(或4)这一点上.如果Q现在位于1(或5)这点上, 则下一时刻就1和5这两点称为反射壁.上面这种游动称为带有两个

9、反射壁的随机游动.12345模拟方法:产生均匀分布的随机数序其中1表示左移;2表示不动;3表示右移.第13页/共54页理论分析:.的位置的位置时时表示时刻表示时刻以以QnXn., 2 , 1 , 0,是一随机过程是一随机过程则则 nXn状态空间就是I.,为已知时为已知时且当且当IiiXn ,1有关有关所处的状态分布只与所处的状态分布只与iXXnn 而与时刻 n 以前所处的状态无关.所以它是一个马氏链, 且是齐次的. 第14页/共54页一步转移概率|1iXjXPpnnij . 21, 04, 52, 1, 151, 1, 1,31 jjijiiiiij或或第15页/共5

10、4页 010003/13/13/10003/13/13/10003/13/13/10001054321P5 4 3 2 1说明:相应链的转移概率矩阵只须把P 中第1行改为改变游动的概率规则, 就可得到不同方式的随机游动和相应的马氏链. 如果把点 1 改为吸收壁吸收壁, ).0 , 0 , 0 , 0 , 1(一步转移概率矩阵第16页/共54页?55,35,15.1,. )10(,1,0.,21,31,于多少于多少日为雨天的概率各等日为雨天的概率各等月月日为晴天日为晴天月月问问天天日为晴日为晴月月又已知又已知的一步转移概率矩阵的一步转移概率矩阵试写出马氏链试写出马氏链或或天状态天状态表示第表示第

11、表示雨天状态表示雨天状态以以表示晴天状态表示晴天状态以以为逆事件为逆事件任一天晴或雨是互任一天晴或雨是互晴天转雨天的概率为晴天转雨天的概率为雨天转晴天的概率为雨天转晴天的概率为设任意相继的两天中设任意相继的两天中 nXnXnn解解为逆事件且雨天转为逆事件且雨天转由于任一天晴或雨是互由于任一天晴或雨是互转转移移概概率率矩矩阵阵分分别别为为故故一一步步转转移移概概率率和和一一步步,21,31晴晴天天转转雨雨天天的的概概率率为为晴晴天天的的概概率率为为例例4第17页/共54页 1, 0,210, 0,211, 1,320, 1,311jijijijiiXjXPnn 323121211010P又由于又

12、由于 181118712712510102P第18页/共54页,6003. 03997. 05995. 04005. 010104 P又由于又由于日为雨天的概率为日为雨天的概率为月月日为晴天日为晴天月月故故55,15.5995. 0)4(01 P日为晴天的概率为日为晴天的概率为月月日为晴天日为晴天月月故故35,15,4167. 0125)2(00 P第19页/共54页 某计算机房的一台计算机经常出故障,研究者每隔15分钟观察一次计算机运行状态,收集了24小时的数据 (共作97次观察) . 用1表示正常状态, 用0表示不正常状态, 所得的数据序列如下:1110010011111110011110

13、111111001111111110001101101分析分析,)97, 2, 1(个时段的计算机状态个时段的计算机状态为第为第设设 nnXn状态空间: I=0, 1. 例例5111011011010111101110111101111110011011111100111第20页/共54页96 次状态转移的情况: ;8, 00次次;18, 01次次因此, 一步转移概率可用频率近似地表示为:,26818880|0100 nnXXPp,2618188180|1101 nnXXPp,70185218181|0110 nnXXPp.70525218521|1111 nnXXPp;18, 10 次次.5

14、2, 11次次第21页/共54页以下研究齐次马氏链的有限维分布.:1的的一一维维分分布布马马氏氏链链在在任任意意时时刻刻Tn ., 2 , 1,)( jIaaXPnpjjnj特点: 1. 1)(jjnp, |100 iiijnjnaXPaXaXPaXP ., 2 , 1),()0()(1 iijijjnppnp即即用行向量表示为)()0()(nPpnp 一维分布由初始分布和转移概率矩阵决定第22页/共54页 由以上讨论知,转移概率决定了马氏链的运转移概率决定了马氏链的运动的统计规律动的统计规律. 因此, 确定马氏链的任意n步转移概率成为马氏链理论中的重要问题之一.第23页/共54页四、小结齐次

15、马氏链、平稳性的概念.一步转移概率矩阵的计算.一步转移概率.|()1(1imjmijijaXaXPPp 一步转移概率矩阵).()1(nPPij 第24页/共54页第二节 多步转移概率的确定 一、一、C-K 方程方程三、应用举例三、应用举例 四、小结四、小结二、二、多步转移概率的确定多步转移概率的确定第25页/共54页一、C-K 方程, )(1TnnX 设设是一齐次马氏链是一齐次马氏链, 则对任意的则对任意的有有,1Tvu ., 2, 1,),()()(1 kkjikijjivpuPvuP切普曼切普曼- -柯尔莫哥洛夫方程柯尔莫哥洛夫方程( (简称简称C -K方程方程) )说明说明C-K 方程基

16、于下列事实:.)(,”转移到状态转移到状态经时段经时段出发出发所处的状态所处的状态“从时刻“从时刻jjiavusXavuas 第26页/共54页这一事件可分解成:转移到中间状态转移到中间状态先经时段先经时段出发出发“从“从uasXi,)( ”等事”等事转移到状态转移到状态经时段经时段在从在从jkkavaka),2, 1( 件的和事件.tosus vus iakaja如下图所示:第27页/共54页证明证明,1TsIak 和和先固定先固定由条件概率定义和乘法定理得)(|)(,)(ikjasXausXavusXP )(,)(|)()(|)(ikjikasXausXavusXPasXausXP ).(

17、)(vPuPkjik (马氏性和齐次性), 2 , 1,)(构成一划分构成一划分”因事件组“因事件组“ kausXk第28页/共54页所以)(|)()(ijijasXavusXPvuP 1)(,)(kjusXavusXP.)(|ikasXa 考虑到马氏性和齐次性, 即得 C-K 方程.C-K 方程也可写成矩阵形式: ).()()(vPuPvuP 第29页/共54页二、多步转移概率的确定利用 C-K 方程我们容易确定 n 步转移概率.得递推关系: , 1, 1 ,)()()( nvuvPuPvuP令令中中在在),1()1()1()( nPPnPPnP( ).nP nP从而可得 马氏链的n步转移概

18、率是一步转移概率的 n 次方,链的有限维分布可由初始分布和一步转移概率完全确定.结论结论第30页/共54页 步步转转移移概概率率矩矩阵阵为为一一马马氏氏链链是是具具有有三三个个状状态态的的齐齐次次设设,0, nXn.1)2(;1,0)1(:,2,1,0,31)0(2200 XPXXPiiXPpi求求初初始始分分布布,4143041214104143 P解解(1)先求出2步转移概率矩阵:例例1.411691631632116516116585)2(2 PP020,1P XX0|10020 XXPXP)2()0(010pp ,48516531 1(2) (2)p12 XP001111221(0)(

19、2)(0)(2)(0)(2)pppppp.2411)16921165(31 第31页/共54页在 传输系统中,真率与三级真率与三级求系统二级传输后的传求系统二级传输后的传设设, 9 . 0)1( p传输后的误码率;,1)0()2(01 XPp设初始分布设初始分布.10)0(00 XPp系统经 n 级传输后输出为 1, 问原发字符也是 1 的概率是多少?例例210 第32页/共54页解解先求出 n 步转移概率矩阵.,101 0 pqqpP因为因为有相异的特征值qp 21, 1 所以可将 P 表示成对角阵,0010021 qp 11)( HHHHPnnn 则则第33页/共54页 .)(2121 ,

20、)(2121)(2121 ,)(2121101 0 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第34页/共54页(2) 根据贝叶斯公式, 当系统经 n 级传输后输出为 1, 原发字符也是 1 的概率为:11|111|1000 nnnXPXXPXPXXP)()0()()0()()0(111010111nPpnPpnPp .)(12(1)(nnqpqp 第35页/共

21、54页说明说明. 1,0 ,11101 0 babbaaPn步转移概率矩阵为 )()()()(10)(1 0 11100100nPnpnPnpPnPn矩阵一般可表示为: ., 2 , 1 n,)1(1 bbaababaababban对于只有两个状态的马氏链, 一步转移概率第36页/共54页.1,.2.,1,1,)1( .,为为齐齐次次马马尔尔可可夫夫链链以以分分时时比比赛赛结结束束两两人人中中有有一一个个人人得得到到当当平平局局不不记记分分分分负负者者得得分分胜胜者者得得比比赛赛后后设设每每局局乙乙胜胜的的概概率率为为的的概概率率为为设设每每局局比比赛赛中中甲甲胜胜甲甲乙乙两两人人进进行行某某

22、种种比比赛赛 nXrqprpn.2,1)3(;2)2(;)1(结束的概率结束的概率局可以局可以最多再赛最多再赛分的情况下分的情况下问在甲获得问在甲获得步转移概率步转移概率求求写出状态空间写出状态空间例例3第37页/共54页解解 .2, 1, 0, 1, 2)1( S 1121012)1(21012)2(prqprqprqP第38页/共54页222222222101212 .22221qrprpqprpPqrqrpqprpqqrrpqppr所求所求甲胜甲胜局局再赛再赛分的情况下分的情况下在甲获得在甲获得,2,1)3(概率为. )1()2(12rpprppp 21012第39页/共54页四、小结切

23、普曼-柯尔莫哥洛夫方程 (简称 C K 方程) . , 2, 1,),()()(1 kkjikijjivpuPvuP 马氏链的n 步转移概率是一步转移概率的n 次方, 链的有限维分布可由初始分布和一步移概率完全确定.由 C K 方程可得第40页/共54页第三节 遍历性 一、遍历性的概念一、遍历性的概念三、应用举例三、应用举例 四、小结四、小结二、二、( (有限链有限链) )遍历性的充分条件遍历性的充分条件第41页/共54页一、遍历性的概念对于一般的两个状态的马氏链, 由上节内容可知,有极限有极限时时当当)(,1,0nPbaij .)(lim)(lim01000 babnPnPnn.)(lim)

24、(lim11101 baanPnPnn意义意义对固定的状态j,不管链在某一时刻的什么状态 i出发, 通过长时间的转移到达状态 j 的概率都趋.近于近于第42页/共54页定义定义若对于所有若对于所有间为间为设齐次马氏链的状态空设齐次马氏链的状态空, I存在极限存在极限转移概率转移概率的的)(,nPIaaijji )()(liminPjijn不依赖于不依赖于 jjjnnPnP212121)()(或或则称此链具有则称此链具有遍历性遍历性.),(, 121为链的极限分布为链的极限分布则称则称若若 jj第43页/共54页二、( (有限链) )遍历性的充分条件, ,21NaaaI 间间为为设设齐齐次次马马

25、氏氏链链的的状状态态空空,mP如如果果存存在在正正整整数数阵阵是是它它的的一一步步转转移移概概率率矩矩都有都有使对任意的使对任意的,Iaaji , 2, 1, 0)(NjimPij 满足条件满足条件它是方程组它是方程组且有极限分布且有极限分布则此链具有遍历性则此链具有遍历性PN, ),(,21 .1, 01的唯一解的唯一解 Njjj第44页/共54页说明说明步步转转移移概概率率使使数数求求证证遍遍历历性性即即找找一一正正整整mm,. 1.无零元无零元矩阵矩阵mP2. 极限分布转化为了求解方程组.3. 在定理的条件下马氏链的极限分布是平稳分布.第45页/共54页,000000 试说明带有两个反射壁的随机游动是遍历的, 并求其极限分布( (平稳分布) ).解解)(的元的元代表转移概率矩阵的正代表转移概率矩阵的正以以 例例12)2(PP 三、应用举例三、应用举例 010003/ 13/ 13/ 10003/ 13/ 13/ 10003/ 13/ 13/ 10001054321P5 4 3 2 1第46页/共54页 000000000000)4(4PP. 无零元,链是遍历的第47页/共54页:),(521满足方程组满足方程组极限分布极限分布 . 1,3/13/13/13/13/13/1,/33/1,3/15