2020/11/04 by Zongchen Chen, Kuikui Liu, Chen, Zongchen +3 · 9 citations
Mathematics · Biochemistry, Genetics and Molecular Biology · #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Protein Structure and Dynamics
paper · pdf · doi:10.48550/arxiv.2011.02075
We prove an optimal mixing time bound on the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al. (2020) and shows O(nlogn) mixing time on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity λ, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree Δ when λ<λc(Δ) where λc(Δ) is the critical point for the uniqueness/non-uniqueness phase transition on the Δ-regular tree. More generally, for any antiferromagnetic 2-spin system we prove O(nlogn) mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain O(nlogn) mixing for q-colorings of triangle-free graphs of maximum degree Δ when the number of colors satisfies q > αΔ where α≈ 1.763, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges.