UNIVERSITY
OF WROCŁAW
 
Main Page
Contents
Online First
General Information
Instructions for authors


VOLUMES
43.2 43.1 42.2 42.1 41.2 41.1 40.2
40.1 39.2 39.1 38.2 38.1 37.2 37.1
36.2 36.1 35.2 35.1 34.2 34.1 33.2
33.1 32.2 32.1 31.2 31.1 30.2 30.1
29.2 29.1 28.2 28.1 27.2 27.1 26.2
26.1 25.2 25.1 24.2 24.1 23.2 23.1
22.2 22.1 21.2 21.1 20.2 20.1 19.2
19.1 18.2 18.1 17.2 17.1 16.2 16.1
15 14.2 14.1 13.2 13.1 12.2 12.1
11.2 11.1 10.2 10.1 9.2 9.1 8
7.2 7.1 6.2 6.1 5.2 5.1 4.2
4.1 3.2 3.1 2.2 2.1 1.2 1.1
 
 
WROCŁAW UNIVERSITY
OF SCIENCE AND
TECHNOLOGY

Contents of PMS, Vol. 42, Fasc. 1,
pages 97 - 108
DOI: 10.37190/0208-4147.00032
Published online 20.5.2022
 

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.

References


D. Aldous and P. Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 (1986), 333-348.

D. Aldous and P. Diaconis, Strong uniform times and finite random walks, Adv. Appl. Math. 8 (1987), 69-97.

G.-Y. Chen and L. Saloff-Coste, The cutoff phenomenon for ergodic Markov processes, Electron. J. Probab. 13 (2008), 26-78.

P. Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. USA 93 (1996), 1659-1664.

P. Diaconis, Group Representations in Probability and Statistics, Inst. Math. Statist., Hayward, CA, 1988.

P. Diaconis and L. Saloff-Coste, Comparison techniques for random walks on finite groups, Ann. Probab. 21 (1993), 2131-2156.

P. Diaconis and L. Saloff-Coste, Moderate growth and random walk on finite groups, Geom. Funct. Anal. 4 (1994), 1-36.

J. Hermon and S. Olesker-Taylor, Cutoff for almost all random walks on abelian groups, arXiv:2102.02809v1 (2021).

J. Hermon and S. Olesker-Taylor, Geometry of random Cayley graphs of abelian groups, arXiv:2102.02801 (2021).

J. Hermon and S. Olesker-Taylor, Cutoff for almost all random walks on upper triangular matrices, arXiv:1911.02974v2 (2019).

R. Hough, Mixing and cut-off in cycle walks, Electron. J. Probab. 22 (2017), art. 90, 49 pp.

E. Lubetzky and A. Sly, Cutoff phenomena for random walks on random regular graphs, Duke Math. J. 153 (2010), 475-510.

D. Micciancio and O. Regev, Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput. 37 (2007), 267-302.

J. Salez, Cutoff for non-negatively curved Markov chains, arXiv:2102.02809v1 (2021).

L. Saloff-Coste, Random walks on finite groups, in: Probability on Discrete Structures, Encyclopaedia Math. Sci. 110, Springer, Berlin, 2004, 263-346.

Download:    Abstract    Full text