《随机过程》课件第5章

第5章马尔可夫过程5.1马尔可夫过程的定义5.2马氏链的刻画5.3马氏链的状态空间分解5.4转移概率的极限与平稳分布5.5连续时间马氏过程的转移概率5.6马氏过程的状态空间分解和平稳分布5.7应用举例习题五

马尔可夫过程是由前苏联数学家A.A.Markov首先提出和研究的一类随机过程，至今已成为内容十分丰富、理论上相当完整、应用也十分广泛的一门数学分支，其应用领域涉及计算机、通信、自动控制、随机服务、可靠性、生物学、经济学、管理学、教育学、气象学、物理、化学等。

本章只介绍状态集可列或有限的离散时间和连续时间马尔可夫过程。离散时间的简称为马氏链。

5.1马尔可夫过程的定义

设有一随机过程{X(t)，

t∈T}，其状态空间S可列或有限(统称为可数)，我们考虑其有限维分布函数。对n>0，t1

<t2<…<tn+1，

tk∈T，(k=1，

2，…，

n+1

)，及状态i1

，

i2

，…，in+1∈S

，由乘法公式我们有

根据条件概率的定义，上式中自然要求

从而

于是(5.1.1)式中各式均有定义。以后在涉及到条件概率时，我们总如此假定，不再一一声明。

对于(5.1.1)式，最简单的莫过于以下情形:

此时

显然，(5.1.3)式对任意的i1

，

i2

，…，

in+1都成立意味着X(t1

)，

X(t2

)，…，

X(tn+1)相互独立。但相互独立在实际中是非常少见的，而且从数学上来说用不着作为随机过程来研究它。比独立稍为复杂一点的则是以下情形:

此时

(5.1.4)式所示的性质，我们称之为无后效性，它表示在已知系统现在所处的状态之下，系统将来的演变与过去无关。很多实际问题都具有这种无后效性。例如，生物基因遗传从这一代到下一代的转移中仅依赖于这一代而与以往各代无关。再如，每当评估一个复杂的计算机系统的性能时，就要充分利用系统在各个时刻的状态演变所具有的通常概率特性:即系统下一个将到达的状态，仅依赖于目前所处的状态，而与以往处过的状态无关。此外，诸如某公司的经营状况等等也常常具有或近似地具有无后效性。我们给出如下定义。

定义5.1.1设X={X(t)，

t∈T}是定义在概率空间(Ω，

F

，

P)上，取值于可数集合S中的一个随机过程，如果对任意的正整数n，t1

<t2<…<tn+1，

tk∈T，(k=1，

2，…，

n+1)及状态i1

，

i2

，…，

in+1∈S均有

则称此过程为马尔可夫过程，简称为马氏过程。称(5.1.6)式为马尔可夫性，简称为马氏性，也称为无后效性。

马氏性的直观含义可以解释如下:将tn

看作为现在时刻，那末，

t1

，

t2

，…，

tn-1就是过去时刻，而

tn+1则是将来时刻，于是，(5.1.6)式是说，当已知系统现时情况的条件下，系统将来的发展变化与系统的过去无关。

我们称马氏过程X取值的全体所组成的集合S为过程的状态空间，它可以是任意的一个集合，但为了数学上的处理，往往要对它加以某种可测性的结构。本章只讨论S为可列或有限(称为可数)的情形。(5.1.6)式是关于S可数时给出的。马氏过程的参数集T常用的有两种情形:连续的区间和可列集，常称前一情形的X为马氏过程，称后一情形的X为马氏链。这些是本章下面将要分别介绍的。我们常称X(t)=i为“系统在t时处于状态i”。

对于T={0，

1，

2，…}的马氏链X={X(0)，

X(1)，

X(2)，…}，我们常将它记为X={Xn

，

n≥0}。对此，容易证明，马氏性(5.1.6)式等价于对任一n≥0，

i0

，

i1

，…，

in+1∈S均有

与(5.1.6)式等价的形式还有不少，详细的可见参考文献[12]第1章的定理1，那儿共给出了10种形式及其互相等价的证明。

5.2马氏链的刻画

本节讨论如何刻画一个马氏链。为方便起见，我们记状态空间S={1，

2，

3，…}，它可以是有限的或可列的，记T={0，

1，

2，…}，马氏链X={Xn，

n≥0}。首先引入概率向量和随机矩阵。

定义5.2.1(1)称可数维的向量p=(p1

，

p2

，

p3

，…)为概率(行)向量，如果其各元均非负且∑jpj=1。概率列向量可类似定义。

(2)称可数维的矩阵P=p(ij)为随机矩阵，如果它的每一行均是概率向量，即

容易验证，随机矩阵具有如下性质。

性质5.2.1(1)随机矩阵P的任意次幂Pm(m≥0)均是随机矩阵;

(2)如果随机矩阵P的各行皆对应相等，即pij=pj

，(∀i，

j)，则

为了描述马氏链X，由其定义(5.1.6)式，我们引入记号

我们进一步约定

定义5.2.2系统在n时处于状态i的条件下经过k步转移，于n+k时转移到j的条件概率p

(k)ij(n)称为X(在n时)的k步转移概率;第(i，

j)个元素为p(k)ij(n)的矩阵P(k)(n)称为X(在n时)的k步转移概率矩阵。特别地，

