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

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

∑ 2eℓ|Λ|
X = t > =
均匀随机抽取的随机子集. 对于每个 i ∈ Λ, 定义指示随机变量 X i = 1 i∈S . 令 X i , 则对于任意
i∈Λ n
−t
2eE[X], 有 Pr[X ⩾ t] ⩽ 2 .
3 证明大纲
本节证明主定理 (定理 1). 首先, 构造一个变换, 将原本的目标硬核模型分布 µ 变换为另外一个硬核模型分布
µ k (定义 3). 这两个分布紧密相关然而 µ k 对应的硬核模型总是具有 Ω(logn) 量级的最大度数. 我们会首先证明 µ k
上的 Glauber dynamics 具有最优的谱隙 (引理 6). 然后, 通过比较 µ 和 µ k 上的 Glauber dynamics, 来证明这两个分
布上的 Glauber dynamics 的谱隙具有相同量级 (引理 7). 最后结合引理 6 和引理 7, 我们就能证明定理 1.
我们考虑以下一系列硬核模型实例.
定义 2. 硬核模型实例族 F(δ). 令 0 < δ < 1 为一个常数. 定义 F(δ) 为满足 ∆ ⩾ 3 且 λ ⩽ (1−δ)λ c (∆) 的所有硬核
I = (G,λ) 的集合, 其中 Δ 是图 G 的最大度数.
模型实例
3.1 谱隙的下界
我们首先证明了谱间隙的下界.
( ) O(1/δ)
1
引理 4. 设 0 < δ < 1 是一个常数. 存在一个常数 C(δ) = , 对于任意 I = (G,λ) ∈ F(δ), Glauber dynamics
δ
在 I 上的谱隙满足:

1
γ I ⩾ ,
C(δ)n
其中, n 是 G 中顶点的数量, Δ 是 G 的最大度数.
固定一个常数 0 < δ < 1. 为了证明引理 4, 我们使用 8/δ 作为阈值, 将 F(δ) 中的所有实例分为两部分: 最大度
8/δ 的实例. 注意对于第 1 部分, 我们已经有了文献 [9] 中的结果如下.
数小于 8/δ 的实例和最大度数大于等于
( ) O(1/δ)
1
[9]
引理 5 . 设 0 < δ < 1 为常数. 存在一个常数 C 0 (δ) = , 使得对于任意 I = (G,λ) ∈ F(δ), 如果 ∆ < 8/δ,
δ
则 I 上 Glauber dynamics 的谱隙满足以下关系:

1
γ I ⩾ ,
C 0 (δ)n
其中, n 是 G 中顶点的数目, Δ 是 G 的最大度数.
引理 5 是通过结合文献 [9] 中的几个结果证明的. 为了完整起见, 我们在附录 B 中给出了证明. 我们现在只关
注最大度数至少为 8/δ 的核心实例. 下面的转换是本文证明中的一个关键工具.
定义 3. k-变换. 设 k ∈ N 为一个整数. 给定一个硬核模型实例 I = (G = (V,E),λ), 定义一个变换实例 I = (G ,λ ) ≜
+
′
′
′
′ ′ ′ ′
Trans(I,k), 使得 λ ≜ λ/k, 图 G = (V ,E ) 构造如下.
′
′
● 对于任意顶点 v ∈ V, 存在 k 个顶点 v 1 ,v 2 ,...,v k ∈ V 在 G 中形成一个 k-团.
′
● 对于任意边 {u,v} ∈ E, 任意 1 ⩽ i, j ⩽ k, 在 G 中 u i 和 v j 通过一条边相连.
图 1 是一个 k-变换 (k=3) 的示例. 首先, 对于 G 中的每个顶点, 在 G 中有一个 3-团. 以顶点 a 为例, 我们在 G ′
′
a 1 、a 2 、a 3 组成的 3-团. 接下来, 我们在团之间添加边. 以 G i, j ∈ [3], 在
中有顶点 中的边 {a,b} 为例, 对于任意的
{ }
′
G 中有一条边 a i ,b j .

a 1 a 2 a 3
a
3-变换
b b 1 b 2 b 3
c d
c 1 c 2 c 3 d 1 d 2 d 3
G G′
图 1 3-变换的示例