《随机过程》课件第6章.pptx

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

2、到了马尔可夫更新过程(也称为半马尔可夫过程)，这两类随机过程具有广泛的应用。本章将分别介绍它们。第6章 更新过程与马尔可夫更新过程6.1 更新过程的定义更新过程的定义在 2.6 节中我们知道 Poisson 过程是这样一类计数过程:其任意两次相邻的到达间隔时间是相互独立同参数指数分布的。比这含义再广一点的是到达间隔时间相互独立同分布但分布函数可以任意的计数过程，这就是更新过程。这类随机过程描述在一系列时刻点上系统变新(称之为更新)且两相继更新时刻点(称为更新点)的间隔是独立同分布的随机系统，刻画此类系统的是两相邻更新点间隔时间的分布函数。第6章 更新过程与马尔可夫更新过程正式地，设X n，n=

3、1，2，是相互独立的非负随机变量，分布函数均为 F(t)，假定F(0)1(请读者考虑:当 F(0)=1 时将会怎样)。由于 X n 非负，故 EX n 存在(可能是无穷)，记第6章 更新过程与马尔可夫更新过程这里，是平均(期望)更新间隔时间，T n是第 n 次更新发生的时间，于是 N(t)表示系统在0，t 中发生的更新次数。由于 X n 独立同分布，因此系统在时刻 T 1，T 2，与新的一样重新开始。我们说 N(t)是有限的，从而是随机变量。实际上，由强大数定律知以概率 1 有 T n/n ，所以 T n t 以概率 1 只对有限多个 n 成立，从而 N(t)以概率 1 有限。第6章 更新过程

4、与马尔可夫更新过程定义定义 6.1.1 称 N(t)，t 0 或 T 0，T 1，是更新过程，称 T n 为第 n 个更新点，称 F为更新分布(函数)。更新论的主要目的是由 X n 的分布函数 F(t)导出有关 N(t)和 T n 的一些有用的性质。例如，0，t 中的期望更新次数称之为更新函数。第6章 更新过程与马尔可夫更新过程由于独立随机变量和的分布函数是各随机变量分布函数的卷积，因此 T n 作为 X 1，X 2，X n 的和，其分布函数其中 F n(t)是 F(t)的 n 重卷积:F 1(t)=F(t)，而第6章 更新过程与马尔可夫更新过程同时，由(6.1.2)式易知，T n 与 N(t

5、)有以下关系:于是第6章 更新过程与马尔可夫更新过程由此，我们可得到更新函数的一个表达式由于 F n(t)非负，以上级数自然是有定义的。如下引理进一步说明更新函数是有限的。第6章 更新过程与马尔可夫更新过程引理引理 6.1.1 m(t)，t 0。证证明明 由 X n 的独立同分布性知，X m+1+X n 与 T n-m 同分布函数，因此 T n 的分布函数等于 T m 的分布函数与 T n-m 的分布函数的卷积。因此由分布函数的单调性知特别地，对任意的正整数 n，r，k，有第6章 更新过程与马尔可夫更新过程由此递推可得因此对任意的正整数 r，有第6章 更新过程与马尔可夫更新过程对 t 0，若

6、F r(t)1，则以上级数是几何收敛的，而由强大数定律知 T n 以概率 1 趋于 ，因此，对任一 t 0，必有 r 使得 F r(t)=P T r t t 时，0，t 中没有更新。第6章 更新过程与马尔可夫更新过程因此代入上式得这是较为特殊的更新方程，已知函数 F，求函数 m。第6章 更新过程与马尔可夫更新过程更新方程的解由以下定理给出。定理定理 6.2.1 更新方程(6.2.1)式的解为第6章 更新过程与马尔可夫更新过程证明证明 注意到(6.2.1)式的卷积形式为 g=h+g*F，取其拉普拉斯变换可得由此及(6.1.10)式得取拉普拉斯反变换即得(6.2.3)式。第6章 更新过程与马尔可夫

7、更新过程现在，我们考虑 m(t)的极限性态。由于平均更新时间是 ，即平均每隔时间 就发生一次更新。因此容易猜想当 时，N()=N(t)=。所以考虑 m(t)的极限一般地没有什么意义。与马氏链中(定理 5.4.5)类似，我们考虑单位时间内的平均更新次数，即N(t)/t 的极限。从其含义容易猜想其极限应是 1/。正式地，我们有以下定理。第6章 更新过程与马尔可夫更新过程定理定理 6.2.2 以概率 1 有证明证明 由 N(t)的定义易知因此第6章 更新过程与马尔可夫更新过程由于 N()有限当且仅当有 n 使得 T n=，于是故 N()以概率 1 等于 ，也即当 t 时，N(t)以概率 1 趋于 。

