Mixing times of Markov chains on a cycle with additional long range connections

Balázs Gerencsér

We develop Markov chain mixing time estimates for a class of Markov chains with restricted transitions. We assume transitions may occur along a cycle of $n$ nodes and on $n^{\gamma }$ addi…