The phase transition for parking on Galton--Watson trees

Abstract

The Galton--Watson branching process (which was actually first studied by Bienaymé) is a central concept in probability theory, often taught in a first university course in the subject. One is given a probability distribution $p$ defined on the positive integers, and one defines a sequence of random variables $X_0,X_1,\dots$ as follows: $X_0$ is identically 1, and for each $n>0$, $X_n$ is a sum of $X_{n-1}$ independent random variables, each distributed according to $p$. This provides a simple model for population growth, where each individual produces a number of offspring that is distributed according to $p$. A basic fact about the process is that if the expectation of $p$ is less than 1, then with probability 1 the process dies out (that is, there exists $n$ such that $X_n=0$), whereas if it is greater than 1, then there is a positive probability that the process never dies out. If the expectation is 1, then the process is called _critical_. In that case, it still dies out with probability 1 (except in the trivial case that $p(1)=1$) , but its behaviour is somewhat different: for example, the expected size of $X_n$ is 1, so it does not tend to zero. For many purposes it is important to study not just the size of the population but also more detailed questions about the structure of the random family tree that results from this process, which is known as a _Galton-Watson tree_. It can be defined formally as follows. Let $\mathcal U$ be the set of all finite sequences of positive integers (including the empty sequence as a sequence). Define a _tree_ in $\mathcal U$ to be a subset $T$ of $\mathcal U$ that is closed under taking initial segments: that is, if $(n_1,\dots,n_s)\in T$ and $r