動機
平穩分佈是指在馬爾可夫(Markov)鏈走一步之後保持不變的分佈。平穩分佈存在,並不等於鏈會收斂到它:一條鏈可以有平穩分佈,卻從某個特定起點出發永遠振盪。懶惰性,即容許鏈停留在原地,可以消除這種振盪。
我們首先證明每條有限鏈都有平穩分佈。然後在明確的不可約性與自環假設下,給出定量的收斂證明。作為應用,連通無向圖上的懶惰隨機漫步會收斂到一個按度數加權的分佈。
定義
定義 5.4.1
(平穩分佈與不可約性)
設 是有限非空狀態空間 上的轉移矩陣。若行概率向量 滿足 ,則稱 是平穩的。若每個狀態都可以沿著一條由正概率轉移構成的有限路徑到達其他任意狀態,則稱該鏈是不可約的。
定義 5.4.2
(全變差距離)
全變差距離為 。我們使用配套章節中已證明的耦合不等式:對分佈 的任意耦合,它們的全變差距離至多等於耦合後兩個狀態不同的概率。
定理
定理 5.4.3
(有限平穩分佈的存在性)
每個有限馬爾可夫鏈至少有一個平穩概率分佈。
定理 5.4.4
(存在可達自環時的收斂性)
設有限鏈不可約,並且存在狀態 滿足 。則它有唯一的平穩分佈 ,並且存在整數 與 ,使得對每個初始分佈 與每個整數 ,都有
證明:Cesàro 平均
證明
(Cesàro 平均有平穩的極限點)
任取初始分佈 ,並定義
概率單純形是緊緻集,所以這個序列有收斂子列。它在一次轉移之後的差是望遠鏡和:
分子的每個座標都有界,所以這個差趨於零。若沿某個子列有 ,則由矩陣乘法的連續性得 。極限仍然是概率向量。這就在不假設不可約性、也不假設原序列 收斂的情況下證明了存在性。
證明透視
以緊緻性與裂項取代收斂
緊緻性提供極限點,裂項求和說明它是平穩的;證明既沒有用到不可約性,也沒有用到 的收斂。邊界項 的每個座標的絕對值至多為 ,因為 與 都是概率向量,所以即使各個分佈振盪,它也趨於零。沿子列取極限用到右乘 的連續性,這在狀態空間有限時成立;極限仍是概率向量,因為單純形是閉集。在交替的兩狀態鏈上,分佈 永遠互換,平均卻收斂到 。
證明:共同的終點
證明
(透過共同終點的耦合)
由不可約性,每個狀態 都有一條通向 的正概率路徑。為每個 選定一條有限路徑。令 不小於所有選定路徑的長度。較短的路徑透過在 處加入自環補齊,直到恰好有 步,其概率仍為正。因此對每個 都有 。
狀態只有有限個,所以 。同時 。對每個 ,把 步轉移分佈分解為在 處的公共質量 與一個剩餘概率分佈。若 ,則每個狀態在 步內以概率一到達 ,下一步論證是顯然的。否則,剩餘分佈為
為了在一個長為 步的區塊上耦合兩個副本,使用一個概率為 的共同伯努利(Bernoulli)決定。若成功,則把兩個區塊終點都置於 ;否則,分別從各自的剩餘分佈中抽取終點。每個終點都具有正確的 邊緣分佈。一旦兩個副本重合,就讓它們使用相同的後續轉移,從而保持相等。
在某個區塊之前尚未相遇的條件下,它們在該區塊末尾相遇的概率至少為 。因此經過 個區塊後它們仍不相同的概率至多為 。把從 出發的鏈與從平穩分佈 出發的鏈耦合起來。第二條鏈的邊緣分佈在區塊時刻始終為 ,由耦合不等式即得所示的界。
若 是另一個平穩分佈,則讓第一個副本從 出發。於是對每個 都有 ,所以該距離為零,。這就證明了唯一性。
證明透視
所有起點共用同一個硬幣
不尋常的想法,是把 分解為 ,且對每個 的 都相同。這讓從不同狀態出發的兩個副本共用同一枚硬幣,因此無論它們的位置如何,都至少以概率 同時位於 。 上的自環只用來把每條路徑補齊到共同的長度 。沒有共同長度, 可能為零,週期鏈就是這樣。
不可約性給出從每個狀態出發的路徑,有限性使最小值為正。論證以幾何方式收束:每個區塊都是一次新的機會,在尚未相遇的條件下,失敗概率相乘為 。耦合只約束區塊的終點,而這正是耦合不等式所需要的。
無向圖上的懶惰隨機漫步
設 是有限、連通、無自環的無向多重圖,至少有兩個頂點,共有 條邊的副本。在頂點 處,以概率 停留在 ;否則均勻地選取一條關聯邊的副本並沿其行走。每個頂點的度數都為正。定義
命題 5.4.5
(懶惰漫步的平穩分佈)
上述懶惰隨機漫步有唯一的平穩分佈 ,並且收斂定理適用於它。
證明
(懶惰漫步的細緻平衡)
度數之和為 ,所以 是概率分佈。對於相鄰的不同頂點 ,設它們之間有 條平行邊的副本,則
同一個細緻平衡等式在 時是平凡的,對不相鄰的頂點則兩邊都為零。對 求和即得平穩性。連通性給出不可約性,並且每個頂點的自環概率都是 ,所以收斂定理適用。只有當所有度數相等時,平穩分佈才是均勻的。
例題詳解
例題 5.4.6
(兩狀態振盪)
在一條邊上的非懶惰漫步會在它的兩個端點之間確定性地交替。均勻分佈是平穩的,但從某一端點出發的漫步會在兩個點質量之間交替,永遠不會收斂到均勻分佈。這裏沒有自環,所以上面的收斂定理不適用。
例題 5.4.7
(懶惰的兩狀態漫步)
在同一條邊上,懶惰漫步以各一半的概率停留或跨過。無論從哪個端點出發,一步之後它的分佈都是均勻的。定理的假設成立。
例題 5.4.8
(三個頂點的路徑)
對於路徑 ,度數分別為一、二、一。它的懶惰漫步的平穩概率為 ,,。在平穩狀態下,中間頂點被訪問的頻率是任一端點的兩倍。
例題 5.4.9
(可約鏈)
若一條兩狀態鏈的兩個狀態都是吸收態,則這兩個狀態上的每個分佈都是平穩的。存在性成立,但唯一性不成立,因為該鏈不是不可約的。
常見錯誤
反例模式
平穩不意味著每個起點都是平穩的
交替的兩狀態鏈有均勻的平穩分佈,但點質量在每個時刻仍是點質量,並且在兩個端點之間交替。平穩分佈描述的是鏈從該分佈出發時會發生甚麼;要使從其他起點出發也收斂,還需要額外的條件。
常見錯誤
(自環是充分條件而非必要條件)
這個證明假設某個狀態上存在可達的自環,這是一個比最一般的非週期性判據更強的充分條件。它並不聲稱每個非週期不可約有限鏈都有自環,儘管存在更廣的收斂定理。
常見錯誤
(耦合只控制區塊的終點)
共同終點的耦合控制的是區塊終點。它並不表示原來的兩條鏈在區塊內部必須沿相同的中間路徑行走。可以在選定終點的條件下抽取路徑,從而得到區塊內部的完整耦合,但全變差的界只用到區塊終點的分佈。
從區塊時刻到每個時刻
定理給出的是 的倍數時刻的界。它也蘊含中間時刻的收斂。對兩個分佈作用同一個轉移矩陣不會增大全變差距離。用耦合來看這一點:先取這兩個分佈的一個最大耦合;當其狀態相等時,讓兩者的下一個狀態相同,並從相應的轉移行中抽取。當它們不同時,使用這兩行的任意耦合。一步之後兩者不一致的概率不大於一步之前。
寫 ,其中 。由於 ,對兩個分佈都作用 得
這個界可能偏保守:用來定義 的路徑的概率可能非常小。它的目的是在所述假設下證明從每個初始分佈出發的收斂性。要得到精確的混合時間估計,一般需要關於該鏈的更多資訊。
沒有自環的非週期性
自環假設很方便,但對有限不可約鏈是非週期的來說並不必要。考慮狀態 ,轉移 與 的概率為一,轉移 與 的概率各為二分之一。其中沒有自環,並且每個狀態都可以到達其他任意狀態。
狀態零有長度為二和三的正概率返回路徑: 與 。它們的最大公因數為一。狀態一同樣有長度為二和三的返回路徑,狀態二有長度為三和五的返回路徑。因此按照通常的定義,即正返回時間的最大公因數,每個狀態的週期都是一。這條鏈儘管沒有一步自環,仍然是非週期的。
我們的證明沒有使用一般的非週期定理;它藉助自環把選定的路徑補齊到同一長度。更一般的證明可以用一般的非週期性論證來取代這個方便的假設,但這裏並未建立這一點。
細緻平衡與平穩性
懶惰漫步的計算使用了細緻平衡:對每一對狀態都有 。對 求和得
因為 中從 出發的那一行之和為一。因此細緻平衡是平穩性的充分條件。它不是平穩性定義的一部分,有些平穩鏈並不是可逆的。
例如,確定性的有向圈 有均勻的平穩分佈,但從零到一有正的流量,而從一到零沒有一步流量。它與均勻分佈並不滿足細緻平衡。這個例子把分佈的不變性與更強的成對流量對稱性區分開來。
度數權重的含義
在無向圖中,每條邊在每個端點處各貢獻一個關聯半邊。簡單隨機漫步在關聯邊的副本中進行選擇,所以度數較大的頂點按比例獲得更多的平穩質量。懶惰性帶來的因子 在不同頂點之間轉移的細緻平衡計算中被約去;它改變漫步的速度,但不改變這個平穩分佈。
對於有一個中心與 個葉子的星形圖,中心的度數為 ,每個葉子的度數為一。共有 條邊,所以中心的平穩概率為 ,每個葉子的概率為 。這些概率之和為一。只有當所有頂點的度數相等時,把它們視為等可能才是正確的。
定理假設圖連通、無自環且至少有兩個頂點,從而每個度數都為正,邊的選取規則有定義。單頂點圖可以單獨處理:規定其唯一狀態為吸收態,其平穩分佈就是該點上的點質量。不連通的圖有互不相通的連通分支,可能有多個平穩分佈。
整數上的簡單漫步沒有平穩概率分佈,因為緊緻性已經失效。
通往推廣的路徑
狀態空間為無限時甚麼不再成立?
整數上的簡單漫步沒有平穩概率分佈,因為緊緻性已經失效。
存在性透過單純形的緊緻性用到了有限性。在 上,每步以概率 向左或向右走的漫步,需要對每個 都有 。於是 是線性的;非負性迫使 ,而總和為一又迫使 ,這是矛盾。這個漫步的 Cesàro 平均仍然存在,但它們越來越分散,極限點不是概率分佈。因此,無限鏈需要額外的假設,才能保證平穩分佈存在。
對於 與目標 ,取 個區塊(向上取整)就足夠了。若 ,則一個區塊就夠。一旦知道所選路徑的概率,這就給出了一個明確的、儘管可能偏鬆的混合時間上界。
參數 是通向 的選定路徑的最大長度,並至少取為一。它不必是最小的公共長度。參數 是到達 的實際 步概率的最小值;選定的補齊路徑的概率給出它的一個可計算的正下界。不同的 與路徑選擇會改變所得的數值估計,但不影響收斂證明的有效性。在具體應用中,比較若干這樣的選擇可以改進所得的界,但不一定能使最終的界對特定的鏈是精確的。
總結
Cesàro 平均為每個有限鏈給出平穩分佈。不可約性加上一個正的自環,給出固定步數之後的共同終點,從而得到幾何衰減的耦合界與唯一性。連通的懶惰無向漫步的平穩概率與度數成正比。
練習
快速檢查
(為甚麼交替的兩狀態鏈有均勻的平穩分佈?)
交換兩個相等的概率,再比較。
解答 · 答案
交換兩個相等的概率不會改變均勻向量。
快速檢查
(三個頂點的路徑上的懶惰漫步的平穩分佈是甚麼?)
計算路徑上各頂點的度數。
解答 · 答案
按路徑順序為 ,因為度數為一、二、一。
快速檢查
(為甚麼公共質量 嚴格為正?)
它是有限多個正數中的最小值。
解答 · 答案
有限多個狀態中的每一個,都有一條補齊到相同長度的、通向 的正概率路徑。有限多個正數的最小值為正。
快速檢查
(為甚麼存在性證明使用平均的收斂子列,而不是直接斷言 收斂?)
想想交替鏈。
解答 · 答案
單獨的分佈可能振盪,交替鏈就是例子。緊緻性保證平均有收斂子列,其望遠鏡和的極限是平穩的。