马尔可夫过程PPT课件

《马尔可夫过程PPT课件》由会员分享，可在线阅读，更多相关《马尔可夫过程PPT课件（83页珍藏版）》请在装配图网上搜索。

1、第5章 马尔可夫过程马春光马春光http:/哈尔滨工程大学哈尔滨工程大学5 马尔可夫过程5.1 5.1 马尔可夫过程的定义马尔可夫过程的定义马尔可夫过程的定义马尔可夫过程的定义5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布5.3 5.3 齐次马尔可夫链的分类齐次马尔可夫链的分类齐次马尔可夫链的分类齐次马尔可夫链的分类5.4 5.4 转移概率的稳定性能转移概率的稳定性能转移概率的稳定性能转移概率的稳定性能 5 马尔可夫过程5.1 5.1 马尔可夫过程的定义马尔可夫过程的定义马尔可夫过程的定义马尔可夫过程的定

2、义5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布5.3 5.3 齐次马尔可夫链的分类齐次马尔可夫链的分类齐次马尔可夫链的分类齐次马尔可夫链的分类5.4 5.4 转移概率的稳定性能转移概率的稳定性能转移概率的稳定性能转移概率的稳定性能 5.1 马尔可夫过程的定义马尔可夫过程是马尔可夫过程是无后效性无后效性无后效性无后效性的随机过程的随机过程马尔可夫性马尔可夫性马尔可夫性马尔可夫性 定义定义定义定义 设设 X X(t t),),t t T T 是一个随机过程，如果是一个随机过程，如果 X X(t t),),t

3、 t T T 在在 t t0 0 时刻所处的状态为已知时，它在时刻时刻所处的状态为已知时，它在时刻 tttt0 0 所处状态所处状态的条件分布与其在的条件分布与其在 t t0 0 之前所处的状态无关之前所处的状态无关.通俗地说，就通俗地说，就是知道过程是知道过程“现在现在”的条件下，其的条件下，其“将来将来”的条件分布的条件分布不依赖于不依赖于“过去过去”，则称，则称 X X(t t),),t t T T 具有具有马尔可夫马尔可夫马尔可夫马尔可夫（MarkovMarkov）性）性）性）性。马尔可夫过程马尔可夫过程 定义定义定义定义 设设 X X(t t),),t t T T 的状态空间为的状态

4、空间为S S，如果，如果 在条件在条件 X X(t ti i)=)=x xi i,x xi iS S,i=i=1,2,1,2,n-n-1 1下下,X X(t tn n)的条件分布函数恰好等于在条件的条件分布函数恰好等于在条件 X X(t tn-n-1 1)=)=x xn-1n-1下的条件分布函数，即下的条件分布函数，即则称则称 X X(t t),),t t T T 为为马尔可夫过程马尔可夫过程马尔可夫过程马尔可夫过程。5.1 马尔可夫过程的定义马尔可夫链马尔可夫链 定义定义定义定义 参数集和状态空间都是离散的马尔可夫过程称为参数集和状态空间都是离散的马尔可夫过程称为马尔科夫链马尔科夫链马尔科夫

5、链马尔科夫链 .为了讨论简单起见，在以后取马尔科夫链的状态空间为为了讨论简单起见，在以后取马尔科夫链的状态空间为有限或可列无限，此时马尔可夫性可表示为有限或可列无限，此时马尔可夫性可表示为5.1 马尔可夫过程的定义 特别地，取特别地，取T=T=0,1,2,0,1,2,的马尔可夫链常记为的马尔可夫链常记为 X X(n n),),n n 00或或 X Xn n,n n 00，此时马尔可夫性为，此时马尔可夫性为n n1,1,i i0 0 ,i,i1 1,i,in nS S,P P(X X(n n)=i in n|X|X(0)(0)=i=i0 0 ,X X(1)(1)=i=i1 1,X X(n n-1

6、)-1)=i=in n-1-1)=P P(X X(n n)=i in n|X|X(n n-1)-1)=i=in n-1-1)（）（）或或 P P(X Xn n=i in n|X X0 0=i=i0 0 ,X X1 1=i=i1 1,X Xn n-1-1=i=in n-1-1)=)=P P(X Xn n=i in n|X Xn n-1-1=i=in n-1-1)（）（）容易证明，对于马尔可夫链容易证明，对于马尔可夫链 X X(n n),),n n 00，（）式等价于（）式或（）式。（）式等价于（）式或（）式。5.1 马尔可夫过程的定义5 马尔可夫过程5.1 5.1 马尔可夫过程的定义马尔可夫过程

7、的定义马尔可夫过程的定义马尔可夫过程的定义5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布5.3 5.3 齐次马尔可夫链的分类齐次马尔可夫链的分类齐次马尔可夫链的分类齐次马尔可夫链的分类5.4 5.4 转移概率的稳定性能转移概率的稳定性能转移概率的稳定性能转移概率的稳定性能 5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布1 1.转移概率转移概率l l定义定义定义定义 5.2.1 5.2.1 设设 X Xn n,n n 00是马尔可夫链，称是马尔可夫链，称 X Xn n,n n

