Cutoff for the Biased Random Transposition Shuffle

The biased random transposition shuffle is a natural generalization of the classical random transposition shuffle studied by Diaconis and Shahshahani. In this variation, rather than selecting two cards uniformly at random and swapping them, two cards are still chosen, but with a higher probability of selecting from one half of the deck over the other. By diagonalizing the transition matrix of the biased random transposition shuffle, we show that it exhibits total variation cutoff with window N. We also show that the limiting distribution of the number of fixed cards near the cutoff time is Poisson. Compared to the case of random transpositions, our proofs require new tools from the representation theory of the symmetric group and the combinatorics of hive models. Joint work with Evita Nestoridi.

For information about the Richard P. Stanley Seminar in Combinatorics, visit https://math.mit.edu/combin/