最新-第三章马尔科夫连1-PPT精品课件.ppt

1、1第三章第三章 马尔可夫链马尔可夫链v马尔可夫链定义马尔可夫链定义v一步转移概率及多步转移概率一步转移概率及多步转移概率v初始概率及绝对概率初始概率及绝对概率vChapman-Kolmogorov方程方程v马尔可夫链状态分类马尔可夫链状态分类v遍历的马尔可夫链及平稳分布遍历的马尔可夫链及平稳分布2马尔可夫过程马尔可夫过程12(),3,niX t tTITnttt ntT设随机过程其状态空间为对参数集 中任意 个数值 111111()|()|nnnnnnnnP X txX txX txP X txX tx(),X t tT则称过程具有或，并称此过程马尔可夫性无后效性马尔为可夫过程。将来的状态只与

2、当前状态有关，与过去状态无关将来的状态只与当前状态有关，与过去状态无关，即无后效性，即无后效性3马尔可夫链定义马尔可夫链定义定义：设有随机过程定义：设有随机过程Xn,nT，若对于任意的整数，若对于任意的整数nT和任意的和任意的 i0,i1,in+1I，条件概率满足，条件概率满足|,|11110011nnnnnnnniXiXPiXiXiXiXP则称则称Xn,nT为马尔可夫链，简称马氏链为马尔可夫链，简称马氏链时间和状态都离散的马尔可夫过程称为马尔可夫链马尔可夫链4定义定义称条件概率称条件概率为马尔可夫链为马尔可夫链Xn,nT在时刻在时刻n的一步转移概率，其中的一步转移概率，其中i,jI，简称转移