8、00在在 n n 时处于状态时处于状态i i 的条件下经过的条件下经过 k k 步转移，于步转移，于n+kn+k 时到达状态时到达状态 j j 的条件概率的条件概率 n n0,0,k k11为为 X Xn n,n n 00 在在在在n n 时的时的时的时的k k 步转移概率步转移概率步转移概率步转移概率；称以；称以 为第为第i i 行第行第j j 列元素的矩阵列元素的矩阵 为为 X Xn n,n n 00在在在在n n 时的时的时的时的k k 步转步转步转步转移概率矩阵移概率矩阵移概率矩阵移概率矩阵.特别地，当特别地，当k k=1=1时，时，X Xn n,n n 00在在在在n n 时的一步时

9、的一步时的一步时的一步转移概率转移概率转移概率转移概率和和一步转移概率矩阵一步转移概率矩阵一步转移概率矩阵一步转移概率矩阵分别简记为分别简记为 和和P P(n n).l l定义定义定义定义 称可数维的矩阵称可数维的矩阵P P=(=(p pij ij)为为随机矩阵随机矩阵随机矩阵随机矩阵，如果，如果 l l显然，显然，X Xn n,n n 00的的 k k 步转移概率矩阵步转移概率矩阵步转移概率矩阵步转移概率矩阵 是一随机是一随机是一随机是一随机矩阵矩阵矩阵矩阵.事实上，由于事实上，由于 ，并且，并且 l l如果我们进一步约定如果我们进一步约定 ,则则 为单位矩阵为单位矩阵.5.2 5.2 马尔

10、可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布2.2.Chapman-KolmogorovChapman-Kolmogorov方程方程方程方程l l定理定理定理定理(C-KC-K方程方程)或或l l X Xn n,n n 00在在n n 时处于状态时处于状态 i i 的条件下经过的条件下经过 k+mk+m 步转移于步转移于 n+k+mn+k+m 时到达状态时到达状态 j j，可以先在，可以先在 n n 时从状态时从状态 i i 出发，经过出发，经过 k k 步于步于 n+kn+k时到达某种中间状态时到达某种中间状态 l l，再在，再在 n+kn+k 时从状态时从状态 l l 出发经过

11、出发经过 m m 步转步转移于移于 n+k+mn+k+m 时到达最终状态时到达最终状态 j j，而中间状态，而中间状态 l l 要取遍整个状态要取遍整个状态空间。空间。5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布证明证明证明证明5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l在在C-KC-K方程矩阵形式中，取方程矩阵形式中，取m=m=1 1，得，得 一直推下去，有一直推下去，有 其分量形式为其分量形式为 在上式中把在上式中把 k+k+1 1换成换成 k k，便可得如下结论，便可得如下结论 ：l l定理定理定理定理 马尔可夫链的马

12、尔可夫链的马尔可夫链的马尔可夫链的k k 步转移概率由一步转移概率所完全步转移概率由一步转移概率所完全步转移概率由一步转移概率所完全步转移概率由一步转移概率所完全确定确定确定确定.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布3.3.马尔可夫链的分布马尔可夫链的分布马尔可夫链的分布马尔可夫链的分布l l1)1)初始分布称初始分布称 为马尔可夫链为马尔可夫链 X Xn n,n n 00的的初始分布初始分布初始分布初始分布；称第称第i i个分量为个分量为 的的(行行)向量向量 为马尔可夫链为马尔可夫链 X Xn n,n n 00 的的初始分布向量初始分布向量初始分布向

13、量初始分布向量，即，即l l 2)2)有限维分布有限维分布 定理定理定理定理 马尔可夫链马尔可夫链马尔可夫链马尔可夫链 X Xn n,n n 0 0 的有限维分布由其初始分的有限维分布由其初始分的有限维分布由其初始分的有限维分布由其初始分布和一步转移概率所完全确定布和一步转移概率所完全确定布和一步转移概率所完全确定布和一步转移概率所完全确定.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l证明证明证明证明5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l3)3)绝对分布绝对分布称称 为马尔可夫链为马尔可夫链 X Xn n,n n

14、 00的的绝对分布绝对分布绝对分布绝对分布；称第；称第j j 个分量为个分量为 的的(行行)向量向量 为马尔可为马尔可夫链夫链 X Xn n,n n 00 的的绝对分布向量绝对分布向量绝对分布向量绝对分布向量，即，即 .l l显然，绝对分布与初始分布和显然，绝对分布与初始分布和n n步转移概率有如下关系：步转移概率有如下关系：或或5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 事实上事实上5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布4.4.齐次马尔可夫链齐次马尔可夫链齐次马尔可夫链齐次马尔可夫链l l定义定义定义定义 设设 X Xn

15、 n,n n 00是一马尔可夫链，如果其一步转移概率是一马尔可夫链，如果其一步转移概率 p pij ij (n n)恒与起始时刻恒与起始时刻n n无关，记为无关，记为p pij ij ，则称，则称 X Xn n,n n 00 为为齐次齐次齐次齐次(时间齐次或时间齐次或时间齐次或时间齐次或时齐时齐时齐时齐)马尔可夫链马尔可夫链马尔可夫链马尔可夫链.否则，称为非齐次马尔可夫链否则，称为非齐次马尔可夫链.l l对于齐次马尔可夫链对于齐次马尔可夫链 X Xn n,n n 00 ，k k 步转移概率步转移概率 也恒与起也恒与起始时刻始时刻n n无关，可记为无关，可记为 .因此在具体讨论时，总可以假定时因

