Master Syscom & Computer Science – Year 2015-2016 – Fall Semester
News feed
- The course starts on Wednesday, September 21, at 2:15 PM in room INM 11. <!–
- Info about the midterm exam: takes place on Wedneday, April 20, from 8:15 AM until 10:00 AM, in room INM 10. Allowed material: two handwritten single-sided A4 pages.
- Info about the final exam: takes place on Tuesday, June 28, from 12:15 PM until 3:15 PM, in room CO 3. Allowed material: four handwritten single-sided A4 pages.
–>
General
- Course description
<!–
- Project’s page
–>
- Grading: (to be confirmed)
- Midterm: 20%
- Mini-project: 20%
- Final exam: 60%
- Grade = 20% midterm + 20% mini-project + 60% final exam
Staff
Teachers E-mail Voice Office Office Hours Olivier Lévêque, IC-LTHI olivier.leveque#epfl.ch 021 693 81 12 INR 132 by appointment Nicolas Macris, IC-LTHC nicolas.macris#epfl.ch 021 693 81 14 INR 134 by appointment TA E-mail Voice Office Office Hours Wei Liu, IC – LTHC wei.liu#epfl.ch 021 693 13 57 INR 038 by appointment Jean Barbier, IC – LTHC jean.barbier#epfl.ch 021 693 81 11 INR 139 by appointment
Schedule
Type Day Hour Room Lectures Wednesday 2:15 PM – 4:00 PM INM 11 Exercise Sessions Thursday 10:15 AM – 12:00 PM INM 11
Detailed Program
Lecture notes for the first four weeks of the course (regrouped in three parts): [to be eventually updated/improved]
- Markov chains, classification of states
- Recurrence/transience, null/positive recurrence, stationary distribution
- Ergodic theorem, coupling argument
Date Subject Wednesday, September 21 (OL) 1. General introduction, Markov chains Wednesday, September 28 (OL) 2. Classification of states, periodicity, recurrence, transience Wednesday, October 5 (OL) 3. Positive-recurrence, null-recurrence, transience, stationary distribution, two theorems Wednesday, October 12 (OL) 4. Proof of the ergodic theorem, coupling argument Wednesday, October 19 (NM) 5. Detailed balance, rate of convergence, spectral gap, mixing times Wednesday, October 26 (NM) 6. Rate of convergence: proofs Wednesday, November 2 (NM) 7. Cutoff phenomenon Wednesday, November 9 Midterm Wednesday, November 16 (OL) 8. Sampling: introduction and general methods, Metropolis-Hastings algorithm Wednesday, November 23 (OL) 9. Applications: function minimization, coloring problem Wednesday, November 30 (NM) 10. Ising model, Glauber dynamics Wednesday, December 7 (OL) 11. Exact simulation: coupling from the past Wednesday, December 14 (NM) 12. Exact simulation: application to the Ising model Wednesday, December 21 Mini-project competition
Homeworks
Problem sets Date Due Solutions Homework 1 Sept 22 Sept 28 Solutions 1 Homework 2 Sept 29 Oct 5 Solutions 2 Homework 3 Oct 6 Oct 12 Solutions 3 Homework 4 Oct 13 Oct 19 Solutions 4 Homework 5 Oct 20 Oct 26 Solutions 5 Homework 6 Oct 27 Nov 2 Solutions 6 Homework 7 Nov 3 Nov 9 Solutions 7 Midterm exam November 9, 2:15 PM November 9, 4:00 PM Midterm solutions Homework 8
(NB: Ex. 3 is optional!)April 27 May 4 Solutions 8 Homework 9 May 4 May 11 Solutions 9 Project description May 4 May 25 Homework 10 May 11 May 18 Solutions 10 Homework 11 May 18 May 25 Solutions 11 Final exam Tuesday, June 28, 12:15 PM Tuesday, June 28, 3:15 PM Final solutions
References for the course
- 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