Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

preprint2016arXivOpen access

Abstract

We study the hard-core model defined on independent sets of an input graph where the independent sets are weighted by a parameter λ>0λ>0. For constant ΔΔ, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree ΔΔ when λ<λc(Δ)λ< λ_c(Δ). The threshold λc(Δ)λ_c(Δ) is the critical point for the phase transition for uniqueness/non-uniqueness on the infinite ΔΔ-regular trees. Sly (2010) showed that there is no FPRAS, unless NP=RP, when λ>λc(Δ)λ>λ_c(Δ). The running time of Weitz's algorithm is exponential in log⁡(Δ)\log(Δ). Here we present an FPRAS for the partition function whose running time is O∗(n2)O^*(n^2). We analyze the simple single-site Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant Δ0Δ_0 such that for all graphs with maximum degree Δ≥Δ0Δ\geqΔ_0 and girth ≥7\geq 7, the mixing time of the Glauber dynamics is O(nlog⁡(n))O(n\log(n)) when λ<λc(Δ)λ<λ_c(Δ). Our work complements that of Weitz which applies for constant ΔΔ whereas our work applies for all Δ≥Δ0Δ\geq Δ_0. We utilize loopy BP (belief propagation), a widely-used inference algorithm. 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 converges, after a short burn-in period, 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\geq 6 and λ<λc(Δ)λ<λ_c(Δ).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.