Localization schemes: A framework for proving mixing bounds for Markov chains

We introduce a framework for proving mixing bounds for Markov chains which connects ideas from two seemingly unrelated techniques: the framework of spectral independence for the mixing of Markov chains on discrete space and the stochastic localization for mixing of Markov chains on log-concave measures and the discrete hypercube. In the center of our framework is the concept of a localization scheme which, to every probability measure on some space, assigns a martingale of probability measures which localize in space as time evolves. To every such scheme corresponds a Markov chain, and many chains can be derived through localization schemes. This viewpoint provides tools for deriving mixing bounds for Markov chains through the analysis of the corresponding localization process. Generalizations of concepts of spectral independence and entropic independence naturally arise from our definitions, and in particular we recover the main theorems in the spectral and entropic independence frameworks via simple martingale arguments bypassing the need to use the theory of high-dimensional expanders. We demonstrate the strength of our proposed framework by deriving new mixing bounds and giving simple proofs to many existing bounds in the recent literature. In particular, we (i) give the first O(nlogn) bound for mixing time of the hardcore model of arbitrary degree in the tree-uniqueness regime, via Glauber dynamics; (ii) give the first optimal mixing bounds for Ising models in the uniqueness regime under any external fields; (iii) prove a Kullback–Leibler (KL) divergence decay bound for log-concave sampling via the restricted Gaussian oracle, which achieves optimal mixing under any exp(n)-warm start; and (iv) prove a log-Sobolev inequality for near-critical ferromagnetic Ising models, recovering in a simple way a variant of a recent result by Bauerschmidt and Dagallier.