Ohio MAA talk followup links
Olle Häggstrom's book, Finite Markov Chains and Algorithmic Applications, is an excellent undergraduate math-major level introduction to almost everything discussed in the talk. See also Dana Randall's CS-targeted expository article on Mixing (pdf version here) from FOCS 2003.
Brad Mann has written a wonderful undergraduate-level exposition of the ``seven shuffles suffice'' result. See also the 1986 American Mathematical Monthly article, "Shuffling cards and stopping times," by David Aldous and Persi Diaconis (available in JSTOR here).
Alastair Sinclair's monograph, Algorithms for Random Generation and Counting, covers the connections between approximate counting and approximate sampling.
Russ Bubley's monograph, Randomized Algorithms: Approximation, Generation, and Counting discusses many modern applications of coupling and path coupling.
For classical Markov chain exposition, nothing beats the lovely account (of Polya's theorems on recurrence of lattice RW in 1 and 2 dimensions, transience in dimensions 3 and above) in Peter Doyle and J. Laurie Snell's Random Walks and Electrical Networks—now available on-line!
|Back to Elizabeth Wilmer's home page|
|Mathematics Department—Faculty & Staff—Events—Courses—Majors Handbook|