## 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

## 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

<!– TO BE RESCHEDULED

–>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, 3
^{rd}edition, Oxford University Press, 2001. - D. Levin, Y. Peres, E. Wilmer, Lecture Notes on Markov Chains and Mixing Times <!–
**Why on earth is it interesting to study random walks?****1. Random walks have puzzling properties:**As an illustration, let X be the simple symmetric random walk on the integer numbers (starting from 0 and going up or down with equal probability 1/2).

a) X comes back to 0

*infinitely often*, but takes also each time an*infinite amount of time*to come back to 0, on average.b) It is very

*unlikely*that during a period of time {0,N}, X spends half the time above or below 0. What is much more likely is that X spends*either*nearly all the time above zero*or*nearly all the time below 0.c) X takes much more time getting out of the interval {-N,+N} than

*any other*ballistic motion with a preferred direction of motion.**2. The study of random walks finds many applications:**a) From the behaviour of a random walk on a graph, it is possible to infer geometric properties of the graph.

b) Let N sensor nodes be located at different places in a room. How much time do they need in order to agree on the actual temperature in the room? The study of random walks helps you answer such questions.

c) The study of random walks helps you also understand why shuffling 6 times a deck of 52 cards is sufficient!

Interested? Then join us in Spring 2014 and learn more about applications of random walks in computer and communication sciences!

Nicolas Macris and Olivier Lévêque –>