Hints and tips:
  • You may need to look up some unfamiliar terms in the title or description to get more of a sense of what is involved.
  • If the project has "No" in the "Current Availability:" field, it is already taken or not being offered this academic year but may be available again in future years.
  • The supervisor name links to a contact details webpage so, if you are interested, you can arrange to discuss this project or even propose a related topic of your own.
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, 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://www.dbwilson.com/exact/.
Key Modules:

MTH6141 Random Processes
Other Information:
Current Availability: Yes