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

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

⌈ ⌉
32 66 66
C ≜ n ⩾ ℓ ⩾ ⩾ 2C, 否则, 如果不存在这样的ℓ, 引理显
证明: 设 . 固定整数ℓ, 使得 ⩽ ℓ ⩽ n. 我们假设
δ δ δ
(n−k −C)(n−k −C +1)...(n−k +C −1)
然成立. 通过一些计算, 可以验证对于任意 1 ⩽ k ⩽ n−1, 总是有 Γ k = =
(n−C)(n+1−C)...(n−1+C)
 / 
(n−1)−k +C (n−1)+C
   
    . 因此, 结合定理 A1 和定理 A2, 有:

  
   
2C 2C
∑ n−1
32
( ) 2C+1 ( ) 2C+1 ( ) 2⌈ σ ⌉ +1 ( ) 67
C ∏ δ
Γ k (⋆) ℓ +k ℓ −C ℓ ℓ ℓ
k=n−ℓ
1−λ 2 (P ℓ ) ⩾ ∑ = ⩾ ⩾ ⩾ ⩾ ,
n−1 n+k n−C 2n 2n 2n
Γ k k=−C
k=0
   
66 ∑ N−1  j  N 
n ⩾ ℓ ⩾ ⩾ 2C 这一事实, 并且标       中获得.
 

其中, 我们利用了 ( ⋆) 等式可以从方程   =    □
 
δ j=0 k k +1
附录 B. 小度数实例的分析
在本节中, 我们证明引理 5.
8
∆ ⩽ 表示图 G 的最大度数. 不
证明: 令 I = (G = (V,E),λ) ∈ F(δ) 为一个硬核模型实例, 其吉布斯分布为 µ. 令
δ
1 1
失一般性, 假设 ⩽ λ ⩽ λ c (∆). 如果 λ < , 那么 I 满足 Dobrushin 条件, 根据命题 1, 引理成立. 如果对于任意
2∆ 2∆
Λ
Λ ⊆ V , 任意合法的 σ ∈ {0,1} , 任意 v ∈ V\Λ, 都有:

σ
∀c ∈ Ω σ V\Λ , µ (c) ⩾ b,
v
1
I 满足 λ ⩾ , 由于硬核模型实例的自规约性, 可以取顶点 v 两跳邻域上的最坏
那么我们说 b-边缘有界. 注意到
2∆
( ) ( )
1 b 2 1 ( ) 66
3
情况, 从而说明 I 在 b = Θ 时是 b-边缘有界的. 令 θ = = Θ = Ω δ . 不失一般性, 我们假设 n ⩾ . 否
∆ 12∆ ∆ 3 θδ
( ) ( )
66 ∆ 3 1
n < = O ⩽ O . 在这种情况下, 我们使用命题 I 上 Glauber 动力学的谱间隙至少为:
则 2, 在
θδ δ δ 4
( ) O(1/δ)
1 1
66
′
(5n) = , C = .
− δ
0
C (δ)n δ
′
0
66
θ < 1 n ⩾ ℓ ⩾ θn ⩾ . 根据引理 µ 上ℓ-block dynamics 的
考虑 µ 上的ℓ-block dynamics, 其中 ℓ = ⌈θn⌉. 因为 , A1,
δ
( ) 67/δ ( )67/δ
ℓ θ [9]
谱隙至少为 ⩾ . 这意味着 Gibbs 分布 µ 满足方差的均匀块分解 (uniform block factorization) , 其中常
2n 2
( ) 67/δ
ℓ 2
数 C UB = = (1/δ) O(1/δ) . 结合文献 [9] 中的引理和事实, 可以证明 Glaube dynamics 的谱隙至少为:
n θ
( ) O(1/δ)
b 4 1 1
= ,其中C = .
′′
18log(1/b)C UB n C (δ)n 0 δ
′′
0
这样就证明了引理 5. □

作者简介
陈小羽, 博士, 主要研究领域为理论计算机, 随机算法, 近似计数与采样.
凤维明, 博士, 助理教授, CCF 专业会员, 主要研究领域为理论计算机, 随机算法, 近似计数与采样.
尹一通, 博士, 教授, 博士生导师, CCF 高级会员, 主要研究领域为随机算法, 数据结构, 并行算法.
张昕渊, 博士生, 主要研究领域为理论计算机, 随机算法, 近似计数与采样.