Markov chains and algorithmic applications
Weekly outline

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 prerecorded: 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 weekbyweek 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):
Grading scheme: four graded homeworks 20% (5% each)
 Lectures on Thursday // 12:152:00 PM // room INM 202
 Exercise sessions on Friday // 3:155:00 PM // room INM 202]
miniproject 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.chReferences:
 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

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 
Recurrence, transience, positive/nullrecurrence
Group on campus for the exercises on Friday: A (Sciper modulo 3 = 0)
TA on campus: Antoine Bodin 
Stationary and limiting distribution, two theorems
Group on campus for the exercises on Friday: C (Sciper modulo 3 = 2)
TA on campus: Alireza Modirshanechi 
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
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 :)

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
Sorry, as this one is slightly longer than the others. The last 5 minutes are a digression about physics: for those interested...


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

Yes, you are right: the total time for these 4 videos is 1h45, not 1h30...

quiz corrected...

... as well as the solutions

Cutoff phenomenon
Exercises on Friday: by Zoom and Slack

Yes, sorry: again 15 minutes longer than 1h30 in total...

Sampling: introduction, examples of high dimensional distributions, and the metropolis Hastings algorithm
Exercises on Friday: by Zoom and Slack

Function minimization, simulated annealing, introduction to the coloring problem
Discussion and quiiz session Thursday Nov 12 at 12h1513h (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

Analysis of the coloring problem
Exercises on Friday: by Zoom and Slack

Ising model, Glauber dynamics for the Ising model, general heat bath dynamics
Exercises on Friday: by Zoom and Slack

Exact simulation: coupling from the pastExercises on zoom and slack

Exact simulation: proof of ProppWilson theorem
Monotone coupling and application to the Ising model
No hmw: session devoted to miniproject

Miniproject competition on Thursday, December 17, 12:152:00 PM, by Zoom


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