Markov Chains

6 EC

Semester 1, period 1, 2

5122KANS6Y

Owner Bachelor Wiskunde
Coordinator dr. B.J.K. Kleijn
Part of Exchange Programme Faculty of Science, specialisation BSc Mathematics, year 1Minor Mathematical Themes, year 1Bachelor Wiskunde, year 3Dubbele bachelor Wis- en Natuurkunde, year 3Dubbele bachelor Wiskunde en Informatica, year 3

Course manual 2022/2023

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 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

 

Activity

Number of hours

Lecture

26

Final exam

3

Midterm exam

~3

Seminar

28

Self-study

108

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 A-6.4, an other arrangement will be proposed in consultation with the study advisor.

Assessment

Item and weight Details

Final grade

5%

Homework 1

5%

Homework 2

30%

Deeltoets

5%

Homework 3

5%

Homework 4

50%

Tentamen

Must be ≥ 5

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 homework will count for 20% towards the final grade, the midterm exam for 30% and the final exam for 50%, provided 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 have a mid-term grade of 6 or higher and hand in the two-hour version of the final exam.

No-mid-term the homework will count for 20% towards the final grade and the final exam for 80%, provided 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 three-hour version of the final exam.

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 the homework, midterm and final exam.

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. The homework will be graded and returned to the students with feedback. Please note that the rules regarding fraud and plagiarism (see below) also apply to 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

The course is tentatively structured as follows. We may deviate from the schedule; see canvas for the most up-to-date schedule.

Week numbers

 Subjects Study Material
1 Definition and basic properties, class structure, hitting probabilities Sections 1.1 - 1.3
2 Hitting times, strong Markov property, probability generating functions Sections 1.3 - 1.4 + generating functions
3 Recurrence and transience, random walks Sections 1.5 - 1.6
4 Invariant distributions Section 1.7
5 Convergence to equilibrium Section 1.8
6 Time-reversal of Markov chains Sections 1.8 - 1.9
7 Ergodic Theorem, recap Chapter 1 Section 1.10 (Sections 1.1 - 1.9)
8 Midterm exam Sections 1.1 - 1.9
9 Q-matrices, continuous-time random processes, properties of the exponential distribution Sections 2.1 - 2.3
10 Poisson processes Section 2.4
11 Birth processes, jump chain, explosion Section 2.5 - 2.7
12 Class structure, absorption probabilities, hitting times, recurrence and transience Sections 3.1 - 3.4
13 (convergence to) invariant distributions of continuous-time Markov chains Sections 3.5 - 3.6
14 An application (just for fun) Either one of Sections 5.1-5.5
15 Recap (Sections 2.1 - 2.7, 3.1 - 3.6)
16 Final exam  

 

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

Processed student feedback

Below you will find the adjustments in the course design in response to the student feedback.

Contact information

Coordinator

  • dr. B.J.K. Kleijn

Staff

  • Philip Boeken
  • Siebe Verheijen