Ohio MAA talk followup links
("Big graphs, fast walks, loose bounds"—October 23, 2004)

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).

There are many on-line widgets for simulating the Ising model. Here's a nice one.

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.

David Wilson maintains an extensive page on all things related to coupling from the past. Also, here's Jeff Rosenthal's CFTP applet.

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 DepartmentFaculty & StaffEventsCoursesMajors Handbook