Abstract
Considering a Markov chain defined on a cycle, near-quadratic improvement of mixing is shown when only a subtle perturbation is introduced to the structure and non-reversible transition probabilities are used. More precisely, a mixing time of O(n k+2 k+1) can be achieved by adding k random edges to the cycle, keeping k fixed while n→∞. The construction builds upon a biased random walk along the cycle.

This publication has 13 references indexed in Scilit: