pith. sign in

arxiv: 1905.03223 · v2 · pith:S37GCMBOnew · submitted 2019-05-08 · 🧮 math.PR

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

classification 🧮 math.PR
keywords chainedgemarkovmixingtimeaddedanalysisaway
0
0 comments X
read the original 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 $\Omega(n^2)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.