24/08/2022, 17:00 — 18:00 — Online
Pietro Caputo, University Roma Tre
Rapid mixing of Gibbs samplers: Coupling, Spectral Independence, and Entropy Factorizations
We discuss some recent developments in the analysis of convergence to stationarity for the Gibbs sampler of general spin systems on arbitrary graphs. These are based on two recently introduced concepts: Spectral Independence and Block Factorization of Entropy. We show that the existence of a contractive coupling for a local Markov chain implies that the system is spectrally independent, and that if a system is spectrally independent then its entropy functional satisfies a general block factorization. As a corollary, we obtain new optimal bounds on the mixing time of a large class of sampling algorithms for the ferromagnetic Ising/Potts models in the so-called tree-uniqueness regime, including non-local chains such as the Swendsen-Wang dynamics. The methods apply to systems with hard constraints such as proper colorings and the hard core gas. We also discuss the entropy factorization for the uniform distribution over permutations and its role in the proof of a conjectured bound on the permanent of arbitrary matrices. Based on some recent joint works with Alexandre Bristiel, Antonio Blanca, Zongchen Chen, Daniel Parisi, Alistair Sinclair, Daniel Stefankovic, and Eric Vigoda.
