Level: MSci, MSc
Title: Coupling of Markov chains
Supervisor:

Prof. Mark Jerrum
Research Area: Combinatorics
Description:

Coupling of random variables is a simple but powerful method introduced by Doeblin in the 1930s. An important application of the technique is to establishing upper bounds on mixing time of Markov chains. (The mixing time of an ergodic Markov chain is the number of steps taken until it is close to its limiting distribution.) The project would cover the connection between mixing time of a Markov chain and coalescence time of a coupling, and would illustrate the method using examples drawn from application areas such as statistical physics. There is scope for novel applications, and for a potential extension of the project to "coupling from the past".
Further Reading:
  • D.A. Levin, Y. Peres and E.L. Wilmer, Markov Chains and Mixing Times. American Mathematical Society, 2008.
  • M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics – ETH Zürich. Birkhäuser, Basel, 2003.
  • D.B. Wilson, Perfectly Random Sampling with Markov Chains, http://dimacs.rutgers.edu/~dbwilson/exact/.
Key Modules:

MTH6141 Random Processes
Other Information:
Current Availability: Yes