Random Walks

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]

    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, 3rd 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 –>