8、而由强大数定律知以概率 1 有 T n/n 。因此当 t 时，以概率 1 有由此及(6.2.4)式知定理结论成立。第6章 更新过程与马尔可夫更新过程关于单位时间平均期望更新次数，即 m(t)/t 的极限，易知它亦应等于 1/，但其证明将稍为复杂一些。以下我们先给出停时的概念。第6章 更新过程与马尔可夫更新过程定义定义 6.2.1 称取正整数值的随机变量 N 是随机序列 X n，n 0 的一个停时，如果对任一 n，事件 N=n 与 X n+1，X n+2，相互独立。直观上，我们一个一个地观察X n，n 0，而 N 表示停止观察的时间，N=n 表示在观察了 X 1，X 2，X n 之后，但在观察

9、X n+1，X n+2，之前停止。于是，停时表示何时停止只与已观察的随机变量有关，而与未观察的无关。第6章 更新过程与马尔可夫更新过程例例 6.2.1 设 X n，n 0 相互独立，(1)若 P X n=0 =P X n=1 =1/2，记则 N 是一个停时。(2)若 P X n=-1 =P X n=1 =1/2，则以下定义的 N 也是一个停时:第6章 更新过程与马尔可夫更新过程定理定理 6.2.3 (Wald 方程)设 X 1，X 2，独立同分布，EX 1 有限，N 是一个停时且 EN有限，则第6章 更新过程与马尔可夫更新过程证明证明 记 为示性函数，由停时的定义可知 N n 表示在观察了 X

10、 1，X 2，X n-1 之后不停止，因此随机变量 (N n)由 X 1，X 2，X n-1 确定而与 X n 独立。因此请读者考虑这里能否运用全期望公式?第6章 更新过程与马尔可夫更新过程例例 6.2.1(续)对(1)应用 Wald 方程有所以 EN=20。若对(2)应用 Wald 方程，则有不成立，这只能说明 EN=，定理 6.2.3 中的条件不满足。第6章 更新过程与马尔可夫更新过程定理定理 6.2.4 (基本更新定理)证明证明 首先，我们假定 。为应用 Wald 方程，我们需要为更新过程构造一个停时，注意到或者第6章 更新过程与马尔可夫更新过程因此 N(t)+1 是一个停时(但 N(t

11、)不是停时)。进而 E(N(t)+1)=m(t)+1 x，将 X 1 作为条件有第6章 更新过程与马尔可夫更新过程从而对以上更新方程应用定理 6.2.1 和关键更新定理可得当 F 为非格时，由以上两式及 P t x =1-P(t)即可分别得到(6.3.1)式和(6.3.2)式。第6章 更新过程与马尔可夫更新过程当 F 为格时，t 的极限分布请读者给出。与(6.3.3)式类似，我们还有由此及定理 6.3.1 即可得到有关 t 的分布函数以及(t，t)的联合分布函数所满足的更新方程和极限分布。具体结果请读者写出。第6章 更新过程与马尔可夫更新过程最后，关于总寿命 t 的分布函数，我们既可从(6.3

12、.5)式类似得到，也可直接应用定理6.3.1 证明中的方法得到。记 Q(t)=P t x，由于其中 x t=max x，t。则由全期望公式可得更新方程由此即可得到以下定理。第6章 更新过程与马尔可夫更新过程定理定理 6.3.2进而，当 F 为非格时，由(6.3.2)式和(6.3.8)式可知，t 和 t 的极限分布相同，且当 有限时，它们仍是分布函数。第6章 更新过程与马尔可夫更新过程6.4 延迟与终止过程延迟与终止过程我们先来讨论延迟(delayed)更新过程。在很多计数过程中，第一个更新间隔时间的分布函数与其余的不同，例如在某个非更新点 t 0 处开始观察系统，以及在例 6.1.1 的(7)

13、中当X 0=j i 时。第6章 更新过程与马尔可夫更新过程正式地，设X n，n=1，2，相互独立，X 1 有分布函数 G，X 2、X 3、有相同的分布函数 F，记 T n 同(6.1.1)式中，而将(6.1.2)式中定义的 N(t)记为 N D(t)，这里用下标 D 以示区别。第6章 更新过程与马尔可夫更新过程定义定义 6.4.1 称随机过程 N D(t)，t 0 为延迟更新过程。与 N(t)中类似，我们可得其中 F 0(x)=1，*号表示卷积，而 G*F 0=G。记(延迟)更新函数 m D(t)=EN D(t)，则第6章 更新过程与马尔可夫更新过程其中 m(t)是更新分布为 F 的更新函数。

