No cutoff for circulants: an elementary proof
A. Abrams
E. Babson
H. Landau
Z. Landau
J. Pommersheim
Abstract:
We give an elementary proof of a result due to Diaconis and Saloff-Coste (1994) that families of symmetric simple random walks
on Cayley graphs of abelian groups with a bound on the number of
generators never have sharp cutoff.
Here convergence to the stationary
distribution is measured in the total variation norm. This is a situation of bounded degree and no expansion;
sharp cutoff (or the cutoff phenomenon) has been shown to occur in families such as random walks on a hypercube
(Diaconis, 1996) in which the degree is unbounded as well as on a random regular graph
where the degree is fixed, but there
is expansion (Diaconis and Saloff-Coste, 1993).
2010 AMS Mathematics Subject Classification:60B15, 05C81, 20K01.
Keywords and phrases: cutoff, mixing time, random walk, abelian groups.