k=1时(在n时)的一步转移概率和一步转移概率矩阵分别简记为pij(n)和P(n)。称{p(k)ij(n)，

i，

j∈S，

n，

k≥0}为X的有限步转移概率族。

由(5.2.2)式知P(0)(n)=I为单位矩阵。

对于X的k步转移概率矩阵P(k)(n)，由概率的定义易知p(k)ij(n)≥0，进而，由完全可加性可得

因此P(k)(n)均是随机矩阵。

从马氏链的定义(5.1.6)式出发，我们在(5.2.1)式中引入了X的k步转移概率，而由马氏链的等价定义(5.1.7)式知，我们似乎只需要引入X的一步转移概率即可。由于定义(5.1.6)式和(5.1.7)式是等价的，因此易于猜测k步转移概率与一步转移概率之间应是等价的，即可以互相表示。为此，我们先来证明以下称之为Chapman-Kolmogorov(简称为C－K)方程的一个公式。

定理5.2.1

其中(5.2.3')式是(5.2.3)式的矩阵形式。

证明由转移概率定义、全概率公式及马氏性，有

C－K方程(5.2.3)式的直观意义如下:系统n时从状态i出发，经过k+m步于n+k+m时转移到状态j，可以先在n时从i出发经过k步于n+k时转移到某个中间状态l，再在n+k时从状态l出发经m步于n+k+m时转移到状态j，而中间状态l取遍全空间S。但需要指出的是，C－K方程并非对所有随机过程均成立，因为在证明的第三个等式中用到了马氏性。

在(5.2.3')式中取m=1，可得

由此递推，即得以下公式:

其分量形式为

(5.2.4')式说明，对于马氏链X，其k步转移概率由一步转移概率所完全确定。因此，两者等价。

马氏链X的转移矩阵列P

(n

)(n=0，

1，

2，…)只刻画了随机系统在转移过程中的概率法则，并不能由它决定出系统初始所处状态的概率，因此有必要引进概率qi=P{X0=i}，i∈S，并称{qi，

i∈S}为X的初始分布，称第i个分量为qi的向量q为X的初始分布向量。

定理5.2.2马氏链X的有限维分布函数族由其初始分布和一步转移概率矩阵列P

(n)(n=0，

1，

2，…)所唯一确定。

证明对任给的n，非负整数t1

<t2<…<tn+1，及状态ik∈S，

k=1，

2，…，

n+1，有

由此及(5.2.4)式知定理结论成立。

定理5.2.2反过来也成立，即任给一概率分布{qi，

i∈S}及随机矩阵列P(n)(n=0，

1，2，…)，则必存在一概率空间及定义在其上的状态空间为S的一个马氏链X={Xn

，

n=0，1，

2，…}，使得{qi

，

i∈S}恰为X的初始分布，

P(n)为X在n时的一步转移概率矩阵(n

=0，

1，

2，…)。实际上，读者不难从第2章第1节中的有关结论出发来证明定理5.2.2的逆也成立。

考虑马氏链的一维分布，即Xn

的概率分布:

常称之为马氏链的绝对分布。由定理5.2.2，有

若记q(n)表示第j个元素为q(n)j的行向量，则上式可重写为

转移概率p(k)ij(n)不仅依赖于状态i，

j，转移步数k，而且一般地也依赖于起始时刻n。有一种特殊情况是转移概率与n无关。

定义5.2.3如果马氏链X的一步转移概率pij(n)恒与起始时刻n无关，记为pij，则称X为时间齐次马氏链，简称为齐次马氏链。不是齐次的马氏链就称为非齐次马氏链。

本章下面只讨论齐次马氏链，关于非齐次的马氏链的讨论，有兴趣的读者可参阅参考文献[12]。

对齐次马氏链，由(5.2.4)式易知，

k步转移概率p(k)

ij(n)也与时间起点n无关，简记为p(k)ij

。因此，在讨论转移概率时，我们就可假定时间起点为零，即

记第(i，

j)个元素为p(k)ij的矩阵为P(k)，称为齐次马氏链的k步转移概率矩阵，一步转移概率矩阵P(1)即为P。

由(5.2.4')式及定理5.2.2即可得到以下推论。

推论5.2.1对齐次马氏链，有(1)P(k)=Pk，k≥1，

q

(k)=q(0)Pk

，k≥0;

(2)X的有限维分布函数族由初始分布和一步转移概率矩阵所完全确定。

齐次马氏链的转移概率矩阵P可用一个有向图来表示，其节点为状态，从i到j有一条弧意指pij>0。称此图为马氏链的状态转移概率图。于是从i到j有一条路意指有正整数n使得

p

(n)ij>0。由于随机矩阵P的行和为1，因此在有向图中我们可以去掉节点自身到其自身的弧(在图论中称为自环)。

下面我们讨论几个马氏链的例子。

例5.2.1(双壁随机游动)设有一质点只能在S={0，

1，

2，…，

N}中各点上作随机游动，移动的规则如下:移动前若在

n∈{1，

2，…，

N-1}上，则以概率p向右移动一格到n+1

，以概率q向左移动一格到n-1处，而以概率r停留在原处，自然，

p、q、r非负且

p+q+r=1;移动前若在0处，则质点以概率p0

反射回1处，以概率r0

继续停留在0处;移动前若在N处，则质点分别以概率qN

和rN

反射回N-1处或停留在N处。0和N是限制质点运动的两道墙壁，当r0=1、p0=0时，称0为吸收壁;当r0=0、p0=1时，称0为反射壁;在一般情形，称0为部分反射壁。

壁N也有类似的多重含义。以Xn表示质点在时刻n所处的位置，则容易看出，

X={Xn

}是一以S为状态空间的齐次马氏链，其转移概率矩阵为

它是一个三对角矩阵。

上例可描述多种实际问题。

实例一赌徒输光问题。设某赌徒与一赌金足够多的对手进行赌博。将状态i∈S解释为赌徒在某时刻所拥有的资金，

p是每局赌博中赌徒赢的概率，q为输的概率，而r则为和的概率;每局中赢或输的赌金为1个单位。假定0和N均为吸收壁，于是吸收壁0表示赌徒已经输光，不能再赌，从而赌博结束;吸收壁N可表示赌徒已赢得较多的钱因而停止赌博。于是Xn表示赌徒在第n局赌博后的赌金，其初始分布表示赌徒开始时所拥有的赌金情况。

实例二参照实例一，只是将其中的术语“赌徒”改为“投资家”、“赌博”改为“投资”、“第n局”改为“第n次投资”，此时，读者将会得到全新的另一种解释。

实例三(随机徘徊滤波器)对一系统接连不断地输入一串脉冲序列，自然脉冲相位可能超前可能滞后，也可能恰好不超前也不滞后。经过一段时间之后的叠加，相位可能出现过于超前或过于滞后的现象，因而造成较大的误差，于是必需设法加以恢复，那么首先应建立一个准则，判断何时过于超前何时过于滞后，以便随时修正。

为此可利用双吸收壁的随机游动模型设计计数器。状态集S={0，

1，

2，…，

2N}，计数器的初始值置为N;在计数器中，p表示有一相位超前的输入脉冲(此时计数器施行加法运算)的概率，q表示有一相位滞后的输入脉冲(此时计数器施行减法运算)的概率，

r表示相位既不超前也不滞后的输入脉冲(计算器保持不动)的概率。一旦计数器上的计数达到0(相当于质点未达到2N处之前先到达0处)，这表示净相位滞后的脉冲个数达到N，此时，计数器判断相位过于滞后，输出一需提前的控制脉冲，同时将计数器上记数重新置为N;

一旦计数器上的记数达到达2N(相当于未达到0之前先到达2N)，这表示净相位超前的脉冲个数达到N，此时，计数器判断相位过于超前，输出一需推后的控制脉冲，同时将计数器上记数重新置为N。如此周而复始地工作可达到控制的目的。

与例5.2.1中类似，可以考虑只有一个壁的随机游动问题。例如，

0为部分反射壁，则状态集为S={0，

1，

2，…}，相应的转移概率矩阵为一可列维矩阵

例5.2.2(市场预测)公司A、B、C是某地区三家主要灭虫剂厂商。根据历史资料得知，公司A、B、C的市场占有率分别为50%、32%、20%。由于C公司实行了改善销售与服务方针的经营管理策略，使其产品销售额逐期稳定上升，而A公司却下降。

通过市场调查发现三个公司间的顾客流动情况如表5.1所示。其中产品销售周期是季度。现在的问题是按照目前的趋势发展下去，

A公司的产品销售额或客户转移的影响将严重到什么程度?更全面的，三个公司的产品销售额的占有率将如何变化?

将表中数据化为转移概率，对研究分析未来若干周期的顾客流向更为有利。表5.2中列出了各公司顾客流动的转移概率。表5.2的数据是每家厂商在一个周期的顾客数与前一个周期的顾客数相除所得。表中每一行表示某公司从一个周期到下个周期将能保住的顾客数的百分比，以及将要丧失给竞争对手的顾客数的百分比。表中每一列表示各公司在下一周期将能保住的顾客数的百分比，以及该公司将要从竞争对手那里获得的顾客数的百分比。

如用矩阵来表示表5.2中的数据，就得到如下的转移概率矩阵:

P中数据表示一个随机挑选的顾客，从一个周期到下一个周期仍购买某一公司产品的可能性或概率。如，随机挑选一名A公司的顾客，他在下一周期仍购买A公司产品的概率为0.7，购买B公司产品的概率为0.1，购买C公司产品的概率为0.2。

考虑未来各周期市场占有率的计算。以A、B、C公司作为我们要分析的系统的状态，那么状态概率向量就分别为三家公司的产品销售额的市场占有率。初始状态概率向量为

转移矩阵由(5.2.6)式给出。于是可用(5.2.5)式来计算未来各期的市场占有率。如状态转移一次后第一周期的市场占有率向量为

可用q(k+1)=q(k)P，

k≥0递推地求得未来各期的市场占有率。

5.3马氏链的状态空间分解

为了揭示齐次马氏链的基本结构，需对其状态按某些概率特性来分类，分类也是研究n步转移概率p(n)ij当n→∞时的极限性态的基础。

5.3.1状态类型的定义

首先我们引入刻画状态特性的若干特征量。

定义5.3.1对i，j∈S，记

f(n)ij表示系统在0时从状态i出发经过n步转移后首次到达状态j的概率。再记

这里

fij表示在0时从i出发，系统经有限步转移后终究要到达状态j的概率，而f(∞)ij则是在0时从i出发，系统在有限步转移内不可能到达状态j的概率。我们将f(n)ij和fij

统称为首达概率。不难看出，

f(∞)

ij+fij=1。

下面讨论首达概率与一步转移概率pij之间的关系，同时，也给出首达概率的计算。

引理5.3.1

(2)首达概率可以用一步转移概率来表示:

(3)任意n步转移概率与首达概率之间有如下重要的关系式:

证明(1)显然。

(2)由定义5.3.1及(5.1.5)式可得

(3)由n步转移概率的定义可得

对j∈S，记矩阵Pj是第j列为零，其余同P

。则式(5.3.4)可写为

公式(5.3.5)是基本而又重要的，它在下面将多次被引用。

引理5.3.2(Doeblin公式)对任意的i，j∈S，有

证明由(5.3.5)式可得

于是

令N→∞取上极限，可得

任取正整数1<N'<N，则由(5.3.7)式有

对任意的N‘

，令N→∞取下极限，然后再令N’→∞，可得

由此及(5.3.8)式即证得引理。

关于首次到达，我们也可用随机变量来刻画。

定义5.3.2对j∈S，称

为首达j的时间，其中约定，当右边集合为空集(即对任意的n≥1，

Xn≠j)时，

Tj=∞，它表示系统不可能在有限时间内到达状态j

由于Tj可取值+∞，因此它不是通常含义上的随机变量，我们称之为取广义实值的随机变量。容易看出，

Tj与首达概率之间有以下关系式:

当Tj取∞的概率为非零时，其数学期望必为无穷大。下面假定Tj取∞的概率为零，故它是一个通常含义上的随机变量，考虑其条件数学期望μij=E{Tj|X0=i}，易知

称μij为从状态i

出发，到达状态j

的平均转移步数，特别地，当i=j

时，μij是从状态j

出发首次返回j的平均转移步数，我们称之为

j的平均返回时间。对应地，称fjj

为j

的返回概率，

f

(n)jj为从j出发在n步时首次返回的概率。

最后一个特征量如下。

定义5.3.3对i∈S，若正整数集{n|n≥1，p(n)ii>0}非空，则定义其最大公约数(GCD)为状态i的周期，记为di，即

类似地，若正整数集{n|n≥1，f(n)ii>0}非空，则记其最大公约数(GCD)为hi，即

特征量di和hi反映了在系统的发展变化过程中状态i重复出现的概率周期规律，它们具有如下性质。

引理5.3.3(1)若p(n)ii>0

，则有正整数m，使得n=mdi

;且di

是满足以上性质的最大整数。hi也具有类似的性质。

(2)hi

和di

中若一个有定义，则另一个也有定义，且两者相等。

证明(1)显然。

(2)对任一给定的状态i，不难看出正整数集N1

∶={n|n≥1，p(n)ii>0}和N2∶={n|n≥1，f(n)ii>0}中若有一个非空，则另一个也非空。因此，我们下面假定这两个集合N1

、N2均非空。

首先，由于f(n)ii≤p(n)ii，所以N2⊂N1

，从而di

≤hi

。如果hi

=1，那么必有hii=di

=1。如果hi

>1，则，对每个l=1，

2，…，

hi-1必有f(l)

ii

=0

，再由(5.3.5)式知p(l)

ii=0。

对n=hi

+l，

l=1，

2，…，

hi

-1，由(1)知，当n不是hi的倍数时f(n)ii=0

，于是由(5.3.5)式得

现作归纳假设:对每个l=1，

2，…，

hi

-1，当n=l，

hi

+l，…，(M-1)hi+l时，已有p(n)ii=0。再由hi的定义，同样道理知

利用归纳法可断言，如果n不是hi的整数倍，必有p(n)ii=0

，故N1中的数都可被hi整除，从而hi能整除di

，所以hi≤di

。

综上，证得结论。

有了上述准备工作之后，我们就可以来划分状态了。

定义5.3.4

对状态i∈S，若fii

=1，则称状态i是常返的(或返回的);否则(fii<1)，称状态i

是非常返的(或不返回的或滑过的、瞬时的)。

由fii的定义知，

fii

=1表示系统从状态i出发必定要返回状态i

，实际上，可以进一步证明，

i常返意指从ii

出发将无穷多次地返回i

;而i

非常返意指从i

出发，至多返回i有穷多次。这就分别是“常返”和“滑过”的含义。

定义5.3.5对常返状态i∈S，若μii

<+∞，则称状态i是正常返的;否则(μii

=+∞)，称状态

i是零常返的(或消极常返的或零状态)。

对于零常返状态i

，其平均返回时间为无穷大，因此称其为消极常返的。两种常返状态;正常返状态和零常返状态，反映到n步转移概率的极限上则区别为非零和零极限(见将要介绍的定理5.3.3)。

定义5.3.6(1)对状态i，若di=1，则称状态i是非周期的;否则(di

>1)，称i

是有周期的，且其周期为di。

(2)称非周期正常返的状态为遍历状态。

综上，我们从状态是否常返，如常返的话是否正常返，如正常返的话是否非周期等三个层次上将状态区分为以下的类型:

5.3.2状态类型判别

上面，我们根据状态的首次返回概率、平均返回时间和周期性将状态进行了分类。但直接从定义出发来判别状态的类型，虽然是件十分困难的事情。下面我们通过不同类型状态所具有的不同性质来区别它们。以下定理给出了判别一个状态是常返的或非常返的准则。

定理5.3.1状态i∈S是常返状态，当且仅当以下三个条件之一成立:

证明由定义5.3.5、(5.3.10)式及引理5.3.2即知该定理成立。

定理5.3.2对任意给定的状态i，如果i是常返的且有周期di

，则存在极限:

其中规定当μii=∞时，

1/μii=0。

证明因为状态i固定，不妨将p(n)ii、

f(n)ii、di、

μii

分别简记为pn

、fn

、d、μ。令

由于i是常返的及(5.3.5)式，则有

从而对一切n=1，

2，…，

由于

i是常返的，

fii=1，故必有某正整数t

使ft

>0，由引理5.3.3知d可整除t，再利用(5.3.5)式得

在(5.3.15)式中取n=(nm-N0)d，并注意到d不能整除v时，

pv=0，便有

由定义5.3.3、引理5.3.3，当d不能整除v时，

fv

=0，再依rn

的定义便知

于是

利用傅比尼定理还有

将(5.3.22)式和(5.3.21)式代入(5.3.20)式中得λ=d/μ。

若令对应地仿照前面的方法可证β=d/μ。

综合两者断言存在并为d/μ。

以下定理给出了常返状态的3种类型的判别准则。．

以下定理给出了常返状态的3种类型的判别准则。

定理5.3.3设状态i是常返状态，则

(1)i为零常返的充要条件是存在极限

(2)i

为正常返非周期(遍历)的充要条件是存在极限

(3)i为正常返有周期的充要条件是极限不存在，但此时有一收敛于某正数的收敛子列，即。

定理5.3.4对状态i∈S:

(1)若有正整数n

使得p(n)ii>0，p(n+1)

ii>0

，则i

无周期。

(2)如果存在正整数m使得在

m步转移概率矩阵Pm

中相应于某状态j的那列元素全不为零，则状态j无周期。

(3)设状态i

有周期d

，则必存在正整数N0，使得对所有N≥N0均有p(Nd)

ii

>0。

证明(1)显然。

(2)由假设知对一切i∈S，p(m)ii

>0。于是由(5.3.4)式知有i1∈S使得pii1

>0，进而由C－K方程及假设有p

(m+1)ij≥pii1p(m)i1j>0，

i∈S。特别地，便有p(m+1)

jj>0，p(m)jj>0，由(1)知j

是非周期的。

(3)正整数集{n:n≥1，p(n)

ii>0}总可写成{nm

，

m=1，

2，…}，记dm∶=GCD{nt

，

t=1，

2，…，

m}，

m≥1

。依此定义易知d1≥d2≥…≥d≥1。显然d1

是一有限正整数，故必存在正整数l使得dl=dl+1=…=d，因此d=GCD{nt

，

t=1，

2，…，

l

}，应用初等数论知识知必存在正整数N0

，使得对任一N≥N0都有

其中Nm

，

m=1，

2，…，

l皆为正整数。由nm的含义及C－K方程便有

当i

为正常返时，由定理5.3.2可立得结论(3)。

5.3.3状态间的关系

上一小节讨论了状态类型的判别问题，现在我们进一步讨论状态之间的关系以及具有一定关系的两个状态的类型之间的关系。首先引入状态之间的可达和互通。

定义5.3.7对给定的两个状态i，j∈S

，若存在正整数n使得p(n)ij>0

，则称从i可到达

j(简称为i可达j

)，并记为i→j。如果i→j和j→i同时成立，则称

i与j互通，记为i↔j。

从马氏链的转移概率图来说，所谓i可达

j，是指从节点i出发存在一条路可到达节点j;i与

j互通则是指从节点i出发存在一条路可到达节点j，同时从节点j出发也存在一条路可到达节点i(对于有向图，这两条路一般是不同的)。利用(5.3.5)式容易证明可达和互通的如下性质:

引理5.3.4

(1)(可达的传递性)若i→j，j→k，则i→k;

(2)(互通的传递性)若i↔j，

j↔k，则i↔k;

(3)(互通的对称性)若

i↔j，则j↔i。

我们也可用首达概率来刻画可达与互通。

引理5.3.5对i，j∈S，

i→j当且仅当fij>0;从而i↔j当且仅当fijfji>0。证明设i→j，则存在n≥1

使得p(n)

ij>0。由此及(5.3.5)式知，必有l=1，

2，…，

n使得f(

l)ij>0

，所以fij>0。反过来，由(5.3.5)式也容易证明。由此即知后一结论也成立。

下面我们来证明，互通的两个状态必具有相同的状态类型。

定理5.3.5设i和j互通，则i和j或者都是非常返的，或者都是零常返的，或者都是正常返非周期的(遍历)，或者都是正常返有周期的且具有相同的周期。

证明由于i↔j，所以必存在l≥1和n≥1

，使得α=p(l)ij>0，

β=p(n)ji>0。由C－K方程有

上式右边取k=s=j的那一项，得

同理可证得

如果j

为常返状态，则由定理5.3.1知由此及(5.3.26)式知∞，所以i也是常返状态。反过来，若i是常返状态，则由(5.3.27)式可类似证得j也是常返状态。所以i和j或者同为非常返，或者同为正常返。

由定理5.3.3的(3)及式(5.3.26)和式(5.3.27)可证得i和j中有一个零常返时另一也是零常返，有一个是正常返时另一个也是正常返的。

剩下所要证明的是di=dj

。由上可知p

(n+l)jj≥αβ>0

，因此dj必能整除n+l。任取m>0，使得p(m)ii>0，由(5.3.27)式有

由此可知dj必能整除

l+m+n，于是也必能整除m。所以dj为集合{m|p(m)ii>0}的公约数，即dj

≤di

。同样可证得di

≤dj

。因此，

di

=dj

。

对于常返状态，我们从可达可推得互通。

定理5.3.6设i≠j∈S，

j是常返态，

j→i，则j↔i，且fij=fji=1，从而i也是常返态。

证明令j

fji表示从状态j

出发最终到达状态i而中间不经过j

的概率，由于j→i，由引理5.3.5知

fji>0，从而推出自j出发，最终到i

而中间不经过j

的概率jfji>0。因此，必须在N≥1

使得从j

出发在N

时首达i而中间不经过j的概率jf(N)ji>0。假若fij<1

，则自j出发，最终不回到j的概率为

式中1-fij表示自

i出发最终不到达j的概率，这与假设j是常返态相矛盾。所以fij=1。从而i→j，因此i↔j。由对称性知fji=1，再由定理5.3.5知i也是常返态。

因此，从常返状态出发可到达的状态，也必定是常返的，且与之前的常返状态具有相同的状态类型。

5.3.4状态空间分解

上一节只是对单个状态的类型进行了讨论，现在，我们将从整体上来剖析齐次马氏链的状态空间S。如果我们约定i→i，则i↔i(称为互通的自反性)，从而由引理5.3.4知互通是状态空间S上的一个等价关系(称一个自反、对称、传递的关系为等价关系)。由等价关系的性质可知，它将S

划分成有限或可列多个互不相交的子集S1

，

S2

，…:

这里同一个子集Sn

中的所有状态互通，不同子集中的状态不互通。上式表示，任一个状态必属于其中的某一个Sn

，而且只属于其中的一个。(自然，单向的可达是允许的，即可能有i∈Sm

，

j∈Sn

，

n≠m，使得i可达j，但j不可达i。)因此，

Sn在如下意义上都是最大的:不存在i⋷

Sn使得Sn中添加i后所有状态仍是互通的。

我们称Sn是一个等价类，包含i的等价类也常记作S(

i)。易见

下面讨论等价类的性质。

定义5.3.8设C是S的一个子集，如果在C之外的任一状态都不能自C内任何一个状态到达，则称C为一个闭集。如果单个状态i构成的集{i}是闭集，则称i是吸收状态。如果闭集C中不再含有任何非空闭的真子集，则称此C是不可约的(或不可分的，或极小的，或最小的)。闭集是存在的，因为整个状态空间S总是闭集。当S不可约时，我们称此马氏链是不可约的，否同称为是可约的。

以下两个引理刻画闭集的性质。

引理5.3.6(1)C是闭集当且仅当

(2)i为吸收态当且仅当pii=1，即从状态i出发以概率1永远停留在状态

i上。

证明(1)C是闭集的定义，这是指

因此必要性是显然的。而充分性可由C－K方程用归纳法证得。具体求证作为练习题留给读者。

(2)证明是简单的。

引理5.3.7等价类S

(i

)若是闭集，则必定是不可约的。

证明设C⊂S

(i)是一个闭集，任取j∈C，则由闭集的定义知，若

j→k，则k∈C。而由等价类的定义知，对任一k∈S(i

)均有j→k，从而k∈C，即S(i)⊂C。因此，

C=S(i)，

S(i

)是不可约的。

由此引理不难得到以下推论。

推论5.3.1齐次马氏链不可约的充要条件是它的任意两个状态均互通。

等价类不一定是闭集，实际上，如果S(i)包含有非常返状态且S(i)有限，则S(i)不是闭集(见后面将要介绍的定理5.3.11，例5.3.1)，当S(i)包含有常返状态时，具有以下结果。

定理5.3.7对任一常返态

i，包含i

的等价类S(

i)是不可约闭集。

证明任取j∈S(i)，

k∈S，若j→k，则由定理5.3.6知j

与k

互通，从而k∈S(i)。因此S

(i

)是闭集，再由引理5.3.7知S(i)是不可约的。

有了上述准备之后，我们就可得到以下的关于状态空间的分解定理。

定理5.3.8(分解定理)齐次马氏链的状态空间S可唯一地分解成有限多个或可列多个互不相交的状态子集，

D，

C1

，

C2

，…之并，即

其中(1)D是所有非常返态所成之集。

(2)每个Cn

，(n=1，

2，…)均是由常返状态组成的不可约闭集，其中的状态互通，从而Cn中的所有状态具有相同的状态类型:或者均为零常返，或者均为正常返非周期(遍历)，或者均为正常返有周期且有相同的周期;而且对i，

j∈Cn

，fij=1。

证明将所有非常返态组成子集D，则对常返态i∈S-D

，由定理5.3.7知包含i的等价类S(i)是不可约闭集，因此将这些包含常返态的等价类依次记为C1

，

C2

，…，由定理5.3.5和定理5.3.6即知(2)中结论成立。

基于定理中的(2)，我们以后将Cn中状态的类型称为是Cn的类型，

Cn中状态的周期(如存在)称为Cn的周期。

顺便指出，

D可以是闭集，也可以不是闭集。

基于以上分解定理，我们将S

中的状态次序按照D，

C1

，

C2

，…重新排列，则转移概率矩阵P将有以下规则的形式:

其中P1

，

P2

，…均是随机矩阵，它们所对应的链都是不可约的，我们将P的以上形式称之为转移概率矩阵的标准形式。为求得n步转移概率矩阵，由标准形式，我们可假定

由此，不难验证Q

n，

m

具有如下递推式:

从而可推得

因此在求n步转移概率矩阵时，我们可将P

写成标准形式(5.3.28)式，然后按(5.3.29)式求Pn

。当PDm

=0

时，

Q

n

，

m≡0，

n≥1。如此计算将可节省不少的工作量。

从前文所述的定理以及P

的标准形式出发，我们不难发现首达概率矩阵F

=(fij)也具有如P

的标准形式:

而且F

n

是元素全为1的方阵，维数同常返类Cn

中的状态数。关于F

Dm

中元素的计算，读者可参阅参考文献[12]等。

不难看出如果马氏链的初始状态在常返类Cn

中，即初始状态分布q

满足qi=1，则马氏链的状态将永远停留在Cn

中。因此可将马氏链局限在Cn

中而得到一个不可约的马氏链。鉴于定理5.3.8，对马氏链很多性质的研究就可转化为对不可约马氏链的研究。

当Cn

是周期链时，我们还可对P

n

作进一步的研究。

定理5.3.9(周期链分解定理)设X是一个周期为d

的不可约马氏链，则其状态空间S可进一步分解成d个互不相交的子集J1

，

J2

，…，

Jd

，使得

其中我们约定Jd+1=J1。

证明设i

是一个固定的状态，记

根据以上定理，对周期为d

的不可约马氏链X

，将状态按J1

，

J2

，…，

Jd

重排后，转移矩阵P

可表示为

其中P(r)ij中的i∈Jr

，j∈Jr+1。我们可以引入新的转移矩阵，把周期链化为非周期链来研究。

定理5.3.10设X是周期为d

的不可约链，转移矩阵为P

，其状态空间的分解J1

，

J2

，…，

Jd如定理5.3.9中所示，则在以Q=P

d

为转移矩阵的马氏链X'中，

J1

，…，

Jd均是不可约非周期的状态闭集。

证明由(5.3.34)式，

Q

有如下形式:

而Q(r)=P(r)…P(d)P(1)…P(r-1)，它定义在Jr

上(r=1，2，…，

d)。这表明在以Q

为转移矩阵的马氏链中，原来链X

中的d步只相应于

X‘中的一步，故新链中的状态是非周期的。

当状态空间

S为有限集时(或者某个常返类Cn有限时)，马氏链将具有一些特殊的性质。

定理5.3.11

(1)非常返状态集D

若是闭集，则必定是无限集;

(2)零常返类Cn

不可能有限;

(3)S

有限时，

D不可能是闭集，也不存在零常返状态。

证明(1)设D为有限闭集，则

令n→∞，因为D有限，故极限号与求和号可交换次序，再由定理5.3.1可得

上式矛盾。

(2)可用类似方法证明。

(3)可由(1)和(2)得到。

至此，我们完全搞清了马氏链的结构(状态结构与转移概率矩阵的结构)，下面来看一个例子。

例5.3.1设X

为一齐次马氏链，状态空间为S={

a，

b，

c，

d，

e}，转移概率矩阵为

试分析其状态类型。

解画出其状态转移概率图，如图5－1所示。从图中不难发现C={a，

c，

e}是一个状态闭集，

D={b，

d}是非常返状态集，自然C

是正常返的而且是非周期的。

如果我们能够发现转移矩阵能够重排为

这相当于将状态的次序重排为S={a，

c，

e，

b，

d}。由上及P

的标准形式即知非常返态集D={b，

d}和遍历态集C={a，

c，

e}。D

和C

也是S

的两个等价类，显然C是闭集，

D

不是闭集。

我们提请读者考虑D

是否一定是一个等价类。图5－1状态转移图

例5.3.2设一齐次马氏链的状态空间为S={1，

2，

3，

4，

5，

6，

7，

8}，转移概率矩阵为

比较此矩阵与不可约周期链的转移概率矩阵的标准形式(5.3.34)可知，本马氏链是一周期为4的正常返不可约链，

J1={1}，

J2={2，

3，

4}，

J3={5，

6}，

J4={7，

8}。

例5.3.3设一齐次马氏链的状态空间为S={1，

2，

3，

4，

5，

6，

7，

8，

9}，其转移概率矩阵有如下形式:

其中*表示正的一个数，其余均为零。从前面所进行的讨论不难发现，为了确定一个齐次马氏链的状态类型，其实只需要知道转移概率矩阵中的非零元素的位置就够了。

容易推知，

p11=1，因此1是一个吸收态，周期为1，故C1={1}为一个遍历类;由于p71>0，故7∈D，而可达7的状态都属于D，从P的第7列可知8，

9∈D;划去P中的第1，7，

8，

9行和1，

7，

8，

9列，在所得的子矩阵中，可以看出C2={2，

3}和C3={4，

5，

6}均是正常返类;C2的周期为2，其分解为{2}和{3}，

C3

的周期为1，因为p55>0。

例5.3.4设一齐次马氏链的状态空间为S={0，

1，

2，…，}，其转移矩阵如下(状态转移图如图5－2所示):

试讨论此链是常返链的充分必要条件。图5－2状态转移图

链是不可约的，因此只要确定其中某一个状态是常返的条件即可。为此我们选择其中较为特殊的状态0。由矩阵P可得

因此，状态0是常返态(f00=1，从而链是常返链)的充要条件是

p0p1…pN=0。此条件相当于以下正项级数发散:

反之，如果级数收敛，则该链为非常返链。例如，

此时的马氏链为常返链。

此时的马氏链为非常返链，而且

5.4转移概率的极限与平稳分布

本节探讨马氏链X={X0，

X1，…}的稳定性，即

P{Xn=j}是否存在，若存在是否是一个概率分布。为此，主要考察n步转移概率p(n)ij当n→∞时的极限是否存在，若存在则是否与初始态i无关，进而，若πj=

p(n)ij存在且与

i无关，则{πj，

j∈S}是否构成一概率分布?

5.4.1

转移概率的极限

为讨论n步转移概率p(n)ij的极限情况，由(5.3.29)式可知我们只须讨论i是非常返态或者i是常返态且j与i属同一常返类(某Cm

)的情形。首先，我们有

定理5.4.1设j∈S是非常返状态或零常返状态，则

基于此定理，下面假定

j是正常返态且i非常返或者

i与j

属同一常返类。注意到定理5.3.3，

p(n)jj当j有周期时极限不存在，因此一般地讨论p(n)ij的极限将无意义。考虑到周期链的性质(定理5.3.9)，我们转而考虑p

(ndj+r)ij当n→∞时的极限问题，

r=1，

2，…，

dj

。为此，引进如下概念:

fij(r)表示从状态i出发，在某时刻n≡r(moddj)首先到达状态j

的概率。不难看出

定理5.4.2设

j为正常返态，则以下极限存在，且

关于(5.4.4)式中的fij(r)，由定理5.3.9我们有以下推论。

推论5.4.1设X

是有周期d的不可约马氏链，状态空间的分解J1，

J2

，…，

Jd

如定理5.3.9中所示，则对r=1，

2，…，

d，

i∈Ji

，

j∈Jm

，

我们将上面的结果总结如下。

定理5.4.3设S=D∪C0∪C+1∪C+2

∪…，其中D

为非常返态集，

C0为零常返态集，C+

1，

C+2，…为正常返状态闭集，则

但j∈C+m时的收敛子列要由定理5.4.2和推论5.4.1给出。

上面我们基本上解决了n

步转移概率的极限问题，其中如上所述对某些类型的i与j

，{p(n)ij，

n≥1}中有dj

个收敛子列。极限不存在的原因是周期的影响。因此如能消除周期的影响，极限也就存在了。为此，我们考虑p(n)ij算术平均的极限。

定理5.4.5对任意的i，j∈S

，如下极限存在且

证明首先注意到数学分析中的一个结论:设数列an

有极限a

，则

由此及定理5.4.3即知(5.4.7)式中的第一式。对于第二式，设N=Mdj+R，

R=1，

2，…，

dj

，则由定理5.4.2及以上结论知

如记Π

是第(i，

j)元为πij的矩阵，则Π

有如下性质。

(2)由法都引理，对i，

j∈S

但

故前式中恒成立等号。因此ΠP=Π。

(3)由已证结果知

令N→∞，由控制收敛定理可得

从而可得Πn=Π。

最后，由已证结果可证得(P-Π)2

=P2

-PΠ-ΠP+Π2

=P2-Π2

，用归纳法可证得(P-Π)n

=Pn-Πn

。

关于矩阵Π

，注意到P

的标准形式(5.3.28)式，结合(5.4.7)式，不难给出Π

的分块形式为

对Πn

，由(5.4.7)式知它的每一行均相同，为

由于它是从P

得到的。我们要问它是否是概率分布。我们有以下进一步的结果。

定理5.4.7设C+h为马氏链的一个正常返子类，则

构成一概率分布。从而(5.4.8)式中相应

的Πh

各行均相同且为σ(h)，即Πh=eσ(h)，e是分量全为1的列向量，维数同|C+h

|。

证明简记C+h为C，设C有周期d，则由法都引理及定理5.4.2可知对i∈C有

从而

我们说其中均成立等号，因为否则，

取n=md+r，令m→∞，由控制收敛定理，得

以上定理说明Πm

是各行相同均为σ

(m)的一个随机矩阵。至此，我们对n

步转移概率的极限性态作了较为全面的研究。关于ΠD1

，

ΠD2

，…的进一步讨论可见参考文献[14]。

进而，若X是不可约正常返的，则

它与初始状态i

无关。

与例5.2.1一样，

r

(i

)和v(i)可有多种不同的解释，如r(i)可解释为系统在i处运行一个周期的报酬(如服务系统所得的服务报酬)、运行一个周期的平均时间等;相应地，

v(

i)则分别是长期运行每周期平均期望报酬和平均期望时间。

5.4.2平稳分布

首先，我们给出平稳分布的定义。

定义5.4.1称概率分布{πi，

i∈S}是马氏链X

的一个平稳分布，如果

上式用向量形式可写为

由(5.2.5)式知，若马氏链的初始分布是一个平稳分布π

，则X

n的概率分布向量q(n)为

亦即当马氏链的初始分布为平稳分布时，其绝对概率分布将保持不变。

注意到第2章中所定义的严平稳过程，(5.4.10)式相当于说X的一维分布是平稳的。实际上，我们有以下结论。

定理5.4.8设马氏链的初始分布π是平稳分布，则X是严平稳随机过程。

证明任取非负整数t1

，

t2

，…，

tn

及m

，状态i1