14、仍记以下定理的证明留给读者。第6章 更新过程与马尔可夫更新过程若 F 为格的且有周期 d，则(6.4.5)式对 a=nd 成立，n=0，1，2，。以下假定 ，此时第6章 更新过程与马尔可夫更新过程是一分布函数，称为 F 的平衡分布，其拉普拉斯变换为当 G=F e 时的延迟更新过程是特别重要的，我们称之为平衡更新过程。由(6.3.2)式知，当开始观察系统的时间 t 充分大时，可将之看作为平衡更新过程。记 Dt 表示延迟更新过程 N D(t)中的剩余寿命。以下定理的证明可见参考文献25 的定理 3.15，它说明了“平衡”的含义。第6章 更新过程与马尔可夫更新过程定理定理 6.4.2 对平衡更新过程

15、:第6章 更新过程与马尔可夫更新过程由定理 6.4.1 知，F e 是原更新过程 N(t)中 t 时的剩余寿命 t 的极限分布;而由定理6.4.2 的(2)知，在平衡更新过程 N D(t)中剩余寿命 Dt 的分布函数保持不变，就为 F e，这也是“平衡”的含义之一。定理 6.4.2 的(1)和(3)还说明了“平衡”的另两个含义。直到现在为止，我们一直假定更新分布 F 是通常的分布函数，即 F()=1。但定义6.1.1 对 F()0)也是成立的。第6章 更新过程与马尔可夫更新过程定理定理 6.4.3 F()=1 EN()=P N()=1。证证明明 设 F()=1，由于 N()有限当且仅当有 n

16、使得 X n=，因此第6章 更新过程与马尔可夫更新过程由此可得 EN()=。另一方面，若 F()1，则第一次更新后，系统以概率 1-F()不再更新，因此则 N()是均值为 F()/1-F()的几何分布，于是 P N()=1，EN()=F()/1-F()。基于以上定理，我们给出如下定义。第6章 更新过程与马尔可夫更新过程定义定义 6.4.2 称 F()=1 时的更新过程为非终止的或常返的，称 F()1 时的更新过程是终止的或非常返的。在应用中所研究的随机过程本身并不一定是更新过程，但其中可能存在一嵌入更新过程，且往往不知更新分布是否满足 F()=1，此时，定理 6.4.3 就变得很重要。关于更新

17、过程的进一步讨论可参阅参考文献25、31、32。第6章 更新过程与马尔可夫更新过程6.5 马尔可夫更新过程的定义马尔可夫更新过程的定义将 Poisson 过程中的更新分布一般化就得到了更新过程。而从连续时间马尔可夫过程的理论知道，它在每个状态处的逗留时间是指数分布的(参数依赖于所处状态)。与更新过程一样，将此指数分布一般化，就得到了所谓的马尔可夫更新过程，也称为半马尔可夫过程。它是马尔可夫过程和更新过程的结合，从而广于这两者。第6章 更新过程与马尔可夫更新过程设对 n=0，1，2，随机变量 X n 取值于一可数状态集合 S，随机变量 T n 取值于0，)，且 0=T 0 T 1 T 2 。我们

