马尔科夫链的状态分类要点课件.ppt

1、马尔可夫链的状态分类马尔可夫链的状态分类一、互通与闭集一、互通与闭集1互通则称自状态i可到达状态j如果对状态 i 和 j，存在某个0n,使0)(nijp记为ji 如果ji 且ij 则称状态i和状态j互通记为ji 说明说明如果自状态i不能到达状态j，则意味着对于一切0n，有0)(nijp定理定理1即它满足（1）自反性）自反性（2）对称性）对称性若ji ，则ij 若ki ，jk ，则ji 证（3）传递性）传递性（1），（2）显然，下证（3）证证3若ki ，jk 则由相通定义，存在0m和0n，使0)(mikp，0)(nkjp根据切普曼-柯尔莫哥洛夫方程，有()()( )mnmnijirrjrSppp

2、0)()(nkjmikpp即存在0nm，使0)(nmijp所以有ji 同理可证若kj，ik ，则ij说明说明 按互通关系是等价关系，可以把状态空间 S 划分为若干个不相交的集合（或者说等价类），并称之为状态类。 若两个状态互通，则这两个状态属于同一类。 任意两个类或不相交或者相同。2闭集设C为状态空间S 的一个子集，若对任意Ci和任意Cj则C称为闭集注1 若C为闭集，则表示自C内任意状态i出发，始终不能到达C以外的任何状态j。 显然，整个状态空间构成一个闭集。吸收态指一个闭集中只含一个状态注2若状态空间含有吸收状态，那么这个吸收状态构成一个最小的闭集。3不可约的 若除整个状态空间 S 以外没有

3、其它的闭集，则称此马氏链是不可约的。 如果闭集C的状态都是互通的，则称闭集C是不可约的。例例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。32310414121021211P解先按一步转移概率，画出各状态间的传递图2/31/41/41/31/21/20121/2图3-1由图可知状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0。因此，状态空间S的各状态都是互通的。又由于S 的任意状态i (i = 0，1，2)不能到达S 以外的任何状态， 所以S是一个闭集而且S 中没有其它闭集所以此马氏链是不可约的。例例2其一步转移矩阵为试讨论哪些状态是吸收态、闭

4、集及不可约链。解先按一步转移概率，画出各状态间的传递图000100000100100002/102/102/1002/11P111/21/21/2311/2图3-24521 闭集，由图可知 状态3为吸收态且故 1C= 3为闭 集2C=1,43C=1,3,4闭集，闭集，4C=1,2,3,4其中 是不可约的。1C，2C又因状态空间S有闭子集，故此链为非不可约链。二、首达时间和状态分类二、首达时间和状态分类1首达时间 系统从状态i出发， 首次到达状态j的时刻称为从状态 i 出发首次进入状态 j 的时间，或称自i 到j 的首达时间。0,min0njXiXnTnij：如果这样的n不存在，就规定ijT说明

5、ijT是一个随机变量，它的取值是系统从状态i 出发使jXn的最小正整数n。自状态 i出发，经过n步首次到达状态j 的概率自状态i出发，经有穷步终于到达状态j的概率注1|0)(iXnTPfijnij1)(ijnnijijTPff,)(jXjXPfmnnij；| 1, 2 , 10iXnm10)(ijnijff对于首次到达时间表示从状态 i出发首次返回状态i所需的时间相应的 便是从状态i出发，经有限步终于返回状态 i的概率，ijT当ji 时1,min0niXiXnTnii：iif)(1niiniiffiiTP|01iXnTPiin2首次到达分解式定理定理2 证证)()(1)(mnjjmijnmni

6、jpfp设系统从状态i经n步转移到状态j，那么首次到达 j 的时间nTij由条件概率及马氏性得|0)(iXjXPpnnij|,01iXjXmTPnijnm|,01iXjXmTPnijnm|01iXmTPijnm,|110jXjXjXiXjXPmmn|01jXjXPiXmTPmnijnm)()(1mnjjmijnmpf对任意Iji,及1n，有说明说明( m =1，2，n)的所有可能值进行分解，定理定理3 本定理表示n步转移概率)(nijp按首次到达时间ijT= m建立了)(mijf与)(nijp之间的关系公式0ijf的充要条件是ji 证证充分性设ji 则存在某1n，使0)(nijp由定理2得0)

