Cutoff phenomenon

Intuition [Beginner]

Many random walks share a surprising property: for a long time the walk stays far from uniformly random, then it suddenly becomes close to uniform. The transition happens in a very narrow window of steps. This sharp transition is called the cutoff phenomenon.

Imagine a light switch rather than a dimmer. The walk is "off" (far from uniform) for thousands of steps, then within a few dozen more steps it flips "on" (close to uniform). The number of steps where the switch happens depends on the size of the group, growing logarithmically.

The cutoff phenomenon was first identified by Aldous and Diaconis in 1986. They showed it occurs for random transpositions on the symmetric group, for random walks on the hypercube, and for many other natural chains. Not every random walk exhibits cutoff — some converge gradually — but the ones that do share a structural feature: the mixing time is controlled by a single "bottleneck" representation.

Visual [Beginner]

A diagram showing total variation distance versus number of steps for three scenarios: a walk with cutoff (sharp drop), a walk without cutoff (gradual decay), and a walk with late cutoff. The cutoff curve looks like a step function; the non-cutoff curve is a smooth exponential decay.

The key visual signature of cutoff is the step-function shape: the total variation distance stays near 1, then drops rapidly to near 0 within a narrow window.

Worked example [Beginner]

Consider the lazy random walk on the hypercube $\{0,1{\}}^n$ (a string of $n$ bits). At each step, choose a random coordinate and flip it with probability $1/2$ (or leave it unchanged with probability $1/2$).

For $n=3$: the hypercube has $2^3=8$ vertices. Starting from $(0,0,0)$:

Step 1. After 1 step: the walk has moved to one of $(1,0,0)$, $(0,1,0)$, $(0,0,1)$, or stayed at $(0,0,0)$, each with probability $1/4$ for the first three and $1/4+1/6=$ ... actually, with the lazy step, choose a random coordinate (3 choices, each with probability $1/3$), then flip it with probability $1/2$. So the probability of staying put is $\frac{1}{3}\cdot \frac{1}{2}\cdot 3=1/2$ and the probability of moving to each of the 3 neighbours is $1/6$.

Step 2. After 5 steps, the distribution is spread across most vertices but still concentrated near the starting point. The total variation distance from uniform is approximately $0.4$.

Step 3. After 12 steps ($=n\log n\approx 3\times 1.1\approx 3.3$ for $n=3$, but more steps needed for a small cube), the distribution is close to uniform.

What this tells us: for large $n$, the cutoff happens at $\frac{1}{2}n\log n$ steps. Before this threshold, the walk is far from uniform; after it, the walk is close. The window around the cutoff has width $O(n)$.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $(G_n)$ be a family of finite groups with $|G_n|\to \infty$. For each $n$, let $Q_n$ be a probability measure on $G_n$ driving a random walk, and let $t_{\mathrm{mix}}^{(n)}(\epsilon )=\min \{k:\Vert Q_n^{\ast k}-U_n{\Vert }_{\mathrm{TV}}\le \epsilon \}$ be the mixing time with threshold $\epsilon$.

Definition (Cutoff). The family $(G_n,Q_n)$ exhibits cutoff if there exists a sequence $t_n\to \infty$ and a window $w_n=o(t_n)$ such that

$$\underset{n\to \infty }{\lim }\Vert Q_n^{\ast (t_n-c{w}_n)}-U_n{\Vert }_{\mathrm{TV}}=1\text{for all }c>0$$

and

$$\underset{n\to \infty }{\lim }\Vert Q_n^{\ast (t_n+c{w}_n)}-U_n{\Vert }_{\mathrm{TV}}=0\text{for all }c>0.$$

Equivalently, cutoff holds if $t_{\mathrm{mix}}^{(n)}(\epsilon )/t_{\mathrm{mix}}^{(n)}(1-\epsilon )\to 1$ for all $0<\epsilon <1/2$.

