The Cut-Off Phenomenon in Random Walks on Finite Groups

2015/04/21 by J.P. McCarthy, McCarthy, J. P.
Mathematics · #60B15 #Advanced Combinatorial Mathematics #FOS: Mathematics #Geometric and Algebraic Topology #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1504.05387

openalex publication_date 2015/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

How many shuffles are needed to mix up a deck of cards? This question may be answered in the language of a random walk on the symmetric group, S₅₂. This generalises neatly to the study of random walks on finite groups, themselves a special class of Markov chains. Ergodic random walks exhibit nice limiting behaviour, and both the quantitative and qualitative aspects of the convergence to this limiting behaviour is examined. A particular qualitative behaviour, the cut-off phenomenon, occurs in many examples. For random walks exhibiting this behaviour, after a period of time, convergence to the limiting behaviour is abrupt.

Related

• Cutoff Phenomenon and Limiting Profile of a Random Walk on the Symmetric Group
• Cutoff for non-backtracking random walks on sparse random graphs
• Cutoff for random walks on dihedral groups
• Random walk on sparse random digraphs
• The predicable dance of random walk: local limit theorems on finitely-generated abelian groups