Math 202C: Lecture 12

Since the representation theory of the symmetric group is likely fresh in your mind thanks to yesterday’s exam, this is a good time to show you a very nice probabilistic application of this theory to card shuffling. This post will discuss the “top-to-random” shuffle, where the cards $1,\dots,n$ are arranged in a single row (or a single stack), and a randomly chosen card is repeatedly swapped with the rightmost (or top) card. The algebraic model for this procedure is the Cayley graph $\Gamma(n)$ of the symmetric group as generated by the so-called “star transpositions” $\tau_1=(1\ n), \tau_2=(2\ n),\dots, \tau_{n-1} = (n-1\ n).$

Problem 12.1: Prove that the above transpositions do in fact generate $\mathrm{S}(n).$

These are called star transpositions because, if one forms the graph on $\{1,\dots,n\}$ such that $\{i,j\}$ is an edge if and only if one of the above transpositions swaps $i$ and $j$, then this graph is a star graph. The top-to-random shuffle is then the same thing as the lazy simple random walk on the Cayley graph $\Gamma(n).$

The paper attached below gives a detailed analysis of the top-to-random shuffle using the representation theory of $\mathrm{S}(n),$ and gives a precise meaning to the statement that $n \log n$ such shuffles are required in order to randomize the deck. The argument is pretty much all representation theory — only some very basic probabilistic reasoning is used towards the end.