Markov Chains and Mixing Times (Google eBook)

Front Cover
American Mathematical Soc. - Mathematics - 371 pages
0 Reviews
This book is an introduction to the modern approach to the theory of Markov chains. The main goal of this approach is to determine the rate of convergence of a Markov chain to the stationary distribution as a function of the size and geometry of the state space. The authors develop the key tools for estimating convergence times, including coupling, strong stationary times, and spectral methods. Whenever possible, probabilistic methods are emphasized. The book includes many examples and provides brief introductions to some central models of statistical mechanics. Also provided are accounts of random walks on networks, including hitting and cover times, and analyses of several methods of shuffling cards. As a prerequisite, the authors assume a modest understanding of probability theory and linear algebra at an undergraduate level. Markov Chains and Mixing Times is meant to bring the excitement of this active area of research to a wide audience.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Classical and Useful Markov Chains
21
Metropolis and Glauber Chains
37
Introduction to Markov Chain Mixing
47
Coupling
63
Strong Stationary Times
75
Lower Bounds on Mixing Times
87
The Symmetric Group and Shuffling Cards
99
Random Walks on Networks
115
From Shuffling Cards to Shuffling Genes
217
Martingales and Evolving Sets
229
The Cutoff Phenomenon
247
Lamplighter Walks
257
ContinuousTime Chains
265
Countable State Space Chains
275
Coupling from the Past
287
Open Problems
299

Hitting Times
127
Cover Times
143
Eigenvalues
153
Eigenfunctions and Comparison of Chains
171
The Transportation Metric and Path Coupling
189
The Ising Model
201
Appendix B Introduction to Simulation
311
Solutions to Selected Exercises
327
Bibliography
353
Notation Index
363
Copyright

Common terms and phrases

Bibliographic information