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

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

′
′
′
′
∀σ ∈ Ω , f (σ ) = f (g(σ )) (20)
′
于是, f = f ◦g. 我们将证明以下两个性质成立, 这意味着引理 15 成立.
′
● E P ′ ( f , f ) = E P lazy ( f, f).
′
′
● Var µ ′ ( f ) = Var µ ( f).
′
根据公式 (4) 中的定义, 我们有:

1 ∑
′
′
E P ′ ( f , f ) = µ (σ )P (σ ,τ )( f (σ )− f (τ )) 2
′
′
′
′
′
′
′
′
′
2
σ ′ ,τ ′ ∈Ω ′

( ) 1 ∑ ∑ 2
′
′
′
′
′
′
′
′
′
′
g将Ω 映射到Ω = µ (σ )P (σ ,τ )( f (σ )− f (τ ))
2
σ,τ∈Ω σ ′ ∈g −1 (σ)
τ ′ ∈g −1 (τ)

1 ∑ ∑
(根据f 的定义) = µ (σ )P (σ ,τ )( f (g(σ ))− f (g(τ ))) 2
′
′
′
′
′
′
′
′
2
σ,τ∈Ω σ ′ ∈g −1 (σ)
τ ′ ∈g −1 (τ)
1 ∑ ∑ ∑
′
′
′
′
= ( f(σ)− f(τ)) 2 µ (σ ) P (σ ,τ )
′
2
σ,τ∈Ω σ ′ ∈g −1 (σ) τ ′ ∈g −1 (τ)

1 ∑
2
(根据公式(18)和(19)) = µ(σ)P lazy (σ,τ)(f(σ)− f(τ)) = E P lazy ( f, f).
2
σ,τ∈Ω
类似地, 对于方差, 根据公式 (3), 我们有:

1 ∑
[ ] 2
′
Var µ ′ f = µ (σ )µ (τ )( f (σ )− f (τ ))
′
′
′
′
′
′
′
′
2
σ ′ ,τ ′ ∈Ω ′
1 ∑ ∑ ∑
′
= ( f(σ)− f(τ)) 2 µ (σ ) µ (τ )
′
′
′
2
σ,τ∈Ω σ ′ ∈g −1 (σ) τ ′ ∈g −1 (τ)
1 ∑
2
= µ(σ)µ(τ)( f(σ)− f(τ)) = Var µ [ f]. □
2
σ,τ∈Ω
6 总 结
将点替换成 k-团是传统计算复杂性规约证明中常见的 gadget. 本文通过在图上考虑这种 gadget 证明了 Glauber
dynamics (吉布斯采样算法) 在硬核模型临界点前的快速收敛. 类似的结果此前已知的证明需要用到高等数学工具
且都很复杂. 本文给出了一个简单且初等的证明, 为硬核模型上 Glauber dynamics 的收敛现象提供了一种新的理
解方式.
目前, 我们的方法暂时无法推广至 Ising 模型等其他吉布斯分布, 因为该证明使用了一个关键性质, 即硬核模
型进行 k-变换 (见定义 3) 之后仍然是硬核模型. 对于 Ising 模型, 这一性质并不成立. 如何推广当前的方法, 为一般
的吉布斯分布的高效采样的临界行为给出组合证明, 是一个未来值得探索的方向.
References
[1] Chen XY, Feng WM. Rapid mixing via coupling independence for spin systems with unbounded degree. arXiv:2407.04672, 2024.
[2] Chen XY, Feng WM, Yin YT, Zhang XY. Rapid mixing of Glauber dynamics via spectral independence for all degrees. In: Proc. of the
62nd IEEE Annual Symp. on Foundations of Computer Science (FOCS). Denver: IEEE, 2022. 137–148. [doi: 10.1109/FOCS52979.2021.
00022]
[3] Chen YS, Eldan R. Localization schemes: A framework for proving mixing bounds for Markov chains (extended abstract). In: Proc. of
the 63rd IEEE Annual Symp. on Foundations of Computer Science (FOCS). Denver: IEEE, 2022. 110–122. [doi: 10.1109/FOCS54457.
2022.00018]
[4] Mézard M, Montanari A. Information, Physics, and Computation. Oxford: Oxford University Press, 2009.
[5] Anari N, Jain V, Koehler F, Pham HT, Vuong TD. Entropic independence: Optimal mixing of down-up random walks. In: Proc. of the