Cutoff for biased transpositions

Abstract

In this paper we study the mixing time of a biased transpositions shuffle on a set of $N$ cards with $N/2$ cards of two types. For a parameter $0<a\le 1$, one type of card is chosen to transpose with a bias of $\frac{a}{N}$ and the other type is chosen with probability $\frac{2-a}{N}$. We show that there is cutoff for the mixing time of the chain at time $\frac{1}{2a}N\log N$. Our proof uses a modified marking scheme motivated by Matthews' proof of a strong uniform time for the unbiased shuffle.

11 pages

Cited by in corpus (1)

• Random Walks on the Symmetric Group: Cutoff for One-sided Transposition Shuffles