北京工业大学研究生概率论与数理统计

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

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

3、布函数下的条件分布函数在条件在条件 iin xtXtX )()( 下下的的条条件件分分布布函函数数在在条条件件 11) ()( nnn xtXtX 或写成或写成 ),;,|,( 121121| 11 nnnnttt tttxxxtxF nn ),|,( 11| 1 nnnntt txtxF nn .),(性性具马尔可夫性或无后效具马尔可夫性或无后效这时称过程这时称过程TttX 并称此过程并称此过程为为马尔可夫过程马尔可夫过程. 3. 马尔可夫链的定义马尔可夫链的定义 时间和状态都是离散的马尔可夫过程称为时间和状态都是离散的马尔可夫过程称为马尔马尔 可夫链可夫链, ., 2 , 1 , 0),(

4、 nnXX n 简记为简记为 研究时间和状态都是离散的随机序列研究时间和状态都是离散的随机序列 .,( 21 RaaaI i 状状态态空空间间为为 二、马尔可夫过程的概率分布二、马尔可夫过程的概率分布 , 2, 1 , 0),( nnXX n 1. 用分布律描述马尔可夫性用分布律描述马尔可夫性 ;0, 21 mtttrn r 和和对对任任意意的的正正整整数数 , ii Tmnmt 有有 ,| 2211 imitititjnm aXaXaXaXaXP , | imjnm aXaXP . Iai 其其中中 称条件概率称条件概率 |),( imjnmij aXaXPnmmP nmam i 在时刻在时

5、刻条件下条件下处于状态处于状态为马氏链在时刻为马氏链在时刻, .的的转转移移概概率率转转移移到到状状态态 j a 说明说明: 转移概率具有特点转移概率具有特点 ., 2 , 1, 1),( 1 j ij inmmP 2. 转移概率转移概率 由转移概率组成的矩阵由转移概率组成的矩阵),(),(nmmPnmmP ij 称为马氏链的称为马氏链的转移概率矩阵转移概率矩阵. 此矩阵的每一行元素之和等于此矩阵的每一行元素之和等于1. 它是随机矩阵它是随机矩阵. 111213 212223 313233 , , , , 1 Pm mnPm mnPm mn Pm mnPm mnPm mn P m mn Pm

6、mnPm mnPm mn 此矩阵的每一 转移概率矩阵： 行元素之 和等于 3. 平稳性平稳性 njinmmP ij 及及时时间间间间距距只只与与当当转转移移概概率率,),( 有关时有关时, 称转移概率具有平稳性称转移概率具有平稳性. 同时也称此链是同时也称此链是齐次的齐次的或或时齐的时齐的. ),(),(,nPnmmP ijij 记记此此时时 . |)( imjnmij aXaXPnP 称为马氏链的称为马氏链的n步转移概率步转移概率 .)()(步步转转移移概概率率矩矩阵阵为为nnPnP ij 111213 212223 313233 1 1111213 2212223 3313233 ( )(

7、 )( ) ( )( )( ) ( )( )( ) 1| 1 ijijmjmi n P nPnPn PnPnPn P n PnPnPn PPP XaXa aPPP aPPP PP aPPP 在齐次马氏链中， 步转移概率矩阵为： 一步转移概率记为： 一步转移概率矩阵记为： a1 1 a2 2 aj j Xm+1的状态 的状态 Xm 一步转移概率一步转移概率.|()1( 1imjmijij aXaXPPp 特别的特别的, 当当 k=1 时时, 一步转移概率一步转移概率矩阵矩阵 的的状状态态 1 m X 的状态的状态 m X i a a a 2 1 j aaa 21 ijii j j ppp ppp

8、 ppp 21 12221 11211 )1(P 记为记为P )1(P 三、应用举例三、应用举例 , 0)0(,0),( XttX且且是独立增量过程是独立增量过程设设 .0),(是是一一个个马马尔尔可可夫夫过过程程证证明明 ttX 证明证明由独立增量过程的定义知由独立增量过程的定义知, ,2, 2 , 1,0 1 时时当当 njttt nnj .)()()0()( 1 相相互互独独立立与与增增量量 nnj tXtXXtX ,)(0)0( 11 nn xtXX与与根据条件根据条件即有即有 .)()( 1相 相互互独独立立与与 nnj xtXtX 例例1 .2, 2 , 1),()(相相互互独独立

9、立与与此此时时 njtXtX jn 是是一一个个即即具具有有无无后后效效性性这这表表明明0),(,)( ttXtX 马尔可夫过程马尔可夫过程. 说明说明: 泊松过程是时间连续状态离散的马氏过程泊松过程是时间连续状态离散的马氏过程; 维纳过程是时间状态都连续的马氏过程维纳过程是时间状态都连续的马氏过程. 设每一级的传真率为设每一级的传真率为 p, 误码率为误码率为 q=1-p. 设一个单位时间传输一级设一个单位时间传输一级, 只传输数字只传输数字0和和1的串联系统的串联系统 ( 传输系统传输系统) 0 X 1 1 X 2 X 1 n X n n X 2 如图如图: 是第一级的输入是第一级的输入

10、0 X)1( nnX n 级的输出级的输出是第是第 分析分析:, 2 , 1 , 0,是一随机过程是一随机过程 nXn ,1, 0 I状态空间状态空间 例例210 ,为为已已知知时时且且当当IiiX n , 1 有有关关所所处处的的状状态态分分布布只只与与iXX nn 而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关. 所以它是一个马氏链所以它是一个马氏链, 且是齐次的且是齐次的. 一步转移概率一步转移概率 1 , 0 , , | 1 ji, ijq ijp iXjXPp nnij 一步转移概率矩阵一步转移概率矩阵 pq qp 10 P 1 0 例例3 一维随机游动一维随机游动 .

11、21,5 , 4 , 3 , 2 , 1 等时刻发生游动等时刻发生游动 秒秒秒、秒、并且仅仅在并且仅仅在上作随机游动上作随机游动 在如图所示直线的点集在如图所示直线的点集一随机游动的质点一随机游动的质点 I 12345 游动的概率规则游动的概率规则 1/3的概率向左或向右移动一格的概率向左或向右移动一格, 或以或以1/3的概率留的概率留 在原处在原处; 如果如果Q现在位于点现在位于点 i (1 i 5),则下一时刻各以则下一时刻各以 12345 以概率以概率1移动到移动到2(或或4)这一点上这一点上. 如果如果Q现在位于现在位于1(或或5)这点上这点上, 则下一时刻就则下一时刻就 1和和5这两

12、点称为这两点称为反射壁反射壁. 上面这种游动称为上面这种游动称为带有两个带有两个反射壁反射壁的随机游动的随机游动. 12345 模拟方法模拟方法:产生均匀分布的随机数序列产生均匀分布的随机数序列132322 11122,其中其中1表示左移表示左移;2表示不动表示不动;3表示右移表示右移. 单击图形播放单击图形播放/ /暂停暂停 ESCESC键退出键退出 一维随机游动的演示一维随机游动的演示 理论分析理论分析:.的的位位置置时时表表示示时时刻刻以以QnX n ., 2 , 1 , 0,是一随机过程是一随机过程则则 nX n 状态空间就是状态空间就是I. ,为为已已知知时时且且当当IiiX n ,

13、 1 有有关关所所处处的的状状态态分分布布只只与与iXX nn 而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关. 所以它是一个马氏链所以它是一个马氏链, 且是齐次的且是齐次的. 一步转移概率一步转移概率| 1 iXjXPp nnij . 2, 0 4, 52, 1, 1 51, 1, 1, 3 1 ij jiji iiiij 或 01000 3/13/13/100 03/13/13/10 003/13/13/1 00010 5 4 3 2 1 P 5 4 3 2 1 说明说明: 相应链的转移概率矩阵只须把相应链的转移概率矩阵只须把P 中第中第1行改为行改为 改变游动的概率规则改变游

14、动的概率规则, 就可得到不同方式的就可得到不同方式的 随机游动和相应的马氏链随机游动和相应的马氏链. 如果把点如果把点 1 改为改为吸收壁吸收壁, ).0 , 0 , 0 , 0 , 1( 一步转移概率矩阵一步转移概率矩阵 . 0,.0 1, 1)10( , 1 0 210 转移概率矩阵转移概率矩阵并求其状态空间和一步并求其状态空间和一步是一马氏链，是一马氏链， 试证试证令令的随机变量序列的随机变量序列 取值取值以概率以概率取值取值以概率以概率 是相互独立且都是相互独立且都设设 n k nkn n nSXS pqpp XXXX 解解 , 3, 2, 1 0 的可能取值为的可能取值为由于由于 n

15、 k kn XS ., , 1 1 故它为马氏链故它为马氏链的取值无关的取值无关之前的之前的 而与而与的取值有关的取值有关的取值的概率只与的取值的概率只与又因又因 in nn SS SS ., 3, 2, 10 InSn的状态空间为的状态空间为所以所以 例例4 :.)(假设假设个人及某种传染病个人及某种传染病有有传染模型传染模型N ;, )1( 可能的可能的且一切成对的接触是等且一切成对的接触是等接触接触 个人中恰有两人互相个人中恰有两人互相在每个单位时间内此在每个单位时间内此 N ; ,)2( 率为率为 被传染上病的概被传染上病的概时时当健康者与患病者接触当健康者与患病者接触 . 0, ,

16、0)3( 得病的概率也为得病的概率也为接触接触 健康者如果不与患者健康者如果不与患者患病者康复的概率为患病者康复的概率为 .数数个单位时间内的患病人个单位时间内的患病人表示第表示第现以现以nX n . ,0, 一步转移概率矩阵一步转移概率矩阵并写出它的状态空间和并写出它的状态空间和 是一马氏链是一马氏链即即试说明这种传染过程试说明这种传染过程 nX n 例例5 解解 , 0NX n 最大可能为最大可能为的取值的最小可能为的取值的最小可能为由于由于 ., 2 , 1 , 0 0,0 NI nXN n 的状态空间为的状态空间为 故故到到之间的任何值均可能达之间的任何值均可能达且且 , 1 的取值有

17、关的取值有关的取值的概率只与的取值的概率只与由于由于 nn XX 步转移概率矩阵为步转移概率矩阵为它的一步转移概率和一它的一步转移概率和一 .)1, 2 , 1, )1( )(2 ,( Nj NN jNj j 其中其中 , 1 的取值无关的取值无关之前的之前的而与而与 in XX .0,为马氏链为马氏链故故 nX n 其它其它, 0 , )1( )(2 1 1, )1( )(2 0, 1 1 ij NN jNj ij NN jNj ji iXjXP nn 10000 1000 0100 0010 00001 11 22 11 NN P ? 55,35, 15.1 ,. )10( ,1,0. ,

18、21,31 , 于多少于多少 日为雨天的概率各等日为雨天的概率各等月月日为晴天日为晴天月月问问天天 日为晴日为晴月月又已知又已知的一步转移概率矩阵的一步转移概率矩阵 试写出马氏链试写出马氏链或或天状态天状态表示第表示第 表示雨天状态表示雨天状态以以表示晴天状态表示晴天状态以以为逆事件为逆事件 任一天晴或雨是互任一天晴或雨是互晴天转雨天的概率为晴天转雨天的概率为 雨天转晴天的概率为雨天转晴天的概率为设任意相继的两天中设任意相继的两天中 n XnX nn 解解为逆事件且雨天转为逆事件且雨天转由于任一天晴或雨是互由于任一天晴或雨是互 转移概率矩阵分别为转移概率矩阵分别为故一步转移概率和一步故一步转移

19、概率和一步 ,21,31晴天转雨天的概率为晴天转雨天的概率为晴天的概率为晴天的概率为 例例6 1, 0,21 0, 0,21 1, 1,32 0, 1,31 1 ji ji ji ji iXjXP nn 3231 2121 1 0 10 P 又由于又由于 1811187 127125 1 0 10 2 P , 6003. 03997. 0 5995. 04005. 0 1 0 10 4 P 又由于又由于 日为雨天的概率为日为雨天的概率为月月日为晴天日为晴天月月故故55,15 .5995. 0)4( 01 P 日为晴天的概率为日为晴天的概率为月月日为晴天日为晴天月月故故35,15 ,4167.

20、0125)2( 00 P 排队模型排队模型 设服务系统由一个服务员和只可以容纳两个设服务系统由一个服务员和只可以容纳两个 人的等候室组成人的等候室组成: 服务规则服务规则 假定一个需要服务的顾客到达系统时发现系统假定一个需要服务的顾客到达系统时发现系统 先到先服务先到先服务, 后来者需在等候室依次排队后来者需在等候室依次排队. 内已有内已有3个顾客个顾客(一个正在接受服务一个正在接受服务, 两个在等候两个在等候 室排队室排队), 则该顾客立即离去则该顾客立即离去. 随机到达者随机到达者 系系 统统 等候室等候室服务台服务台 离去者离去者 例例7 分析分析 . 1qt的的概概率率为为内内有有一一

21、个个顾顾客客进进入入系系统统时时间间间间隔隔 假设假设: 有一原来被服务的顾客离开系统有一原来被服务的顾客离开系统 (即服务完毕即服务完毕)的的 .p概率为概率为 个个顾顾客客在在这这时时间间间间隔隔内内多多于于一一充充分分小小时时当当,. 2t 进入或离开系统实际上是不可能的进入或离开系统实际上是不可能的. 3. 再设有无顾客来到与服务是否完毕是相互独立再设有无顾客来到与服务是否完毕是相互独立 的的. 以下用马氏链来描述这个服务系统以下用马氏链来描述这个服务系统. 时时系系统统内内的的顾顾客客数数表表示示时时刻刻tntnXX n :)( 系统状态系统状态 ., 2, 1 , 0,是一随机过程

22、是一随机过程则则 nX n 3 , 2 , 1 , 0 I状态空间状态空间 可知它是一个可知它是一个齐次马氏链齐次马氏链. : 00 p 在系统内没有顾客的条件下在系统内没有顾客的条件下, .1. 00 qpt 后后仍仍无无顾顾客客的的概概率率经经 : 01 p 在系统内没有顾客的条件下在系统内没有顾客的条件下, .概率概率后有一顾客进入系统的后有一顾客进入系统的经经t : 10 p 系统内恰有一顾客正在接受服务的条件下系统内恰有一顾客正在接受服务的条件下, ).1(. 10 qppt 后后系系统统内内无无人人的的概概率率经经 : 11 p 系统内恰有一顾客的条件下系统内恰有一顾客的条件下,

23、,时时间间内内在在 t 他因服务完毕而离去而另一他因服务完毕而离去而另一 顾客进入系统或者正在接受服务的顾客将继续顾客进入系统或者正在接受服务的顾客将继续 要求服务要求服务,且无人进入系统的概率且无人进入系统的概率. ).1)(1( 11 qppqp . 01 qp 正在接受服务的顾客继续要求服务正在接受服务的顾客继续要求服务,且在且在 : 12 p 正在接受服务的顾客继续要求服务正在接受服务的顾客继续要求服务, 且另一且另一 个顾客进入系统的概率个顾客进入系统的概率.).1( 12 pqp : 13 p t 间隔内有两个客顾进入系统的概率间隔内有两个客顾进入系统的概率, 由假设由假设, 后者

24、实际上是不可能发生的后者实际上是不可能发生的. 0 13 p 类似的类似的, ).2(0),1( ),1)(1(),1( 23 223221 jippqp qppqpqppp ij : 33 p 或者一人将离去且另一人将进入系统或者一人将离去且另一人将进入系统,或者或者 无人离开系统的概率无人离开系统的概率. ).1( 33 ppqp 该马氏链的一步转移概率为该马氏链的一步转移概率为 )1 ()1 (00 )1 ()1 ()1)(1 (0 00)1 ( 00)1 ( 3 2 1 0 3210 ppqqp pqpqqpqp qqp qq 某计算机房的一台计算机经常出故障某计算机房的一台计算机经常

25、出故障,研究者研究者 每隔每隔15分钟观察一次计算机运行状态分钟观察一次计算机运行状态,收集了收集了24小小 时的数据时的数据 (共作共作97次观察次观察) . 用用1表示正常状态表示正常状态, 用用0 表示不正常状态表示不正常状态, 所得的数据序列如下所得的数据序列如下: 1110010011111110011110111111001111111110001101101 分析分析 ,)97, 2, 1(个时段的计算机状态个时段的计算机状态为第为第设设 nnX n 状态空间状态空间: I=0, 1. 例例8 1110110110101111011101111011111100110111111

26、00111 96 次状态转移的情况次状态转移的情况: ;8, 00次次 ;18, 01次次 因此因此, 一步转移概率可用频率近似地表示为一步转移概率可用频率近似地表示为: , 26 8 188 8 0|0 100 nn XXPp , 26 18 188 18 0|1 101 nn XXPp , 70 18 5218 18 1|0 110 nn XXPp . 70 52 5218 52 1|1 111 nn XXPp ;18, 10 次次.52, 11次次 以下研究齐次马氏链的有限维分布以下研究齐次马氏链的有限维分布. : 1的一维分布 的一维分布马氏链在任意时刻马氏链在任意时刻Tn ., 2

27、, 1,)( jIaaXPnp jjnj 特点特点: 1 . 1)( j j np , | 1 00 i iijnjn aXPaXaXPaXP ., 2 , 1),()0()( 1 i ijij jnppnp即即 用行向量表示为用行向量表示为)()0()(nPpnp 一维分布由初始分布和一维分布由初始分布和 转移概率矩阵决定转移概率矩阵决定 （书（书P362 公式公式1.7） 一维分布也可用行向量表示成一维分布也可用行向量表示成 p(n)=( p1 1(n) , p2 2(n), pj j(n),) 这样，利用矩阵乘法（这样，利用矩阵乘法（I是可列无限集时，仍用有限阶是可列无限集时，仍用有限阶

28、 ）矩阵乘法的规则确定矩阵之积的元素，可写成）矩阵乘法的规则确定矩阵之积的元素，可写成 p(n) = p(0)P(n) (矩阵矩阵)。 结论：结论：马氏链在任一时刻马氏链在任一时刻n T1 1时的一维分布时的一维分布 由初始分布由初始分布 p(0)和和n 步转移概率矩阵所确定步转移概率矩阵所确定 。 121 ,Tttttn in 个时刻个时刻对于任意对于任意 , 21 Iaaa n iii 以及状态以及状态 马氏链的马氏链的 n 维分布维分布 ,., 2211nn ititit aXaXaXP |) 112211 ititit aXaXPaXP ,| 112211 nnnn itititit

29、aXaXaXaXP | 112211 ititit aXaXPaXP | 11 nnnn itit aXaXP ).()()( 1121 1211 nniiiii ttPttPtp nn 有限维分布仍由初始分布有限维分布仍由初始分布 和转移概率矩阵决定和转移概率矩阵决定 由乘法公式 （书（书P362 公式公式1.8） 例例9(续例续例8)若计算机在前一段（若计算机在前一段（15分钟）的状态为分钟）的状态为0，问从时段，问从时段 起此计算机能连续正常工作一小时（起此计算机能连续正常工作一小时（4个时段）的概率为多少？个时段）的概率为多少？ 解解 由题意，前一时段的状态为由题意，前一时段的状态为0就是初始分布就是初始分布P0 0（0)=PX 0 0= 0 。 计算机能连续正常