Markov Chains and Mixing Times is a magical
book, managing to be both friendly and deep. It gently introduces
probabilistic techniques so that an outsider can follow. At the same
time, it is the first book covering the geometric theory of Markov
chains and has much that will be new to experts. It is certainly THE
book that I will use to teach from. I recommend it to all comers, an
amazing achievement.
—Persi Diaconis, Mary V. Sunseri Professor
of Statistics and Mathematics, Stanford University
Mixing times are an active research topic
within many fields from statistical physics to the theory of
algorithms, as well as having intrinsic interest within mathematical
probability and exploiting discrete analogs of important geometry
concepts. The first edition became an instant classic, being
accessible to advanced undergraduates and yet bringing readers close
to current research frontiers. This second edition adds chapters on
monotone chains, the exclusion process and hitting time
parameters. Having both exercises and citations to important research
papers it makes an outstanding basis for either a lecture course or
self-study.
—David Aldous, University of California,
Berkeley
Mixing time is the key to Markov chain Monte
Carlo, the queen of approximation techniques. With new chapters on
monotone chains, exclusion processes, and set-hitting, Markov
Chains and Mixing Times is more comprehensive and thus more
indispensable than ever. Prepare for an eye-opening mathematical
tour!
—Peter Winkler, Dartmouth College
The study of finite Markov chains has recently
attracted increasing interest from a variety of researchers. This is
the second edition of a very valuable book on the subject. The main
focus is on the mixing time of Markov chains, but there is a lot of
additional material.
In this edition, the authors have taken the opportunity to add new
material and bring the reader up to date on the latest research. I
have used the first edition in a graduate course and I look forward to
using this edition for the same purpose in the near future.
—Alan Frieze, Carnegie Mellon
University
This book is an introduction to the modern theory of Markov chains,
whose goal is to determine the rate of convergence to the stationary
distribution, as a function of state space size and geometry. This
topic has important connections to combinatorics, statistical physics,
and theoretical computer science. Many of the techniques presented
originate in these disciplines.
The central tools for estimating convergence times, including
coupling, strong stationary times, and spectral methods, are
developed. The authors discuss many examples, including card shuffling and the
Ising model, from statistical mechanics, and present the connection of
random walks to electrical networks and apply it to estimate hitting
and cover times.
The first edition has been used in courses in mathematics and
computer science departments of numerous universities. The second
edition features three new chapters (on monotone chains, the exclusion
process, and stationary times) and also includes smaller additions and
corrections throughout. Updated notes at the end of each chapter
inform the reader of recent research developments.
Readership
Undergraduate and graduate students interested in
the modern theory of Markov chains.