Markov Chains

6 EC

Semester 1, period 1, 2

5122KANS6Y

Owner Bachelor Wiskunde
Coordinator dr. J.L. Dorsman
Part of Exchange Programme Faculty of Science, specialisation BSc Mathematics, year 1Bachelor Wiskunde, year 3Dubbele bachelor Wis- en Natuurkunde, year 3Dubbele bachelor Wiskunde en Informatica, year 3

Course manual 2018/2019

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 disrtibution, 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, in particular branching processes and queueing theory.

Study materials

Literature

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

  • Handout Probability Generating Functions

Objectives

In general, after this course, the student will have a thorough understanding of Markov chains in continuous and discrete time, which serves as a basis for further studies in stochastic processes. More precisely:

1. Given a Markov chain, the student can determine or calculate the following properties or quantities of a Markov chain:

  • (strong) Markov property, class structure (open and closed classes)
  • (a)periodicity, (ir)reducibility, hitting times, hitting probabilities
  • (positive) recurrence, transience
  • invariant distributions
  • reversibility.

2. The student understands and is able to apply several equivalent definitions of the Poisson process.

3. The student will understand the wide applicability of Markov chains in other fields,

4. The student wiil be able to solve basic questions regarding queueing theory (including M/M/1, M/G/1, G/M/1 queues) or branching processes.

 

Teaching methods

  • Hoorcollege
  • Werkcollege
  • Zelfstudie

Learning activities

Activiteit

Aantal uur

Hoorcollege

26

Tentamen

3

Tussentoets

3

Werkcollege

28

Zelfstudie

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

Assessment

Item and weight Details

Final grade

1 (50%)

Tussentoets

1 (50%)

Tentamen

Inspection of assessed work

The date, time and location of the inspection moment are in the DataNose timetable.

Assignments

Huiswerkopdrachten

  • 3 of 4 huiswerkopdrachten

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

Weeknummer Onderwerpen Studiestof Homework deadline
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 next Monday
3 Recurrence and transience, random walks Sections 1.5 - 1.6  
4 Invariant distributions Section 1.7  
5 Convergence to equilibrium Section 1.8 next Monday
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, and invariant distributions of continuous-time Markov chains Sections 3.1 - 3.5 next Monday
13 Biological  models Section 5.1  
14 Queueing models Section 5.2 next Monday (optional)
15 Recap Chapters 2 and 5  
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 course evaluations

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

Contact information

Coordinator

  • dr. J.L. Dorsman

 

Staff

  • prof. dr. R. Nunez Queija
  • L. Ravner PhD