Markov chains and mixing times. With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. (English) Zbl 1160.60001

Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L.

Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4739-8/hbk). xvii, 371 p. (2009).

This book by David Levin, Yuval Peres and Elizabeth Wilmer is a beautiful introduction to Markov chains and the analysis of their convergence towards a stationary distribution. The text is divided into two parts. In the first part the authors give an elementary introduction to Markov chains and discuss many classical examples of Markov chains on different state spaces, Markov chain Monte Carlo methods and introduce mixing times. The focus is on techniques such as coupling, strong stationary times and spectral methods that are important for estimating mixing times. The material is complemented by many illustrative examples from statistical mechanics or theoretical computer science as for example the Ising model or random walks on networks. My favorite application is the mathematical analysis of card shuffling as a random walk on the symmetric group.
The second part contains more advanced material that leads the reader to recent research topics. Path coupling is introduced to derive bounds for the mixing time of a Markov chain on a connected graph. For the Ising model the Glauber dynamics on various graphs above and below the critical temperature are discussed. Other themes in this part are the cutoff phenomenon and the evolving set process of a Markov chain. Furthermore, short expositions on continuous time chains and the case of countable state space are given. The second part closes with a chapter by J.G. Propp and D.B. Wilson on their coupling from the past method.
The first part of the book requires only basic knowledge of probability and linear algebra and is therefore a good starting point for a first course on Markov processes. The material is supplemented by a large number of exercises and solutions. The underlying principles are carefully explained and well motivated by the authors. Personally, I enjoyed very much the lucid and clear writing style of the exposition in combination with full mathematical rigor and the fascinating relations of the theory of Markov chains to several other mathematical areas.

Reviewer: H. M. Mai (Berlin)

MSC:

60-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to probability theory
60J10	Markov chains (discrete-time Markov processes on discrete state spaces)

Keywords:

Markov chains; mixing times; Markov chain Monte Carlo; coupling; Ising model; hitting times