Markov Chains

Course manual 2024/2025

Course content

The course consists of three parts. The first (and also largest) part is an introduction to discrete-time Markov chains in which we treat class structure, hitting times, absorption probabilities, strong Markov property, random walks, invariant distributions, convergence to equilibrium and reversibility.

The second part deals with continuous-time Markov chains where we focus on the exponential distribution, the Poisson process and embedded discrete-time Markov chains, among other things.

In the final part of the course we consider the connection with harmonic analysis and discuss applications of Markov chains, such as branching processes and queueing theory.

Study materials

Literature

• James R. Norris, 'Markov Chains', Cambridge University Press.

• Handout Probability Generating Functions

Objectives

• The student is able to prove or disprove that a given discrete-time stochastic process on a discrete state space is a Markov chain.
• The student is able to compute the transient probabilities of a Markov chain in discrete time in terms of the eigenvalues of the transition matrix.
• The student is able to classify the states of a Markov chain into transient and recurrent.
• The student is able to determine open and closed classes of a Markov chain.
• The student is able to characterize the entrance (first passage, absorption) probabilities and expected entrance (first passage, absorption) times for a given transition matrix; and be able to compute these for chains with a small number of states and/or a transition matrix with a special structure (in particular birth-death processes).
• The student is able to characterize the distribution of entrance (first passage, absorption) times for a given transition matrix in terms of its generating function; and be able to compute these for chains with a small number of states and/or a transition matrix with a special structure (in particular birth-death processes).
• The student is able to characterize (i.e. verify) stationary distributions for a Markov chain with given transition matrix; and be able to compute these for chains with a small number of states and/or a transition matrix with a special structure (in particular birth-death processes).
• The student is able to prove convergence to a stationary distribution for an irreducible, positive recurrent Markov chain (both for aperiodic and periodic chains).
• The student is able to verify reversibility of a Markov chain using detailed balance conditions and use these to compute stationary distributions for these chains.
• The student is able to formulate the connection between a continuous-time Markov chain on a discrete state space with its embedded jump-chain, and use this to conclude on all the aforementioned items for continuous time Markov processes.
• The student is able to prove the equivalence of three definitions of a Poisson process.
• The student is able to prove the splitting and merging properties of (independent) Poisson processes.
• The student is able to determine the stationary queue-length and waiting-time distributions in several basic queueing models using embedded Markov chains.
• The student is able to understand the wide applicability of Markov chains in other fields.

Teaching methods

• Lecture
• Self-study
• Seminar

Learning activities

Attendance

Programme's requirements concerning attendance (OER-B):

• Each student is expected to actively participate in the course for which he/she is registered.
• If a student cannot be present due to personal circumstances with a compulsory part of the programme, he / she must report this as quickly as possible in writing to the relevant lecturer and study advisor.
• It is not allowed to miss obligatory parts of the programme's component if there is no case of circumstances beyond one's control.
• In case of participating qualitatively or quantitatively insufficiently, the examiner can expel a student from further participation in the programme's component or a part of that component. Conditions for sufficient participation are stated in advance in the course manual and on Canvas.
• In the first and second year, a student should be present in at least 80% of the seminars and tutor groups. Moreover, participation to midterm tests and obligatory homework is required. If the student does not comply with these obligations, it can be decided to deny the positive effects of homework to be counted towards the final grade of the course. In case of personal circumstances, as described in OER-A Article A-6.4, a different arrangement will be proposed in consultation with the study advisor.

Assessment

For the calculation of the final grade, every student has two options, the standard option and the no-mid-term option. Correspondingly, there are two versions of the final exam, one of two hours and one of three.

Standard the midterm exam for 40% and the final exam for 60%, provided the grade for the mid-term exam is at least a 6.0  and the grade for the final exam is at least a 5.0. If the grade for the final exam is less than 5.0, then this grade is the final grade. To opt for this version, the student has to hand in the two-hour version of the final exam.

No-mid-term the final exam counts for 100% of the final grade. To opt for this version, the student has to hand in the three-hour version of the final exam.

Retake If a student decides to take the retake exam, the grade of the retake will count for 100% towards the final grade, and will thus override the grades obtained for midterm and final exams.

Homework does not count toward the final grade for the course.

Inspection of assessed work

The manner of inspection will be communicated via the digitial learning environment.

Assignments

Homework exercises

• Four sets of homework

Four sets of homework will be posted with a deadline on canvas. Handing in homework assignments is voluntary. Homework is corrected and discussed with the student. Homework is not graded and does not count towards the final grade for the course.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Honours information

There is no honours extension of this course.

Additional information

Prerequisites: Stochastics 1

Also recommended: Stochastics 2

Processed student feedback

Based on experiences in past years, homework is now voluntary and does not count towards the final grade for the course

Contact information

Coordinator

• dr. B.J.K. Kleijn

Staff

• Duarte Fragoso
• Alex Hanrath