School of Mathematical Sciences
Monday, December 10, 2012
Schreiber 006, 12:15
Microsoft Research and the University of Washington
Cutoff Phenomenon: Instant Randomness
Abstract: How many shuffles are needed to mix a deck of cards?
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