第6章更新過(guò)程與馬爾可夫更新過(guò)程6.1更新過(guò)程的定義6.2更新方程與極限定理6.3剩余壽命與現(xiàn)時(shí)壽命6.4延遲與終止過(guò)程6.5馬爾可夫更新過(guò)程的定義6.6狀態(tài)分類(lèi)與極限概率6.7馬爾可夫更新方程與極限定理6.8再生過(guò)程與報(bào)酬過(guò)程6.9廣義半馬氏過(guò)程簡(jiǎn)介習(xí)題六

更新過(guò)程是Poisson過(guò)程的推廣，將其與馬爾可夫過(guò)程結(jié)合就得到了馬爾可夫更新過(guò)程(也稱(chēng)為半馬爾可夫過(guò)程)，這兩類(lèi)隨機(jī)過(guò)程具有廣泛的應(yīng)用。本章將分別介紹它們。

6.1更新過(guò)程的定義

在2.6節(jié)中我們知道Poisson過(guò)程是這樣一類(lèi)計(jì)數(shù)過(guò)程:其任意兩次相鄰的到達(dá)間隔時(shí)間是相互獨(dú)立同參數(shù)指數(shù)分布的。比這含義再?gòu)V一點(diǎn)的是到達(dá)間隔時(shí)間相互獨(dú)立同分布但分布函數(shù)可以任意的計(jì)數(shù)過(guò)程，這就是更新過(guò)程。這類(lèi)隨機(jī)過(guò)程描述在一系列時(shí)刻點(diǎn)上系統(tǒng)變新(稱(chēng)之為更新)且兩相繼更新時(shí)刻點(diǎn)(稱(chēng)為更新點(diǎn))的間隔是獨(dú)立同分布的隨機(jī)系統(tǒng)，刻畫(huà)此類(lèi)系統(tǒng)的是兩相鄰更新點(diǎn)間隔時(shí)間的分布函數(shù)。

正式地，設(shè){Xn

，

n=1，

2，…}是相互獨(dú)立的非負(fù)隨機(jī)變量，分布函數(shù)均為F(t)，假定F

(0)<1(請(qǐng)讀者考慮:當(dāng)F(0)=1時(shí)將會(huì)怎樣)。由于Xn

非負(fù)，故EXn

存在(可能是無(wú)窮)，記

這里，μ是平均(期望)更新間隔時(shí)間，

Tn是第n

次更新發(fā)生的時(shí)間，于是N

(t

)表示系統(tǒng)在[0，

t]中發(fā)生的更新次數(shù)。由于Xn

獨(dú)立同分布，因此系統(tǒng)在時(shí)刻T1，

T2

，…與新的一樣重新開(kāi)始。

我們說(shuō)N

(t

)是有限的，從而是隨機(jī)變量。實(shí)際上，由強(qiáng)大數(shù)定律知以概率1有Tn/n→μ，所以Tn≤t以概率1只對(duì)有限多個(gè)n

成立，從而N

(t)以概率1有限。

定義6.1.1稱(chēng){N

(t)，

t≥0}或{T0，

T1

，…}是更新過(guò)程，稱(chēng)Tn

為第n個(gè)更新點(diǎn)，稱(chēng)F為更新分布(函數(shù))。

更新論的主要目的是由Xn

的分布函數(shù)F

(t)導(dǎo)出有關(guān)N(t)和Tn

的一些有用的性質(zhì)。例如，[0，

t]中的期望更新次數(shù)

稱(chēng)之為更新函數(shù)。

由于獨(dú)立隨機(jī)變量和的分布函數(shù)是各隨機(jī)變量分布函數(shù)的卷積，因此Tn

作為X1

，

X2

，…，

Xn

的和，其分布函數(shù)

其中Fn

(t)是F(t)的n

重卷積:F

1(t)=F(t)，而

同時(shí)，由(6.1.2)式易知，

Tn與N(t)有以下關(guān)系:

于是

由此，我們可得到更新函數(shù)的一個(gè)表達(dá)式

由于Fn

(t

)非負(fù)，以上級(jí)數(shù)自然是有定義的。如下引理進(jìn)一步說(shuō)明更新函數(shù)是有限的。

引理6.1.1m

(t)<∞，

t≥0。

證明由Xn

的獨(dú)立同分布性知，

Xm+1+…+Xn

與Tn-m同分布函數(shù)，因此Tn的分布函數(shù)等于Tm

的分布函數(shù)與Tn-m的分布函數(shù)的卷積。因此由分布函數(shù)的單調(diào)性知

特別地，對(duì)任意的正整數(shù)n，

r，

k，有

由此遞推可得

因此對(duì)任意的正整數(shù)r

，有

對(duì)t≥0，若Fr

(t

)<1，則以上級(jí)數(shù)是幾何收斂的，而由強(qiáng)大數(shù)定律知Tn

以概率1趨于∞，因此，對(duì)任一t≥0，必有r使得Fr

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

由(6.1.8)式可知，

m(t)是非降函數(shù)，進(jìn)而，由級(jí)數(shù)在任一區(qū)間[0，

t]中的一致收斂性及分布函數(shù)的右連續(xù)性知m

(t

)也是右連續(xù)的。因此，除了m(∞)≠1(實(shí)際上m(∞)=∞)外，m

(t)具有與分布函數(shù)類(lèi)似的性質(zhì)。

上面，我們討論了由分布函數(shù)F

確定更新函數(shù)m

的問(wèn)題。反過(guò)來(lái)，這也是成立的。

引理6.1.2分布函數(shù)F

(t)與更新函數(shù)m(t)相互唯一確定。

證明在(6.1.8)式中取拉普拉斯變換可得

由于一個(gè)函數(shù)與其拉普拉斯變換間相互唯一確定，

F

與m

也相互唯一確定。

下面給出更新過(guò)程的幾個(gè)例子。

例6.1.1

(1)Poisson過(guò)程。比率為λ的Poisson過(guò)程N(yùn)(t)是相鄰更新點(diǎn)間隔時(shí)間服從參數(shù)為λ的指數(shù)分布的更新過(guò)程。

(2)計(jì)數(shù)過(guò)程。由記錄儀器(稱(chēng)之為計(jì)數(shù)器)所記錄的相繼到達(dá)的電子脈沖或信號(hào)的間隔時(shí)間常常是獨(dú)立同分布的。此時(shí)的計(jì)數(shù)過(guò)程是更新過(guò)程。

(3)交通流。具有足夠長(zhǎng)的高速公路的某個(gè)車(chē)道中的相繼汽車(chē)間的距離可看作是獨(dú)立同分布的，從而形成一個(gè)更新過(guò)程;同樣，通過(guò)某一地點(diǎn)的汽車(chē)數(shù)可看作是一個(gè)更新過(guò)程。這是兩個(gè)更新過(guò)程，分別是從空間上和時(shí)間上來(lái)描述公路上的汽車(chē)流的。

