| 摘要: |
| 吉布斯采样的临界行为是计算相变理论所关注的核心问题. 以硬核模型这一经典模型为例, 研究了吉布斯采样在临界点前的快速收敛. 在该模型中, 给定一个最大度为Δ≥3的n顶点图G以及参数λ≥0, 则图G中的每个独立集S以正比于λ|S|的概率被采样. 研究了实现这一采样的经典吉布斯采样算法——Glauber dynamics, 在临界条件λ<(Δ–1)Δ–1/(Δ–2)Δ下, 证明了该采样过程的马尔可夫链具有渐进最优的谱隙为Ω(1/n), 因此这一经典采样算法在该临界点前始终快速收敛.吉布斯采样过程在临界点前的快速收敛是马尔可夫链蒙特卡洛(MCMC) 理论中的一类重要问题. 针对硬核模型上的这一问题, 此前已有若干依赖高等数学工具的证明. 为这个重要问题提供了一个简化的组合证明, 引入计算复杂性归约的思想来分析采样过程的收敛速率. |
| 关键词: 计算相变 马尔可夫链蒙特卡洛方法 硬核模型 |
| DOI：10.13328/j.cnki.jos.007533 |
| 分类号:TP301 |
| 基金项目: |
|
| Rapid Convergence of Gibbs Sampling Before Critical Point |
|
CHEN Xiao-Yu1, FENG Wei-Ming2, YIN Yi-Tong1, ZHANG Xin-Yuan1
|
|
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 with a probability proportional to λ|S|. 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 |
