為甚麼要倒過來看?
轉移矩陣讓我們由現在預測下一個狀態。假如把一段處於平穩狀態的記錄倒放,問題便變成:已知現在的狀態,之前各個狀態的可能性有多大?答案既取決於正向轉移,也取決於各狀態被訪問的頻率。罕見狀態可以很容易轉到常見狀態,但反方向的轉移卻不一定頻繁。
本節討論有限狀態、時間齊次的鏈。下文以行向量表示分佈,並假設讀者熟悉條件概率和矩陣乘法。
流量與反向鏈
設 是有限狀態空間 上的隨機矩陣, 是各分量均為正的平穩概率分佈。令鏈以 開始,則每個後續時刻的分佈都是 。定義一步平穩流量
平穩性表示每個狀態的流入總量等於流出總量:。這並不表示每一對狀態之間的兩個方向流量都相等。
定理 2.10.1
(平穩有限鏈的反演)
對 定義
任取固定終點 ,反向序列 ()是一條初始分佈為 、轉移矩陣為 的馬爾可夫(Markov)鏈。此外 ,而 。
證明
(沿路徑抵消平穩權重)
由平穩方程,;各項也非負。正向路徑 的概率 等於
因為各個 因子互相抵消。右邊正是反向初始分佈和轉移所給出的路徑概率,因而證明有限時間範圍內的反向馬爾可夫性。另外,;再用一次反演公式便得到 。除以 需要正值假設;平穩記錄中不會觀察到平穩質量為零的狀態,要另行處理。
貝葉斯(Bayes)公式可以直接給出單步反向概率;路徑證明更進一步說明整段反向記錄也是馬爾可夫鏈。這裏固定有限終點,不必預先構造雙向無限時間過程。
細緻平衡比平穩性強
定義 2.10.2
(可逆性)
若一條平穩鏈的每條有限路徑,與把它倒轉後的路徑具有相同概率,就稱這條鏈可逆。這等價於 ,亦即以下細緻平衡方程:
事實上,長度為一步的路徑概率相等便給出這些方程;反過來,方程使 ,路徑定理便保證任意有限長度的正反路徑概率相等。
概念視角代數
可逆性即流量矩陣對稱
細緻平衡就是說流量矩陣 (其中 )是對稱矩陣。等價地,對列向量上的加權內積 , 是自伴的:
兩者對所有 相等,恰好當 。此時 是與 相似的實對稱矩陣,所以可逆鏈只有實特徵值。下面的循環鏈有複特徵值 ,單憑這一點已可知它對任何平穩分佈都不可逆。
細緻平衡是求平穩分佈的常用方法,因為它是逐對的條件,而不是按頂點排列的方程組。
命題 2.10.3
(細緻平衡推出平穩性)
若概率向量 對所有 滿足 ,則 。一般而言逆命題不成立。
證明
(對起始狀態求和)
對每個 ,把細緻平衡對 求和,得 ,因為 的第 行和為一。逆命題不成立:平穩性只平衡每個頂點的總流量,細緻平衡卻要求每對狀態的兩個方向分別抵消。例題中的循環鏈對均勻分佈平穩,卻有 。
實際求解時,可以先找正權重 ,使 ,再除以 。有限空間的總和必然有限;可數無限空間則不能想當然地認為總和有限,下例說明了這一點。
反例模式
細緻平衡權重需要有限總和
聲稱:在可數狀態空間上,滿足細緻平衡的正權重總可歸一化為平穩概率。取 上以概率 向右、以概率 向左的遊走,其中 。權重 在每條邊上滿足細緻平衡:,而 。但 ,因為兩邊尾部之一是發散的等比級數。事實上這個遊走是暫態的,根本沒有平穩概率。修正後的敘述加上假設 ;此時由上述命題, 是可逆的平穩概率。
例題
例題 2.10.4
(兩狀態鏈)
設
兩狀態間的平衡方程為 ,所以 。兩方向流量都等於 ,對角方程自動成立,故 。事實上,任何具有嚴格正平穩分佈的兩狀態鏈都可逆:唯一非平凡的平穩方程,正是唯一非平凡的細緻平衡方程。
例題 2.10.5
(平穩但不可逆的循環流)
在狀態 上令 。均勻分佈 是平穩的:每個狀態流入的概率與流出的概率相同。然而 ,。反向鏈必定沿相反方向移動,因此與正向鏈不同。此鏈有週期;平穩性仍然成立,只是由固定狀態出發時未必收斂。
若想要非週期的例子,可令 。均勻分佈仍然平穩,而 、。自環消除了週期,卻沒有消除循環流。因此平穩性和非週期性都不能推出可逆性。
第三個例子直接用細緻平衡求 ,再驗證反向矩陣並不是轉置。
例題 2.10.6
(三狀態的生滅鏈)
設
一步之內只有相鄰狀態互通,所以細緻平衡只有兩條非平凡方程: 及 。因此 、,歸一化得 。用第一列驗證平穩性:。此鏈可逆,所以 。轉置則不同:它的第一行 之和為 ,所以 甚至不是隨機矩陣。這裏的邊界情形是轉移圖為一條沒有環路的路徑;對這種圖,下面的環路判別法自動成立,細緻平衡總可逐條邊求解。
環路判別法及其限制
循環流的例子提示:不可逆性是環路的性質。以下判別法把這一點說得精確。
定理 2.10.7
(可逆性的環路判別法)
設 是有限不可約鏈,且 當且僅當 。則 對某個嚴格正的平穩分佈可逆,當且僅當每條使用正概率轉移的有向環路 都滿足
證明
(由根狀態沿路徑構造權重)
必要性:把環路上各條邊的細緻平衡方程相乘,消去正的 因子即可。充分性:選一個根狀態 ,令 。沿由 到 的正概率路徑,逐步定義 。任意兩條路徑給出的乘積相同:先走第一條,再反向走第二條,便得到閉合路徑,可應用環路條件。不可約性確保每個狀態都可到達。所得權重在每條正概率邊上滿足細緻平衡;由對稱支撐假設,零概率邊也沒有問題。最後把正權重歸一化為 ,由上述命題它是平穩的。
證明透視
為甚麼權重定義良好
充分性的證明以沿路徑的乘積定義 ,所以唯一真正的困難是與路徑無關。這正是用到環路條件之處:兩條由 到 的路徑合成一條閉合路徑,而閉合路徑的條件使兩個乘積相等。閉合路徑可以重複經過狀態,但它可分解為有向環路,所以對環路的條件已經足夠。
對稱支撐假設用了兩次:比值 的分母必須非零,而 的邊自動滿足細緻平衡。不可約性使每個 都有定義,有限性則使 有限,這正是上面可數反例中失效的一步。這也說明,若圖中有多個獨立環路,單檢查其中一個並不足夠:只要一條環路不平衡,就有兩條路徑給出不同結果。
常見錯誤
常見錯誤
(用轉置來反演)
反向鏈是 ,而不是 。兩者只在 均勻時一致,例如雙隨機矩陣。在生滅鏈的例子中, 有一行之和為 ,根本不是轉移矩陣。
常見錯誤
(由平穩性推斷可逆性)
解出 本身並不保證細緻平衡。循環鏈對均勻分佈平穩,但 、。必須逐對檢查 ,或對每條環路使用環路判別法。
練習與解答
快速檢查
(設 。求平穩分佈 和平穩狀態下的 。)
兩狀態鏈只有一條非平凡的平衡方程。
解答 · 答案
由 和總和為一,得 。細緻平衡成立,所以 。
快速檢查
(一條三狀態鏈以概率 順時針移動,以概率 逆時針移動。求平穩分佈及反向轉移概率。此鏈可逆嗎?)
先檢查各列之和。
解答 · 答案
每列的總和都是一,故 。反向鏈交換兩個方向的概率:順時針為 ,逆時針為 。兩方向邊流量不同,因此不可逆。等價地,順時針環路的乘積為 ,其反向為 。
快速檢查
(假設 對嚴格正的平穩分佈 可逆。證明對每個 ,都有 。)
比較一條路徑與其反向路徑。
解答 · 答案
正向每條 步路徑與其反向路徑概率相同。對所有中間狀態求和,就得到所需等式。也可利用 和路徑中的因子抵消。
快速檢查
(某同學在可數無限狀態空間找到滿足細緻平衡的正向量 ,便斷言 是概率分佈。給出反例,並指出缺了甚麼步驟。)
試考慮對稱遊走。
解答 · 答案
整數上的簡單對稱隨機遊走取 ,每條邊都滿足細緻平衡,但 。歸一化需要非零且有限的總質量;這裏得到的是不變測度,不是概率分佈。