A Random Walk in Representations

The unifying objective of this thesis is to find the mixing time of the Markov chain on $S_n$ formed by applying a random $n$-cycle to a deck of $n$ cards and following with repeated random transpositions. This process can be viewed as a Markov chain on the partitions of $n$ that starts at $(n)$, making it a natural counterpart to the random transposition walk, which starts at $(1^n)$. By considering the Fourier transform of the increment distribution on the group representations of $S_n$ and then computing the characters of the representations, Diaconis and Shahshahani showed in \cite{DS81} that the order of mixing for the random transposition walks is $n\ln n$. We adapt this approach to find an upper bound for the mixing time of the $n$-cycle-to-transpositions shuffle. To obtain a lower bound, we derive the distribution of the number of fixed points for the chain using the method of moments. In the process, we give a nice closed-form formula for the irreducible representation decomposition of tensor powers of the defining representation of $S_n$. Along the way, we also look at the more general $m$-cycle-to-transpositions chain ($m \le n$) and give an upper bound for the mixing time of the $m=n-1$ case as well as characterize the expected number of fixed points in the general case where $m$ is an arbitrary function of $n$.