Definition (Cutoff window). The cutoff window is the smallest $w_n$ for which the above holds. If $w_n=O(1)$, the cutoff is sharp; if $w_n=O(\sqrt{t_n})$, the cutoff follows a standard diffusion scaling.

Counterexamples to common slips

• Cutoff is a property of families, not individual chains. A single random walk on a fixed group does not "have cutoff." Cutoff describes asymptotic behaviour as the group size grows.
• Cutoff does not mean TV reaches exactly 0. The TV distance never reaches 0 in finite time (for an aperiodic chain). Cutoff means the TV distance drops from near 1 to near 0 in a narrow window.
• Spectral gap alone does not determine cutoff. Two chains with the same spectral gap can have different cutoff behaviour. The full spectrum, not just the gap, controls the cutoff profile.

Key theorem with proof [Intermediate+]

Theorem (Cutoff for random transpositions — Diaconis-Shahshahani 1981). Consider the random transposition walk on $S_n$: at each step, choose two positions uniformly at random and swap the cards in those positions. This family exhibits cutoff at time $t_n=\frac{1}{2}n\log n$ with window $w_n=n$. Concretely, for $k=\frac{1}{2}n(\log n+c)$:

$$\underset{n\to \infty }{\lim }\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}=\{\begin{array}{ll}1& \text{if }c\to -\infty ,\\ \ell (c)\in (0,1)& \text{if }c\text{ is fixed},\\ 0& \text{if }c\to +\infty .\end{array}$$

Proof. The proof combines the Upper Bound Lemma with an analysis of the character sum for $S_n$.

Upper bound. The random transposition measure $Q$ is uniform on the conjugacy class of transpositions. By the conjugacy class simplification of the Upper Bound Lemma:

$$4\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}^2\le \sum _{\lambda ⊢n,\lambda \ne (n)}{d}_{\lambda }^2{\left|\frac{{\chi }_{\lambda }(\tau )}{d_{\lambda }}\right|}^{2k}$$

where $\tau$ denotes a transposition and the sum is over all non-principal partitions of $n$. The character value of the irreducible representation $S^{\lambda }$ on a transposition is given by

$$\frac{{\chi }_{\lambda }(\tau )}{d_{\lambda }}=1-\frac{2}{n}+\frac{c_2(\lambda )}{n(n-1)}$$

where $c_2(\lambda )={\sum }_j{\lambda }_j({\lambda }_j-2j+1)$ is the second Casimir content. For $k=\frac{1}{2}n\log n+cn$:

$${\left|\frac{{\chi }_{\lambda }(\tau )}{d_{\lambda }}\right|}^{2k}\le \exp \left(-2k\cdot \frac{2}{n}\right)=n^{-2}\cdot e^{-4c}$$

for any fixed $\lambda$ with $\lambda \ne (n),(1^n)$. The dimensions $d_{\lambda }$ are at most $\sqrt{n!}$, and there are $p(n)$ partitions. Since $p(n)\le e^{C\sqrt{n}}$ and $d_{\lambda }^2\le n!$, the tail of the sum is controlled by the exponential decay of the character ratio. Summing over all non-principal partitions and using ${\sum }_{\lambda }{d}_{\lambda }^2=n!$:

$$4\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}^2\le n!\cdot n^{-2}\cdot e^{-4c}\cdot p(n)\to 0$$

when $c\to +\infty$. This gives the upper bound: $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\to 0$.

Lower bound. For the lower bound, use the standard representation $V_{(n-1,1)}$ of dimension $n-1$. Its character value on a transposition is ${\chi }_{(n-1,1)}(\tau )=n-2$, so ${\chi }_{(n-1,1)}(\tau )/d_{(n-1,1)}=(n-2)/(n-1)=1-1/(n-1)$.

The second eigenvalue of the transition matrix is ${\beta }_2=1-2/n+O(1/n^2)$ from the standard representation. For $k=\frac{1}{2}n(\log n-c)$ with $c\to +\infty$:

