MATS255 Markov processes

Course data

Lectures: Mon 12:15–14:00 MaD380 and Tue 14:15–16:00 MaD380 (29.10.2012 – 4.12.2012).

Exercises: Mon 10:15–12:00 MaD355 (5.11.2012 – 10.12.2012).

Instructors: Lasse Leskelä and Mikko Kuronen

Course data in Korppi: https://korppi.jyu.fi/kotka/r.jsp?course=134481

This course replaces the old course MATS252 Stochastic processes 1. After this course you can proceed to more advanced topics by attending MATS453 Reading seminar on Markov processes in the spring.

Initial distribution and transition matrix
Simulation of paths
Irreducibility and aperiodicity
Existence and uniqueness of equilibrium distribution
Convergence to equilibrium distribution
Monte Carlo algorithms

Learning outcomes

After completing the course the participant:

Can compute the distribution of a finite Markov process using its transition matrix
Can simulate a path of a Markov process using independent random variables
Recognizes when a Markov process has a unique equilibrium distribution
Can numerically compute the expectation of a discrete distribution using the Metropolis algorithm
Knows applications of Markov processes in natural sciences, computer science, and economics

Literature

The lectures shall closely follow Chapters 1–5 in the textbook

David A. Levin, Yuval Peres, Elizabeth L. Wilmer.
Markov Chains and Mixing Times.
American Mathematical Society 2008.

See links for other recommended material.

Handouts and solutions

There will be no separate lectures notes distributed, except possibly for selected topics which are not covered in the excellent textbook which is available online. The students are encouraged to write down and distribute their own notes with each other. The same goes for exercise solutions. Because written solutions to the exercises shall not be systematically delivered, it is a good idea to compare and share written solutions with other students.

Language

The primary language of the lectures is English. The primary language of the exercises will be Finnish, while English may be used as a secondary language.

Evaluation

The course is completed by passing a written exam and two project assignments. A successful completion of the project assignments is a prerequisite for attending the exam. The course grade is obtained from the formula

  g = min(floor(max(x+y+z-14,0)/3),5),

where

  x = points from the final exam (max 24)
  y = points from the project assignments (max 6)
  z = bonus points from the weekly exercises (max 6)

The threshold for the maximum grade is 29 points, and the course can be passed with 17 points.

Exercises

The weekly exercises are not compulsory, but they are strongly recommended. Indeed, obtaining the maximum grade without any bonus points from the exercises will be rather difficult.

You can mark a problem solved if you think that you understand it well enough to explain its solution to the others.
The solution does not need to be 100% correct or 100% complete.
The solution does not need to be based on your own original ideas. You are allowed—in fact recommended— to cooperate with others while solving the problems.

Five solved problems yields one bonus point, so that the bonus points from the exercises are given by

  z = min(floor(w/5),6),

where w is the total number of exercises marked as solved.

Course workload

The major part of the workload consists of independent study (solving the exercises, finding out how things work, etc.). Passing the course successfully requires allocating sufficient weekly time for independent study.

Weekly independent study  (6 x 8 h) 48 h
Lectures                 (10 x 2 h) 20 h
Exercise classes          (6 x 2 h) 12 h
Project work              (2 x 5 h) 10 h
Preparing for the exam    (1 x 8 h)  8 h
Computer labs             (1 x 2 h)  2 h
Reading seminar           (1 x 4 h)  4 h
Exam                      (1 x 4 h)  4 h
----------------------------------------
Total                              108 h

1 cr amounts to 27 h total work -> 4 cr equals 108 h of work.

Prerequisites

Elementary probability (e.g. MATA271 Stochastic models or TILA120 Probability A) and linear algebra (e.g. MATA121 Linear Algebra and Geometry 1). The course MATA261 Introduction to stochastics is recommended but not mandatory.

MATS255 Markov processes (4 cr)