2、马尔科夫链

[马尔科夫链]  马尔科夫链是时间与状态都是离散的马尔科夫过程。

1° 设在一系列随机试验下,系统的可能离散状态为E0,E1,L,如果对于任意二正整数k,m,任意整数0j1<j2<L<jl<m,等式

都成立(表示“第m次试验出现Em的事件),那末称这一随机试验列为马尔科夫链,简称马氏链。

2°  随机变量序列{xn}(n=0,1,L)为马尔科夫链的定义

{xn}(n=0,1,L)为一随机变量序列,它们中间的每一个都可能取值(相当于所处状态Ei) xi(i=0,1,2,L),如果对于任意正整数k,m,任意正整数0j1<j2<L<jl<m,等式

成立,就称{xn}为马尔科夫链,简称马氏链。

通常可取{xi}={1,2,L}

马氏链所刻划的随机试验序列,可以直观地理解为要验测“将来”所处的状态只要用“现在”已知的状态,而“过去”的状态不起任何作用,这就是无后效性。

马氏链,以至于马尔科夫过程都是具有无后效性的随机过程。

[马尔科夫链的转移概率矩阵]  如果在时刻m系统由状态Ei经过一次转移到达状态Ej的概率和时刻m无关,那末就可用pij表示这个一次转移概率。显然

                        pij0,i,j=0,1,2,L

转移概率pij可排成一个转移概率矩阵

               

这是一个每行元素和为1的非负元素的矩阵,称为马氏链的一步转移概率矩阵。

同样用表示系统由状态Ei经过n次转移而到达状态Ej的转移概率,

同样定义马氏链的n步转移概率矩阵:

由无后效性,得

称为切普曼-柯尔莫哥洛夫方程。

由切普曼-柯尔莫哥洛夫方程可以推出

P(n)=Pn

[闭集与状态的分类]  考虑时齐的马氏链。设E为状态空间,E=(E0,E1,E2,L),如果存在正整数n使得,则称Ek可自Ej到达,并记为EjÞEk. 。如EjÞEkEkÞEj就说EjEk,互通,记作EjÛEk

E的子集C为闭集,是指C外的任一状态都不能自C内任一状态到达。设E是闭集,若单点集{Ek}成一闭集,就称Ek为吸引状态,若E不存在真子集是闭集,称这个马氏链是不可分的。

记“系统处在状态Ei的条件下,经n步转移初次到状态Ej的条件概率为,它可用转移概率表示为

                    

于是

它是“系统在开始处于状态Ei的条件下,经有穷次转移后终于到达状态Ej的条件概率,并令

fij=1,则可视mij为从状态Ei出发,初次到达状态Ej转移次数的数学期望

状态分类如下:

1° 如果fjj=1,则称Ej为常返的;如果fjj<1,则称Ej为非常返的;

2°Ej是常返状态,若mjj=,则称Ej为消极常返的(或零状态);若μjj<,则称Ej为积极常返的(或正状态)。

3° 如果正整数集有最大公约数t,当t>1,称Ej为周期的,或具有周期t;当t=1,则称Ej为非周期的。

4° 如果Ej是常返,非周期正状态,则称Ej为遍历的。

状态分类的判别法

1°  Ej为非常返的充分必要条件是

2°  Ej是有周期t的常返状态,则

3°  Ej是遍历的,则

4°  Ej是常返的,则它为零状态的充分必要条件是

[马尔科夫链的分解定理]  任一系统的状态空间可以分解为下列不交子集D,C1,C2,L之和,其中

1°  任一Cj是由常返状态构成的不可分的闭集,Ci中的状态不能自Cj(ij)中的状态到达;

2°  Cj中的状态属同类:或者都是零的,或者都是遍历的,或者都是有周期的非零的状态(在任何一种情况下,Cj中各状态都有相同的周期),而且fik=1(EiÎCj,EkÎCj);

3°  D由一切非常返状态构成(Cj中的状态可能自D中的状态到达,反过来不行)。

[马尔科夫链的遍历性定理]  对于不同的类型,有如下的遍历性定理:

1°  EkÎDEk为零状态,则对任意的j,有

2°  Ek是周期为t的正的常返状态,则对任意的j,有

  (1rt)

其中                         

表示自Ej出发,在某n(nr(modt))上初次到达Ek的概率。

3°  对于不可分非周期的马氏链,极限

存在,而且只能有下面两种情况:

i)所有pj(出现Ej概率)都大于零,此时{pj}是唯一的平稳分布,即概率分布{pj}满足

    j=0,1,L

ii)所有的pj等于零,此时不存在平稳分布。