16、此在具体讨论时，总可以假定时间起始为零，即间起始为零，即 进而进而k k步转移概率矩阵步转移概率矩阵 和一步转移概率矩阵和一步转移概率矩阵 P P(n n)也恒与起也恒与起始时刻始时刻n n无关，分别记为无关，分别记为 和和P P.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 对于马尔可夫链我们有以下定理对于马尔可夫链我们有以下定理l l定理定理定理定理 (1)(1)(2)(2)(3)(3)X Xn n,n n 00的有限维分布由其初始分布和一步转移概率的有限维分布由其初始分布和一步转移概率 所完全确定所完全确定.5.2 5.2 马尔可夫链的转移概率与概率分布马

17、尔可夫链的转移概率与概率分布l l例例例例 5.2.1 5.2.1(天气预报问题天气预报问题)如果明天是否有雨仅与今天的天如果明天是否有雨仅与今天的天气有关，而与过去的天气无关，并设今天下雨、明天有气有关，而与过去的天气无关，并设今天下雨、明天有雨的概率为雨的概率为，今天无雨而明天有雨的概率为，今天无雨而明天有雨的概率为；又假定；又假定把有雨称为把有雨称为 0 0 状态天气，把无雨称为状态天气，把无雨称为1 1状态天气，状态天气，X Xn n 表表示时刻示时刻n n时的状态天气，则时的状态天气，则 X Xn n,n n 00是以是以S=S=0,10,1为状态为状态空间的齐次马尔可夫链，其一步转

18、移概率矩阵为空间的齐次马尔可夫链，其一步转移概率矩阵为5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l例例例例 (有限制随机游动问题有限制随机游动问题)设有一质点只能在设有一质点只能在0,1,2,0,1,2,a a 中的各点上作随机游动，移动规则如下：移中的各点上作随机游动，移动规则如下：移动前若在点动前若在点i i1,2 1,2,a-a-1 1 上，则以概率上，则以概率p p向右移动一格向右移动一格到到i i+1+1处，以概率处，以概率q q 向左移动一格到向左移动一格到i i-1-1处，而以概率处，而以概率r r 停停留在留在i i 处，其中处，其中p,q

19、,rp,q,r0,0,p+q+rp+q+r=1 1 ；移动前若在；移动前若在0 0处，则处，则以概率以概率p p0 0 向右移动一格到向右移动一格到1 1处，而以概率处，而以概率r r0 0停留在停留在0 0处，处，其中其中p p0 0,r r0 000，p p0 0+r r0 0=1=1；移动前若在；移动前若在a a 处，则以概率处，则以概率q qa a 向向左移动一格到左移动一格到a a-1-1处，而以概率处，而以概率r ra a停留在停留在a a处，其中，处，其中，q qa a，r ra a 00，q qa a+r+ra a =1.=1.5.2 5.2 马尔可夫链的转移概率与概率分布马尔

20、可夫链的转移概率与概率分布 设设X Xn n表示质点在表示质点在n n时刻所处的位置，则时刻所处的位置，则 X Xn n,n n 00是以是以S=S=0,1,2,0,1,2,a a 为状态空间的齐次马尔可夫链，其一步转为状态空间的齐次马尔可夫链，其一步转移概率矩阵为移概率矩阵为5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 其中其中0 0和和a a是限制质点游动的两道墙壁，当是限制质点游动的两道墙壁，当r r0 0=1,=1,p p0 0 =0=0时称时称0 0 为吸收壁；当为吸收壁；当r r0 0=0,=0,p p0 0 =1=1时，称时，称0 0为完全反射壁；

21、当为完全反射壁；当00r r0 01,01,0 p p0 011 时，称时，称0 0为部分吸收壁或部分反射壁为部分吸收壁或部分反射壁.对于对于a a也有类似的含义也有类似的含义.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l例例例例5.2.3 5.2.3(无限制随机游动问题无限制随机游动问题)设有一质点只能在设有一质点只能在,-,-a,-a,-(a-a-1)1),-,-2,-1,0,1,22,-1,0,1,2,a,a,中的各点上作随机游动，移中的各点上作随机游动，移动规则如下：移动前若点在动规则如下：移动前若点在i i ,-a,-,-a,-(a-a-1)1)

22、,-,-2,-2,-1,0,1,21,0,1,2,a,a,上，则以概率上，则以概率p p向右移动一格到向右移动一格到i+i+1 1处，以处，以概率概率q q向左移动一格到向左移动一格到i-i-1 1处，其中处，其中p,qp,q 0 0.p+qp+q=1.1.设设X Xn n 表表示质点在示质点在n n时刻所处的位置，则时刻所处的位置，则 X Xn n,n n 00是以是以S S=,-a,-,-a,-(a-a-1)1),-,-2,-1,0,1,22,-1,0,1,2,a,a,为状态空间的齐次马尔可夫链为状态空间的齐次马尔可夫链.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与

