School of Mathematical Sciences

Department Colloquium

Schreiber 006, 12:15

Microsoft Research and the University of Washington

How many shuffles are needed to mix a deck of cards?

Abstract:

How long does it take a random walk on a transitive expander to be suitably uniform?

Is there a sharp threshold? For many such questions the order of the mixing time

is well understood, and yet it is unknown whether mixing occurs gradually or abruptly.

The latter scenario, where the distance to equilibrium drops from near 1 to near 0 over a

negligible time period, corresponds to the ``cutoff phenomenon’’ discovered by Diaconis,

Shahshahani and Aldous in the early 80’s. We will survey different aspects of this topic,

including recent results and some of the main problems that remain open.

Coffee will be served at 12:00 before the lecture

at Schreiber building 006