Markov Chains and Mixing Times

The mixing time of a Markov chain is the number of steps needed for this convergence to happen, to a suitable degree of accuracy.

In this situation, rapid mixing of the Markov chain means that one does not have to perform a huge number of shuffles to reach a sufficiently randomized state.

Beyond card games, similar considerations arise in the behavior of the physical systems studied in statistical mechanics, and of certain randomized algorithms.

[5] The final chapter of this part discusses the connection between the spectral gap of a Markov chain and its mixing time.

[6] The second part of the book includes many more examples in which this theory has been applied, including the Glauber dynamics on the Ising model, Markov models of chromosomal rearrangement, the asymmetric simple exclusion process in which particles randomly jump to unoccupied adjacent spaces, and random walks in the lamplighter group.

A guest chapter by Jim Propp and David B. Wilson describes coupling from the past, a method for obtaining samples drawn exactly from the stationary distribution rather than (as one obtains from Markov chain Monte Carlo methods) approximations to this distribution.

[2] Reviewer László Lakatos calls it "a brilliant guide to the modern theory of Markov chains".