Thursday, February 04, 2021, 11:00am - 12:00pm
How many times should you shuffle a deck of cards so that its distribution is approximately uniform? This question can be formalised through the notion of mixing time for a Markov chain. Elementary theory tells us that, given an irreducible and aperiodic Markov chain on a finite state space, its distribution will converge to a unique "equilibrium" distribution. But this theory doesn't say anything about how long one should wait to be close to this distribution. In the early 1980s, Persi Diaconis and David Aldous discovered independently and simultaneously the remarkable fact that many chains undergo a "cutoff phenomenon", where the convergence to equilibrium occurs abruptly (as some parameter n, say the size of the state space, tends to infinity), at a well defined time called the mixing time. I will explain these notions and ideas in a self-contained way; in particular no probabilistic prerequisite will be assumed. I hope to discuss some examples and give a (very rapid) glimpse of the current state of the theory.
Location: Zoom