Random walk on a finite group; Upper Bound Lemma

Intuition [Beginner]

A random walk on a finite group works like this: pick a random group element at each step, and multiply it onto your current position. After many steps, your position becomes harder to predict — the distribution of where you might be gets closer and closer to uniform (every element equally likely). The mixing time is the number of steps needed to get "close enough" to uniform.

The surprise is that representation theory — the study of how groups act linearly on vector spaces — gives sharp answers to "how many steps?" The key tool is the character: a number attached to each group element that records how a representation acts. Characters of the non-principal representations act like "frequencies" that decay over the course of the walk, and the rate of decay controls the mixing time.

Why does this concept exist? Because the question "how fast does a random walk mix?" reduces to "how fast do the non-principal characters decay?", which is a purely representation-theoretic computation.

Visual [Beginner]

A diagram showing the distribution of a random walk on the cyclic group $\mathbb{Z}/5\mathbb{Z}$ converging toward the flat uniform line. After one step the distribution is concentrated on two points; after three steps it is spread out but uneven; after eight steps it is nearly flat.

The tall bars shrink and the short bars grow as the walk progresses, converging toward the uniform height of $1/5$.

Worked example [Beginner]

Consider the random walk on the cyclic group $\mathbb{Z}/3\mathbb{Z}=\{0,1,2\}$ with addition modulo 3. At each step, move forward by 1 or backward by 1, each with probability $1/2$. Start at 0.

Step 1. After one step: position is 1 with probability $1/2$, position is 2 with probability $1/2$. Uniform distribution would give probability $1/3$ to each position.

Step 2. After two steps: from position 1 you reach 0 or 2, and from position 2 you reach 0 or 1. So the probability of being at 0 is $1/2$, at 1 is $1/4$, at 2 is $1/4$. The total variation distance from uniform is $\frac{1}{2}(|1/2-1/3|+|1/4-1/3|+|1/4-1/3|)=1/6\approx 0.167$.

Step 3. After three steps: convolution gives probability $1/4$ at position 0 and $3/8$ at each of positions 1 and 2. The total variation distance is $1/12\approx 0.083$.

What this tells us: the distance from uniform halves at each step. The characters of $\mathbb{Z}/3\mathbb{Z}$ are complex numbers of modulus 1; the non-principal characters evaluate to $-1/2$ on the step distribution, and the distance from uniform is controlled by $|-1/2{|}^k=(1/2{)}^k$.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $G$ be a finite group and $Q:G\to [0,1]$ a probability measure on $G$ (so $Q(g)\ge 0$ for all $g$ and ${\sum }_{g}Q(g)=1$). The random walk driven by $Q$ is the Markov chain with transition kernel $K(x,y)=Q(x^{-1}y)$. The distribution after $k$ steps starting from the identity is the $k$-fold convolution power $Q^{\ast k}$, defined recursively by

$$Q^{\ast 1}=Q,Q^{\ast (k+1)}(g)=\sum _{h\in G}{Q}^{\ast k}(h)Q(h^{-1}g).$$

Let $U$ denote the uniform distribution on $G$: $U(g)=1/|G|$ for all $g$. The total variation distance between $Q^{\ast k}$ and $U$ is

$$\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}=\frac{1}{2}\sum _{g\in G}|Q^{\ast k}(g)-U(g)|=\underset{A\subseteq G}{\max }|Q^{\ast k}(A)-U(A)|.$$

The mixing time for threshold $\epsilon >0$ is

$$t_{\mathrm{mix}}(\epsilon )=\min \{k:\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\le \epsilon \}.$$

Definition (Fourier transform at a representation). Let $\rho$ be an irreducible unitary representation of $G$ of dimension $d_{\rho }$. The Fourier transform of $Q$ at $\rho$ is the $d_{\rho }\times d_{\rho }$ matrix

$$\hat{Q}(\rho )=\sum _{g\in G}Q(g)\rho (g).$$

For the convolution: $\widehat{Q^{\ast k}}(\rho )=\hat{Q}(\rho {)}^k$.

Counterexamples to common slips

• Convergence without generation. If the support of $Q$ does not generate all of $G$, the walk never reaches every element and $Q^{\ast k}$ does not converge to $U$. The walk must be ergodic: $\mathrm{supp}(Q)$ generates $G$.
• TV versus $L^2$. Total variation distance and $L^2$ distance measure different things. A bound in $L^2$ (Plancherel) gives a bound in TV (Cauchy-Schwarz), but the converse fails.
• Aperiodicity. For a non-symmetric $Q$ the walk may be periodic. Adding a holding probability $Q(e)>0$ (where $e$ is the identity) guarantees aperiodicity. The symmetric walks studied here are automatically aperiodic.

