Math 593
Graphs and Markov Chains
(Updated Summer 2012)General Information
- Math 593 section 1
- Summer 2012 Meets MTR 9:30-11:35 in RH 121 (the Linux Lab).
- Dr. Bryan Clair
- Course syllabus
- Textbook: Markov Chains and Mixing Times by Levin, Peres, Wilmer.
News
This week (6/25-6/28), relevant material from the book is in Ch 7-7.2, 12, 13.3, and 13.6.Another great reference on expanders is: S. Hoory, N. Linial, A. Wigderson, Expander Graphs and their Applications.
There's also a recent blog post by Terence Tao Thursday, 6/28 is the last day of class.
Links
- GNU Octave: Official site, reference manual.
- Monopoly: A discussion by R. Pratt. Pratt's animation of the first 40 turns. The stationary distribution. A monopoly matrix.
- Gambler's ruin applet
- Simple random walk on the integers applet
- Python program for computing random walks on the cube: cubewalk.py
- Hardcore Model
- Python programs for Markov chains on the grid: HardcoreGrid.py, hardcore_animated.py (needs cs1graphics package), convergence_of_hardcore.py.
- Pictures of configurations: Fugacity 0.5, Fugacity 2, Fugacity 5
- Python programs for Markov chains on domino tilings: DimerGrid.py, DimerDisplay.py, dimer_demo.py. The display and demo components require the cs1graphics package. Some loadable shapes: ring.txt, mickey.txt, duck.txt
- Random domino tiling of a square: square.gif
- Random domino tiling of an Aztec diamond: aztec.gif
- All lozenge tilings of a 2x2x2 hexagon.
- More lozenge tiling images by Syngola.
- James Propp's random tiling applets
References
- Markov Chains and Mixing Times, David Levin, Yuval Peres, Elizabeth Wilmer, AMS 2009. (book site)
- Finite Markov Chains and Algorithmic Applications, Olle Haggstrom, LMS Student Texts, 2002. (amazon)
- R. Kenyon, Lectures on dimers Statistical mechanics, 191--230, IAS/Park City Math. Ser., 16, Amer. Math. Soc., Providence, RI, 2009.
- S. Hoory, N. Linial, A. Wigderson, Expander Graphs and their Applications. Bulletin AMS, V43, No. 4, Oct. 2006, pg 439-561