Rapid Convergence of Gibbs Sampling Before Critical Point
Author:
Affiliation:

Clc Number:

TP301

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

陈小羽,凤维明,尹一通,张昕渊.吉布斯采样在临界点前的快速收敛.软件学报,2026,37(4):1615-1633

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 01,2025
  • Revised:August 23,2025
  • Adopted:
  • Online: December 10,2025
  • Published: April 06,2026
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063