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.