3、概率。，简称转移概率。|)(1iXjXPnpnnij定义定义若对任意的若对任意的i,jI，马尔可夫链，马尔可夫链Xn,nT的转移概率与的转移概率与n无关，则称马尔无关，则称马尔可夫链是齐次马尔可夫链。我们只讨论齐次马氏链。可夫链是齐次马尔可夫链。我们只讨论齐次马氏链。5设设P表示一步转移概率所组成的矩阵，则表示一步转移概率所组成的矩阵，则nnppppppP2122211211称为系统状态的一步转移概率矩阵，它具有如下性质：称为系统状态的一步转移概率矩阵，它具有如下性质：10,ijpi jI、21,ijj Ipi jI、满足上述两个性质的矩阵称为随机矩阵。满足上述两个性质的矩阵称为随机矩阵。6例

4、：一维随机游动一维随机游动。设一醉汉Q(或看作一随机游动的 质点)在直线上的点集I=1,2,3,4,5作随机游动，游动的概率规则是：如果Q现在位于点i(1i=0为齐次马尔科夫链，其转移概率为,1,1iijiib jipr jiaji 例：仓储系统例：仓储系统维修点有一仓库，存储某配件以备维修时使用，该配件每周的消耗量为独立同分布的随机变量，其概率分布为：每周要对该配件进行补充，用Xn表示该仓库在第n周开始未补充配件时的配件个数，补充的原则是如果库存不少于s件，则不补充；如果少于s件，则补充到S件。则随机过程Xn，n=0,1,是一个马尔科夫链。0(),0,1,;1niiinP Dii nDn为第

5、 周的配件消耗量10定义定义称条件概率称条件概率为马尔可夫链为马尔可夫链Xn,nT的的n步转移概率，并称步转移概率，并称1,0,|)(nmIjiiXjXPpmnmnij)()()(nijnpP为马尔可夫链的为马尔可夫链的n步转移矩阵。规定步转移矩阵。规定例题例题设马尔可夫链设马尔可夫链Xn,nT有状态空间有状态空间I=0,1，其一步转移概率矩阵为，其一步转移概率矩阵为11100100ppppP求求 和两步转移概率矩阵和两步转移概率矩阵P(2)0|02mmXXP(0)0,1,ijijpij11定理定理设设Xn,nT为马尔可夫链，则对任意整数为马尔可夫链，则对任意整数n0，0l0非空，则称该集合的

6、最大公约数非空，则称该集合的最大公约数d=d(i)=G.C.Dn:pii(n)0为状态为状态i的周期。的周期。引理引理如如i的周期为的周期为d，则存在正整数，则存在正整数M，对一切，对一切nM，有，有pii(nd)0。如如d1就称就称i为周期的，如为周期的，如d=1就称就称i为非周期的。为非周期的。如果如果i有周期有周期D，则对一切非零的，则对一切非零的n0(mod(D)都有都有pii(n)=0。但这也并不是说对任意但这也并不是说对任意n有有pii(nd)0。例如上图中状态。例如上图中状态1的的d=2，但，但pii(2)=0。23例：状态转移概率图例：状态转移概率图状态的常返性状态的常返性24

7、首中概率首中概率它表示质点由它表示质点由i出发，经出发，经n步首次到达步首次到达j 的概率的概率)|,11,()(iXjXnvjXPfmnmvmnij 表示质点由表示质点由i出发，经有限步终于到达出发，经有限步终于到达j 的概率。的概率。1)(nnijijff定义定义 称状态称状态i为常返的，如为常返的，如fii=1；称状态；称状态i为非常返的，如为非常返的，如fii1。对于常返态对于常返态i，由定义知，由定义知fii(n),n1构成一概率分布构成一概率分布1)(nniiinf表示由表示由i出发再返回出发再返回i的平均返回时间。的平均返回时间。()()()()()10 ,1,nnnknknkk

8、ijijjjijjjkkijnpfpfp 定 理对 任 一 状 态及有25定义定义如如ui，则称常返态，则称常返态i为正常返的；如为正常返的；如ui=，则称常返态，则称常返态i为零常返的。为零常返的。非周期的正常返态称为遍历状态。非周期的正常返态称为遍历状态。常返性的判别常返性的判别()()001 .1nniiiinniiipipf 定理：状态 常返的充要条件为 如 非常返，则含义：当含义：当i常返时，返回常返时，返回i的次数为无限多次；当的次数为无限多次；当i非常返时，返回的次数非常返时，返回的次数只能是有限多次。只能是有限多次。26()lim0.ndiiniiiiiddpdi 定理：设 常

9、返且有周期，则 其中为 的平均返回时间。当，1lim0;12lim0.niinniiniiipip推论：设 常返，则 （）零常返 （）遍历27()00nijijijnpijijijji定义：称自状态 可达状态，并记为，如果存在 使；称状态 与 互通，并记为，如且00,100,1,2111,.222ni iiXIpppiI例：设马氏链的状态空间为，转移概率为分析其遍历性ijjkikijjkik定理：可达和互通关系都具有传递性，即 如果，则 如果，则ijijij定理：如，则 (1)与同为常返或非常返，如为常返，则同为 正常返或零常返 (2)与 有相同的周期28状态空间的分解状态空间的分解CiCk定

10、义：定义：状态空间状态空间I的子集的子集C称为闭集，如果对任意称为闭集，如果对任意 及及 都有都有0ikp定义：定义：闭集闭集C称为不可约的，如果称为不可约的，如果C的状态互通。的状态互通。定义：定义：马尔可夫链称为不可约的，如果其状态空间不可约。马尔可夫链称为不可约的，如果其状态空间不可约。291,2,3,4,50.5000.500.500.500001001000001000nXIP例：设马氏链的状态空间，转移矩阵为 例：无限制随机游动为不可约马尔可夫链，各状态周期为例：无限制随机游动为不可约马尔可夫链，各状态周期为2，当，当p=q时是零常返，时是零常返，pq时是非常返。时是非常返。303

11、）D由全体非常返状态组成，自由全体非常返状态组成，自Cn中的状态不能到达中的状态不能到达D中的状态。中的状态。001000000001000010P=1/31/301/30010000001/20001/2例：分析状态空间的分解定理：状态空间的分解定理：任一马尔可夫链的状态空间任一马尔可夫链的状态空间I，可唯一的分解成有限个或可列个互不相交的，可唯一的分解成有限个或可列个互不相交的子集子集D,C1,C2,之和，使得之和，使得1）每一每一Cn是常返态组成的不可约闭集；是常返态组成的不可约闭集；2）Cn中的状态同类，或全是正常返，或全是零常返。中的状态同类，或全是正常返，或全是零常返。它们有相同的

12、周期且它们有相同的周期且fjk=1,j,kCn。3110()(),0,2,()drrsrrr+d0nddijdCdCGGGrsGGGGddXPp 定理：周期为 的不可约马氏链，其状态空间 可唯一 地分解为 个互不相交的子集之和，即 且使得自中任一状态出发，经一步转移必进入 中（其中）如果只在时刻上考虑，即得一新马氏链，其 其转移矩阵，对此rG新链，每一是非周期不可 约闭集1,261 21 201 31 301 3010000 001000010000001 43 4CP例设马氏链的状态空间为，转移阵为00/0/00/0/01/3001/301/3010000007/1205/120 1/300

13、1/301/3007/1205/1201/3001/301/3(3)P32 的渐进性质与平稳分布的渐进性质与平稳分布()nijp()(),0lim.mnijnmi jpP定理：设有一有限状态的马氏链，若存在一个正整数，使得对状态空间的任何状态有，则其中，是一随机矩阵，且它的各行均相同()0.70.30.40.6nPP例：一马氏链的一步转移概率矩阵为分析的情况33()0,mijpi jI结论：对状态有限的马氏链，当满足（）时，经过一段试验时间后，过程将到达平稳状态，此后过程所处状态的概率不再随时间而变化(2)0.610.390.520.48PPP(4)(2)(2)0.5750.4250.5670

14、.433PPP(8)(4)(4)0.57150.42850.57140.4286PPP34()lim limnnijjnnP Xjp推论2：所取的值与初始分布无关满足定理的矩阵每一行都相同，我们取其中某一行来研究，也用表示1 1),0,2)1 ()iijiii Iii IPpPiI推论：的极限矩阵的每一行满足：即而且该极限矩阵是唯一满足上述关系的矩阵35定义定义称概率分布称概率分布j,jI为马尔可夫链的平稳分布，若它满足为马尔可夫链的平稳分布，若它满足0,1jIjjIiijijp定理定理不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布，且此不可约非周期马尔可夫链是正常返的充要条件是存在平

15、稳分布，且此平稳分布就是极限分布平稳分布就是极限分布 。1,jjI推论推论1：有限状态的不可约非周期马氏链必存在平稳分布。：有限状态的不可约非周期马氏链必存在平稳分布。推论推论2：若所有状态是非常返或零常返的，则不存在平稳分布。若所有状态是非常返或零常返的，则不存在平稳分布。36例题例题若马尔可夫链有三状态，其概率转移矩阵为若马尔可夫链有三状态，其概率转移矩阵为pqpqpq000P问此马尔可夫链是否遍历，若遍历求其平稳分布。问此马尔可夫链是否遍历，若遍历求其平稳分布。例：马尔科夫连的状态空间为例：马尔科夫连的状态空间为1,2,3,4,5,6,7，其转移概率矩阵为，其转移概率矩阵为130.10.

16、10.20.20.400000.50.50000001000P010000000000.50.5000000.500.5000000.50.51limnnp）求每一不可约闭集的平稳分布；2）计算任一马尔可夫链的状态空间任一马尔可夫链的状态空间I，可唯一的分解成有限个或可列个互不相交的，可唯一的分解成有限个或可列个互不相交的子集子集D,C1,C2,之和，使得每一之和，使得每一Cn是常返态组成的不可约闭集；是常返态组成的不可约闭集；D由全体非常返状态组成，自由全体非常返状态组成，自Cn中的状态不能到达中的状态不能到达D中的状态。中的状态。把一步转移概率矩阵行、列按照分解的次序重新排列，不可约闭集在

17、把一步转移概率矩阵行、列按照分解的次序重新排列，不可约闭集在前，前，D在后，则在后，则P矩阵可改写为所谓的标准形：矩阵可改写为所谓的标准形：1212000000000000.000000.nnPPPPRRRQ 吸收马尔科夫链吸收马尔科夫链如果只关心非常返状态与各闭集之间的关系，忽略闭集内部的转移，则可把各闭集内部的状态合并成一个状态吸收态（pii=1），P矩阵可进一步改写为：nIOPRQCnInDvRv nQv v其中：为 为 维单位阵，其各状态集合用 表示，若 中的非常返态个数为，则 为矩阵，为矩阵例如：马尔科夫链的状态空间为例如：马尔科夫链的状态空间为I=1,2,10，其转移概率矩阵为：，

18、其转移概率矩阵为：11000000002212000000003310000000000000100000111000000033300000100003100000000441111000000444401000000001110000000333P 吸收马尔科夫链性质吸收马尔科夫链性质2：Q矩阵中至少有一行的和不为矩阵中至少有一行的和不为1（亚随机矩阵），（亚随机矩阵），Qn收敛到收敛到0矩矩阵（阵（n趋于无限）。趋于无限）。3：定义：定义W=I+Q+Q2+为基本矩阵，其中的每一项为基本矩阵，其中的每一项1：()210,()nnnnnnIPPRIQQQRRQ()()()0 ,mmmijijijmwppQi j，为中的（）元素表示从非常返态表示从非常返态i i到非常返态到非常返态j j，在被吸收之前的平均到达次数。，在被吸收之前的平均到达次数。4：令：令F(n)=fij(n)，其中：，其中：I D，j C，则，则F(n)=Qn-1R。5：令：令F=fij，其中：，其中：I D，j C，则，则F=WR。()0lim0nnIPF6：41作业：4.1 4.6 4.12