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

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

{ }
1 λ n
µ min ⩾ min n , n .
(1+λ) (1+λ)
( )
1 2e 1
注意到 ⩽ λ ⩽ λ c (∆) ⩽ . 这意味着 log ⩽ nlog(8∆). 我们有:
2∆ ∆−2 µ min
( ) ( ) ( )
1 1 1
T mix (ε) ⩽ C(δ)nlog ⩽ C(δ)n nlog(8∆)+log ⩽ 4C(δ)·n· nlog∆+log .
εµ min ε ε
谱隙的上界的证明是对 Cheeger 不等式的简单应用. 固定任意顶点 u ∈ V. 定义一个集合 S ≜ {σ ∈ Ω I | σ u = 1}.
换句话说, S 表示所有独立集 I 的集合, 其中 u ∈ I. 注意, 对于任意的 σ ∈ S , 存在唯一的 τ ∈ Ω\S 使得 P(σ,τ) > 0, 其
1
,
中 τ u = 0, 且对于所有 v ∈ V\{u} τ v = σ v . 根据 Glauber dynamics 的转移规则, 有 P(σ,τ) ⩽ . 因此, 集合 S 的导通率
n
可以被限制为:

∑
µ(σ)P(σ,τ) ∑ 1
µ(σ)
σ∈S,τ∈Ω\S σ∈S n 1
Φ(S ) = ∑ ⩽ ∑ = .
µ(σ) µ(σ) n
σ∈S σ∈S
∑
µ(σ)P(σ,r)
σ∈Ω\S,τ∈S 1
类似地, 集合 Ω\S 的导通率可以被限制为 Φ(Ω\S ) = ∑ ⩽ . 于是, Glauber dynamics 的导
µ(σ) n
σ∈Ω\S
通率 Φ 满足:

1
Φ = min Φ(H) ⩽ max{Φ(S ),Φ(Ω\S )} ⩽ .
H⊆Ω:µ(H)⩽1/2 n
2
根据 Cheeger 不等式 (命题 4), 我们有 γ I ⩽ 2Φ = .
n
4 Glauber dynamics 在 k-变换实例上的谱隙
本节使用以下两个结果证明引理 6. 第 1 个结果 (命题 5) 表明, 在 k-变换之后, 新实例仍然满足唯一性条件.
第 2 个结果 (引理 8) 表明, 如果一个硬核模型实例满足唯一性条件并且具有足够大的最大度数, 则相应 Glauber
dynamics 的谱隙有下界.
8
命题 5. 设 0 < δ < 1 为常数, k ∈ N 为正整数. 对于任意实例 I = (G,λ) ∈ F(δ), 其中图 G 的最大度数 ∆ G ⩾ , 新
+
δ
′ ′ ′ ′
实例 I = (G ,λ ) ≜ Trans(I,k) 满足 I ∈ F(δ/2).
e e(∆−1)
证明: 设 Δ 和 Δ′分别表示图 G 和 G 的最大度数. 可以验证 ∆ = k(∆+1)−1. 注意到 ⩽ λ c (∆) ⩽ .
′
′
∆−2 (∆−2) 2
因此:

δ
( ) −2 1−
′
λ c (∆) (∆−1)(∆ −2) 2 (∗) 1 1 2
⩽ ⩽ 1− ⩽ ⩽ = ,
kλ c (∆ ) k(∆−2) 2 ∆ 4 4 1−δ
′
1− 1−
∆ 8 −4
δ
其中, (∗) 成立是由于伯努利不等式和 ∆ ⩾ 8/δ ⩾ 8 这一事实. 因此:

λ (1−δ)λ c (∆) ( δ )
λ = ⩽ ⩽ 1− λ c (∆ ). □
′
′
k k 2
12000
引理 8. 令 0 < δ < 1 为常数. 存在常数 C 2 (δ) = exp(O(1/δ)), 使得对于任意 I = (G,λ) ∈ F(δ), 如果 ∆ ⩾ logn,
δ
1
I 上 , 其中 Δ 是图 G 的最大度数, n 是图 G 的顶点数.
则 Glauber dynamics 的谱隙至少为
C 2 (δ)n
我们将引理 8 的证明推迟到第 4.1 节中进行, 本文下面证明引理 6.
( ⌈ 6 ⌉) ⌈ 6 ⌉
10 10
I = (G ,λ ) ≜ Trans I, logn logn -变换得到的实例, 其中 n
′
′
′
证明: 令 I = (G,λ) ∈ F(δ) 以及 是通过
δ 2 δ 2