动机
目标的相对权重容易算,不代表容易独立抽样。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
(正次方界有 、。求十二步后的全变差界,以及取值在 的函数的均值偏差界;多少预烧步数足以使偏差界不超过 ?)
核心
解答 · 答案
十二步含四个完整块,全变差至多 ,偏差至多 。要使偏差界不超过 ,需 ; 约为 ,二十一块足够,所以 是充分的预烧步数。此界保守,也说明惯用的预烧步数本身不是定量证明。