- ホーム
- > 洋書
- > 英文書
- > Science / Mathematics
Full Description
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.
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
Continuous-time chains
Countable state space chains
Monotone chains
The exclusion process
Cesaro 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
Bibliography
Notation index
Index.