23、概率分布 其一步转移概率矩阵为其一步转移概率矩阵为5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l例例例例5.2.4 5.2.4 (赌徒输光问题赌徒输光问题)有两个赌徒甲、乙进行一系列有两个赌徒甲、乙进行一系列赌博赌博.在每一局中甲获胜的概率为在每一局中甲获胜的概率为p p，乙获胜的概率为，乙获胜的概率为q q，p+qp+q=1=1 每一局后，负者要付每一局后，负者要付1 1元给胜者元给胜者.如果起始时甲有如果起始时甲有资本资本a a元，乙有资本元，乙有资本b b元，元，a+ba+b=c=c 元，两人赌博直到甲输元，两人赌博直到甲输光或乙输光为止，求甲输光的概

24、率光或乙输光为止，求甲输光的概率.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l解解解解 根据题设，这个问题可以看成以根据题设，这个问题可以看成以S=S=0,1,20,1,2,c,c 为状为状态空间的随机游动态空间的随机游动 X Xn n,n n 00，质点从，质点从a a点出发到达点出发到达0 0状态状态先于到达先于到达c c状态的概率就是甲先输光的概率状态的概率就是甲先输光的概率.设设0j0jc,uc,uj j 为质点从为质点从j j出发到达出发到达0 0状态先于到达状态先于到达c c状态的概率状态的概率.由全概由全概率公式有率公式有 u uj j=u=

25、uj+j+1 1p p+u uj-j-1 1q q 显然显然u u0 0=1,=1,u uc c=0,0,从而得到了一个具有边界条件的差分方程从而得到了一个具有边界条件的差分方程.设设5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 则可得到两个相邻差分间的递推关系：则可得到两个相邻差分间的递推关系：d dj j=rd=rdj-j-1 1 于是于是当当r r1 1时，时，于是于是5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 而而所以所以故故5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 当当r r=1 1

26、时，时，u u0 0-u-uc c=1 1=cd=cd0 0 而而 u uj j=(c-jc-j)d d0 0 故故根据以上计算结果可知，当根据以上计算结果可知，当r r1 1即即p p q q时，甲先输光的概时，甲先输光的概率为率为 当当r r=1 1即即p p=q q时，甲先输光的概率为时，甲先输光的概率为b b c.c.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l例例例例5.2.5 5.2.5(艾伦菲斯特问题艾伦菲斯特问题)设一个坛子中装有设一个坛子中装有m m个球，它个球，它们或是红色的，或是黑色的，从坛中随机地摸出一个球，们或是红色的，或是黑色的

27、，从坛中随机地摸出一个球，并换入一个相反颜色的球并换入一个相反颜色的球.设经过设经过n n次摸换坛中黑球数为次摸换坛中黑球数为X Xn n，则，则 X Xn n,n n 00是以是以S=S=0,1,20,1,2,m,m 为状态空间的齐次马为状态空间的齐次马尔可夫链尔可夫链.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 其一步转移概率矩阵为其一步转移概率矩阵为5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l例例例例(卜里耶问题卜里耶问题)设坛子中有设坛子中有a a只红球，只红球，b b只黑球，从坛中只黑球，从坛中随机地摸出一个球，

28、然后把该球放回，并加入与摸出的随机地摸出一个球，然后把该球放回，并加入与摸出的球颜色相同的球球颜色相同的球c c只只.设经过设经过n n次摸取坛中黑球数为次摸取坛中黑球数为X Xn n ，则，则 X Xn n,n n 00是以是以S=S=b,b+c,b+b,b+c,b+2 2c c,为状态空间的非齐次马为状态空间的非齐次马尔可夫链尔可夫链.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 其一步转移概率矩阵为其一步转移概率矩阵为5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l例例例例 设设 X Xn n,n n 00具有三个状态具有

29、三个状态0,1,20,1,2的齐次马尔可夫链，的齐次马尔可夫链，其一步转移概率矩阵为其一步转移概率矩阵为 初始分布初始分布 试求试求:（1 1）（2 2）5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l解解解解 由于由于因此因此(1)(1)(2)(2)5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l例例例例 有一有一多级传输系统只传输数字多级传输系统只传输数字0 0和和1 1，设每一级的传，设每一级的传真率为真率为p p，误码率为，误码率为q=q=1-1-p p，且一个单位时间传输一级，且一个单位时间传输一级，X X0 0是第

30、一级的输入，是第一级的输入，X Xn n是第是第n n级得输出，则级得输出，则 X Xn n,n n 11是是以以S=S=0,10,1为状态空间的齐次马尔可夫链，其一步转移概为状态空间的齐次马尔可夫链，其一步转移概率矩阵为率矩阵为 (1)(1)设设p p，求系统二级传输后的传真率与三级传输后的误，求系统二级传输后的传真率与三级传输后的误码率；码率；(2)(2)设初始分布设初始分布 ，又已知系统经，又已知系统经n n级传输级传输后输出为后输出为1 1，求原发数字也是，求原发数字也是1 1的概率的概率.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l解解解解 由于

31、由于有相异特征值有相异特征值 1 1=1,=1,2 2=p-qp-q ，则，则P P 可表示成对角阵可表示成对角阵 的相似矩阵的相似矩阵.5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 又又 1 1,2 2 对应的特征向量分别为对应的特征向量分别为 令令 则则5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布 从而从而l l（1 1）当当p p时，系统经二级传输后的传真率与三级传输后时，系统经二级传输后的传真率与三级传输后的误码率分别为的误码率分别为5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布l l（2 2

