Markov chains and mixing times

Brownian Motion - By Peter Mörters and Yuval Peres

By David A. Levin and Yuval Peres


“Markov chains and mixing times” is a textbook on an active topic, of interest to probabilists, computer scientists, statisticians, physicists and combinatorialists. Finite Markov chains were considered well  understood objects, until new applications and a new point of view emerged in the 1980s.  Traditionally, the distribution of a fixed Markov chain as  time tends to infinity was considered, and a complete answer was given by eigenvalues of the transition matrix. Quantitative analysis of simulation algorithms used in physics, statistics and computing led to the insight that the most interesting asymptotics arises when the target distance to stationarity is fixed, and both the size of the chain and the running time grow to infinity. This insight is the organizing principle behind the book.

The first twelve chapters can be used for an undergraduate course, while more advanced material, suitable for graduate students, is presented in later chapters. Preliminaries and examples are presented in the first four chapters; The most useful probabilistic techniques for bounding mixing times, coupling and stationary stopping times, appear in chapters 5-6   Methods to prove lower bounds and card shuffling are in the next two chapters. The connection to electrical networks in Chapter 9 is a key tool to analyze hitting and cover times in Chapters 10-11. Eigenvalues  are studied and utilized to bound mixing in Chapters 12-13.   Chapter 14 uses the transportation metric to give an effective recipe for coupling, which is crucial in the analysis of the Ising model in Chapter 15. Highlights in the remaining chapters include the Ising model of Statistical Physics, Martingale methods, and the cutoff phenomenon, when the total variation distance to stationarity drops rapidly at a prescribed time. 


Related Presentation: