Here are some suggested topics for your project.
Feel free to choose your own topic as long as it is relevant to the course.
Please discuss your choice with me.
Using Markov chains for approximately solving hard counting problems
such as counting the number of $k$-colorings of a given graph.
Suggested references:
Chapter 9 of Häggström's book Finite Markov Chains and Algorithmic Applications.
Mark Jerrum and Alistair Sinclair,
The Markov chain Monte Carlo method: an approach to approximate counting and integration,
Chapter 12 in Approximation Algorithms for NP-hard Problems,
1996.
A puzzle by Peter Winkler:
Consider a regular hexagon in a triangular lattice.
Suppose we cover this hexagon with diamond-shaped tiles each covering two adjacent triangles.
There are three constraints: the tiles cannot overlap, every tile should be completely
inside the hexagon, and every triangle in the hexagon should be covered by a tile.
Note that a single tile placed on the lattice can have three possible orientations.
Show that in any possible covering, the number of diamonds in all three orientations
are the same.
(According to Peter Winkler, this should be obvious from a suitably drawn figure.)
Project: the problem of generating a random diamond tiling of the hexagon.
Suggested references:
M. Luby, D. Randall and A.J. Sinclair,
Markov chain algorithms for planar lattice structures,
SIAM Journal on Computing, 31:167--192, 2001.
D. B. Wilson,
Mixing times of lozenge tiling and card shuffling Markov chains,
The Annals of Applied Probability, 14(1):274--325, 2004.
Mathematical proofs (not necessarily related to Markov chains)
in which it is helpful to cook up thought experiments involving Markov chains.
References:
Olle Häggström, Problem solving is often a matter of cooking up an appropriate Markov chain,
Scandinavian Journal of Statistics 34:768--780, 2007.
The usual Monte Carlo Markov chains (Gibbs samplers and the Metropolis chains)
for sampling from a distribution only asymptotically converge to the desired
distribution. In order to be able to obtain mathematically reliable answers,
we would therefore need theoretical estimates on the mixing times.
The coupling from the past method of Propp and Wilson
on the other hand provides a perfect sample from the desired distribution.
Suggested references:
Chapter 22 of the textbook.
Chapters 10--12 of Häggström book
Finite Markov Chains and Algorithmic Applications.
A natural (and useful) generalization of Markov chains arises
when we have a collection of random variables $X_i$ that
instead of time are indexed by the vertices of a graph $G$.
A Markov random field on $G$ is such a collection of random variables
that satisfies a suitable "Markov property".
Suggested references:
Chapter 7 of the book
Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues
by Pierre Brémaud.
Chapter 7 of the book
Probability on Graphs by Geoffrey Grimmett.