動機
目標的相對權重容易算,不代表容易獨立抽樣。Markov 方法由一個狀態開始,逐次提議局部改變;後期狀態的分佈可以接近目標,但相鄰輸出相依。因此至少要回答兩件事:轉移為何保留所需分佈,以及從指定起點是否真的能接近它。
細緻平衡只回答第一問。完全不移動的算法也可對許多目標滿足平衡;兩狀態輪流切換也可保留目標,卻不從固定起點收斂。我們會額外證明連通及正停留條件,然後用轉移矩陣的正次方推導收斂,而不是只說一句未解釋的「混合」。
全部狀態空間均有限。我們為四狀態目標寫出完整 Metropolis–Hastings 與隨機掃描 Gibbs 程式,亦計算精確平穩方差。沒有宣稱適用一般可數或連續狀態空間,也沒有引用未證的一般 MCMC 中心極限定理。
定義
狀態集 有 點,正權重為 ,目標 。
定義 9.1.1
(轉移矩陣、平穩與細緻平衡)
上的轉移矩陣 元素非負,每行和為一。分佈寫成行向量,一步後為 。若 ,稱分佈 對 平穩。若每對狀態 都有 ,稱 對 滿足細緻平衡。
細緻平衡是逐對條件,平穩則是整列的條件。另一種描述可以把兩者的關係說得精確。
概念視角代數
細緻平衡即一個矩陣的對稱性
令 。 的 元素是 ,即從 出發的鏈在時刻零位於 、時刻一位於 的概率。細緻平衡正是說 對稱,亦即 與 有相同聯合分佈。平穩只說 的列和等於 :第 列之和是 ,而第 行之和因 每行和為一而等於 。對稱使列和等於行和,所以細緻平衡推出平穩。反方向不成立:三狀態輪轉 保留均勻分佈,但 在 的元素是 ,在 的元素是 。
Metropolis 構造正是為了直接得到這種對稱形式。
定義 9.1.2
(Metropolis–Hastings 核及其惰性版本)
設提議矩陣 每行和為一。當 ,由 到 的提議以概率 接受;沒有反向支撐,接受概率就是零。對 ,令 為 乘該接受概率,其餘概率放到 。惰性版本為 ,即另加一半機會直接停留而不提議。
定義 9.1.3
(互相提議圖、不可約與周期)
當 與 皆正時,互相提議圖連接兩個不同狀態 。若任意狀態都能以正概率在有限步內到達任何其他狀態,稱轉移核不可約。狀態的周期是其正概率返回時間的最大公因數;每個狀態周期為一時,稱轉移核非周期。
互相提議無向圖連通會給出不可約性;有正停留機會,返回時間便包含一,因而周期為一。
定義 9.1.4
(全變差距離)
對有限集 上的分佈 ,全變差距離為 。
函數期望之差不多於其取值範圍長度乘該距離。程式的觀測量是指示函數,所以範圍長度為一。
定理 / 命題
定理 9.1.5
(Metropolis 平衡與有限可達性)
Metropolis 核及其惰性版本均保留 ,非對角正轉移恰好是互相提議邊。若圖連通, 不可約且非周期;取 ,則 每個元素都正。
定理 9.1.6
(正次方給收斂,而不只是不變性)
設 保留 ,且 嚴格正。令 。由每行和為一,必有 。若 ,任意起始分佈滿足
所以目標是唯一平穩分佈,且分佈實際收斂。若 ,則 ,其中 每行皆均勻; 亦均勻,而且所有 都有 。
定理 9.1.7
(正有限乘積上的 Gibbs 收斂)
有限非空座標集的 重乘積上,假設每個配置的目標概率都正。均勻選一座標,依給定其餘座標的精確條件目標重新抽取。此隨機掃描 Gibbs 核滿足細緻平衡、不可約及非周期,且第 次方嚴格正,因此前一定理適用。若有結構性零值,須另查可達性。
證明思路
證明
(平衡、互相提議邊及以停留補足步數)
非對角 Metropolis 概率流為 ,交換兩點不變;對角平衡自動成立。加總平衡式即得平穩,惰性化也保留它。目標權重正,故正轉移恰是互相提議邊。連通路徑可取長度至多 ,再以正對角停留補足至 ,便證每對的 步概率正。停留也直接證周期為一。
證明
(從正次方分出均勻部分)
令 每行都是均勻分佈。 每行至少包含 份均勻行,故 時可寫成 ,其中 是隨機矩陣。乘隨機矩陣不增加全變差,因逐座標展開後可用三角不等式。兩分佈差的總質量零,乘 消失,因此每 步至少乘收縮因子 。與平穩 比較,再處理不足一整塊的非擴張剩餘步,便得公式。若另有平穩分佈,其距離既不變又趨零,必與 相同。若 ,每項下界為 ,行和又是一,便迫使 所有元素皆為 。平穩性使 均勻,且第 步起一直保持 。
證明
(Gibbs 平衡與逐座標路徑)
Gibbs 中,僅選定座標不同的兩配置,其流量為共同其餘座標的概率,乘兩個條件概率。兩因子交換仍相同,因此每個座標核平衡,平均後亦平衡。要由任意配置到另一個,依次選座標一至 ,每次設成最終所需值。所有條件概率正,連保留已正確值也正,因此指定次序及取值的概率為正,證第 次方全正。條件自更新容許停留,亦證非周期。
證明透視
每個假設在收斂證明中的位置
平衡只證明已從目標出發的鏈會保持目標;其後每個結論都需要另一個假設。所有目標權重為正,使反向提議為正時接受比率也為正,所以被接受的移動恰是互相提議邊。一半停留概率用了兩次:它把每條連接路徑補足至同一長度 ,令單一次方 每個元素都正;它亦給出非周期性。不明顯的一步是分解 。由於 、 總質量都是一,:均勻部分完全忘記起點,只有權重 的餘下部分能把差異帶到下一塊。證明以取 並用 收結,這是平穩性唯一出場之處;沒有它,同一估計只說明兩份鏈的分佈互相靠攏,不說明它們靠向 。在 Gibbs 情形,所有配置為正同時取代了停留與互相提議邊兩個條件;若有結構性零值,逐座標路徑可能被阻斷,正如最後一個例題所示。
例題詳解
例題 9.1.8
(兩狀態鏈把漸近標準誤放大三倍)
矩陣對角為 、非對角為 ,平穩分佈均勻。狀態一指示量中心化為 ,特徵值是 ,所以平穩時滯 協方差為 。 個平穩觀測的平均方差是
時約為 ,獨立指示量卻只有 。 乘方差的極限為 ,故漸近標準誤是獨立值三倍。 只能作有效樣本數的方差比代理,不會真的產生這麼多獨立觀測。
公式由中心和平方展開而來:平穩使相隔 的每對都有同一協方差,兩種次序各有 對。一般有限平穩鏈可寫 ,其中 是中心觀測量。正次方收縮使這些條件中心期望幾何下降,絕對協方差可求和,所以平穩均方誤差是 級別。這仍不證常態近似,也不證短軌跡能準確估計前面的常數。
例題 9.1.9
(完整四狀態 Metropolis 與 Gibbs 計算)
把二元對編成零至三,權重為 ,低位元(state & 1)為一的概率是 。Metropolis 等概率提議翻轉其中一位,再加一半停留;Gibbs 選一位後依兩個條件權重重新抽取。程式另建立精確有限轉移矩陣,並用上式算平穩平均方差。
import math
import random
weights = [1.0, 2.0, 2.0, 5.0]
pi = [w / sum(weights) for w in weights]
values = [0.0, 1.0, 0.0, 1.0]
def mh_step(state, rng):
if rng.random() < 0.5:
return state
proposed = state ^ (1 << rng.randrange(2))
ratio = min(1.0, weights[proposed] / weights[state])
return proposed if rng.random() < ratio else state
def gibbs_step(state, rng):
bit = 1 << rng.randrange(2)
zero, one = state & ~bit, state | bit
chance_one = weights[one] / (weights[zero] + weights[one])
return one if rng.random() < chance_one else zero
def transition(kind):
P = [[0.0] * 4 for _ in range(4)]
for i in range(4):
for bit in [1, 2]:
if kind == "mh":
j = i ^ bit
P[i][j] += 0.25 * min(1.0, weights[j] / weights[i])
else:
zero, one = i & ~bit, i | bit
total = weights[zero] + weights[one]
P[i][zero] += 0.5 * weights[zero] / total
P[i][one] += 0.5 * weights[one] / total
if kind == "mh":
P[i][i] = 1.0 - sum(P[i])
return P
def stationary_mean_variance(P, n):
mean = sum(p * value for p, value in zip(pi, values))
g = [value - mean for value in values]
z = list(g)
total = n * sum(p * x*x for p, x in zip(pi, g))
for lag in range(1, n):
z = [sum(a * b for a, b in zip(row, z)) for row in P]
covariance = sum(p * a * b for p, a, b in zip(pi, g, z))
total += 2 * (n - lag) * covariance
return total / (n * n)
for name, step, seed in [("mh", mh_step, 2026),
("gibbs", gibbs_step, 2027)]:
P = transition(name)
assert all(math.isclose(sum(row), 1.0) for row in P)
assert all(math.isclose(pi[i] * P[i][j], pi[j] * P[j][i])
for i in range(4) for j in range(4))
rng, state = random.Random(seed), 0
for _ in range(500):
state = step(state, rng)
output = []
for _ in range(20000):
state = step(state, rng)
output.append(values[state])
mean = math.fsum(output) / len(output)
descriptive = mean * (1 - mean)
naive_se = math.sqrt(descriptive / len(output))
model_se = math.sqrt(stationary_mean_variance(P, len(output)))
print(name, round(mean, 6), round(naive_se, 6), round(model_se, 6))
輸出依次是觀測均值、假設獨立的標準誤,以及精確平穩模型的參考標準誤。最後一列不是此固定起點軌跡的區間覆蓋保證。五百步暖身只是示意,不會使起點恰好平穩。正次方界可另限制初始化偏差:範圍長度 的觀測,在 步暖身後任何平均的均值偏差,至多 。
本例每步只查固定數量的表。一般目標求值及條件抽樣可能很貴。示範保存 個輸出,故除了有限目標,另需 空間;精確參考方差需要 算術。這些成本與鏈只保存一個當前狀態不同。大問題通常不能像此處直接建立全矩陣計方差。
例題 9.1.10
(平衡仍可容許兩種收斂失敗)
兩狀態必定翻轉的核,對均勻目標滿足平衡,但從零開始永遠交替。加入正停留可修復周期。另一例的二元目標只在 有質量,單座標 Gibbs 無法在不經零質量配置下互通,所以兩者皆吸收;暖身多久也不會從固定起點選出所需混合。一次改兩個座標可修復可達性,但單純惰性不能連通兩類。
常見錯誤
第一個錯誤關乎可達性定理的假設:需要連通的是互相提議圖,而不是提議本身。
反例模式
提議不可約,Metropolis 核卻凍結
聲稱:若提議矩陣 不可約,則 Metropolis 核亦不可約。取三個狀態及單向環 ,它是不可約的。對任何正目標,由 到 (下標按模 3)的提議,接受概率為 ,因為 。所有提議都被拒絕,所以 、。從狀態 出發,分佈永遠是點質量 ,對每個 與 的全變差距離都是 。修正後的假設是互相提議圖連通;例如以各一半概率提議另外兩個狀態,每對狀態便互相提議,定理隨即適用。
非對稱提議若在接受概率中漏去提議比值,也會改變不變分佈。
常見錯誤
(刪去重複狀態)
重複狀態也是正式輸出,包括拒絕及刻意停留。刪去它們便改變觀測規則。練習中權重為一及三的兩狀態鏈,每次真正改變都切到另一點;只記改變會得到交替清單,長期比例各一半,不是目標的一比三。重複記錄保存不同停留時間,正是目標分佈的表示方式。方差公式應按經過步數計,不可直接換成接受移動次數。
常見錯誤
(把有初始化或抽稀的鏈當作獨立)
任意起始鏈不能直接套平穩協方差公式。單時刻分佈收斂處理初始化,平穩後的自相關處理相依性。每隔十步取一個並不證明獨立。經驗自相關及分批均值可作診斷,但短軌跡的噪音估計不是精度定理。此處有限矩陣提供了大多數大型模擬沒有的參考答案。
不需要:任何固定分佈都可擔當這個角色,而這種形式正是能推廣到無限狀態空間的形式。
通往推廣的路徑
收斂證明需要均勻行嗎?
不需要:任何固定分佈都可擔當這個角色,而這種形式正是能推廣到無限狀態空間的形式。
設 的每一行都不小於 ,其中 是一個固定分佈。當 時,便有 , 為隨機矩陣;又因兩個分佈的總質量都是一,,所以每一段後的距離同樣至多變為原來的 倍。這種下界(minorization)形式在不存在均勻分佈的地方仍有意義,例如可數或連續狀態空間;在那裏它通常只在空間的一部分成立,所需的進一步論證超出本節範圍。
總結
Metropolis 平衡控制目標,互相支撐控制可達性,正停留控制周期。正有限 Gibbs 條件給類似保證。嚴格正次方證明幾何收斂;相依樣本誤差再須計協方差。有限平穩計算及初始化限制讓這些條件清楚可核查,毋須冒稱一般 MCMC 中心極限定理。
練習
練習 9.1.11
(兩個目標權重為一及三,提議總是切換,再作 Metropolis 接受及額外一半停留。求轉移矩陣並驗證細緻平衡。)
基礎
解答 · 答案
目標為 。由輕狀態出發的切換必被接受;由重狀態出發則以概率 接受。惰性矩陣是 。兩向流分別為 、,皆是 。每行和一,非對角與對角皆正,亦有可達性及非周期。
練習 9.1.12
(對稱兩狀態鏈的切換概率為 。求狀態一指示量的時滯 協方差,以及 乘平穩平均方差的極限,並與獨立觀測比較。)
核心
解答 · 答案
中心指示量是特徵向量,特徵值為 ,故 ,極限為 。獨立指示量只有 ,所以漸近方差四倍、標準誤兩倍。此方差計算仍不是常態近似定理。
練習 9.1.13
(二元配置 的權重依序為 。在 ,求兩個 Gibbs 座標取值為一的條件概率,並驗證隨機掃描下由 至 的邊滿足平衡。)
核心
解答 · 答案
第一座標取一的概率是 ,第二是 。向 的轉移為 ,反向為 。兩點目標質量為 ,乘起來流皆為 。全正也容許逐座標連接任何兩配置。
練習 9.1.14
(正次方界有 、。求十二步後的全變差界,以及取值在 的函數的均值偏差界;多少暖身步足以使偏差界不多於 ?)
核心
解答 · 答案
十二步有四完整塊,全變差至多 ,偏差至多 。要不多於 ,需 ; 約為 ,二十一塊足夠,所以 是充分暖身數。界保守,也說明慣用暖身數字本身不是量化證明。