Project: Markov Chain Mixing Times (Level 3)

How many times do you need to shuffle a deck of cards to make the deck fully random? The answer for a standard deck of cards turns out to be 7 times, at least if you use a standard riffle shuffle. While this question might seem like a bit of trivia, it is in fact an important mathematical discovery: it is an example of a rigorous estimate of the mixing time of a Markov chain.

Markov chains are a major topic in probability theory, in part due to the ubiquity and importance of Markov chain monte carlo (MCMC) algorithms in modern science. These algorithms give a practical way to sample from complicated probability distributions. The basic idea is to design a Markov chain whose stationary distribution is the desired distribution. The fundamental theorem of Markov chains then says that the distribution of this Markov chain, started from any initial configuration, converges to its stationary distribution. Thus one can get a sample by running the Markov chain for a long time. A central question in practice is to address what 'a long time' means. A failure to run the chain for long enough can lead to biased or incorrect samples. Rigorously addressing this question is the subject of Markov chain mixing times, and it constitutes an active research topic in probability theory, and more generally in mathematics, statistics, and computer science.

For the example of a deck of cards, the desired distribution is the uniform distribution on arrangements of 52 cards. This is an enormous sample space with 52! elements. The result of the first paragraph says that starting from anywhere in this astronomically large sample space, after 7 riffle shuffles, you will end up with an (essentially) uniformly random chosen point in this sample space. On the other hand, with fewer shuffles there will still be strong correlations between the original order of the cards and the final order of the cards.

This project will introduce you to this subject, and to some of the interesting mathematics that can arise. After a brief revision of Markov chains the first half of the project will focus on learning some tools for analysing mixing times. The second half of the project will then involve choosing some particular Markov chains of interest (e.g., card shuffling methods, simple random walk, Ising model, to name just a few) and analysing them. Depending on the models chosen, this could involve proving dependence on parameters (e.g., slow versus fast mixing) or investigating more detailed fast mixing results (e.g., cutoff phenomena).

Prerequsites: Markov Chains II. Probability II is desirable.

Resources: