TY - GEN

T1 - On Mixing of Markov Chains

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

AU - Blanca, Antonio

AU - Caputoz, Pietro

AU - Chen, Zongchen

AU - Parisiy, Daniel

AU - Stefankovic, Daniel

AU - Vigoda, Eric

N1 - Publisher Copyright:
Copyright © 2022 by SIAM.

PY - 2022

Y1 - 2022

N2 - For general spin systems, we prove that a contractive coupling for an arbitrary local Markov chain implies optimal bounds on the mixing time and the modified log-Sobolev constant for a large class of Markov chains including the Glauber dynamics, arbitrary heat-bath block dynamics, and the Swendsen-Wang dynamics. This reveals a novel connection between probabilistic techniques for bounding the convergence to stationarity and analytic tools for analyzing the decay of relative entropy. As a corollary of our general results, we obtain O(n log n) mixing time and Ω(1/n) modified log-Sobolev constant of the Glauber dynamics for sampling random q-colorings of an n-vertex graph with constant maximum degree Δ when q > (11/6-?0)Δ for some fixed ?0 > 0. We also obtain O(log n) mixing time and Ω(1) modified log-Sobolev constant of the Swendsen-Wang dynamics for the ferromagnetic Ising model on an n-vertex graph of constant maximum degree when the parameters of the system lie in the tree uniqueness region. At the heart of our results are new techniques for establishing spectral independence of the spin system and block factorization of the relative entropy. On one hand we prove that a contractive coupling of any local Markov chain implies spectral independence of the Gibbs distribution. On the other hand we show that spectral independence implies factorization of entropy for arbitrary blocks, establishing optimal bounds on the modified log-Sobolev constant of the corresponding block dynamics.

AB - For general spin systems, we prove that a contractive coupling for an arbitrary local Markov chain implies optimal bounds on the mixing time and the modified log-Sobolev constant for a large class of Markov chains including the Glauber dynamics, arbitrary heat-bath block dynamics, and the Swendsen-Wang dynamics. This reveals a novel connection between probabilistic techniques for bounding the convergence to stationarity and analytic tools for analyzing the decay of relative entropy. As a corollary of our general results, we obtain O(n log n) mixing time and Ω(1/n) modified log-Sobolev constant of the Glauber dynamics for sampling random q-colorings of an n-vertex graph with constant maximum degree Δ when q > (11/6-?0)Δ for some fixed ?0 > 0. We also obtain O(log n) mixing time and Ω(1) modified log-Sobolev constant of the Swendsen-Wang dynamics for the ferromagnetic Ising model on an n-vertex graph of constant maximum degree when the parameters of the system lie in the tree uniqueness region. At the heart of our results are new techniques for establishing spectral independence of the spin system and block factorization of the relative entropy. On one hand we prove that a contractive coupling of any local Markov chain implies spectral independence of the Gibbs distribution. On the other hand we show that spectral independence implies factorization of entropy for arbitrary blocks, establishing optimal bounds on the modified log-Sobolev constant of the corresponding block dynamics.

UR - http://www.scopus.com/inward/record.url?scp=85126694182&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85126694182&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85126694182

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 3670

EP - 3692

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

Y2 - 9 January 2022 through 12 January 2022

ER -