18、不妨设 S=0，1，2，。第6章 更新过程与马尔可夫更新过程定义定义 6.5.1 称二元随机过程 X，T =X n，T n，n=0，1，2，为马尔可夫更新过程，简称为马氏更新过程，如果对所有的 n，i0，i n，j，t 0，t n，t 均成立。第6章 更新过程与马尔可夫更新过程我们在这里考虑时齐的情形，即与 n 无关。称矩阵函数 Q(t)=(Qij(t)为状态空间 S 上的半马尔可夫核，简称为半马氏核。定义第6章 更新过程与马尔可夫更新过程其中当 pij=0 时，由定义知 Qij(t)0，此时 Qij(t)/pij可任意取值，它不影响我们的讨论，但为确定起见，我们约定此时 Fij(t)是常数

19、1 的分布函数。pij和 Fij(t)均有它们自己的概率含义。我们先来看 pij。由定义，P=(pij)构成一个随机矩阵，从而是某个马氏链的转移概率矩阵。实际上，由(6.5.1)式和(6.5.2)式易知于是得到以下定理。第6章 更新过程与马尔可夫更新过程定理定理 6.5.1 X=X n，n=0，1，2 是状态空间为 S、转移概率矩阵为 P=(pij)的齐次马氏链(称之为嵌入马氏链)。再来看 Fij(t)。不难看出，对任意的 i，j S，Fij(t)是一个分布函数，实际上，第6章 更新过程与马尔可夫更新过程引理引理 6.5.1 对任意的 n 1，t 1，t n 0，以上引理是说当已知马氏链 X

20、n 时，T 1-T 0，T n-T n-1 是相互独立的，而且T n-T n-1 的分布函数仅仅依赖于 X n 和 X n-1。当系统只有一个状态时，即 S 为单点集时，容易看出 T n，n=0，1，2，是更新过程。更一般地，我们有以下定理，其证明可见参考文献32。第6章 更新过程与马尔可夫更新过程定理 6.5.2 对状态 j S，定义 N j(t)为在(0，t 中达到状态 j 的次数，则 N j(t)是一个更新过程或延迟更新过程。对 N j(t)的更新时刻，设 Z n 由例 6.1.1 的(7)中定义，则第 n 个更新时刻点为 T j n=T Z n。设 K j 表示在嵌入马氏链 X 中的首

21、次到达状态 j 的时间，在初始条件 X 0=i 下，其分布由 f(k)ij给出，则对 n 0，T jn+1-Tjn 与 T K j 同分布，从而第6章 更新过程与马尔可夫更新过程因此，在初始条件 X 0=j 下，N j(t)是更新过程;而在 X 0=i j 时，一般地 N j(t)仅是一个延迟更新过程。定理 6.5.1 和 6.5.2 说明了“马尔可夫更新过程”是马尔可夫过程和更新过程相结合的产物。第6章 更新过程与马尔可夫更新过程马氏更新过程也可以从另一角度描述。我们构造随机过程 Y=Y(t)，t 0 如下:其中，S 为一记号;supnT n 是过程的终止时间。从而 Y(t)=表示马氏更新过

22、程已经结束。第6章 更新过程与马尔可夫更新过程 Y 是一个一元随机过程，Y(t)可解释为某系统在 t 时的状态，此系统在状态处停留一段时间后转移到另一个状态，停留时间区间T n，T n+1)的长度是随机的，其分布依赖于所停留的状态 X n 和下一步将要到达的状态 X n+1。它相继到达的状态形成一个马氏链，当已知此马氏链时，它相继的停留时间相互独立。第6章 更新过程与马尔可夫更新过程定义定义 6.5.2 称随机过程 Y=Y(t)，t 0 为半马尔可夫过程，简称为半马氏过程；称Q(t)为其半马氏核，X=X n，n=0，1，2，为其嵌入马氏链。这里用“半马氏过程”是因为 Y 具有“某种”马氏性:已

23、知现在、将来与过去无关，只是这里的“现在”应是状态转移时刻，即某个 T n。本章以下将不再区分半马氏过程与马氏更新过程。第6章 更新过程与马尔可夫更新过程下面讨论在有限时间区间内是否会发生无穷多次状态转移的问题。首先，定义自然，Q i(t)是在状态 i 处逗留时间的分布函数，即本章中恒假定 Q i(0)0 和 0，使(2)对任一 i S，在 X 0=i 的条件下，马氏链 X n，n=0，1，2，以概率 1 到达某一常返状态。证明可见参考文献25 的命题 5.1。定理中的条件(1)和(2)均称为正则性条件。第6章 更新过程与马尔可夫更新过程以下我们假定所讨论的马氏更新过程总是正则的。现在来看几个

24、例子。例例 6.5.2 如果有非负数组 i，i S 使则由(5.5.19)式和(5.5.21)式知 Y 是马氏过程。因此，马氏过程是特殊的半马氏过程。第6章 更新过程与马尔可夫更新过程例例 6.5.3 交通流。设 T 0，T 1，是某高速公路上相继车辆的位置(时间或空间上的)，记 X n 为第 n 辆车的类型(如小车、卡车、公共汽车、重量、大小、速度等)，通常 X n 是一个马氏链，而 T n+1-T n 仅与类型 X n 和 X n+1 有关，从而(X，T)是一个马氏更新过程。第6章 更新过程与马尔可夫更新过程例例 6.5.4 M/G/1 排队。顾客按率为 的 Poisson 过程到达，服务

25、时间相互独立同分布函数 G，一个服务台。记 T 0=0 T 1 T 2 为顾客的相继离去时间，X n 为第 n 次离去后系统中的顾客数，则(X，T)=X n，T n，n=0，1，2，为马氏更新过程，其核为第6章 更新过程与马尔可夫更新过程其中第6章 更新过程与马尔可夫更新过程6.6 状态分类与极限概率状态分类与极限概率马氏更新过程同时具有马氏链和更新过程的很多性质。我们先来讨论马氏更新过程的状态分类，它与马氏链中的状态分类类似。首先，对状态 i，j S 和 t 0，定义第6章 更新过程与马尔可夫更新过程Gij(t)表示过程从状态 i 出发在 t 之前到达状态 j 的概率。若以 T j 1 表示

26、更新过程 N j(t)中第一次更新时间，则显然有 Gij(t)=P T j 1 t|X 0=i。Gij()表示从 i 出发，终究要到达 j的概率。Pij(t)相应于连续时间马氏过程中的状态转移概率。基于 Gij(t)，我们定义从 i 出发到达 j 的期望时间为于是称 ii 为状态 i 的平均返回时间。第6章 更新过程与马尔可夫更新过程现在，我们给出各类状态的定义，以及马氏链中相应定义的推广。定定义义 6.6.1 (1)称状态 i 可达 j，如果 i=j 或者 Gij()0;称 i 和 j 互通，如果 i 可达 j 且 j 可达 i;(2)称状态 i 是常返的，如果 Gij()=1;否则，称状态

27、 i 是非常返的(或瞬时的);(3)称常返状态 i 是正常返的，如果 ii ;否则称状态 i 是零常返的;(4)互通是一个等价关系，等价类简称为类，记 C i 为包含状态 i 的等价类;第6章 更新过程与马尔可夫更新过程(5)称马氏更新过程(半马氏过程)是不可约的，如果它只有一个类，即所有状态互通。容易猜想，马氏更新过程(X，T)中的状态性质与嵌入马氏链 X 中的状态性质有密切关系。为此，首先注意到(X，T)和 X 间的如下关系:由此公式不难得到以下定理。第6章 更新过程与马尔可夫更新过程定理定理 6.6.1 状态 i 在马氏更新过程(X，T)中常返(或非常返、互通)当且仅当状态 i 在嵌入马

28、氏链 X 中常返(或非常返、互通)。由此定理可知，(X，T)有与 X 相同的状态类。为讨论(X，T)和 X 中正常返(或零常返)间的关系，我们需要在(X，T)和 X 中有关正常返的判别准则之间架起一座桥梁。第6章 更新过程与马尔可夫更新过程定义 ij为过程从 i 出发下一步到达 j 的条件下，在 i 的期望逗留时间;i为过程在 i 的期望逗留时间。它们分别用公式表示为现在，利用 n 时首次到达状态 j，中间依次经过 i 1 j，i n-1 j 作为条件，由全期望公式可得第6章 更新过程与马尔可夫更新过程定理定理 6.6.2 对常返状态 i，设类 C i 有限，则 i 在马氏更新过程(X，T)中

29、正常返，当且仅当 i 在嵌入马氏链中正常返，且对 j C i 均有 j 。证明证明 由(6.6.5)式可得其中第6章 更新过程与马尔可夫更新过程是在嵌入马氏链 X 中状态 i 的平均返回时间。设 i 在(X，T)中正常返，即 ii ，如果有j C i 使得 i=，则从 i 出发以正概率使平均返回时间无穷，从而 ii=，与 ii 矛盾。因此对 j C i 均有 j 。从而 jk0，则 jk0，由此及 C i 的有限性、互通性及(6.6.6)式知，inf jk|pjk0，j，k C i (0，)，从而 *ii 。反过来，若 *ii 且 j 0，j，k C i (0，)，由此及(6.6.6)式即知

30、ii 0 使则 P L=1。为给出讨论更新解的极限定理，需推广直接(黎曼)可积的概念。第6章 更新过程与马尔可夫更新过程定义定义 6.7.1 设 是 S 上的非负向量，称函数 g B 是相对于 直接可积的，如果对任意的 a 0 均有限，且当 a 0 时，1(a)-2(a)0。记 B 是所有如此函数 g 所组成的集合。第6章 更新过程与马尔可夫更新过程定定理理 6.7.3 设(X，T)不可约常返，向量 0 满足 P=，g B ，则当所有 Gij(j S)均是非格时当 G jj(j S)均是格的且有相同的周期 时其中 ij是分布 Gij中的第一个跳跃点，而约定当 x 0 时 g(j，x)=0。最后

31、，由定理 6.7.3 可证得以下关于 Pij(t)当 t 时的极限。第6章 更新过程与马尔可夫更新过程定理定理 6.7.4 设(X，T)不可约常返，向量 0 满足 =P，Gij均为非格，则对 i S均有第6章 更新过程与马尔可夫更新过程若 G jj 均是格的且有相同的周期 ，则其中 ij同定理 6.7.3 中，Q j(x)=0(x 0 时)。以上的定理 6.7.3 和定理 6.7.4 可推广到(X，T)的任一个常返类，它们的证明均可见参考文献32。第6章 更新过程与马尔可夫更新过程6.8 再生过程与报酬过程再生过程与报酬过程现在，我们考虑这样一类随机过程，它存在一个时刻，使得从此时此刻开始的过

32、程与原过程完全相同。第6章 更新过程与马尔可夫更新过程定义定义 6.8.1 对状态集 S=0，1，2，上的随机过程 X=X(t)，t 0，设有随机变量 T 1 使得 X(t-T 1)，t T 1 与原过程 X 完全相同(概率的)，则称 X 是一个再生过程。由定义知还存在时 T 2，T 3，它们具有与 T 1 相同的性质，从而 T 1，T 2，形成一个更新过程，我们称两相继更新间隔为一个周期。显然，更新过程是再生过程，T 1 就是首次更新时间。常返马氏更新过程也是再生过程，T 1 表示首次到达初始状态的时间。记 P j(t)=P X(t)=j，T 1 的分布函数为 F。以下定理仍运用关键更新定理

33、证得。第6章 更新过程与马尔可夫更新过程定理定理 6.8.1 设 T 1在某个区间上有密度，即有 0 a 0 是连续折扣因子，表示 t 时获得的单位报酬仅值 0 时的 e-t;V (i)表示从初始状态 i 出发的期望折扣总报酬。在关于 r(i)的假设下，V (i)存在，且分别有界，非负或者非正。由全期望公式，有由于第6章 更新过程与马尔可夫更新过程故记第6章 更新过程与马尔可夫更新过程其中，R(i)表示当 X n=i 时在 T n，T n+1 中获得的折扣到 T n 时计算的期望折扣总报酬;ij则表示 T n+1 时的一单位报酬仅值 T n 时的 ij。我们称 ij为一阶段折扣因子。因此有对此

34、，我们有以下结论第6章 更新过程与马尔可夫更新过程定理定理 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=(pijij)，则(6.8.7)式的向量形式为第6章 更新过程与马尔可夫更新过程前面我们已证得 V 是(6.8.7)式的解。下设 V 是(6.8.7)式的另一个解，则由 V=R+AV 递推可得由于 A 的行和 ，故由

35、矩阵论的知识知道收敛于当 r 有界时，R 也有界。设 V 有界，则 A N+1 V 0。在(6.8.8)式中令 N 即知 V=(I-A)-1R=V 。所以(6.8.7)式有唯一有界解。第6章 更新过程与马尔可夫更新过程当 r 0 时有 R 0。设 V 0，则由(6.8.8)式知故 V 是(6.8.7)式的最小非负解。当 r 0 时，证明是类似的。在半马氏报酬过程中，如果在各次状态转移时刻，我们有不同的决策可供选择以影响过程未来的发展变化，就得到了半马氏决策过程，这是研究随机动态系统最优控制的主要工具之一，有兴趣的读者可参阅参考文献20 和 21。第6章 更新过程与马尔可夫更新过程6.9 广义半

36、马氏过程简介广义半马氏过程简介广义半马氏过程(GSMP:Generalizedsemi-Markovprocesses)是比半马氏过程更广的一类随机过程，它是德国学者 Matthes 在 60 年代初提出来的，当时取名为 Bedienugsprozesse(德文)，意指服务动态学，它可用来描述存储论、可靠性理论、排队系统、计算机/通信网络等中的随机模型。第6章 更新过程与马尔可夫更新过程6.9.1 模型模型考虑一随机系统，它可用状态事件框架来描述，其状态的变化仅是由于事件的发生引起的，而且事件的总数是可数的，于是状态也是可数的。例如在排队系统中，状态表示队长，事件只有两个:到达一个顾客，服务完

37、一个顾客。设 S 为可数状态集，E 为可数事件集。为与下面将要引入的数学状态相区别，我们称 s S 为系统的物理状态。对 s S，E(s)E 为s 处可发生的事件集，称之为 s 的可行事件集。第6章 更新过程与马尔可夫更新过程对 e E，记 c e 为事件 e 的已持续时间(最后一次发生至今的时间)，称 ce 为 e 的时钟读数(clockreading)。对 e E(s)，r se 0 表示 c e 随时间增加的速度。记 R+-1=-1 0，)，C(s)=c=(c e，e E)(R+-1)E:对 e E，c e=-1 当且仅当 e E(s)。于是 c C(s)表示在状态 s 处所有事件的时钟

