News

Final Projects:

Amir Barghi: Exponents of Primitive Digraphs (PDF)

Jonathan Connell: Sampling and Counting Contingency Tables Using Markov Chains (PDF)

Dan Crytser: Continuous Time Markov Chains (PDF)

Alyssa Eisenberg: The Application of Markov Chain Monte Carlo to Infectious Diseases (PDF)

Paul Finkelstein: Music Segmentation using Markov Chain Methods (PDF)

Shahrzad Haddadan: Vigoda's Improvement on Sampling Colorings (PDF)

Zachary Hamaker: Electric Networks and Commute Time (PDF)

Seth Harris: Counting Linear Extensions of a Partial Order (PDF)

Zhiyu Liu: The Upper Bound on Time Complexity of Collisions among Random Walks on a Graph (PDF)

Andrew Lyons: Polynomial-Time Approximation of the Permanent (PDF) and slide presentation (PDF)

Yu-Han Lyu: Random-Turn Hex and Other Selection Games (PDF)

Nathan McNew: The Eigenvalue Gap and Mixing Time (PDF)

Cole Ott: Simulated Annealing (program folder)

Carter Tazio Schonwald: Bounding Mixing Time with Markov Chain Comparison: Theory and Applications (PDF)

Robert Bradford Svenson: Subgraphs-world Process in the Ising model (PDF)

Ye Tang: The Hard Disc Model (program folder)

Weifu Wang: The Road Coloring Problem (PDF)

Zhenghui Wang: Counting the Number of Eulerian Orientations (PDF)

Lin Zhao: Recurrence vs Transience in Dimensions 2 and 3 (PDF)

Abstract

Markov chains are random processes in which each state depends on the previous one. In recent years MCMC, in which Markov chains are run to get random samples, has become a major tool in applied mathematics and computer science.

Course topics include random walk, shuffling, rapid mixing, and some approximation algorithms.

Prerequisites: Basic probability and linear algebra, with the mathematical sophistication of a beginning graduate student, a well-progressing undergraduate mathematics major, or a theory-oriented CS major. In particular, Math 20 and 22/24, or CS 19/25, or permission of the instructor.

Here is a tentative syllabus:

1. Markov chain definition and examples (random walk, card shuffling)

Week 1, Häggström Chapter 2.

2. Ergodicity and Stationarity

Week 2, Häggström Chapters 4-5.

3. Reversibility and the Gibbs Sampler

Week 3, Häggström Chapters 6-7.

4. Eigenvalues and mixing time

Week 4, Häggström Chapter 8.

5. Stopping times and exact mixing

Week 5, Mixing Times article (will be supplied).

6. Counting

Week 6, Häggström Chapter 9.

7. Coupling from the Past

Week 7, Häggström Chapters 10-12.

8. Simulated Annealing

Week 8, Häggström Chapter 13.

7. Markov Random Fields

Week 9, supplementary materials.

8. The Metropolis algorithm and other applications

Week 10, supplementary materials.

Classes

Room: Kemeny Hall 004
Lectures: "2A" slot, in particular: Tuesdays 2-3:50 (with a break), and Thursdays 2-3:30.
X-hour: Wednesdays 4:15 pm--5:20pm (rare!)

Tutorials

Since the X-hour conflicts with Computer Science Colloquium, it will be used only for occasional, optional meetings. When it does occur it will be on a Wednesday, 4:15 PM - 5:20 PM, in Kemeny 004.

Staff

Instructor:

Peter Winkler -- Kemeny Hall 231 / Tel. 6-3468
Office Hours: Tuesdays, 4-5pm; Wednesdays, 2-3pm; Fridays, 11-12pm; and by appointment.

Textbook

Olle Häggström, Finite Markov Chains and Algorithmic Applications, Cambridge U. Press, 2002.
(required)

This book will be available from Wheelock Books and elsewhere.

Grading

Your grade will be based on homework, class participation, and a project (different for each student) which entails a half-hour presentation and, at the end of the term, a short paper or computer program. If the choice is a paper, it is suggested that you write the paper in LaTeX and convert to PDF via pdflatex. If you wish you can use the following sample.tex as a template; the pdf result of this source is this sample.pdf. To see examples of papers written last year for Math 100 projects, go to http://math.dartmouth.edu/~m100w10, last year's course website. (Note that the topic---Percolation---of last year's Math 100 was different.) Your choice of project will be determined by an individual discussion with the instructor during the second or third week of the term.