(4)排隊(duì)系統(tǒng)中的更新過(guò)程。在一個(gè)單服務(wù)臺(tái)的排隊(duì)系統(tǒng)中有多個(gè)更新過(guò)程。如①顧客的到達(dá)過(guò)程?？醋魇且粋€(gè)更新過(guò)程;②顧客按一更新過(guò)程到達(dá)時(shí)，相繼忙期的開(kāi)始時(shí)間形成一個(gè)更新過(guò)程，這里忙期是指服務(wù)員忙的時(shí)期;③當(dāng)顧客按Poisson過(guò)程到達(dá)時(shí)，相繼忙期的結(jié)束時(shí)刻是一個(gè)更新過(guò)程;④當(dāng)服務(wù)時(shí)間是指數(shù)分布時(shí)，服務(wù)完的顧客的離去也形成一個(gè)更新過(guò)程。

(5)生產(chǎn)/存儲(chǔ)系統(tǒng)。在大多數(shù)生產(chǎn)/存儲(chǔ)系統(tǒng)中，需求的到達(dá)常假定是更新過(guò)程，在多種存儲(chǔ)策略下，庫(kù)存的相繼恢復(fù)時(shí)間等也構(gòu)成更新過(guò)程。

(6)系統(tǒng)更換。設(shè)有一系統(tǒng)，其壽命為X

，當(dāng)其失效時(shí)用同一類(lèi)型的系統(tǒng)更換之，更換時(shí)間為Y

。于是若記Xn

和Yn

分別為第n

次壽命和第n次更換時(shí)間，當(dāng){Xn+Yn

，

n=1，

2，…}獨(dú)立同分布時(shí)就成為一個(gè)更新過(guò)程。

(7)在馬氏鏈{Xn

，

n=0，

1，

2，…}中，對(duì)狀態(tài)j記

則在X0=j

的條件下，

Zn

是獨(dú)立同分布的，從而產(chǎn)生一個(gè)更新過(guò)程。

(8)更新過(guò)程還出現(xiàn)在保險(xiǎn)、人口增長(zhǎng)、遺傳進(jìn)化、工程系統(tǒng)、經(jīng)濟(jì)系統(tǒng)等眾多領(lǐng)域中。

6.2更新方程與極限定理

設(shè)函數(shù)g(t

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

∞)上，

F(t)是非負(fù)分布函數(shù)，它們有如下關(guān)系:

如果h

(t

)和F(t)已知，而g(t)未知，則g(t)可看作是以上積分方程的解。(6.2.1)式是一特殊的積分方程，我們稱(chēng)之為更新方程。在更新理論中，有許多量都滿足更新方程，例如更新函數(shù)m

(t

)。實(shí)際上，由全期望公式可得

當(dāng)?shù)谝淮胃掳l(fā)生時(shí)間x≤t時(shí)，從x

開(kāi)始，系統(tǒng)與新的一樣，于是[0，

t]中的期望更新數(shù)等于發(fā)生在x

上的更新數(shù)1加上在(x，

t]上的期望更新數(shù);而當(dāng)x>t時(shí)，[0，

t]中沒(méi)有更新。

因此

代入上式得

這是較為特殊的更新方程，已知函數(shù)F，求函數(shù)m。

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

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

證明注意到(6.2.1)式的卷積形式為g=h+g*F，取其拉普拉斯變換可得

由此及(6.1.10)式得

取拉普拉斯反變換即得(6.2.3)式。

現(xiàn)在，我們考慮m

(t

)的極限性態(tài)。由于平均更新時(shí)間是μ

，即平均每隔時(shí)間μ

就發(fā)生一次更新。因此容易猜想當(dāng)μ<∞時(shí)，

N(∞)∶=

N(t

)=∞。所以考慮m(t)的極限一般地沒(méi)有什么意義。與馬氏鏈中(定理5.4.5)類(lèi)似，我們考慮單位時(shí)間內(nèi)的平均更新次數(shù)，即N

(t)/t

的極限。從其含義容易猜想其極限應(yīng)是1/μ

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

定理6.2.2以概率1有

證明由N(t)的定義易知

因此

由于N(∞)有限當(dāng)且僅當(dāng)有n

使得Tn=∞

，于是

故N(∞)以概率1等于∞，也即當(dāng)t→∞時(shí)，

N(t)以概率1趨于∞。而由強(qiáng)大數(shù)定律知以概率1有Tn/n→μ。因此當(dāng)t→∞時(shí)，以概率1有

由此及(6.2.4)式知定理結(jié)論成立。

關(guān)于單位時(shí)間平均期望更新次數(shù)，即m

(t

)/t

的極限，易知它亦應(yīng)等于1/μ，但其證明將稍為復(fù)雜一些。以下我們先給出停時(shí)的概念。

定義6.2.1稱(chēng)取正整數(shù)值的隨機(jī)變量N

是隨機(jī)序列{X

n

，

n≥0}的一個(gè)停時(shí)，如果對(duì)任一n

，事件{N=n}與

Xn+1，

Xn+2，…相互獨(dú)立。

直觀上，我們一個(gè)一個(gè)地觀察{Xn

，

n≥0}，而N

表示停止觀察的時(shí)間，

N=n表示在觀察了X1

，

X2

，…，

Xn

之后，但在觀察Xn+1，

Xn+2，…之前停止。于是，停時(shí)表示何時(shí)停止只與已觀察的隨機(jī)變量有關(guān)，而與未觀察的無(wú)關(guān)。

例6.2.1設(shè){Xn

，

n≥0}相互獨(dú)立，

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

則N是一個(gè)停時(shí)。

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

也是一個(gè)停時(shí):

定理6.2.3(Wald方程)設(shè)X1

，

X2，…獨(dú)立同分布，

EX1

有限，

N

是一個(gè)停時(shí)且EN有限，則

證明記χ為示性函數(shù)，由停時(shí)的定義可知N≥n表示在觀察了X1

，

X2

，…，

Xn-1之后不停止，因此隨機(jī)變量χ(N≥n)由X1

，

X2

，…Xn-1確定而與Xn

獨(dú)立。因此

請(qǐng)讀者考慮這里能否運(yùn)用全期望公式?

例6.2.1(續(xù))對(duì)(1)應(yīng)用Wald方程有

所以EN=20。

若對(duì)(2)應(yīng)用Wald方程，則有

不成立，這只能說(shuō)明EN=∞，定理6.2.3中的條件不滿足。

定理6.2.4(基本更新定理)

證明首先，我們假定μ<∞。為應(yīng)用Wald方程，我們需要為更新過(guò)程構(gòu)造一個(gè)停時(shí)，注意到

或者

因此N(t

)+1是一個(gè)停時(shí)(但N(t)不是停時(shí))。進(jìn)而E(N(t)+1)=m(t)+1<∞。故由Wald方程得

由此及TN

(t)+1≥t

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

定義6.2.2稱(chēng)非負(fù)隨機(jī)變量X是格的，如果有正常數(shù)d使即X取值于d的整數(shù)倍上，最大的d稱(chēng)為X的周期。當(dāng)X是格隨機(jī)變量時(shí)，其分布函數(shù)也稱(chēng)為是格的。如果X沒(méi)有周期，則稱(chēng)之為非格隨機(jī)變量。

