A random walk in representations

The unifying objective of this thesis is to find the mixing time of the Markov chain on Sn 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 (1n). 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 [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-totranspositions 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 Sn. Along the way, we also look at the more general m-cycle-to-transpositions chain (m ≤ 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