Analysis of a non-reversible Markov chain speedup by a single edge

2019/05/08 by Balázs Gerencsér, Gerencsér, Balázs
Computer Science · Mathematics · #37A25 #60J10 #Algorithms and Data Compression #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1905.03223

openalex publication_date 2019/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a Markov chain example where non-reversibility and an added edge jointly improve mixing time: when a random edge is added to a cycle of n vertices and a Markov chain with a drift is introduced, we get mixing time of O(n^3/2) with probability bounded away from 0. If only one of the two modifications were performed, the mixing time would stay Ω(n²).

Related

• Mixing on the cycle with constant size perturbation
• Improved mixing rates of directed cycles by added connection
• Mixing times of Markov chains on a cycle with additional long range\n connections
• Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
• Mixing time bounds for edge flipping on regular graphs