马尔可夫过程及其概率分布.ppt

第一节 马尔可夫过程及其概率分布 一、马尔可夫过程的概念 二、马尔可夫过程的概率分布 三、应用举例 四、小结 一、马尔可夫过程的概念 1. 马尔可夫性 (无后效性 ) 所处的状态为已知的在时刻系统过程或 0)( t 所处状态的条件分布与过程在时刻条件下 0, tt 特性称为之前所处的状态无关的与过程在时刻 0t 马尔可夫性 或 无后效性 . 即 : 过程“将来”的情况与“过去”的情况是无 关的 . 2. 马尔可夫过程的定义 具有马尔可夫性的随机过程称为 马尔可夫过程 . 用分布函数表述马尔可夫过程 ,),(: 的状态空间随机过程设 TttXI ,个数值的任意如果对时间 nt ,3,21 Ttnttt in 恰有 )(,)(,)(|)( 112211 nnnn xtXxtXxtXxtXP ,)(|)( 11 RxxtXxtXP nnnnn 下的条件分布函数在条件 iin xtXtX )()( 下的条件分布函数在条件 11 )()( nnn xtXtX 或写成 ),;,|,( 121121| 11 nnnnttt tttxxxtxF nn ),|,( 11| 1 nnnntt txtxF nn .),( 性具马尔可夫性或无后效这时称过程 TttX 并称此过程 为 马尔可夫过程 . 3. 马尔可夫链的定义 时间和状态都是离散的马尔可夫过程称为 马尔 可夫链 , .,2,1,0),( nnXX n简记为 研究时间和状态都是离散的随机序列 .,( 21 RaaaI i 状态空间为 二、马尔可夫过程的概率分布 ,2,1,0),( nnXX n 1. 用分布律描述马尔可夫性 ;0, 21 mtttrn r 和对任意的正整数 , ii Tmnmt 有 1 1 2 2 | , , , , rrm n j t i t i t i m iP X a X a X a X a X a ,| imjnm aXaXP .Ia i 其中 称条件概率 |),( imjnmij aXaXPnmmP nmam i 在时刻条件下处于状态为马氏链在时刻 , .的转移概率转移到状态 ja 说明 : 转移概率具有特点 .,2,1,1),( 1 j ij inmmP 2. 转移概率 由转移概率组成的矩阵 ),(),( nmmPnmmP ij 称为马氏链的 转移概率矩阵 . 此矩阵的每一行元 素之和等于 1. 它是随机矩阵 . 3. 平稳性 njinmmP ij 及时间间距只与当转移概率 ,),( 有关时 , 称转移概率具有平稳性 . 同时也称此链是 齐次的 或 时齐的 . ),(),(, nPnmmP ijij 记此时 .|)( imjnmij aXaXPnP 称为马氏链的 n步转移概率 .)()( 步转移概率矩阵为 nnPnP ij 一步转移概率 .|()1( 1 imjmijij aXaXPPp 特别的 , 当 k=1 时 , 一步转移概率 矩阵 的状态1mX 的 状 态 mX i a a a 2 1 jaaa 21 ijii j j ppp ppp 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),()( 相互独立与此时 njtXtX jn 是一个即具有无后效性这表明 0),(,)( ttXtX 马尔可夫过程 . 说明 : 泊松过程是时间连续状态离散的马氏过程 ; 维纳过程是时间状态都连续的马氏过程 . 设每一级的传真率为 p, 误码率为 q=1-p. 设一个单位时间传输一级 , 只传输数字 0和 1的串联系统 ( 传输系统 ) 0X 1 1X 2X 1nX n nX 2 如图 : 是第一级的输入0X )1( nnX n 级的输出是第 分析 : ,2,1,0, 是一随机过程nX n ,1,0I状态空间 例 2 10 , 为已知时且当 IiiX n ,1 有关所处的状态分布只与 iXX nn 而与时刻 n 以前所处的状态无关 . 所以它是一个马氏链 , 且是齐次的 . 一步转移概率 1,0,| 1 ji,ijq ijpiXjXPp nnij 一步转移概率矩阵 pq qp 10P 1 0 例 3 一维随机游动 . 21,5,4,3,2,1 等时刻发生游动 秒秒、并且仅仅在上作随机游动 在如图所示直线的点集一随机游动的质点 I 1 2 3 4 5 游动的概率规则 1/3的概率向左或向右移动一格 , 或以 1/3的概率留 在原处 ; 如果 Q现在位于点 i (1 i 5),则下一时刻各以 1 2 3 4 5 以概率 1移动到 2(或 4)这一点上 . 如果 Q现在位于 1(或 5)这点上 , 则下一时刻就 1和 5这两点称为 反射壁 . 上面这种游动称为 带有两个 反射壁 的随机游动 . 1 2 3 4 5 模拟方法 :产生均匀分布的随机数序列 132322 11122 ,其中 1表示左移 ;2表示不动 ;3表示右移 . 理论分析 : .的位置时表示时刻以 QnX n .,2,1,0, 是一随机过程则 nX n 状态空间就是 I. , 为已知时且当 IiiX n ,1 有关所处的状态分布只与 iXX nn 而与时刻 n 以前所处的状态无关 . 所以它是一个马氏链 , 且是齐次的 . 一步转移概率 | 1 iXjXPp nnij .21,0 4,52,1,1 51,1,1, 3 1 j 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行改为 改变游动的概率规则 , 就可得到不同方式的 随机游动和相应的马氏链 . 如果把点 1 改为 吸收壁 , ).0,0,0,0,1( 一 步 转 移 概 率 矩 阵 ? 55,35, 15.1 ,.)10( ,1,0. ,21,31 , 于多少 日为雨天的概率各等月日为晴天月问天 日为晴月又已知的一步转移概率矩阵 试写出马氏链或天状态表示第 表示雨天状态以表示晴天状态以为逆事件 任一天晴或雨是互晴天转雨天的概率为 雨天转晴天的概率为设任意相继的两天中 n XnX nn 解 为逆事件且雨天转由于任一天晴或雨是互 转移概率矩阵分别为故一步转移概率和一步 ,21,31 晴天转雨天的概率为晴天的概率为 例 4 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 2P , 6 0 0 3.03 9 9 7.0 5 9 9 5.04 0 0 5.0 1 0 10 4 P 又由于 日为雨天的概率为月日为晴天月故 55,15 .5995.0)4(01 P 日为晴天的概率为月日为晴天月故 35,15 ,4167.0125)2(00 P 某计算机房的一台计算机经常出故障 ,研究者 每隔 15分钟观察一次计算机运行状态 ,收集了 24小 时的数据 (共作 97次观察 ) . 用 1表示正常状态 , 用 0 表示不正常状态 , 所得的数据序列如下 : 1110010011111110011110111111001111111110001101101 分析 ,)97,2,1( 个时段的计算机状态为第设 nnX n 状态空间 : I=0, 1. 例 5 111011011010111101110111101111110011011111100111 96 次状态转移的情况 : ;8,00 次 ;18,01 次 因此 , 一步转移概率可用频率近似地表示为 : ,268188 80|0 100 nn XXPp ,2618188 180|1 101 nn XXPp ,70185218 181|0 110 nn XXPp .70525218 521|1 111 nn XXPp ;18,10 次 .52,11 次 以下研究齐次马氏链的有限维分布 . :1 的一维分布马氏链在任意时刻 Tn .,2,1,)( jIaaXPnp jjnj 特点 : 1 .1)( j j np ,| 1 00 i iijnjn aXPaXaXPaXP .,2,1),()0()( 1 i ijij jnppnp 即 用行向量表示为 )()0()( nPpnp 一维分布由初始分布和 转移概率矩阵决定 由以上讨论知 ,转移概率决定了马氏链的运 动的统计规律 . 因此 , 确定马氏链的任意 n步转 移概率成为马氏链理论中的重要问题之一 . 四、小结 齐次马氏链、平稳性的概念 . 一步转移概率矩阵的计算 . 一步转移概率 .|()1( 1 imjmijij aXaXPPp 一步转移概率 矩阵 ).()1( nPP ij 第二节 多步转移概率的确定 一 、 C-K 方程 三、应用举例 四、小结 二、 多步转移概率的确定 一 、 C-K 方程 ,)( 1TnnX 设 是一齐次马氏链 , 则对任意的 有, 1Tvu .,2,1,),()()( 1 k kjikij jivpuPvuP 切普曼 -柯尔莫哥洛夫方程 (简称 C -K方程 ) 说明 C-K 方程基于下列事实 : .)(, , ”转移到状态 经时段出发所处的状态“从时刻 jj i avusXa vuas 这一事件可分解成 : 转移到中间状态先经时段出发“从 uasX i ,)( ”等事转移到状态经时段在从 jkk avaka ),2,1( 件的和事件 . to s us vus ia ka ja 如下图所示 : 证明 ,1TsIa k 和先固定 由条件概率定义和乘法定理得 )(|)(,)( ikj asXausXavusXP )(,)(|)( )(|)( ikj ik asXausXavusXP asXausXP ).()( vPuP kjik (马氏性和齐次性 ) ,2,1,)( 构成一划分”因事件组“ kausX k 所以 )(|)()( ijij asXavusXPvuP 1 )(,)( k j usXavusXP .)(| ik asXa 考虑到马氏性和齐次性 , 即得 C-K 方程 . C-K 方程也可写成矩阵形式 : ).()()( vPuPvuP 二、多步转移概率的确定 利用 C-K 方程我们容易确定 n 步转移概率 . 得递推关系 : ,1,1 ,)()()( nvuvPuPvuP 令中在 ),1()1()1()( nPPnPPnP ( ) .nP n P 从而可得 马氏链的 n步转移概率是一步转移概率的 n 次 方 ,链的有限维分布可由初始分布和一步转移概率 完全确定 . 结论 步转移概率矩阵为 一马氏链是具有三个状态的齐次设 ,0, nX n .1)2( ;1,0)1( :,2,1,0 , 3 1 )0( 2 20 0 XP XXP i iXPp i 求 初始分布 , 4 1 4 3 0 4 1 2 1 4 1 0 4 1 4 3 P 解 (1)先求出 2步转移概率矩阵 : 例 1 . 4 1 16 9 16 3 16 3 2 1 16 5 16 1 16 5 8 5 )2( 2 PP 02 0 , 1 P X X 0|10 020 XXPXP )2()0( 010 pp ,48516531 1(2 ) (2 )p 1 2 XP 0 0 1 1 1 1 2 2 1 ( 0 ) ( 2 ) ( 0 ) ( 2 ) ( 0 ) ( 2 ) p p p p pp .2411)16921165(31 在 传输系统中 , 真率与三级求系统二级传输后的传设 ,9.0)1( p 传输后的误码率 ; ,1)0()2( 01 XPp设初始分布 .10)0( 00 XPp 系统经 n 级传输后输出为 1, 问原发字符也是 1 的 概率是多少 ? 例 2 10 解 先求出 n 步转移概率矩阵 . , 1 0 1 0 pq qp P因为 有相异的特征值 qp 21 ,1 所以可将 P 表示成对角阵 ,0 010 0 2 1 qp 11 )( HHHHP nnn 则 . )( 2 1 2 1 ,)( 2 1 2 1 )( 2 1 2 1 ,)( 2 1 2 1 1 0 1 0 nn nn qpqp qpqp 率与三级系统二级传输后的传真当 ,9.0)1( p 传输后的误码率分别为 : ,820.0)1.09.0(2121)2()2( 20011 PP ;244.0)1.09.0(2121)2()3( 30110 PP (2) 根据贝叶斯公式 , 当系统经 n 级传输后输出 为 1, 原发字符也是 1 的概率为 : 1 1|111|1 00 0 n n n XP XXPXPXXP )()0()()0( )()0( 111010 111 nPpnPp nPp .)(12(1 )( n n qp qp 说明 .1,0, 1 1 1 0 1 0 ba bb aa P n步转移概率矩阵 为 )()( )()( 1 0 )( 1 0 1110 0100 nPnp nPnp PnP n 矩阵一般可表示为 : .,2,1 n , )1(1 bb aa ba ba ab ab ba n 对于只有两个状态的马氏链 , 一步转移概率 . 1,.2 .,1,1, )1(., , 为齐次马尔可夫链 以分时比赛结束两人中有一个人得到 当平局不记分分负者得分胜者得比赛后 设每局乙胜的概率为的概率为 设每局比赛中甲胜甲乙两人进行某种比赛 nX rqprp n . 2,1)3( ;2)2( ;)1( 结束的概率 局可以最多再赛分的情况下问在甲获得 步转移概率求 写出状态空间 例 3 解 .2,1,0,1,2)1( S 1 1 2 1 0 1 2 )1( 21012)2( prq prq prq P 22 2 2 2 2 22 2 1 0 1 2 1 2 .2 2 2 2 1 q rp r p q p r p P q rq r p q p r p q q r r p q p p r 所求甲胜局再赛分的情况下在甲获得 ,2,1)3( 概率为 .)1()2(12 rpprppp 2 1 0 1 2 四、小结 切普曼 -柯尔莫哥洛夫方程 (简称 C K 方程 ) . ,2,1,),()()( 1 k kjikij jivpuPvuP 马氏链的 n 步转移概率是一步转移概率的 n 次 方 , 链的有限维分布可由初始分布和一步移概率完 全确定 . 由 C K 方程可得 第三节 遍历性 一 、 遍历性的概念 三 、 应用举例 四 、 小结 二 、 (有限链 )遍历性的充分条件 一、遍历性的概念 对于一般的两个状态的马氏链 , 由上节内容可知 , 有极限时当 )(,1,0 nPba ij .)(l i m)(l i m 01000 ba bnPnP nn .)(l i m)(l i m 11101 ba anPnP nn 意义 对固定的状态 j,不管链在某一时刻的什么 状 态 i出发 , 通过长时间的转移到达状态 j 的概率都趋 .近于 定义 若对于所有间为设齐次马氏链的状态空 ,I 存在极限转移概率的 )(, nPIaa ijji )()(l i m inP jijn 不依赖于 j j j n n PnP 21 21 21 )( )(或 则称此链具有 遍历性 . .),(,1 21 为链的极限分布则称若 j j 二 、 (有限链 )遍历性的充分条件 , 21 NaaaI 间为设齐次马氏链的状态空 , mP 如果存在正整数阵是它的一步转移概率矩 都有使对任意的 , Iaa ji ,2,1,0)( NjimP ij 满足条件它是方程组 且有极限分布则此链具有遍历性 PN ,),( , 21 .1,0 1 的唯一解 N j jj 说明 步转移概率使数求证遍历性即找一正整 mm ,.1 .无零元矩阵 mP 2. 极限分布转化为了求解方程组 . 3. 在定理的条件下马氏链的极限分布是平稳分布 . , 00 0 0 00 试说明带有两个反射壁的随机游动是遍历的 , 并求其极限分布 (平稳分布 ). 解 )( 的元代表转移概率矩阵的正以 例 1 2)2( PP 三 、 应用举例 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 00 0 0 00 00 0 0 00 )4( 4 PP . 无零元 ,链是遍历的 :),( 521 满足方程组极限分布 .1 ,3/1 3/13/1 3/13/13/1 ,/33/1 ,3/1 54321 45 5434 4323 3212 21 .33: 54321 由前四个方程解得 代入最后一个方程 (归一条件 ), 得唯一解 P 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 .11/3,11/1 43251 所以极限分布为 .)11/1,11/3,11/3,11/3,11/1( 这个 分布表明 经过长时间游动之后 , 醉汉 Q 位于点 2 (或 3 或 4 ) 的概率约为 3/11, 位于点 1 (或 5) 的概率约为 1/11. 设一马氏链的一步转移概率阵为 , 02/102/1 2/102/10 02/102/1 2/102/10 P 试讨论它的遍历性 . 解 , 2/102/10 02/102/1 2/102/10 02/102/1 )2( 2 PP 例 2 ,)1()(, PPnPn 为奇数时当 ).2()(, PnPn 为偶数时当 .)(l i m),4,3,2,1( 都不存在极限对任意固定的 npj ijn 表明 此链不具遍历性 . 四、小结 遍历性的概念 若对于所有的间为设齐次马氏链的状态空 ,I 存在极限转移概率 )(, nPIaa ijji ),()(l i m inP jijn 不依赖于 则称此链具有遍历性 . (有限链 ) 遍历性的充分条件 , 21 NaaaI 间为设齐次马氏链的状态空 , mP 如果存在正整数阵是它的一步转移概率矩 都有使对任意的 , Iaa ji ,2,1,0)( NjimP ij 满足条件它是方程组 且有极限分布则此链具有遍历性 PN ),( , 21 .1,0 1 的唯一解 N j jj