概率论与随机过程：第6章 8状态分类判定法

1、状态分类判定法引言引言三、状态分类判定法(充要条件)定义为一实数列，称幂级数记 0)(nnnsasA为数列an的母函数。若an有界，当|s|1时，A(s)收敛。性质0n,an 设若A(s),B(s)为an, bn的母函数,且当|s|1时收敛，则, 2 , 1 , 0,0 nbacnkknkn的母函数C(s)= A(s)B(s),称cn是an, bn的卷积。 00)()(nnknknksbasC定理状态j是常返的,0)( nnjjp如状态j非常返，则.110)(jjnnjjfp 证明 记 的母函数为P(s),F(s),且约定,)()(njjnjjfp0, 1)0()0( jjjjfp1,0)()

2、()( npfpnllnjjljjnjj将上式两端乘sn，并对n求和,)(10)()(1)( nnnllnjjljjnnnjjspfsp2 2常返态的充要条件常返态的充要条件)()(1)(sFsPsP 当0s1时，, 1)(0)( jjnnnjjfsfsF)(11)(sFsP 当0s1时，对任意的正整数N，有,)(0)(0)(0)( nnjjnnnjjNnnnjjpspsPspP(s)单调不减，先令s1，再令N ，有,)(lim0)(1 nnjjspsP同理可证，,)(lim0)(1jjnnjjsffsF )(lim11)(lim11sFsPss jjf 0)(nnjjp所以状态j是常返的,0

3、)( nnjjp若状态j非常返，则. 0lim)( njjnp推论表示由表示由j出发返出发返回回j的平均次数的平均次数(.)PjX|Pj0 记 0,01.nnnnnYYjXjXYDefY表示到达j的次数。 0)(00nnjjnnjnnpjXPEYEY 0)(nnjjp表示由j出发返回j的平均次数。定理若j常返且有周期d，则. 0,.lim)( jjjndjjnddp 则如果状态j是零常返或非常返，则 i E,有推论. 0lim)( nijnp推论 如果状态j常返，则(1) j是零常返. 0lim)( njjnp()j是遍历的.1lim)(jnjjnp 证明 (1)且d=1，即j是遍历。“” j

4、是零常返，由推论1，. 0lim)( nijnp. 0lim)( njjnp从而“” 若j是正常返，由定理，. 0lim)( jndjjndp 与已知矛！()“” 由定理，d=1,显然成立。“” 若.1lim)(jnjjnp 则j是正常返，否则极限为0。总之，,)1(0)( 常返非常返jjpnnjj,0lim0lim)2()()(0)( 正常返零常返且jpjppnjjnnjjnnnjj相通与状态分类的关系：定理 若i常返，且ij，则j也是常返的，且fji=1, j i 。 即：常返态的可达状态是常返的。证明 fji表示由状态j出发，系统经有限步迟早出发，系统经有限步迟早到达i的概率。若i常返，

5、且ij，则fji=1，否则： 若fji0，而1- fji表示系统由j出发经任何有限步都不能到达i的概率， 1- fji0表示当状态由j到达i后，就会发生再经任何有限步都不能返回i的事件，这与i常返矛盾！1 jif由定理， j i，而，而i常返，有常返，有,0)( nniip0, 0)()( rjisijpp设 由C-K方程：)()()()()(niisijniirjirnsjjppppp 常返。jpnnjj,0)( ijfji 01定理设ij，则有：(1) i，j同为常返或同为非常返；(2) i，j同为零常返或同为正常返；(3)同为周期或非周期的，在同为周期时，有相同周期。证明 (1)由上定理

6、可得。(2)设 j 零常返，有 而. 0lim)( njjnp)(0)()( nppniirnsjj所以i零常返。,)()()()(iinjjsijrjirnspppp (3)设0)( sijp0)( rjiptjddid )(,)(设，0)( njjp当, 0)()()()(ii njjrjisijrnspppp从而rnsd |, 0)()()(ii rjisijrsppp又rsd |从而.,|tdnd 同理. td 例P96(2)或教案上一、状态空间的分解TH 所有常返态构成一闭集。用C表示。证明 令,*CEC 由上定理可得*C是E中所有非常返态构成的集合，则. 0,* ijpCjCi有所

7、以C为闭集。综上，状态空间可分为常返态和非常返态两部分，分别记为C和D，由定理， C为闭集，若按状态相通算一类，又可将C进一步分解为C1 1, C2 2, Cn n.（否则j也是常返的）TH 任一马氏链的E可唯一分解为有限个或可列个互不相交的子集D， C1, C2, Cn之并，使得(1)每一Cn是常返态构成的(不可分)闭集。(2) Cn中的状态同类，或全是正常返，或全是零常返，他们有相同的周期，且(3) D由全体非常返态组成，自Cn中的状态不能到达D中的状态。称Cn为基本常返闭集。njkCkjf , 1马氏链所表示的随机运动系统的运动情况一般有：(1)若系统自某一闭集Cl中状态出发开始运动，则

8、以后 随机点只能在Cl中随机运动；(2)若系统自D中某一状态开始运动，其后的运动情况有 两种： 永远在D中运动； 经有限步转移到某个闭集Cl中，以后就在 Cl中随机运动。三、有限链的状态空间TH 有限链所有非常返状态组成的集D不是闭集。证明 若D是闭集，1,)( DjnijpDi有和式中只有有限项，由推论， 若j非常返，0,)( nijpEinlim有两边令n，有0=1，所以D不是闭集。TH 有限链没有零常返状态，即有限链只有非常返状态及正常返状态。(若有零常返状态，则是闭集，同上证明0=1。)例教案。三、不可分链的状态空间TH 不可分链的E中每状态都是常返的或非常返的。有限不可分链只有正常返

9、态。例P100。TH 不可分链Xn, n0, E=0,1,2,则他是常返链的 方程组), 3 , 2 , 1(1 izpzjjiji没有非零有界解。二、不可分闭集(讨论质点在不可分闭集中如何运动)TH 设不可分马氏链 的状态空间为C，周期为d，则C可唯一分解成互不相交的子集之并，即0, nXnsrGGGCsrdrr ,10 使得若自 的某一状态出发，下一步必转移到中。rG)( ,01GGGdr 证明 任取状态iC，对r=0,1,2,d-1,令,0, 0:)( rndijrpnjG对某个因C不可分，ij,有.10 drrGC下证 互不相交：rGrG1 rG反证：若sr,存在 ，由 的定义，srG

10、Gj rG0, 0,)()( rndijsmdijppnm使而ij,有h，使, 0)( hjip于是，, 0)()()( hjirndijhrndiippp, 0)()()( hjismdijhsmdiippp所以，hsdhrd |,|从而srd |但srdsr , 1,0下证 若自 的某一状态j出发，下一步必转移到rG,1 rG只需证明. 11 rGkjkp例P99和教案上。,111 rrGkjkGkjkCkjkppp, 0,)( rmdijrpGj又,0,)()1(1jkrmdijrmdikrpppGk 有若. 1, 0, 011 rrGkjkGjjkjkppp下证分类唯一性： 若用i分类

11、又得 ,110 dGGG只需证：若 用i分类两状态仍属同一,rGkj . lG设,sGi 若rs,则由i出发，只能经r-s,r-s+d,r-s+2d,等步数到达j或k,因此j,k同属. srG若r1时就可得到n步转移概率的近似值：jijnp )(1.1.定义定义 设马尔可夫链的状态空间为，如果对于所有的ai , aj, 转移概率pij(n) ,当n时，存在不依赖于i的极限 jijnnp )(lim jjjnnPnP 212121)(或或 则称此链具有遍历性，又若 ,称 =(1,2,)为链的极限分布。 1 jj 2.2.遍历性的定理遍历性的定理 定理定理 设齐次马氏链Xn,n0的状态空间为a1,

12、 a2,an，P是它的一步转移概率矩阵，如果存在正整数m，使对任意的ai ,aj，都有 Pij(m)0, i , j =1,2,N 则此链具有遍历性，且有极限分布 =(1,2, N)，它是方程组 NjpPNiijij,.,2 , 11 或或的满足条件 j0, 的唯一解。11 Njj 在定理的条件下，马氏链的极限分布又是平稳分布，意即若用作为链的初始分布，即p(0)=，则链在任一时刻n的分布p(n)永远与一致.因为 PPPnPpnpnn1)()0()(例1: 试说明例2中，带有两个反射壁的随机游动是遍历的，并求其极限分布。 解: 为简便，以符号“”代表转移概率矩阵的正元素。于是，由例2中的一步转移概率矩阵P，得 00000000000000000000000000000000)2(2PP 000000000000)4(4PP 即P(4)无零元。由定理，链是遍历的。再根据定理，极限分布 满足的方程组 13/13/13/13/13/13/13/13/13/1543214554344323321221 先由前四个方程，解得 31=2=3=4=35.将它们代入归一条件，即最后一个方程，解之得唯一解： 1=5=1/11, 2=3=4=3/11 所以极限分布为 =(1/11, 3/11, 3/11, 3/11, 1/11). 例2 设一马氏链的