Tel-Aviv University
School of Mathematical Sciences

Department Colloquium

Monday, December 10, 2012

Schreiber 006, 12:15

Eyal Lubetzky

Microsoft Research and the University of Washington

Cutoff Phenomenon: Instant Randomness

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