Mixing
Dana Randall, Georgia Tech.
In this tutorial, we introduce the notion of a Markov chain and explore
how it can be used to sample from a large set of configurations. Our
primary focus is determining how quickly a Markov chain ``mixes,'' or
converges to its stationary distribution, as this is the key factor in
the running time. We provide an overview of several techniques
used to establish good bounds on the mixing time. The
applications are mostly chosen from statistical physics, although the
methods are much more general.