Markov Chains

Course manual 2019/2020

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 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 define the Galton Watson branching process and compute the extinction probability for various basic branching 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 can not 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, the student is expelled from the resit of this course. In case of personal circumstances, as described in OER-A Article 6.4, an other arrangement will be proposed in consultation with the study advisor.

Assessment

The homework will count for 10%. Your homework set with the lowest grade will not count towards the overall homework grade.

The final exam covers the material of the whole course. The grade of the final exam must be at least 5.0. If the grade of the final exam is less than 5.0, the course grade will be equal to the grade of the final exam and the course will not have been passed.

The retake exam will count for 100%.

Inspection of assessed work

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

Assignments

Homework exercises

• Three or four sets of homework

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

Timetable

The schedule for this course is published on DataNose.

Honours information

There is no honours extension of this course.

Additional information

Prerequisites: Stochastics 1

Also recommended: Stochastics 2

Contact information

Coordinator

• dr. J.L. Dorsman

Staff

• L. Ravner PhD