Random Walks on Transitive Graphs Autumn 2022

Lecturer
Prof. Vincent Tassion
Coordinator
Daniel Contreras

Content

Consider a random walker on an infinite graph (for example, the hypercubic lattice \( \mathbb{Z}^d \) or the infinite regular tree \( \mathbb{T}^d \)). At each steps the walker jumps uniformly on one of its neighbours. Does the random walker come back to its starting point? With which probability? Where is the random walker typically after \( n \) steps? Does the random walker travel with a positive speed?

The answer to these questions depend on the geometric structure of the underlying graph: growth, isoperimetry,Liouville property,... In this course, at the interface between probability and geometric group theory, we will describe the behaviour of the random walk, and relate it to the geometric properties of the underlying graphs.

Prerequisites

Lectures

Lectures will take place in-person every Tuesday from 10:15 to 12:00 at HG E 33.5.

Lecture Notes

Exercises

New exercises will be posted here on Tuesdays. Starred exercises \( (\star) \) are an important part of this course and can be evaluated at the final exam.

Office hours

If you have questions about the lecture or the exercises, you can come on Thursdays between 14:00 and 15:00 to HG E 66.2. Please send an email to the coordinator with your question before coming, so it will be answered directly by email when possible.

Literature

Random Walks on Graphs

Graph Theory

Geometric group theory

Markov Chains

Information Theory