第五章马尔可夫过程2课件.ppt

1、5 马尔可夫过程 马尔可夫过程马尔可夫过程的概念的概念马尔可夫链马尔可夫链马尔可夫链马尔可夫链 生灭过程及应用生灭过程及应用 5 5 马尔可夫过程马尔可夫过程 有限维概率分布有限维概率分布(簇簇)转移概率转移概率 绝对概率绝对概率 极限分布极限分布 平稳分布平稳分布 状态空间的性质状态空间的性质 5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类 一些基本状态类型、概率性质及其关系一些基本状态类型、概率性质及其关系 状态空间的分解状态空间的分解 极限特性与平稳分布极限特性与平稳分布5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_ _状态的基本属性状态的基本属性一、可达与相通一、可达与相

2、通可达的定义可达的定义：对给定的两个状态：对给定的两个状态i和和j,若存在正整数若存在正整数n1,使得使得pij(n)0,则称则称从状态从状态i 可到达可到达状态状态j，记为，记为ij；否则，称；否则，称从状从状态态i不不可到达可到达状态状态j，记为，记为ij。若从状态若从状态i不可不可到达到达状态状态j时，一个时，一个齐次马尔可夫链对于一齐次马尔可夫链对于一切切n(1),总有总有pij(n)=0。11()()()()0NNijnnPjX miP X mnjX mip n到达状态概率概率p概率概率qi=12345两个吸收壁两个吸收壁1,51,55.2.4 马尔可夫链的状态分类马尔可夫链的状态分

3、类_状态的基本属性状态的基本属性一、可达与相通一、可达与相通相通的定义相通的定义：给定的两个状态：给定的两个状态i和和j，如果从状态，如果从状态i可到达状态可到达状态j，即即ij；而且从状态；而且从状态j也可到达状态也可到达状态i，即，即j i，则称，则称状态状态i与与状态状态j 相通相通，记为，记为ij。定理定理：可可达和相通都具有达和相通都具有传递性传递性。即若。即若 ik，kj，则，则ij；若若ik，kj，则，则ij。证证 若若ik，kj，则由定义存在，则由定义存在m1和和n1，使，使pik(m)0,pkj(n)0,根据切普曼柯尔莫哥洛夫方程，根据切普曼柯尔莫哥洛夫方程，()()()0i

4、jikkjk Ep m np m p n状态可达的传递性状态可达的传递性 状态相通的传递性状态相通的传递性5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态的基本属性状态的基本属性二、到达时间和到达概率二、到达时间和到达概率 状态到达时间定义状态到达时间定义：对于任意的对于任意的i,jE，从状态，从状态i出发，到达出发，到达状态状态j的步长。的步长。首达时间定义首达时间定义：对于任意的：对于任意的i,jE，m时刻从状态时刻从状态i出发，经出发，经过过n步首次到达状态步首次到达状态j的时间，的时间，称为从称为从状态状态i到达状态到达状态j的的首达时间首达时间。即从即从状态状态i出发，到达

5、状态出发，到达状态j的最小步长的最小步长n。首达时间是一随机首达时间是一随机变量，取值于集合变量，取值于集合1,2,。Tij=,ij Tii表示从状态表示从状态i出发首次回到状态出发首次回到状态i的时间。的时间。min:(),(),1i jTn X miX m njn5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态的基本属性状态的基本属性二、到达时间和到达概率二、到达时间和到达概率 首达概率定义首达概率定义：对于任意的：对于任意的i,jE，m时刻从状态时刻从状态i出发，经出发，经过过n步首次到达状态步首次到达状态j的概率，的概率，称称为为首达概率首达概率。显然，。显然，()|()()

6、,(),1|()ijijf nP Tn X miP X m nj X m kjkn X mi(1)(1)()ijijfpP X mjX mi()(),1()ijfPXmnj nXmifii(n)表示从状态表示从状态i出发经过出发经过n步首次回到状态步首次回到状态i的概率。的概率。5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态的基本属性状态的基本属性二、到达时间和到达概率二、到达时间和到达概率 迟早到达概率定义迟早到达概率定义：对于任意的：对于任意的i,jE，m时刻从状态时刻从状态i出发，出发，迟早到达状态迟早到达状态j的概率定义为的概率定义为显然，显然，11()|()ijijiji

7、jnnffnP TnX miP T ()11ijijijijfP TP Tf 表示系统在从状态表示系统在从状态i出发，经过有限步转移后不可能到达状态出发，经过有限步转移后不可能到达状态j的概率。的概率。fii表示从状态表示从状态i出发迟早回到状态出发迟早回到状态i的概率的概率:1()iiiiiinffnP T 5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态的基本属性状态的基本属性二、到达时间和到达概率二、到达时间和到达概率 平均转移时间定义平均转移时间定义：定义条件数学期望定义条件数学期望为从状态为从状态i出发，首次到达状态出发，首次到达状态j的的平均转移时间平均转移时间或或平均转

