Markov chains and algorithmic applications

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

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:

• Analyze the behaviour of a random walk
• Assess / Evaluate the performance of an algorithm on a graph
• Implement efficiently various sampling methods

Teaching methods

ex-cathedra course

Expected student activities

active participation to exercise sessions and implementation of a sampling algorithm

Assessment methods

midterm (20%), mini-project (20%), final exam (60%)

Resources

Bibliography

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

Ressources en bibliothèque

• Probability and random processes / Grimmett

Notes/Handbook

Lecture notes will be provided

Websites

• https://moodle.epfl.ch/course/view.php?id=15016

Moodle Link

• https://go.epfl.ch/COM-516

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.