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