A Random Walk in Representations

Institution: | University of Pennsylvania |
---|---|

Department: | |

Year: | 2014 |

Keywords: | Mathematics |

Record ID: | 2045435 |

Full text PDF: | http://repository.upenn.edu/edissertations/1074 http://repository.upenn.edu/cgi/viewcontent.cgi?article=2198&context=edissertations |

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