Course: Markov chains and algorithmic applications

General

The course starts on Thursday, September 17, 2020, at 12:15 PM on Zoom.

Please note the following about the coming special semester:

1. The lectures will be pre-recorded: this means that we kindly ask you to watch the videos of the course in advance. Here is the SWITCHTube channel of the course (but you find also the week-by-week links to the videos below).

2. On Thursdays at 12:15 PM, we will organize a 1h online Zoom session, with a review of the main points of the lecture of the week, followed by a quiz about this lecture (available in advance on the Moodle page). Zoom link for all these sessions: https://epfl.zoom.us/j/81680751479

3. On Fridays at 3:15 PM, online exercise sessions will be organized on Slack (updated October 25). Here is the link for Slack.

[NB: Official course schedule (in the highly unlikely eventuality that things come back to normal):
- Lectures on Thursday // 12:15-2:00 PM // room INM 202
- Exercise sessions on Friday // 3:15-5:00 PM // room INM 202]

Grading scheme: four graded homeworks 20% (5% each)
mini-project 20% (+5% for the winning team)

final exam 60%

The final exam will be a written exam, taking place on campus, in room PO 01, on Monday, January 18, from 4:15PM until 7:15PM.

Allowed material: all lecture notes, exercises and solutions (in paper format). No calculator, computer, smartphone or tablet allowed.

Course instructors:

Olivier Lévêque // LTHI // INR 132 // 021 693 81 12 // olivier.leveque#epfl.ch (first part of the course)
Nicolas Macris // LTHC // INR 134 // 021 693 81 14 // nicolas.macris#epfl.ch (second part of the course)

Teaching assistants:

Antoine Bodin // LTHC // antoine.bodin#epfl.ch
Alireza Modirshanechi // LCN // AI 2101 // 021 695 52 44 // alireza.modirshanechi#epfl.ch
Adrien Vandenbroucque // IC master student // adrien.vandenbroucque#epfl.ch

References:

- Geoffrey R. Grimmett, David R. Stirzaker, Probability and Random Processes, 3rd edition, Oxford University Press, 2001

- D. Levin, Y. Peres, E. Wilmer, Lecture Notes on Markov Chains and Mixing Times, 2nd edition, AMS, 2017

Week 1 (September 17-18)

General introduction, Markov chains, classification of states, periodicity

Group on campus for the exercises on Friday: B (Sciper modulo 3 = 1)
TA on campus: Adrien Vandenbroucque

Week 2 (September 24-25)

Recurrence, transience, positive/null-recurrence

Group on campus for the exercises on Friday: A (Sciper modulo 3 = 0)
TA on campus: Antoine Bodin

Week 3 (October 1-2)

Stationary and limiting distribution, two theorems

Group on campus for the exercises on Friday: C (Sciper modulo 3 = 2)
TA on campus: Alireza Modirshanechi

Lecture 3.1 URL
Lecture 3.2 URL

In this video (and in the corresponding slide), the proof of the proposition (with the doubly-stochastic matrix $P$ and the uniform stationary distribution $\pi$ ) has a bug: it should be a sum over $i$ and not $j$ .
Lecture 3.3 URL
Lecture 3 slides File
lecture_notes3.pdf File
Lecture 3 quiz File
Lecture 3 quiz: solutions File
Homework 3 File

Week 4 (October 8-9)

Proof of the ergodic theorem, coupling argument

Group on campus for the exercises on Friday: B (Sciper modulo 3 = 1)
TA on campus: Adrien Vandenbroucque

Lecture 4.1 URL
Lecture 4.2 URL
Lecture 4.3 URL
Lecture 4 slides File
lecture_notes4.pdf File
Lecture 4 quiz File
Lecture 4 quiz: solutions File
Graded Homework 4 Assignment

In exercise 1, I replaced the notation max by sup, as the sets are (potentially) infinite. This is also to be coherent with the notation used in the lectures.
In exercise 2, S is finite, so the notation max can stay.
Anyway, all this does not change a single bit of what you have to do for this homework :)

Week 5 (October 15-16)

Detailed balance, rate of convergence, spectral gap, mixing time

Group on campus for the exercises on Friday: A (Sciper modulo 3 = 0)
TA on campus: Antoine Bodin

Lecture 5.1 URL

Sorry, as this one is slightly longer than the others. The last 5 minutes are a digression about physics: for those interested...
Lecture 5.2 URL
Lecture 5.3 URL
Lecture 5 slides File
lecture_notes5.pdf File
Lecture 5 quiz File
Lecture 5 quiz: solutions File
Homework 5 File

Week 6 (October 22-23)

Rate of convergence: proofs

Group on campus for the exercises on Friday: C (Sciper modulo 3 = 2)
TA on campus: Alireza Modirshanechi

Lecture 6.1 URL
Lecture 6.2 URL
Lecture 6.3 URL

Sorry, as at the very end of the proof of the lemma, a factor $\sqrt{\pi_j}$ is missing in the video: this has been corrected in the slides.
Lecture 6.4 URL

Yes, you are right: the total time for these 4 videos is 1h45, not 1h30...
Lecture 6 slides File
lecture_notes6.pdf File
Lecture 6 quiz File

quiz corrected...
Lecture 6 quiz: solutions File

... as well as the solutions
Graded Homework 6 Assignment