Coursebooks 2017-2018

PDF
 

Markov chains and algorithmic applications

COM-516

Lecturer(s) :

Lévêque Olivier
Macris Nicolas

Language:

English

Remarque

The same course was given in Spring 2015-2016 under the name "Random Walks".

Summary

The study of random walks finds many applications in computer science and communications. The goal of the course is to get familiar with the theory of random walks, and to get an overview of some applications of this theory to problems of interest in communications, computer and network science.

Content

Part 1: Markov chains (~6 weeks):

- basic properties: irreducibility, periodicity, recurrence/transience, stationary and limiting distributions,

- ergodic theorem: coupling method

- detailed balance

- convergence rate to the equilibrium, spectral gap, mixing times

- cutoff phenomenon

Part 2: Sampling (~6 weeks)

- classical methods, importance and rejection sampling

- Markov Chain Monte Carlo methods, Metropolis-Hastings algorithm, Glauber dynamics, Gibbs sampling

- applications: function minimization, coloring problem, satisfiability problems, Ising models

- coupling from the past and exact simulation

Keywords

random walks, stationarity, ergodic, convergence, spectral gap, mixing time, sampling, Markov chain Monte Carlo, coupling from the past

Learning Prerequisites

Required courses

Basic probability course

Basic linear algebra and calculus courses

Recommended courses

Stochastic Models for Communications (COM-300)

Important concepts to start the course

Good knowledge of probability and analysis.

Having been exposed to the theory of Markov chains.

Learning Outcomes

By the end of the course, the student must be able to:

Teaching methods

ex-cathedra course

Expected student activities

active participation to exercise sessions and implementation of a sampling algorithm

Assessment methods

midterm, mini-project, written exam

Resources

Bibliography

Various references will be given to the students during the course, according to the topics discussed in class.

Ressources en bibliothèque
Notes/Handbook

Lecture notes will be provided

Websites

Prerequisite for

This course is not so to speak a prerequisite for other courses, but could complement well the course COM-512 on Networks out of control, as well as other courses in statistics.

In the programs

  • Data Science, 2017-2018, Master semester 1
    • Semester
      Fall
    • Exam form
      Written
    • Credits
      4
    • Subject examined
      Markov chains and algorithmic applications
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      2 Hour(s) per week x 14 weeks
  • Computer Science, 2017-2018, Master semester 1
    • Semester
      Fall
    • Exam form
      Written
    • Credits
      4
    • Subject examined
      Markov chains and algorithmic applications
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      2 Hour(s) per week x 14 weeks
  • Computer Science, 2017-2018, Master semester 3
    • Semester
      Fall
    • Exam form
      Written
    • Credits
      4
    • Subject examined
      Markov chains and algorithmic applications
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      2 Hour(s) per week x 14 weeks
  • Communication Systems - master program, 2017-2018, Master semester 1
    • Semester
      Fall
    • Exam form
      Written
    • Credits
      4
    • Subject examined
      Markov chains and algorithmic applications
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      2 Hour(s) per week x 14 weeks
  • Communication Systems - master program, 2017-2018, Master semester 3
    • Semester
      Fall
    • Exam form
      Written
    • Credits
      4
    • Subject examined
      Markov chains and algorithmic applications
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      2 Hour(s) per week x 14 weeks

Reference week

MoTuWeThFr
8-9
9-10
10-11
11-12
12-13 INM202
13-14
14-15
15-16 INM11
16-17
17-18
18-19
19-20
20-21
21-22
Lecture
Exercise, TP
Project, other

legend

  • Autumn semester
  • Winter sessions
  • Spring semester
  • Summer sessions
  • Lecture in French
  • Lecture in English
  • Lecture in German