動機
離散鏈記錄每次更新後去哪裏,卻沒有記錄更新之間停留多久。兩個系統可以依次到訪完全相同的狀態,但在各狀態所佔的實際時間比例截然不同。連續時間馬爾可夫(Markov)鏈加入依賴狀態的停留時鐘;只要不同狀態的變化快慢有別,這一層便很重要。
例如機器在兩種模式間交替。如果離開第一種模式的速率是第二種的九倍,兩種模式的到訪次數相等,但時間佔用比例並不相等。混淆跳鏈與實際時間鏈,便會丟失引入時鐘所要表達的特徵。
本節研究有限或可數空間上的純跳躍鏈,再專門研究一步只移至相鄰狀態的生滅鏈。無限空間中,有限時間以前可能發生無限次跳躍,因此使用平穩方程之前必須交代非爆炸條件。
定義
定義 3.1.1
(速率、停留時間與嵌入跳鏈)
可數空間上的保守速率矩陣 滿足 時 ,以及
在 的狀態 ,先等待速率 的指數時間,再以概率 選擇下一個不同狀態 。給定所到訪的狀態序列後,各停留時間獨立。若 ,則 吸收。依次到訪的狀態形成嵌入跳鏈 。
具體構造可取互相獨立的單位速率指數變量 ,以及獨立的跳躍目的地抽樣。若第 跳後的狀態為 ,停留時間為 。令 , 是頭 段停留時間之和。在 以前,當 時令 ;遇到吸收狀態則停止跳躍。若從每個起點均幾乎必然有 ,稱過程非爆炸。在證明此性質以前,構造只給出爆炸前的最小過程。
概念視角算法
互相競爭的時鐘給出同一跳躍規則
不必先用一個停留時鐘再抽目的地;可以對每個 啟動一個速率 的獨立指數時鐘,並跳往最先響的時鐘。由於 ,第一次響鈴時間 幾乎必然被達到,而且
因此停留時間是速率 的指數變量,目的地的分佈是 ,兩者互相獨立,與定義完全一致。無記憶性使所有時鐘在跳躍後重新開始。在這個描述中,每個 是某一特定轉移的速率。
定義 3.1.2
(生成矩陣與生滅速率)
非爆炸鏈的轉移概率為 。速率矩陣描述短時間極限
在 上,生滅鏈具有 、(),且 ;其餘非對角速率為零。平穩概率分佈要求對所有 都有 。
對角元 是非正速率,吸收狀態時為零,並非轉移概率,其作用是平衡總流出速率。 各行和為零, 及 各行和為一。生滅模型的零狀態沒有負鄰居;在那裏加入死亡轉移會改變狀態空間,破壞原來的邊界條件。
定理/命題
定理 3.1.3
(有界速率、均勻化與平穩性)
假設 且 。則鏈非爆炸, 是隨機矩陣,而且
對概率行向量 , 等價於平穩性。有限空間上 ;若鏈不可約,便有唯一正平穩分佈,且 。
對生滅鏈,平穩方程可以明確求解。
定理 3.1.4
(有界速率下的生滅平衡)
假設所有 均有 ,所有 均有 ,且 。令
存在平穩概率分佈,恰好當 。此時唯一分佈為 ,滿足細緻平衡 。若 ,權重不能正規化;單憑此事不能分辨零常返與暫態。
有界速率是此處採用的充分條件,使存在性與平穩性均有完整理由。許多速率無界的實用模型也非爆炸,但須另行證明。在無限空間寫出形式上的 解,並不會自動證明非爆炸,也不會自動證明該解是所需過程的平穩分佈。
證明思路
證明
(泊松(Poisson)時鐘實現此鏈)
使用速率 的泊松(Poisson)時鐘;每次響起按 更新,容許選回原狀態。位於 時,每次響起真正離開的概率為 。截至時間 尚未真正離開的概率是
給定離開後,目的地 的概率為 ,故構造恰有指定的停留時間與目的地。任何有界時段內只有有限次泊松響鈴,因此真正跳躍不能爆炸。對響鈴次數條件化即得 公式。 的自轉移只是虛擬更新,並非原過程額外的真正跳躍。
若 ,則 ,均勻化和式每一項均保持 。反方向在零時刻微分平穩等式,得到 。速率有界時,生成矩陣在可和行向量上是有界算子,因此即使狀態可數,也可交換此極限。有限矩陣時同一級數等於 。有限不可約情形選 ,使各狀態都有正的虛擬自環。離散鏈 不可約且非週期,故收斂至唯一平穩分佈;泊松計數依概率趨於無限,從而給出連續時間收斂。真正跳躍即使確定性交替,隨機停留時間仍使觀察時刻不受離散週期阻礙。
證明透視
速率上界在哪裏用上
上界 用了三次,每次目的不同。
- 它使 成為隨機矩陣,鐘響因而可由真正的離散鏈實現;虛擬自環吸收剩餘速率 。
- 它把非爆炸化為單一泊松過程的性質:真正跳躍是鐘響的子集,而鐘響在有界區間內有限。
- 它使 成為可和行向量上的有界算子,從而在可數空間上亦可在零點對 微分。
關鍵一步是稀疏化:幾何個數的鐘響、每次是速率 的指數等待,加起來是速率 的指數等待。有限收斂的敘述再加一個想法:取 使自環為正, 因而非週期;泊松計數趨於無限,把離散收斂轉移到連續時間。
生滅定理只需要平穩方程及零處的邊界。
證明
(每條邊上的概率流為零)
生滅鏈在零狀態的方程為 。在內部狀態重排平衡方程得
所以跨每條邊的概率流相同,邊界迫使此常數為零。反覆代入便得 。若 ,正規化得到概率向量,再由有界速率均勻化證明平穩。若 ,除非 ,否則不能正規化;但 又迫使所有分量為零。這也證明成功正規化時的唯一性。
第一個定理的收斂敘述除有限性外還需要不可約。
反例模式
缺乏不可約性的有限鏈
聲稱:每條有限鏈都有唯一平穩分佈,且 。取狀態 ,,其他非對角速率為零,所以 與 是吸收狀態。,故 迫使 ,而每個 ()都是平穩的。由狀態一出發,鏈以速率 離開,並各以概率 選擇兩個吸收狀態,所以 ,而 、。極限取決於起點。正是不可約性迫使 各行趨向同一向量。
向前方程、向後方程與可觀察量
均勻化還解釋轉移矩陣所滿足的微分方程。對絕對收斂的泊松級數微分,或對有界矩陣指數微分,得到
向前方程 考慮時段末端的可能轉移;向後方程 考慮起點附近的首次轉移。初始行分佈為 時, 滿足 ,各座標平衡流入與流出。把導數設零會得到平穩方程,但它們在上述假設下的充分性,仍來自已建立的過程構造。
有時狀態函數比整個分佈更易解讀。對有界實函數 ,定義
它是位於 時,可觀察量的瞬時期望變化率。速率及函數皆有界,保證求和與微分合法,得 。這並非聲稱個別樣本路徑有普通導數:純跳躍路徑在跳躍間固定,在跳躍處不連續;導數屬於對眾多路徑的期望。
生滅計數取 ,形式漂移在正狀態為 ,在零為 。但此函數無界,不能直接套用有界函數結論;須先局部化或建立所需矩界。檢查符號或數值軟件方程時,這個細節很實用:漂移公式形式正確,仍可能超出證明假設的適用範圍。
例題詳解
例題 3.1.5
(兩種模式:時鐘改變佔用比例)
設 、,則
嵌入鏈確定性交替,平穩分佈為 。但兩種停留時間的均值是 及 ,所以較慢的第一狀態佔較多時間。由零開始,令 。向前方程 配合 ,給出 。這驗證收斂,也顯示嵌入分佈有別於實際時間平衡。
例題 3.1.6
(固定速率的單服務台計數)
所有狀態以速率 出生;正狀態以速率 死亡,零狀態不死亡。總速率至多 ,故存在且非爆炸。權重為 、,從而
細緻平衡直接由 驗證。一般固定出生率 、正狀態死亡率 給出 。平穩概率恰在 時存在。兩率相等時,常數權重不可和;形式等式不能當作平衡概率。
例題 3.1.7
(各狀態速率有限仍會爆炸)
純生鏈從零開始,出生率 。每個停留速率皆有限,但相鄰獨立停留時間滿足
交換和與期望由單調收斂定理保證。非負隨機變量若期望有限,便幾乎必然有限,因此有限隨機時間以前已有無限次出生,最小過程幾乎必然爆炸。只檢查 每行的總離開速率有限,並不能證明非爆炸。相比之下,固定速率泊松純生過程的停留時間和由強大數定律趨於無限。
常見錯誤
常見錯誤
(混淆跳鏈權重與實際時間權重)
跳鏈在轉移時刻抽樣;連續時間平穩分佈在一般固定時刻抽樣。在不可約且相關正規化常數有限時,平穩跳鏈權重正比於 ,因為快速狀態的到訪更頻繁。例如 、 時,實際時間平衡為 ;嵌入鏈仍交替,到訪頻率相等。把實際時間權重乘以 ,恰得相等跳躍權重。吸收狀態沒有下一次真正跳躍,須另行處理。
常見錯誤
(把細緻平衡當作平衡的定義)
一般鏈中,細緻平衡比平穩性強。三狀態有向環沿正方向各以速率一轉移,均勻分佈是平穩的,因各狀態流入、流出平衡。但逆邊速率為零,故不滿足邊上的細緻平衡。生滅模型的細緻平衡來自最近鄰結構及反射邊界,是推導結果,並非通用規則。
常見錯誤
(以為截斷可以創造平衡)
數值截斷也會改變邊界。在 截斷並禁止最後一次出生,會產生有限反射模型。平穩權重只是保留原權重至 ,再用有限和正規化。若無限模型本有平衡且省略尾部很小,可作近似;若原來 發散,有限截斷不能替無限模型創造平衡。
總結
速率矩陣指定指數停留時鐘與跳躍目的地。有界總速率容許泊松時鐘構造,同時證明非爆炸、給出轉移半群並證明 的作用。生滅平衡化為逐邊零概率流,之後仍須檢查可和性。無限狀態存在性、實際時間平穩性及跳鏈平穩性是三項不同檢查。
練習
快速檢查
(對 、,求實際時間平穩分佈、平均停留時間及嵌入平穩分佈。)
平衡唯一一條邊上的概率流。
解答 · 答案
平衡是 ,故分佈為 。平均停留時間依次為 、。嵌入鏈交替,故為 ;把 乘以離開速率 ,亦驗證跳躍權重相等。
快速檢查
(生滅鏈對所有 有 ,對 有 。求平穩分佈、正狀態概率及平均狀態。)
權重是公比 的幾何數列。
解答 · 答案
令 ,則 。正狀態概率為 ,平均為 。總速率不超過 ,故可使用有界速率定理。
快速檢查
(對 選均勻化速率 。求 、驗證行和及平穩分佈,並解釋自轉移為何不改變模型。)
逐個元素計算 。
解答 · 答案
。兩行之和都是一;兩行都等於 ,故此向量被保持。選回當前狀態的鐘響不是真正離開;泊松稀疏化給出離開速率 及 ,因而保持原來的指數停留分佈。
練習 3.1.8
(純生鏈速率為 。不求爆炸時刻的分佈,證明由零開始會爆炸。)
核心證明
解答(3)
- 1
計算期望停留時間
由零出發,第 次停留時間是均值 的指數變量。
- 2
把期望相加
關鍵一步
。
依據: 單調收斂適用於非負部分和 。
- 3
得出爆炸
∎期望有限的非負隨機變量幾乎必然有限,所以 幾乎必然成立,有限時間前已發生無限次出生。毋須知道 的密度。