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

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

ACM-SIAM Symp. on Discrete Algorithms (SODA). Virtual: Society for Industrial and Applied Mathematics, 2021. 1558–1577. [doi: 10.
1137/1.9781611976465.95]
[30] Levin DA, Peres Y. Markov Chains and Mixing Times. 2nd ed., Providence: American Mathematical Society, 2017.
[31] Dyer M, Greenhill C, Ullrich M. Structure and eigenvalues of heat-bath Markov chains. Linear Algebra and Its Applications, 2014, 454:
57–71. [doi: 10.1016/j.laa.2014.04.018]
[32] Caputo P, Menz G, Tetali P. Approximate tensorization of entropy at high temperature. Annales de la Faculté des Sciences de Toulouse:
Mathématiques, 2015, 24(4): 691–716. [doi: 10.5802/afst.1460]
[33] Martinelli F, Sinclair A, Weitz D. The Ising model on trees: Boundary conditions and mixing time. In: Proc. of the 44th Annual IEEE
Symp. on Foundations of Computer Science, 2003. Cambridge: IEEE, 2003. 628–639. [doi: 10.1109/SFCS.2003.1238235]
2
[34] Lawler GF, Sokal AD. Bounds on the L spectrum for Markov chains and Markov processes: A generalization of Cheeger’s inequality.
Trans. of the American Mathematical Society, 1988, 309(2): 557–580. [doi: 10.2307/2000925]
[35] Sinclair A, Jerrum M. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation,
1989, 82(1): 93–133. [doi: 10.1016/0890-5401(89)90067-9]
[36] Joag-Dev K, Proschan F. Negative association of random variables with applications. The Annals of Statistics, 1983, 11(1): 286–295.
[doi: 10.1214/AOS/1176346079]
[37] Guo H, Mousa G. Local-to-global contraction in simplicial complexes. arXiv:2012.14317, 2021.

附录 A. Block dynamics 分析

在本附录中, 我们证明引理 9. 我们将在一般情形下证明以下引理.
引理 A1. 令 0 < δ < 1 是一个常数. 令 I = (G = (V,E),λ) ∈ F(δ) 是一个 n-顶点的硬核模型实例. 对于任何整数
66
⩽ ℓ ⩽ n, ℓ-block dynamics P ℓ 的谱隙至少为:
δ

( ) 67
ℓ δ
1−λ 2 (P ℓ ) ⩾ .
2n
12000 ⌊ n ⌋
引用引理 9 是引理 A1 的一个推论. 在引理 9 中, 实例 I ∈ F(δ) 满足 n ⩾ ∆ ⩾ 且 ℓ = . 可以验证
δ 32e
( ) 67/δ
66 2n
ℓ ⩾ . 因此, 弛豫时间最多为 ⩽ 350 67/δ . 现在我们来证明引理 A1. 首先引入一些定义. 设 µ 为硬核模型
δ ℓ
I 的吉布斯分布. 设 Ω Λ ⊂ V 和任意的 Λ σ Λ ∈ Ω Λ . 对于任意不同的
实例 为 µ 的支持. 固定任意的 上的可行配置
u,v ∈ V\Λ, 定义 u 对 v 的 (两两) 影响为:

σ Λ
Ψ (u,v) ≜ Pr X∼µ [X v = 1 | X u = 1,X Λ = σ Λ ]−Pr X∼µ [X v = 1 | X u = 0,X Λ = σ Λ ] (A.1)
µ
σ Λ σ Λ 是文献 ζ 0 ,ζ 1 ,...,ζ n−2 ∈ [0,1] 为一个实数
对于任意的 u ∈ V\Λ, 令 Ψ (u,u) = 0. 矩阵 Ψ µ [6] 中的影响矩阵. 令
µ
 
V
 
 
序列. 如果对于所有整数 0 ⩽ k ⩽ n−2, 对于所有属于   的子集 Λ, 对于在 Λ 上的任意可行配置 σ Λ ∈ Ω Λ , 都有
 
( ) k
λ max Ψ σ Λ
µ
⩽ ζ k , 那么分布 µ 被称为 (ζ 0 ,ζ 1 ,...,ζ n−2 ) -谱独立 [6] .
n−k −1
[8]
定理 A1 . 令 0 < δ < 1 为一个常数. 令 I ∈ F(δ) 为一个有 n 个顶点的硬核模型实例, 其吉布斯分布为 µ. 分布
{⌈ ⌉ }
32 1
,
µ 是 (ζ 0 ,ζ 1 ,...,ζ n−2 ) -谱独立的, 其中对于 0 ⩽ i ⩽ n−2 ζ i = min ,1 .
δ n−i−1
[9]
定理 A2 . 令 V 为一个大小为 n 的基底集合. 令 ζ 0 ,ζ 1 ,...,ζ n−2 ∈ [0,1] 为一个实数序列. 对于任何在 {0,1} 上的
V
(ζ 0 ,ζ 1 ,...,ζ n−2 ) -谱独立的, 那么对于任何 µ 上的谱隙至少为:
分布 µ, 只要该分布是 1≤ℓ≤n, ℓ-block dynamics P ℓ 在

∑ n−1
Γ k
k=n−ℓ
1−λ 2 (P ℓ ) ⩾ ∑ ,
n−1
Γ k
k=0
∏
k−1 1−ζ j
,
其中, 对于 k > 0 Γ k ≜ , Γ 0 ≜ 1.
j=0 1+ζ j