32、）根据贝叶斯公式，当已知系统经根据贝叶斯公式，当已知系统经n n级传输后输出为级传输后输出为1 1，原发数字也是，原发数字也是1 1的概率为的概率为5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布5 马尔可夫过程5.1 5.1 马尔可夫过程的定义马尔可夫过程的定义马尔可夫过程的定义马尔可夫过程的定义5.2 5.2 马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布马尔可夫链的转移概率与概率分布5.3 5.3 齐次马尔可夫链的分类齐次马尔可夫链的分类齐次马尔可夫链的分类齐次马尔可夫链的分类5.4 5.4 转移概率的稳定性能转移概

33、率的稳定性能转移概率的稳定性能转移概率的稳定性能 5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类1 1 状态的基本属性状态的基本属性状态的基本属性状态的基本属性l l定义定义定义定义 设设i,ji,jS S，称，称为系统在为系统在0 0时从状态时从状态i i 出发经过出发经过n n 步转移后首次到达状态步转移后首次到达状态 j j 的概率，简称的概率，简称首达概率首达概率首达概率首达概率.称称 为系统在为系统在0 0时从状态时从状态i i 出发经过有限步转移后迟早要回到出发经过有限步转移后迟早要回到状态状态j j 的概率，简称的概率，简称迟早概率迟早概率迟早概率迟早概率.称称

34、为系统在为系统在0 0时从状态时从状态i i 出发永远也不能回到状态出发永远也不能回到状态j j 的概率的概率.l l引理引理引理引理 (1)(1)(2)(2)(3)(3)5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定义定义定义定义 设设j jS S，称，称 为系统首次到达为系统首次到达状态状态 j j 的时间，简称的时间，简称首达时首达时首达时首达时.当当 n|nn|n1,1,X Xn n=j=j=，即，即n n1,1,X Xn nj j 时，时，,即系统在有限时间内不即系统在有限时间内不可能到达状态可能到达状态 j j.显然显然 T Tj j 是一个是一个随机变量

35、随机变量随机变量随机变量.引理引理引理引理 (1)(1)(2)(2)(3)(3)5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定义定义定义定义 设设i iS S，若若 ，则称其最大公约数，则称其最大公约数为为状态状态状态状态 i i 的周期的周期的周期的周期，记为，记为d di i，即，即若若 ，则记其最大公约是为，则记其最大公约是为h hi i ，即，即l l引理引理引理引理 (1)(1)若若 ，则存在，则存在 m m11，使得，使得 n=n=mdmdi i (2)(2)若若 ，则存在，则存在 ，使得，使得 (3)(3)若若 d di i 和和 h hi i 中一个存

36、在，则另一个也存在，且中一个存在，则另一个也存在，且 d di i=h hi i .5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定义定义定义定义 设设i iS S (1)(1)若若f fii ii=1 1则称状态则称状态i i为为常返状态常返状态常返状态常返状态，或称状态，或称状态i i为返回状态；为返回状态；若若f fii ii 1 1则称状态则称状态i i为为非常返状态非常返状态非常返状态非常返状态，或称状态，或称状态i i为滑过状态为滑过状态.(2)(2)若若i i是常返状态且是常返状态且 u uii ii 1 1则称状态则称状态i i为为周期状态周期状态周期状

37、态周期状态，且周期为，且周期为d di i,若若d di i=1 1则称状则称状态态i i为为非周期状态非周期状态非周期状态非周期状态；若状态；若状态i i是正常返的非周期状态，则称是正常返的非周期状态，则称状态状态i i为为遍历状态遍历状态遍历状态遍历状态.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定义定义定义定义 设设i i,j jS S，若若n n11，使使 ,则称状态则称状态 i i 可达可达可达可达状状态态 j j，记为记为i i j j；若若i i j j且且j j i i，则称状态则称状态 i i 与状态与状态 j j 互通互通互通互通，记为记为i i

38、 j.j.l l引理引理引理引理 (1)(1)可达的传递性可达的传递性可达的传递性可达的传递性：若：若i i j,j j,j k k则则i ik k .(2)(2)互通的传递性互通的传递性互通的传递性互通的传递性：若：若i i j,j j,j k k 则则i i k.k.(3)(3)互通的对称性互通的对称性互通的对称性互通的对称性：若：若i i j j则则j j k.k.l l引理引理引理引理 设设 ，则，则l l引理引理引理引理 设设 是常返状态，是常返状态，则则 ，且且5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l引理引理引理引理 设设 则则l l引理引理引理引理

39、设设 是常返状态，是常返状态，则则，且，且2 2.状体属性的判定状体属性的判定状体属性的判定状体属性的判定 定理定理定理定理 5.3.1 5.3.1(DoeblinDoeblin公式公式)，有有 5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类2.2.状态属性的判定状态属性的判定状态属性的判定状态属性的判定l l定理定理定理定理 5.3.1 5.3.1(DoeblinDoeblin公式公式)，有有l l推论推论推论推论 设设 ,则则l l推论推论推论推论 设设 ，则则（1 1）（2 2）5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定理定理定理定理 是是

