Random Walk, Trees and Graphs

Yueyun Hu

In this course we study certain aspects of discrete probability on infinite graphs (in particular on infinite trees). These domains are full of interesting, sometimes surprising results, many of which are closely related to other areas of probability theory and theoretical computer science. Below is a tentative planning:
  1. Random walk and electrical networks.
  2. Branching processes, second moments and percolation.
  3. Size-biased trees and Biggins' theorem.
  4. Branching random walks: the law of large numbers.
  5. The lambda-biased walks on a Galton-Watson tree.
  6. Random walk in random environment on trees.
We try to make this course self-contained, the only prerequisite is basic knowledge of Markov chains and conditional expectation. Two references:
R. Lyons with Y. Peres: Probability on Trees and Networks. Cambridge Series in Statistical and Probabilistic Mathematics, 2016.
Z. Shi: Branching random walk. Saint-Flour's course, Springer, 2015.