Workshop
Home
Schedule
(w/links)
Speakers and organizers
References
Book
Questions?
References
Naturally our presentation of the material owes a huge debt to other expositors. Aldous and Fill have made available a draft of their monograph-in-progress on random walks on finite graphs. The books of Diaconis, Jerrum and Sinclair, and the survey paper by Lovász, while written at a higher level, include many wonderful topics. Doyle and Snell is a perfect account of the electrical networks material it covers, while Häggström's undergraduate-level book on Markov chains has a different emphasis.
Accessible to undergraduates
- Aldous, D. and Diaconis, P. "Shuffling Cards and Stopping Times." Amer. Math. Monthly 93, 333-348, 1986.
- Doyle, P. G. and Snell, J. L. Random Walks and Electric Networks. Carus Mathematical Monographs, 22. Mathematical Association of America, Washington, DC, 1984. (An electronic edition is available at http://front.math.ucdavis.edu/math.PR/0001057.)
- Häggström, O. Finite Markov Chains and Algorithmic Applications. London Mathematical Society Student Texts, 52. Cambridge University Press, Cambridge, 2002.
- Jerrum, M. Counting, Sampling and Integrating: Algorithms and Complexity. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2003. Draft chapters available at http://homepages.inf.ed.ac.uk/mrj/pubs.html.
More advanced
- Aldous, D. and Fill, J. Reversible Markov Chains and Random Walks on Graphs. Monograph in preparation. Draft available at http://www.stat.berkeley.edu/users/aldous/RWG/book.html.
- Diaconis, P. Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988.
- Lovász, L. ``Random walks on graphs: a survey''. In Combinatorics: Paul Erdos is Eighty (vol. 2), 1996, pp. 353-398.
- Montenegro, R. and Tetali, P. Mathematical Aspects of Mixing Times in Markov Chains. To appear in Foundations & Trends in Theoretical Computer Science, Now Publishers. Also available at http://www.math.gatech.edu/%7Etetali/PUBLIS/survey.pdf.
- Peres, Y. Probability on Trees: An Introductory Climb. Lectures on probability theory and statistics (Saint-Flour, 1997), 193–280, Lecture Notes in Math., 1717, Springer, Berlin, 1999. Also available at http://stat-www.berkeley.edu/~peres/climb.ps.
- Sinclair, A. Algorithms for Random Generation and Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkhaüser Boston, Inc., Boston, MA, 1993.
Web pages
- David Wilson's perfect random sampling page.
- Web pages for courses on Markov chains taught by Ravi Montenegro, Dana Randall, and Eric Vigoda.