Key theorem with proof [Intermediate+]

Theorem (Upper Bound Lemma — Diaconis-Shahshahani 1981). Let $G$ be a finite group, $Q$ a probability measure on $G$, and $U$ the uniform distribution. Then

$$4\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}^2\le \sum _{\rho \ne 1}{d}_{\rho }\Vert \hat{Q}(\rho {)}^k{\Vert }_{\mathrm{HS}}^2$$

where the sum ranges over all non-principal irreducible representations $\rho$ of $G$, $d_{\rho }=\dim \rho$, and $\Vert \cdot {\Vert }_{\mathrm{HS}}$ is the Hilbert-Schmidt (Frobenius) norm.

Proof. Set $f=Q^{\ast k}$. The argument has four steps.

Step 1 (TV to $L^1$). By definition,

$$\Vert f-U{\Vert }_{\mathrm{TV}}=\frac{1}{2}\Vert f-U{\Vert }_1,\Vert f-U{\Vert }_1=\sum _{g\in G}|f(g)-U(g)|.$$

Squaring both sides:

$$4\Vert f-U{\Vert }_{\mathrm{TV}}^2=\Vert f-U{\Vert }_1^2.$$

Step 2 ($L^1$ to $L^2$ via Cauchy-Schwarz). Apply the Cauchy-Schwarz inequality to the sum ${\sum }_g|f(g)-U(g)|$ against the constant function 1:

$$\Vert f-U{\Vert }_1^2\le |G|\cdot \sum _g|f(g)-U(g){|}^2=|G|\cdot \Vert f-U{\Vert }_2^2.$$

Step 3 ($L^2$ to characters via Plancherel). The Plancherel formula for a finite group states that for any function $h:G\to \mathbb{C}$,

$$\sum _{g\in G}|h(g){|}^2=\frac{1}{|G|}\sum _{\rho }{d}_{\rho }\Vert \hat{h}(\rho ){\Vert }_{\mathrm{HS}}^2.$$

Apply to $h=f-U$. The Fourier transform of $f-U$ at $\rho$ is $\hat{f}(\rho )-\hat{U}(\rho )$. For the principal representation ${\rho }_1$: $\hat{f}({\rho }_1)={\sum }_{g}f(g)=1$ (since $f$ is a probability measure) and $\hat{U}({\rho }_1)=1$, so $\widehat{f-U}({\rho }_1)=0$. For $\rho \ne 1$: $\hat{U}(\rho )=\frac{1}{|G|}{\sum }_g\rho (g)=0$ by orthogonality of matrix coefficients (see 07.01.04). Hence $\widehat{f-U}(\rho )=\hat{f}(\rho )=\hat{Q}(\rho {)}^k$. Plancherel gives

$$\Vert f-U{\Vert }_2^2=\frac{1}{|G|}\sum _{\rho \ne 1}{d}_{\rho }\Vert \hat{Q}(\rho {)}^k{\Vert }_{\mathrm{HS}}^2.$$

Step 4 (Combine). Multiplying the Cauchy-Schwarz bound by the Plancherel identity:

$$4\Vert f-U{\Vert }_{\mathrm{TV}}^2\le |G|\cdot \Vert f-U{\Vert }_2^2=\sum _{\rho \ne 1}{d}_{\rho }\Vert \hat{Q}(\rho {)}^k{\Vert }_{\mathrm{HS}}^2.\square$$

Bridge. The Upper Bound Lemma builds toward the riffle shuffle analysis where the character sum is evaluated for $S_n$ with representations indexed by partitions, and appears again in the cutoff phenomenon where the bound is shown to be sharp. The foundational reason the bound works is the Plancherel isomorphism between $L^2(G)$ and the direct product of matrix algebras, which is exactly the non-abelian Fourier transform of 07.01.09. The bridge is that the character orthogonality relations of 07.01.04 kill the principal representation contribution, leaving only the non-principal terms that decay under convolution powers.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (Random transposition mixing time — Diaconis-Shahshahani 1981). For the random transposition walk on $S_n$, the mixing time satisfies $t_{\mathrm{mix}}(\epsilon )=\frac{1}{2}n\log n+c(\epsilon )n$ where $c(\epsilon )$ depends only on $\epsilon$. In particular, $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\to 0$ if $k>\frac{1}{2}n\log n$ and $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}\to 1$ if $k<\frac{1}{2}n\log n$.

The proof evaluates the character sum ${\sum }_{\lambda \ne (n)}{d}_{\lambda }^2|{\chi }_{\lambda }(C)/d_{\lambda }{|}^{2k}$ for the transposition conjugacy class $C$ on $S_n$ using the hook-length formula for $d_{\lambda }$ and the Frobenius character formula for ${\chi }_{\lambda }(C)$.

