Abstract

Cutoff for biased transpositions

Evita Nestoridi
SUNY Stony Brook

Diaconis and Shahshahani proved that shuffling a deck of $n$ cards with random transpositions takes $1/2 n \log n$ steps to mix. In this talk we will discuss the case where a card that is located in the top $n/2$ positions gets selected with probability $b/n$ and otherwise it gets selected with probability $(2-b)/n$, where $0<b≤1$ is fixed. We then swap the cards. In joint work in progress with A. Yan, we prove that this shuffle takes $(2b)^{-1} n \log n$ steps to mix. Our proof heavily relies on the results of Diaconis and Shahshahani for random transpositions.