1、第10章马尔科夫链(重修班)10.1.1 马尔可夫链的定义马尔可夫链的定义 1、马尔可夫性马尔可夫性(无后效性无后效性)马尔可夫过程是目前发展很快，应用甚广马尔可夫过程是目前发展很快，应用甚广的一种重要随机过程。的一种重要随机过程。0()过过程程或或 系系统统 在在时时刻刻 所所处处的的状状态态为为已已知知的的t0,tt 条条件件下下 过过程程在在时时刻刻所所处处状状态态的的条条件件分分布布与与0t与与过过程程在在时时刻刻 之之前前所所处处的的状状态态无无关关的的特特性性称称为为马尔可夫性马尔可夫性或或无后效性无后效性。2、马尔可夫过程的定义马尔可夫过程的定义具有马尔可夫性的随机过程称为具有马
2、尔可夫性的随机过程称为马尔可夫过程马尔可夫过程。用分布函数表述马尔可夫过程用分布函数表述马尔可夫过程12:(),3,niIX ttTtntttntT 设设随随机机过过程程的的状状态态空空间间如如果果对对时时间间 的的任任意意 个个数数值值有有112211(),(),()|)nnnnX txX tPxX txX tx 11(|),(nnnnnX txP X txxR (),X ttT 这这时时称称过过程程具具马马尔尔可可夫夫性性或或无无后后效效性性。并称此过程并称此过程为为马尔可夫过程马尔可夫过程。3、马尔可夫链的定义马尔可夫链的定义 马尔可夫过程按照其状态和时间参数是连马尔可夫过程按照其状态和
3、时间参数是连续还是离散进行划分续还是离散进行划分,其中其中状态和时间参数都状态和时间参数都是离散是离散的马尔可夫过程称为的马尔可夫过程称为马尔可夫链马尔可夫链，这一，这一节我们着重讨论马尔可夫链。节我们着重讨论马尔可夫链。(),1,2,nXX n n 简简记记为为。1121,2,niTnIaaaaR 马马尔尔可可夫夫链链可可看看作作在在时时间间集集上上对对离离散散状状态态的的过过程程相相继继观观察察的的结结果果。我我们们约约定定链链的的状状态态空空间间为为。10.1.2 马尔可夫过程的概率分布马尔可夫过程的概率分布12,;,0,irttn rtnmTmmt 对对任任意意的的正正整整数数和和有有
4、1122|,rrm njtititimiP XaXaXaXaXa (,|)im njijmP XaXapm mn iaI 其其中中。(,),|ijm njmijipm mnP XammaXana 称称条条件件概概率率为为马马氏氏链链在在时时刻刻 处处于于状状态态 条条件件下下 在在时时刻刻转转转转移移到到状状态态 的的移移概概率率。(,)|ijm njmip m mnP XaXa 转转移移概概率率说明说明:12ijmamnaaa 由由于于链链在在时时刻刻 处处从从任任何何一一个个状状态态 出出发发,到到另另一一时时刻刻必必然然转转移移到到,中中诸诸状状态态中中的的某某一一个个,所所以以mmn
5、iaja(,)(01,ijjipm mna aI 1(,)1(2),ijijja aIpm mn (,),ijmpm mnt 如如果果与与无无关关 则则称称转转移移概概率率具具有有此此时时也也称称马马氏氏平平稳稳性性齐齐次次链链是是的的或或时时齐齐的的。(,),ijijmpm mna a nt 一一般般不不仅仅依依赖赖于于而而且且还还依依赖赖于于。3、平稳性平稳性 下面我们只讨论齐次马氏链，并习惯上常下面我们只讨论齐次马氏链，并习惯上常将将“齐次齐次”两字省略。两字省略。(,)(|)ijm njmip m mnP XaXa 0(0,)(|)ijnjipnP XaXa(0,)(,),ijijpn
6、pm mn若若则则称称马马氏氏链链是是齐齐次次的的。10.1.3 n步步转移转移概率矩阵概率矩阵,(0,)(,)(|)ijijm njminpnpm mnP XaXa 对对齐齐次次马马氏氏链链步步转转移移概概率率由由n步转移概率组成的矩阵步转移概率组成的矩阵(,)(,)ijP m mnpm mn称为马氏链的称为马氏链的n步步转移概率矩阵转移概率矩阵。它是随机矩阵。它是随机矩阵。此矩阵的此矩阵的每一行元素之和等于每一行元素之和等于1。这个矩阵具有以下两个性质：这个矩阵具有以下两个性质：(1)0,ijijpa aI (2)1jijiaIpaI 一步转移概率矩阵一步转移概率矩阵1mX 的的状状态态的
7、状态的状态mX12iaaa 12jaaa111212122212jjiiijppppppppp(1)P 记为记为P(1)P1(,1)(|ijijmjmippm mP XaXa 。例例10.1 一维随机游动一维随机游动0,1,2,3,4I 一一随随机机游游动动的的质质点点在在如如图图所所示示直直线线的的点点集集上上作作随随机机游游动动。01234游动的概率规则游动的概率规则 如果如果Q现在位于点现在位于点1,2或者或者3时时,则下一时刻则下一时刻都以都以1/3的概率向左移动一格或以的概率向左移动一格或以2/3的概率向的概率向右移动一格。右移动一格。如果如果Q现在位于现在位于0这点上这点上,则下一
8、时刻就以概则下一时刻就以概率率1移动到移动到1，当，当Q到达到达4点时，它以概率点时，它以概率1停留在停留在该点上（该点上（0称为反射壁，称为反射壁，4称为吸收壁）。称为吸收壁）。01234上面这种游动称为带有上面这种游动称为带有1个个反射壁反射壁的随机游动。的随机游动。,0,1,2,nnXnQXn 以以表表示示时时刻刻 时时 的的位位置置,则则是是一一随随机机过过程程。状态空间就是状态空间就是I=0,1,2,3,4。1,nnnXi iIXXin 当当为为已已知知时时所所处处的的状状态态分分布布只只与与有有关关 而而与与时时刻刻 以以前前的的状状态态无无关关。所以它是一个马氏链所以它是一个马氏
9、链,且是齐次的且是齐次的。游动的概率规则游动的概率规则 一步转移概率矩阵一步转移概率矩阵012340 1 2 3 4 0010001 1/302/300201/302/303001/302/3400001P 说明说明:如果把点如果把点 0 改为改为吸收壁吸收壁,4改为反射壁相应链的改为反射壁相应链的转移概率矩阵只须把转移概率矩阵只须把P 中第中第1行改为行改为(1,0,0,0,0)。改变游动的概率规则改变游动的概率规则,就可得到不同方式就可得到不同方式的的随机游动和相应的马氏链。随机游动和相应的马氏链。一步转移概率矩阵一步转移概率矩阵0100001 1/302/300201/302/30300
10、1/302/3400010P 0 1 2 3 4 设一个单位时间传输一级设一个单位时间传输一级,设每一级的传真率设每一级的传真率为为 p,误码率为误码率为 q=1 p。只传输数字只传输数字0和和1的串联系统的串联系统(0 1)传输系统传输系统)0X11X2X1 nXnnX2如图如图:0X 是是第第一一级级的的输输入入(1)nXnn 是是第第 级级的的输输出出分析分析:,0,1,2,nXn 是是一一随随机机过过程程0,1,I 状状态态空空间间例例10.21,nnnXi iIXXin 且且当当为为已已知知时时所所处处的的状状态态分分布布只只与与有有关关 与与时时刻刻 以以前前所所处处的的状状态态无
11、无关关。所以它是一个马氏链所以它是一个马氏链,且是齐次的且是齐次的。一步转移概率矩阵一步转移概率矩阵pqqp01P 0110,11,nnnnnqnppqXnXi iIXXin 若若把把例例中中两两个个状状态态看看作作独独立立的的n n重重伯伯努努利利试试验验的的结结果果即即状状态态 看看作作第第 次次试试验验失失败败，概概率率为为状状态态 看看作作第第 次次成成功功，概概率率为为，且且表表示示第第 次次试试验验结结果果。且且当当为为已已知知时时所所处处的的状状态态分分布布只只与与有有关关 与与时时刻刻 以以前前所所处处的的状状态态无无关关。一步转移概率矩阵一步转移概率矩阵pqqp01P 011
12、100,11ijnnnpjpXj XiP Xjiqj 10.2 10.2 多步转移概率的确定多步转移概率的确定 一、一、C-K 方程方程二、多步转移概率的确定二、多步转移概率的确定这就是有名的切普曼柯尔莫哥洛夫方程。这就是有名的切普曼柯尔莫哥洛夫方程。简称简称 C K 方程方程11,0,()()(),1,2,nijikkjkpuvpu pXtvinujTvT 设设是是马马氏氏链链 则则对对于于任任意意的的整整数数和和0.10.1有有定定理理1 1。()()()P uvP u P v 或或。说明说明C K 方程基于下列事实方程基于下列事实:,()ijjsauvaX suva “从从时时刻刻所所处
13、处的的状状态态出出发发 经经时时段段转转移移到到状状态态”。10.2.1切普曼柯尔莫哥洛夫切普曼柯尔莫哥洛夫方程方程这一事件可分解成这一事件可分解成:(),(1,2),ikkjX sauakava “从从出出发发 先先经经时时段段 转转移移到到中中间间状状态态在在从从经经时时段段 转转移移到到状状态态”等等事事件件的的和和事事件件。tosus vus iakaja如下图所示如下图所示:10.2.2 多步转移概率的确定多步转移概率的确定利用利用 C K 方程我们容易确定方程我们容易确定 n 步转移概率。步转移概率。得递推关系得递推关系:()()(),1,1,P uvP u P vuvn 在在中中
14、 令令()(1)(1)P nPP n 2(2)(1)(1)(1)PPPP()(1),nP nnP 当当 为为任任意意整整数数时时3(3)(1)(2)(1)PPPP010 1/21/2(1)1 1/32/3P 又又由由于于2010 5/127/12(2)(1)1 7/1811/18PP51,53故故在在 月月 日日为为晴晴天天的的条条件件下下月月 日日为为晴晴天天的的概概率率为为00(2)5/120.4167p,00,1,2nXn 是是具具有有三三个个状状态态的的齐齐次次马马氏氏链链 0 1 2 03/41/40 11/41/21/4,203/41/4P 0(0)1/3,0,1,2ipP Xii
15、 初初始始分分布布。一步转移概率为一步转移概率为022:(1)0,1;(2)1P XXP X 试试求求。例例10.3解解先求出二步转移概率矩阵先求出二步转移概率矩阵2 0 1 205/85/161/16(2)(1)1 5/161/23/162 3/169/161/4PP 于是于是:02(1)0,1P XX0200 1|0P XP XX 001(0)(2)PP 153 16548。12(2)(2)1pP X 001111221(0)(2)(0)(2)(0)(2)pppppp 151119316323161124。02020002011|101|21|20PP XPXPXXPPXXXXX 0202
16、020,11,12,1P XXP XXP XX 0 1 205/85/16 1/16(2)1 5/161/23/162 3/16 9/161/4P (0)1/3ip 初初始始分分布布注：注：0 10 1,0,111ppPp qqq 。n步转移概率矩阵步转移概率矩阵为为00011011 0 1()()0()(1)()()1npnpnP nPpnpn 1,2,n 。1(1),nqppppqpq qppqqq 对于只有两个状态的马氏链对于只有两个状态的马氏链,一步转移概一步转移概率率矩阵一般可表示为矩阵一般可表示为:10.3 马氏链的有限维分布马氏链的有限维分布0,(0)njjXtTpP Xa定定义
17、义1010设设是是马马氏氏链链 称称为为马马.2.2初初氏氏链链的的始始概概率率。(0),(0)jjjpaIp 称称马马氏氏链链的的初初始始分分布布,简简记记为为。()()jnjjp nP XaaI 称称为为马马氏氏链链的的绝绝对对概概率率。(),()jjjp naIp n 称称为为马马氏氏链链的的绝绝对对分分布布。简简记记为为。1()1jjp n 特特点点。向量表示形式向量表示形式 12()(),(),(),jp np np np n 向量表示形式向量表示形式 12(0)(0),(0),(0),jpppp 10.3.1 初始概率与绝对概率初始概率与绝对概率2.绝对概率与初始概率的关系绝对概率
18、与初始概率的关系()jnjp nP Xa 0,iinjaIP XaXa 00|iijaniIPPaXXXaa ()(0()ijnjiijaIpp nP Xpna 0njaia表明绝对分布可由初始分布和表明绝对分布可由初始分布和n步转移概率矩阵确定。步转移概率矩阵确定。()(,)(|)()ijijm njmijnpnpm mnP XaXaaI 步步转转移移概概率率绝对分布与初始分布的关系可表示为绝对分布与初始分布的关系可表示为()(0)()p npP n 10.3.2 马氏链的有限维分布律马氏链的有限维分布律112111,0,1,(0),nnninniiniiiiiiaiIiP XaXapXna
19、aaIppn 设设是是齐齐次次马马氏氏链链 则则对对于于任任意意的的和和有有定定理理10.310.30100 11 21100 11 210110,(0),nnnnnniiniii ii iiiiniii ii iiiP XaXaXappppP XaXaXappp (1 1)(2 2)推论推论10.2，由定理，由定理10.3不难得到不难得到10.4 遍历性遍历性 10.4.1 遍历性的概念遍历性的概念10.4.2(有限链有限链)遍历性的充分条件遍历性的充分条件定义定义,()ijijIa aIP n 设设齐齐次次马马氏氏链链的的状状态态空空间间为为若若对对于于所所有有的的转转移移概概率率存存在在
20、极极限限lim()()ijjnniP 不不依依赖赖于于1212()12()jjnnjP nP或或则称此链具有则称此链具有遍历性遍历性。121,(,)jj 若若则则称称为为链链的的极极限限分分布布。10.4.2有限马氏链遍历性的充分条件有限马氏链遍历性的充分条件 研究遍历性问题的中心是要确定在什么样研究遍历性问题的中心是要确定在什么样的条件下马氏链才具有遍历性，以及如何求得的条件下马氏链才具有遍历性，以及如何求得 j ，这个问题已彻底解决。，这个问题已彻底解决。12,nNijXnTIa aaPma aI 设设为为齐齐次次有有限限马马氏氏链链,其其状状态态空空间间为为是是它它的的一一步步转转移移概
21、概率率矩矩阵阵 如如果果存存在在正正整整数数使使对对任任意意的的定定理理1 10 0.4 4都都有有()0,1,2,ijpmi jN 1211,(,),1,2,0,1NNjijiNjjjjpjNP 则则此此链链具具有有且且有有极极限限分分布布它它是是方方程程组组或或即即满满足足条条件件遍遍历历性性的的唯唯一一解解。定理给出了判别有限马氏链具有遍历性的定理给出了判别有限马氏链具有遍历性的一个简单充分条件，以及求一个简单充分条件，以及求 j 的方法。的方法。2、求求极限分布极限分布 j可转可转化为求解方程组。化为求解方程组。1,()()ijmmP mpm、求求证证遍遍历历性性即即找找一一正正整整数
22、数使使步步转转移移概概率率 矩矩阵阵中中无无零零元元。设一马氏链的一步转移概率矩阵为设一马氏链的一步转移概率矩阵为试讨论它的遍历性试讨论它的遍历性,并求出其极限分布。并求出其极限分布。例例10.70.90.1(1)0.10.9P(1)0,ijp 由由于于所以此链是遍历链。所以此链是遍历链。lim(),(1,2)ijjnpnj解解设其极限分布为设其极限分布为01(,)可列出如下方程：可列出如下方程：0101(,),1(0)jjjP 则则极极限限分分布布是是满满足足方方程程组组的的唯唯一一解解。0101010.90.1(,)(,)0.10.91 001101010.90.10.10.91 可得解为
23、：可得解为：即即001101010.90.10.10.91 0101010.10.100.90.901 0112011 1(,)(,)2 2 且且有有极极限限分分布布。例例10.8 例例10.1的一步转移概率矩阵为的一步转移概率矩阵为证明此随机游动具有遍历性，并求其极限分布。证明此随机游动具有遍历性，并求其极限分布。0010001 1/302/300201/302/303001/302/3400001P 0 1 2 3 4()以以+代代表表转转移移概概率率矩矩阵阵的的正正的的元元解解2(2)(1)PP 0000000000000000000000000000 000000 4000000(4)
24、(1)000000PP 。无零元无零元所以此随机游动具有遍历性。所以此随机游动具有遍历性。12551,1(0)(,):jjjP 极极限限分分布布满满足足方方程程组组1221233234434554123451/3,1/33/,1/31/31/31/31/31/3,1 。12345:33 由由前前四四个个方方程程解解得得。代入最后一个方程代入最后一个方程(归一条件归一条件),得唯一解。得唯一解。1523413,1111 。所以极限分布为所以极限分布为13331(,)11 11 11 11 11。这个这个分布表明分布表明 经过长时间游动之后经过长时间游动之后,质点质点 Q 位于点位于点 2(或或
25、3 或或 4)的概率约为的概率约为 3/11,位于点位于点 1(或或 5)的概率约为的概率约为 1/11。设一马氏链的一步转移概率阵为设一马氏链的一步转移概率阵为01/201/21/201/20(1)01/201/21/201/20P 试讨论它的遍历性。试讨论它的遍历性。解解21/201/2001/201/2(2)(1)1/201/2001/201/2PP例例10.9301/201/21/201/20(3)(1)(1)01/201/21/201/20PPP,()(1)nP nP 当当为为奇奇数数时时,()(2)nP nP 当当为为偶偶数数时时。(1,2,3,4),lim()ijnjpn 对对任任意意固固定定的的极极限限都都不不存存在在。表明表明此链不具遍历性。此链不具遍历性。
