xvi PREFACE For the Expert Several other recent books treat Markov chain mixing. Our account is more comprehensive than those of aggstr¨ om (2002), Jerrum (2003), or Montenegro and Tetali (2006), yet not as exhaustive as Aldous and Fill (1999). Norris (1998) gives an introduction to Markov chains and their applications, but does not focus on mix- ing. Since this is a textbook, we have aimed for accessibility and comprehensibility, particularly in Part I. What is different or novel in our approach to this material? Our approach is probabilistic whenever possible. We introduce the ran- dom mapping representation of chains early and use it in formalizing ran- domized stopping times and in discussing grand coupling and evolving sets. We also integrate “classical” material on networks, hitting times, and cover times and demonstrate its usefulness for bounding mixing times. We provide an introduction to several major statistical mechanics models, most notably the Ising model, and collect results on them in one place. We give expository accounts of several modern techniques and examples, including evolving sets, the cutoff phenomenon, lamplighter chains, and the L-reversal chain. We systematically treat lower bounding techniques, including several ap- plications of Wilson’s method. We use the transportation metric to unify our account of path coupling and draw connections with earlier history. We present an exposition of coupling from the past by Propp and Wilson, the originators of the method.
Previous Page Next Page