Abstract
We study the hard-core model defined on independent sets of an input graph where the independent sets are weighted by a parameter . For constant , previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree when . The threshold 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 . The running time of Weitz's algorithm is exponential in . Here we present an FPRAS for the partition function whose running time is . We analyze the simple single-site 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 , the mixing time of the Glauber dynamics is when . Our work complements that of Weitz which applies for constant whereas our work applies for all . 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 and .
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.