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

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

⌈ 6 ⌉
10 8
是 G 中顶点的数目. 通过变换, G 中的顶点数为 n = logn ·n. 通过命题 5, 我们知道如果 ∆ ⩾ , 那么 I = (G ,λ ) ∈
′
′
′
′
′
δ 2 δ
′ ′
F(δ/2). 记 δ = δ/2, Δ′表示 G 的最大度数. 我们声明以下结论:

⌈ ⌉
12000
∆ ⩾ logn ′ (8)
′
δ ′
1
通过引理 8, 可以知道 I 上 ′ Glauber dynamics 的谱隙至少为 , 其中 C 2 (δ ) > 0 是某个仅依赖于 δ = δ/2
′
′
C 2 (δ )n ′
′
′
的常数. 最后, 我们设置 C 1 (δ) = C 2 (δ ) = C 2 (δ/2) = exp(O(1/δ)).
⌈ 6 ⌉
10 2 20
现在证明公式 (8). 根据 k-变换的定义, 有 n = logn ·n ⩽ nlogn. 由于 0 < δ < 1, 以下不等式很容易验证:
′
δ 2 δ 2
( )
40 2 20
′
logn ⩾ log n· ·logn ⩾ logn .
δ δ 2
⌈ 6 ⌉
10
另外, 根据 k-变换的定义, 我们有 ∆ G ′ ⩾ logn . 结合上述不等式, 我们有:
δ 2
10 6 ( 25000 )( 40 ) 25000 (⋆) 12500 ⌈ 12000 ⌉
∆ ⩾ logn = logn ⩾ ·logn = logn ⩾ logn ,
′
′
′
′
δ 2 δ δ δ δ ′ δ ′
其中, 标 ( ⋆) 等式成立是因为 δ = 2δ . □
′
4.1 引理 8 的证明
12000
∆ ⩾ I = (G = (V,E),λ) ∈ F(δ), 其中
固定一个常数 0 < δ < 1 及一个最大度数为 logn 的硬核模型实例
δ
12000
n = |V| 是 G 中顶点的数量. 我们注意到 n ⩾ ∆ ⩾ . 令 µ = µ I 表示其吉布斯分布. 令 Ω = Ω I ⊆ {0,1} 表示 µ 的
V
δ
支撑集. 根据定义 1, 对于任意整数 1 ⩽ ℓ ⩽ n, 在分布 µ 上定义ℓ-block dynamics P ℓ . 具体地, P ℓ 从任意可行配置
X ∈ Ω 开始; 在每个更新步骤中, 它执行以下操作.
 
V
 
 
● 从大小为ℓ的   中均匀随机选择一个集合 S.
 
ℓ
● 从条件分布 µ X V\S 中重新采样 X S .
S
我们证明的起点是引理 9.
⌊ n ⌋
引理 ℓ = 350 −67/δ , 这意味着其弛豫时间为:
32e
9. 如果 , 那么 P ℓ 的谱隙至少为
67
t rel (P ℓ ) ⩽ 350 δ .
通过参考文献 [9,37] 中开发的局部到全局技术, 可以证明引理 9. 为了完整起见, 我们在附录 A 中证明引理 9.
使用 P = P 1 表示吉布斯分布 µ 的 Glauber 动力学 (1-block dynamics). 引理 9 给出了 block dynamics P ℓ 的谱隙, 其中
⌊ n ⌋
ℓ = . 我们通过比较 P ℓ 和 P 的弛豫时间来证明引理 8. 严格来说, 可以有引理 10.
32e
⌊ n ⌋
引理 10. 如果 ℓ = , 那么弛豫时间 t rel (P ℓ ) 和 t rel (P) 满足:
32e
3n 2
t rel (P) ⩽ t rel (P ℓ ).
ℓ
引理 10 的证明将推迟到第 4.2 节. 我们现在证明引理 8. 结合引理 9 和引理 10, Glauber dynamics 的弛豫时间
可以被界定为:

3n 2
70
t rel (P) ⩽ t rel (P ℓ ) ⩽ 300n·t rel (P ℓ ) ⩽ 350 δ n.
ℓ
1
这意味着 Glauber dynamics 的谱隙至少为 , 其中 C 4 (δ) = 350 δ = exp(O(1/δ)).
70
C 4 (δ)n
4.2 Block dynamics 和 Glauber dynamics 之间的比较 (引理 10 的证明)
⌊ n ⌋
ℓ = , 根据命题 3, block dynamics f : Ω → R, 结合引理 1 和引理 2, 可以得到
令 P ℓ 是不可约的. 对于任何
32e
以下不等式: