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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(4):1615−1633 [doi: 10.13328/j.cnki.jos.007533] [CSTR: 32375.14.jos.007533] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
吉布斯采样在临界点前的快速收敛

陈小羽 1 , 凤维明 2 , 尹一通 1 , 张昕渊 1

(计算机软件新技术全国重点实验室 (南京大学), 新基石科学实验室, 江苏 南京 210023)
1
2
(香港大学 计算与数据科学学院, 香港 999077)
通信作者: 尹一通, E-mail: yinyt@nju.edu.cn

摘 要: 吉布斯采样的临界行为是计算相变理论所关注的核心问题. 以硬核模型这一经典模型为例, 研究了吉布斯
采样在临界点前的快速收敛. 在该模型中, 给定一个最大度为 Δ≥3 的 n 顶点图 G 以及参数 λ≥0, 则图 G 中的每个
|S|
独立集 S 以正比于 λ 的概率被采样. 研究了实现这一采样的经典吉布斯采样算法——Glauber dynamics, 在临界条
Δ
件 λ<(Δ–1) Δ–1 /(Δ–2) 下, 证明了该采样过程的马尔可夫链具有渐进最优的谱隙为 Ω(1/n), 因此这一经典采样算法在
该临界点前始终快速收敛.吉布斯采样过程在临界点前的快速收敛是马尔可夫链蒙特卡洛 (MCMC) 理论中的一类
重要问题. 针对硬核模型上的这一问题, 此前已有若干依赖高等数学工具的证明. 为这个重要问题提供了一个简化
的组合证明, 引入计算复杂性归约的思想来分析采样过程的收敛速率.
关键词: 计算相变; 马尔可夫链蒙特卡洛方法; 硬核模型
中图法分类号: TP301

中文引用格式: 陈小羽, 凤维明, 尹一通, 张昕渊. 吉布斯采样在临界点前的快速收敛. 软件学报, 2026, 37(4): 1615–1633. http://
www.jos.org.cn/1000-9825/7533.htm
英文引用格式: Chen XY, Feng WM, Yin YT, Zhang XY. Rapid Convergence of Gibbs Sampling Before Critical Point. Ruan Jian Xue
Bao/Journal of Software, 2026, 37(4): 1615–1633 (in Chinese). http://www.jos.org.cn/1000-9825/7533.htm

Rapid Convergence of Gibbs Sampling Before Critical Point
2
1
1
CHEN Xiao-Yu , FENG Wei-Ming , YIN Yi-Tong , ZHANG Xin-Yuan 1
1
(New Cornerstone Science Laboratory, State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023, China)
2
(School of Computing & Data Science, The University of Hong Kong, Hong Kong 999077, China)
Abstract: The critical behavior of Gibbs sampling is a central issue in the theory of computational phase transitions. This study takes the
hard-core model, a classical model, as an example to study the rapid convergence of Gibbs sampling before the critical point. In this
model, given an n-vertex graph G with a maximum degree of Δ≥3 and a parameter λ≥0, each independent set S in graph G is sampled
|S|
with a probability proportional to λ . This study investigates the canonical Gibbs sampling algorithm, Glauber dynamics, which
Δ
implements this sampling. Under the critical condition λ<(Δ–1) Δ–1 /(Δ–2) , it is proven that the Glauber dynamics has an asymptotically
optimal spectral gap of Ω(1/n), thus establishing that this classical sampling algorithm mixes rapidly up to the critical point. The rapid
convergence of the Gibbs sampling process before the critical point is an important issue in Markov chain Monte Carlo (MCMC) theory.
For this problem on the hard-core model, several proofs relying on advanced mathematical tools have been previously provided. This study
offers a simplified combinatorial proof for this significant problem, introducing the idea of reductions from computational complexity to
analyze the convergence rate of the sampling process.
Key words: computational phase transition; Markov chain Monte Carlo (MCMC) method; hardcore model

1 引 言

吉布斯分布 (Gibbs distribution) 是一类由局部约束所描述的高维概率分布. 在计算机科学、概率论、统计物

* 收稿时间: 2025-03-01; 修改时间: 2025-08-23; 采用时间: 2025-08-27; jos 在线出版时间: 2025-12-10
CNKI 网络首发时间: 2025-12-11