Page 175 - 《软件学报》2026年第4期

1616 软件学报 2026 年第 37 卷第 4 期

理、数理统计与机器学习等多个领域中, 吉布斯分布都被广泛且深入地研究, 并有诸多重要应用. 在理论计算机科
学当中, 人们关注的吉布斯分布通常和经典的图论问题紧密相关. 这些吉布斯分布的合法状态通常恰好就是某个
图论问题的解空间, 例如硬核模型 (hardcore model): 状态空间为图的所有独立集 (independent set); 单体-双体模型
(monomer-dimer model): 状态空间为图的所有合法匹配 (matching); 玻茨模型 (Potts model): 参数取值恰当时状态
空间为图的所有合法 q-染色 (q-vertex coloring).
吉布斯分布的采样问题是理论计算机科学的重要研究课题, 这是因为采样这种计算任务在吉布斯分布上常有
计算相变现象——采样问题的计算复杂性会随着吉布斯分布的参数变化而发生骤然变化. 马尔可夫链蒙特卡洛
(Markov chain Monte Carlo, MCMC) 方法是针对这类问题研究最为深入的算法. 其中, 硬核模型是研究吉布斯采样
计算相变所最经常用的基准 (benchmark) 模型, 也是各种采样算法以及分析工具的试金石 [1−17] .
一个硬核模型实例由一个元组 I = (G,λ) 指定, 其中 G = (V,E) 是一个简单无向图, λ ∈ R >0 是一个正实数. 令
Ind(G) ⊆ 2 表示图 G 中所有独立集的集合. 对于任意独立集 S ⊆ Ind(G), 其权重定义为:
V

|S |
w(S ) = w I (S ) ≜ λ .
I 指定了一个在
硬核模型实例 Ind(G) 上的吉布斯分布 µ = µI, 满足:

w(S )
∀S ∈ Ind(G), µ(S ) ≜ .
Z G (λ)
∑
在无向图 G 中, Z G (λ) ≜ w(S ) 被称为配分函数. 计数问题, 即计算配分函数, 是硬核模型的核心计算任
S ∈Ind(G)
务. 精确计数是#P 难问题 [18,19] . 更多研究集中在近似计数 [15,17,20,21] . 根据经典的规约算法 [22] , 这一问题等价于吉布
斯分布 µ 的采样问题.
硬核模型中有一个著名的相变现象. 在无穷 Δ-正则树中, 存在关键的唯一性阈值 (uniqueness threshold):

(∆−1) ∆−1 e
λ c (∆) ≜ ≈ .
(∆−2) ∆ ∆−2
如果 λ < λ c , 根节点上的边缘分布与叶节点上的边界条件在深度为ℓ的情况下以指数方式衰减; 如果 λ > λ c , 即
使ℓ→∞, 长程相关性始终存在. 在相同的阈值处, 也发现了计算复杂性的相变. Weitz [17] 表明, 对于所有最大度数为
常数 Δ 的图, 如果 λ < λ c (∆), 则存在一种完全多项式时间逼近方案 (FPTAS) 用于估计 Z G (λ). 另一方面, Sly [15] 证明
除非 NP =RP, 否则当 λ > λ c (∆) 时, 不存在用于估计 Z G (λ) 的完全多项式随机化逼近方案. 对于硬核模型来说, 从其
吉布斯分布中采样在计算上等同于近似计数 [22] .
Glauber dynamics (也称吉布斯采样算法) 是从硬核模型当中采样的标准 (canonical) 马尔可夫链蒙特卡洛方
法. 设 I = (G = (V,E),λ) 为一个硬核模型实例. 设 Γ(v) 表示 G 中 v ∈ V 的邻居. I 上的 Glauber dynamics 从任意一个
X 0 ∈ Ind(G) 开始. 在第 t 个转移步骤中, 它执行以下操作.
独立集
● 均匀随机选择一个顶点 v ∈ V.
● 如果 X t−1 ∩Γ(v) , ∅, 则 X t = X t−1 ; 否则, 令:

 1

 X t−1 \{v}, 以概率



 1+λ

X t =  .

 λ
 X t−1 ∪{v}, 以概率



1+λ
Glauber dynamics 最终会收敛到唯一的稳态分布 µ. 为了衡量收敛的速度, 我们定义 Glauber dynamics 的混合
时间 (mixing time) 为:

∀0 < ε < 1, T mix (ε) ≜ max min{t|d TV (X t ,µ) ⩽ ε},
X 0 ∈Ind(G)
其中, d TV (X t ,µ) 表示 X t 的分布与 µ 之间的全变差距离 (total variation distance).
2
对于硬核模型上的 Glauber dynamics, 之前有相当多的研究. 早期的工作证明了在一个亚临界区域 λ <
∆−2
内的 O(nlogn) 混合时间, 其中 n 是顶点数量 [13,14,16] . 随后一些工作在特殊图上做到了任意的亚临界区域 (对任意