以下兩個(gè)定理的證明可參見(jiàn)參考文獻(xiàn)[31]。

定理6.2.5(Blackwell定理)(1)若F非格，則對(duì)任一a≥0有

(2)若F

是格的且有周期d，則(6.2.9)式對(duì)a=nd成立，

n=1，

2，…。

(6.2.9)式表示當(dāng)時(shí)間足夠長(zhǎng)之后，在任一長(zhǎng)度為a

的區(qū)間中的期望更新次數(shù)為a/μ。

定理6.2.6(關(guān)鍵更新定理)(1)若F(t)不是格的，

h(t)直接可積，則

其中約定1/∞=0。

(2)若F是格的且有周期d，函數(shù)h直接可積，則對(duì)任一a≥0有

關(guān)鍵更新定理是非常重要而又有用的一個(gè)結(jié)果。在應(yīng)用中，將某更新時(shí)間作為條件，導(dǎo)出一個(gè)更新方程，對(duì)此應(yīng)用定理6.2.1得到更新方程的解，就可應(yīng)用關(guān)鍵更新定理了。下面來(lái)看幾個(gè)例子。

例6.2.2(交替更新過(guò)程)考慮一個(gè)系統(tǒng)，其工作壽命為X1

，發(fā)生故障后進(jìn)行修理，修理時(shí)間為Y1

，修復(fù)后系統(tǒng)與新的一樣，工作壽命為X2

，故障后的修理時(shí)間為Y2

，…，假定Xn

相互獨(dú)立同分布函數(shù)F，

Yn

相互獨(dú)立同分布函數(shù)G，{Xn

}與{Yn

}也相互獨(dú)立。記H=F*G為X1+Y1的分布函數(shù)，

A(t)=P{系統(tǒng)在t時(shí)工作}。

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

H不是格的，則

證明記事件E={系統(tǒng)在t時(shí)工作}，則由全期望公式可得

所以

于是得到如下更新方程:

由此還可知

例6.2.3(更新報(bào)酬過(guò)程)設(shè)N(t)是一更新過(guò)程，

Xn

是更新點(diǎn)間隔時(shí)間，

Yn

是第n

次更新時(shí)系統(tǒng)獲得的報(bào)酬(可為負(fù))，

Yn

可與Xn

有關(guān)，但假定(Xn，

Yn

)，

n=1，

2，…相互獨(dú)立同分布。記

表示到t時(shí)所獲得的總報(bào)酬。

命題6.2.2若E|Yn

|和EXn均有限，則

當(dāng)t→∞時(shí)。

由于ε任意，所以g(t)/t→0，結(jié)論成立。

6.3剩余壽命與現(xiàn)時(shí)壽命

更新論中討論的隨機(jī)變量還有剩余壽命、現(xiàn)時(shí)壽命和總壽命等三種，三者分別定義如下:

三者的關(guān)系如圖6－1所示。圖6－1剩余壽命γt、現(xiàn)時(shí)壽命δt和總壽命β

定理6.3.1γt

的分布函數(shù)如下:

進(jìn)而，若F為非格，則

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

記P(t)=P{γt>x}，將X1作為條件有

從而

對(duì)以上更新方程應(yīng)用定理6.2.1和關(guān)鍵更新定理可得當(dāng)F為非格時(shí)，

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

當(dāng)F為格時(shí)，

γt

的極限分布請(qǐng)讀者給出。

與(6.3.3)式類(lèi)似，我們還有

由此及定理6.3.1即可得到有關(guān)δt

的分布函數(shù)以及(δt，

γt

)的聯(lián)合分布函數(shù)所滿足的更新方程和極限分布。具體結(jié)果請(qǐng)讀者寫(xiě)出。

最后，關(guān)于總壽命βt的分布函數(shù)，我們既可從(6.3.5)式類(lèi)似得到，也可直接應(yīng)用定理6.3.1證明中的方法得到。記Q(t)=P{βt>x}，由于

其中x∨t=max{x，

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

由此即可得到以下定理。

定理6.3.2

進(jìn)而，當(dāng)F

為非格時(shí)，

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

γt和βt

的極限分布相同，且當(dāng)μ有限時(shí)，它們?nèi)允欠植己瘮?shù)。

6.4延遲與終止過(guò)程

我們先來(lái)討論延遲(delayed)更新過(guò)程。在很多計(jì)數(shù)過(guò)程中，第一個(gè)更新間隔時(shí)間的分布函數(shù)與其余的不同，例如在某個(gè)非更新點(diǎn)t>0處開(kāi)始觀察系統(tǒng)，以及在例6.1.1的(7)中當(dāng)X0=j≠i時(shí)。

正式地，設(shè){Xn

，

n=1，

2，…}相互獨(dú)立，

X1

有分布函數(shù)G，

X2

、X3

、…有相同的分布函數(shù)F

，記Tn同(6.1.1)式中，而將(6.1.2)式中定義的N

(t)記為ND(t)，這里用下標(biāo)D

以示區(qū)別。

定義6.4.1稱(chēng)隨機(jī)過(guò)程{ND

(t)，

t≥0}為延遲更新過(guò)程。與N

(t

)中類(lèi)似，我們可得

其中F0(x)=1，

*號(hào)表示卷積，而G*F0=G。記(延遲)更新函數(shù)mD(t)=END(t)，則

其中m(t)是更新分布為F的更新函數(shù)。仍記

以下定理的證明留給讀者。

若F為格的且有周期d，則(6.4.5)式對(duì)a=nd成立，

n=0，

1，

2，…。

以下假定μ<∞，此時(shí)

是一分布函數(shù)，稱(chēng)為F的平衡分布，其拉普拉斯變換為

當(dāng)G=Fe

時(shí)的延遲更新過(guò)程是特別重要的，我們稱(chēng)之為平衡更新過(guò)程。由(6.3.2)式知，當(dāng)開(kāi)始觀察系統(tǒng)的時(shí)間t充分大時(shí)，可將之看作為平衡更新過(guò)程。記γDt

表示延遲更新過(guò)程N(yùn)D

(t)中的剩余壽命。以下定理的證明可見(jiàn)參考文獻(xiàn)[25]的定理3.15，它說(shuō)明了“平衡”的含義。

定理6.4.2對(duì)平衡更新過(guò)程:

由定理6.4.1知，

Fe是原更新過(guò)程N(yùn)(t)中t時(shí)的剩余壽命γt

的極限分布;而由定理6.4.2的(2)知，在平衡更新過(guò)程N(yùn)D(t)中剩余壽命γDt

的分布函數(shù)保持不變，就為Fe，這也是“平衡”的含義之一。定理6.4.2的(1)和(3)還說(shuō)明了“平衡”的另兩個(gè)含義。

直到現(xiàn)在為止，我們一直假定更新分布F是通常的分布函數(shù)，即F(∞)=1。但定義6.1.1對(duì)F(∞)<1(即P{Tn+1-Tn=∞}>0)也是成立的。

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

