Course: Markov chains and algorithmic applications

Weekly outline

General
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)
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)
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)
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
- Solutions 3 File
Week 4 (October 8-9)
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 :)
- Solutions 4 File
Week 5 (October 15-16)
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
- Solutions 5 File
  9.1.2021: computation mistake corrected in the solution of exercise 3
Week 6 (October 22-23)
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
- Solutions 6 File
Week 7 (October 29-30)
Week 7 (October 29-30)
Cutoff phenomenon
Exercises on Friday: by Zoom and Slack
- Lecture 7.1 URL
- Lecture 7.2 URL
- Lecture 7.3 URL
  Yes, sorry: again 15 minutes longer than 1h30 in total...
- Lecture 7 slides File
- lecture_notes7.pdf File
- Lecture 7 quiz File
- Lecture 7 quiz: solutions File
- Homework 7 File
- Solutions 7 File
Week 8 (November 5-6)
Week 8 (November 5-6)
Sampling: introduction, examples of high dimensional distributions, and the metropolis Hastings algorithm
Exercises on Friday: by Zoom and Slack
Week 9 (November 12-13)
Week 9 (November 12-13)
Function minimization, simulated annealing, introduction to the coloring problem
Discussion and quiiz session Thursday Nov 12 at 12h15-13h (see zoom link on top of page)
Extended deadline for graded hmw: Thursday Nov 12 at 23:59
Exercises on Friday: by Zoom and Slack
Week 10 (November 19-20)
Week 10 (November 19-20)
Analysis of the coloring problem
Exercises on Friday: by Zoom and Slack
Week 11 (November 26-27)
Week 11 (November 26-27)
Ising model, Glauber dynamics for the Ising model, general heat bath dynamics
Exercises on Friday: by Zoom and Slack
Week 12 (December 3-4)
Week 12 (December 3-4)
Exact simulation: coupling from the past

Exercises on zoom and slack
Week 13 (December 10-11)
Week 13 (December 10-11)
Exact simulation: proof of Propp-Wilson theorem
Monotone coupling and application to the Ising model
No hmw: session devoted to miniproject
Week 14 (December 17)
Week 14 (December 17)
Mini-project competition on Thursday, December 17, 12:15-2:00 PM, by Zoom
Course mini-project (2020-2021)
Course mini-project (2020-2021)
- Project description File
- Project submission Assignment
  Please submit one report and code per team only, specifying the name of the team as well the team members in the report (so no need to upload 3 times).
- Github page with the datasets URL
- Competition results File
- Link to the AIcrowd website URL
- TA team notebook URL