《随机过程》课件第6章

第6章更新过程与马尔可夫更新过程6.1更新过程的定义6.2更新方程与极限定理6.3剩余寿命与现时寿命6.4延迟与终止过程6.5马尔可夫更新过程的定义6.6状态分类与极限概率6.7马尔可夫更新方程与极限定理6.8再生过程与报酬过程6.9广义半马氏过程简介习题六

更新过程是Poisson过程的推广，将其与马尔可夫过程结合就得到了马尔可夫更新过程(也称为半马尔可夫过程)，这两类随机过程具有广泛的应用。本章将分别介绍它们。

6.1更新过程的定义

在2.6节中我们知道Poisson过程是这样一类计数过程:其任意两次相邻的到达间隔时间是相互独立同参数指数分布的。比这含义再广一点的是到达间隔时间相互独立同分布但分布函数可以任意的计数过程，这就是更新过程。这类随机过程描述在一系列时刻点上系统变新(称之为更新)且两相继更新时刻点(称为更新点)的间隔是独立同分布的随机系统，刻画此类系统的是两相邻更新点间隔时间的分布函数。

正式地，设{Xn

，

n=1，

2，…}是相互独立的非负随机变量，分布函数均为F(t)，假定F

(0)<1(请读者考虑:当F(0)=1时将会怎样)。由于Xn

非负，故EXn

存在(可能是无穷)，记

这里，μ是平均(期望)更新间隔时间，

Tn是第n

次更新发生的时间，于是N

(t

)表示系统在[0，

t]中发生的更新次数。由于Xn

独立同分布，因此系统在时刻T1，

T2

，…与新的一样重新开始。

我们说N

(t

)是有限的，从而是随机变量。实际上，由强大数定律知以概率1有Tn/n→μ，所以Tn≤t以概率1只对有限多个n

成立，从而N

(t)以概率1有限。

定义6.1.1称{N

(t)，

t≥0}或{T0，

T1

，…}是更新过程，称Tn

为第n个更新点，称F为更新分布(函数)。

更新论的主要目的是由Xn

的分布函数F

(t)导出有关N(t)和Tn

的一些有用的性质。例如，[0，

t]中的期望更新次数

称之为更新函数。

由于独立随机变量和的分布函数是各随机变量分布函数的卷积，因此Tn

作为X1

，

X2

，…，

Xn

的和，其分布函数

其中Fn

(t)是F(t)的n

重卷积:F

1(t)=F(t)，而

同时，由(6.1.2)式易知，

Tn与N(t)有以下关系:

于是

由此，我们可得到更新函数的一个表达式

由于Fn

(t

)非负，以上级数自然是有定义的。如下引理进一步说明更新函数是有限的。

引理6.1.1m

(t)<∞，

t≥0。

证明由Xn

的独立同分布性知，

Xm+1+…+Xn

与Tn-m同分布函数，因此Tn的分布函数等于Tm

的分布函数与Tn-m的分布函数的卷积。因此由分布函数的单调性知

特别地，对任意的正整数n，

r，

k，有

由此递推可得

因此对任意的正整数r

，有

对t≥0，若Fr

(t

)<1，则以上级数是几何收敛的，而由强大数定律知Tn

以概率1趋于∞，因此，对任一t≥0，必有r使得Fr

(t)=P{Tr≤t}<1。

由(6.1.8)式可知，

m(t)是非降函数，进而，由级数在任一区间[0，

t]中的一致收敛性及分布函数的右连续性知m

(t

)也是右连续的。因此，除了m(∞)≠1(实际上m(∞)=∞)外，m

(t)具有与分布函数类似的性质。

上面，我们讨论了由分布函数F

确定更新函数m

的问题。反过来，这也是成立的。

引理6.1.2分布函数F

(t)与更新函数m(t)相互唯一确定。

证明在(6.1.8)式中取拉普拉斯变换可得

由于一个函数与其拉普拉斯变换间相互唯一确定，

F

与m

也相互唯一确定。

下面给出更新过程的几个例子。

例6.1.1

(1)Poisson过程。比率为λ的Poisson过程N(t)是相邻更新点间隔时间服从参数为λ的指数分布的更新过程。

(2)计数过程。由记录仪器(称之为计数器)所记录的相继到达的电子脉冲或信号的间隔时间常常是独立同分布的。此时的计数过程是更新过程。

(3)交通流。具有足够长的高速公路的某个车道中的相继汽车间的距离可看作是独立同分布的，从而形成一个更新过程;同样，通过某一地点的汽车数可看作是一个更新过程。这是两个更新过程，分别是从空间上和时间上来描述公路上的汽车流的。

(4)排队系统中的更新过程。在一个单服务台的排队系统中有多个更新过程。如①顾客的到达过程常看作是一个更新过程;②顾客按一更新过程到达时，相继忙期的开始时间形成一个更新过程，这里忙期是指服务员忙的时期;③当顾客按Poisson过程到达时，相继忙期的结束时刻是一个更新过程;④当服务时间是指数分布时，服务完的顾客的离去也形成一个更新过程。

(5)生产/存储系统。在大多数生产/存储系统中，需求的到达常假定是更新过程，在多种存储策略下，库存的相继恢复时间等也构成更新过程。

(6)系统更换。设有一系统，其寿命为X

