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

陈小羽 等: 吉布斯采样在临界点前的快速收敛 1617

,
δ ∈ (0,1) λ ⩽ (1−δ)λ c (∆)) 内的 O(nlogn) 混合时间 [10−12] .
最近, 研究人员提出一种基于高维扩张器的马尔可夫链分析工具 [23−25] , 也被称为谱独立性 (spectral indepen-
dence) 技术. 借助这种技术, Anari 等人 [6] 首次证明了一般图上任意亚临界区域以内的多项式混合时间. 这个结果
. 其中, SI 是谱独立性参量, 只和目标分布相关. 对于硬核模型来说, 这个参量有如下的上界:
之后被优化为 n O(SI) [8]

{ min{1/δ, n}, λ ⩽ (1−δ)λ c (∆)
SI = O(1)× .
n, λ > λ c (∆)
所以, 当 δ 很小时, n O(SI) 是一个大多项式.
因为高维扩张器技术对一般的分布都适用 (甚至是唯一性区域以外的硬核模型), 所以在一般情形下 (不一定
是硬核模型) 改进这个 n O(SI) 的混合时间界是不可能的 (不然会和 Sly 的下界矛盾 [15] ). 想要改进这个混合时间界,
需要用到硬核模型独有的性质.
在 Chen 等人 [9] 的工作中, 他们注意到在稀疏图上随机选取足够多比例的点删掉之后剩下的点大概率断开成
若干规模很小的连通块. 利用这个额外性质, 他们证明了稀疏图 (最大度数为常数) 上硬核模型的 Glauber dynamics
O(nlogn) 混合时间. 之后的若干工作引入了场动力系统 (field dynamics), 熵独立性 (entropic independence) 等新
的
工具 [1,2] , 它们能利用上硬核模型在 λ ∈ (0, (1−δ)λ c (∆)) 这整个区域内 SI 都是常数这一特殊性质. 最终成功证明了

硬核模型上任意的亚临界区域内的 O(nlogn) 混合时间 [3,7] .
值得一提的是, 上面提到的这些证明通常都依赖一些高等数学工具例如随机微分方程. 本文通过引入计算复
杂性规约的思想实现了类似的结果. 它的证明更简单并且完全是初等的.
1.1 主要结果
本文通过研究 Glauber dynamics 的谱隙 (spectral gap) 来研究其混合时间. 设 P I 为 Glauber dynamics 在硬核模
I = (G,λ) 上的转移矩阵. 众所周知, 1 = λ 1 ⩾ λ 2 ⩾ ... ⩾ λ |Ind(G)| ⩾ 0. 谱隙与混
型实例 P I 具有|Ind(G)|个非负实特征值
合时间密切相关, 定义 P I 的谱隙如下:

γ I ≜ 1−λ 2 .
我们的主要贡献是以下定理.
定理 1. 设 0 < δ < 1 为常数, 对于任何满足 ∆ ⩾ 3 和 λ ⩽ (1−δ)λ c (∆) 的硬核模型实例 I = (G,λ), Glauber dynamics

在 I 上的谱隙满足:

1 2
⩽ γ I ⩽ ,
C(δ)n n
并且 Glauber dynamics 的混合时间满足:

( )
1
T mix (ε) ⩽ 4C(δ)·n· nlog∆+log ,
ε
( ) O(1/δ)
1
其中, n 是 G 中顶点的数量, Δ 是 G 的最大度数, C(δ) = 是仅依赖于 δ 的常数.
δ
我们的证明依赖于一种新的变换思想. 具体来说, 首先将硬核模型实例转换为具有足够大最大度数的新实例.
接下来, 分析变换后实例上的 Glauber dynamics. 这种分析利用了某些概率集中性质, 还使用了文献 [9,20] 中发展
的“局部到全局”理论. 最后, 将原始实例上的 Glauber dynamics 与转换后实例上的 Glauber dynamics 进行比较. 这
种转换提供了一定的优良特性, 以便每个证明步骤可以顺利进行. 请参见第 3 节查看证明概要.
更加直观地说, “局部到全局”技术的核心, 在于利用特定的一系列条件分布对目标分布 µ 进行分解. 在 Chen
等人 [9] 以及更早的 Anari 等人 [6] 的工作中, 通过固定一系列顶点的状态 (即 pinning) 来得到这些条件分布. 在我们
的前期工作 [2] 中, 为了改进 Chen 等人 [9] 的工作而引入了场动力系统, 该技术在此前的基础上考虑了更复杂的一系
列条件分布. 在场动力系统引入的条件分布当中, 除了一些特定顶点状态被固定之外, 硬核模型的参数也会有相应
的偏移. 这些更复杂的条件分布虽然帮助我们解决了度数受限的问题, 但是处理它们需要更高等的数学工具以及
更复杂的分析. 在本文的证明中, 首先通过一个组合变换将原分布 µ 转换为一个相似却又不同的新分布 . 之后本
µ k