Nima Anari, Stanford University

Abstract

I will introduce a notion of expansion for weighted simplicial complexes called entropic independence. This notion is motivated by the desire to obtain tight mixing time bounds for natural discrete Markov chains. As is widely known in Markov Chain analysis, spectral analysis is often lossy (by polynomial factors) when the state space is exponentially large. Instead, Modified Log-Sobolev Inequalities (MLSI), which characterize the rate of entropy decay, are powerful enough to often yield a tight mixing time bound. We show how to obtain entropic independence, and as a consequence, tight MLSI and mixing time bounds, for a range of natural chains/distributions. We recover earlier known results about mixing of basis-exchange walks on matroids, and obtain new tight mixing time bounds for several others: examples include monomer dynamics in monomer-dimer systems, variants of Glauber dynamics in high-temperature Ising models and high-temperature hardcore models, and down-up walks for non-symmetric determinantal point processes. Our framework allows an easy way of lifting the widely successful notion of spectral independence to entropic independence, yielding, in many cases with no extra effort, tight MLSI and mixing times from existing spectral analyses.
Time-permitting, I will discuss an additional application of entropic independence involving analogs of the notion of isotropy and phenomena akin to the KLS conjecture for discrete strongly Rayleigh distributions.
Based on joint works with: Vishesh Jain, Frederic Koehler, Yang P. Liu, Huy Tuan Pham, Thuy-Duong Vuong.

[Video]