Gerencsér Balázs (Rényi Intézet és ELTE): Markov chain speedup on the cycle by a single random edge and a non-reversible modification

We are interested in the better understanding of mixing time improvement possibilities for Markov chains on the cycle, considering the ones with uniform stationary distribution. For any reversible Markov chain, it is well known that the mixing time is $\Omega(n^{^2})$.

Two natural extensions are combined, first by dropping the technical condition of reversibility, second by allowing more edges as it is also motivated by certain random graph models. However, for the latter, we are very conservative: we already stop at one extra edge.

Interestingly, a non-trivial speedup already appears, the mixing time can drop to $\Theta(n^{3/2})$, provided that the added edge is appropriate in some sense.