Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model

We study the hard-core (gas) model defined on independent sets of an input graph where the independent sets are weighted by a parameter (aka fugacity) λ > 0. For constant Δ, the previous work of Weitz [Proceedings of STOC, 2006, pp. 140-149] established an FPTAS for the partition function for graphs of maximum degree Δ when λ < λc(Δ). Sly [Proceedings of FOCS, 2010, pp. 287-296] showed that there is no FPRAS, unless NP=RP, when λ > λc(Δ). The threshold λc(Δ) is the critical point for the statistical physics phase transition for uniqueness/nonuniqueness on the infinite Δ-regular tree. The running time of Weitz's algorithm is exponential in log Δ. Here we present an FPRAS for the partition function whose running time is O^∗(n²). We analyze the simple single-site Markov chain known as the Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant Δ₀ such that for all graphs with maximum degree Δ ≥ Δ₀ and girth ≥ 7 (i.e., no cycles of length ≤ 6), the mixing time of the Glauber dynamics is O(n log n) when λ < λc(Δ). Our work complements that of Weitz, which applies for small constant Δ, whereas our work applies for all Δ at least a sufficiently large constant Δ₀. (This includes Δ depending on n = |V |.) Our proof utilizes loopy belief propagation (BP) which is a widely used algorithm for inference in graphical models. A novel aspect of our work is using the principal eigenvector for the BP operator to design a distance function which contracts in expectation for pairs of states that behave like the BP fixed point. We also prove that the Glauber dynamics behaves locally like loopy BP. As a byproduct we obtain that the Glauber dynamics, after a short burn-in period, converges close to the BP fixed point, and this implies that the fixed point of loopy BP is a close approximation to the Gibbs distribution. Using these connections we establish that loopy BP quickly converges to the Gibbs distribution when the girth ≥ 6 and λ < λc(Δ).