38、读数所组成的向量，c k=-1当且仅当 e 在 s 处不可行。我们用下述例题来说明上述各元的含义。第6章 更新过程与马尔可夫更新过程例例 6.9.1 考虑有 M 个服务中心的开环排队网络，各中心均有一个服务台，顾客类型只有一种。记 N+=0，1，2，则网络的状态集 S=(N+)M:对 s=(s 1，s 2，s M)S，s i 为中心 i 的队长;事件集 E=(i，1)，(i，2):1 i M:其中(i，1)表示有一个顾客从外部到达中心 i;(i，2)表示有一个顾客因服务结束而离开中心 i。显然 E(s)=(i，1):1 i M (i，2):s i 1，1 i M。对 e=(i，1)，c e 表

39、示中心 i 的最后一次外部到达至今的时间;对 e=(i，2)，c e表示中心 i 处接受服务之顾客的已服务时间。对 e=(i，2)，r se=1 表示中心 i 的服务速率恒定，而 rse=r i s i 则表示中心 i 处的服务速率与队长 s i 成正比。第6章 更新过程与马尔可夫更新过程系统的动态变化如下。由于系统的轨迹是分段为常数的，于是可假定其(物理)状态过程S(t);t 0 为式中，0=T 0 T 1 0，亦即同时为使 e n+1 唯一，假定对任一 s S，至多有一个 e E(s)使F e(t)不连续。显然，T n+1=T n+n+1，而 Sn+1 由状态转移概率族确定，其中 p(s|

40、s，e)=P S n+1=s|S n=s，e n+1=e。再记第6章 更新过程与马尔可夫更新过程分别表示在条件 S n=s，en+1=e，S n+1=s 下 s 处可行事件集 E(s)中的旧事件集和新事件集。自然，我们假定状态转移不改变旧事件的时钟读数，于是这样，在引入了F e()和 p 之后，X n+1 就由 X n 确定。容易看出，数学状态过程 X=X n，n 0 是时齐马氏链，其状态空间第6章 更新过程与马尔可夫更新过程记 B(H)为 H 中的 域。X 的转移概率为:对 x=(s，c)H 及第6章 更新过程与马尔可夫更新过程其中而 F e，a(t)=F e(at)。第6章 更新过程与马尔

41、可夫更新过程定义定义 6.9.1 设 S 为可数状态集，E(s)为状态 s 的可行事件集，p=p(s|s，e):s，s S，e E(s)为状态转移概率族，r=r se:s S，e E(s)为速率族，F=F e():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=X n，n 0 为(，r)上由 F 确

42、定的扩充(supplemented)GSMP。第6章 更新过程与马尔可夫更新过程上面所定义的是时齐 GSMP，对非时齐 GSMP 可用类似方法定义。记 X n =(X 0，X 1，X n)，如果转移概率族 p=p(s|x n，e):x n Hn+1，e E 和分布函数族 F=F(|x n，e):x n Hn+1，e E 均与 x n 有关，则得到的过程 X 是非时齐马氏链，其状态转移概率 PS n+1=s|X n=x n，e n+1=e 与(6.9.5)式中类似。称相应的 S(t)为非时齐 GSMP。第6章 更新过程与马尔可夫更新过程例例 6.9.1 (续)设 pij为离开中心 i 的顾客到达

43、中心 j 的概率，为离开网络的概率。则 P=(pij)为次随机矩阵。此时的排队网络可用一时齐 GSMP 表示。若记 ei 为第 i 个单位向量，则第6章 更新过程与马尔可夫更新过程若进一步假定中心 i 的外部到达是间隔时间分布为 F i()的更新过程，中心 i 的服务时间分布为 G i()，服务速率是 ri s i，先到先服务规则，则 r s，(i，1)=1，r s，(i，2)=r i s i，F(i，1)()=F i()，F(i，2)()=G i()。第6章 更新过程与马尔可夫更新过程下面我们考虑 GSMP 的几种特例。(1)之所以将 S(t)称为广义半马氏过程，是因为它比半马氏过程的含义更