證明設(shè)F(∞)=1，由于N(∞)有限當(dāng)且僅當(dāng)有n使得Xn=∞，因此

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

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

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

基于以上定理，我們給出如下定義。

定義6.4.2稱(chēng)F(∞)=1時(shí)的更新過(guò)程為非終止的或常返的，稱(chēng)F(∞)<1時(shí)的更新過(guò)程是終止的或非常返的。

在應(yīng)用中所研究的隨機(jī)過(guò)程本身并不一定是更新過(guò)程，但其中可能存在一嵌入更新過(guò)程，且往往不知更新分布是否滿足F(∞)=1，此時(shí)，定理6.4.3就變得很重要。

關(guān)于更新過(guò)程的進(jìn)一步討論可參閱參考文獻(xiàn)[25]、[31]、[32]。

6.5馬爾可夫更新過(guò)程的定義

將Poisson過(guò)程中的更新分布一般化就得到了更新過(guò)程。而從連續(xù)時(shí)間馬爾可夫過(guò)程的理論知道，它在每個(gè)狀態(tài)處的逗留時(shí)間是指數(shù)分布的(參數(shù)依賴于所處狀態(tài))。與更新過(guò)程一樣，將此指數(shù)分布一般化，就得到了所謂的馬爾可夫更新過(guò)程，也稱(chēng)為半馬爾可夫過(guò)程。它是馬爾可夫過(guò)程和更新過(guò)程的結(jié)合，從而廣于這兩者。

設(shè)對(duì)n=0，

1，

2，…，隨機(jī)變量X

n

取值于一可數(shù)狀態(tài)集合S

，隨機(jī)變量Tn取值于[0，

∞)，且0=T

0≤T

1≤T2≤…。我們不妨設(shè)S={0，

1，

2，…}。

定義6.5.1稱(chēng)二元隨機(jī)過(guò)程{X，

T}={Xn

，

Tn，

n=0，

1，

2，…}為馬爾可夫更新過(guò)程，簡(jiǎn)稱(chēng)為馬氏更新過(guò)程，如果

對(duì)所有的n，i0

，…，

in

，

j，

t0

，…tn

，

t均成立。

我們?cè)谶@里考慮時(shí)齊的情形，即

與n

無(wú)關(guān)。稱(chēng)矩陣函數(shù)Q

(t

)=(Qij(t

))為狀態(tài)空間S

上的半馬爾可夫核，簡(jiǎn)稱(chēng)為半馬氏核。

定義

其中當(dāng)pij=0時(shí)，由定義知Qij(t

)≡0，此時(shí)Qij(t

)/pij可任意取值，它不影響我們的討論，但為確定起見(jiàn)，我們約定此時(shí)Fij(t

)是常數(shù)1的分布函數(shù)。pij和Fij(t

)均有它們自己的概率

含義。我們先來(lái)看pij。由定義，

P=(pij)構(gòu)成一個(gè)隨機(jī)矩陣，從而是某個(gè)馬氏鏈的轉(zhuǎn)移概率矩陣。實(shí)際上，由(6.5.1)式和(6.5.2)式易知

于是得到以下定理。

定理6.5.1X={Xn

，

n=0，

1，

2…}是狀態(tài)空間為S

、轉(zhuǎn)移概率矩陣為P=(pij)的齊次馬氏鏈(稱(chēng)之為嵌入馬氏鏈)。

再來(lái)看Fij(t

)。不難看出，對(duì)任意的i，

j∈S，F(xiàn)ij(t)是一個(gè)分布函數(shù)，實(shí)際上，

引理6.5.1對(duì)任意的n≥1，

t1

，…，

tn

≥0，

以上引理是說(shuō)當(dāng)已知馬氏鏈{Xn}時(shí)，

T1-T0

，…，

Tn-Tn-1

是相互獨(dú)立的，而且Tn-Tn-1

的分布函數(shù)僅僅依賴于

Xn

和Xn-1。

當(dāng)系統(tǒng)只有一個(gè)狀態(tài)時(shí)，即

S為單點(diǎn)集時(shí)，容易看出{Tn

，

n=0，

1，

2，…}是更新過(guò)程。更一般地，我們有以下定理，其證明可見(jiàn)參考文獻(xiàn)[32]。

定理6.5.2對(duì)狀態(tài)j∈S，定義Nj

(t

)為在(0，

t]中達(dá)到狀態(tài)j的次數(shù)，則Nj

(t)是一個(gè)更新過(guò)程或延遲更新過(guò)程。

對(duì)Nj

(t

)的更新時(shí)刻，設(shè)Zn

由例6.1.1的(7)中定義，則第n個(gè)更新時(shí)刻點(diǎn)為T(mén)jn=TZn。設(shè)Kj

表示在嵌入馬氏鏈X

中的首次到達(dá)狀態(tài)j的時(shí)間，在初始條件X0=i下，其分布由f(k)ij給出，則對(duì)n≥0，

Tjn+1-Tjn

與TKj同分布，從而

因此，在初始條件X0

=j下，

Nj

((t)是更新過(guò)程;而在X0=i≠j時(shí)，一般地Nj

(t)僅是一個(gè)延遲更新過(guò)程。

定理6.5.1和6.5.2說(shuō)明了“馬爾可夫更新過(guò)程”是馬爾可夫過(guò)程和更新過(guò)程相結(jié)合的產(chǎn)物。

馬氏更新過(guò)程也可以從另一角度描述。我們構(gòu)造隨機(jī)過(guò)程Y={Y(t)，

t≥0}如下:

其中，

Δ∈S為一記號(hào);supnTn

是過(guò)程的終止時(shí)間。從而Y(t)=Δ表示馬氏更新過(guò)程已經(jīng)結(jié)束。

Y

是一個(gè)一元隨機(jī)過(guò)程，

Y(t)可解釋為某系統(tǒng)在t時(shí)的狀態(tài)，此系統(tǒng)在狀態(tài)處停留一段時(shí)間后轉(zhuǎn)移到另一個(gè)狀態(tài)，停留時(shí)間區(qū)間[Tn

，

Tn+1)的長(zhǎng)度是隨機(jī)的，其分布依賴于所停留的狀態(tài)Xn

和下一步將要到達(dá)的狀態(tài)Xn+1。它相繼到達(dá)的狀態(tài)形成一個(gè)馬氏鏈，當(dāng)已知此馬氏鏈時(shí)，它相繼的停留時(shí)間相互獨(dú)立。

定義6.5.2稱(chēng)隨機(jī)過(guò)程

Y={Y(t)，

t≥0}為半馬爾可夫過(guò)程，簡(jiǎn)稱(chēng)為半馬氏過(guò)程；稱(chēng)Q

(t)為其半馬氏核，

X={Xn

，

n=0，

1，

2，…}為其嵌入馬氏鏈。

這里用“半馬氏過(guò)程”是因?yàn)閅具有“某種”馬氏性:已知現(xiàn)在、將來(lái)與過(guò)去無(wú)關(guān)，只是這里的“現(xiàn)在”應(yīng)是狀態(tài)轉(zhuǎn)移時(shí)刻，即某個(gè)

