  We analyze the absolute spectral gap of Markov chains on graphs obtained from
a cycle of $n$ vertices and perturbed only at approximately $n^{1/\rho}$ random
locations with an appropriate, possibly sparse, interconnection structure.
Together with a strong asymmetry along the cycle, the gap of the resulting
chain can be bounded inversely proportionally by the longest arc length (up to
logarithmic factors) with high probability, providing a significant mixing
speedup compared to the reversible version.