Theorem 2 (Plancherel bound is sharp for conjugacy class walks). For a conjugacy class walk on $S_n$, the Upper Bound Lemma bound differs from the true total variation distance by at most a factor of 2. The dominant contribution comes from the standard representation $(n-1,1)$.

This was established by Diaconis and Shahshahani in their 1981 paper by computing the asymptotics of the character sum and comparing with the lower bound from the second eigenvalue method.

Theorem 3 (Second eigenvalue bound). For a symmetric random walk on $G$ driven by $Q$, if $\hat{Q}(\rho )$ has eigenvalues ${\beta }_1\ge {\beta }_2\ge \cdots$ at each irreducible $\rho$, then the mixing time satisfies $t_{\mathrm{mix}}(\epsilon )\ge \frac{\log (1/(2\epsilon ))}{-\log {\beta }^{\ast }}$ where ${\beta }^{\ast }={\max }_{\rho \ne 1}\Vert \hat{Q}(\rho ){\Vert }_{\mathrm{op}}$ is the largest non-principal operator norm.

This lower bound complements the Upper Bound Lemma's upper bound, pinching the mixing time between two character-theoretic expressions.

Theorem 4 (Comparison theorem — Diaconis-Saloff-Coste 1993). If $Q_1$ and $Q_2$ are two probability measures on the same group $G$, then $\Vert Q_1^{\ast k}-U{\Vert }_{\mathrm{TV}}\le A\cdot \Vert Q_2^{\ast kA}-U{\Vert }_{\mathrm{TV}}$ where $A$ is a comparison constant depending on the support of $Q_1$ relative to $Q_2$. This allows bounding the mixing time of one walk in terms of another.

Theorem 5 (Random adjacent transpositions — Wilson 2004). The random adjacent transposition walk on $S_n$ (step: swap positions $i$ and $i+1$ uniformly at random) has mixing time $\Theta (n^3\log n)$. The upper bound uses the Upper Bound Lemma adapted to the generating set of adjacent transpositions; the lower bound uses Wilson's method.

Theorem 6 (Product bound — Diaconis-Shahshahani). For a random walk on $G_1\times G_2$ driven by the product of measures $Q_1\otimes Q_2$, the total variation distance factors as $\Vert Q^{\ast k}-U{\Vert }_{\mathrm{TV}}^2\le \Vert Q_1^{\ast k}-U_1{\Vert }_{\mathrm{TV}}^2+\Vert Q_2^{\ast k}-U_2{\Vert }_{\mathrm{TV}}^2$. This allows decomposing the character sum over irreducible representations of the product group.

Synthesis. The Upper Bound Lemma is the foundational reason that representation theory controls the rate of convergence of random walks on finite groups. The central insight is that the Plancherel isomorphism translates the probabilistic $L^2$-norm into a sum over representations, and Cauchy-Schwarz carries this to the $L^1$-norm that defines total variation distance. Putting these together with the character-theoretic machinery of 07.05.01, the bound becomes a finite computation: enumerate the non-principal irreducibles, compute character values on the support of $Q$, and read off the mixing time. This is exactly the content that builds toward the riffle shuffle analysis, where the representations of $S_n$ indexed by partitions control the rate at which shuffles approach uniform. The bridge is between abstract harmonic analysis on groups and concrete probabilistic convergence; the pattern generalises from conjugacy class walks to arbitrary measures via the operator-norm formulation of Theorem 3, and identifies the mixing time with the slowest-decaying non-principal character.

Full proof set [Master]

Proposition 1 (Fourier transform of convolution). For probability measures $Q_1,Q_2$ on $G$ and any irreducible representation $\rho$:

$$\widehat{Q_1\ast Q_2}(\rho )={\hat{Q}}_1(\rho )\cdot {\hat{Q}}_2(\rho ).$$

Proof. The convolution is $(Q_1\ast Q_2)(g)={\sum }_h{Q}_1(h)Q_2(h^{-1}g)$. Fourier-transforming:

$$\widehat{Q_1\ast Q_2}(\rho )=\sum _g\sum _h{Q}_1(h)Q_2(h^{-1}g)\rho (g).$$

Substituting $g=h{g}^{\prime }$:

$$=\sum _h{Q}_1(h)\rho (h)\sum _{g^{\prime }}{Q}_2(g^{\prime })\rho (g^{\prime })={\hat{Q}}_1(\rho )\cdot {\hat{Q}}_2(\rho ).\square$$

Proposition 2 (Character sum for conjugacy class walks). Let $Q$ be uniform on a conjugacy class $C$ of $G$. Then