Tn

。

本章以下將不再區(qū)分半馬氏過(guò)程與馬氏更新過(guò)程。

下面討論在有限時(shí)間區(qū)間內(nèi)是否會(huì)發(fā)生無(wú)窮多次狀態(tài)轉(zhuǎn)移的問(wèn)題。首先，定義

自然，

Qi

(t

)是在狀態(tài)i處逗留時(shí)間的分布函數(shù)，即

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

?i∈S。對(duì)t≥0，仍記N(

t)=sup{n|Tn≤t}，不難證明

定義6.5.3稱(chēng)狀態(tài)i

是正則的，如果

稱(chēng)馬氏更新過(guò)程是正則的，如果所有狀態(tài)均是正則的。

由本章第一節(jié)可知，對(duì)任一i∈S，{Ni

(t)，

t≥0}是一個(gè)更新過(guò)程(可能延遲)，且以概率1有Ni

(t

)對(duì)任意的t均有限。因此，當(dāng)狀態(tài)數(shù)有限時(shí)，以概率1有

所以，有限狀態(tài)馬氏更新過(guò)程必定是正則，但狀態(tài)可數(shù)時(shí)就不一定了，反例如下。

例6.5.1設(shè)對(duì)某馬氏更新過(guò)程有

則

因此，此馬氏更新過(guò)程沒(méi)有正則狀態(tài)。

但如下定理說(shuō)明在一定條件下，馬氏更新過(guò)程就是正則的。

定理6.5.3(正則性定理)若以下兩個(gè)條件之一成立，則馬氏更新過(guò)程是正則的:

(1)存在常數(shù)δ>0和ε>0，使

(2)對(duì)任一i∈S，在X0=i的條件下，馬氏鏈{Xn

，

n=0，

1，

2，…}以概率1到達(dá)某一常返狀態(tài)。

證明可見(jiàn)參考文獻(xiàn)[25]的命題5.1。定理中的條件(1)和(2)均稱(chēng)為正則性條件。

以下我們假定所討論的馬氏更新過(guò)程總是正則的。

現(xiàn)在來(lái)看幾個(gè)例子。

例6.5.2如果有非負(fù)數(shù)組{λi

，

i∈S}使

則由(5.5.19)式和(5.5.21)式知Y是馬氏過(guò)程。因此，馬氏過(guò)程是特殊的半馬氏過(guò)程。

例6.5.3交通流。設(shè)T0，

T1

，…是某高速公路上相繼車(chē)輛的位置(時(shí)間或空間上的)，記Xn

為第n

輛車(chē)的類(lèi)型(如小車(chē)、卡車(chē)、公共汽車(chē)、重量、大小、速度等)，通常Xn

是一個(gè)馬氏鏈，而Tn+1-Tn

僅與類(lèi)型Xn

和Xn+1有關(guān)，從而(X，

T)是一個(gè)馬氏更新過(guò)程。

例6.5.4M/G/1排隊(duì)。顧客按率為λ的Poisson過(guò)程到達(dá)，服務(wù)時(shí)間相互獨(dú)立同分布函數(shù)G

，一個(gè)服務(wù)臺(tái)。記T0=0≤T1≤T2

≤…為顧客的相繼離去時(shí)間，

Xn

為第n

次離去后系統(tǒng)中的顧客數(shù)，則(X，

T)={Xn

，

Tn

，

n=0，

1，

2，…}為馬氏更新過(guò)程，其核為

其中

6.6狀態(tài)分類(lèi)與極限概率

馬氏更新過(guò)程同時(shí)具有馬氏鏈和更新過(guò)程的很多性質(zhì)。我們先來(lái)討論馬氏更新過(guò)程的狀態(tài)分類(lèi)，它與馬氏鏈中的狀態(tài)分類(lèi)類(lèi)似。首先，對(duì)狀態(tài)i，j∈S和t≥0，定義

Gij(t)表示過(guò)程從狀態(tài)i

出發(fā)在t

之前到達(dá)狀態(tài)

j的概率。若以Tj

1

表示更新過(guò)程N(yùn)j

(t)中第一次更新時(shí)間，則顯然有Gij(t)=P{Tj

1≤t|X0=i}。Gij(∞)表示從i出發(fā)，終究要到達(dá)j的概率。Pij(t)相應(yīng)于連續(xù)時(shí)間馬氏過(guò)程中的狀態(tài)轉(zhuǎn)移概率。

基于Gij(t)，我們定義從i出發(fā)到達(dá)j的期望時(shí)間為

于是稱(chēng)μii

為狀態(tài)i

的平均返回時(shí)間。

現(xiàn)在，我們給出各類(lèi)狀態(tài)的定義，以及馬氏鏈中相應(yīng)定義的推廣。

定義6.6.1(1)稱(chēng)狀態(tài)i

可達(dá)

j，如果i=j或者Gij(∞)>0;稱(chēng)i

和

j互通，如果

i可達(dá)

j且

j可達(dá)

i;

(2)稱(chēng)狀態(tài)

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

=1;否則，稱(chēng)狀態(tài)i是非常返的(或瞬時(shí)的);

(3)稱(chēng)常返狀態(tài)i

是正常返的，如果μii

<∞;否則稱(chēng)狀態(tài)i是零常返的;

(4)互通是一個(gè)等價(jià)關(guān)系，等價(jià)類(lèi)簡(jiǎn)稱(chēng)為類(lèi)，記Ci為包含狀態(tài)i

的等價(jià)類(lèi);

(5)稱(chēng)馬氏更新過(guò)程(半馬氏過(guò)程)是不可約的，如果它只有一個(gè)類(lèi)，即所有狀態(tài)互通。容易猜想，馬氏更新過(guò)程(X，

T)中的狀態(tài)性質(zhì)與嵌入馬氏鏈X

中的狀態(tài)性質(zhì)有密切關(guān)系。為此，首先注意到(X，

T)和X

間的如下關(guān)系:

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

定理6.6.1狀態(tài)i在馬氏更新過(guò)程(X，

T)中常返(或非常返、互通)當(dāng)且僅當(dāng)狀態(tài)i在嵌入馬氏鏈X

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

由此定理可知，(X，

T)有與X

相同的狀態(tài)類(lèi)。為討論(X，

T)和X

中正常返(或零常返)間的關(guān)系，我們需要在(X，

T)和X中有關(guān)正常返的判別準(zhǔn)則之間架起一座橋梁。

定義ηij為過(guò)程從i

出發(fā)下一步到達(dá)

j的條件下，在i的期望逗留時(shí)間;ηi為過(guò)程在

i的期望逗留時(shí)間。它們分別用公式表示為

現(xiàn)在，利用n

時(shí)首次到達(dá)狀態(tài)j

，中間依次經(jīng)過(guò)i1≠j，…，

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

定理6.6.2對(duì)常返狀態(tài)i，設(shè)類(lèi)Ci有限，則i

