Math 202C: Lecture 5

Lectures 5 and 6 of Math 202C give an application of the representation theory of the symmetric group \mathrm{S}(d) as discussed in Math 202B together with the additional material on the YJM elements in the corresponding group algebra \mathcal{A}(d). This application is probabilistic in nature, and concerns the following question: how many times do you have to shuffle a deck of cards in order to randomize it?

In order to analyze this question rigorously, we need to model it mathematically. The first step is to say exactly what we mean by “shuffle.” We consider a deck of d cards labeled 1,\dots,d laid face up on a table, arranged in a single row. Initially, this arrangement is 1,\dots,d, from left to right. At each tick of the clock, we choose a random card, and swap its position with the rightmost card. This gives us a new arrangement of cards which, reading the labels from left to right, corresponds to a permutation in the symmetric group \mathrm{S}(d). This is called the “top-to-random” shuffle. Note that it is possible the randomly chosen card is in fact the rightmost (top) card, and in this case no shuffling occurs.

The top-to-random shuffle is a stochastic process evolving in discrete time. It may equivalently be formulated as a random walk on the the Cayley graph \Gamma(d)=\mathrm{Cay}(\mathrm{S}(d),R) of the symmetric group generated by the set

Y_d=\{(1\ d), (2\ d),\dots, (d-1\ d)\}.

The elements of R are transpositions; they are called “star transpositions” because, if we picture R as the edge set of a graph on \{1,\dots,d\}, we get the star graph with hub vertex d. The simple random walk on \Gamma(d) is the following stochastic process: a particle is initially located at the identity permutation \iota \in \mathrm{S}(d), and at each tick of the clock it jumps to a neighboring vertex, with equal probability of jumping in any direction. This can be encoded algebraically as follows. Let \mathcal{A}(d) be the group algebra of \mathrm{S}(d), equipped with the scalar product in which the permutation basis is orthonormal. Identify the generating set with the sum of its elements,

Y_d (1\ d) +\dots +(d-1\ d),

which you will recognize from our previous lectures as the top YJM element in \mathcal{A}(d). The probability that a particle on \Gamma(d) evolving by simple random walk is located at a given permutation \pi \in \mathrm{S}(d) at a given time r \in \mathbb{N}_0 is then equal to the normalized scalar product

P_r(\pi) = \frac{1}{(d-1)^r} \langle \pi, Y_d^r \iota \rangle.

This random walk is not equivalent to the top-to-random shuffle, but rather to a shuffling process in which one of the d-1 cards below the top card is exchanged with the top card. This is not a good way to shuffles cards, because randomness is never achieved; equivalently, the corresponding random walk is not ergodic. A random walk on a graph is said to be ergodic if, for all sufficiently large times, the particle has positive probability of being located at each vertex. This is not the case for simple random walk on \Gamma(d) — at even times, the probability the particle is located at an odd permutation is zero, and vice versa.

A shuffling process should have the property that as r \to \infty we get closer and closer to a uniform distribution, which algebraically is represented by the vector

\mathbf{u} = \frac{1}{d!} \sum\limits_{\pi \in \mathrm{S}(d)} \pi.

More formally, let us introduce the \ell_1-norm on \mathcal{A}(d) corresponding to the permutation basis, which assigns to each \mathbf{a}\in \mathcal{A}(d) the number

\|\mathbf{a}\| = \sum\limits_{\pi \in \mathrm{S}(d)} |\langle \pi,\mathbf{a}\rangle|.

In probability theory, the corresponding distance \|\mathbf{a}_1-\mathbf{a}_2\| is called total variation distance. The lazy simple random walk on \Gamma(d) is the modification of simple random walk in which, at each tick of the clock, the particle either jumps to an adjacent vertex or stays put, with each such event occurring with equal probability. This random walk is generated by the group algebra element \iota + Y_d, which means that the probability the particle is located at \pi \in \mathrm{S}(d) is

P^r(\pi) = \frac{1}{d^r} \langle \pi, (\iota+Y_d)^r\iota \rangle.

This random walk is ergodic, and it follows from the Perron-Frobenius theorem in linear algebra that

\lim\limits_{d\to \infty} P^r(\pi) = \frac{1}{d!}

for each \pi \in \mathrm{S}(d), so that perfect randomness is achieved in the limit of infinitely many shuffles.

Shuffling infinitely many times is not something that can be done in the real world. Therefore what we want is an effective version of the above, which tells us how close our deck is to randomized after r shuffles have been performed. Algebraically, we want bounds on the \ell_1-norm

\|\frac{1}{d^r}(\iota+Y_d)^r\iota - \mathbf{u}\|.

This weeks lectures, which take the form of a typeset document posted to Piazza in the resources section, explain how to do this using the representation theory of the symmetric group, in particular the spectral theory of the YJM elements which we have been discussing. A remarkable insight coming out of the analysis is that the top-to-random shuffle exhibits what is known as the cutoff phenomenon: for small values of r, the total variation distance to uniform remains close to its initial value, and then suddenly crosses a d-dependent cutoff time and becomes exponentially small, indicating that near-perfect randomness has been achieved in finite time.

Leave a Reply