，当其失效时用同一类型的系统更换之，更换时间为Y

。于是若记Xn

和Yn

分别为第n

次寿命和第n次更换时间，当{Xn+Yn

，

n=1，

2，…}独立同分布时就成为一个更新过程。

(7)在马氏链{Xn

，

n=0，

1，

2，…}中，对状态j记

则在X0=j

的条件下，

Zn

是独立同分布的，从而产生一个更新过程。

(8)更新过程还出现在保险、人口增长、遗传进化、工程系统、经济系统等众多领域中。

6.2更新方程与极限定理

设函数g(t

)和h(t)都定义在[0，

∞)上，

F(t)是非负分布函数，它们有如下关系:

如果h

(t

)和F(t)已知，而g(t)未知，则g(t)可看作是以上积分方程的解。(6.2.1)式是一特殊的积分方程，我们称之为更新方程。在更新理论中，有许多量都满足更新方程，例如更新函数m

(t

)。实际上，由全期望公式可得

当第一次更新发生时间x≤t时，从x

开始，系统与新的一样，于是[0，

t]中的期望更新数等于发生在x

上的更新数1加上在(x，

t]上的期望更新数;而当x>t时，[0，

t]中没有更新。

因此

代入上式得

这是较为特殊的更新方程，已知函数F，求函数m。

更新方程的解由以下定理给出。

定理6.2.1更新方程(6.2.1)式的解为

证明注意到(6.2.1)式的卷积形式为g=h+g*F，取其拉普拉斯变换可得

由此及(6.1.10)式得

取拉普拉斯反变换即得(6.2.3)式。

现在，我们考虑m

(t

)的极限性态。由于平均更新时间是μ

，即平均每隔时间μ

就发生一次更新。因此容易猜想当μ<∞时，

N(∞)∶=

N(t

)=∞。所以考虑m(t)的极限一般地没有什么意义。与马氏链中(定理5.4.5)类似，我们考虑单位时间内的平均更新次数，即N

(t)/t

的极限。从其含义容易猜想其极限应是1/μ

。正式地，我们有以下定理。

定理6.2.2以概率1有

证明由N(t)的定义易知

因此

由于N(∞)有限当且仅当有n

使得Tn=∞

，于是

故N(∞)以概率1等于∞，也即当t→∞时，

N(t)以概率1趋于∞。而由强大数定律知以概率1有Tn/n→μ。因此当t→∞时，以概率1有

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

关于单位时间平均期望更新次数，即m

(t

)/t

的极限，易知它亦应等于1/μ，但其证明将稍为复杂一些。以下我们先给出停时的概念。

定义6.2.1称取正整数值的随机变量N

是随机序列{X

n

，

n≥0}的一个停时，如果对任一n

，事件{N=n}与

Xn+1，

Xn+2，…相互独立。

直观上，我们一个一个地观察{Xn

，

n≥0}，而N

表示停止观察的时间，

N=n表示在观察了X1

，

X2

，…，

Xn

之后，但在观察Xn+1，

Xn+2，…之前停止。于是，停时表示何时停止只与已观察的随机变量有关，而与未观察的无关。

例6.2.1设{Xn

，

n≥0}相互独立，

(1)若P{Xn=0}=P{Xn=1}=1/2，记

则N是一个停时。

(2)若P{Xn=-1}=P{Xn=1}=1/2，则以下定义的N

也是一个停时:

定理6.2.3(Wald方程)设X1

，

X2，…独立同分布，

EX1

有限，

N

是一个停时且EN有限，则

证明记χ为示性函数，由停时的定义可知N≥n表示在观察了X1

，

X2

，…，

Xn-1之后不停止，因此随机变量χ(N≥n)由X1

，

X2

，…Xn-1确定而与Xn

独立。因此

请读者考虑这里能否运用全期望公式?

例6.2.1(续)对(1)应用Wald方程有

所以EN=20。

若对(2)应用Wald方程，则有

不成立，这只能说明EN=∞，定理6.2.3中的条件不满足。

定理6.2.4(基本更新定理)

证明首先，我们假定μ<∞。为应用Wald方程，我们需要为更新过程构造一个停时，注意到

或者

因此N(t

)+1是一个停时(但N(t)不是停时)。进而E(N(t)+1)=m(t)+1<∞。故由Wald方程得

由此及TN

(t)+1≥t

可得μ(m(t)+1)≥t，从而

定义6.2.2称非负随机变量X是格的，如果有正常数d使即X取值于d的整数倍上，最大的d称为X的周期。当X是格随机变量时，其分布函数也称为是格的。如果X没有周期，则称之为非格随机变量。

以下两个定理的证明可参见参考文献[31]。

定理6.2.5(Blackwell定理)(1)若F非格，则对任一a≥0有

(2)若F

是格的且有周期d，则(6.2.9)式对a=nd成立，

n=1，

2，…。

(6.2.9)式表示当时间足够长之后，在任一长度为a

的区间中的期望更新次数为a/μ。

定理6.2.6(关键更新定理)(1)若F(t)不是格的，

h(t)直接可积，则

其中约定1/∞=0。

(2)若F是格的且有周期d，函数h直接可积，则对任一a≥0有

关键更新定理是非常重要而又有用的一个结果。在应用中，将某更新时间作为条件，导出一个更新方程，对此应用定理6.2.1得到更新方程的解，就可应用关键更新定理了。下面来看几个例子。