44、广。如果在 GSMP 中假定则可证对 n 1，x=(s，c)有第6章 更新过程与马尔可夫更新过程其中Y e 有分布 F e，从而 S(t)是半马氏过程。第6章 更新过程与马尔可夫更新过程则第6章 更新过程与马尔可夫更新过程所以S n 是马氏链，S(t)是马氏过程，其转移速率矩阵 Q 为对以上的详细推导并不难，读者可自己给出。实际上，半马氏过程和马氏链在 GSMP 中所起的作用与线性系统在连续变量动态系统(CVDS:continuousvariabledynamicsystems)中所起的作用是类似的，这一点从表 6.1 中不难看出。第6章 更新过程与马尔可夫更新过程第6章 更新过程与马尔可夫更

45、新过程注:(1)表中所作的对比主要是概念上的。(2)在 GSMP 中，S(t)是物理状态轨迹，但直接研究 S(t)一般并不容易，GSMP 引入较易研究的数学状态过程 X，通过对 X 的研究来得到关于 S 的有关结果，而 S=h 1(X)为 X 的第一个分量。这种思路与 CVDS 中是类似的。(3)关于特例的类比是因为线性系统和半马氏过程、马氏链分别是 CVDS、GSMP 中研究得较为透彻的两类特例，同时从状态方程 、的形式上也可见一斑。第6章 更新过程与马尔可夫更新过程6.9.2 平稳分布平稳分布扩充 GSMP 的马氏性可用来研究系统的长期运行行为。我们有如下两个定理。定定理理 6.9.1 设

