In this Lecture, we analyze simple random walk on the group of permutations generated by the disjoint transpositions

The corresponding Cayley graph has vertex set with an edge if and only if for some

Simple random walk on has an interesting equivalent formulation known Ehrenfest diffusion model, which is used in thermodynamics. The Ehrenfest model consists of two urns, and and balls At time zero, all balls are in urn At each instant of discrete time thereafter, a ball is chosen uniformly at random, and moved to the other urn.

**Problem 10.1:** Explain the equivalence between Ehrenfest diffusion and simple random walk on

Simple random walk on begins with a single particle positioned at the identity permutation At each tick of the clock, the particle makes a random jump to an adjacent permutation, with equal probability of jumping to any neighboring vertex on the -regular graph However, because is bipartite, the distribution of this random walk does not converge.

**Problem 10.2:** Prove that is a bipartite graph.

To fix the bipartiteness issue, we replace with a new graph which differs only from by the addition of exactly one loop at each vertex, resulting in a -regular graph with the same vertex set. This resolves the bipartiteness issue: by the Markov limit theorem, simple random walk on converges to uniform measure on Note that one can equivalently think of simple random walk on as a “lazy” random walk on where at each time instant the particle either stays put or jumps to a neighboring vertex, with all events being equally likely.

We proceed to analysis of simple random walk on Let be the group algebra of i.e. the Hilbert space with orthonormal basis

and multiplication given by bilinear extension of the group law

The probability operator for lazy simple random walk on is then implemented as multiplication by

where is the identity permutation. In other words, the distribution of the particle at time is given by the vector We would like to compare this to the vector

which corresponds to uniform measure on . More precisely, we would like to estimate the quantity

which, up to a factor of coincides with the total variation distance between the distribution of the particle at time and the uniform distribution.

We will get an upper bound on the above total variation distance using the eigenvalues and eigenvectors of We have ample information concerning the eigenvalues and eigenvectors of the operator from Lecture 9, where we analyzed the operator of multiplication by

which is the adjacency operator of We know that the eigenvalues of are the numbers

and that the eigenspace of has dimension (an orthogonal basis of is given by the characters of indexed by permutations with ) Now, it is immediate to see that

where is the identity operator, so that has the same eigenspaces as and more precisely that acts in as multiplication by

In particular, the largest eigenvalue of is and it is a simple eigenvalue, which is consistent with Perron-Frobenius, and moreover is the eigenvalue of largest absolute value, since the smallest eigenvalue is

which is also consistent with Perron-Frobenius. We will now plug this information into the famous Upper Bound Lemma of Diaconis-Shahshahani to get an estimate on the total variation distance between the distribution of lazy simple random walk on at time and the uniform distribution on the vertices of We skip the proof, and comment only that it follows from combining character expansion and the Cauchy-Schwarz inequality. A proof can be found in the “Harmonic Analysis on Finite Groups” reference text.

**Theorem (Upper Bound Lemma):** We have

with the eigenvalue of the transition operator acting on the character . The only eigenvalue equal to is and hence we have

Let us apply the Upper Bound Lemma. Right off the bat, it tells us that

so we just have to estimate this sum of explicit quantities. Observing that

we have the estimate

and the factor of two which appears cancels with the missing factor of which distinguishes the -norm from the actual total variation distance. Thus we get that the total variation distance between the distribution of lazy simple random walk on at time and the uniform distribution, satisfies

To estimate the right hand side, first observe that

so that

Using that

for we have

so that we have arrived at the upper bound

Now observe that if is large enough so that the exponentially small factor defeats the polynomially large factor even for small values of then the distance will be very small. More precisely, if

for some constant then

and we have

a number exponentially close to Thus as soon as the number of steps in lazy simple random walk on exceeds the threshold

the distribution of the walk becomes exponentially close to its limiting distribution. On the other hand, if instead

is below this threshold, then the distance between the total variation distance between the distribution of the walk and its limit distribution is still exponentially close to its initial value of Thus the transition from not very random to exponentially close to total randomness happens suddenly, in a neighborhood of the “cutoff”

This so-called “cutoff phenomenon,” was discovered by Diaconis and Shahshahani for card shuffles, i.e. random walks on the symmetric group, which we will discuss next. There is no known characterization of the class of Markov chains for which this phenomenon occurs; observe that to establish it for we needed total knowledge of the eigenvalues and eigenvectors of the associated probability operator For random walks on groups this information can often be obtained thanks to representation theory, which is a testament to the power of symmetry. For random walks on graphs which are not Cayley graphs of groups, complete knowledge of eigenvalues and eigenvectors is typically unavailable, and one cannot determine effective bounds on the speed of convergence of random walk to its stationary distribution.