為甚麼使用有時甚麼也不做的時鐘?
生成矩陣告訴我們鏈離開各狀態有多快;轉移矩陣告訴我們經過指定時間後它在哪裏。這是兩個不同問題。只知道下一次跳躍的目的地,並沒有計入觀察前完全沒有跳躍、已經跳了數次,或離開後又返回原狀態的可能性。
前面的生成矩陣筆記已介紹均勻化。本篇把它展開為精確的構造,以及帶有餘項保證的實際計算。一個共同時鐘在所有狀態都會響;部分鐘響只是保留原狀態。這些看似多餘的操作,把不同的停留速率換成一個獨立泊松(Poisson)計數。給定該計數後,問題就變成普通隨機矩陣的冪次。
本篇一律考慮有限狀態空間。因此所有離開速率有有限共同上界,矩陣運算都是有限維的,構造的路徑也存在於每個有限時刻。一般無界速率的存在性,以及嵌入鏈佔用問題,留在前面的筆記處理。
有限生成矩陣與獨立構造材料
設 S={1,…,d},其中 d≥1。保守生成矩陣是滿足下列條件的實矩陣:
qij≥0(i=j),qi:=j=i∑qij,qii=−qi.
因此 Q1=0,其中 1 是全為一的列向量。本篇以行向量表示概率分佈。選取 λ>0 且 λ≥imaxqi,定義
K=I+Q/λ,Kii=1−qi/λ,Kij=qij/λ(i=j).
K 的每個元素非負,每行總和是一。Q 的非對角元素具有「每單位時間」的量綱;K 的元素則是概率。
若取 λ<imaxqi,對角元素 1−qi/λ 便是負數,K 不是轉移矩陣,無法用來作這個概率構造。代數恆等式 etQ=e−λteλtK 仍然成立,但各項失去概率意義;泊松尾項保證之後的反例說明其後果。
取轉移矩陣為 K 的離散馬爾可夫(Markov)鏈 Y0,Y1,…,以及速率為 λ、與整條離散鏈獨立的泊松過程 N(t)。初始分佈為 α 時,令 Y0 服從 α 並與時鐘獨立;Y 每次轉移都使用新的獨立隨機選擇。設
X(t)=YN(t).
獨立性不可省略。一個隨機下標只有泊松邊際分佈並不足夠:若下標依賴 Y 未來的轉移,給定下標就可能改變鏈的分佈。我們先建立互相獨立的材料,再將它們組合。
零速率情況很直接。若希望取 λ=0,條件 λ≥imaxqi 迫使 Q=0。直接定義 X(t)=X(0) 及 P(t)=I 即可,既不用除以零,也不用替 Q/0 定義意義。對同一零生成矩陣,也可以任取正的 λ,此時 K=I,所有鐘響都是虛擬更新。
從虛擬事件到真正停留時間
設 X(0)=i 且 qi>0,並令 Hi=inf{t≥0:X(t)=i} 為首次真正離開的時刻。真正離開前,每次鐘響以概率 1−qi/λ 保留狀態 i。給定 N(t)=n,直到時間 t 仍未離開的概率為 (1−qi/λ)n。取平均得到
iPr(Hi>t)=n=0∑∞e−λtn!(λt)n(1−qi/λ)n=e−qit.
真正停留時間是速率 qi 的指數變量,兩次鐘響之間的等待則是速率 λ 的指數變量。兩者不一定是同一段隨機時間,因為第一次鐘響可能只是虛擬更新。
對不同狀態 j,把離開前可能出現的虛擬事件次數相加,得到
iPr(下個不同狀態=j)=n=0∑∞(1−qi/λ)nλqij=qiqij.
目的地也與離開時間獨立。不能只從兩個邊際分佈推斷這一點。令 G 是首次成功離開的鐘響編號,則 G=n 且目的地為 j 的聯合概率是
(1−qi/λ)n−1λqij=Pr(G=n)qiqij,n≥1.
因此目的地與 G 獨立,也與獨立的時鐘等待時間獨立;真正停留時間是前 G 段時鐘等待的總和。離開時,新的轉移選擇及新的指數時鐘等待使論證重新開始。因此,給定真正到訪的狀態序列,各次停留時間具有通常指數構造所要求的條件獨立性。若 qi=0,整行沒有向外速率,Kii=1,狀態 i 就是吸收狀態。
泊松過程在任意有界區間內幾乎必然只有有限次事件,真正跳躍次數也因此有限。這直接證明非爆炸性。它沒有替離開速率無界的可數生成矩陣證明任何結論;那種矩陣可能根本沒有有限的共同 λ。
轉移分佈與半群
對上述獨立構造及 λ>0,
P(t)=e−λtn=0∑∞n!(λt)nKn=etQ,t≥0.這些矩陣都是隨機矩陣,滿足 P(0)=I、P(s+t)=P(s)P(t),以及
P′(t)=P(t)Q=QP(t).對概率行向量 π,下列三條件等價:πQ=0、πK=π,以及對每個 t≥0 都有 πP(t)=π。若 Q=0,所有概率分佈都平穩,包括直接使用零時鐘的構造。
給定 N(t)=n,獨立性使 Yn 的分佈保持不變,因此從 Y0 出發的轉移矩陣是 Kn。這證明泊松混合公式。每項非負,每行總和等於相應泊松權重;整個級數的行總和是一。
構造具有馬爾可夫性:時間 s 之後,時鐘有獨立增量,尚未使用的轉移選擇也是新的。令 Gs 包含截至 s 的時鐘歷史及 Y0,…,YN(s)。給定這個較大歷史,未來轉移只透過 X(s) 依賴過去,所以 E[f(X(s+t))∣Gs]=(P(t)f)(X(s))。自然歷史 FsX=σ(X(r):0≤r≤s) 包含於 Gs。條件期望的塔式性質因此給出以 FsX 條件化的同一公式,這才是 X 本身所需的馬爾可夫性。
半群恆等式還有一個有啟發性的直接證明。將兩個級數相乘,按 m+n=r 分組,再用二項式定理:
P(s)P(t)=e−λ(s+t)r=0∑∞λrKrm=0∑rm!(r−m)!smtr−m=e−λ(s+t)r=0∑∞r![λ(s+t)]rKr=P(s+t).非負元素容許重新分組;在任何有限矩陣範數下也有絕對收斂。由 Q=λ(K−I),且 K 與 I 可交換,收斂的矩陣指數級數給出 etQ=e−λteλtK。這證明第二個公式,並容許在有界時間區間逐項微分。特別地,P′(0)=Q。
最後,πQ=0 等價於 πK=π。後者推出每個 n 都有 πKn=π,所以混合分佈保留 π。反過來,將 πP(t)=π 在零點微分,便得 πQ=0。有限維性保證這個微分合法。上述等價性完全不需要不可約假設。
證明透視
每個假設負責哪一步?
證明分四步,每步消耗不同的假設。
- 混合公式以 N(t)=n 條件化。這只因時鐘與整條鏈 Y 獨立才合法;條件 λ≥imaxqi 使每個 Kn 都是轉移矩陣,因此每項都是行總和等於相應泊松權重的非負矩陣。
- 馬爾可夫性先對包含時鐘及離散路徑的較大歷史 Gs 證明。微妙之處在塔式性質:右邊 (P(t)f)(X(s)) 已對 FsX 可測,所以給定 Gs 成立的公式,給定較小歷史 FsX 亦成立。
- 半群律及 etQ=e−λteλtK 是矩陣代數;非負性容許重新分組,K 與 I 可交換則容許拆開指數。
- 有限維性容許在零點微分,把 πP(t)=π 變成 πQ=0。
論證得以收結,是因為構造已定義了一個概率過程;對無界無限狀態模型,只寫矩陣冪次並不能提供同樣的構造。
任選時鐘速率為何不改變過程?
不同的容許正值 λ 給出不同的 K,也產生不同數目的虛擬事件,但它們都給出同一個 etQ。它們亦給出前面已推導的同一組真正指數停留時間及目的地分佈。增大 λ 只增加計算工作,不會增加模型本身的轉移。
固定時刻的轉移核亦決定長期行為;在有限狀態下答案是完整的。
每個有限保守生成矩陣都有平穩概率。若 Q 不可約,則對每個 u>0,P(u) 的所有元素為正,平穩概率 π 唯一,並且對每個初始概率 α 都有 αP(t)→π。
存在性不需要不可約。一個有限維證明從平均 T−1∫0TαP(s)ds 出發。概率單純形緊緻,所以存在收斂子序列。將平均乘以 P(u),只是平移積分區間;其 ℓ1 差不超過 2u/T。因此每個子序列極限對任意 u≥0 都平穩。
要證唯一性,現在假設不可約並固定 u>0。每對 i=j 之間都有一條有限的正速率路徑,故 K 的某個冪在 (i,j) 位置為正,而它在時間 u 的泊松權重也為正。對 i=j,零次冪 K0=I 已經貢獻正對角元素。因此 P(u) 的所有元素為正。若 η=i,jminPij(u) 及 δ=dη,則 0<δ≤1。當 δ<1,可寫 P(u)=δ1v+(1−δ)B,其中 v 是均勻分佈,B 是隨機矩陣。這把概率分佈之差的 ℓ1 範數收縮至不超過原來的 1−δ 倍。若 δ=1,所有行已等於 v。兩個平穩分佈因此必須相同。相同收縮論證證明在 u 的整數倍時刻收斂;不足 u 的剩餘時間不會增加與平穩分佈的距離。即使真正跳躍交替發生,固定時刻概率仍可以收斂。
證明透視
存在性與唯一性的兩個不同理由
存在性與唯一性依靠不同的性質。存在性只用到有限性:時間平均位於緊緻單純形內,而平移窗口的估計 2u/T 使每個子序列極限對每個 P(u) 都不變。唯一性需要不可約,它透過 P(u) 每個元素皆正而起作用;對角元素自然為正,因為有零事件項 e−λuI。關鍵一步是分解 P(u)=δ1v+(1−δ)B。對分佈 α,β 有 (α−β)1=0,所以共同部分消失,每經過長度 u 的一步,差只剩下 1−δ 倍。
完整的二狀態計算
本例使用狀態 0,1,速率為 q01=1 及 q10=3。取 λ=4,則
Q=(−131−3),K=(3/43/41/41/4)=:Π.Π 每行都是 π=(3/4,1/4),所以 Π2=Π。但零次冪仍是 I,代表沒有鐘響。將其餘權重相加,得到完整轉移矩陣:
P(t)=e−4tI+(1−e−4t)Π=(3/4+e−4t/43(1−e−4t)/4(1−e−4t)/41/4+3e−4t/4).在 t=(log2)/4,矩陣是 (7/83/81/85/8)。在 t=1/2,第一行約為 (0.783833821,0.216166179)。矩陣從 I 開始,每行總和是一,在零點的導數是 Q,各行則趨向 π。這些是不同方面的核對。
從零開始,到時間 t 完全沒有真正離開的概率是 e−t;完全沒有鐘響的概率是 e−4t。兩者都不是 P00(t),因為終點是零也可能發生於離開再返回之後。真正嵌入鏈的矩陣為 R=(0110),平穩到訪分佈是 (1/2,1/2);均勻化鏈 K 的不變分佈卻是 (3/4,1/4)。典型到訪對兩個狀態給予相同權重;典型時刻則較常落在停留較久的零狀態。這個有限例子分清 R、K 與 P(t),毋須重做一般佔用轉換定理。
任何容許的時鐘速率都可用,較快的時鐘只是增加虛擬事件。
對同一生成矩陣取 λ=8,則
K=I+Q/8=(7/83/81/85/8)=Π+21(I−Π);由 Π2=Π 及 Π(I−Π)=0 得 Kn=Π+2−n(I−Π)。泊松混合給出係數
e−8tn∑(8t)n2−n/n!=e−8te4t=e−4t,所以仍有 P(t)=Π+e−4t(I−Π)。平穩時時鐘以速率 8 響,真正跳躍的速率卻是 3/2,只有 3/16 的鐘響改變狀態;λ=4 時這比例是 3/8。
概念視角結構
三種不同計數
泊松計數記錄潛在更新,真正跳躍計數記錄實際狀態改變,固定時刻觀察則只記錄當前狀態。在二狀態例子中,第一種計數的均值是 4t,與初始分佈無關。在平穩狀態下,第二種計數的均值是 [(3/4)1+(1/4)3]t=3t/2。第三種觀察在每個時刻的分佈都是 (3/4,1/4)。把三者都當成同一種「轉移」,就會丟失均勻化本來要保留的時鐘資訊。
帶嚴格餘項的有限計算
對 x=λt 及非負整數 m,定義
wn=e−xn!xn,Pm(t)=n=0∑mwnKn,sm=n=0∑mwn,εm=1−sm.
在 x=0 時約定 w0=1,便精確得到單位矩陣。對 x>0,省略的權重等於尾概率 εm=Pr(Poisson(x)>m)。Pm 每行總和是 sm 而非一。它是次隨機的下近似,並不是精確的隨機轉移矩陣。
逐元素有 0≤P(t)−Pm(t),且差矩陣每行總和為 εm。因此,對任意初始概率 α 及集合 A⊆S,
(αPm(t))(A)≤αPr(X(t)∈A)≤(αPm(t))(A)+εm.對任何滿足 ∣f(i)∣≤M 的實值觀察量,
∣αP(t)f−αPm(t)f∣≤Mεm.這是精確算術下的截斷界;浮點捨入誤差需要另外控制。
省略各項都是非負矩陣,行總和各為 wn。把它們相加就得到逐元素及行總和的結論。集合截取的省略質量介於零與全部質量之間。對觀察量,取絕對值後以 M 控制每個被省略的 f 值即可。
省略項的非負性,正是條件 λ≥imaxqi 發揮作用之處。
反例模式
慢時鐘破壞下界
聲稱:既然對每個 λ>0 都有 etQ=e−λtn∑(λt)nKn/n!,誤差保證對任何時鐘速率都成立。取例題的二狀態生成矩陣及 λ=2<q1=3,則 K=I+Q/2=(1/23/21/2−1/2) 有負元素,且 K2=I。在 t=(log2)/2,只保留零次項的截斷是 P0(t)=e−2tI=I/2,但 P11(t)=1/4+3e−4t/4=7/16<1/2。所以 P(t)−P0(t) 有負元素,P0 不是下界。條件 λ≥imaxqi 使每個 Kn 非負,證明用的正是這一點。
若 sm>0,也可以將結果正規化為 Pm/sm。對初始分佈 α,這是給定 N(t)≤m 的條件終點分佈;它一般不再是逐元素下界。把真實分佈寫成這個條件分佈與給定 N(t)>m 的條件分佈的混合,可證正規化答案與真實分佈的全變差距離不超過 εm。此處全變差定義為 Asup∣μ(A)−ν(A)∣。
若只計算一個初始分佈,不需要形成所有完整矩陣冪。從 v0=α 出發,更新 vn+1=vnK,並累加 n=0∑mwnvn。精確恆等式 w0=e−x 及 wn+1=wnx/(n+1) 對所有有限 x≥0 都成立;對大小適中的 x,這個向前遞推在數值上方便。若 x 很大,從零開始可能產生下溢;選用數值穩定的權重算法,是精確算術誤差保證之外的數值分析工作。
利用比值可以取得明確尾界。若 x<m+2,第一個省略權重之後的每個比值都不超過 x/(m+2),所以
εm≤1−x/(m+2)e−xxm+1/(m+1)!.
例題 3.6.6
(為 t=1/2 的二狀態分佈給出誤差保證)
取 λ=4、t=1/2,則 x=2。m=8 時條件 x<m+2 成立,且
ε8≤1−2/10e−229/9!=567e−2<0.000239.由於 n≥1 時 Kn=Π,零至一的近似概率是 (s8−e−2)/4≈0.216107,精確值是 (1−e−2)/4≈0.216166。實際誤差為 ε8/4≈0.0000594,一般保證則容許整個 ε8。有效的上界不必恰好等於誤差。
習題
練習 3.6.7
(對上述二狀態生成矩陣取 λ=3。求 K,驗證其不變分佈,並由其冪次恢復 P(t)。為甚麼 K 有負特徵值也沒有問題?)
核心
解答(3)
1寫出 K 並檢查不變性
K=I+Q/3=(2/311/30),直接相乘得 (3/4,1/4)K=(3/4,1/4)。
2把 K 拆成互補投影
K=Π−31(I−Π),Kn=Π+(−1/3)n(I−Π),n≥0. 依據: Π2=Π 且 Π(I−Π)=0。
3對泊松計數取平均
混合把第二個係數化成 e−3texp(−t)=e−4t,所以仍有 P(t)=Π+e−4t(I−Π)。隨機矩陣要求元素非負,而非特徵值非負;離散冪中的交替因子被隨機時鐘平均掉。
練習 3.6.8
(設 Q=(−2020) 且 λ=2。求 P(t)、所有平穩概率,以及從狀態零出發在 t=(log2)/2 的分佈。若所有速率為零,答案怎樣改變?)
基礎
解答(3)
1計算 K 的冪
K=(0011) 在 n≥1 時滿足 Kn=K,所以
P(t)=e−2tI+(1−e−2t)K=(e−2t01−e−2t1). 2求平穩分佈並代入時刻
πQ=0 迫使 π0=0,故 (0,1) 是唯一平穩分佈。在 t=(log2)/2,e−2t=1/2,從零出發的分佈是 (1/2,1/2),並不平穩。
3處理零生成矩陣
若 Q=0,兩個狀態都吸收,P(t)=I,所有概率分佈都平穩;可以直接使用零時鐘,或使用正時鐘及 K=I。
練習 3.6.9
(證明尾項比值界。對 x=2,求使該界保證 εm<10−3 的最小 m,並判斷把 Pm 換成 Pm/sm 後是否仍保留逐元素下界性質。)
核心
解答(3)
1與幾何級數比較
關鍵一步
省略的總和至多是 wm+1k≥0∑(x/(m+2))k,即所述上界。
依據: 對 n≥m+1,wn+1/wn=x/(n+1)≤x/(m+2)<1。
2代入 x=2
m=7 時上界為 e−2(28/8!)⋅79≈0.00110,仍太大;m=8 時為 e−2/567<0.000239。所以 m=8 是最小的保證選擇。
3檢驗正規化截斷
正規化不保留下界。在二狀態例子中,其零至零元素是 3/4+e−2/(4s8);因 s8<1,它大於真實值 3/4+e−2/4。條件混合論證仍保證全變差誤差界。
練習 3.6.10
(在二狀態例子中從零出發,求時間 t 前真正跳躍次數的期望,並與潛在更新次數的期望比較。解釋只計算零至一轉移為何得到不同答案。)
綜合
解答(3)
1對離開速率積分
真正跳躍次數的期望為 E0J(t)=∫0t[p0(s)⋅1+p1(s)⋅3]ds。
依據: 從狀態 i 開始、長度為 h 的區間中,恰有一次鐘響貢獻的真正跳躍期望為 qihe−4h,兩次或以上鐘響的貢獻至多 4h(1−e−4h)=O(h2);對 [0,t] 的分割求和再加細,便得速率積分。
2代入轉移分佈
由 p0(s)=3/4+e−4s/4,
E0J(t)=∫0t[3/2−e−4s/2]ds=23t−81−e−4t. 3比較其他計數
潛在更新的均值為 4t,包括被拒絕的自更新。只計零至一轉移的期望是 ∫0tp0(s)ds=43t+(1−e−4t)/16,因為它省略所有一至零跳躍。只要清楚說明所計事件,每種計數都有用途。