Analysis of a non-reversible Markov chain speedup by a single edge. (4th June 2023)

• Record Type: Journal Article
• Authors: Gerencsér, Balázs
• Is Part Of: Journal of applied probability. Volume 60:Number 2(2023)
• Page Start: 642
• Page End: 660
• Publication Date: 2023-06-04
• Subjects: Mixing time -- random edge -- drift; 60J10 -- 37A25; 519.2
• DOI: 10.1017/jpr.2022.88
• Languages: English
• ISSNs: 0021-9002

Abstract

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 $\Omega(n^2)$ .