46、 S 上的实值函数 f 满足条件其中 1、2、3均为有限随机变量，且 2 0，a.s.，则第6章 更新过程与马尔可夫更新过程(2)对一切满足 p(s|s，e)0 的 s，s S 及 e E(s)，存在 e N(s|s，e)使得 r se 0。这时，当 X 有平稳分布 时，对任一实值函数 f 均有 E|f(S 0)1|。这里 E 表示当X 0 的初始分布为 时 X 的样本空间上的数学期望;为平稳分布是指它在 H 上满足如下条件(P 为 X 上的转移概率):关于平稳分布的存在性，我们有以下定理。第6章 更新过程与马尔可夫更新过程关于平稳分布的存在性，我们有以下定理。定理定理 6.9.3 设(1)|

47、S|;(2)e E，F e(0)=0，F e(t)0;(4)0，e E，存在 T 使得对 t 一致的有 F e(T+t)/F e(t)0，j，k C i 0，则 i 在 X 中正常返且 j 0，j，k C i x。8.试证明下式:第6章 更新过程与马尔可夫更新过程 9.对一个更新分布为非格的更新过程，试证明以下两式:第6章 更新过程与马尔可夫更新过程 10.设有一个过程，它有三个状态:1、2、3，其状态转移是 1231 的循环形式，在状态 1、2、3 处的逗留时间分别服从分布函数 F 1、F 2、F 3，试求以此，试求 n 个状态的类似问题。第6章 更新过程与马尔可夫更新过程 11.有一个计数

48、器，粒子的到达服从间隔分布为 F 的更新过程，计数器每记录一个粒子后锁住一段固定时间 L，在此期间，它不能记录任何到达的粒子。试求从锁住结束到下一个粒子到达的时间长度的分布函数。12.设顾客相继到达一个汽车站形成一个均值为 的更新过程，当有 N 个顾客时就发出一辆汽车。假定汽车站需给逗留在汽车站的每个顾客以率 支付费用。需研究汽车站在长期运行下单位时间的费用。第6章 更新过程与马尔可夫更新过程 13.设某更新过程的更新密度为其中 是固定的，试计算概率 P N(t)k。14.设某更新过程的更新密度是 f(t)=2t e-t，t 0，试证明其更新函数是第6章 更新过程与马尔可夫更新过程 15.考虑

49、一个系统，由于使用时间过长会失效，而且一般失效时所造成的损失较大，因此经常是在失效前就用一个新的同类系统更换之。考虑这样一种策略:对固定的 T 0，当系统在 T 时还未失效时就更换(称事前更换);若在 T 之前已经失效，则在失效时就更换(称事后更换)。设 c 1 是事前更换的费用，c 2 是事后更换的费用。试求使长期运行单位时间费用达到最小的 T。第6章 更新过程与马尔可夫更新过程 16.设有一马氏更新过程(X，T)，其状态空间为 S=a，b，半马氏核为(1)试求嵌入马氏链 X 的转移概率矩阵;(2)对任意的状态 i、j，试计算给定现在的状态为 i 而下一步的状态为 j 的条件下，在状态 i

50、的逗留时间的分布函数。第6章 更新过程与马尔可夫更新过程 17.对题 16 中的(X，T)，设 X 0=a，X 1=a，X 2=b，X 3=b，试求以下条件概率:(1)P T 1 x，T 2-T 1 y，T 3-T 2 z|X 0，X 1，X 2，X 3;(2)P T 3 x|X 0，X 1，X 2，X 3。第6章 更新过程与马尔可夫更新过程 18.某机器由两个部件组成，它们的寿命分别是参数为 0.01 和 0.04 的指数分布。当有一个部件失效时，机器就失效，两个部件失效时的修理时间分别服从分布函数 F 和 G，定义随机过程 Y(t)=0，1，2，分别表示机器在 t 时工作，部件 1 在修理