# Coursebooks

## Markov chains and algorithmic applications

Lévêque Olivier
Macris Nicolas

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:
• 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, mini-project, written exam

#### Resources

##### Bibliography

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

##### Notes/Handbook

Lecture notes will be provided

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

### Reference week

MoTuWeThFr
8-9
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
Under construction

Lecture
Exercise, TP
Project, other

### legend

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