例6.2.2(交替更新过程)考虑一个系统，其工作寿命为X1

，发生故障后进行修理，修理时间为Y1

，修复后系统与新的一样，工作寿命为X2

，故障后的修理时间为Y2

，…，假定Xn

相互独立同分布函数F，

Yn

相互独立同分布函数G，{Xn

}与{Yn

}也相互独立。记H=F*G为X1+Y1的分布函数，

A(t)=P{系统在t时工作}。

命题6.2.1若E(X1+Y1)有限，

H不是格的，则

证明记事件E={系统在t时工作}，则由全期望公式可得

所以

于是得到如下更新方程:

由此还可知

例6.2.3(更新报酬过程)设N(t)是一更新过程，

Xn

是更新点间隔时间，

Yn

是第n

次更新时系统获得的报酬(可为负)，

Yn

可与Xn

有关，但假定(Xn，

Yn

)，

n=1，

2，…相互独立同分布。记

表示到t时所获得的总报酬。

命题6.2.2若E|Yn

|和EXn均有限，则

当t→∞时。

由于ε任意，所以g(t)/t→0，结论成立。

6.3剩余寿命与现时寿命

更新论中讨论的随机变量还有剩余寿命、现时寿命和总寿命等三种，三者分别定义如下:

三者的关系如图6－1所示。图6－1剩余寿命γt、现时寿命δt和总寿命β

定理6.3.1γt

的分布函数如下:

进而，若F为非格，则

证明首先注意到由于TN(t)≤t，故

记P(t)=P{γt>x}，将X1作为条件有

从而

对以上更新方程应用定理6.2.1和关键更新定理可得当F为非格时，

由以上两式及P{γt≤x}=1-P(t)即可分别得到(6.3.1)式和(6.3.2)式。

当F为格时，

γt

的极限分布请读者给出。

与(6.3.3)式类似，我们还有

由此及定理6.3.1即可得到有关δt

的分布函数以及(δt，

γt

)的联合分布函数所满足的更新方程和极限分布。具体结果请读者写出。

最后，关于总寿命βt的分布函数，我们既可从(6.3.5)式类似得到，也可直接应用定理6.3.1证明中的方法得到。记Q(t)=P{βt>x}，由于

其中x∨t=max{x，

t}。则由全期望公式可得更新方程

由此即可得到以下定理。

定理6.3.2

进而，当F

为非格时，

由(6.3.2)式和(6.3.8)式可知，

γt和βt

的极限分布相同，且当μ有限时，它们仍是分布函数。

6.4延迟与终止过程

我们先来讨论延迟(delayed)更新过程。在很多计数过程中，第一个更新间隔时间的分布函数与其余的不同，例如在某个非更新点t>0处开始观察系统，以及在例6.1.1的(7)中当X0=j≠i时。

正式地，设{Xn

，

n=1，

2，…}相互独立，

X1

有分布函数G，

X2

、X3

、…有相同的分布函数F

，记Tn同(6.1.1)式中，而将(6.1.2)式中定义的N

(t)记为ND(t)，这里用下标D

以示区别。

定义6.4.1称随机过程{ND

(t)，

t≥0}为延迟更新过程。与N

(t

)中类似，我们可得

其中F0(x)=1，

*号表示卷积，而G*F0=G。记(延迟)更新函数mD(t)=END(t)，则

其中m(t)是更新分布为F的更新函数。仍记

以下定理的证明留给读者。

若F为格的且有周期d，则(6.4.5)式对a=nd成立，

n=0，

1，

2，…。

以下假定μ<∞，此时

是一分布函数，称为F的平衡分布，其拉普拉斯变换为

当G=Fe

时的延迟更新过程是特别重要的，我们称之为平衡更新过程。由(6.3.2)式知，当开始观察系统的时间t充分大时，可将之看作为平衡更新过程。记γDt

表示延迟更新过程ND

(t)中的剩余寿命。以下定理的证明可见参考文献[25]的定理3.15，它说明了“平衡”的含义。

定理6.4.2对平衡更新过程:

由定理6.4.1知，

Fe是原更新过程N(t)中t时的剩余寿命γt

的极限分布;而由定理6.4.2的(2)知，在平衡更新过程ND(t)中剩余寿命γDt

的分布函数保持不变，就为Fe，这也是“平衡”的含义之一。定理6.4.2的(1)和(3)还说明了“平衡”的另两个含义。

直到现在为止，我们一直假定更新分布F是通常的分布函数，即F(∞)=1。但定义6.1.1对F(∞)<1(即P{Tn+1-Tn=∞}>0)也是成立的。

定理6.4.3F(∞)=1⇔EN(∞)=∞⇔P{N(∞)=∞}=1。

证明设F(∞)=1，由于N(∞)有限当且仅当有n使得Xn=∞，因此

由此可得EN(∞)=∞。另一方面，若F(∞)<1，则第一次更新后，系统以概率1-F(∞)不再更新，因此

则N(∞)是均值为F(∞)/[1-F(∞)]的几何分布，于是P{N(∞)<∞}=1，

EN(∞)=F(∞)/[1-F(∞)]<∞。

基于以上定理，我们给出如下定义。

