马尔科夫链的状态分类PPT课件

1、证3若ki ，jk 则由相通定义，存在0m和0n，使0)(mikp，0)(nkjp根据切普曼-柯尔莫哥洛夫方程，有()()( )mnmnijirrjrSppp0)()(nkjmikpp即存在0nm，使0)(nmijp所以有ji 同理可证若kj，ik ，则ij第1页/共52页说明 按互通关系是等价关系，可以把状态空间 S 划分为若干个不相交的集合（或者说等价类），并称之为状态类。 若两个状态互通，则这两个状态属于同一类。 任意两个类或不相交或者相同。2闭集设C为状态空间S 的一个子集，若对任意Ci和任意Cj则C称为闭集注1 若C为闭集，则表示自C内任意状态i出发，始终不能到达C以外的任何状态j。

2、 显然，整个状态空间构成一个闭集。第2页/共52页吸收态指一个闭集中只含一个状态注2若状态空间含有吸收状态，那么这个吸收状态构成一个最小的闭集。3不可约的 若除整个状态空间 S 以外没有其它的闭集，则称此马氏链是不可约的。 如果闭集C的状态都是互通的，则称闭集C是不可约的。第3页/共52页例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。32310414121021211P解先按一步转移概率，画出各状态间的传递图第4页/共52页2/31/41/41/31/21/20121/2图3-1由图可知状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0。因此，

3、状态空间S的各状态都是互通的。又由于S 的任意状态i (i = 0，1，2)不能到达S 以外的任何状态， 所以S是一个闭集而且S 中没有其它闭集所以此马氏链是不可约的。第5页/共52页例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。解先按一步转移概率，画出各状态间的传递图000100000100100002/102/102/1002/11P第6页/共52页111/21/21/2311/2图3-24521 闭集，由图可知 状态3为吸收态且故 1C= 3为闭 集2C=1,43C=1,3,4闭集，闭集，4C=1,2,3,4其中 是不可约的。1C，2C又因状态空间S有闭子集，故此链为非不可

4、约链。第7页/共52页二、首达时间和状态分类1首达时间 系统从状态i出发， 首次到达状态j的时刻称为从状态 i 出发首次进入状态 j 的时间，或称自i 到j 的首达时间。0,min0njXiXnTnij：如果这样的n不存在，就规定ijT说明ijT是一个随机变量，它的取值是系统从状态i 出发使jXn的最小正整数n。第8页/共52页自状态 i出发，经过n步首次到达状态j 的概率自状态i出发，经有穷步终于到达状态j的概率注1|0)(iXnTPfijnij1)(ijnnijijTPff,)(jXjXPfmnnij；| 1, 2 , 10iXnm10)(ijnijff第9页/共52页对于首次到达时间表示

5、从状态 i出发首次返回状态i所需的时间相应的 便是从状态i出发，经有限步终于返回状态 i的概率，ijT当ji 时1,min0niXiXnTnii：iif)(1niiniiffiiTP|01iXnTPiin第10页/共52页2首次到达分解式定理2 证)()(1)(mnjjmijnmnijpfp设系统从状态i经n步转移到状态j，那么首次到达 j 的时间nTij由条件概率及马氏性得|0)(iXjXPpnnij|,01iXjXmTPnijnm|,01iXjXmTPnijnm|01iXmTPijnm,|110jXjXjXiXjXPmmn|01jXjXPiXmTPmnijnm)()(1mnjjmijnmp

6、f对任意Iji,及1n，有第11页/共52页说明( m =1，2，n)的所有可能值进行分解，定理3 本定理表示n步转移概率)(nijp按首次到达时间ijT= m建立了)(mijf与)(nijp之间的关系公式0ijf的充要条件是ji 证充分性设ji 则存在某1n，使0)(nijp由定理2得0)()(1)(mnjjmijnmnijpfp从而)1(ijf，)2(ijf，)(nijf中至少有一个为正，所以0)(1mijmijff第12页/共52页必要性由定理2得所以设0ijf因为)(1mijmijff所以至少有一个1n，使0)(nijf0)()0()()()(1)(nijjjnijmnjjmijnmn

7、ijfpfpfpji 推论ji 的充要条件是0ijf且0jif第13页/共52页3常返态与瞬时态则称状态i为常返态则称状态i为瞬时态注若1iif若1iif“常返”一词，有时又称“返回”、“常驻”或“持久”“瞬时”也称“滑过” 或“非常返”定理4若1iif，则系统以概率 1 无穷次返回 i；若1iif，则系统以概率 1 只有有穷次返回 i。 证若1iif则系统从状态i出发，经过有限次转移之后，必定以概率1返回状态i。再由马氏性系统返回状态i要重复发生第14页/共52页这样，系统从状态i出发，又返回，再出发，再返回，随着时间的无限推移，将无限次访问状态i。将“不返回i”称为成功，则首次成功出现的次

8、数服从几何分布，若1iif则每次回到 i 后都有正的概率iif1不返回 i， 其均值为iif11， 这就是说平均回到 i 共iif11次 就不再回到 i 了。 也就是说以概率1只有有穷次返回i。第15页/共52页定理5证 令n = 0，1，2，因此，从状态i出发，访问状态i的平均次数为i是 常 返 态 的 充 要 条 件 是0)(nniipiXiXInnn，当，当01那么过程访问状态i 的次数为0nnIE访 问 状 态 i 的 次 数 |iX0iXIEnn00|00iXIEnn| 1100iXIPnn|00iXiXPnn0)(nniip由定理4，得证。第16页/共52页说明本定理的等价形式：i

9、为瞬时态，当且仅当定理6证如果i为常返态，且 ，则j也是常返态。因由切普曼-可尔莫哥洛夫方程得上式两边对所有的s相加，得0)(nniipji ji 所以存在0m，0n使0)(mijp，0)(njip 对于任意的0s，()( )()m n snm sjjjiiji Sppp ( )( )()nsmjiillji Sl Sppp )()()(mijsiinjippp)(0snmjjsp)()()(0mijsiinjisppp)(0)()(siismijnjippp又因为i为常返态，所以)(0siisp第17页/共52页故得从而即状态j也是常返态定理7所有常返态构成一个闭集证设i为常返态，)(0sn

10、mjjsp)(0njjnp如果ji ，则ij ，即i和j相通。这是因为若自j出发不能到达i，那么从i出发到达j后，就不能再返回i，这与i是常返态的 相矛盾。1iif再由定理6知，j也是常返态， 这就是说，自常返态出发，只能到达常返态，不能到达瞬时态。故常返态全体构成一个闭集第18页/共52页4状态空间的分解如果已知类中有一个常返态，则这个类中其它状态都是常返的；若类中有一个瞬时态，则类中其它状态都是瞬时态。若对不可约马氏链，则要么全是常返态，要么全是瞬时态。定理8任一马氏链的状态空间S必可分解为12kSNCCC其中N是瞬时态集，21CC是互不相交的由常返态组成的闭集而且（1）对每一个确定的 h

11、，hC内任意两个状态相通；（2）hC和gC（gh ）中的状态不相同。第19页/共52页证记C为全体常返态所构成的集合，则由定理7知C为闭集将C按互通关系分类：那么再从余下的状态中任取一个状态如此进行下去 ，并且显然满足条件（1）和（2）。在 C 中任取一个状态1i，在组成1C后，如果还有余下的状态，2i就可将 C 分解成，21CC等集合之和，第20页/共52页5正常返态与零常返态平均返回时间 从状态i出发，首次返回状态i的平均时间称为状态i平均返回时间.根据 的值是有限或无限，可把常返态分为两类：设i是常返态，则称i为正常返态；)(11niiniiniiinfnTnPTE若i，则称i为零常返态

12、。i第21页/共52页定理9设i是常返态，则（1）i是零常返态的充要条件是（2）i是正常返态的充要条件是0lim)(niinp0lim)(niinp证明（略）推论0lim)(nijnp证因为如果j 是零常返态， i 是任一状态，则第22页/共52页( )( )()10nnkn kijijjjkpfp()()1Nknkijjjkfp)(1)(knjjnNkkijpf)(1)(knjjNkkijpfnNkkijf1)(固定 N，先令n，由定理9，上式第一项有0lim)(1)(knjjNkkijnpf又由于级数1)(1kijkijff收敛，故其尾部1)(Nkkijf当N时趋于0，即第二项当N时趋于

13、0，从而推论得证。第23页/共52页说明用极限判断状态类型的准则（2）i是零常返态（2）i是正常返态0lim)(niinp（1）i是瞬时态)(0niinp（这时0lim)(niinp）)(0niinp且)(0niinp且0lim)(niinp第24页/共52页定理10证明若ji,为常返态，且ji ，则ji,同 为 正 常 返 或 同 为 零 常 返设ji,为 常 返 态因为ji 所 以 存 在 正整 数 k、 m，使0)(kijp，0)(mjip对 于 任 意 正 整 数 r，由切普曼-可尔莫哥洛夫方程得)()()()()(rjjmjirjjkijmrkiippppp)()()()()(rii

14、kijriimjimrkjjppppp令r， 得)()(limlimrjjrmrkiirpp)()(limlimriirmrkjjrpp由此可知)(limriirp与)(limrjjrp或同为零，或同为正，由定理9知ji,同 为 正 常 返 或 同 为 零 常 返第25页/共52页6有限马氏链对有限状态的马氏链我们给出不加证明的性质定理11（1）瞬时态集N不可能是闭集；（2）至少有一个常返态；（3）不存在零常返态；（4）若链是不可约的，那么状态都是正常返的（5）其状态空间可分解为12kSNCCC其中 N 是瞬时态集，kCCC，21是互不相交的由正常返态组成的闭集。第26页/共52页例3转移矩阵

15、已知马氏链, 2 , 1 , 0,nXn的状态空间1,2,3,4S 00011000010041414141P试对其状态分类。解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143第27页/共52页从图可知，此链的每一状态都可到达另一状态，即4个状态都是互通的。考虑状态1是否常返，需要计算11f：41)1(11f1| 1, 1012)2(11XXXPf 1| 2, 1012XXXP 1| 3, 1012XXXP1|4, 1012XXXP 1, 4| 1012XXXP1|401XXP414114pp第28页/共52页类似地可求得所以41413413)3(11pppf4141

16、342312)4(11ppppf0)(11nf（, 6 , 5n）)(11111nnff141414141于是状态1是常返的。又因为25)(1111nnfn所以状态1是正常返的。由定理可知，此链所有状态都是正常返的。第29页/共52页例4 设马氏链的状态空间S=0,1,2,，其一步转移概率为其中试证此马氏链是一个不可约常返态链ppii1，qpi0，Ii10 p，1qp证先证S不可约设i，j是I中任意两个状态，若ji ，则有jjiipppp11即ji 若ji ，则有jjippppq110即ji 于是对于任意的Iji,，都有ji 第30页/共52页类似地可证所以即I中任意两个状态都是相通的。因此，

17、S是一个不可约的闭集再证S中状态0是一个常返态：由状态的转移规则，得ij ji 01210 qppppn所以)(00100nnff0|0001XnTPn第31页/共52页0|0, 1, 2, 101211XXnXXXPnnn1, 0|20| 1102011XXXPXXPn1, 0|010nXXXPnn 1| 20| 112011XXPXXPn 1| 01nXXPnn11nnqp11pq由定义知状态0为常返态。因此，由定理知S中所有状态都是常返态。故此马氏链为不可约常返链。第32页/共52页三、状态的周期与遍历1周期状态对于任意的 ，令其中GCD表示最大公约数iS01)(niiipnGCDd：如

18、果1id，则称 为周期态，iid为周期如果1id则称 为非周期态。i定理12（1）若ji ，则jidd ；（2）若是不可约马氏链，且0iip，则此马氏链是非周期链。第33页/共52页证所以存在正整数m、n，使则有则有因此有（1） 因为ji ， 0)(mijp，0)(njip)(nmiip)(mijp0)(njip所以id能整除 m + n若对某一0s有0)(sjjp，)(snmiip)(mijp)(sjjp0)(njip所以id能整除m + n + s，从而id能整除s。jidd 类似地可证得ijdd 故jidd 第34页/共52页（2）所以1id从而i为非周期态。又因为马氏链不可约，所以j也

19、是非周期态，从而该马氏链是非周期链。2遍历状态若状态i是正常返且非周期，则称i为遍历状态。若马氏链nX的所有状态都是遍历的，则称nX为遍历马氏链，简称遍历链第35页/共52页例5设马氏链的状态空间S = 0,1,2,，转移概率为试讨论各状态的遍历性。解根据转移概率作出状态传递图2100p，211,iip，210ip，Ii1/21/21/21/21/21/20121/2图3-431/2第36页/共52页从图可知，对任一状态 都有 ，故由定理可知，S中的所以状态都是相通的，iS0i因此只需考虑状态0是否正常返即可。21)1(00f412121)2(00f81)21(3) 3(00f故121100n

20、nf从而0是常返态。又因为nnnnnnf2111)(000所以状态0为正常返。又由于021) 1 (00p故状态0为非周期的从而状态0是遍历的。故所有状态i都是遍历的。第37页/共52页习题课1带有两个反射壁的随机游动如果状态空间S = 0，1，2，m，移动的规则是： （1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）； （2）若移动前在m处，则下一步以概率q向左移动一个单位，以概率p停留在原处； （3）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设 表示在时刻n质点的位置，则 ， 是一个齐次马氏链，写出其一步转移概率矩阵。

21、nXnX0n第38页/共52页qp右反射壁m-1mpq左反射壁120pqpqpqpqpqP0000000000000000000000000000001第39页/共52页2带有反射壁的随机游动设随机游动的状态空间S = 0，1，2，移动的规则是： （1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）； （2）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设 表示在时刻n质点的位置，则 ， 是一个齐次马氏链，写出其一步转移概率。nXnX0n第40页/共52页pq反射壁12300000000001pqpqpqP第41页/共52页3一

22、个圆周上共有N格（按顺时针排列），一个质点在该圆周上作随机游动，移动的规则是：质点总是以概率p顺时针游动一格， 以概率 逆时针游动一格。试求转移概率矩阵。pq 1000000000000000000001qppqpqpqqpP1,2,SN第42页/共52页4一个质点在全直线的整数点上作随机游动，移动的规则是：以概率p从i移到i-1，以概率q从i移到i+1，以概率r停留在i，且 ，试求转移概率矩阵。1qpr0000001qrpqrpP, 2, 1,0,1,2,S 第43页/共52页5设袋中有a个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。若在袋里有k个白球，则称系统

23、处于状态k，试用马尔可夫链描述这个模型（称为爱伦菲斯特模型），并求转移概率矩阵。解 这是一个齐次马氏链，其状态空间为 S=a，a+1，1，0，1，2，a一步转移矩阵是01000101000202000101000101aaaaaaaaaP第44页/共52页1/31/211/31/211/312346设马氏链的状态空间S=1，2，3，4，其一步转移矩阵为解 试对其状态分类。0010021210000131313101P按一步转移概率，画出各状态间的传递图它是有限状态的马氏链，故必有一个常返态，又链中四个状态都是互通的。因此，所有状态都是常返态，这是一个有限状态不可约的马氏链。可继续讨论是否为正常返态第45页/共52页可讨论状态11/31/211/31/211/312340)1(11f31)2(11f21213131)3(11f1211212131)4(11f1221122112121312)(11111nnff1221121212131)5(11f122112121