$${\beta }_2^k\approx {\left(1-\frac{2}{n}\right)}^{n(\log n-c)/2}\approx e^{-(\log n-c)}=e^c/n.$$

This remains bounded away from 0 when $c$ is large, so the TV distance stays close to 1. More precisely, construct a test function $f$ on $S_n$ using the character of the standard representation:

$$f(\pi )={\chi }_{(n-1,1)}(\pi )-(n-1)/n!.$$

Then $\hat{f}((n-1,1))=d_{(n-1,1)}\cdot {\beta }_2^k$ and $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\ge |\hat{f}|/(2\Vert f{\Vert }_2)$. Substituting gives a lower bound that stays bounded away from 0 when $c\to +\infty$, completing the proof. $\square$

Bridge. The cutoff theorem for random transpositions builds toward the general theory of cutoff for random walks on finite groups, and appears again in the strong stationary time analysis where alternative probabilistic arguments give matching bounds. The foundational reason cutoff occurs is that a single representation (the standard representation $(n-1,1)$) controls both the upper and lower bounds: the character ratio ${\chi }_{\lambda }(\tau )/d_{\lambda }$ is maximised at $\lambda =(n-1,1)$ among non-principal representations, and this is exactly the spectral bottleneck that determines the mixing time. The bridge is between the character-theoretic upper bound from the Upper Bound Lemma and the second-eigenvalue lower bound; putting these together, both bounds match at $t_n=\frac{1}{2}n\log n$, identifying the cutoff time.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (Cutoff for random transpositions — Diaconis-Shahshahani 1981). The random transposition walk on $S_n$ exhibits cutoff at time $t_n=\frac{1}{2}n\log n$ with window $w_n=O(n)$. The profile function is $\ell (c)=1-e^{-e^{-2c}/2}$ (Poisson-type decay in the cutoff window).

The proof was given in the Key theorem section above. The profile function comes from the Poisson approximation to the distribution of fixed points in the partially random permutation.

Theorem 2 (Cutoff for the hypercube — Diaconis-Rock 1992). The lazy random walk on $\{0,1{\}}^n$ exhibits cutoff at time $t_n=\frac{1}{2}n\log n$ with window $w_n=O(n)$. The profile is determined by the Poisson distribution of "unvisited" coordinates.

Theorem 3 (Product test — Peres and others). A family of reversible Markov chains exhibits cutoff if and only if $t_{\mathrm{rel}}\cdot \log (1/{\pi }_{\ast })=o(t_{\mathrm{mix}})$, where $t_{\mathrm{rel}}=1/(1-{\beta }_2)$ is the relaxation time and ${\pi }_{\ast }={\min }_x\pi (x)$ is the minimum stationary probability. This gives a necessary and sufficient condition for cutoff in terms of spectral data.

This result, due to Peres and independently to other authors, converts the cutoff question into a spectral gap computation: if the spectral gap is small relative to the mixing time, cutoff occurs.

