Time and venue

Lecture:
Tuesdays, 10–12, HeHo18 E60

Exercise:
Fridays, 8–10, HeHo18 E20, fortnightly

Length

2 hours lecture + 1 hour tutorial
Credit points: 4

Theoretical background

Lectures: Probability Theory, Calculus, Linear Algebra

Target audience

Compulsory elective lecture for: Bachelor’s in Mathematics, Mathematics and Management, Mathematical Biometry; Master’s in Mathematics, Mathematics and Management, Mathematical Biometry; Teacher Education in Mathematics

Content

The lecture focuses on:

• Markov chains in discrete time and discrete state space
• Stationarity and ergodicity of Markov chains
• Markov-Chain Monte-Carlo (MCMC)
• Reversibility and coupling algorithms 

The lecture will be delivered in English.

Lecture notes

The (English) lecture notes can be found on Moodle; subject to ongoing changes.

Criteria for achieving the prerequisite

To be announced.

Examination

Admission to the examination is conditional upon having passed the prerequisite (see above). The examination takes the form of an individual oral examination (in German or English as required); dates must be arranged individually.

Exercise sheets 

The exercise sheets and marks achieved will be published on Moodle.

Literature

• David Aldous, James A. Fill. Reversible Markov Chains and Random Walks on Graphs. 2014. Unfinished monograph, recompiled version of the 2002 draft.
• Søren Asmussen, Peter W. Glynn. Stochastic Simulation: Algorithms and Analysis. Springer, New York, 2007.
• Abraham Berman, Robert J. Plemmons. Non-negative Matrices in the Mathematical Sciences. SIAM, Philadelphia, 1994.
• Pierre Brémaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues. Springer, Cham, 2nd edition, 2020.
• Steve Brooks, Andrew Gelman, Galin L. Jones, Xiao-Li Meng (eds.). Handbook of Markov Chain Monte Carlo. CRC Press, Boca Raton, FL, 2011.
• Pierre Collet, Servet Martínez, Jaime San Martín. Quasi-Stationary Distributions: Markov Chains, Diffusions and Dynamical Systems. Springer, Heidelberg, 2013.
• Amir Dembo, Ofer Zeitouni. Large Deviations Techniques and Applications. Springer, New York, 2nd edition, 1998.
• Luc Devroye. Non-Uniform Random Variate Generation. Springer, New York, 1986.
• Persi Diaconis. Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward, CA, 1988.
• Joseph L. Doob. Classical Potential Theory and Its Probabilistic Counterpart. Springer, New York, 1984.
• Rick Durrett. Essentials of Stochastic Processes. Springer, New York, 2nd edition, 2012.
• William Feller. An Introduction to Probability Theory and Its Applications, Volume I. Wiley, New York, 3rd edition, 1968.
• Dani Gamerman, Hedibert F. Lopes. Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference. Chapman & Hall/CRC, Boca Raton, FL, 2nd edition, 2006.
• James E. Gentle. Random Number Generation and Monte Carlo Methods. Springer, New York, 2nd edition, 2003.
• Geoffrey R. Grimmett, David R. Stirzaker. Probability and Random Processes. Oxford University Press, Oxford, 4th edition, 2020.
• Olle Häggström. Finite Markov Chains and Algorithmic Applications. Cambridge University Press, Cambridge, 2002.
• Roger A. Horn, Charles R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, 2nd edition, 2013.
• Mark L. Huber. Perfect Simulation. CRC Press, Boca Raton, FL, 2016.
• John G. Kemeny, J. Laurie Snell. Finite Markov Chains. Springer, New York, 1976.
• Achim Klenke. Probability Theory: A Comprehensive Course. Springer, Cham, 3rd edition, 2020.
• Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 3rd edition, 1998.
• Dirk P. Kroese, Thomas Taimre, Zdravko I. Botev. Handbook of Monte Carlo Methods. Wiley, Hoboken, NJ, 2011.
• David A. Levin, Yuval Peres. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI, 2nd edition, 2017.
• Torgny Lindvall. Lectures on the Coupling Method. Dover Publications, Mineola, NY, 2002.
• Jun S. Liu. Monte Carlo Strategies in Scientific Computing. Springer, New York, 2001.
• Sean Meyn, Richard L. Tweedie. Markov Chains and Stochastic Stability. Cambridge University Press, Cambridge, 2nd edition, 2009.
• Jesper Møller, Rasmus P. Waagepetersen. Statistical Inference and Simulation for Spatial Point Processes. Chapman & Hall/CRC, Boca Raton, FL, 2004.
• Radford M. Neal. MCMC using Hamiltonian dynamics. In Steve Brooks, Andrew Gelman, Galin L. Jones, Xiao-Li Meng (eds.), Handbook of Markov Chain Monte Carlo. CRC Press, Boca Raton, FL, 2011.
• James R. Norris. Markov Chains. Cambridge University Press, Cambridge, 1997.
• Sidney I. Resnick. Adventures in Stochastic Processes. Birkhäuser, Boston, 1992.
• Christian P. Robert, George Casella. Monte Carlo Statistical Methods. Springer, New York, 2nd edition, 2004.
• Christian P. Robert, George Casella. Introducing Monte Carlo Methods with R. Springer, New York, 2010.
• Reuven Y. Rubinstein, Dirk P. Kroese. Simulation and the Monte Carlo Method. Wiley, Hoboken, NJ, 3rd edition, 2017.
• Laurent Saloff-Coste. Lectures on finite Markov chains. In Pierre Bernard (ed.), Lectures on Probability Theory and Statistics (École d’Été de Probabilités de Saint-Flour XXVI – 1996). Springer, Berlin, 1997. Reprinted in Markov Semigroups at Saint-Flour, Springer, Heidelberg, 2012.
• Eugene Seneta. Non-negative Matrices and Markov Chains. Springer, New York, 2nd edition, 2006.
• Evgeny Spodarev. Monte Carlo simulation of random variables. Springer, 2026. To be published.
• Yuri Suhov, Mark Kelbert. Probability and Statistics by Example. Volume II, Markov Chains: A Primer in Random Processes and their Applications. Cambridge University Press, Cambridge, 2008.
• Hermann Thorisson. Coupling, Stationarity, and Regeneration. Springer, New York, 2000.
• Gerhard Winkler. Image Analysis, Random Fields and Markov Chain Monte Carlo Methods. Springer, Berlin, 2nd edition, 2003.