  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$ additional edges, where $\gamma < 1$. We find that
the mixing times of reversible Markov chains properly interpolate between the
mixing times of the cycle with no added edges and of the cycle with $cn$ added
edges (which is in turn a Small World Network model). In the case of
non-reversible Markov-chains, a considerable gap remains between lower and
upper bounds, but simulations give hope to experience a significant speedup
compared to the reversible case.
