中科院研究生院《随机过程》讲稿：第二章 Markov 过程（2-4）马尔可夫链状态的分类

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 第二章 Markov过程 4.马尔可夫链状态的分类 (一)到达与相通 定义:对给定的两个状态,j∈S,若存在正整数n≥1,是的 p>0,则称从状态i可到达状态j,记作i→j,反之称从状态i 不可到达状态j。 注意:当状态i不能到达状态j时,对于Vn≥1,p=0,因此 P(到达状态x=1}=PUx=X= ≤∑Pxn=X0=l}=∑p=0 定义:有两个状态i和j,如果由i状态可到达j状态,即 i→j,且由j状态也可到达状态,即j→,则称状态i和状态 j相通,记作ij。 定理:可到达和相通都具有传递性。即若i→k,k→>j,则 j;若i>k,kj 证明:如果i→k,k→j,则由定义,存在r≥1和n≥1,使得: pir>0, Pr

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 1 第二章 Markov 过程 4. 马尔可夫链状态的分类 （一） 到达与相通 定义：对给定的两个状态 i , jS ，若存在正整数 n 1 ，是的 0 ( )  n p i j ，则称从状态 i 可到达状态 j ，记作 i → j ，反之称从状态 i 不可到达状态 j 。 注意：当状态 i 不能到达状态 j 时，对于 n 1 ， 0 ( ) = n pi j ，因此     0 1 ( ) 1 0 0 1 0  = = = =       = = = =    =  =  = n n i j n n n n P X j X i p P 到达状态 j X i P X j X i 定义：有两个状态 i 和 j ，如果由 i 状态可到达 j 状态，即 i → j ，且由 j 状态也可到达 i 状态，即 j →i ，则称状态 i 和状态 j 相通，记作 i  j。 定理：可到达和相通都具有传递性。即若 i → k , k → j ，则 i → j ；若 i  k , k  j ，则 i  j。 证明：如果 i → k , k → j ，则由定义，存在 r 1 和 n 1 ，使得： 0, 0 ( ) ( )   n k j r pi k p

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 根据C-K方程,我们有: ∑Pmpm)≥p"p>0(k∈S) 因此,i→j。同理可以证明相通的情形。 (二)首达时间和首达概率: 定义:对于任意的,j∈S,称: T=mm{n:X=,X,=j,n≥1 为从状态i出发首次到达(进入)状态j的时间(时刻),简称首 达时间。 注意:首达时间T是一随机变量,它取值于N={1,2,…,∞}。 定义:对于任意的i,∈S,称: 为系统在0时从状态i出发,经n步首次到达状态j的概率。 由定义,显然有: f0=P{Xn=j;X≠j,m=12…,n-1X0=} f,=p,=p(X=jlO =i) f=P(Xm≠j,Vm21|X0= 定义:对于任意的i,∈S,称: f,=∑m=∑P{,=nX。=i}=P{T,<o 为系统在0时从状态i出发经过有限步转移后迟早到达状态j的

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 2 根据 C－K 方程，我们有： 0 ( ) ( ) ( ) ( ) ( ) ( ) p p p p p k S n k j r i k m S n m j r i m r n i j =      + 因此， i → j 。同理可以证明相通的情形。 （二） 首达时间和首达概率： 定义：对于任意的 i, jS ，称： Ti j = ˆ min n :X 0 = i, X n = j, n 1 为从状态 i 出发首次到达（进入）状态 j 的时间（时刻），简称首 达时间。 注意：首达时间 Ti j 是一随机变量，它取值于 N  = 1,2,  ,。 定义：对于任意的 i, jS ，称： f PTi j n X i  n i j = = 0 = ( ) ˆ 为系统在 0 时从状态 i 出发，经 n 步首次到达状态 j 的概率。 由定义，显然有： f P X n j X m j m n X i  n i j = =  = − 0 = ( ) ; , 1,2,  , 1 f i j = pi j = P X1 = j X0 = i  (1) f i j = P X m  j m  X = i   0 ( ) , 1 定义：对于任意的 i, jS ，称： =  =   = = =        i j n i j n n f i j f i j P T n X i P T 1 0 1 ( ) 为系统在 0 时从状态 i 出发经过有限步转移后迟早到达状态 j 的

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 概率。 注意:P{T1=m}m)=1-f,它表示系统在0时从状态出 发,经过有限步转移后不可能到达状态j的概率。 (三)首达概率的基本性质: (1)对于任意的,j∈S,0≤f0÷1→>j。 (4)对于任意的i,j∈S,f,>0andf,>0分ij 证明:因为: xn=,x,=}={x=1,x=}nU U{x=1x,=1,T,=1U{U(x=1,x,=, 而 1{X=,x,=j,T,=1} 于是我们有: X。=1,X,=/}=U{X。=,Xn=1,T=1 因此,有:

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 3 概率。 注意：  i j  i j i j P T =  = f = − f  ˆ 1 ( ) ，它表示系统在 0 时从状态 i 出 发，经过有限步转移后不可能到达状态 j 的概率。 （三）首达概率的基本性质： （1）对于任意的 i, jS ， 0 1 ( )   i j  n i j f f （2）对于任意的 i, jS 及 1 n   ，有： = − = n l n l j j l i j n pi j f p 1 ( ) ( ) ( ) （3）对于任意的 i, jS ， f i j i j  0  → 。 （4）对于任意的 i, jS ， f and f i j i j  0 j i  0  → 证明：因为：     ( )           = = = = = = =       = = = = = = =   =      l n n i j n l n i j l n n i j X i X j T l X i X j T l X i X j X i X j T l , , , , , , 0 1 0 1 0 0 而  = = = =    l n n i j X i, X j,T l 0 于是我们有：     n l n n i j X i X j X i X j T l 1 0 0 , , , = = = = = = = 因此，有：

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P(Xo=iP(X=j Xo=i) 2P=i PT=IlO=iP(, =j Xo=i, T,=1) 因此 P{X=川X0=} ∑PT,=lX0=1P{X=X=1,T,=1} PT=1X=PXn=X0=1,X≠1,1≤ks1-1X=} ∑fP{Xn=川X=j} ∑/0p)" 即有 p=∑f 于是结论(2)成立。 当i→j时,彐n>0,使得p>0,取: n'=minn: P>0 则有 f0=P{x,=n1X0=i}=p>0 因此 f1=2f≥f 反之,当>0时, ,使得>0,从而p>0,得 因此(3)成立,(4)是(3)的结果

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 4 = = = = = = = = = = = = n l i j n i j n P X i P T l X i P X j X i T l P X i P X j X i 1 0 0 0 0 0 { } { } { , } { } { } 因此：     = − = = = = = = = = = = = =    − = = = = = = = = = = n l n l j j l i j n l n l l i j n l i j n k l n l i j n i j n f p f P X j X j P T l X i P X j X i X j k l X j P T l X i P X j X i T l P X j X i 1 ( ) ( ) 1 ( ) 1 0 0 1 0 0 0 { } { } { , ,1 1, } { } { , } { } 即有： = − = n l n l j j l i j n pi j f p 1 ( ) ( ) ( ) 于是结论（2）成立。 当 i → j 时， n  0 ，使得 0 ( )  n pi j ，取： min : 0 ( )  =  n n n pi j ， 则有：   0 ( ) 0 ( ) = =  = =   n  i j i j n f i j P T n X i p 因此 0 ( ) 1 ( ) =     =  n i j n n i j i j f f f 反之，当 f i j  0 时， n   0 ，使得 0 ( )  n  i j f ，从而 0 ( )  n  pi j ，得 i → j 。 因此（3）成立，（4）是（3）的结果

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 (四)状态的分类 定义:对于状态i∈S,如果f,=1,则称状态为常返态(返 回态);如果f<1,则称状态为非常返态(滑过态) 令条件数学期望: H,=E{mn|X0=i}=∑n u,是从状态i出发,到达状态j的平均转移步数(时间) 注意:特别地,若i=,则A1÷是从状态出发,首次返回 状态的平均转移步数,称为状态的平均返回时间;对应的f称 为状态i的返回概率;f称为从状态出发,首次返回状态i的 概率。 定义:对于常返态i∈S,若<+,则称状态i是正常返的; 否则,若=∞,则称状态i是零常返的。 (五)常返态和非常返态的判别 (1)状态eS是常返(f=1)的∑p=∞。 (2)状态i∈S是非常返(f<1)的分∑pm) fr

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 5 （四）状态的分类 定义：对于状态 iS ，如果 f i i =1 ，则称状态 i 为常返态（返 回态）；如果 f ii 1 ，则称状态 i 为非常返态（滑过态）。 令条件数学期望：     = = = = 1 ( ) 0 ˆ n n i j i j nfi j  E T X i i j 是从状态 i 出发，到达状态 j 的平均转移步数（时间）。 注意：特别地，若 i = j ，则 i i = i ˆ 是从状态 i 出发，首次返回 状态 i 的平均转移步数，称为状态 i 的平均返回时间；对应的 i i f 称 为状态 i 的返回概率； (n) i i f 称为从状态 i 出发，首次返回状态 i 的 概率。 定义：对于常返态 iS ，若 i  + ，则称状态 i 是正常返的； 否则，若 i =  ，则称状态 i 是零常返的。 （五）常返态和非常返态的判别 （1） 状态 iS 是常返（ f i i =1 ）的   =   =0 ( ) n n pi i 。 （2） 状态 iS 是非常返（ f ii 1 ）的    −  =  = i i n n i i f p 1 1 0 ( )

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 (3)如果j∈S是非常返的,则对vieS,有∑pm<; P (4)设j,则和j或者都是正常返的,或者都是非常返的, 或者都是零常返的 (5)若状态i∈S是常返的,则i是零常返的limp"=0 (6)如果j∈S是零常返的,则对vi∈S,有lmp=0。 证明:对于序列{p,n20和{f,n21,分别引入其母函数为: ()=∑Ps"=o,+∑ F,(s)=∑f 上面两个级数当s<时,都是绝对收敛的。利用公式 p=∑fp 我们有 P(s)=6,+∑ps=6,+∑∑ J ∑m"s∑(pm"s") 6,+∑f s∑(PS E,(s)P,(s) 令 由上式,有

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 6 （3） 如 果 j S 是非常返的，则对 iS ， 有     =0 ( ) n n pi j ； lim 0 ( ) = → n i j n p 。 （4） 设 i  j ，则 i 和 j 或者都是正常返的，或者都是非常返的， 或者都是零常返的。 （5） 若状态 iS 是常返的，则 i 是零常返的  lim 0 ( ) = → n i i n p （6） 如果 j S 是零常返的，则对 iS ，有 lim 0 ( ) = → n i j n p 。 证明：对于序列  , 0 ( ) p n  n i j 和  , 1 ( ) f n  n i j ，分别引入其母函数为：    =  = = = + 1 ( ) 0 ( ) ( ) n n n i j i j n n n i j i j P s p s  p s   = = 1 ( ) ( ) n n n i j i j F s f s 上面两个级数当 s 1 时，都是绝对收敛的。利用公式： = − = n v n v j j v i j n pi j f p 1 ( ) ( ) ( ) 我们有： ( )( ) ( ) ( ) ( ) ( ) ( ) 0 ( ) 1 ( ) ( ) 1 ( ) 1 1 ( ) ( ) 1 1 ( ) ( ) 1 ( ) F s P s f s p s f s p s f s p s P s p s f p s i j i j j j m m m j j v v v i j i j n v n v n v j j v v v i j i j n n v n v n v j j v v i j i j n n n v n v j j v i j i j n n n i j i j i j = + = + = + = +       = + = +          =  =  = − −  =  = = − −  = = −  =       令 j = i ，由上式，有：

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P(S)=1-F1(s) 在上式中,令s→1,我们有: 由此可得以上结论的(1)、(2)。 另外,当j是非常返态,且i≠j时,由 P,(s)=61+F(s)P,(s) 可得 P,(1)=E(1)P,()≤P,()j,则存在正整数k,m,使得 0,pm>0 因此对于任意的正整数r,有 pup 由此可得: ∑p/P"p"=pmp∑P 因此,当i是常返态时,可知j也是常返态;当i是非常返态时, 可知j也是非常返态。结论(4)成立。 注意:一个状态有限的马氏链,不可能所有状态都为非常返

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 7 1 ( ) 1 ( ) F s P s i i i i − = 在上式中，令 → − s 1 ，我们有： i i n n i i f p −  =  = 1 1 0 ( ) 由此可得以上结论的（1）、（2）。 另外，当 j 是非常返态，且 i  j 时，由 P (s) F (s)P (s) i j = i j + i j i j 可得： Pi j (1) = Fi j (1)Pj j (1)  Pj j (1)   即     =0 ( ) n n pi j ，且 lim 0 ( ) = → n i j n p 由此可得结论（3）。 若 i  j ，则存在正整数 k , m ，使得 0 , 0 ( ) ( )   m j i k pi j p 因此对于任意的正整数 r ，有： ( ) ( ) ( ) (k ) i j r i i m j i k r m pj j  p p p + + 由此可得：     =  =  = + +  = 0 ( ) ( ) ( ) 0 ( ) ( ) ( ) 0 ( ) r r i i k i j m j i r k i j r ii m j i r k r m pj j p p p p p p 因此，当 i 是常返态时，可知 j 也是常返态；当 i 是非常返态时， 可知 j 也是非常返态。结论（4）成立。 注意：一个状态有限的马氏链，不可能所有状态都为非常返

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 态 例1(赌徒输光问题)赌徒甲有赌资a元,赌徒乙有赌资b元, a,b为不小于1的正整数。两人进行一系列的赌博。每赌一局, 输者给赢者1元,没有和局,直赌到两人中有一人输光为止。设 在每局中甲赢的概率为p,输的概率为1-p,求甲输光的概率 解:此问题实际上就是状态空间为S={02,…a+b}的一个马 氏链,其中状态0和状态a+b为吸收态。甲开始处于状态a,最 后它要么到达状态0(输光),要么到达状态a+b(将对方赢完), 然后就不赌了。求甲输光的概率,实际上就是求甲从状态a首达 状态0的概率。理论上有一步转移概率矩阵(很容易写出)就可 以求得,但这样求相当麻烦,现在用其它方法来求。 令u为甲从状态i出发首达状态0的概率。我们要求的是u。 因为状态0和状态a+b为吸收态,所以u=1,un=0,用全概率 公式,我们有: u=pu 1+qu=(p+q)u=pu+qu- 因此有: p(ln-l,)=g(u14-l1)→(u1-1)=(u1-u-1)= P 因此有: (u1-l) P

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 8 态。 例 1 （赌徒输光问题）赌徒甲有赌资 a 元，赌徒乙有赌资 b 元， a , b 为不小于 1 的正整数。两人进行一系列的赌博。每赌一局， 输者给赢者 1 元，没有和局，直赌到两人中有一人输光为止。设 在每局中甲赢的概率为 p ，输的概率为 1− p ，求甲输光的概率。 解：此问题实际上就是状态空间为 S = 0,1,2, a + b 的一个马 氏链，其中状态 0 和状态 a + b 为吸收态。甲开始处于状态 a ，最 后它要么到达状态 0 （输光），要么到达状态 a + b （将对方赢完）， 然后就不赌了。求甲输光的概率，实际上就是求甲从状态 a 首达 状态 0 的概率。理论上有一步转移概率矩阵（很容易写出）就可 以求得，但这样求相当麻烦，现在用其它方法来求。 令 i u 为甲从状态 i 出发首达状态 0 的概率。我们要求的是 u a 。 因为状态 0 和状态 a + b 为吸收态，所以 u0 =1, u a+b = 0 ，用全概率 公式，我们有： 1 1 1 1 ( ) ui = pui+ + qui−  p + q ui = pui+ + qui− 因此有： ( ) ( ) ( ) ( ) ( ) 1 0 1 1 1 1 u u p q u u p q p u u q u u u u i i i i i i i i i −         = = + − = − −  + − = − − =  因此有：   + − = + − = + −         − = 1 1 0 1 1 ( ) ( ) a b i k i a b i k i i u u p q u u

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 k=0,1,2,…,a+b 令k=0,利用u=1,ub=0,可得: (41-1) u P P 代入上面的式子,有 l= k=0.1.2.….a+b P P 令k=a,u=0,可得: 此即为所要求的结果。 当p=q=0.5时,u a+b 当p≠q时, P 例2设有一电脉冲,脉冲的幅度是随机的,其幅度的可取值 是{12,3…,n},且各幅度出现的概率相同。现用一电表测量其幅 度,每隔一单位时间测量一次,从首次测量开始,记录其最大幅 值为X(n≥1)。(1)证明该过程为一齐次马氏链;(2)写出一步 转移概率矩阵;(3)仪器记录到最大值n的期望时间

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 9  + − = + = +         − = − 1 1 ( 1) 0,1,2, , a b i k i a b k k a b p q u u u  令 k = 0 ，利用 u0 =1, u a+b = 0 ，可得：   + − = + − = = −          −         − = − 1 0 1 1 0 1 ( 1 1) ( 1)/ 1 a b i i a b i i u p q p q u 代入上面的式子，有   + − + − = = + = +                 − − = 1 1 0 0,1,2, , 1 a b i k i a b i a b k i k a b p q p q u u  令 k = a ， u a+b = 0 ，可得：   + − + − = =                 = 1 1 0 1 a b i a i a b i a i p q p q u 此即为所要求的结果。 当 p = q = 0.5 时， a b b u a + = 当 p  q 时， a b a a b a p q p q p q u + +         −         −         = 1 。 例 2 设有一电脉冲，脉冲的幅度是随机的，其幅度的可取值 是 1,2,3,  ,n ，且各幅度出现的概率相同。现用一电表测量其幅 度，每隔一单位时间测量一次，从首次测量开始，记录其最大幅 值为 X (n 1) n 。（1）证明该过程为一齐次马氏链；（2）写出一步 转移概率矩阵；（3）仪器记录到最大值 n 的期望时间

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 解:(1)记:5是第i(i=1,2…)次记录的幅度值,则是 相互独立同分布的随机变量序列。X是前m次记录幅度的最大 值。则有 PX -m-1 X P( max(5, i)=ji P(max(s, i)=j; 以上用到了的相互独立性。因此: P )(m)=P(Xm X=i)=P(max 5=j max 5i=i) =P{max(51,)=j} 因此此过程是齐次马氏过程。 (2)一步转移概率为 J 1<≤n 0,其它 (3)设T为仪器记录到最大值n的首达时间,则可以看为起初 在n状态的首达返回时间,则: PIT=k)=f 因此记录到最大值n的期望为 ET 由此可知,n状态是正常返态。 例3随机游动:

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 10 解：（1）记：  i 是第 i （ i =1,2,  ）次记录的幅度值，则  i 是 相互独立同分布的随机变量序列。 X m 是前 m 次记录幅度的最大 值。则有：   ( ) {max( , ) } { max , } , , , 2 1 1 1 1 1 1 P i j P i j P X j X i X i X i l l k l m l m k m k m m m = = = = = = = =   + +   + + − −    以上用到了  i 的相互独立性。因此： {max( , ) } ( ) { } {max max } 2 1 1 1 ( ) P i j p m P X X i P j i l l k l l m l l m k m k m k i j = = = = = = =   +   +   +    因此此过程是齐次马氏过程。 （2）一步转移概率为            = = 0 , 其 它 , 1 , i j n n j i n i pi j （3）设 T n 为仪器记录到最大值 n 的首达时间，则可以看为起初 在 n 状态的首达返回时间，则： 1 1 ( ) 1 ( 1) { } − − − = = = k k k n n n n n n P T k f ， 因此记录到最大值 n 的期望为 n n n n E T k k k k n = − =   = − − 1 1 1 1 ( 1) { } 由此可知， n 状态是正常返态。 例 3 随机游动：