動機
到達計數把每個事件當作一單位,但數據傳輸系統常需要另一數量:封包在隨機時刻到達,每包又有隨機位元組數。事件數與累積負載是不同過程,兩者期望均可能隨時間線性增加,方差計算卻不同,因為負載項的數目本身也隨機。
另一個分別在時鐘。指數等待產生泊松(Poisson)過程,但重複的獨立週期未必服從指數分佈。更新過程保留獨立週期結構,同時容許一般等待分佈。它把伯努利(Bernoulli)、泊松模型連接到再生論證,也清楚指出哪些結論依賴無記憶性。
以下使用獨立可積變量的強大數定律、基本條件化及非負積分。
定義
令 W1,W2,… 獨立同分佈、嚴格為正,且幾乎必然有限。設 S0=0、Sn=W1+⋯+Wn,以及
NR(t)=max{n≥0:Sn≤t}.對獨立同分佈的對 (Wn,Yn),完成週期報酬為 C(t)=n=1∑NR(t)Yn。同一對內可相依,例如長週期賺得更多報酬;不同對則須獨立。
更新時刻之和幾乎必然發散。選 η>0 使 Pr(W1≥η)>0;這些足夠長的等待,由獨立指示變量的強大數定律可知會出現無限次。因此有限時刻只有有限次更新。若 m=EW1<∞,由嚴格正性亦知 m>0。報酬可有正負,但其絕對期望須有限。
設 N(t) 為速率 λ>0 的齊次泊松過程。給每個事件配上獨立同分佈標記 Y1,Y2,…,並獨立於整個到達過程。有限類型標記的概率為總和一的 p1,…,pd,各類計數為 Nr(t)。數值標記產生複合過程
Z(t)=k=1∑N(t)Yk,空和為零。數值標記可以是非負負載,也可以是帶正負的變化;後者的 Z 未必單調不減。
事件標記不是新事件時刻。零標記不會令 Z 出現可見跳躍,即使到達計數確有跳升。因此只數累積過程的非零跳躍,一般不能還原原始到達速率。
定理/命題
若 m=EW1<∞、E∣Y1∣<∞,則幾乎必然有
tNR(t)⟶m1,tC(t)⟶mEY1(t→∞).這些是路徑極限,本身不斷言相應期望收斂,也不描述尚未完成週期內已賺得的報酬。
獨立有限類型標記下,N1,…,Nd 是速率 λpr 的獨立泊松過程。數值標記的 Z 有平穩獨立增量,且對每個實數 u,
EeiuZ(t)=exp{λt(EeiuY1−1)}.若 E∣Y1∣<∞,則 EZ(t)=λtEY1;若再有 EY12<∞,則 Var(Z(t))=λtEY12。
注意方差公式用標記的二階矩,而非標記方差。事件數的隨機性補上均值平方項。特徵函數總是存在,因複指數的絕對值為一;矩母函數則另需指數可積性假設。
證明思路
反轉時鐘及計算報酬
強大數定律給出 Sn/n→m。由 NR(t)→∞ 及 SNR(t)≤t<SNR(t)+1,除以相應索引並夾逼,得 NR(t)/t→1/m。早期可能有 NR(t)=0,不影響極限。報酬可寫為
tC(t)=NR(t)1k=1∑NR(t)YktNR(t).整個報酬序列的強大數定律在概率一的事件上成立,因此沿趨於無限的隨機索引亦成立,毋須假設 NR(t) 與報酬獨立。這正是容許同一週期的長度與報酬相依的原因。
證明透視
隨機指標為何不需要獨立性
證明有兩步。夾逼式 SNR(t)≤t<SNR(t)+1 把以 n 為指標的更新時刻強大數定律,轉成以連續時間為指標的敘述:當 NR(t)≥1,
NR(t)SNR(t)≤NR(t)t<NR(t)+1SNR(t)+1⋅NR(t)NR(t)+1,兩端都趨於 m。這需要 NR(t)→∞,而它來自每個 Sn 幾乎必然有限。第二步是逐路徑的:報酬平均在整個序列的同一個概率一事件上收斂,故沿任何趨於無限的指標,不論是否隨機,都會收斂。證明從未使用 NR(t) 與報酬之間的獨立性,所以週期報酬可以依賴本週期的長度。假設 m<∞ 只用於確定極限值;若 m=∞,同一夾逼給出 NR(t)/t→0。
另有有限時間方程。若等待分佈為 F,M(t)=ENR(t),對首次更新條件化得
M(t)=F(t)+∫(0,t]M(t−s)dF(s).
積分依等待分佈進行,故包含原子與確定性等待。為證期望有限,沿用 η,令 p=Pr(W1≥η)>0。當出現 ⌊t/η⌋+1 次這樣的等待時,累積時間已超過 t。獲得這麼多次成功所需試驗數的期望為 (⌊t/η⌋+1)/p,並為 NR(t)+1 提供上界。故 M(t) 有限,首次條件化合法。更新方程並未斷言其解隨時間線性變化。
分開各類計數
在長 t 的時段內給定 N(t)=n,類型計數服從多項分佈。對總和為 n 的非負整數 kr,乘上泊松概率得到
Pr(N1(t)=k1,…,Nd(t)=kd)=r=1∏de−λprtkr!(λprt)kr.這分解成獨立泊松分佈。對多個不相交時段,原增量獨立,而各段所屬不同事件的標記亦獨立。同時使用同一分解,便由有限維分佈證明整個類型計數過程互相獨立;這比只研究單一時刻提供更多資訊。
隨機和及其波動
給定 N(t)=n,標記獨立給出 EeiuZ(t)=(EeiuY1)n。對泊松級數取平均即得特徵函數公式。對不相交時段使用同樣條件化,也證明平穩獨立增量,標記有負值時亦然。若 b=EY1、s2=Var(Y1) 有限,條件均值及方差為 nb、ns2。全期望及全方差給出
Var(Z(t))=E[N(t)]s2+Var(N(t))b2=λt(s2+b2)=λtEY12.全方差等式可把 Z−EZ 分解為 (Z−E[Z∣N])+(E[Z∣N]−EZ),交叉項的條件期望為零而證。只假設一階絕對矩時,非負求和給出 Ek=1∑N(t)∣Yk∣=λtE∣Y1∣,先證明絕對可積,再求均值。
概念視角分析
每個事件與每單位時間的平均
平均標記是每事件報酬,到達速率是每時間事件數,相乘才是長期報酬速率。複合泊松方差有兩個隨機來源:報酬大小及事件次數。量綱可檢查計算,條件化才提供證明。
整數負載的有限時間分佈計算
非負整數標記的概率母函數不只給矩。寫 pj=Pr(Y=j)、G(z)=j≥0∑pjzj、fk(t)=Pr(Z(t)=k),對計數條件化得
Ft(z):=k≥0∑fk(t)zk=exp{λt[G(z)−1]},f0(t)=eλt(p0−1).
0≤z<1 時級數絕對收斂。在內部微分,並在 Ft′(z)=λtG′(z)Ft(z) 比較係數,得到
fk(t)=kλtj=1∑kjpjfk−j(t),k≥1.
右邊只有較早概率,故可依次精確計算有限多個負載概率,毋須正態近似。單位圓盤內解析冪級數可微分,甚至標記均值無限時亦可比較係數,因每個係數只涉及有限項。初始概率一般不是 e−λt,因零標記不改變總負載。
若每個標記恆為二,p2=1,遞推令所有奇數負載概率為零,並給 f2n(t)=e−λt(λt)n/n!,符合 Z(t)=2N(t)。可見累積負載未必在所有非負整數上服從泊松分佈;事件數泊松,不代表把跳幅乘二後的總量仍有同一分佈形式。
另有兩時刻計算。0≤s≤t 且標記平方可積時,寫 Z(t)=Z(s)+[Z(t)−Z(s)]。括號增量獨立於 Z(s),故
Cov(Z(s),Z(t))=Var(Z(s))=λsEY2.
總量一般相依,即使不相交增量獨立。這與普通泊松計數的分別相同,只是如今包含隨機跳幅。
零或一標記是有用的模型檢查:非零事件形成稀疏化泊松過程,因此累積量確實是較低速率的泊松過程。若有正概率標記大於一,便引入批量跳躍,一般改變分佈。只顯示總負載的數據表,沒有標記規律便不能識別封包次數。選似然或解讀表面到達速率以前,事件時鐘及觀察規則兩者都須交代。
例題詳解
封包以每秒兩次到達,各包獨立地以概率 3/4 帶一負載單位,以概率 1/4 帶三單位。則 EY=3/2、EY2=3,在 t 秒後總負載均值為 3t、方差為 6t。若用 λtVar(Y)=2t(3−9/4)=3t/2,便遺漏事件數波動。一單位與三單位封包計數,分別是速率 3/2、1/2 的獨立泊松過程。
令每個 Wk=2、Yk=5 均確定。則 NR(t)=⌊t/2⌋、C(t)=5⌊t/2⌋,長期速率為 1/2、5/2,符合定理。但它不是泊松過程:0.2 至 0.7 之間不可能到達,包含時刻二的長 0.5 時段卻有一次。增量不平穩。與速率 1/2 泊松過程有相同平均等待,並不令時鐘等價。
只用一枚獨立公平硬幣決定所有到達的顏色:全部紅或全部藍。固定時刻令 m=λt,則 R+B=N(t)、RB=0,且 ER=EB=m/2,所以 t>0 時 Cov(R,B)=−m2/4<0。各色計數有共同硬幣產生的原子,兩者並不獨立。每次到達各自的紅色概率都是 1/2,但相同標記邊際並不保證事件間獨立標記。
常見錯誤
反例模式
跨週期共用的報酬破壞報酬定律
聲稱:同分佈且均值有限的報酬總給出長期報酬率 EY1/m,所以週期之間的獨立性只是技術細節。取每個 Wk=1,用一枚公平硬幣選出 Y∈{0,2},並令所有 Yk=Y。每個 Yk 的均值都是一,所以該聲稱預測報酬率為一。但 C(t)=Y⌊t⌋,故 C(t)/t→Y,它各以一半概率等於 0 或 2,永不等於一。平均值不收斂到均值,因為所有報酬共用同一個隨機來源。修正就是定理的假設:各對 (Wn,Yn) 在週期之間必須獨立;相依只容許出現在同一對之內。
普通更新過程在零時刻開始一次全新等待;在隨機選的較後時刻觀察,一般得到不同的剩餘壽命分佈。確定性長度二的等待,其餘下時間取決於觀察在當前週期的位置。指數無記憶性是特殊性質,並非相鄰完整等待獨立的結果。本節不宣稱一般平衡剩餘壽命定理。
報酬定律需要可積性。到達速率有限不會令非負無限均值負載變得可積:固定正時間恰有一次到達的概率已為正,足以令總負載期望無限。
路徑極限如 C(t)/t→EY1/m,本身並不給出 EC(t)/t→EY1/m。交換極限與期望需要控制界、一致可積或另一條更新定理。
總結
更新週期把事件速率與特殊指數時鐘分開。反轉強大數定律得到事件速率,完成週期報酬給出每時間報酬。泊松獨立標記分出獨立類型過程;複合和保留泊松時刻但加入隨機跳幅,方差亦包含事件數不確定性。
練習
快速檢查
(更新等待獨立,各以相同概率取一或三;每個完成週期賺其長度平方。求長期事件及報酬速率。)
解答 · 答案
平均等待二,平均報酬 (1+9)/2=5,即使同一對內報酬與等待相依也可用定理。速率為每時間 1/2 個事件及 5/2 報酬單位。
快速檢查
(速率三的泊松過程,獨立標記以概率 1/3 取零、2/3 取二。求 Z(t) 均值、方差及可見跳躍速率。)
方差公式用 EY2,不是 Var(Y)。
解答
EY=4/3、EY2=8/3,故均值 4t、方差 8t。只有非零標記可見,跳躍速率為 3(2/3)=2,大小恆為二;零標記仍是原到達。
快速檢查
(速率 λ 泊松過程獨立標記為三類,概率 1/2,1/3,1/6。求時刻 t 計數為 (1,0,2) 的聯合概率。)
解答 · 答案
類型過程獨立給出 e−λt(λt/2)(λt/6)2/2!=e−λt(λt)3/144。第二類零計數提供指數因子,但無正冪項。
快速檢查
(等待恆為二,驗證 M(t)=⌊t/2⌋ 的更新方程,包括 0≤t<2。)
解答
等待分佈在二有單位質量。t<2 時 F(t) 與積分均為零;t≥2 時方程成為 M(t)=1+M(t−2),正是向下取整恆等式。積分範圍包含右端點,故包括該原子。