## Markov Chains and Mixing TimesThis 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 |

353 | |

363 | |

### Common terms and phrases

Aldous algorithm aperiodic Applying bits cards CFTP chain with transition Chapter Chebyshev's inequality color complete graphs compute configurations Consider constant Convergence coordinate Corollary coupling cutoff deck defined denote Diaconis edges eigenfunction eigenvalue equal example EXERCISE FIGURE finite follows function gambler's ruin Glauber dynamics graph G hardcore Hence hitting hypercube implies independent inequality integer irreducible Ising model lamplighter lazy random walk Lemma Let Xt lower bound Markov chain martingale mixing moves neighbors nlogn Note pair path permutation position probability 1/2 probability distribution Proposition prove random transpositions random variable recurrent reversible chains riffle shuffle right-hand side sample satisfies Section sequence shows simple random walk space spectral gap stationary distribution stationary distribution TT step strong stationary Suppose tmix total variation distance transition matrix triangle inequality TT(X uniform distribution uniformly at random update upper bound vector vertex set vertices visits walk on G