Hardcover ISBN:  9781470429621 
Product Code:  MBK/107 
List Price:  $84.00 
MAA Member Price:  $75.60 
AMS Member Price:  $67.20 
Electronic ISBN:  9781470442323 
Product Code:  MBK/107.E 
List Price:  $84.00 
MAA Member Price:  $75.60 
AMS Member Price:  $67.20 

Book Details2017; 447 ppMSC: Primary 60; 65; 68; 82;
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.ReadershipUndergraduate and graduate students interested in the modern theory of Markov chains.

Table of Contents

Basic methods and examples

Introduction to finite Markov chains

Classical (and useful) Markov chains

Markov chain Monte Carlo: Metropolis and Glauber chains

Introduction to Markov chain mixing

Coupling

Strong stationary times

Lower bounds on mixing times

The symmetric group and shuffling cards

Random walks on networks

Hitting times

Cover times

Eigenvalues

The plot thickens

Eigenfunctions and comparison of chains

The transportation metric and path coupling

The Ising model

From shuffling cards to shuffling genes

Martingales and evolving sets

The cutoff phenomenon

Lamplighter walks

Continuoustime chains

Countable state space chains

Monotone chains

The exclusion process

Cesàro mixing time, stationary times, and hitting large sets

Coupling from the past

Open problems

Background material

Introduction to simulation

Ergodic theorem

Solutions to selected exercises


Additional Material

Reviews

Taking a recently emerged topic with a massive research literature and writing a textbook that can take a student from basic undergraduate mathematics to the ability to read current research papers is a hugely impressive achievement. This book will long remain the definitive required reading for anyone wishing to engage the topic more than superficially.
David Aldous, Mathematical Intelligencer 
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 selfstudy.
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 sethitting, Markov Chains and Mixing Times is more comprehensive and thus more indispensable than ever. Prepare for an eyeopening 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 
Praise for the first edition: 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 
In this book, [the authors] rapidly take a wellprepared undergraduate to the frontiers of research. Short, focused chapters with clear logical dependencies allow readers to use the book in multiple ways.
CHOICE Magazine


RequestsReview Copy – for reviewers who would like to review an AMS bookDesk Copy – for instructors who have adopted an AMS textbook for a courseExamination Copy – for faculty considering an AMS textbook for a coursePermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Reviews
 Requests
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.
Undergraduate and graduate students interested in the modern theory of Markov chains.

Basic methods and examples

Introduction to finite Markov chains

Classical (and useful) Markov chains

Markov chain Monte Carlo: Metropolis and Glauber chains

Introduction to Markov chain mixing

Coupling

Strong stationary times

Lower bounds on mixing times

The symmetric group and shuffling cards

Random walks on networks

Hitting times

Cover times

Eigenvalues

The plot thickens

Eigenfunctions and comparison of chains

The transportation metric and path coupling

The Ising model

From shuffling cards to shuffling genes

Martingales and evolving sets

The cutoff phenomenon

Lamplighter walks

Continuoustime chains

Countable state space chains

Monotone chains

The exclusion process

Cesàro mixing time, stationary times, and hitting large sets

Coupling from the past

Open problems

Background material

Introduction to simulation

Ergodic theorem

Solutions to selected exercises

Taking a recently emerged topic with a massive research literature and writing a textbook that can take a student from basic undergraduate mathematics to the ability to read current research papers is a hugely impressive achievement. This book will long remain the definitive required reading for anyone wishing to engage the topic more than superficially.
David Aldous, Mathematical Intelligencer 
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 selfstudy.
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 sethitting, Markov Chains and Mixing Times is more comprehensive and thus more indispensable than ever. Prepare for an eyeopening 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 
Praise for the first edition: 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 
In this book, [the authors] rapidly take a wellprepared undergraduate to the frontiers of research. Short, focused chapters with clear logical dependencies allow readers to use the book in multiple ways.
CHOICE Magazine