No cutoff for circulants : an elementary proof

• Autorzy: Abrams Aaron , Landau Henry , Pommersheim Jamie , Babson Eric , Landau Zeph

Identyfikatory

DOI

10.37190/0208-4147.00032

• Języki publikacji: EN

Abstrakty

EN

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).

Słowa kluczowe

EN

cutoff; mixing time; random walk; abelian groups

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2022
• Tom: Vol. 42, Fasc. 1
• Strony: 97--108
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Abrams Aaron

• Mathematics Department Washington and Lee University, Lexington, VA, 24450, USA

autor

Landau Henry

• AT&T Research Murray Hill, NJ 07974, USA

autor

Pommersheim Jamie

• Mathematics Department Reed College, Portland, OR 97202, USA

autor

Babson Eric

• Department of Mathematics University of California, Davis, CA 95616, USA

autor

Landau Zeph

• Department of Computer Science University of California, Berkeley CA 94706, USA

Bibliografia

• 1. D. Aldous and P. Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 (1986), 333-348.
• 2. D. Aldous and P. Diaconis, Strong uniform times and finite random walks, Adv. Appl. Math. 8 (1987), 69-97.
• 3. G.-Y. Chen and L. Saloff-Coste, The cutoff phenomenon for ergodic Markov processes, Electron. J. Probab. 13 (2008), 26-78.
• 4. P. Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. USA 93 (1996), 1659-1664.
• 5. P. Diaconis, Group Representations in Probability and Statistics, Inst. Math. Statist., Hayward, CA, 1988.
• 6. P. Diaconis and L. Saloff-Coste, Comparison techniques for random walks on finite groups, Ann. Probab. 21 (1993), 2131-2156.
• 7. P. Diaconis and L. Saloff-Coste, Moderate growth and random walk on finite groups, Geom. Funct. Anal. 4 (1994), 1-36.
• 8. J. Hermon and S. Olesker-Taylor, Cutoff for almost all random walks on abelian groups, arXiv:2102.02809v1 (2021).
• 9. J. Hermon and S. Olesker-Taylor, Geometry of random Cayley graphs of abelian groups, arXiv:2102.02801 (2021).
• 10. J. Hermon and S. Olesker-Taylor, Cutoff for almost all random walks on upper triangular matrices, arXiv:1911.02974v2 (2019).
• 11. R. Hough, Mixing and cut-off in cycle walks, Electron. J. Probab. 22 (2017), art. 90, 49 pp.
• 12. E. Lubetzky and A. Sly, Cutoff phenomena for random walks on random regular graphs, Duke Math. J. 153 (2010), 475-510.
• 13. D. Micciancio and O. Regev, Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput. 37 (2007), 267-302.
• 14. J. Salez, Cutoff for non-negatively curved Markov chains, arXiv:2102.02809v1 (2021).
• 15. L. Saloff-Coste, Random walks on finite groups, in: Probability on Discrete Structures, Encyclopaedia Math. Sci. 110, Springer, Berlin, 2004, 263-346.