中科院研究生院《随机过程》讲稿：第二章 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,k<j,则i<>j 证明:如果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≤f<,≤1 (2)对于任意的,j∈S及1≤n<∞,有: =∑f0 (3)对于任意的,j∈S,f>0÷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 ( )