在馬氏更新過(guò)程(X，

T)中正常返，當(dāng)且僅當(dāng)i

在嵌入馬氏鏈中正常返，且對(duì)j∈Ci

均有ηj<∞。

證明由(6.6.5)式可得

其中

是在嵌入馬氏鏈X

中狀態(tài)i的平均返回時(shí)間。設(shè)i在(X，

T)中正常返，即μ

ii<∞，如果有j∈Ci

使得ηi=∞，則從i出發(fā)以正概率使平均返回時(shí)間無(wú)窮，從而μii=∞，與μii<∞矛盾。因此對(duì)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

<∞。

反過(guò)來(lái)，若μ*ii

<∞且η

j<∞，

?j∈Ci

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

j，

k∈Ci}∈(0，

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

由定理可知對(duì)(X，

T)的一個(gè)類(lèi)C

，若其中有一個(gè)狀態(tài)正常返，則它在X

中也是正常返的，由馬氏鏈的知識(shí)(定理5.3.5)知，

C

中的狀態(tài)在X

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

中狀態(tài)在(X，

T)中也都是正常返的，這就是說(shuō)正常返(或零常返)當(dāng)它所在的類(lèi)有限時(shí)是類(lèi)性質(zhì)(互通的狀態(tài)有相同的狀態(tài)類(lèi)型)。

6.7馬爾可夫更新方程與極限定理

本節(jié)將更新論中的更新方程與極限定理推廣到馬氏更新過(guò)程中來(lái)。為使記號(hào)簡(jiǎn)單起見(jiàn)，我們以Pi

和Ei

分別表示在X0=i條件下的條件概率和條件期望。進(jìn)而，為避免平凡，我們假定:

對(duì)n≥0，定義

由定理6.5.2知，對(duì)i，

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

Nj(t)是一個(gè)延遲更新過(guò)程，其更新函數(shù)為

由假設(shè)(6.7.1)式及引理6.1.1易知mij(t)有限。我們稱(chēng)mij

(·)是馬爾可夫更新函數(shù)，稱(chēng)族m={mij(·)|i，

j∈S}是馬爾可夫更新核。

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

其中Gnjj是分布Gjj

的n

重卷積。上式將mij(t)轉(zhuǎn)化為mjj(t)的確定。

定義函數(shù)空間B

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

∞)→[0，

∞)|

對(duì)i∈S，

g(i，·)在任一有限區(qū)間上均有界;對(duì)t≥0，g(·，

t)在S

上有界。}

對(duì)g∈B

，定義半馬氏核Q

與

g

的卷積為

顯然Q*g∈B。m*g類(lèi)似定義且當(dāng)g

∈B

時(shí)亦有m*g∈B。

稱(chēng)g∈B

滿足馬爾可夫更新方程，如果有h∈B使

寫(xiě)成卷積形式為

更新方程(6.2.1)式的卷積形式與上式完全相同。關(guān)于馬氏更新方程的解有以下結(jié)論。

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

其中f

滿足

特別地，

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

證明由(6.7.7)式遞推可得

由于Q

nij(t)對(duì)n單調(diào)下降，

g非負(fù)，

Qn+1*g

對(duì)n單調(diào)下降，從而其極限存在，記為f

，易知

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

定義馬氏更新過(guò)程(X，

T)的壽命為隨機(jī)變量

關(guān)于方程(6.7.9)式只有零解，或馬氏更新方程(6.7.7)式有唯一解的若干條件給出如下。

定理6.7.2

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

(2)如果只有有限個(gè)非常返狀態(tài)(特別地S有限)，則P{L=∞}=1。

(3)如果有常數(shù)δ>0使則P{L=∞}=1。

為給出討論更新解的極限定理，需推廣直接(黎曼)可積的概念。

定義6.7.1設(shè)π

是

S上的非負(fù)向量，稱(chēng)函數(shù)g∈B

是相對(duì)于π直接可積的，如果

對(duì)任意的a>0均有限，且當(dāng)a→0時(shí)，

σ1

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

π

是所有如此函數(shù)g所組成的集合。

定理6.7.3設(shè)(X，

T)不可約常返，向量π≥0滿足πP

=π，

g

∈B

π

，則當(dāng)所有Gij(j∈S)均是非格時(shí)

當(dāng)Gjj

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

其中γij是分布

Gij中的第一個(gè)跳躍點(diǎn)，而約定當(dāng)x<0時(shí)g

(j，

x)=0。

最后，由定理6.7.3可證得以下關(guān)于Pij(t

)當(dāng)t→∞

時(shí)的極限。

定理6.7.4設(shè)(X，

T)不可約常返，向量π≥0滿足π=πP，

Gij均為非格，則對(duì)i∈S均有

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

，則

其中γij同定理6.7.3中，

Qj(x)=0(x<0時(shí))。

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

T)的任一個(gè)常返類(lèi)，它們的證明均可見(jiàn)參考文獻(xiàn)[32]。

6.8再生過(guò)程與報(bào)酬過(guò)程

現(xiàn)在，我們考慮這樣一類(lèi)隨機(jī)過(guò)程，它存在一個(gè)時(shí)刻，使得從此時(shí)此刻開(kāi)始的過(guò)程與原過(guò)程完全相同。

定義6.8.1對(duì)狀態(tài)集S={0，

1，

2，…}上的隨機(jī)過(guò)程X={X(t)，

t≥0}，設(shè)有隨機(jī)變量T1

使得{X

(t-T1

)，

t≥T1}與原過(guò)程

X完全相同(概率的)，則稱(chēng)

X是一個(gè)再生過(guò)程。

由定義知還存在時(shí)T2

，

T3

，…，它們具有與T1

相同的性質(zhì)，從而{T1

，

T2

，…}形成一個(gè)更新過(guò)程，我們稱(chēng)兩相繼更新間隔為一個(gè)周期。

顯然，更新過(guò)程是再生過(guò)程，

T1

就是首次更新時(shí)間。常返馬氏更新過(guò)程也是再生過(guò)程，T1

表示首次到達(dá)初始狀態(tài)的時(shí)間。

記Pj

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

T1

的分布函數(shù)為

F。以下定理仍運(yùn)用關(guān)鍵更新定理證得。

定理6.8.1設(shè)T1在某個(gè)區(qū)間上有密度，即有0≤a<b≤∞及函數(shù)f

(x

)使得對(duì)

t∈[a，

b]有P{T1

≤t}=P

{T1

≤a}+

證明運(yùn)用更新論中的方法有

由定理6.2.1和關(guān)鍵更新定理可得

但

因此

其中χ為示性函數(shù)，而就表示在一個(gè)周期[0，

T1

]中過(guò)程處于狀態(tài)j的總時(shí)間。

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

現(xiàn)在，我們進(jìn)一步假定當(dāng)處于狀態(tài)i

時(shí)，過(guò)程將以率

r(

i)獲得報(bào)酬，于是t

時(shí)記得的報(bào)酬率為r(X(t))，我們稱(chēng)之為再生報(bào)酬過(guò)程。當(dāng)X

