NOTES

Markov Chains and Mixing Times

Markov Chains and Mixing Times by David Levin, Yuval Peres, and Elizabeth Wilmer.

Overview

Make no mistake of it, markov chains are the coolest thing ever. That being said, I have found my own study of them has developed in fits and starts, as I study specific applications. I was attracted to this book as it promises to introduces techniques to calculate the asymptotes geometrically, showing where chains converge to stationarity. I have known this to be possible for over a year, but I didn’t know what math foundations were needed to approach it (I kept thinking this would best be assessed using differential geometry). The book says we’re good to go with probability and linear algebra, and a certain level of mathematical “maturity” (we’ll see if I have that), so I think we’re good to dive in.

The key idea that forms the central thread of this book is mixing time, which is the number of steps it takes for a particular chain to converge to the stationary distribution. From the physics perspective, the material would be mixed at this point.