After a single application of an m-cycle to a deck of n cards, how many transpositions are needed to mix the deck? The m=2 case was solved by Diaconis and Shahshahani with the seminal result that the mixing time is O(nln(n)). We give an overview of their approach, which involves Fourier transforms and the representation theory of the symmetric group. We then present our results on the m=n case and, time permitting, the general case. An interesting related question is how the number of fixed points is distributed under this process, and we describe how to compute the moments of these distributions.
Probability and Combinatorics
Tuesday, November 27, 2012 - 4:30pm
Shanshan Ding
University of Pennsylvania