Random Walks and Trees

Zhan Shi¹

¹ Université Paris VI, Laboratoire de Probabilités et Modèles Aléatoires, 4 place Jussieu, 75252 Paris Cedex 05, France.
e-mail: zhan.shi@upmc.fr

Abstract

These notes provide an elementary and self-contained introduction to branching random walks.

Section 1 gives a brief overview of Galton–Watson trees, whereas Section 2 presents the classical law of large numbers for branching random walks. These two short sections are not exactly indispensable, but they introduce the idea of using size-biased trees, thus giving motivations and an avant-goût to the main part, Section 3, where branching random walks are studied from a deeper point of view, and are connected to the model of directed polymers on a tree.

Tree-related random processes form a rich and exciting research subject. These notes cover only special topics. For a general account, we refer to the St-Flour lecture notes of Peres [47] and to the forthcoming book of Lyons and Peres [42], as well as to Duquesne and Le Gall [23] and Le Gall [37] for continuous random trees.