Analysis of a non-reversible Markov chain speedup by a single edge. (4th June 2023) - Gerencsér, Balázs
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 a 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^2)$ .