定义6.4.2称F(∞)=1时的更新过程为非终止的或常返的，称F(∞)<1时的更新过程是终止的或非常返的。

在应用中所研究的随机过程本身并不一定是更新过程，但其中可能存在一嵌入更新过程，且往往不知更新分布是否满足F(∞)=1，此时，定理6.4.3就变得很重要。

关于更新过程的进一步讨论可参阅参考文献[25]、[31]、[32]。

6.5马尔可夫更新过程的定义

将Poisson过程中的更新分布一般化就得到了更新过程。而从连续时间马尔可夫过程的理论知道，它在每个状态处的逗留时间是指数分布的(参数依赖于所处状态)。与更新过程一样，将此指数分布一般化，就得到了所谓的马尔可夫更新过程，也称为半马尔可夫过程。它是马尔可夫过程和更新过程的结合，从而广于这两者。

设对n=0，

1，

2，…，随机变量X

n

取值于一可数状态集合S

，随机变量Tn取值于[0，

∞)，且0=T

0≤T

1≤T2≤…。我们不妨设S={0，

1，

2，…}。

定义6.5.1称二元随机过程{X，

T}={Xn

，

Tn，

n=0，

1，

2，…}为马尔可夫更新过程，简称为马氏更新过程，如果

对所有的n，i0

，…，

in

，

j，

t0

，…tn

，

t均成立。

我们在这里考虑时齐的情形，即

与n

无关。称矩阵函数Q

(t

)=(Qij(t

))为状态空间S

上的半马尔可夫核，简称为半马氏核。

定义

其中当pij=0时，由定义知Qij(t

)≡0，此时Qij(t

)/pij可任意取值，它不影响我们的讨论，但为确定起见，我们约定此时Fij(t

)是常数1的分布函数。pij和Fij(t

)均有它们自己的概率

含义。我们先来看pij。由定义，

P=(pij)构成一个随机矩阵，从而是某个马氏链的转移概率矩阵。实际上，由(6.5.1)式和(6.5.2)式易知

于是得到以下定理。

定理6.5.1X={Xn

，

n=0，

1，

2…}是状态空间为S

、转移概率矩阵为P=(pij)的齐次马氏链(称之为嵌入马氏链)。

再来看Fij(t

)。不难看出，对任意的i，

j∈S，Fij(t)是一个分布函数，实际上，

引理6.5.1对任意的n≥1，

t1

，…，

tn

≥0，

以上引理是说当已知马氏链{Xn}时，

T1-T0

，…，

Tn-Tn-1

是相互独立的，而且Tn-Tn-1

的分布函数仅仅依赖于

Xn

和Xn-1。

当系统只有一个状态时，即

S为单点集时，容易看出{Tn

，

n=0，

1，

2，…}是更新过程。更一般地，我们有以下定理，其证明可见参考文献[32]。

定理6.5.2对状态j∈S，定义Nj

(t

)为在(0，

t]中达到状态j的次数，则Nj

(t)是一个更新过程或延迟更新过程。

对Nj

(t

)的更新时刻，设Zn

由例6.1.1的(7)中定义，则第n个更新时刻点为Tjn=TZn。设Kj

表示在嵌入马氏链X

中的首次到达状态j的时间，在初始条件X0=i下，其分布由f(k)ij给出，则对n≥0，

Tjn+1-Tjn

与TKj同分布，从而

因此，在初始条件X0

=j下，

Nj