40、常返状态的充要条件常返状态的充要条件常返状态的充要条件常返状态的充要条件是以下三条件之一成立：是以下三条件之一成立：(1)(1)(2)(2)(3)(3)是是非常返状态的充要条件非常返状态的充要条件非常返状态的充要条件非常返状态的充要条件是以下三条件之一成立：是以下三条件之一成立：(1)(1)(2)(2)(3)(3)5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定理定理定理定理 对任意给定的状态对任意给定的状态 i i ，如果，如果i i 是常返状态且周期为是常返状态且周期为 d di i ，则存在极限，则存在极限 .规定当规定当 时，时，l l定理定理定理定理 设设 是

41、常返状态，则是常返状态，则(1)(1)i i 是是零常返的充要条件零常返的充要条件零常返的充要条件零常返的充要条件是是(2)(2)i i 是是遍历的充要条件遍历的充要条件遍历的充要条件遍历的充要条件是是(3)(3)i i 是是正常返周期的充要条件正常返周期的充要条件正常返周期的充要条件正常返周期的充要条件是是 不存在，但此时不存在，但此时有一收敛于某正数的子列有一收敛于某正数的子列.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l推论推论推论推论 设设 是非常返状态或零常返状态，则是非常返状态或零常返状态，则 有有 l l定理定理定理定理 5.3.5 5.3.5 设设 (

42、1)(1)若存在正整数若存在正整数n n，使得，使得 则则i i 非周期非周期；(2)(2)若存在正整数若存在正整数 m m，使得，使得m m 步转移概率矩阵步转移概率矩阵 中相应中相应于状态于状态 的那列元素全不为零，则的那列元素全不为零，则 j j 非周期非周期.(3)(3)设状态设状态i i 的周期为的周期为d d，则必存在正整数，则必存在正整数 ，使得当，使得当 时，都有时，都有 .5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定理定理定理定理 互通的两个状态有相同的状态类型互通的两个状态有相同的状态类型互通的两个状态有相同的状态类型互通的两个状态有相同的状态类

43、型.即设即设 且且 则则i i 和和 j j 或者同为非常返状态，或或者同为非常返状态，或者同为零常返状态，或者同为正常非周期状态，或者同者同为零常返状态，或者同为正常非周期状态，或者同为正常返周期状态且周期相同为正常返周期状态且周期相同.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类3 3.状态空间的分解状态空间的分解状态空间的分解状态空间的分解l l我们约定若我们约定若 ,则则 ，从而互通满足：，从而互通满足：(1)(1)自反性：自反性：(2)(2)对称性：若对称性：若 则则(3)(3)传递性：若传递性：若 则则即，即，互通是一种等价关系互通是一种等价关系互通是一种等价关

44、系互通是一种等价关系.l l利用互通这一等价关系，可利用互通这一等价关系，可将状态空间将状态空间将状态空间将状态空间 进行划分进行划分进行划分进行划分：5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l显然，同一子集显然，同一子集 中的所有状态都互通，不同子集中中的所有状态都互通，不同子集中 和和 的状态不互通的状态不互通(但单向可达是可以的但单向可达是可以的).).l l称称 为一个为一个等价类等价类等价类等价类，包含，包含 i i 的等价类的等价类 也常记为也常记为 ，于是，于是5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定义定义定义定义 (1

45、)(1)闭集：设闭集：设 C C 是是S S 的子集，如果的子集，如果 和和有有 ，则称，则称C C 为为闭集闭集闭集闭集.显然状态空间显然状态空间 S S 是闭集是闭集.(2)(2)吸收状态：设吸收状态：设 如果状态子集如果状态子集 是闭集，则状态是闭集，则状态 i i 称称为为吸收状态吸收状态吸收状态吸收状态.(3)(3)不可约闭集：设不可约闭集：设C C 是闭集，如果是闭集，如果C C中不再含有任何非空真中不再含有任何非空真闭子集，则称闭子集，则称 C C 是是不可约闭集不可约闭集不可约闭集不可约闭集.或称或称 C C 是不可约的，或不可是不可约的，或不可分的，或最小的分的，或最小的.(

46、4)(4)不可约的齐次马尔可夫链：如果状态空间不可约的齐次马尔可夫链：如果状态空间S S 是不可约的，是不可约的，那么称该那么称该齐次马尔可夫链是不可约齐次马尔可夫链是不可约齐次马尔可夫链是不可约齐次马尔可夫链是不可约的，否则称为可约的的，否则称为可约的.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l引理引理引理引理 (1)(1)是闭集的充要条件是是闭集的充要条件是(2)(2)是闭集的充要条件是是闭集的充要条件是(3)(3)是闭集的充要条件是是闭集的充要条件是(4)(4)是吸收状态的充要条件是是吸收状态的充要条件是 5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链

47、状态的分类l l引理引理引理引理 等价类等价类 若是闭集，则若是闭集，则 是不可约的是不可约的.l l引理引理引理引理5.3.9 5.3.9 设设C C是闭集，当且仅当是闭集，当且仅当C C中的任何两个状态都中的任何两个状态都互通时，互通时，C C 是不可约的是不可约的.l l推论推论推论推论 齐次马尔可夫链不可约的充要条件是它的任何两个齐次马尔可夫链不可约的充要条件是它的任何两个状态都互通状态都互通.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定理定理定理定理 (1)(1)有限齐次马尔可夫链的所有非常返状态之集有限齐次马尔可夫链的所有非常返状态之集 不可不可能是闭集