Homework

Homework will be assigned at each class period, due at the beginning of the next class. In some cases nothing written will be due, but any student may be called upon to present his or her homework to the class.

Assignments

Due Thursday Jan 6: In a "Binary Symmetric Channel" a bit is sent from place to place and each time it is accidentally flipped with some small fixed probability epsilon. Set this up as a Markov chain, and compute the probability that after n steps a "1" sent initially arrives as a "1".

Due Tuesday Jan 11: (a) For each chess piece (king, queen, rook, knight, bishop) determine whether the Markov chain whose states are the 64 possible positions for the piece (alone on the board) with all legal moves possible, is irreducible, aperiodic, both, or neither. (b) Consider the "random chess" Markov chain beginning in the standard opening position, where all legal moves are permitted except those which would force an end to the game. Which positions are transient?

Due Thursday Jan 13: Let G be a finite graph of maximum degree Delta, and let q = Delta+2. Let P be the Markov chain on proper q-colorings of G in which a step consists of selecting a vertex uniformly at random, and then giving it a randomly chosen legal color (which might be its old color). Show that P is ergodic.

Due Tuesday Jan 18: (a) Let G be the (partly directed) graph consisting of a C_3, a C_4 and a C_5, with two additional arcs: one from a vertex of the C_3 to a vertex of the C_4, and the second from another vertex of the C_3 to a vertex of the C_5. Let P be the simple random walk on G, where an out-neighbor from the current vertex is chosen uniformly at random. (The edges of the cycles are directed both ways.) Characterize all the stationary distributions of the Markov chain P. (b) Prove that in an irreducible Markov chain (with finite state space), all states have the same period.

Due Thursday Jan 20: (a) Determine whether the random "15 game" is irreducible and/or aperiodic. (b) How would you go about solving the version in which the opening configuration is RATE YOUR MIND PLA ?

Due Tuesday Jan 25: Problem 6.2 (all parts), p. 43 of your text.

Due Thursday Jan 27: (a) Problem 7.4, p. 52. (b) In this generalized hard-core model, assuming the graph is part of a 2-dimensional square grid, can you get the distance between the chains X and Y to shrink (probabilistically) for small lambda? How small?

Due Tuesday Feb 1: Read Chapter 8 of the text, and try to think of a better way to couple the two coloring chains.

Due Thursday Feb 3: (a) Check that the lazy version of our coloring algorithm, in which a color is chosen u.a.r. and the chain loops if it isn't legal, still satisfies detailed balance. (b) In the Dartmouth coupling, where q exceeds 3Delta so that |D| tends to go down, what is the resulting value of alpha?

Due Tuesday Feb 8: Find the paper where Jerrum shows how to approximate the number of colorings of a graph when q exceeds 2Delta, and try to read it.

Due Thursday Feb 10: Redo Jerrum's argument for fast mixing of the graph-coloring chain, using path coupling.

Due Tuesday Feb 15: Compute the transition probabilities for the Markov chain which is the reverse of the "winning streak" chain. The latter has states 0 through 10, with transitions from 0 to 1, 1 to 2, 2 to 3, etc. up to 9 to 10, and 10 to itself (corresponding to flipping a head); and from anything to 0 (corresponding to flipping a tail). All of these transitions have probability 1/2.

Due Tuesday Feb 22: Determine the parameters for the "local rule" that starts at vertex 3 of the path on vertices 1,2,3,4,5, and stops at a vertex distributed as (1/8,1/4,1/4,1/4,1/8). You may let p be the probability of moving from vertex 3, q from 2 or 4; you won't be moving from 1 or 5.

Due Thursday Feb 24: (a) Compute the exact mixing time for the cycle C_n (that is, the expected number of steps for an optimal stopping rule that gets you from vertex 0 to the uniform distribution.) (b) For what Markov chains is it the case that the naive stopping rule is optimal, for getting from state 1 to the stationary distribution?

Due Tuesday March 1: Find a stopping rule for the reverse GSR shuffle that achieves the uniform (stationary) distribution.

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Coordinator, Nancy Pompian, can be reached at 6-2014 if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.