((t)是更新过程;而在X0=i≠j时，一般地Nj

(t)仅是一个延迟更新过程。

定理6.5.1和6.5.2说明了“马尔可夫更新过程”是马尔可夫过程和更新过程相结合的产物。

马氏更新过程也可以从另一角度描述。我们构造随机过程Y={Y(t)，

t≥0}如下:

其中，

Δ∈S为一记号;supnTn

是过程的终止时间。从而Y(t)=Δ表示马氏更新过程已经结束。

Y

是一个一元随机过程，

Y(t)可解释为某系统在t时的状态，此系统在状态处停留一段时间后转移到另一个状态，停留时间区间[Tn

，

Tn+1)的长度是随机的，其分布依赖于所停留的状态Xn

和下一步将要到达的状态Xn+1。它相继到达的状态形成一个马氏链，当已知此马氏链时，它相继的停留时间相互独立。

定义6.5.2称随机过程

Y={Y(t)，

t≥0}为半马尔可夫过程，简称为半马氏过程；称Q

(t)为其半马氏核，

X={Xn

，

n=0，

1，

2，…}为其嵌入马氏链。

这里用“半马氏过程”是因为Y具有“某种”马氏性:已知现在、将来与过去无关，只是这里的“现在”应是状态转移时刻，即某个

Tn

。

本章以下将不再区分半马氏过程与马氏更新过程。

下面讨论在有限时间区间内是否会发生无穷多次状态转移的问题。首先，定义

自然，

Qi

(t

)是在状态i处逗留时间的分布函数，即

本章中恒假定Qi(0)<1，

∀i∈S。对t≥0，仍记N(

t)=sup{n|Tn≤t}，不难证明

定义6.5.3称状态i

是正则的，如果

称马氏更新过程是正则的，如果所有状态均是正则的。

由本章第一节可知，对任一i∈S，{Ni

(t)，

t≥0}是一个更新过程(可能延迟)，且以概率1有Ni

(t

)对任意的t均有限。因此，当状态数有限时，以概率1有

所以，有限状态马氏更新过程必定是正则，但状态可数时就不一定了，反例如下。

例6.5.1设对某马氏更新过程有

则

因此，此马氏更新过程没有正则状态。

但如下定理说明在一定条件下，马氏更新过程就是正则的。

定理6.5.3(正则性定理)若以下两个条件之一成立，则马氏更新过程是正则的:

(1)存在常数δ>0和ε>0，使

(2)对任一i∈S，在X0=i的条件下，马氏链{Xn

，

n=0，

1，

2，…}以概率1到达某一常返状态。

证明可见参考文献[25]的命题5.1。定理中的条件(1)和(2)均称为正则性条件。

以下我们假定所讨论的马氏更新过程总是正则的。

现在来看几个例子。

例6.5.2如果有非负数组{λi

，

i∈S}使

则由(5.5.19)式和(5.5.21)式知Y是马氏过程。因此，马氏过程是特殊的半马氏过程。

例6.5.3交通流。设T0，

T1

，…是某高速公路上相继车辆的位置(时间或空间上的)，记Xn

为第n

辆车的类型(如小车、卡车、公共汽车、重量、大小、速度等)，通常Xn

是一个马氏链，而Tn+1-Tn

仅与类型Xn

和Xn+1有关，从而(X，

T)是一个马氏更新过程。

例6.5.4M/G/1排队。顾客按率为λ的Poisson过程到达，服务时间相互独立同分布函数G

，一个服务台。记T0=0≤T1≤T2

≤…为顾客的相继离去时间，

Xn

为第n

次离去后系统中的顾客数，则(X，

T)={Xn

，

Tn

，

n=0，

1，

2，…}为马氏更新过程，其核为

其中

6.6状态分类与极限概率

马氏更新过程同时具有马氏链和更新过程的很多性质。我们先来讨论马氏更新过程的状态分类，它与马氏链中的状态分类类似。首先，对状态i，j∈S和t≥0，定义

Gij(t)表示过程从状态i

出发在t

之前到达状态

j的概率。若以Tj

1

表示更新过程Nj

(t)中第一次更新时间，则显然有Gij(t)=P{Tj

1≤t|X0=i}。Gij(∞)表示从i出发，终究要到达j的概率。Pij(t)相应于连续时间马氏过程中的状态转移概率。

基于Gij(t)，我们定义从i出发到达j的期望时间为

于是称μii

为状态i

的平均返回时间。

现在，我们给出各类状态的定义，以及马氏链中相应定义的推广。

定义6.6.1(1)称状态i

可达

j，如果i=j或者Gij(∞)>0;称i

和

j互通，如果

i可达

j且

j可达

i;

(2)称状态

i是常返的，如果Gij(∞)

=1;否则，称状态i是非常返的(或瞬时的);

(3)称常返状态i

是正常返的，如果μii

<∞;否则称状态i是零常返的;

(4)互通是一个等价关系，等价类简称为类，记Ci为包含状态i

的等价类;

(5)称马氏更新过程(半马氏过程)是不可约的，如果它只有一个类，即所有状态互通。容易猜想，马氏更新过程(X，

T)中的状态性质与嵌入马氏链X

中的状态性质有密切关系。为此，首先注意到(X，

T)和X

间的如下关系:

由此公式不难得到以下定理。

定理6.6.1状态i在马氏更新过程(X，

T)中常返(或非常返、互通)当且仅当状态i在嵌入马氏链X

中常返(或非常返、互通)。

由此定理可知，(X，

T)有与X

相同的状态类。为讨论(X，

T)和X

中正常返(或零常返)间的关系，我们需要在(X，

T)和X中有关正常返的判别准则之间架起一座桥梁。

定义ηij为过程从i

出发下一步到达

j的条件下，在i的期望逗留时间;ηi为过程在

i的期望逗留时间。它们分别用公式表示为

现在，利用n

时首次到达状态j

，中间依次经过i1≠j，…，

in-1≠j作为条件，由全期望公式可得

定理6.6.2对常返状态i，设类Ci有限，则i

在马氏更新过程(X，

T)中正常返，当且仅当i

在嵌入马氏链中正常返，且对j∈Ci

均有ηj<∞。

证明由(6.6.5)式可得

其中

是在嵌入马氏链X

中状态i的平均返回时间。设i在(X，

T)中正常返，即μ

ii<∞，如果有j∈Ci

使得ηi=∞，则从i出发以正概率使平均返回时间无穷，从而μii=∞，与μii<∞矛盾。因此对j∈Ci均有

ηj<∞。从而ηjk<∞，

∀j，

k∈Ci。但∀j，

k∈Ci，若pjk>0，则ηjk>0，由此及Ci

的有限性、互通性及(6.6.6)式知，

inf{ηjk|pjk>0，

j，

k∈Ci}∈(0，

∞)，从而μ*ii

<∞。

反过来，若μ*ii

<∞且η

j<∞，

∀j∈Ci

，则由Ci的有限性知sup{ηjk|pjk>0，

j，

k∈Ci}∈(0，

∞)，由此及(6.6.6)式即知μii<∞。

由定理可知对(X，

T)的一个类C

，若其中有一个状态正常返，则它在X

中也是正常返的，由马氏链的知识(定理5.3.5)知，

C

中的状态在X

中都是正常返的，再由以上定理即知C

中状态在(X，

T)中也都是正常返的，这就是说正常返(或零常返)当它所在的类有限时是类性质(互通的状态有相同的状态类型)。

6.7马尔可夫更新方程与极限定理

本节将更新论中的更新方程与极限定理推广到马氏更新过程中来。为使记号简单起见，我们以Pi

和Ei

分别表示在X0=i条件下的条件概率和条件期望。进而，为避免平凡，我们假定:

对n≥0，定义

由定理6.5.2知，对i，

j∈S，在X0=i的条件下，

Nj(t)是一个延迟更新过程，其更新函数为

由假设(6.7.1)式及引理6.1.1易知mij(t)有限。我们称mij

(·)是马尔可夫更新函数，称族m={mij(·)|i，

j∈S}是马尔可夫更新核。

另一方面，由(6.1.8)式和(6.4.2)式可得

其中Gnjj是分布Gjj

的n

重卷积。上式将mij(t)转化为mjj(t)的确定。

定义函数空间B

如下:B={g:S×[0，

∞)→[0，

∞)|

对i∈S，

g(i，·)在任一有限区间上均有界;对t≥0，g(·，

t)在S

上有界。}

对g∈B

，定义半马氏核Q

与

g

的卷积为

显然Q*g∈B。m*g类似定义且当g

∈B

时亦有m*g∈B。

称g∈B

满足马尔可夫更新方程，如果有h∈B使

写成卷积形式为

更新方程(6.2.1)式的卷积形式与上式完全相同。关于马氏更新方程的解有以下结论。

定理6.7.1马氏更新方程(6.7.7)式的任一解g均具有以下形式:

其中f

满足

特别地，

f=0满足上式，故(6.7.7)式有解h+m*h。

证明由(6.7.7)式递推可得

由于Q

nij(t)对n单调下降，

g非负，

Qn+1*g

对n单调下降，从而其极限存在，记为f

，易知

在(6.7.10)式中令n→∞，由(6.7.3)式即得(6.7.8)式和(6.7.9)式。

定义马氏更新过程(X，

T)的寿命为随机变量

关于方程(6.7.9)式只有零解，或马氏更新方程(6.7.7)式有唯一解的若干条件给出如下。

定理6.7.2

(1)(6.7.9)式有唯一解f=0的充要条件是P{L=∞}=1。

(2)如果只有有限个非常返状态(特别地S有限)，则P{L=∞}=1。

(3)如果有常数δ>0使则P{L=∞}=1。

为给出讨论更新解的极限定理，需推广直接(黎曼)可积的概念。

定义6.7.1设π

是

S上的非负向量，称函数g∈B

是相对于π直接可积的，如果

对任意的a>0均有限，且当a→0时，

σ1

(a)-σ2(a)→0。记B

π

是所有如此函数g所组成的集合。

定理6.7.3设(X，

T)不可约常返，向量π≥0满足πP

=π，

g

∈B

π

，则当所有Gij(j∈S)均是非格时

当Gjj

(j∈S)均是格的且有相同的周期δ时

其中γij是分布

Gij中的第一个跳跃点，而约定当x<0时g

(j，

x)=0。

最后，由定理6.7.3可证得以下关于Pij(t

)当t→∞

时的极限。

定理6.7.4设(X，

T)不可约常返，向量π≥0满足π=πP，

Gij均为非格，则对i∈S均有

若Gjj均是格的且有相同的周期δ

，则

其中γij同定理6.7.3中，

Qj(x)=0(x<0时)。

以上的定理6.7.3和定理6.7.4可推广到(X，

T)的任一个常返类，它们的证明均可见参考文献[32]。

6.8再生过程与报酬过程

现在，我们考虑这样一类随机过程，它存在一个时刻，使得从此时此刻开始的过程与原过程完全相同。

定义6.8.1对状态集S={0，

1，

2，…}上的随机过程X={X(t)，

t≥0}，设有随机变量T1

使得{X

(t-T1

)，

t≥T1}与原过程

X完全相同(概率的)，则称

X是一个再生过程。

由定义知还存在时T2

，

T3

，…，它们具有与T1

相同的性质，从而{T1

，

T2

，…}形成一个更新过程，我们称两相继更新间隔为一个周期。

显然，更新过程是再生过程，

T1

就是首次更新时间。常返马氏更新过程也是再生过程，T1

表示首次到达初始状态的时间。

记Pj

(t)=P{X(t)=j}，

T1

的分布函数为

F。以下定理仍运用关键更新定理证得。

定理6.8.1设T1在某个区间上有密度，即有0≤a<b≤∞及函数f

(x

)使得对

t∈[a，

b]有P{T1

≤t}=P

{T1

≤a}+

证明运用更新论中的方法有

由定理6.2.1和关键更新定理可得

但

因此

其中χ为示性函数，而就表示在一个周期[0，

T1

]中过程处于状态j的总时间。

由以上定理也可立得命题6.2.1和6.2.2，也可推得定理6.7.4中的(6.7.14)式。

现在，我们进一步假定当处于状态i

时，过程将以率

r(

i)获得报酬，于是t

时记得的报酬率为r(X(t))，我们称之为再生报酬过程。当X

是半马氏过程时，就称r(X(t))为半马氏报酬过程。

由命题6.2.2，可立得以下结论。

定理6.8.2若

以概率1成立；进而

以上两式给出了长期运行下单位时间平均(期望)报酬的表达式，两者是相同的。对于等式的右边，我们还有以下进一步的结论。

定量6.8.3设定理6.8.1和6.8.2中的条件均成立，则

证明由积分的定义可知

因此(6.8.6)式成立。

直观上，(6.8.6)式的左边和右边均表示单位时间内的平均期望报酬。

最后，我们来研究半马氏报酬过程。设报酬率函数r(

i)有界，或者r≥0，或者r≤0。

考虑

式中，

α>0是连续折扣因子，表示t

时获得的单位报酬仅值0

时的e-αt;Vα(i)表示从初始状态i

出发的期望折扣总报酬。在关于r(i)的假设下，

Vα

(i)存在，且分别有界，非负或者非正。由全期望公式，有

由于

故

记

其中，

R

(i

)表示当Xn=i时在[Tn

，

Tn+1]中获得的折扣到Tn

时计算的期望折扣总报酬;βij则表示Tn

+1时的一单位报酬仅值Tn

时的βij。我们称βij为一阶段折扣因子。因此有

对此，我们有以下结论

定理6.8.4设(X，

T)满足正则性条件(6.5.9)式，则当r有界时，

Vα

是(6.8.7)式的唯一有界解;当r非负(或非正)时，

Vα

是(6.8.7)式的最小非负(或最大非正)解。

证明由条件(6.5.9)式可知有β<1使βij≤β，

∀i，

j。记向量Vα=(Vα(i)，

i∈S)，R=(R(i)，

i∈S)，矩阵A=(pijβij)，则(6.8.7)式的向量形式为

前面我们已证得V

α是(6.8.7)式的解。下设V是(6.8.7)式的另一个解，则由V=R+AV递推可得

由于A的行和≤β，故由矩阵论的知识知道收敛于

当

r有界时，

R

也有界。设V有界，则AN+1V→0。在(6.8.8)式中令N→∞即知V=(I-A)-1R=Vα

。所以(6.8.7)式有唯一有界解。

当r≥0时有R≥0

。设V≥0

，则由(6.8.8)式知

故V

α

是(6.8.7)式的最小非负解。

当r≤0

时，证明是类似的。

在半马氏报酬过程中，如果在各次状态转移时刻，我们有不同的决策可供选择以影响过程未来的发展变化，就得到了半马氏决策过程，这是研究随机动态系统最优控制的主要工具之一，有兴趣的读者可参阅参考文献[20]和[21]。

6.9广义半马氏过程简介

广义半马氏过程(GSMP:Generalizedsemi-Markovprocesses)是比半马氏过程更广的一类随机过程，它是德国学者Matthes在60年代初提出来的，当时取名为Bedienugsprozesse(德文)，意指服务动态学，它可用来描述存储论、可靠性理论、排队系统、计算机/通信网络等中的随机模型。

6.9.1模型

考虑一随机系统，它可用状态—事件框架来描述，其状态的变化仅是由于事件的发生引起的，而且事件的总数是可数的，于是状态也是可数的。例如在排队系统中，状态表示队长，事件只有两个:到达一个顾客，服务完一个顾客。设S

为可数状态集，

E为可数事件集。为与下面将要引入的数学状态相区别，我们称s∈S为系统的物理状态。对s∈S

，

E(s)⊂E为s处可发生的事件集，称之为s的可行事件集。

对e∈E，记ce为事件e的已持续时间(最后一次发生至今的时间)，称ce

为e

的时钟读数(clockreading)。对e∈E(s)，

rse≥0表示ce

随时间增加的速度。

记R+-1∶={-1}∪[0，

∞)，

C(s)∶={c=(ce，

e∈E)∈(R+-1)E

:对e∈E，ce=-1当且仅当e∈E(s)}。于是c∈C(s)表示在状态s处所有事件的时钟读数所组成的向量，

ck=-1当且仅当e在s

处不可行。

我们用下述例题来说明上述各元的含义。

例6.9.1考虑有M个服务中心的开环排队网络，各中心均有一个服务台，顾客类型只有一种。记N+={0，

1，

2，…}，则网络的状态集S=(N+

)M:对s=(s1

，

s2

，…，

sM)∈S

，si为中心

i的队长;事件集E={(i，

1)，(i，

2):1≤i≤M}:其中(i，

1)表示有一个顾客从外部到达中心i;(i，

2)表示有一个顾客因服务结束而离开中心i。显然E(s)={(i，

1):1≤i≤M}∪{(i，

2):si

≥1，

1≤i≤M}。对e=(i，

1)，

ce

表示中心

i的最后一次外部到达至今的时间;对e=(i，

2)，

ce表示中心

i处接受服务之顾客的已服务时间。对e=(i，

2)，

rse=1表示中心

i的服务速率恒定，而rse=ri

si

则表示中心

i处的服务速率与队长si

成正比。

系统的动态变化如下。由于系统的轨迹是分段为常数的，于是可假定其(物理)状态过程{S(t);t≥0}为

式中，

0=T0<T1

<…满足{Sn

}为取值于S

中的随机序列;χ为示性函数;Tn表示系统的第n

次状态转移时刻;Sn

为Tn

时的状态。于是

是S

(t

)的第n次和第n+1次状态转移的间隔时间。记Cn为Tn时的时钟读数向量，

表示在Tn

时的数学状态。

现在设对某n≥0，

Xn=(s，

δ，

c)。由于系统由事件驱动，所以Tn

后的首次状态转移将由首先发生的事件所确定，记此事件为en+1，并称为触发事件(triggerevent)。为确定en

+1，设有分布函数族{Fe(·):e∈E}满足Fe

(0)=0。Fe

(·)为事件e

的持续时间分布函数。

由于Cn=c表示Tn

时各事件的已持续时间，

e∈E(

s)的剩余持续时间(记为Yne)的分布函数为

为使所定义的各式有意义，令rse=0时Yne/rse=+∞;且假定对任一s

，至少有一e∈E(s)使得rse

>0，亦即

同时为使en+1唯一，假定对任一s∈S，至多有一个e∈E(s)使Fe

(t)不连续。

显然，

Tn+1=Tn+Δn+1，而Sn

+1由状态转移概率族

确定，其中p(s'|s，

e)=P{Sn+1=s'|Sn=s，

en+1=e}。再记

分别表示在条件Sn=s，en+1=e，

Sn+1=s'下s'

处可行事件集E(s')中的旧事件集和新事件集。自然，我们假定状态转移不改变旧事件的时钟读数，于是

这样，在引入了{Fe(·)}和p

之后，

Xn+1就由Xn

确定。容易看出，数学状态过程X∶={Xn

，

n≥0}是时齐马氏链，其状态空间

记B

(H

)为H

中的σ

域。X

的转移概率为:对x=(s，

δ，

c)∈H

及

其中

而Fe，

a(t)=Fe(at)。

定义6.9.1设S

为可数状态集，

E(s

)为状态s

的可行事件集，

p={p(s‘|s，

e):s，s'∈S，

e∈E(s)}为状态转移概率族，

r={rse:s∈S，

e∈E(s)}为速率族，

F={Fe(·):e∈E}为事件的持续时间表分布函数族，记Σ=(S，(E(s)，

s∈S)，

p)。

(1)称(Σ，

r)为具有速度的广义半马氏概型(GSMS:generalizedsemi-Markovscheme);当rse

≡1时，简记(Σ，

r)为Σ

，并称Σ为GSMS。

(2)称(6.9.1)式中的S(t)为(Σ，

r)上由F

确定的广义半马氏过程(GSMP)，称X

={Xn，

n≥0}为(Σ，

r)上由F

确定的扩充(supplemented)GSMP。

上面所定义的是时齐GSMP，对非时齐GSMP可用类似方法定义。记Xn∶=(X0，

X1

，…，

Xn

)，如果转移概率族p={p(s'|xn，

e):xn∈Hn+1，e∈E}和分布函数族F={F(·|xn

，e):xn∈Hn+1，e∈E}均与xn有关，则得到的过程X

是非时齐马氏链，其状态转移概率P{Sn+1=s'|Xn=xn，

en+1=e}与(6.9.5)式中类似。称相应的S(t)为非时齐GSMP。

例6.9.1(续)设pij为离开中心i的顾客到达中心

j的概率，为离开网络的概率。则P∶=(pij)为次随机矩阵。此时的排队网络可用一时齐GSMP表示。若记ei

为第i

个单位向量，则

若进一步假定中心i的外部到达是间隔时间分布为Fi

(·)的更新过程，中心i的服务时间分布为Gi

(·)，服务速率是r

i

si

，先到先服务规则，则rs

，(i，

1)=1，

rs

，(i，

2)=risi

，

F(i，

1)(·)=Fi(·)，

F(i，

2)(·)=Gi

(·)。

下面我们考虑GSMP的几种特例。

(1)之所以将S(t)称为广义半马氏过程，是因为它比半马氏过程的含义更广。

如果在GSMP中假定

则可证对n≥1，

x=(s，

δ，

c)有

其中

Ye

有分布Fe

，从而S(t)是半马氏过程。

则

所以{Sn

}是马氏链，{S(t)}是马氏过程，其转移速率矩阵Q

为

对以上的详细推导并不难，读者可自己给出。

实际上，半马氏过程和马氏链在GSMP中所起的作用与线性系统在连续变量动态系统(CVDS:continuousvariabledynamicsystems)中所起的作用是类似的，这一点从表6.1中不难看出。

注:(1)表中所作的对比主要是概念上的。

(2)在GSMP中，

S(t)是物理状态轨迹，但直接研究S(t)一般并不容易，

GSMP引入较易研究的数学状态过程X，通过对X的研究来得到关于S的有关结果，而S=h1

(X)为X的第一个分量。这种思路与CVDS中是类似的。

(3)关于特例的类比是因为线性系统和半马氏过程、马氏链分别是CVDS、GSMP中研究得较为透彻的两类特例，同时从状态方程③、④的形式上也可见一斑。

6.9.2平稳分布

扩充GSMP的马氏性可用来研究系统的长期运行行为。我们有如下两个定理。

定理6.9.1设S上的实值函数f满足条件

其中μ1、μ2

、μ3均为有限随机变量，且μ2>0，

a.s.，则

(2)对一切