Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems
share
We present a simple combinatorial framework for establishing approximate tensorization of variance and entropy in the setting of spin systems (a.k.a. undirected graphical models) based on balanced separators of the underlying graph. Such approximate tensorization results immediately imply as corollaries many important structural properties of the associated Gibbs distribution, in particular rapid mixing of the Glauber dynamics for sampling. We prove approximate tensorization by recursively establishing block factorization of variance and entropy with a small balanced separator of the graph. Our approach goes beyond the classical canonical path method for variance and the recent spectral independence approach, and allows us to obtain new rapid mixing results. As applications of our approach, we show that: 1. On graphs of treewidth t, the mixing time of the Glauber dynamics is n^O(t), which recovers the recent results of Eppstein and Frishberg with improved exponents and simpler proofs; 2. On bounded-degree planar graphs, strong spatial mixing implies Õ(n) mixing time of the Glauber dynamics, which gives a faster algorithm than the previous deterministic counting algorithm by Yin and Zhang.
READ FULL TEXT