8、移平均转移步数步数。当当i=j 时，时，称为从状态称为从状态i出发，首次出发，首次返回状态返回状态i的的平均返回时间平均返回时间或或平均返回步数平均返回步数。1(0)()ijijijnE TXinfn1()iiiiinnfn5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态的基本属性状态的基本属性二、到达时间和到达概率二、到达时间和到达概率 基本性质基本性质：（1 1）对于任意的）对于任意的i,jE，（2）定理：）定理：对于任意的对于任意的i,jE及及n，该式表明，从状态该式表明，从状态i出发经过时间出发经过时间n后到达状态后到达状态j的概率的概率,等于所有从等于所有从状态状态i出发经

9、过一段时间出发经过一段时间m(0，因，因 则至少存在一个正整数则至少存在一个正整数n1,使得使得fij(n)0。由上定理，。由上定理，因此，因此，ij。（4 4）定理：对于任意的）定理：对于任意的i,jE，0ijfij 1()()()()(0)()0nijijjjijjjijmpnfm pnmfn pfn0 0ijjiffij且1()0ijijmffm5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态的基本属性状态的基本属性三、常返态与非常返态三、常返态与非常返态定义定义：对于对于状态状态i E，若迟早返回的概率若迟早返回的概率fii=1=1，则称状态，则称状态i是是常返态常返态（返回

10、态）；若（返回态）；若fii11，则称状态，则称状态i是是非非常返态常返态（滑过（滑过态、瞬时态）。态、瞬时态）。对于常返态对于常返态i E，若平均返回时间，若平均返回时间 i0,而当而当n不能被不能被d整除时，整除时，pii(n)=0,则称状态则称状态i是是周期的周期的，且周期为，且周期为d；如果不存在上述的；如果不存在上述的d时，则称状时，则称状态态i是是非周期的非周期的。（。（d=1）若状态若状态i为正常返态且为非周期的，则称状态为正常返态且为非周期的，则称状态i是是遍遍历状态历状态。（。（d=1）5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态的基本属性状态的基本属性非常返态

11、 零常返态 状态常返态有周期 正常返态非周期（遍历态）fii=1fii1 i+i=+5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态属性的判定状态属性的判定五、状态判别准则五、状态判别准则平均返回次数平均返回次数：当状态：当状态i是是常返态常返态时，则平均返回时，则平均返回i的次数的次数为无穷；若状态为无穷；若状态i是是非非常返态常返态时，则平均返回时，则平均返回i的次数应为的次数应为有限次。有限次。5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态属性的判定状态属性的判定五、状态判别准则五、状态判别准则 平均返回次数与转移概率的关系平均返回次数与转移概率的关系：若若X(0)

12、=j,X(0)=j,经过经过n n步返回状态步返回状态j j，定义随机变，定义随机变量量 。那么，那么，就表示返回就表示返回j j的次数。平均返回次数为的次数。平均返回次数为 1,()()0,()X njY nX nj1()nNY n11111|(0)()|(0)()|(0)()()|(0)()|(0)()nnjjnnnE N XjEY nXjE Y n XjY n P Y n XjP X nj Xjpn5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态属性的判定状态属性的判定五、状态判别准则五、状态判别准则 定理定理:状态状态i是是常返态常返态的充要条件是下列三个条件之一成的充要条件

13、是下列三个条件之一成立立:(1)(1)fii=1=1 (2)(2)(3)(3)1()iinpn 1iiP T 5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类_状态属性的判定状态属性的判定五、状态判别准则五、状态判别准则 定理定理:状态状态i是是非常返态非常返态的充要条件是下列三个条件之一的充要条件是下列三个条件之一成立成立:(1)(1)fii10,pii(n+1)0,则状态则状态i是是非周期的。非周期的。（2）如果）如果n步转移概率矩阵中相应某状态步转移概率矩阵中相应某状态i的那一列元素的那一列元素全不为零，则状态全不为零，则状态i是非周期的。是非周期的。5.2.4 马尔可夫链的状态分类

14、马尔可夫链的状态分类_状态属性的判定状态属性的判定六、状态之间的等价关系六、状态之间的等价关系定理定理:(1)(1)如果状态如果状态i是常返的是常返的,且且i可达可达j,则状态则状态j也是常返的也是常返的,并且并且fji=1;(2)(2)如果如果i和和j相通相通,则则i和和j状态的常返性、非常返性、状态的常返性、非常返性、正常返性、零常返性、周期性是相同的。正常返性、零常返性、周期性是相同的。相通是一种等价关系相通是一种等价关系,用之对状态进行分解用之对状态进行分解.5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类七、状态空间的分解七、状态空间的分解 闭集定义闭集定义 设设C是状态空间是状

15、态空间E的一个子集，如果从的一个子集，如果从C内任何一个状态内任何一个状态i不能到达不能到达C外的任何状态，则称外的任何状态，则称C是一个是一个闭集闭集。即，对任意。即，对任意的的iC，jC，n1,都有都有pij(n)=0.显然，如果显然，如果C是闭集，对于任意是闭集，对于任意 iC，恒有，恒有 。整个状态空间整个状态空间E是最大的闭集。是最大的闭集。如果单个状态如果单个状态i构成的集构成的集i是闭集，则称状态是闭集，则称状态i是是吸收态吸收态。任何一个吸收状态构成最小的单点闭集。任何一个吸收状态构成最小的单点闭集。()1ijj Cp n5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类七、

16、状态空间的分解七、状态空间的分解 不可约定义不可约定义 如果闭集如果闭集C中不再含有任何非空的子闭集，则称中不再含有任何非空的子闭集，则称C是是不不可约的可约的(不可分的不可分的)。如果闭集如果闭集C的状态是相通的，则的状态是相通的，则C是不可约的。是不可约的。当整个状态空间当整个状态空间E这个闭集不可约时，称此马氏链为这个闭集不可约时，称此马氏链为不不可约马氏链可约马氏链，否则称为，否则称为可约马氏链可约马氏链。5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类七、状态空间的分解七、状态空间的分解 性质性质 （1）C是闭集是闭集 对于对于iC,jC,pij(n)=0,n1,（2）所有常返态

17、构成一个闭集）所有常返态构成一个闭集。（3）齐次马氏链不可约）齐次马氏链不可约 任何两个状态均相通。任何两个状态均相通。（4）在不可约马氏链中，所有状态具有相同的状态类型。）在不可约马氏链中，所有状态具有相同的状态类型。（5）不可）不可约马氏链或没有非常返态或没有常返态。约马氏链或没有非常返态或没有常返态。()1ijj Cp n5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类七、状态空间的分解七、状态空间的分解 状态空间分解状态空间分解 齐次马氏链的状态齐次马氏链的状态E可唯一地分解为有限多个或可列可唯一地分解为有限多个或可列多个互不相交的状态子集：多个互不相交的状态子集：其中，其中，N是

18、非常返态集合，是非常返态集合，C1,C2,是互不相交的是互不相交的不可约不可约常返态常返态闭集。各闭集中的闭集。各闭集中的状态具有相同的状态类型：或者状态具有相同的状态类型：或者均为零常返态；或者均为正常返态。均为零常返态；或者均为正常返态。12ENCC5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类七、状态空间的分解七、状态空间的分解 状态空间分解状态空间分解 对状态空间进行分类，先按常返态和非常返态分成两对状态空间进行分类，先按常返态和非常返态分成两类：类：C和和N。C是一是一闭集闭集.对对C再按相通关系分类，在再按相通关系分类，在C中任取一个状态中任取一个状态i1，凡与，凡与i1相通

19、的状态组成一个集合，记为相通的状态组成一个集合，记为C1；若；若C-C1，再在，再在C-C1中中任取一个状态任取一个状态i2，凡与，凡与i2相通的状态组成一个集合，记相通的状态组成一个集合，记为为C2；再看；再看C-C1 C2？，直到，直到C-C1 C2 =为为止。止。5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类八、有限马尔可夫链的性质八、有限马尔可夫链的性质有限马尔可夫链：有限马尔可夫链：该链的状态空间是一个有限集合该链的状态空间是一个有限集合.有限马尔可夫链性质：有限马尔可夫链性质：（1 1）状态空间）状态空间E可分解为可分解为 其中，其中，N是非常返态集合，是非常返态集合，C1,

20、C2,Ck是互不相交的常返态是互不相交的常返态闭集；闭集；（2）非常返态的集合一定不是闭集；）非常返态的集合一定不是闭集；（3）没有零常返态；）没有零常返态；（4）必有正常返态；）必有正常返态；12kEN CCC5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类八、有限马尔可夫链的性质八、有限马尔可夫链的性质证明证明:（2）非常返态的集合一定不是闭集；）非常返态的集合一定不是闭集；假设非常返态的集合假设非常返态的集合N是一闭集，则对任意的是一闭集，则对任意的iN，有有 因为因为N是非常返态组成的集合，所以对任意的是非常返态组成的集合，所以对任意的jN，有有因此因此 矛盾。矛盾。()1ijj

21、Npnlim()0ijnpn1lim()lim()0ijijnnjNjNpnpn 5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类八、有限马尔可夫链的性质八、有限马尔可夫链的性质（3）没有零常返态；）没有零常返态；如果有某个零常返态如果有某个零常返态i存在，且它属于一个基本闭集存在，且它属于一个基本闭集Ck，那么由闭集性质有，那么由闭集性质有，因为因为Ck是零常返态组成的集合，所以对任意的是零常返态组成的集合，所以对任意的jCk有有 因此，因此，矛盾。矛盾。()1kijj Cpnlim()0ijnpn1lim()lim()0kkijijnnj Cj Cpnpn5.2.4 马尔可夫链的状态分

22、类马尔可夫链的状态分类八、有限马尔可夫链的性质八、有限马尔可夫链的性质（4）必有正常返态；）必有正常返态；根据转移概率性质，总有根据转移概率性质，总有 由于由于E是有限集合，于是是有限集合，于是 这表明不可能对一切的这表明不可能对一切的jE都有都有 设有一状态设有一状态k使得使得 那么状态那么状态k就是正常返态。就是正常返态。()1ijj Epnlim()lim()1ijijnnj Ej Epnpnlim()0ijnpnlim()0iknpn5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类九、极限特性九、极限特性(转移概率转移概率)1 1、非常返态与零常返态的情况、非常返态与零常返态的情况

23、定理定理：若状态：若状态j是非常反态或零常反态，则对任意是非常反态或零常反态，则对任意iE，有，有 lim()0ijnpn 01lim()0nijnkpkn 5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类九、极限特性九、极限特性(转移概率转移概率)2 2、正常返态的情况、正常返态的情况定理定理：（：（1）若）若j为正常返态，则对任意为正常返态，则对任意i E，有，有当状态当状态i可达可达j,当状态当状态i不可达不可达j,11lim()nijijnkjfpkn lim()ijijnjfpn lim()0ijijnjfpn lim()0ijnpn 5.2.4 马尔可夫链的状态分类马尔可夫链的

24、状态分类九、极限特性九、极限特性(转移概率转移概率)2 2、正常返态的情况、正常返态的情况定理定理：（：（2）若）若j为正常返态，周期为为正常返态，周期为d，则对任意，则对任意i E，及及0r d-1，有，有其中，其中，lim()()ijijnjdpndrfr 0()()ijijmfrfm dr5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类九、极限特性九、极限特性(转移概率转移概率)2 2、正常返态的情况、正常返态的情况定理定理：（：（3）若）若j为遍历状态，则对任意为遍历状态，则对任意i E，有，有 （4）若不可约马氏链的状态）若不可约马氏链的状态j是常返态，则对任意是常返态，则对任意

25、i,jE，有，有lim()ijijnjfpn 111lim()nijnkjpkn 5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类九、极限特性九、极限特性(转移概率转移概率)2 2、正常返态的情况、正常返态的情况定理定理：（：（5）对于任何不可约的遍历马氏链，则对任意）对于任何不可约的遍历马氏链，则对任意i,jE，有，有推论推论：不可约非周期常返态齐次马氏链是遍历马氏链，即不可约非周期常返态齐次马氏链是遍历马氏链，即这时，其极限分布、绝对分布、平稳分布一致：这时，其极限分布、绝对分布、平稳分布一致：1lim()ijnjpn lim()(,)ijjnpni jE1lim()lim()(,)i

26、jjjnnjpnpni jEu5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类十、几个例子十、几个例子 (教材教材 例例1-1-例例4)4)例例1 1 两个吸收壁的随机游离运动。两个吸收壁的随机游离运动。状态空间：状态空间：E=1,2,3,4 转移矩阵：转移矩阵：状态转移图状态转移图：pqi=1234pq100000000001qpqpP12341qppq15.2.4 马尔可夫链的状态分类马尔可夫链的状态分类十、几个例子十、几个例子 (教材教材 例例1-1-例例4)4)例例1 1 两个吸收壁的随机游离运动。两个吸收壁的随机游离运动。状态状态1:1:p11=1,f11(1)=1,f11(n)

27、=0(n1),状态状态1为正常返态，吸收态为正常返态，吸收态同理同理，状态状态4为正常返态，吸收态为正常返态，吸收态.pqi=1234pq11111()1nffn1111()1nnfn 5.2.4 马尔可夫链的状态分类马尔可夫链的状态分类十、几个例子十、几个例子 (教材教材 例例1-1-例例4)4)例例1 1 两个吸收壁的随机游离运动。两个吸收壁的随机游离运动。状态状态2:2:p22=0,p23=p,p32=q f22(1)=0,f22(2)=pq,f22(n)=0(n2),状态状态2为非正常返态为非正常返态 状态状态2与与3相通，相通，3也为非正常返态。也为非正常返态。pqi=1234pq22221()1nffnpqp 经常不断地学习,你就什么都知道。你知道得越多,你就越有力量p Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be写在最后谢谢你的到来学习并没有结束，希望大家继续努力Learning Is Not Over.I Hope You Will Continue To Work Hard演讲人：XXXXXX 时 间：XX年XX月XX日