首次清空要回答甚麼問題?
一名顧客到來,服務員立即開始工作。在服務完成之前,新顧客仍可到來;他們接受服務時又可能有更多人到來。服務員要連續工作多久,系統才首次清空?單知道平均到達率不足以回答:服務時間的分佈和兩種時鐘的獨立性同樣重要。
本節把已有的泊松(Poisson)過程和生滅鏈連到首次到達問題。
模型與首次回到零
設到達構成速率 λ>0 的泊松過程;各次服務時間獨立,均服從速率 μ>0 的指數分佈,並且與到達過程獨立。系統只有一名服務員,等待空間無限,按先到先服務的次序處理;只要有顧客,服務員便不停工作。令 X(t) 為時刻 t 系統中的人數,包含正在接受服務的人。
由 X(0)=1 開始,定義繁忙期 B=inf{t≥0:X(t)=0};若永不清空,則取 B=∞。負載定義為 ρ=λ/μ。
指數分佈的無記憶性保證,只需知道當前人數,便足以決定下一事件的條件分佈。由狀態 n≥1 出發,到達率為 λ,離開率為 μ;在零狀態則只可能有到達。總跳躍率有界,所以跳躍構造不會爆炸。若服務時間不是指數分佈,已服務多久一般會影響剩餘時間,單記錄 X(t) 未必是馬爾可夫(Markov)過程。
對 s>0,定義 L(s)=E[e−sB;B<∞]。則
L(s)=2λλ+μ+s−(λ+μ+s)2−4λμ.而且
Pr(B<∞)=min(1,λμ),EB={(μ−λ)−1,∞,λ<μ,λ≥μ.這裏期望容許取無限大;若 B=∞ 有正概率,期望便是無限大。
設第一個事件的時間為 T。兩個獨立指數時鐘競爭,得到 T∼Exp(λ+μ);事件為離開的概率是 μ/(λ+μ),為到達的概率是 λ/(λ+μ),事件種類與 T 獨立。若第一事件是離開,繁忙期便結束;若是到達,人數增至二。由二到零必先由二到一,再由一到零。在正狀態的平移對稱性及首次到達時的強馬爾可夫性下,由二到零的時間與兩個獨立 B 的和具有相同的廣義分佈。這是分佈上的構造:即使第一個副本為無限大,仍可獨立抽取第二個副本;在該路徑上第二段實際上並未開始。以 e−s∞=0 約定,可得
L(s)=λ+μ+sμ+λ+μ+sλL(s)2.此二次方程有兩個正根。由於 s>0,二次式在零處為正,在一處為負,故較大根大於一。由 0≤L(s)≤1,只能取所寫的較小根。
令 s↓0,單調收斂定理給出 L(s)↑Pr(B<∞),於是得到上述最小值。若 λ<μ,對明確根式求導,得 −L′(0+)=(μ−λ)−1。再利用 (1−e−sB)/s 隨 s↓0 單調增加,便得到期望。若 λ=μ,右導數的負值為無限大,故雖然清空幾乎必然發生,平均時間仍無限。若 λ>μ,永不清空有正概率,期望亦為無限大。
證明透視
為甚麼不能只解二次方程?
證明分兩個階段,需要小心的是第二階段。
- 首步方程用了第一事件的競爭指數時鐘,並以正狀態的平移對稱性及強馬爾可夫性,把由二到零的時間寫成兩個獨立的 B 之和。約定 e−s∞=0 使方程在 B=∞ 有正概率時仍然成立。
- 在 s=0,二次方程的根為 1 及 μ/λ;到達較快時兩者都落在 [0,1],所以代數根不一定是真實事件的概率。關鍵一步是在 s>0 下處理:對 f(L)=λL2−(λ+μ+s)L+μ 有 f(0)=μ>0、f(1)=−s<0,故 [0,1] 內恰有一根。
- 之後令 s↓0,單調收斂確定 Pr(B<∞),並經 (1−e−sB)/s↑B 確定期望。
論證最後把三種情形分開:繁忙期無限、繁忙期有限但期望無限,以及繁忙期有限且期望有限。
若起初有有限的 n 人,人數必依次經過 n−1,n−2,…,0。同一首次到達論證給出變換 L(s)n 和最終清空概率 min(1,μ/λ)n。當 λ<μ 時,平均清空時間是 n/(μ−λ)。
數值例子
例題 3.7.3
(每小時一名到達,平均可服務兩名)
令 λ=1、μ=2,時間單位為小時。此時 ρ=1/2,繁忙期幾乎必然結束,平均長度為一小時。其變換為
L(s)=23+s−(3+s)2−8.對二次方程求兩次導數,得 EB2=4 平方小時及 Var(B)=3 平方小時。平均繁忙期是平均服務時間 1/2 小時的兩倍,因為服務期間的到達延長了工作。若開始時有三人,平均清空時間是三小時,而非一小時。
該例的二階矩來自一條一般公式;它顯示單看平均值可能掩蓋擁擠程度。
例題 3.7.4
(平均繁忙期相同,波動卻大不相同)
把 λL2−(λ+μ+s)L+μ=0 對 s 求導:L′(2λL−λ−μ−s)=L。當 λ<μ,代入 s=0 及 L(0)=1,得 L′(0)=−1/(μ−λ)。再求導一次並令 s=0,
L′′(0)(λ−μ)=2L′(0)−2λL′(0)2=−(μ−λ)22μ,EB2=L′′(0)=(μ−λ)32μ.λ=1,μ=2 時得 4,與上例一致。λ=9,μ=10 時平均繁忙期仍是 1/(10−9)=1 小時,但 EB2=20、Var(B)=19;一個繁忙期的平均服務人數由 2 升至 1/(1−0.9)=10。
在臨界負載下,同一變換仍決定行為,只是零處的導數為無限大。
例題 3.7.5
(臨界負載:必然清空但平均時間無限)
取 λ=μ=1。此時 (2+s)2−4=s2+4s,且
L(s)=22+s−s2+4s,L(0+)=1,所以繁忙期幾乎必然結束。至於期望,(1−e−sB)/s 隨 s↓0 遞增至 B,而
s1−L(s)=2ss2+4s−s=21+4/s−1→∞.由單調收斂,EB=∞。由於 ρ=1,下面的平穩定理亦表明不存在平穩概率。
一次服務的平均長度為 1/μ,該段時間的平均到達人數為 λ/μ。把這些到達者視為該次服務的子代,把他們服務時的到達者視為下一代,如此類推。對上一有限代作條件化,再利用獨立的服務時間與泊松增量,各代期望人數依次是 1,ρ,ρ2,…。當 ρ<1,由單調收斂,整個繁忙期平均服務人數為 1/(1−ρ)。例子中的答案為二;這是隨機總人數的期望,並不是說每次必定服務兩人。
概念視角結構
服務人數是一個家族的大小
改為計算顧客人數而非時間。在一次速率 μ 的指數服務期間,到達人數為 k 的概率是 λ+μμ(λ+μλ)k,各次服務之間互相獨立。因此一個繁忙期內服務的人數 N,正是以這個幾何後代分佈為規律的分枝過程的家族總人數;G(z)=EzN 滿足 G=zμ/(λ+μ−λG),即
λG2−(λ+μ)G+μz=0,與繁忙期方程同一形式的二次方程。平均後代數為 ρ,所以 ρ<1 同時支配家族大小與繁忙期。
平穩分佈是另一個問題
隊長鏈恰在 ρ<1 時有平穩概率分佈;此時分佈唯一,且
πn=(1−ρ)ρn,n≥0,EπX=1−ρρ.
當 ρ<1,所寫的概率總和為一,並滿足各相鄰狀態的流量平衡 πnλ=πn+1μ,包括零狀態在內的每個狀態均有流入等於流出。有界速率生成元的均勻化構造因此給出連續時間轉移半群下的不變性。
反過來,任何平穩概率在零狀態滿足 π0λ=π1μ。再用狀態一的平衡方程得到 π1λ=π2μ,歸納可知 πn=ρnπ0。若 π0=0,所有項均為零;否則只有 ρ<1 才可求和。正規化強制 π0=1−ρ,亦證明唯一性。對幾何級數求導即得均值。
平穩分佈下空系統所佔概率是 π0=1−ρ,繁忙概率是 ρ。它們是平穩分佈下的長期狀態概率,與「現在開始的一個繁忙期最終會否結束」不同。上例的平穩平均人數為一,而新繁忙期的平均長度是一小時;兩個數值相同只是巧合,單位亦不同。
公式 EB=1/(μ−λ) 只對 λ<μ 推導。λ>μ 時它是負數,不可能是平均值;λ=μ 時它沒有定義。兩種情形下廣義期望都是無限大。
臨界及超臨界兩種情形說明,若把最終清空當作穩定的定義,會出現甚麼問題。
反例模式
必然返回不代表平均返回時間有限
取 λ=μ=1,繁忙期以概率一結束,但平均長度無限,亦不存在平穩概率。若只因最終會清空就稱系統「穩定」,便會遺漏這兩點。取 λ=2,μ=1,由一人開始的清空概率只有 1/2,其餘路徑永遠不達零。兩種情形都由同一首次事件方程得到,但必須選對解。
練習與解答
快速檢查
(設 λ=3、μ=5,單位為每小時。求由兩人開始的清空概率及平均時間。)
解答 · 答案
因 3<5,清空幾乎必然發生。兩段向下首次到達時間各有平均 1/(5−3) 小時,所以總平均為一小時。兩個速率同乘正數不改變清空概率,但各段時間都除以該數。
快速檢查
(設 λ=4、μ=2。由三人開始,最終清空的概率是多少?由一人開始,無條件平均繁忙期是多少?)
每次向下一級成功的概率是 min(1,μ/λ)。
解答 · 答案
每次向下一級成功的概率為 μ/λ=1/2,三段依次成功的概率是 (1/2)3=1/8。由一人開始,永不清空的概率為 1/2,故廣義期望為無限大。1/(μ−λ)=−1/2 是負數,不可能是平均時間;此處不滿足次臨界公式的條件。
練習 3.7.7
(當 λ>μ,求 E[B∣B<∞]。)
核心
解答(3)
1以清空為條件的變換
此時 q=Pr(B<∞)=μ/λ<1,且 E[e−sB∣B<∞]=L(s)/q。
2在零處對根式求導
關鍵一步
L′(s)=(1−(λ+μ+s)/(λ+μ+s)2−4λμ)/(2λ),所以 −L′(0+)=μ/(λ(λ−μ))=q/(λ−μ)。
依據: λ>μ 時,s=0 處 (λ+μ)2−4λμ=λ−μ。
3除以清空概率
E[B∣B<∞]=1/(λ−μ)。這個條件平均有限,無條件廣義平均卻是無限大;無條件計算仍不能忽略永不清空的事件。
快速檢查
(在 λ=1,μ=2 的例子中,求平穩時至少兩人的概率,以及由一人開始的繁忙期平均服務人數。)
解答 · 答案
平穩幾何分佈的尾概率為 n≥2∑(1/2)(1/2)n=1/4。按上面的世代計數,繁忙期平均服務人數是 1/(1−1/2)=2。前者是平穩時刻的概率,後者是在整段隨機時間內的總人數。
本節範圍
上述分析使用獨立泊松到達、獨立指數服務時間及一名持續工作的服務員。一般服務時間、顧客等待時間分佈、有限容量系統和到達時刻的抽樣都需要進一步論證。