48、能是闭集.(2)(2)有限齐次马尔可夫链不可能存在零常返状态有限齐次马尔可夫链不可能存在零常返状态.(3)(3)不可约的有限齐次马尔可夫链的所有状态都是正常不可约的有限齐次马尔可夫链的所有状态都是正常返状态返状态.l l定理定理定理定理 设设 是常返状态，则包含是常返状态，则包含 的等价类的等价类S S(i i)是闭集，从而是不可约的是闭集，从而是不可约的.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定理定理定理定理 齐次马尔可夫链的齐次马尔可夫链的状态空间状态空间状态空间状态空间 可唯一地分解可唯一地分解可唯一地分解可唯一地分解成有成有限个或可列无限多个互不相交的状

49、态子集限个或可列无限多个互不相交的状态子集 之并，即之并，即其中其中 是所有是所有非常返状态构成的状态子集非常返状态构成的状态子集非常返状态构成的状态子集非常返状态构成的状态子集，是由是由常返状态构成的不可约闭集常返状态构成的不可约闭集常返状态构成的不可约闭集常返状态构成的不可约闭集，每个状态子集中的状，每个状态子集中的状态有着相同的状态类型，且态有着相同的状态类型，且 总有总有5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l引理引理引理引理 设设 是不可约闭集，周期为是不可约闭集，周期为 如果如果 则则 l l定理定理定理定理 设设 是周期为是周期为 的不可约闭集，则的

50、不可约闭集，则 可惟一地分可惟一地分解为解为 个互不相交的状态子集个互不相交的状态子集之并，即之并，即而且而且 有有其中其中 5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l定理定理定理定理 设设 是周期为是周期为 的不可约的齐次马尔可的不可约的齐次马尔可夫链，其状态空间夫链，其状态空间 已被唯一地分解为已被唯一地分解为 个互不相交的状个互不相交的状态子集态子集 之并之并.现仅在时刻现仅在时刻 上考虑上考虑 即令即令 则：则：(1)(1)是以是以 为一步转移概率矩阵的为一步转移概率矩阵的新的齐次马尔可夫链新的齐次马尔可夫链;(2)(2)对对 而言，每个而言，每个 都是不可

51、约闭集，而且都是不可约闭集，而且 中的状态都是非周期的中的状态都是非周期的;(3)(3)如果如果 X Xn n,n n=0,1,2,=0,1,2,的所有状态皆为常返状态，那么的所有状态皆为常返状态，那么 Y Yn n,n n=0,1,2,=0,1,2,的所有状态也都是常返状态的所有状态也都是常返状态.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l例例例例 设状态空间设状态空间S S=0,1,20,1,2 的齐次马尔可夫链，它的一步的齐次马尔可夫链，它的一步转移概率矩阵为转移概率矩阵为研究其各个状态间的关系以及状态类型研究其各个状态间的关系以及状态类型.5.3 5.3 齐

52、次马尔可夫链状态的分类齐次马尔可夫链状态的分类 解解解解 由于由于 ，其中圈中的，其中圈中的数字代表状态，箭头上的数字代表概率。于是可得到如数字代表状态，箭头上的数字代表概率。于是可得到如图所示状态转移图图所示状态转移图.由于由于 ，由周期的定义可知，状，由周期的定义可知，状态态0 0是非周期的是非周期的.由于三个状态互通，故该齐次马尔可夫由于三个状态互通，故该齐次马尔可夫链是不可约的，且只有三个状态，故三个状态都是正常链是不可约的，且只有三个状态，故三个状态都是正常返状态，从而都是遍历状态返状态，从而都是遍历状态.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l例例例例

53、 设状态空间设状态空间 的齐次马尔可夫链，其一步的齐次马尔可夫链，其一步转移概率矩阵为转移概率矩阵为试分析其状态类型试分析其状态类型.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l解解解解 状态转移图如图所示状态转移图如图所示.状态状态3 3可达状态可达状态1,21,2和和4 4，但这三，但这三个状态不能可达状态个状态不能可达状态3 3，故，故33是非常返状态集，闭集有是非常返状态集，闭集有两个两个1,21,2和和4,4,其中其中44是吸收状态集是吸收状态集.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类例例例例 设设 X Xn n,n n=0,1,2

54、,=0,1,2,是一齐次马尔可夫链，状态空间是一齐次马尔可夫链，状态空间S S=1,2,3,4,51,2,3,4,5 ，其中一步转移概率矩阵为，其中一步转移概率矩阵为 试分析状态类型试分析状态类型.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l解解解解 状态转移图如图所示状态转移图如图所示.状态状态2,42,4可达状态可达状态1,3,51,3,5，但反过，但反过来不可达的，于是一旦离开状态集来不可达的，于是一旦离开状态集2,42,4就不可能回到状就不可能回到状态态2 2或或4 4，所以，所以2,42,4为非常返状态集，为非常返状态集，1,3,51,3,5是闭集是闭集.5

