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 XaXaXaXaXa ,|imjnmaXaXP .Iai 其其中中称条件概率称条件概率|),(imjnmijaXaXPnmmP nmami 在在时时刻刻条条件件下下处处于于状状态态为为马马氏氏链链在在时时刻刻,.的转移概率的转移概率转移到状态转移到状态ja说明说明:转移概率具有特点转移概率具有特点 .,2,1,1),(1 jijinmmP2.转移概率转移概率由转移
5、概率组成的矩阵由转移概率组成的矩阵),(),(nmmPnmmPij 称为马氏链的称为马氏链的转移概率矩阵转移概率矩阵.此矩阵的每一行元此矩阵的每一行元素之和等于素之和等于1.它是随机矩阵它是随机矩阵.3.平稳性平稳性njinmmPij及及时时间间间间距距只只与与当当转转移移概概率率,),(有关时有关时,称转移概率具有平稳性称转移概率具有平稳性.同时也称此链是同时也称此链是齐次的齐次的或或时齐的时齐的.),(),(,nPnmmPijij 记记此此时时 .|)(imjnmijaXaXPnP 称为马氏链的称为马氏链的n步转移概率步转移概率.)()(步步转转移移概概率率矩矩阵阵为为nnPnPij 一步
6、转移概率一步转移概率.|()1(1imjmijijaXaXPPp 特别的特别的,当当 k=1 时时,一步转移概率矩阵一步转移概率矩阵的的状状态态1 mX的状态的状态mXiaaa21jaaa21 ijiijjppppppppp211222111211)1(P 记为记为P)1(P三、应用举例三、应用举例,0)0(,0),(XttX且且是是独独立立增增量量过过程程设设.0),(是一个马尔可夫过程是一个马尔可夫过程证明证明 ttX证明证明由独立增量过程的定义知由独立增量过程的定义知,2,2,1,01时时当当 njtttnnj.)()()0()(1相相互互独独立立与与增增量量 nnjtXtXXtX,)(
7、0)0(11 nnxtXX与与根根据据条条件件即有即有.)()(1相互独立相互独立与与 nnjxtXtX例例1.2,2,1),()(相相互互独独立立与与此此时时 njtXtXjn是一个是一个即即具有无后效性具有无后效性这表明这表明0),(,)(ttXtX马尔可夫过程马尔可夫过程.说明说明:泊松过程是时间连续状态离散的马氏过程泊松过程是时间连续状态离散的马氏过程;维纳过程是时间状态都连续的马氏过程维纳过程是时间状态都连续的马氏过程.设每一级的传真率为设每一级的传真率为 p,误码率为误码率为 q=1-p.设一个单位时间传输一级设一个单位时间传输一级,只传输数字只传输数字0和和1的串联系统的串联系统
8、(传输系统传输系统)0X11X2X1 nXnnX2如图如图:是第一级的输入是第一级的输入0X)1(nnXn级级的的输输出出是是第第分析分析:,2,1,0,是是一一随随机机过过程程 nXn,1,0 I状态空间状态空间例例210,为已知时为已知时且当且当IiiXn ,1有有关关所所处处的的状状态态分分布布只只与与iXXnn 而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关.所以它是一个马氏链所以它是一个马氏链,且是齐次的且是齐次的.一步转移概率一步转移概率1,0,|1 ji,ijqijpiXjXPpnnij一步转移概率矩阵一步转移概率矩阵 pqqp10 P10例例3 一维随机游动一维随机
9、游动.21,5,4,3,2,1等等时时刻刻发发生生游游动动秒秒秒秒、并并且且仅仅仅仅在在上上作作随随机机游游动动在在如如图图所所示示直直线线的的点点集集一一随随机机游游动动的的质质点点 I12345游动的概率规则游动的概率规则1/3的概率向左或向右移动一格的概率向左或向右移动一格,或以或以1/3的概率留的概率留在原处在原处;如果如果Q现在位于点现在位于点 i(1 i 5),则下一时刻各以则下一时刻各以12345以概率以概率1移动到移动到2(或或4)这一点上这一点上.如果如果Q现在位于现在位于1(或或5)这点上这点上,则下一时刻就则下一时刻就1和和5这两点称为这两点称为反射壁反射壁.上面这种游动
10、称为上面这种游动称为带有两个带有两个反射壁反射壁的随机游动的随机游动.12345模拟方法模拟方法:产生均匀分布的随机数序列产生均匀分布的随机数序列13232211122,其中其中1表示左移表示左移;2表示不动表示不动;3表示右移表示右移.理论分析理论分析:.的的位位置置时时表表示示时时刻刻以以QnXn.,2,1,0,是是一一随随机机过过程程则则 nXn状态空间就是状态空间就是I.,为已知时为已知时且当且当IiiXn ,1有有关关所所处处的的状状态态分分布布只只与与iXXnn 而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关.所以它是一个马氏链所以它是一个马氏链,且是齐次的且是齐次的.
11、一步转移概率一步转移概率|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行改为行改为改变游动的概率规则改变游动的概率规则,就可得到不同方式的就可得到不同方式的随机游动和相应的马氏链随机游动和相应的马氏链.如果把点如果把点 1 改为改为吸收壁吸收壁,).0,0,0,0,1(一步转移概率矩阵一步转移概率矩阵?55,35,15.1,.)10(,1,0.,21,3
12、1,于多少于多少日为雨天的概率各等日为雨天的概率各等月月日为晴天日为晴天月月问问天天日为晴日为晴月月又已知又已知的一步转移概率矩阵的一步转移概率矩阵试写出马氏链试写出马氏链或或天状态天状态表示第表示第表示雨天状态表示雨天状态以以表示晴天状态表示晴天状态以以为逆事件为逆事件任一天晴或雨是互任一天晴或雨是互晴天转雨天的概率为晴天转雨天的概率为雨天转晴天的概率为雨天转晴天的概率为设任意相继的两天中设任意相继的两天中 nXnXnn解解为逆事件且雨天转为逆事件且雨天转由于任一天晴或雨是互由于任一天晴或雨是互转转移移概概率率矩矩阵阵分分别别为为故故一一步步转转移移概概率率和和一一步步,21,31晴晴天天转
13、转雨雨天天的的概概率率为为晴晴天天的的概概率率为为例例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分钟观察一次
14、计算机运行状态分钟观察一次计算机运行状态,收集了收集了24小小时的数据时的数据(共作共作97次观察次观察).用用1表示正常状态表示正常状态,用用0表示不正常状态表示不正常状态,所得的数据序列如下所得的数据序列如下:1110010011111110011110111111001111111110001101101分析分析,)97,2,1(个个时时段段的的计计算算机机状状态态为为第第设设 nnXn状态空间状态空间:I=0,1.例例511101101101011110111011110111111001101111110011196 次状态转移的情况次状态转移的情况:;8,00次次;18,01次次因
15、此因此,一步转移概率可用频率近似地表示为一步转移概率可用频率近似地表示为:,26818880|0100 nnXXPp,2618188180|1101 nnXXPp,70185218181|0110 nnXXPp.70525218521|1111 nnXXPp;18,10 次次.52,11次次以下研究齐次马氏链的有限维分布以下研究齐次马氏链的有限维分布.:1的的一一维维分分布布马马氏氏链链在在任任意意时时刻刻Tn .,2,1,)(jIaaXPnpjjnj特点特点:1.1)(jjnp,|100 iiijnjnaXPaXaXPaXP .,2,1),()0()(1 iijijjnppnp即即用行向量表
16、示为用行向量表示为)()0()(nPpnp 一维分布由初始分布和一维分布由初始分布和转移概率矩阵决定转移概率矩阵决定 由以上讨论知由以上讨论知,转移概率决定了马氏链的运转移概率决定了马氏链的运动的统计规律动的统计规律.因此因此,确定马氏链的任意确定马氏链的任意n步转步转移概率成为马氏链理论中的重要问题之一移概率成为马氏链理论中的重要问题之一.四、小结四、小结齐次马氏链、平稳性的概念齐次马氏链、平稳性的概念.一步转移概率矩阵的计算一步转移概率矩阵的计算.一步转移概率一步转移概率.|()1(1imjmijijaXaXPPp 一步转移概率矩阵一步转移概率矩阵).()1(nPPij 第二节第二节 多步
17、转移概率的确定多步转移概率的确定 一、一、C-K 方程方程三、应用举例三、应用举例 四、小结四、小结二、多步转移概率的确定二、多步转移概率的确定一、一、C-K 方程方程,)(1TnnX 设设是一齐次马氏链是一齐次马氏链,则对任意的则对任意的有有,1Tvu .,2,1,),()()(1 kkjikijjivpuPvuP切普曼切普曼-柯尔莫哥洛夫方程柯尔莫哥洛夫方程(简称简称C-K方程方程)说明说明C-K 方程基于下列事实方程基于下列事实:.)(,”转转移移到到状状态态经经时时段段出出发发所所处处的的状状态态“从从时时刻刻jjiavusXavuas 这一事件可分解成这一事件可分解成:转转移移到到中
18、中间间状状态态先先经经时时段段出出发发“从从uasXi,)(”等等事事转转移移到到状状态态经经时时段段在在从从jkkavaka),2,1(件的和事件件的和事件.tosus vus iakaja如下图所示如下图所示:证明证明,1TsIak 和和先先固固定定由条件概率定义和乘法定理得由条件概率定义和乘法定理得)(|)(,)(ikjasXausXavusXP )(,)(|)()(|)(ikjikasXausXavusXPasXausXP ).()(vPuPkjik(马氏性和齐次性马氏性和齐次性),2,1,)(构成一划分构成一划分”因事件组“因事件组“kausXk所以所以)(|)()(ijijasXa
19、vusXPvuP 1)(,)(kjusXavusXP.)(|ikasXa 考虑到马氏性和齐次性考虑到马氏性和齐次性,即得即得 C-K 方程方程.C-K 方程也可写成矩阵形式方程也可写成矩阵形式:).()()(vPuPvuP 二、多步转移概率的确定二、多步转移概率的确定利用利用 C-K 方程我们容易确定方程我们容易确定 n 步转移概率步转移概率.得递推关系得递推关系:,1,1,)()()(nvuvPuPvuP令令中中在在),1()1()1()(nPPnPPnP().nP nP从而可得从而可得 马氏链的马氏链的n步转移概率是一步转移概率的步转移概率是一步转移概率的 n 次次方方,链的有限维分布可由
20、初始分布和一步转移概率链的有限维分布可由初始分布和一步转移概率完全确定完全确定.结论结论 步步转转移移概概率率矩矩阵阵为为一一马马氏氏链链是是具具有有三三个个状状态态的的齐齐次次设设,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)(2)
21、(0)(2)(0)(2)pppppp.2411)16921165(31 在在 传输系统中传输系统中,真率与三级真率与三级求系统二级传输后的传求系统二级传输后的传设设,9.0)1(p传输后的误码率传输后的误码率;,1)0()2(01 XPp设设初初始始分分布布.10)0(00 XPp系统经系统经 n 级传输后输出为级传输后输出为 1,问原发字符也是问原发字符也是 1 的的概率是多少概率是多少?例例210 解解先求出先求出 n 步转移概率矩阵步转移概率矩阵.,101 0 pqqpP因为因为有相异的特征值有相异的特征值qp 21,1 所以可将所以可将 P 表示成对角阵表示成对角阵,0010021 q
22、p 11)(HHHHPnnn 则则 .)(2121 ,)(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(2)根据贝叶斯公式根据贝叶斯公式,当系统经当系统经 n 级传输后输出级传输后输出为为 1,原发字符也是原发字符也是 1 的概率为的概率为:11|111|1000 nnnXPXXPXPXXP)()0()()0()()0(11
23、1010111nPpnPpnPp .)(12(1)(nnqpqp 说明说明.1,0,11101 0 babbaaPn步转移概率矩阵步转移概率矩阵为为 )()()()(10)(1 0 11100100nPnpnPnpPnPn矩阵一般可表示为矩阵一般可表示为:.,2,1 n,)1(1 bbaababaababban对于只有两个状态的马氏链对于只有两个状态的马氏链,一步转移概率一步转移概率.1,.2.,1,1,)1(.,为为齐齐次次马马尔尔可可夫夫链链以以分分时时比比赛赛结结束束两两人人中中有有一一个个人人得得到到当当平平局局不不记记分分分分负负者者得得分分胜胜者者得得比比赛赛后后设设每每局局乙乙胜
24、胜的的概概率率为为的的概概率率为为设设每每局局比比赛赛中中甲甲胜胜甲甲乙乙两两人人进进行行某某种种比比赛赛 nXrqprpn.2,1)3(;2)2(;)1(结结束束的的概概率率局局可可以以最最多多再再赛赛分分的的情情况况下下问问在在甲甲获获得得步步转转移移概概率率求求写写出出状状态态空空间间例例3解解 .2,1,0,1,2)1(S 1121012)1(21012)2(prqprqprqP222222222101212 .22221qrprpqprpPqrqrpqprpqqrrpqppr所求所求甲胜甲胜局局再赛再赛分的情况下分的情况下在甲获得在甲获得,2,1)3(概率为概率为.)1()2(12r
25、pprppp 21012四、小结四、小结切普曼切普曼-柯尔莫哥洛夫方程柯尔莫哥洛夫方程(简称简称 C K 方程方程).,2,1,),()()(1 kkjikijjivpuPvuP 马氏链的马氏链的n 步转移概率是一步转移概率的步转移概率是一步转移概率的n 次次方方,链的有限维分布可由初始分布和一步移概率完链的有限维分布可由初始分布和一步移概率完全确定全确定.由由 C K 方程可得方程可得第三节第三节 遍历性遍历性 一、遍历性的概念一、遍历性的概念三、应用举例三、应用举例 四、小结四、小结二、二、(有限链有限链)遍历性的充分条件遍历性的充分条件一、遍历性的概念一、遍历性的概念对于一般的两个状态的
26、马氏链对于一般的两个状态的马氏链,由上节内容可知由上节内容可知,有有极极限限时时当当)(,1,0nPbaij .)(lim)(lim01000 babnPnPnn.)(lim)(lim11101 baanPnPnn意义意义对固定的状态对固定的状态j,不管链在某一时刻的什么状不管链在某一时刻的什么状态态 i出发出发,通过长时间的转移到达状态通过长时间的转移到达状态 j 的概率都趋的概率都趋.近于近于定义定义若对于所有若对于所有间为间为设齐次马氏链的状态空设齐次马氏链的状态空,I存在极限存在极限转移概率转移概率的的)(,nPIaaijji)()(liminPjijn不不依依赖赖于于 jjjnnPn
27、P212121)()(或或则称此链具有则称此链具有遍历性遍历性.),(,121为链的极限分布为链的极限分布则称则称若若 jj二、二、(有限链有限链)遍历性的充分条件遍历性的充分条件,21NaaaI 间间为为设设齐齐次次马马氏氏链链的的状状态态空空,mP如如果果存存在在正正整整数数阵阵是是它它的的一一步步转转移移概概率率矩矩都有都有使对任意的使对任意的,Iaaji,2,1,0)(NjimPij 满足条件满足条件它是方程组它是方程组且有极限分布且有极限分布则此链具有遍历性则此链具有遍历性PN,),(,21 .1,01的的唯唯一一解解 Njjj说明说明步步转转移移概概率率使使数数求求证证遍遍历历性性
28、即即找找一一正正整整mm,.1.无无零零元元矩矩阵阵mP2.极限分布转化为了求解方程组极限分布转化为了求解方程组.3.在定理的条件下马氏链的极限分布是平稳分布在定理的条件下马氏链的极限分布是平稳分布.,000000 试说明带有两个反射壁的随机游动是遍历的试说明带有两个反射壁的随机游动是遍历的,并求其极限分布并求其极限分布(平稳分布平稳分布).解解)(的的元元代代表表转转移移概概率率矩矩阵阵的的正正以以 例例12)2(PP 三、应用举例三、应用举例 010003/13/13/10003/13/13/10003/13/13/10001054321P5 4 3 2 1 000000000000)4(
29、4PP.无零元无零元,链是遍历的链是遍历的:),(521满满足足方方程程组组极极限限分分布布 .1,3/13/13/13/13/13/1,/33/1,3/1543214554344323321221.33:54321 由由前前四四个个方方程程解解得得代入最后一个方程代入最后一个方程(归一条件归一条件),得唯一解得唯一解P 010003/13/13/10003/13/13/10003/13/13/10001054321P5 4 3 2 1.11/3,11/143251 所以极限分布为所以极限分布为.)11/1,11/3,11/3,11/3,11/1(这个分布表明这个分布表明经过长时间游动之后经过
30、长时间游动之后,醉汉醉汉 Q 位于点位于点 2(或或 3 或或 4)的概率约为的概率约为 3/11,位于点位于点 1(或或 5)的概率约为的概率约为 1/11.设一马氏链的一步转移概率阵为设一马氏链的一步转移概率阵为,02/102/12/102/1002/102/12/102/10 P试讨论它的遍历性试讨论它的遍历性.解解,2/102/1002/102/12/102/1002/102/1)2(2 PP例例2,)1()(,PPnPn 为为奇奇数数时时当当).2()(,PnPn 为为偶偶数数时时当当.)(lim),4,3,2,1(都不存在都不存在极限极限对任意固定的对任意固定的npjijn 表明表
31、明此链不具遍历性此链不具遍历性.四、小结四、小结 遍历性的概念遍历性的概念若对于所有的若对于所有的间为间为设齐次马氏链的状态空设齐次马氏链的状态空,I存在极限存在极限转移概率转移概率)(,nPIaaijji),()(liminPjijn不依赖于不依赖于 则称此链具有遍历性则称此链具有遍历性.(有限链有限链)遍历性的充分条件遍历性的充分条件,21NaaaI 间间为为设设齐齐次次马马氏氏链链的的状状态态空空,mP如果存在正整数如果存在正整数阵阵是它的一步转移概率矩是它的一步转移概率矩都都有有使使对对任任意意的的,Iaaji,2,1,0)(NjimPij 满足条件满足条件它是方程组它是方程组且有极限分布且有极限分布则此链具有遍历性则此链具有遍历性PN ),(,21.1,01的唯一解的唯一解 Njjj
