Colloquium Series: Mehtaab Sawhney

Our upcoming event for the Statistics Colloquium Series is scheduled for Monday, October 20 from 12:00 – 1:00pm (ET) and will be an in-person presentation Science Center 316. Lunch will be provided to guests following the talk. This week's speaker will be Mehtaab Sawhney, assistant professor at Columbia University's Mathematics Department.

Hitting time mixing for the transposition walk

Consider shuffling a deck of n cards, labeled 1 through n, as follows: at each time step, pick one card uniformly with your right hand and another card, independently and uniformly with your left hand; then swap the cards. How long does it take until the deck is close to random?

Confirming a conjecture of N. Berestycki, we prove the definitive "hitting time" version for the mixing of this shuffle. Let τ denote the first time at which all cards have been touched. The total variation distance between the stopped distribution at τ and the uniform distribution on permutations is o_n(1); this is best possible, since at time τ−1, the total variation distance is at least (1+o_n(1))/e. A key feature of this proof is to combine the representation theoretic inputs of Diaconis and Shahshahani with a physical space argument.
Based on joint work w. Vishesh Jain

Mehtaab Sawhney is a Clay Research Fellow and a tenure-track assistant professor at Columbia University. His research interests are broadly within combinatorics, probability, analytic number theory and theoretical computer science.