55、.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l例例例例 设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S S=0,0,1,2,3,4,1,2,3,4,5,6,7,8 5,6,7,8 其一步转移概率矩阵为其一步转移概率矩阵为 其中其中*表示一个正数表示一个正数.试分析状态类型试分析状态类型.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l解解解解 由于由于p p0000=0=0，因此，因此0 0是一个吸收状态，又是一个吸收状态，又p p60600,0,故故6 6是非是非常返状态，从而可达状态常返状态，从而可达状态6 6的状态的状态7 7、8 8也

56、是非常返状态，也是非常返状态，故故D D=6,7,8=6,7,8是非常返状态集是非常返状态集.状态状态1 1只可达只可达2 2，同时，同时2 2只可只可达达1 1，所以，所以1,21,2是周期为是周期为2 2的正常返状态集，可分解为的正常返状态集，可分解为J J1 1 =1,=1,J J2 2=2.3,4,5 =2.3,4,5 是状态闭集，由于是状态闭集，由于p p44440,0,因此其周期因此其周期为为1.1.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l例例例例 设状态空间设状态空间S S=0,1,2,3=0,1,2,3的齐次马尔可夫链，其一步转的齐次马尔可夫链，其

57、一步转移概率矩阵为移概率矩阵为试对其状态进行分类试对其状态进行分类.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l解解解解 状态转移图如下图所示状态转移图如下图所示.它是一个有限齐次马尔可夫它是一个有限齐次马尔可夫链，所有状态都是互通的，所以所有状态均为常返状态，链，所有状态都是互通的，所以所有状态均为常返状态，整个状态空间整个状态空间 S S=0,1,2,3=0,1,2,3 构成一个不可约闭集构成一个不可约闭集.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l例例例例 设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S S=0,1,2,3,4

58、=0,1,2,3,4它的一步它的一步转移概率矩阵为转移概率矩阵为试对其状态进行分类试对其状态进行分类.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l解解解解 (1)(1)从一步转移概率矩阵可知状态从一步转移概率矩阵可知状态2 2和和3 3不能和其它状态互不能和其它状态互通，通，2,32,3组成一个闭集组成一个闭集.如果过程初始就处于如果过程初始就处于2 2状态或状态或3 3状状态，则过程永远处于态，则过程永远处于2 2、3 3状态，故状态，故2,32,3是常返状态是常返状态.(2)(2)状态状态4 4可转移到可转移到0,10,1状态，但状态，但0,10,1两个状态不能到

59、达两个状态不能到达4 4状态，状态，0,10,1组成一个闭集，并且组成一个闭集，并且0,10,1是常返状态，是常返状态，4 4是非是非常返状态常返状态.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l例例例例 设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S S=0,1,2,3=0,1,2,3其一步转其一步转移概率矩阵为移概率矩阵为试分析过程的周期性试分析过程的周期性.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l解解解解 状态转移图如图所示状态转移图如图所示.四个状态可以分成四个状态可以分成0,10,1，2,32,3两个子集，该过程有确定性

60、的周期转移两个子集，该过程有确定性的周期转移.0,10,12,32,30,10,12,32,3显然它的周期显然它的周期d d=2.=2.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l例例例例 设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S S=1,2,3,4,5,6,7,8=1,2,3,4,5,6,7,8，其，其一步转移概率矩阵为一步转移概率矩阵为 试研究过程的周期性试研究过程的周期性.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l解解解解 状态转移图如图所示状态转移图如图所示.八个状态可以分成四个状态子集八个状态可以分成四个状态子集J

61、J1 1=1,=1,J J2 2=2,3,4,=2,3,4,J J3 3=5,6,=5,6,J J4 4=7,8.=7,8.J J1 1,J J2 2,J J3 3,J J4 4 是互是互不相交的状态子集，它们的并是整个状态空间，该过程不相交的状态子集，它们的并是整个状态空间，该过程有确定的周期转移有确定的周期转移J J1 1 J J2 2 J J3 3 J J4 4 J J1 1 显然它的显然它的周期周期d d=4.=4.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类例例例例 设状态空间设状态空间S S=0,1,2,=0,1,2,的齐次马尔可夫链，其一步的齐次马尔可夫链，其

62、一步转移概率矩阵为转移概率矩阵为试研究该链是常返链的充要条件试研究该链是常返链的充要条件.5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类l l解解解解 状态转移图如上图所示状态转移图如上图所示.由于由于5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类 故故从而从而所以所以f f0000=1=1的充要条件是的充要条件是 即即0 0是常返状是常返状态的充要条件是态的充要条件是 由于链中的所有状态由于链中的所有状态互通，所以所有状态都是常返，故该链是常返链的充要互通，所以所有状态都是常返，故该链是常返链的充要条件是条件是 此条件相当于以下正项级数发此条件相当于以下正项级数发散，即散，即5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类 反之，如果级数反之，如果级数 收敛则该链为非常返链收敛则该链为非常返链.例如，例如，若若 则则时齐次马尔可夫链是常返链时齐次马尔可夫链是常返链.若若 则则 级数收敛，此时齐次马尔可夫链是非常返链，而且级数收敛，此时齐次马尔可夫链是非常返链，而且5.3 5.3 齐次马尔可夫链状态的分类齐次马尔可夫链状态的分类