Faster Mixing of the Jerrum-Sinclair Chain

2025/04/03 by Chen, Xiaoyu, Feng, Weiming, Ju, Zhe +3
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2504.02740

Abstract

We show that the Jerrum-Sinclair Markov chain on matchings mixes in time \widetildeO(Δ² m) on any graph with n vertices, m edges, and maximum degree Δ, for any constant edge weight λ>0. For general graphs with arbitrary, potentially unbounded Δ, this provides the first improvement over the classic \widetildeO(n² m) mixing time bound of Jerrum and Sinclair (1989) and Sinclair (1992). To achieve this, we develop a general framework for analyzing mixing times, combining ideas from the classic canonical path method with the "local-to-global" approaches recently developed in high-dimensional expanders, introducing key innovations to both techniques.

Related

• Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
• Bounding Fastest Mixing
• Broder's Chain Is Not Rapidly Mixing
• Improved mixing rates of directed cycles by added connection
• Mixing times of Markov chains on a cycle with additional long range\n connections