Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, November 27, 2012 - 4:30pm

Shanshan Ding

University of Pennsylvania

Location

University of Pennsylvania

4C6

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.