Markov chains and mixing times
Markov chain Monte Carlo (MCMC) is a widely used algorithm in Mathematical Physics, Computer Science and Statistics, in order to sample from intractable distributions.
The main component in the running time of the MCMC algorithm is the “mixing time” of the underlying Markov chain., i.e., the number of steps one needs to run the chain to approximate the stationary distribution well. The modern mathematical theory of Markov chain mixing was initiated by Aldous and Diaconis in the 1980s. They described the “cutoff phenomenon” where the distribution of the Markov chain approaches the limiting stationary distribution abruptly. They wrote “From a theoretical viewpoint, there are interesting questions concerning the cut-off phenomenon. This occurs in all the examples we can explicitly calculate, but we know no general result which says that the phenomenon must happen for all “reasonable” shuffling methods”.
This book introduces the modern theory of Markov chain mixing, starting from basic notions and inequalities, and later developing the key tools used in analysis of Markov chains; Coupling, expansion, strong stationary times, electrical networks, eigenvalues, comparison inequalities, transportation methods (path coupling) and martingales. These tools are then applied to a variety of interesting chains, including random walks on graphs, card shuffling, Glauber dynamics for the Ising model, birth and death chains and lamplighter walks. Advanced chapters are devoted to the cutoff phenomenon, the exclusion process, and chains on infinite state spaces. The book has been used in undergraduate and graduate. courses in many universities.