马尔科夫模型简介

1、第一节第一节 马尔可夫过程及其概率分布马尔可夫过程及其概率分布一、马尔可夫过程的概念一、马尔可夫过程的概念 二、马尔可夫过程的概率分布二、马尔可夫过程的概率分布 三、应用举例三、应用举例 四、小结四、小结一、马尔可夫过程的概念一、马尔可夫过程的概念 1. 马尔可夫性马尔可夫性(无后效性无后效性)所所处处的的状状态态为为已已知知的的在在时时刻刻系系统统过过程程或或0)(t所所处处状状态态的的条条件件分分布布与与过过程程在在时时刻刻条条件件下下0,tt 特特性性称称为为之之前前所所处处的的状状态态无无关关的的与与过过程程在在时时刻刻0t马尔可夫性马尔可夫性或或无后效性无后效性.即即: 过程过程“将

2、来将来”的情况与的情况与“过去过去”的情况是无的情况是无关的关的.2. 马尔可夫过程的定义马尔可夫过程的定义具有马尔可夫性的随机过程称为具有马尔可夫性的随机过程称为马尔可夫过程马尔可夫过程.用分布函数表述马尔可夫过程用分布函数表述马尔可夫过程,),(:的的状状态态空空间间随随机机过过程程设设TttXI ,个数值个数值的任意的任意如果对时间如果对时间nt, 3,21Ttntttin 恰有恰有)(,)(,)(|)(112211 nnnnxtXxtXxtXxtXP ,)(|)(11RxxtXxtXPnnnnn 下的条件分布函数下的条件分布函数在条件在条件iinxtXtX )()(下下的的条条件件分分

3、布布函函数数在在条条件件11)()( nnnxtXtX或写成或写成),;,|,(121121|11 nnnnttttttxxxtxFnn),|,(11|1 nnnntttxtxFnn.),(性性具马尔可夫性或无后效具马尔可夫性或无后效这时称过程这时称过程TttX 并称此过程并称此过程为为马尔可夫过程马尔可夫过程.3. 马尔可夫链的定义马尔可夫链的定义 时间和状态都是离散的马尔可夫过程称为时间和状态都是离散的马尔可夫过程称为马尔马尔可夫链可夫链, ., 2 , 1 , 0),( nnXXn简记为简记为研究时间和状态都是离散的随机序列研究时间和状态都是离散的随机序列.,(21RaaaIi 状状态态

4、空空间间为为二、马尔可夫过程的概率分布二、马尔可夫过程的概率分布, 2, 1 , 0),( nnXXn1. 用分布律描述马尔可夫性用分布律描述马尔可夫性;0,21mtttrnr 和和对对任任意意的的正正整整数数,iiTmnmt 有有1122|,rrm njtititimiP XaXa XaXaXa , |imjnmaXaXP . Iai 其其中中称条件概率称条件概率 |),(imjnmijaXaXPnmmP nmami 在时刻在时刻条件下条件下处于状态处于状态为马氏链在时刻为马氏链在时刻,.的的转转移移概概率率转转移移到到状状态态ja说明说明: 转移概率具有特点转移概率具有特点 ., 2 ,

5、1, 1),(1 jijinmmP2. 转移概率转移概率由转移概率组成的矩阵由转移概率组成的矩阵),(),(nmmPnmmPij 称为马氏链的称为马氏链的转移概率矩阵转移概率矩阵.此矩阵的每一行元此矩阵的每一行元素之和等于素之和等于1.它是随机矩阵它是随机矩阵.3. 平稳性平稳性njinmmPij及及时时间间间间距距只只与与当当转转移移概概率率,),( 有关时有关时, 称转移概率具有平稳性称转移概率具有平稳性.同时也称此链是同时也称此链是齐次的齐次的或或时齐的时齐的.),(),(,nPnmmPijij 记记此此时时 . |)(imjnmijaXaXPnP 称为马氏链的称为马氏链的n步转移概率步

6、转移概率.)()(步步转转移移概概率率矩矩阵阵为为nnPnPij 一步转移概率一步转移概率.|()1(1imjmijijaXaXPPp 特别的特别的, 当当 k=1 时时,一步转移概率一步转移概率矩阵矩阵的的状状态态1 mX的状态的状态mXiaaa21jaaa21 ijiijjppppppppp211222111211)1(P 记为记为P)1(P三、应用举例三、应用举例, 0)0(,0),( XttX且且是独立增量过程是独立增量过程设设.0),(是是一一个个马马尔尔可可夫夫过过程程证证明明 ttX证明证明由独立增量过程的定义知由独立增量过程的定义知,2, 2 , 1,01时时当当 njtttn

7、nj.)()()0()(1相相互互独独立立与与增增量量 nnjtXtXXtX,)(0)0(11 nnxtXX与与根据条件根据条件即有即有.)()(1相相互互独独立立与与 nnjxtXtX例例1.2, 2 , 1),()(相相互互独独立立与与此此时时 njtXtXjn是是一一个个即即具具有有无无后后效效性性这这表表明明0),(,)( ttXtX马尔可夫过程马尔可夫过程.说明说明:泊松过程是时间连续状态离散的马氏过程泊松过程是时间连续状态离散的马氏过程;维纳过程是时间状态都连续的马氏过程维纳过程是时间状态都连续的马氏过程.设每一级的传真率为设每一级的传真率为 p, 误码率为误码率为 q=1-p.设

8、一个单位时间传输一级设一个单位时间传输一级,只传输数字只传输数字0和和1的串联系统的串联系统 ( 传输系统传输系统)0X11X2X1 nXnnX2如图如图:是第一级的输入是第一级的输入0X)1( nnXn级的输出级的输出是第是第分析分析:, 2 , 1 , 0,是是一一随随机机过过程程 nXn,1, 0 I状态空间状态空间例例210 ,为为已已知知时时且且当当IiiXn ,1有有关关所所处处的的状状态态分分布布只只与与iXXnn 而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关.所以它是一个马氏链所以它是一个马氏链, 且是齐次的且是齐次的. 一步转移概率一步转移概率1 , 0,|1

9、ji,ijqijpiXjXPpnnij一步转移概率矩阵一步转移概率矩阵 pqqp10 P10例例3 一维随机游动一维随机游动.21,5 , 4 , 3 , 2 , 1等时刻发生游动等时刻发生游动秒秒秒、秒、并且仅仅在并且仅仅在上作随机游动上作随机游动在如图所示直线的点集在如图所示直线的点集一随机游动的质点一随机游动的质点 I12345游动的概率规则游动的概率规则1/3的概率向左或向右移动一格的概率向左或向右移动一格, 或以或以1/3的概率留的概率留在原处在原处; 如果如果Q现在位于点现在位于点 i (1 i 5),则下一时刻各以则下一时刻各以12345以概率以概率1移动到移动到2(或或4)这一

10、点上这一点上.如果如果Q现在位于现在位于1(或或5)这点上这点上, 则下一时刻就则下一时刻就1和和5这两点称为这两点称为反射壁反射壁.上面这种游动称为上面这种游动称为带有两个带有两个反射壁反射壁的随机游动的随机游动.12345模拟方法模拟方法:产生均匀分布的随机数序列产生均匀分布的随机数序其中其中1表示左移表示左移;2表示不动表示不动;3表示右移表示右移.理论分析理论分析:.的的位位置置时时表表示示时时刻刻以以QnXn., 2 , 1 , 0,是一随机过程是一随机过程则则 nXn状态空间就是状态空间就是I.,为为已已知知时时且且当当IiiXn ,1有有关关所所处处的的

11、状状态态分分布布只只与与iXXnn 而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关.所以它是一个马氏链所以它是一个马氏链, 且是齐次的且是齐次的. 一步转移概率一步转移概率|1iXjXPpnnij . 21, 04, 52, 1, 151, 1, 1,31 jjijiiiiij或或 010003/13/13/10003/13/13/10003/13/13/10001054321P5 4 3 2 1说明说明:相应链的转移概率矩阵只须把相应链的转移概率矩阵只须把P 中第中第1行改为行改为改变游动的概率规则改变游动的概率规则, 就可得到不同方式的就可得到不同方式的随机游动和相应的马氏链随

12、机游动和相应的马氏链. 如果把点如果把点 1 改为改为吸收壁吸收壁, ).0 , 0 , 0 , 0 , 1(一步转移概率矩阵一步转移概率矩阵?55,35,15.1,. )10(,1,0.,21,31,于多少于多少日为雨天的概率各等日为雨天的概率各等月月日为晴天日为晴天月月问问天天日为晴日为晴月月又已知又已知的一步转移概率矩阵的一步转移概率矩阵试写出马氏链试写出马氏链或或天状态天状态表示第表示第表示雨天状态表示雨天状态以以表示晴天状态表示晴天状态以以为逆事件为逆事件任一天晴或雨是互任一天晴或雨是互晴天转雨天的概率为晴天转雨天的概率为雨天转晴天的概率为雨天转晴天的概率为设任意相继的两天中设任意相

13、继的两天中 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(

14、01 P日为晴天的概率为日为晴天的概率为月月日为晴天日为晴天月月故故35,15,4167. 0125)2(00 P 某计算机房的一台计算机经常出故障某计算机房的一台计算机经常出故障,研究者研究者每隔每隔15分钟观察一次计算机运行状态分钟观察一次计算机运行状态,收集了收集了24小小时的数据时的数据 (共作共作97次观察次观察) . 用用1表示正常状态表示正常状态, 用用0表示不正常状态表示不正常状态, 所得的数据序列如下所得的数据序列如下:1110010011111110011110111111001111111110001101101分析分析,)97, 2, 1(个时段的计算机状态个时段的计算

15、机状态为第为第设设 nnXn状态空间状态空间: I=0, 1. 例例511101101101011110111011110111111001101111110011196 次状态转移的情况次状态转移的情况: ;8, 00次次;18, 01次次因此因此, 一步转移概率可用频率近似地表示为一步转移概率可用频率近似地表示为:,26818880|0100 nnXXPp,2618188180|1101 nnXXPp,70185218181|0110 nnXXPp.70525218521|1111 nnXXPp;18, 10 次次.52, 11次次以下研究齐次马氏链的有限维分布以下研究齐次马氏链的有限维分

16、布.:1的的一一维维分分布布马马氏氏链链在在任任意意时时刻刻Tn ., 2 , 1,)( jIaaXPnpjjnj特点特点: 1. 1)(jjnp, |100 iiijnjnaXPaXaXPaXP ., 2 , 1),()0()(1 iijijjnppnp即即用行向量表示为用行向量表示为)()0()(nPpnp 一维分布由初始分布和一维分布由初始分布和转移概率矩阵决定转移概率矩阵决定 由以上讨论知由以上讨论知,转移概率决定了马氏链的运转移概率决定了马氏链的运动的统计规律动的统计规律. 因此因此, 确定马氏链的任意确定马氏链的任意n步转步转移概率成为马氏链理论中的重要问题之一移概率成为马氏链理论

17、中的重要问题之一.四、小结四、小结齐次马氏链、平稳性的概念齐次马氏链、平稳性的概念.一步转移概率矩阵的计算一步转移概率矩阵的计算.一步转移概率一步转移概率.|()1(1imjmijijaXaXPPp 一步转移概率一步转移概率矩阵矩阵).()1(nPPij 第二节第二节 多步转移概率的确定多步转移概率的确定 一、一、C-K 方程方程三、应用举例三、应用举例 四、小结四、小结二、多步转移概率的确定二、多步转移概率的确定一、一、C-K 方程方程, )(1TnnX 设设是一齐次马氏链是一齐次马氏链, 则对任意的则对任意的有有,1Tvu ., 2, 1,),()()(1 kkjikijjivpuPvuP

18、切普曼切普曼- -柯尔莫哥洛夫方程柯尔莫哥洛夫方程( (简称简称C -K方程方程) )说明说明C-K 方程基于下列事实方程基于下列事实:.)(,”转移到状态转移到状态经时段经时段出发出发所处的状态所处的状态“从时刻“从时刻jjiavusXavuas 这一事件可分解成这一事件可分解成:转转移移到到中中间间状状态态先先经经时时段段出出发发“从从uasXi,)( ”等事”等事转移到状态转移到状态经时段经时段在从在从jkkavaka),2, 1( 件的和事件件的和事件.tosus vus iakaja如下图所示如下图所示:证明证明,1TsIak 和和先先固固定定由条件概率定义和乘法定理得由条件概率定义

19、和乘法定理得)(|)(,)(ikjasXausXavusXP )(,)(|)()(|)(ikjikasXausXavusXPasXausXP ).()(vPuPkjik (马氏性和齐次性马氏性和齐次性), 2 , 1,)(构构成成一一划划分分”因因事事件件组组“ kausXk所以所以)(|)()(ijijasXavusXPvuP 1)(,)(kjusXavusXP.)(|ikasXa 考虑到马氏性和齐次性考虑到马氏性和齐次性, 即得即得 C-K 方程方程.C-K 方程也可写成矩阵形式方程也可写成矩阵形式: ).()()(vPuPvuP 二、多步转移概率的确定二、多步转移概率的确定利用利用 C-

20、K 方程我们容易确定方程我们容易确定 n 步转移概率步转移概率.得递推关系得递推关系: , 1, 1 ,)()()( nvuvPuPvuP令令中中在在),1()1()1()( nPPnPPnP( ).nP nP从而可得从而可得 马氏链的马氏链的n步转移概率是一步转移概率的步转移概率是一步转移概率的 n 次次方方,链的有限维分布可由初始分布和一步转移概率链的有限维分布可由初始分布和一步转移概率完全确定完全确定.结论结论 步步转转移移概概率率矩矩阵阵为为一一马马氏氏链链是是具具有有三三个个状状态态的的齐齐次次设设,0, nXn.1)2(;1,0)1(:,2,1,0,31)0(2200 XPXXPi

21、iXPpi求求初初始始分分布布,4143041214104143 P解解(1)先求出先求出2步转移概率矩阵步转移概率矩阵:例例1.411691631632116516116585)2(2 PP020,1P XX0|10020 XXPXP)2()0(010pp ,48516531 1(2) (2)p12 XP001111221(0)(2)(0)(2)(0)(2)pppppp.2411)16921165(31 在在 传输系统中传输系统中,真率与三级真率与三级求系统二级传输后的传求系统二级传输后的传设设, 9 . 0)1( p传输后的误码率传输后的误码率;,1)0()2(01 XPp设设初初始始分分

22、布布.10)0(00 XPp系统经系统经 n 级传输后输出为级传输后输出为 1, 问原发字符也是问原发字符也是 1 的的概率是多少概率是多少?例例210 解解先求出先求出 n 步转移概率矩阵步转移概率矩阵.,101 0 pqqpP因为因为有相异的特征值有相异的特征值qp 21, 1 所以可将所以可将 P 表示成对角阵表示成对角阵,0010021 qp 11)( HHHHPnnn 则则 .)(2121 ,)(2121)(2121 ,)(2121101 0 nnnnqpqpqpqp率与三级率与三级系统二级传输后的传真系统二级传输后的传真当当, 9 . 0)1( p传输后的误码率分别为传输后的误码率

23、分别为:,820. 0)1 . 09 . 0(2121)2()2(20011 PP;244. 0)1 . 09 . 0(2121)2()3(30110 PP(2) 根据贝叶斯公式根据贝叶斯公式, 当系统经当系统经 n 级传输后输出级传输后输出为为 1, 原发字符也是原发字符也是 1 的概率为的概率为:11|111|1000 nnnXPXXPXPXXP)()0()()0()()0(111010111nPpnPpnPp .)(12(1)(nnqpqp 说明说明. 1,0 ,11101 0 babbaaPn步转移概率矩阵步转移概率矩阵为为 )()()()(10)(1 0 11100100nPnpnP

24、npPnPn矩阵一般可表示为矩阵一般可表示为: ., 2 , 1 n,)1(1 bbaababaababban对于只有两个状态的马氏链对于只有两个状态的马氏链, 一步转移概率一步转移概率.1,.2.,1,1,)1( .,为为齐齐次次马马尔尔可可夫夫链链以以分分时时比比赛赛结结束束两两人人中中有有一一个个人人得得到到当当平平局局不不记记分分分分负负者者得得分分胜胜者者得得比比赛赛后后设设每每局局乙乙胜胜的的概概率率为为的的概概率率为为设设每每局局比比赛赛中中甲甲胜胜甲甲乙乙两两人人进进行行某某种种比比赛赛 nXrqprpn.2,1)3(;2)2(;)1(结束的概率结束的概率局可以局可以最多再赛最

25、多再赛分的情况下分的情况下问在甲获得问在甲获得步转移概率步转移概率求求写出状态空间写出状态空间例例3解解 .2, 1, 0, 1, 2)1( S 1121012)1(21012)2(prqprqprqP222222222101212 .22221qrprpqprpPqrqrpqprpqqrrpqppr所求所求甲胜甲胜局局再赛再赛分的情况下分的情况下在甲获得在甲获得,2,1)3(概率为概率为. )1()2(12rpprppp 21012四、小结四、小结切普曼切普曼-柯尔莫哥洛夫方程柯尔莫哥洛夫方程 (简称简称 C K 方程方程) . , 2, 1,),()()(1 kkjikijjivpuPvu

26、P 马氏链的马氏链的n 步转移概率是一步转移概率的步转移概率是一步转移概率的n 次次方方, 链的有限维分布可由初始分布和一步移概率完链的有限维分布可由初始分布和一步移概率完全确定全确定.由由 C K 方程可得方程可得第三节第三节 遍历性遍历性 一、遍历性的概念一、遍历性的概念三、应用举例三、应用举例 四、小结四、小结二、二、( (有限链有限链) )遍历性的充分条件遍历性的充分条件一、遍历性的概念一、遍历性的概念对于一般的两个状态的马氏链对于一般的两个状态的马氏链, 由上节内容可知由上节内容可知,有有极极限限时时当当)(,1,0nPbaij .)(lim)(lim01000 babnPnPnn.

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

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