7、()(1)(mnjjmijnmnijpfp从而)1(ijf，)2(ijf，)(nijf中至少有一个为正，所以0)(1mijmijff必要性由定理2得所以设0ijf因为)(1mijmijff所以至少有一个1n，使0)(nijf0)()0()()()(1)(nijjjnijmnjjmijnmnijfpfpfpji 推论推论ji 的充要条件是0ijf且0jif3常返态与瞬时态常返态与瞬时态则称状态i为常返态则称状态i为瞬时态注注若1iif若1iif“常返”一词，有时又称“返回”、“常驻”或“持久”“瞬时”也称“滑过” 或“非常返”定理定理4若1iif，则系统以概率 1 无穷次返回 i；若1iif，则

8、系统以概率 1 只有有穷次返回 i。 证证若1iif则系统从状态i出发，经过有限次转移之后，必定以概率1返回状态i。再由马氏性系统返回状态i要重复发生这样，系统从状态i出发，又返回，再出发，再返回，随着时间的无限推移，将无限次访问状态i。将“不返回i”称为成功，则首次成功出现的次数服从几何分布，若1iif则每次回到 i 后都有正的概率iif1不返回 i， 其均值为iif11， 这就是说平均回到 i 共iif11次 就不再回到 i 了。 也就是说以概率1只有有穷次返回i。定理定理5证证 令n = 0，1，2，因此，从状态i出发，访问状态i的平均次数为i是 常 返 态 的 充 要 条 件 是0)(

9、nniipiXiXInnn，当，当01那么过程访问状态i 的次数为0nnIE访 问 状 态 i 的 次 数 |iX0iXIEnn00|00iXIEnn| 1100iXIPnn|00iXiXPnn0)(nniip由定理4，得证。说明说明本定理的等价形式：i为瞬时态，当且仅当定理定理6证证如果i为常返态，且 ，则j也是常返态。因由切普曼-可尔莫哥洛夫方程得上式两边对所有的s相加，得0)(nniipji ji 所以存在0m，0n使0)(mijp，0)(njip 对于任意的0s，()( )()m n snm sjjjiiji Sppp ( )( )()nsmjiillji Sl Sppp )()()(

10、mijsiinjippp)(0snmjjsp)()()(0mijsiinjisppp)(0)()(siismijnjippp又因为i为常返态，所以)(0siisp故得从而即状态j也是常返态定理定理7所有常返态构成一个闭集证证设i为常返态，)(0snmjjsp)(0njjnp如果ji ，则ij ，即i和j相通。这是因为若自j出发不能到达i，那么从i出发到达j后，就不能再返回i，这与i是常返态的 相矛盾。1iif再由定理6知，j也是常返态， 这就是说，自常返态出发，只能到达常返态，不能到达瞬时态。故常返态全体构成一个闭集4状态空间的分解如果已知类中有一个常返态，则这个类中其它状态都是常返的；若类中

11、有一个瞬时态，则类中其它状态都是瞬时态。若对不可约马氏链，则要么全是常返态，要么全是瞬时态。定理8任一马氏链的状态空间S必可分解为12kSNCCC其中N是瞬时态集，21CC是互不相交的由常返态组成的闭集而且（1）对每一个确定的 h，hC内任意两个状态相通；（2）hC和gC（gh ）中的状态不相同。证记C为全体常返态所构成的集合，则由定理7知C为闭集将C按互通关系分类：那么再从余下的状态中任取一个状态如此进行下去 ，并且显然满足条件（1）和（2）。在 C 中任取一个状态1i，在组成1C后，如果还有余下的状态，2i就可将 C 分解成，21CC等集合之和，5正常返态与零常返态平均返回时间 从状态i出

12、发，首次返回状态i的平均时间称为状态i平均返回时间.根据 的值是有限或无限，可把常返态分为两类：设i是常返态，则称i为正常返态；)(11niiniiniiinfnTnPTE若i，则称i为零常返态。i定理定理9设i是常返态，则（1）i是零常返态的充要条件是（2）i是正常返态的充要条件是0lim)(niinp0lim)(niinp证明证明（略）推论推论0lim)(nijnp证证因为如果j 是零常返态， i 是任一状态，则( )( )()10nnkn kijijjjkpfp()()1Nknkijjjkfp)(1)(knjjnNkkijpf)(1)(knjjNkkijpfnNkkijf1)(固定 N，

13、先令n，由定理9，上式第一项有0lim)(1)(knjjNkkijnpf又由于级数1)(1kijkijff收敛，故其尾部1)(Nkkijf当N时趋于0，即第二项当N时趋于 0，从而推论得证。说明说明用极限判断状态类型的准则（2）i是零常返态（2）i是正常返态0lim)(niinp（1）i是瞬时态)(0niinp（这时0lim)(niinp）)(0niinp且)(0niinp且0lim)(niinp定理定理10证明证明若ji,为常返态，且ji ，则ji,同 为 正 常 返 或 同 为 零 常 返设ji,为 常 返 态因为ji 所 以 存 在 正整 数 k、 m，使0)(kijp，0)(mjip对

14、 于 任 意 正 整 数 r，由切普曼-可尔莫哥洛夫方程得)()()()()(rjjmjirjjkijmrkiippppp)()()()()(riikijriimjimrkjjppppp令r， 得)()(limlimrjjrmrkiirpp)()(limlimriirmrkjjrpp由此可知)(limriirp与)(limrjjrp或同为零，或同为正，由定理9知ji,同 为 正 常 返 或 同 为 零 常 返6有限马氏链对有限状态的马氏链我们给出不加证明的性质定理定理11（1）瞬时态集N不可能是闭集；（2）至少有一个常返态；（3）不存在零常返态；（4）若链是不可约的，那么状态都是正常返的（5）

15、其状态空间可分解为12kSNCCC其中 N 是瞬时态集，kCCC，21是互不相交的由正常返态组成的闭集。例例3转移矩阵已知马氏链, 2 , 1 , 0,nXn的状态空间1,2,3,4S 00011000010041414141P试对其状态分类。解解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143从图可知，此链的每一状态都可到达另一状态，即4个状态都是互通的。考虑状态1是否常返，需要计算11f：41)1(11f1| 1, 1012)2(11XXXPf 1| 2, 1012XXXP 1| 3, 1012XXXP1|4, 1012XXXP 1, 4| 1012XXXP1|4

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

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

18、iS01)(niiipnGCDd：如果1id，则称 为周期态，iid为周期如果1id则称 为非周期态。i定理定理12（1）若ji ，则jidd ；（2）若是不可约马氏链，且0iip，则此马氏链是非周期链。证证所以存在正整数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 （2）所以1id从而i为非周期态。又因为马氏链不可约，所

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

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

21、p右反射壁m-1mpq左反射壁120pqpqpqpqpqP00000000000000000000000000000012带有反射壁的随机游动带有反射壁的随机游动设随机游动的状态空间S = 0，1，2，移动的规则是： （1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）； （2）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设 表示在时刻n质点的位置，则 ， 是一个齐次马氏链，写出其一步转移概率。nXnX0npq反射壁12300000000001pqpqpqP3一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作随机游动，移

22、动的规则是：质点总是以概率p顺时针游动一格， 以概率 逆时针游动一格。试求转移概率矩阵。pq 1000000000000000000001qppqpqpqqpP1,2,SN4一个质点在全直线的整数点上作随机游动，移动的规则是：以概率p从i移到i-1，以概率q从i移到i+1，以概率r停留在i，且 ，试求转移概率矩阵。1qpr0000001qrpqrpP, 2, 1,0,1,2,S 5设袋中有a个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。若在袋里有k个白球，则称系统处于状态k，试用马尔可夫链描述这个模型（称为爱伦菲斯特模型），并求转移概率矩阵。解 这是一个齐次马氏链

23、，其状态空间为 S=a，a+1，1，0，1，2，a一步转移矩阵是01000101000202000101000101aaaaaaaaaP1/31/211/31/211/312346设马氏链的状态空间S=1，2，3，4，其一步转移矩阵为解 试对其状态分类。0010021210000131313101P按一步转移概率，画出各状态间的传递图它是有限状态的马氏链，故必有一个常返态，又链中四个状态都是互通的。因此，所有状态都是常返态，这是一个有限状态不可约的马氏链。可继续讨论是否为正常返态可讨论状态11/31/211/31/211/312340)1(11f31)2(11f21213131)3(11f12

24、11212131)4(11f1221122112121312)(11111nnff1221121212131)5(11f1221121212121312)6(11f1状态1是常返态)(1111nnfn122161221512142133122状态1是正常返态所以，全部状态都是正常返态7设马氏链的状态空间S=1，2，3，4，5，其一步转移矩阵为试研究各状态的类及周期性解00001000016 . 04 . 00008 . 02 . 0000005 . 05 . 001P各状态间的传递图对于任意 有， 即S为不可再分闭集。所以S中每一个状态都是常返态，且此马氏链为有限状态不可约常返链。0.40.2

25、11 0.50.50.80.631254, i jSji 142112 . 05 . 0 152118 . 05 . 0 143114 . 05 . 0153116 . 05 . 0 所以状态1的周期为3，由定理知，S中所有状态都为周期态，且周期都为3。因此，这个马氏链又是以3为周期的周期链。又因为马氏链为有限状态不可约链，所以所有状态都是正常返状态。8设马氏链的状态空间为S = 1，2，3，其一步转移矩阵为试研究各状态间的关系。解10005 . 05 . 005 . 05 . 01P0.50.50.5120.513在1C中两个状态是互通的，在2C中状态 3 是吸收状态。因此，1C，2C都是闭集可继续讨论正常返9设马氏链的状态空间为S = 1，2，3，4，其一步转移矩阵为试研究各状态间的关系。解02 . 02 . 06 . 0007 . 03 . 0000101001P10.60.20.20.71120.334状态空间为S分两个部分：= 1，2，3， =41C2C 是闭集1C 中状态4可到达 中各状态，且它非吸收状态，所以 不是闭集。2C1C2C