是半馬氏過(guò)程時(shí)，就稱(chēng)r(X(t))為半馬氏報(bào)酬過(guò)程。

由命題6.2.2，可立得以下結(jié)論。

定理6.8.2若

以概率1成立；進(jìn)而

以上兩式給出了長(zhǎng)期運(yùn)行下單位時(shí)間平均(期望)報(bào)酬的表達(dá)式，兩者是相同的。對(duì)于等式的右邊，我們還有以下進(jìn)一步的結(jié)論。

定量6.8.3設(shè)定理6.8.1和6.8.2中的條件均成立，則

證明由積分的定義可知

因此(6.8.6)式成立。

直觀上，(6.8.6)式的左邊和右邊均表示單位時(shí)間內(nèi)的平均期望報(bào)酬。

最后，我們來(lái)研究半馬氏報(bào)酬過(guò)程。設(shè)報(bào)酬率函數(shù)r(

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

考慮

式中，

α>0是連續(xù)折扣因子，表示t

時(shí)獲得的單位報(bào)酬僅值0

時(shí)的e-αt;Vα(i)表示從初始狀態(tài)i

出發(fā)的期望折扣總報(bào)酬。在關(guān)于r(i)的假設(shè)下，

Vα

(i)存在，且分別有界，非負(fù)或者非正。由全期望公式，有

由于

故

記

其中，

R

(i

)表示當(dāng)Xn=i時(shí)在[Tn

，

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

時(shí)計(jì)算的期望折扣總報(bào)酬;βij則表示Tn

+1時(shí)的一單位報(bào)酬僅值Tn

時(shí)的βij。我們稱(chēng)βij為一階段折扣因子。因此有

對(duì)此，我們有以下結(jié)論

定理6.8.4設(shè)(X，

T)滿足正則性條件(6.5.9)式，則當(dāng)r有界時(shí)，

Vα

是(6.8.7)式的唯一有界解;當(dāng)r非負(fù)(或非正)時(shí)，

Vα

是(6.8.7)式的最小非負(fù)(或最大非正)解。

證明由條件(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)式的解。下設(shè)V是(6.8.7)式的另一個(gè)解，則由V=R+AV遞推可得

由于A的行和≤β，故由矩陣論的知識(shí)知道收斂于

當(dāng)

r有界時(shí)，

R

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

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

當(dāng)r≥0時(shí)有R≥0

。設(shè)V≥0

，則由(6.8.8)式知

故V

α

是(6.8.7)式的最小非負(fù)解。

當(dāng)r≤0

時(shí)，證明是類(lèi)似的。

在半馬氏報(bào)酬過(guò)程中，如果在各次狀態(tài)轉(zhuǎn)移時(shí)刻，我們有不同的決策可供選擇以影響過(guò)程未來(lái)的發(fā)展變化，就得到了半馬氏決策過(guò)程，這是研究隨機(jī)動(dòng)態(tài)系統(tǒng)最優(yōu)控制的主要工具之一，有興趣的讀者可參閱參考文獻(xiàn)[20]和[21]。

6.9廣義半馬氏過(guò)程簡(jiǎn)介

廣義半馬氏過(guò)程(GSMP:Generalizedsemi-Markovprocesses)是比半馬氏過(guò)程更廣的一類(lèi)隨機(jī)過(guò)程，它是德國(guó)學(xué)者M(jìn)atthes在60年代初提出來(lái)的，當(dāng)時(shí)取名為Bedienugsprozesse(德文)，意指服務(wù)動(dòng)態(tài)學(xué)，它可用來(lái)描述存儲(chǔ)論、可靠性理論、排隊(duì)系統(tǒng)、計(jì)算機(jī)/通信網(wǎng)絡(luò)等中的隨機(jī)模型。

6.9.1模型

考慮一隨機(jī)系統(tǒng)，它可用狀態(tài)—事件框架來(lái)描述，其狀態(tài)的變化僅是由于事件的發(fā)生引起的，而且事件的總數(shù)是可數(shù)的，于是狀態(tài)也是可數(shù)的。例如在排隊(duì)系統(tǒng)中，狀態(tài)表示隊(duì)長(zhǎng)，事件只有兩個(gè):到達(dá)一個(gè)顧客，服務(wù)完一個(gè)顧客。設(shè)S

為可數(shù)狀態(tài)集，

E為可數(shù)事件集。為與下面將要引入的數(shù)學(xué)狀態(tài)相區(qū)別，我們稱(chēng)s∈S為系統(tǒng)的物理狀態(tài)。對(duì)s∈S

，

E(s)?E為s處可發(fā)生的事件集，稱(chēng)之為s的可行事件集。

對(duì)e∈E，記ce為事件e的已持續(xù)時(shí)間(最后一次發(fā)生至今的時(shí)間)，稱(chēng)ce

為e

的時(shí)鐘讀數(shù)(clockreading)。對(duì)e∈E(s)，

rse≥0表示ce

隨時(shí)間增加的速度。

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

∞)，

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

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

:對(duì)e∈E，ce=-1當(dāng)且僅當(dāng)e∈E(s)}。于是c∈C(s)表示在狀態(tài)s處所有事件的時(shí)鐘讀數(shù)所組成的向量，

ck=-1當(dāng)且僅當(dāng)e在s

處不可行。

我們用下述例題來(lái)說(shuō)明上述各元的含義。

例6.9.1考慮有M個(gè)服務(wù)中心的開(kāi)環(huán)排隊(duì)網(wǎng)絡(luò)，各中心均有一個(gè)服務(wù)臺(tái)，顧客類(lèi)型只有一種。記N+={0，

1，

2，…}，則網(wǎng)絡(luò)的狀態(tài)集S=(N+

)M:對(duì)s=(s1

，

s2

，…，

sM)∈S

，si為中心