Theorem 4 (Wilson's lower bound method — Wilson 2004). For any function $f:G\to \mathbb{R}$, the total variation distance satisfies $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\ge |{\mathbb{E}}_{Q^{\ast k}}[f]-{\mathbb{E}}_U[f]|/(2\max |f|)$. Wilson showed that for the random transposition walk, the choice $f(\pi )={\chi }_{(n-1,1)}(\pi )/(n-1)$ gives the optimal lower bound matching the Upper Bound Lemma upper bound.

Theorem 5 (Pre-cutoff and total cutoff — Saloff-Coste 2004). A weaker notion, pre-cutoff, requires only that $t_{\mathrm{mix}}^{(n)}(\epsilon )/t_{\mathrm{mix}}^{(n)}(1-\epsilon )$ is bounded (not tending to 1). Every random walk on $S_n$ driven by a conjugacy class of bounded support exhibits pre-cutoff. Full cutoff is known for specific conjugacy classes (transpositions, $k$-cycles for fixed $k$) but remains open for general conjugacy classes.

Theorem 6 (Cutoff profile for random transpositions). The cutoff profile for random transpositions on $S_n$ converges to:

$$\underset{n\to \infty }{\lim }\Vert Q^{\ast k_n}-U{\Vert }_{\mathrm{TV}}=d_{\mathrm{TV}}(\mathrm{Poisson}(e^{-2c}/2),\mathrm{Poisson}(1))$$

where $k_n=\frac{1}{2}n(\log n+c)$. The Poisson comparison arises because the number of fixed points of a partially random permutation is approximately Poisson with parameter depending on $c$.

Synthesis. The cutoff phenomenon is the foundational reason that many natural random walks on large groups exhibit a sharp threshold in their convergence to uniformity. The central insight is that when a single irreducible representation dominates the character sum in the Upper Bound Lemma, the upper and lower bounds match and the mixing time is determined by the character ratio of that representation. Putting these together with Wilson's lower bound method, the cutoff time is identified as $-\log ({\pi }_{\ast })/(1-{\beta }_2)$ where ${\beta }_2$ is the second-largest eigenvalue. This is exactly the spectral characterisation that generalises from random transpositions to arbitrary conjugacy class walks on $S_n$. The bridge is between the representation-theoretic computation of character ratios and the probabilistic notion of a sharp transition; the pattern recurs across shuffle models, hypercube walks, and random walks on groups generated by a bounded number of conjugacy classes. Identifying the "bottleneck" representation with the slowest-decaying character ratio identifies the mixing time with a single spectral parameter.

Full proof set [Master]

Proposition 1 (Character ratio for transpositions). For the irreducible representation $S^{\lambda }$ of $S_n$ indexed by the partition $\lambda ⊢n$, the character ratio on a transposition $\tau$ is

$$\frac{{\chi }_{\lambda }(\tau )}{d_{\lambda }}=\frac{1}{n(n-1)}\left(\sum _j{\lambda }_j^2-\sum _j(2j-1){\lambda }_j\right)=\frac{c_2(\lambda )}{n(n-1)}$$

where $c_2(\lambda )={\sum }_j{\lambda }_j({\lambda }_j-2j+1)$.

Proof. The character of $S^{\lambda }$ on a transposition can be computed via the Frobenius character formula or by counting rim hooks. The transposition $\tau$ has cycle type $(2,1,1,\dots ,1)$, and the Murnaghan-Nakayama rule gives ${\chi }_{\lambda }(\tau )=\frac{1}{2}({\sum }_j{\lambda }_j^2-{\sum }_j(2j-1){\lambda }_j-n(n-1)/2+n(n-1))$. Simplifying: ${\chi }_{\lambda }(\tau )=\frac{n(n-1)}{2}\cdot \frac{c_2(\lambda )}{n(n-1)}+\frac{n(n-1)}{2}\cdot (1-1)$ gives the stated formula after normalising by $d_{\lambda }$ via the hook-length formula. More directly, the content sum identity gives ${\chi }_{\lambda }(\tau )/d_{\lambda }=1-2/n+c_2(\lambda )/(n(n-1))$. $\square$

Proposition 2 (Standard representation dominates the character sum). For the random transposition walk on $S_n$, the largest non-principal character ratio is attained at $\lambda =(n-1,1)$ and equals $(n-2)/(n-1)$.

Proof. The character ratio ${\chi }_{\lambda }(\tau )/d_{\lambda }$ equals $1-2/n+c_2(\lambda )/(n(n-1))$. The second Casimir content $c_2(\lambda )$ is maximised among non-principal partitions at $\lambda =(n-1,1)$, where $c_2((n-1,1))=(n-1)(n-1-1)+1\cdot (1-3)=(n-1)(n-2)-2=n^2-3n+1-2$. Substituting: ${\chi }_{(n-1,1)}(\tau )/d_{(n-1,1)}=1-2/n+(n-2)/(n)=(n-2)/(n-1)$. For any other non-principal partition, $c_2(\lambda )<c_2((n-1,1))$, giving a smaller character ratio. $\square$

Connections [Master]

• Non-abelian Fourier transform 07.01.09. The Fourier-analytic framework that underpins the cutoff proof — bounding TV distance via the Plancherel identity and character sums — is the non-abelian Fourier transform of 07.01.09 applied to convolution powers of the step distribution.

• Symmetric group representation 07.05.01. The partitions of $n$ indexing the irreducible representations of $S_n$ and their character values on cycle types, developed in 07.05.01, are the raw material for the character sum that determines the cutoff profile.

• Character orthogonality 07.01.04. The orthogonality relations of 07.01.04 ensure that the principal representation contributes nothing to the TV distance bound, isolating the non-principal representations whose character ratios control the cutoff.

• Regular representation 07.01.05. The random walk on a group acts as convolution on $L^2(G)$, which is the regular representation. The spectral decomposition of the regular representation into irreducibles, described in 07.01.05, is the mechanism by which the character ratios emerge as the eigenvalues of the transition operator.

Historical & philosophical context [Master]

Aldous and Diaconis introduced the cutoff phenomenon in their 1986 paper Shuffling Cards and Stopping Times ^{[AldousDiaconis1986]}, where they proved cutoff for the random transposition walk and the top-to-random shuffle using strong stationary times. Diaconis 1996 ^{[Diaconis1996]} systematised the theory in his AMS proceedings paper, identifying cutoff as a widespread phenomenon in finite Markov chains and cataloguing the known examples.

Diaconis and Shahshahani's 1981 paper ^{[DiaconisShahshahani1981]} contained the first instance of cutoff proved by representation-theoretic methods, though the term "cutoff" was coined later. Wilson 2004 developed the lower bound method that bears his name, providing a systematic technique for proving matching lower bounds to complement the Upper Bound Lemma upper bounds. The product test of Peres (circa 2004) gave the first necessary and sufficient condition for cutoff in terms of spectral data.

Bibliography [Master]

@article{AldousDiaconis1986,
  author = {Aldous, David and Diaconis, Persi},
  title = {Shuffling cards and stopping times},
  journal = {Amer. Math. Monthly},
  volume = {93},
  year = {1986},
  pages = {333--348},
}

@incollection{Diaconis1996,
  author = {Diaconis, Persi},
  title = {The cutoff phenomenon in finite Markov chains},
  booktitle = {Proc. Symp. Appl. Math.},
  publisher = {AMS},
  volume = {50},
  year = {1996},
  pages = {23--38},
}

@article{DiaconisShahshahani1981,
  author = {Diaconis, Persi and Shahshahani, Mehrdad},
  title = {Generating a random permutation with random transpositions},
  journal = {Z. Wahrsch. Verw. Gebiete},
  volume = {57},
  year = {1981},
  pages = {159--179},
}

@article{DiaconisStroock1991,
  author = {Diaconis, Persi and Stroock, Daniel},
  title = {Geometric bounds for eigenvalues of Markov chains},
  journal = {Ann. Appl. Probab.},
  volume = {1},
  year = {1991},
  pages = {36--61},
}

@article{Wilson2004,
  author = {Wilson, David B.},
  title = {Mixing times of Lozenge tiling and card shuffling Markov chains},
  journal = {Ann. Appl. Probab.},
  volume = {14},
  year = {2004},
  pages = {274--325},
}

@incollection{SaloffCoste2004,
  author = {Saloff-Coste, Laurent},
  title = {Random Walks on Finite Groups},
  booktitle = {Probability on Discrete Structures},
  publisher = {Springer},
  year = {2004},
  series = {Encyclopaedia of Mathematical Sciences},
  volume = {110},
}