The phase transition for parking on Galton–Watson trees

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<s$, then $(n_1,\dots,n_r)\in T$.

We now choose for each $u\in\mathcal U$ a number $c(u)$ distributed according to the distribution $p$, with all these choices being independent. The corresponding Galton–Watson tree $T$ is then defined inductively as follows: the empty sequence belongs to $T$, and if $u=(n_1,\dots,n_k)$ belongs to $T$ and $n_{k+1}\leq c(u)$, then $(n_1,\dots,n_{k+1})$ belongs to $T$. As one would expect, the tree is called critical if the corresponding branching process is critical – that is, if $p$ has mean 1.

The authors consider the following problem. They begin by taking a critical Galton–Watson tree for a distribution $p$ with variance $\Sigma$, and they condition on its being large. They then place at each vertex a random number of cars, where these numbers are independent and identically distributed with mean $m$ and variance $\sigma^2$. The cars then all drive towards the route of the tree, parking as soon as they reach an empty vertex. If they never reach an empty vertex, then they “escape” through the root.

One assumes for convenience that two or more cars do not reach a vertex at the same time (or alternatively, if they do and the vertex is empty, then one of them parks and the rest do not). It is easy to see that the set of eventually occupied vertices, and hence also the number of cars that escape, does not depend on the order in which the cars reach the vertices. (The authors call this the Abelian property of the model.)

Clearly, there is a positive probability that some cars escape, since there may happen to be a lot of cars near the root. So the rough question one asks is the following: under what circumstances do almost all cars end up parked (with high probability)?

It was conjectured by Goldschmidt and Przykucki that, rather surprisingly, there should be a phase transition that depends only on $m, \sigma$ and $\Sigma$ – that is, on the mean and variance of the number of cars and on the variance of the offspring distribution of the Galton–Watson tree (the mean of which is by assumption 1). The main result of this paper is a proof of this conjecture. More precisely, the authors show that with high probability most cars park if the quantity $(1-m)^2- \Sigma^2 (\sigma^2+m^2-m)$ is positive, whereas a positive proportion of cars fail to park if it is negative.