Module leader: N Georgiou & Hugo Lo

Please see the full Module Specifications for background information relating to all of the APTS modules, including how to interpret the information below.

Aims: This module will introduce students to two important notions in stochastic processes — reversibility and martingales — identifying the basic ideas, outlining the main results and giving a flavour of some of the important ways in which these notions are used in statistics.

Learning outcomes: A student successfully completing this module will be able to:

• describe and calculate with the notion of a reversible Markov chain, both in discrete and continuous time;
• describe the basic properties of discrete-parameter martingales and check whether the martingale property holds;
• recall and apply significant concepts from martingale theory (indicative list: optional stopping, martingale convergence);
• explain how to use Foster-Lyapunov criteria to establish recurrence and speed of convergence to equilibrium for Markov chains.

Prerequisites: Preparation for this module should include a review of the basic theory and concepts of Markov chains as examples of simple stochastic processes (transition and rate matrices, irreducibility and aperiodicity, equilibrium equations and results on convergence to equilibrium), and with the definition and basic properties of the Poisson process (as an example of a simple counting process).

Further reading: Various useful textbooks at increasing levels of mathematical sophistication:

• Haggstrom (2002) “Finite Markov chains and algorithmic applications”.
• Grimmett and Stirzaker (2001) “Probability and random processes”.
• Breiman (1992) “Probability”.
• Norris (1998) “Markov chains”.
• Ross (1996) “Stochastic processes”.
• Williams (1991) “Probability with martingales”.

Some useful texts that are free on the web:

• Doyle and Snell (1984) “Random walks and electric networks”
• Kelly (1979) “Reversibility and stochastic networks”
• Kindermann and Snell (1980) “Markov random fields and their applications”
• Meyn and Tweedie (1993) “Markov chains and stochastic stability”
• Aldous and Fill (2001) “Reversible Markov Chains and Random Walks on Graphs”

Topics:

• Reversibility of Markov chains in both discrete and continuous time, computation of equilibrium distributions for such chains, application to important examples.
• Discrete time martingales, examples, application, super-martingales, sub-martingales.
• Stopping times, statements and applications of optional stopping theorem, martingale convergence theorem.
• Recurrence and rates of convergence for Markov chains, application to important examples.
• Statements and applications of Foster-Lyapunov criteria, viewed using the language of martingales.
• Statistical applications and relevance (highlighted where appropriate throughout).

Assessment:

• Complete appropriate exercises that are simple developments or extensions of aspects of the results in the module.
  

 

• Contact APTS •

Module resources