《概率论》第10章--马尔可夫链课件.ppt

1、第十章第十章 马尔可夫链马尔可夫链第一节第一节 马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率第二节第二节 多步转移概率的确定多步转移概率的确定第三节第三节 马氏链的有限维分布马氏链的有限维分布第四节第四节 遍历性遍历性第一节第一节马尔可夫链的概念及马尔可夫链的概念及转移概率转移概率,2,1,0.,21 TaaI并记并记,2,1,0),(nnXXn马尔可夫过程的定义马尔可夫过程的定义、112111111(),(2)()|(),()()|()(),.nnnnnnnnnX ttTntttnP X txX txX txP X txX txX ttT 定定义义、设设为为一一随随机机过过程程，若若

2、对对任任意意个个时时间间有有：则则称称具具有有马马尔尔可可夫夫性性或或无无后后效效性性，并并称称其其为为马马尔尔可可夫夫过过程程.简简称称马马氏氏链链可可夫夫链链，马马尔尔可可夫夫过过程程称称为为马马尔尔时时间间和和状状态态都都是是离离散散的的.本本章章只只讨讨论论马马氏氏链链,|2211imitititjnmaXaXaXaXaXPrr 有有|imjnmaXaXP ,;0,TnmmtmtNrnir 和和对对(,)|ijm njmipm mnP XaXa 记记下面我们只讨论齐次马氏链，并习惯上常将下面我们只讨论齐次马氏链，并习惯上常将“齐次齐次”两字省略两字省略。马马氏氏链链的的转转移移概概率率

3、、2,2,1,0,21 TaaI,2,1,0),(nnXXn(,).ijijpm mnmamna 称称为为马马氏氏链链在在时时刻刻处处于于状状态态条条件件下下，在在时时刻刻转转移移到到状状态态的的转转移移概概率率(,).ijpm mnm 如如果果与与无无关关，则则称称马马氏氏链链为为齐齐次次的的或或时时齐齐的的，并并说说转转移移概概率率是是平平稳稳的的()().ijP npnn 称称为为步步转转移移概概率率矩矩阵阵111212122212()()()()()()()()()()()NNijNNNNpnpnpnpnpnpnP npn pnpnpnNaaa21Naaa21矩矩阵阵齐齐次次马马氏氏链

4、链的的转转移移概概率率、3()(,)|ijijm njmipnpm mnP XaXa 对对齐齐次次马马氏氏链链，记记有有以以下下两两个个性性质质：)(nP(1)()0,ijijpna aI1(2)()1ijjpn 11(1)|ijijmjminppP XaXa 当当时时，记记 NNNNNNppp ppppppPP212222111211)1(Naaa21Naaa21.)1(率率矩矩阵阵为为马马氏氏链链的的一一步步转转移移概概称称PP 这这一一点点上上。或或移移动动到到就就以以概概率率，则则下下一一时时刻刻或或现现在在位位于于点点的的概概率率停停在在原原处处；如如果果一一格格，或或以以的的概概率

5、率向向左左或或向向右右移移动动则则下下一一时时刻刻各各以以现现在在位位于于点点是是：如如果果发发生生游游动动。游游动动的的规规则则等等时时刻刻秒秒秒秒、仅仅在在上上作作随随机机游游动动，并并且且仅仅在在如如图图所所示示直直线线的的点点集集设设一一醉醉汉汉一一维维随随机机游游动动、例例题题)4(21)5(13/13/1),51(215,4,3,2,1)(1QiiQIQ 12345过过程程，是是一一随随机机则则的的位位置置，时时表表示示时时刻刻若若以以,2,1,0,nXQnXnn 而且当而且当 时，时，等以后的行为只与等以后的行为只与 有关，而与质点以前是如何到有关，而与质点以前是如何到 是完全无

6、关的，所以，它是一是完全无关的，所以，它是一个马氏链，且为齐次马氏链。个马氏链，且为齐次马氏链。iXn,21 nnXXiXn i其状态空间为：其状态空间为：5,4,3,2,1 I .2,0,4,52,1,151,1,1,3/1|1ijjijiiiiijiXjXPpnnij或或一一步步转转移移概概率率为为：010003/13/13/10003/13/13/10003/13/13/100010P一一步步转转移移概概率率矩矩阵阵为为：5432154321称其为具有称其为具有两个反射壁的随机游动两个反射壁的随机游动iiri1 iip1 iiq1 nn01iir1 iip1 iiq若令若令 表示质点在时

7、刻表示质点在时刻 的位置，那末，的位置，那末，是是一个随机过程，而且当一个随机过程，而且当 时，时，等以后的行为等以后的行为只与只与 有关，而与质点以前是如何到有关，而与质点以前是如何到 是完全无关的，所是完全无关的，所以，它是一个马氏链。以，它是一个马氏链。nXn,2,1,0,nXniXn,21 nnXXiXn i其状态空间为：其状态空间为：,2,1,0 I例：例：一维随机游动。一维随机游动。考虑在直线上作随机游动的质点，且只在非负整数上作随机考虑在直线上作随机游动的质点，且只在非负整数上作随机游动。当质点在时刻游动。当质点在时刻 时处在位置时处在位置 ，在，在 时刻转移到时刻转移到 的概率

8、为的概率为 ，转移到，转移到 的概率为的概率为 ，不动的概率为，不动的概率为 ，而处在别的位置的概率为而处在别的位置的概率为 0。n)0(i1 n1 iip1 iiqir它的一步转移矩阵为：它的一步转移矩阵为：0000000210)1(22211100iiiprqprqprqpriP0123 这里这里,0,0,0 iiirqp并且并且,2,1,1 irqpiii1,0,00000 prrp 由于它的转移概率与起点由于它的转移概率与起点 无关，所以它还是无关，所以它还是齐次马氏链齐次马氏链。m 如果如果 称为带一个称为带一个吸收壁的随机游动吸收壁的随机游动，质点一，质点一旦到达状态旦到达状态 0

9、 后就永远停留在后就永远停留在 0 这个状态上，这样的状态称为这个状态上，这样的状态称为吸收状态吸收状态。1,000 rp 如果如果 称为带一个称为带一个反射壁的随机游反射壁的随机游动动，质点一旦到达状态，质点一旦到达状态 0 后下一步它以概率后下一步它以概率 向右移一格。向右移一格。1,0,00000 prrp0p0101 如果状态空间如果状态空间 是有限的，且状态是有限的，且状态 0 与状态与状态 N 都为吸收状态，即都为吸收状态，即称为具有称为具有两个吸收壁的随机游动两个吸收壁的随机游动.,2,1,0NI 0,1,0,100 NNqrpr01Niir1 iip1 iiq第二节第二节多步转

10、移概率的确定多步转移概率的确定定理定理:设设 为齐次马氏链为齐次马氏链，则对任意的则对任意的 有有,2,1,0),(nnXvu,1()()(),1,2,.ijikkjkpuvpu pvi j 或或 )()()(vPuPvuP 证明：利用全概率公式及马尔可夫性，有证明：利用全概率公式及马尔可夫性，有()()|()ijjipuvP X suvaX sa 111(),()|()()|()()|(),()()()kjikkikjkiikkjkPX sua X su vaX saP X suaX saP X su vaX sua X sap u p v sus vus iakaja这就是有名的切普曼柯尔

11、莫哥洛夫方程这就是有名的切普曼柯尔莫哥洛夫方程，简，简称称为为 方程方程。KC 1()()(),1,2,.ijikkjkpuvpu pvi j 或或 )()()(vPuPvuP 2)1()1()1()2(PPPP 3)1()2()1()3(PPPP nnPPnP )1()(有有由由 )()()(vPuPvuP 可见齐次马氏链，它的多步转移概率完全由它的一可见齐次马氏链，它的多步转移概率完全由它的一步转移概率所决定。因此，在马氏链中，一步转移概步转移概率所决定。因此，在马氏链中，一步转移概率是最基本的率是最基本的。第三节第三节马氏链的有限维分布马氏链的有限维分布定义：设定义：设 为马氏链为马氏链

12、，,2,1,0,)(nnX.,2,1,)0(0 jIaaXPpjjj记记称称它它为马氏链的初始分布为马氏链的初始分布 。IaaXPnpjjnj )(记记 100|()(iijnijnjaXaXPaXPaXPnp1()(0)(),1,2,.jiijip nppnj 构构成成一一个个划划分分）（由由全全概概率率公公式式得得：,2,1,0 iaXi0njaia一一维维分布可用向量形式表示为：分布可用向量形式表示为：初始分布初始分布与一与一维维分布的关系可表示为：分布的关系可表示为：)()0()(nPpnp 表明一表明一维维分布可由初始分布和分布可由初始分布和 n 步转移概率矩阵确定。步转移概率矩阵确

13、定。12()(),(),(),jp np np np n 01112211 2111 2101212111211,00,()()()(0)()()()kkkkkkkinkiiinininiii iiikkiiii iiikkaIXnnnnnaaaIP XaXaXapnpnnpnnppnpnnpnn 定定理理：设设为为马马氏氏链链，则则对对任任意意时时刻刻和和任任意意状状态态，有有 1122000 11 2110211,|()()().kkkkninininii ii iiikkP XaXaXaXapnnpnnpnn 和和 定理说明，马尔可夫链的有限维分布完全由它的初始定理说明，马尔可夫链的有限

14、维分布完全由它的初始分布分布和和转移概率决定转移概率决定。112211221133221111 2111 211121112111,=|()()()(0)()()().kkkkkkkkkkninininininininininiii iiikkiiii iiikkinP XaXaXaP XaP XaXaP XaXaP XaXapnpnnpnnppnpnnpnnP Xa 证证明明：而而 1220000110000 11 2100 11 21010211010211,|,()()()()()()()().kkkkkkkkinininininininiii ii iiikkii ii iiikkXa

15、XaXaP XaXaXaP Xapnpnnpnnpnnpnpnnpnnpnn 4/116/916/316/32/116/516/116/58/5)1()2(2PP 4/14/304/12/14/104/14/32,1,00,PnXn一步转移概率矩阵为一步转移概率矩阵为的齐次马氏链，的齐次马氏链，是具有三个状态是具有三个状态例题：设例题：设2,1,0,3/1)0(0 iiXPpi已知初始分布为：已知初始分布为：.1)2(;1,0)1(220 XPXXP试求：试求：矩矩阵阵解解：先先求求二二步步转转移移概概率率210210210210所以有所以有0|101,0)1(02020 XXPXPXXP).

16、2(1)2(12pXP 001155(0)(2)31648pp001111221(0)(2)(0)(2)(0)(2)pppppp2411)16921165(31 1340,2,1;P XXX练练习习：求求13411310,2,1=316464P XXX答答案案：例：某计算机房的一台计算机经常出现故障，研究者每隔例：某计算机房的一台计算机经常出现故障，研究者每隔15分钟分钟观察一次计算机的运行状态，收集了观察一次计算机的运行状态，收集了24小时的数据（共作小时的数据（共作97次观次观察）。用察）。用1表示正常状态，用表示正常状态，用0表示不正常状态，所得数据序列如表示不正常状态，所得数据序列如下

17、：下：1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111设设 为第为第 n 个时段的计算机状态，可以认为它是一个齐次马氏个时段的计算机状态，可以认为它是一个齐次马氏链，状态空间为链，状态空间为nX1,0 I由于由于96次状态转移的情况是：次状态转移的情况是：52,11 次次8,00 次次18,10 次次18,01 次次 因此，一步转移概率可用频率近似地表示为：因此，一步转移概率可用频率近似地表示为：13418880|0100 nnXXPp1391881

18、80|1101 nnXXPp35952881|0110 nnXXPp3526528521|1111 nnXXPp续例：若计算机在某一时段（续例：若计算机在某一时段（15分钟）的状态为分钟）的状态为 0，问从此时段，问从此时段起此计算机能连续正常工作起此计算机能连续正常工作 一小时一小时（4个时段）的概率为多少？个时段）的概率为多少？解：由题意，解：由题意，0|1,1,1,104321 XXXXXP01,1,1,1,0043210 XPXXXXXP0/1|11|11|10|100342312010 XPXXPXXPXXPXXPXP1|11|11|10|134231201 XXPXXPXXPXXP

19、01111111(1)(1)(1)(1)926 26 2613 35 35 35pppp 284.0 9.01.01.09.0)1(PP一一步步转转移移概概率率矩矩阵阵为为：754.0244.0244.0754.0)2()3(82.018.018.082.0)2(2PPPPP概概率率矩矩阵阵分分别别为为：所所以以，两两步步、三三步步转转移移的的概概率率是是多多少少？输输出出两两步步都都传传的的条条件件下下，那那么么又又接接连连、在在某某步步传传输输出出数数字字的的概概率率是是多多少少？经经三三步步传传输输输输出出、数数字字。传传输输错错误误的的概概率率为为的的概概率率为为步步骤骤。设设每每步步

20、传传输输正正确确的的传传输输需需经经若若干干的的通通信信系系统统，每每个个数数字字和和例例题题：传传输输数数字字11)2(11)1(10/1,10/9101,0,2,1,0,InXnXnn态态空空间间为为：一一个个齐齐次次马马氏氏链链，其其状状是是则则步步传传输输出出的的数数字字，表表示示第第解解：以以11(1).(3)0.754p 110.754所所以以数数字字经经三三步步传传输输输输出出 的的概概率率是是1|1,1).2(21 nnnXXXP1|11|11,1|11|1121121 nnnnnnnnnXXPXXPXXXPXXP81.09.021111 pp 754.0244.0244.07

21、54.0)2()3(82.018.018.082.0)2(2PPPPP续例：续例：（3）设初始分布设初始分布,1)0(01 XPp,10)0(00 XPp 又已知系统经又已知系统经 n 级传输后输出为级传输后输出为1，问原发数字也是，问原发数字也是1的概率为的概率为多少？多少？先求出先求出n步转移概率矩阵步转移概率矩阵 nPnP)(由于由于 109101101109)1(P由特征方程由特征方程0 EP 54,121 可得到两个相异的特征值可得到两个相异的特征值:由线性代数知识可将由线性代数知识可将 P 表示成表示成对角阵对角阵 54001的的相似矩阵相似矩阵。具体做法是具体做法是:求出求出 对

22、应的对应的特征向量特征向量21,21211e 21212e令：令：21212121,21eeH则则1 HHP 于是于是11)(HHHHPnnn nnnnnP542121542121542121542121)(根据贝叶斯公式，当已知系统经根据贝叶斯公式，当已知系统经 n 级传输后输出为级传输后输出为1，原数字，原数字也是也是1的概率为的概率为1/10 nXXP11/1100 nnXPXXPXP111001111(0)()(0)()(0)()ppnppnppn nn 54)12(154 第四节第四节遍历性遍历性jijnjjinnPiaaTnX )(lim,，使使得得的的常常数数存存在在不不依依赖赖

23、于于及及切切状状态态为为齐齐次次马马氏氏链链，若若对对一一定定义义：设设、遍历性的概念、遍历性的概念1 jjjnnPnP 212121)(或或性性。则则称称此此马马氏氏链链具具有有遍遍历历。为为此此马马氏氏链链的的极极限限分分布布则则称称又又若若),(,121 jj分分条条件件有有限限马马氏氏链链遍遍历历性性的的充充.21212,()0,1,2,(,)nNijijNXnTIa aama apmi jN 定定理理：设设为为有有限限马马氏氏链链，状状态态空空间间为为，若若存存在在正正整整数数使使得得对对一一切切状状态态有有则则此此链链是是遍遍历历的的，且且有有极极限限分分布布111,2,:0,1N

24、jiijiNjjjPpjN 它它是是方方程程组组或或满满足足条条件件的的唯唯一一解解。则称则称 为平稳分布，称为平稳分布，称 具有平稳性具有平稳性。jvV nX定义：定义：对于齐次马氏链对于齐次马氏链 如果存在概率分布如果存在概率分布,TnXn,21vvV 满足满足：VPV 0,2,1iijijjpvv即即定义中平稳性的直观含义是过程在任何时刻处于状态定义中平稳性的直观含义是过程在任何时刻处于状态 的概率的概率都相等。都相等。ja在定理的条件下，马氏链的极限分布就是平稳分布，且是唯一的在定理的条件下，马氏链的极限分布就是平稳分布，且是唯一的。即，若用即，若用 作为链的初始分布，即作为链的初始分

25、布，即 ，则链在任一时刻，则链在任一时刻的绝对分布永远与的绝对分布永远与 一致。一致。)0(p 事实上由事实上由)()0()(nPpnp 和和P 有有)()0()(nPpnp PPPnn1例：考虑直线上带反射壁的随机游动例：考虑直线上带反射壁的随机游动,如果质点只能取如果质点只能取1 1、2 2、3 3三个点三个点,一步转移概率矩阵为一步转移概率矩阵为:pqpqpqP000)1(其中其中1,0,0 qpqp试说明此链是遍历的，并求出极限分布。试说明此链是遍历的，并求出极限分布。解：解：计算二步转移概率矩阵计算二步转移概率矩阵 22222222)1()2(ppqpqqppqqppqpqqPP可见

26、当可见当,对任意的对任意的 有有2 n3,2,1,ji0)2(ijp由定理可知由定理可知,此链具有遍历性此链具有遍历性,下面求极限分布下面求极限分布列出方程式列出方程式：由此解得：由此解得：12 qp 123 qp1121 qpqp 1211 qpqp 1221 qpqpqp 12231 qpqpqp 1321323312211 ppqpqq即即 1)1(321 P例：设一马氏链的一步转移概率矩阵为例：设一马氏链的一步转移概率矩阵为讨论它的遍历性。讨论它的遍历性。02/102/12/102/1002/102/12/102/10)1(P解：先计算二步转移矩阵解：先计算二步转移矩阵 2/102/1002/102/12/102/1002/102/1)2(2PP进一步可验证：进一步可验证：这表明对任一固定的这表明对任一固定的 j，极限，极限 都不存在，都不存在，)(limnpijn 当当 n 为奇数时，为奇数时，；PPnP )1()(而当而当 n 为偶数时，为偶数时，)2()(PnP 按定义，此链不具有遍历性。按定义，此链不具有遍历性。