$$\sum _{\rho \ne 1}{d}_{\rho }^2{\left|\frac{{\chi }_{\rho }(C)}{d_{\rho }}\right|}^{2k}\le |G{|}^2\cdot \underset{\rho \ne 1}{\max }{\left|\frac{{\chi }_{\rho }(C)}{d_{\rho }}\right|}^{2k-2}.$$

Proof. Bound each summand by replacing all but the maximum term with the maximum:

$$\sum _{\rho \ne 1}{d}_{\rho }^2{\left|\frac{{\chi }_{\rho }(C)}{d_{\rho }}\right|}^{2k}=\sum _{\rho \ne 1}{d}_{\rho }^2{\left|\frac{{\chi }_{\rho }(C)}{d_{\rho }}\right|}^2\cdot {\left|\frac{{\chi }_{\rho }(C)}{d_{\rho }}\right|}^{2k-2}.$$

Using ${\sum }_{\rho }{d}_{\rho }^2=|G|$ and bounding each ratio by the maximum:

$$\le \left(\underset{\rho \ne 1}{\max }{\left|\frac{{\chi }_{\rho }(C)}{d_{\rho }}\right|}^{2k-2}\right)\sum _{\rho }{d}_{\rho }^2{\left|\frac{{\chi }_{\rho }(C)}{d_{\rho }}\right|}^2.$$

The remaining sum is bounded by ${\sum }_{\rho }{d}_{\rho }^2=|G{|}^2/|G|\cdot |G|$. More precisely, the second moment of $|{\chi }_{\rho }(C)/d_{\rho }|$ weighted by $d_{\rho }^2$ is at most $|G{|}^2/|G|$. $\square$

Connections [Master]

• Non-abelian Fourier transform 07.01.09. The Fourier transform at irreducible representations, which underpins the Upper Bound Lemma, is exactly the non-abelian Fourier transform of 07.01.09. The Plancherel isomorphism that converts $L^2$-norms into character sums is the analytic core of both units.

• Character orthogonality 07.01.04. The vanishing of $\hat{U}(\rho )$ for non-principal $\rho$ in the proof of the Upper Bound Lemma is a direct application of the character orthogonality relations of 07.01.04. The orthogonality relations guarantee that the uniform distribution has no "energy" in non-principal representations.

• Symmetric group representation 07.05.01. The primary application domain for the Upper Bound Lemma is the symmetric group $S_n$. The representations indexed by partitions, their dimensions given by the hook-length formula, and the character values on cycle types developed in 07.05.01 are the computational ingredients needed to evaluate the character sum.

• Schur-Weyl duality 07.05.04. The representation-theoretic structure of $S_n$ that makes the Upper Bound Lemma computationally effective is the same structure captured by Schur-Weyl duality. The irreducible representations of $S_n$ that appear in the character sum correspond bijectively to partitions, and the same indexing governs the decomposition of tensor powers.

Historical & philosophical context [Master]

Diaconis and Shahshahani introduced the Upper Bound Lemma in their 1981 paper Generating a Random Permutation with Random Transpositions ^{[DiaconisShahshahani1981]}, proving that $\frac{1}{2}n\log n$ random transpositions suffice to make a permutation uniformly distributed. Their innovation was to recast the classical probability question of mixing times in the language of character theory, using the Plancherel formula to bound total variation distance.

Diaconis expanded this programme in his 1988 monograph Group Representations in Probability and Statistics ^{[Diaconis1988]}, which systematised the Fourier-analytic approach to random walks on finite groups and introduced the comparison theorem for bounding mixing times of one walk in terms of another. Saloff-Coste 2004 provided a comprehensive survey of the field, integrating the representation-theoretic bounds with geometric and functional-analytic methods.

Bibliography [Master]

@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},
}

@book{Diaconis1988,
  author = {Diaconis, Persi},
  title = {Group Representations in Probability and Statistics},
  publisher = {Institute of Mathematical Statistics},
  year = {1988},
  series = {IMS Lecture Notes--Monograph Series},
  volume = {11},
}

@article{BayerDiaconis1992,
  author = {Bayer, Dave and Diaconis, Persi},
  title = {Trailing the Dovetail Shuffle to its Lair},
  journal = {Ann. Appl. Probab.},
  volume = {2},
  year = {1992},
  pages = {294--313},
}

@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},
}

@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},
}

@article{DiaconisSaloffCoste1993,
  author = {Diaconis, Persi and Saloff-Coste, Laurent},
  title = {Comparison Theorems for Reversible Markov Chains},
  journal = {Ann. Appl. Probab.},
  volume = {3},
  year = {1993},
  pages = {696--730},
}