i的隊(duì)長(zhǎng);事件集E={(i，

1)，(i，

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

1)表示有一個(gè)顧客從外部到達(dá)中心i;(i，

2)表示有一個(gè)顧客因服務(wù)結(jié)束而離開(kāi)中心i。顯然E(s)={(i，

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

2):si

≥1，

1≤i≤M}。對(duì)e=(i，

1)，

ce

表示中心

i的最后一次外部到達(dá)至今的時(shí)間;對(duì)e=(i，

2)，

ce表示中心

i處接受服務(wù)之顧客的已服務(wù)時(shí)間。對(duì)e=(i，

2)，

rse=1表示中心

i的服務(wù)速率恒定，而rse=ri

si

則表示中心

i處的服務(wù)速率與隊(duì)長(zhǎng)si

成正比。

系統(tǒng)的動(dòng)態(tài)變化如下。由于系統(tǒng)的軌跡是分段為常數(shù)的，于是可假定其(物理)狀態(tài)過(guò)程{S(t);t≥0}為

式中，

0=T0<T1

<…滿足{Sn

}為取值于S

中的隨機(jī)序列;χ為示性函數(shù);Tn表示系統(tǒng)的第n

次狀態(tài)轉(zhuǎn)移時(shí)刻;Sn

為T(mén)n

時(shí)的狀態(tài)。于是

是S

(t

)的第n次和第n+1次狀態(tài)轉(zhuǎn)移的間隔時(shí)間。記Cn為T(mén)n時(shí)的時(shí)鐘讀數(shù)向量，

表示在Tn

時(shí)的數(shù)學(xué)狀態(tài)。

現(xiàn)在設(shè)對(duì)某n≥0，

Xn=(s，

δ，

c)。由于系統(tǒng)由事件驅(qū)動(dòng)，所以Tn

后的首次狀態(tài)轉(zhuǎn)移將由首先發(fā)生的事件所確定，記此事件為en+1，并稱(chēng)為觸發(fā)事件(triggerevent)。為確定en

+1，設(shè)有分布函數(shù)族{Fe(·):e∈E}滿足Fe

(0)=0。Fe

(·)為事件e

的持續(xù)時(shí)間分布函數(shù)。

由于Cn=c表示Tn

時(shí)各事件的已持續(xù)時(shí)間，

e∈E(

s)的剩余持續(xù)時(shí)間(記為Yne)的分布函數(shù)為

為使所定義的各式有意義，令rse=0時(shí)Yne/rse=+∞;且假定對(duì)任一s

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

>0，亦即

同時(shí)為使en+1唯一，假定對(duì)任一s∈S，至多有一個(gè)e∈E(s)使Fe

(t)不連續(xù)。

顯然，

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

+1由狀態(tài)轉(zhuǎn)移概率族

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

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

en+1=e}。再記

分別表示在條件Sn=s，en+1=e，

Sn+1=s'下s'

處可行事件集E(s')中的舊事件集和新事件集。自然，我們假定狀態(tài)轉(zhuǎn)移不改變舊事件的時(shí)鐘讀數(shù)，于是

這樣，在引入了{(lán)Fe(·)}和p

之后，

Xn+1就由Xn

確定。容易看出，數(shù)學(xué)狀態(tài)過(guò)程X∶={Xn

，

n≥0}是時(shí)齊馬氏鏈，其狀態(tài)空間

記B

(H

)為H

中的σ

域。X

的轉(zhuǎn)移概率為:對(duì)x=(s，

δ，

c)∈H

及

其中

而Fe，

a(t)=Fe(at)。

定義6.9.1設(shè)S

為可數(shù)狀態(tài)集，

E(s

)為狀態(tài)s

的可行事件集，

p={p(s‘|s，

e):s，s'∈S，

e∈E(s)}為狀態(tài)轉(zhuǎn)移概率族，

r={rse:s∈S，

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

F={Fe(·):e∈E}為事件的持續(xù)時(shí)間表分布函數(shù)族，記Σ=(S，(E(s)，

s∈S)，

p)。

(1)稱(chēng)(Σ，

r)為具有速度的廣義半馬氏概型(GSMS:generalizedsemi-Markovscheme);當(dāng)rse

≡1時(shí)，簡(jiǎn)記(Σ，

r)為Σ

，并稱(chēng)Σ為GSMS。

(2)稱(chēng)(6.9.1)式中的S(t)為(Σ，

r)上由F

確定的廣義半馬氏過(guò)程(GSMP)，稱(chēng)X

={Xn，

n≥0}為(Σ，

r)上由F

確定的擴(kuò)充(supplemented)GSMP。

上面所定義的是時(shí)齊GSMP，對(duì)非時(shí)齊GSMP可用類(lèi)似方法定義。記Xn∶=(X0，

X1

，…，

Xn

)，如果轉(zhuǎn)移概率族p={p(s'|xn，

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

，e):xn∈Hn+1，e∈E}均與xn有關(guān)，則得到的過(guò)程X

是非時(shí)齊馬氏鏈，其狀態(tài)轉(zhuǎn)移概率P{Sn+1=s'|Xn=xn，

en+1=e}與(6.9.5)式中類(lèi)似。稱(chēng)相應(yīng)的S(t)為非時(shí)齊GSMP。

例6.9.1(續(xù))設(shè)pij為離開(kāi)中心i的顧客到達(dá)中心

j的概率，為離開(kāi)網(wǎng)絡(luò)的概率。則P∶=(pij)為次隨機(jī)矩陣。此時(shí)的排隊(duì)網(wǎng)絡(luò)可用一時(shí)齊GSMP表示。若記ei

為第i

個(gè)單位向量，則

若進(jìn)一步假定中心i的外部到達(dá)是間隔時(shí)間分布為Fi

(·)的更新過(guò)程，中心i的服務(wù)時(shí)間分布為Gi

(·)，服務(wù)速率是r

i

si

，先到先服務(wù)規(guī)則，則rs

，(i，

1)=1，

rs

，(i，

2)=risi

，

F(i，

1)(·)=Fi(·)，

F(i，

2)(·)=Gi

(·)。

下面我們考慮GSMP的幾種特例。

(1)之所以將S(t)稱(chēng)為廣義半馬氏過(guò)程，是因?yàn)樗劝腭R氏過(guò)程的含義更廣。

如果在GSMP中假定

則可證對(duì)n≥1，

x=(s，

δ，

c)有

其中

Ye

有分布Fe

，從而S(t)是半馬氏過(guò)程。

則

所以{Sn

}是馬氏鏈，{S(t)}是馬氏過(guò)程，其轉(zhuǎn)移速率矩陣Q

為

對(duì)以上的詳細(xì)推導(dǎo)并不難，讀者可自己給出。

實(shí)際上，半馬氏過(guò)程和馬氏鏈在GSMP中所起的作用與線性系統(tǒng)在連續(xù)變量動(dòng)態(tài)系統(tǒng)(CVDS:continuousvariabledynamicsystems)中所起的作用是類(lèi)似的，這一點(diǎn)從表6.1中不難看出。

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

(2)在GSMP中，

S(t)是物理狀態(tài)軌跡，但直接研究S(t)一般并不容易，

GSMP引入較易研究的數(shù)學(xué)狀態(tài)過(guò)程X，通過(guò)對(duì)X的研究來(lái)得到關(guān)于S的有關(guān)結(jié)果，而S=h1

(X)為X的第一個(gè)分量。這種思路與CVDS中是類(lèi)似的。

(3)關(guān)于特例的類(lèi)比是因?yàn)榫€性系統(tǒng)和半馬氏過(guò)程、馬氏鏈分別是CVDS、GSMP中研究得較為透徹的兩類(lèi)特例，同時(shí)從狀態(tài)方程③、④的形式上也可見(jiàn)一斑。

6.9.2平穩(wěn)分布

擴(kuò)充GSMP的馬氏性可用來(lái)研究系統(tǒng)的長(zhǎng)期運(yùn)行行為。我們有如下兩個(gè)定理。

定理6.9.1設(shè)S上的實(shí)值函數(shù)f滿足條件

其中μ1、μ2

、μ3均為有限隨機(jī)變量，且μ2>0，

a.s.，則

(2)對(duì)一切