# Parking on the infinite binary tree

David Aldous & Alice Contat & Nicolas Curien & Olivier Hénard U.C. Berkeley.
<EMAIL_ADDRESS>Paris-Saclay. alice.contat@universite-paris-
saclay.frUniversité Paris-Saclay<EMAIL_ADDRESS>Paris-
Saclay<EMAIL_ADDRESS>
###### Abstract

Let $(A_{u}:u\in\mathbb{B})$ be i.i.d. non-negative integers that we interpret
as car arrivals on the vertices of the full binary tree $\mathbb{B}$. Each car
tries to park on its arrival node, but if it is already occupied, it drives
towards the root and parks on the first available spot. It is known [14, 1]
that the parking process on $\mathbb{B}$ exhibits a phase transition in the
sense that either a finite number of cars do not manage to park in expectation
(subcritical regime) or all vertices of the tree contain a car and infinitely
many cars do not manage to park (supercritical regime). We characterize those
regimes in terms of the law of $A$ in an explicit way. We also study in detail
the critical regime as well as the phase transition which turns out to be
“discontinuous”.

Figure 1: Simulation of the parking process on the first $9$ levels of the
full binary tree (the edges are oriented towards the origin of the tree which
is at the center of the figures). The dotted vertices on the left figure
initially contain $2$ cars whereas the others are void. In the middle and
right figures, the highlighted edges have seen a positive flux of car.

##  1 Introduction

The parking process is a central algorithm in combinatorics and probability.
When the underlying graph is an oriented line, it was first studied by Konheim
& Weiss [16] in relation with hash tables and it has led to many developments
in probability notably via connections with the Brownian continuum random tree
and the additive coalescent [5]. Recently, Lackner & Panholzer [17] started
the systematic study of the parking functions on finite rooted trees. This
triggered an intense activity on the model of parking on a random _critical_
Galton–Watson tree. In particular, a phase transition was proved to occur and
the threshold was located in an increasing level of generality [14, 12, 8].
Furthermore a surprising connection with the Erdös–Rényi random graph and the
multiplicative coalescent was unraveled in [10].

However, much less is known about the parking scheme on supercritical
Galton–Watson trees, apart from the existence of a phase transition [14, 1]
and despite an intense activity on the closely related Derrida–Retaux model
[7]. The goal of this paper is to close this gap and locate and study the
phase transition in the case of the parking process on the infinite binary
tree (see Section 6 for extensions).

#### Parking on the infinite binary tree.

Consider the full planar rooted binary tree. Its vertices can be conveniently
represented by the finite words on two letters $\mathbb{B}=\cup_{n\geqslant
0}\\{0,1\\}^{n}$, with $\\{0,1\\}^{0}=\varnothing$ being the root of the tree
and with edges between the words $u$ and $u0$ and the words $u$ and $u1$.
Those vertices will be interpreted as free parking spots, each spot
accommodating at most $1$ car. On top of that tree, we consider a non-negative
integer labeling $(A_{u}:u\in\mathbb{B})$ representing the number of cars
arriving on each vertex $u\in\mathbb{B}$. Each car tries to park on its
arrival vertex, and if the spot is occupied, it travels downwards in direction
of the root of the tree until it finds an empty vertex to park. If there is no
such vertex on the path towards the root $\varnothing$, the car exits the
tree, contributing to the _flux_ of cars at the root. If we introduce the
random variable

$X:=\mbox{ number of cars which have visited }\varnothing,$

the outgoing flux of cars is then simply $\mathrm{F}=(X-1)_{+}=\max(X-1,0)$.
As we will see in Section 2.1, the final configuration (flux and status
void/occupied for the vertices), and in particular the value of variables $X$
and $\mathrm{F}$, does not depend upon the order chosen to park the cars.

Figure 2: Illustration of the parking process in the first $5$ levels of the
full binary tree. The car arrivals are represented by red squares (including
the cars that may come from higher levels on top of the tree). After the
parking process, the vertices accommodating a car are displayed in gray,
whereas the free spots are displayed in white. The connected components of
parked cars are drawn with thick lines, they are _fully parked trees_.

In the remainder of this paper we shall suppose that the car arrivals
$(A_{u}:u\in\mathbb{B})$ are i.i.d. with a given distribution
$\mu=(\mu_{k}:k\geqslant 0)$ on $\\{0,1,2,3,...\\}$. To avoid trivialities, we
always suppose that $\mu(\\{0,1\\})<1$ for otherwise the cars would always
park on their arrival node. We let

$G(x)=\sum_{k\geqslant 0}\mu_{k}x^{k}$

be the generating function of the law $\mu$. One can then establish a
dichotomy (see Lemma 1 and also [14, 1] as well as Proposition 1 below):

  * •

Either the number $X$ of cars that visited the root $\varnothing$ has a finite
mean and all clusters of parked vertices are finite almost surely, we call
this phase the subcritical regime,

  * •

Or almost surely $X=\infty$ and actually, all vertices of $\mathbb{B}$ are
occupied after the parking process, we call this phase the supercritical
regime.

We shall furthermore distinguish the critical regime, when it is not possible
to stochastically increase $\mu$ and stay subcritical. A first trivial remark
is that when $\mathbb{E}[A]>1$ the process is necessarily supercritical (since
there are more cars than parking spots on average). Our main result is then a
characterization of those regimes explicitly in terms of the generating
function $G$ of $\mu$:

######  Theorem 1 (Location of the phase transition).

Suppose that there exists $t_{c}\in(0,\infty)$ such that

$t_{c}=\min\\{t\geqslant 0:\
2(G(t)-tG^{\prime}(t))^{2}=t^{2}G(t)G^{\prime\prime}(t)\\}\qquad(\star).$

Then the parking process is subcritical if and only if

$\displaystyle(t_{c}-2)G(t_{c})\geqslant t_{c}(t_{c}-1)G^{\prime}(t_{c}).$ (1)

The condition $(\star)$ on the existence of $t_{c}$ is mild and is for example
verified for all generating functions with infinite radius of convergence (see
Remark Remark). When $(\star)$ is not verified, we provide a method to check
if we are in the subcritical phase, see Section 5.3. Checking the signs of the
two sides of the inequality (1), see Remark Remark, we see in particular that
the generating function $G$ must have a radius of convergence at least $2$ to
be in the subcritical phase. This can easily be explained by probabilistic
arguments: otherwise, the maximum of $2^{n}$ independent copies of a random
variable with law $\mu$ is larger than $n$ with high probability, so that the
car arrivals at the single level $n$ of $\mathbb{B}$ suffice to guarantee that
the root $\varnothing$ is occupied, see Lemma 1. The same argument actually
even proves that the radius of convergence of $X$ (which is stochastically
larger than $A$) must stay above $2$ in the subcritical regime. Notice that
deciding whether $\mu$ is subcritical for parking depends in a subtle way on
the distribution as opposed to the case of critical Galton–Watson trees [14,
12, 8] where its depends only on the first two moments.

Let us give a couple of examples of application of our theorem in the case of
a car arrival distribution that is parametrized by a family
$(\mu_{\alpha}:0\leqslant\alpha)$ which is stochastically increasing with mean
$\alpha\geqslant 0$: in this case the parking is subcritical if
$\alpha\leqslant\alpha_{c}$ and supercritical if $\alpha>\alpha_{c}$, for some
threshold $\alpha_{c}$ depending on the family of laws:

  * •

Binary 0/2 arrivals. If
$\mu_{\alpha}=(1-\frac{\alpha}{2})\delta_{0}+\frac{\alpha}{2}\delta_{2}$, then
the critical threshold is

$\alpha_{c}(\mathrm{Binary_{\,0/2}})=\frac{1}{14}\cdot$

This settles an open problem of Bahl, Barnet & Junge [1]. Obviously the value
of $\alpha_{c}$ is in agreement with the bounds
$\frac{1}{32}\leqslant\alpha_{c}\leqslant\frac{1}{2}$ of [14, Proposition 3.5]
and improved to $0.03175\leqslant\alpha_{c}\leqslant 0.08698$ in [1,
Proposition 4].

  * •

Binary 0/k arrivals. More generally if
$\mu_{\alpha}=(1-\frac{\alpha}{k})\delta_{0}+\frac{\alpha}{k}\delta_{k}$ for
some $k\in\\{2,3,4,...\\}$, then the threshold is

$\alpha_{c}(\mathrm{Binary_{\,0/k}})=\frac{k}{1+2^{-k-2}\left(3+\sqrt{\frac{k+7}{k-1}}\right)^{k}\left((k-1)(k+4)+k\sqrt{(k+7)(k-1)}\right)}.$

  * •

Poisson arrivals. If $\mu_{\alpha}$ is Poisson with mean $\alpha$, then

$\alpha_{c}(\mathrm{Poisson})=3-2\sqrt{2}.$

  * •

Geometric arrivals. If $\mu_{\alpha}=p^{k}(1-p)$ for $k\geqslant 0$ is a
geometric law with mean $\alpha=\frac{p}{1-p}$ then
$p_{c}(\mathrm{Geometric})=1/9$ and

$\alpha_{c}(\mathrm{Geometric})=\frac{1}{8}\cdot$

#### The critical regime.

Let us now focus more precisely on the critical regime : we assume that $\mu$
is subcritical (and $(\star)$ holds) and that it is not possible to
stochastically increase $\mu$ while remaining subcritical. As we shall see in
Section 5, this means that the inequality in (1) is actually an equality.
Recall that we denoted by $X$ the number of cars that _visited_ the root
$\varnothing$ of $\mathbb{B}$ during the parking process. We set for
$k\geqslant 0$, $p_{k}=\mathbb{P}(X=k)$ and will use the shorthands
$p_{\circ}=p_{0}$ and $p_{\bullet}=p_{1}$ for respectively the probability
that the root is void and the probability that the root is at the bottom of a
parked cluster without flux, after parking. In the following, we shall call
_white_ the clusters of void vertices, and _black_ the clusters of parked
vertices.

######  Theorem 2 (Critical computations).

Suppose that $(\star)$ holds and that (1) is an equality. Then almost surely
the root $\varnothing$ is void or it belongs to a finite black cluster, and we
have

$p_{\circ}=\frac{t_{c}^{2}}{4(t_{c}-1)G(t_{c})}\quad\mbox{ and }\quad
p_{\bullet}=\sqrt{\frac{p_{\circ}}{\mu_{0}}}-p_{\circ}.$

These calculations have a few surprising consequences:

  * •

$\mathbb{E}[X]<\infty$. The fact that the expectation of the flux of cars is
finite in the whole subcritical regime (including at criticality) may be
surprising at first, but this can actually be seen from the recursive
distributional equation satisfied by $X$ by splitting at the root of
$\mathbb{B}$

$\displaystyle X$ $\displaystyle\overset{(d)}{=}$
$\displaystyle\quad(X_{1}-1)_{+}+(X_{2}-1)_{+}+A,$ (2)

where $X_{1},X_{2}$ are two copies of law $X$ independent of the car arrivals
$A$ of law $\mu$. Indeed, the RHS has expectation at least $2\mathbb{E}[X]-2$
which is strictly larger than $\mathbb{E}[X]$ as soon as $\mathbb{E}[X]>2$.
Iterating the argument, one sees that there is no a.s. finite solution to the
above recursive distributional equation which has a mean $>2$, see [1, Theorem
1.1] for details. Actually, as we already mentioned the variable $X$ must have
a radius of convergence larger than $2$, even at the critical point, see the
forthcoming Lemma 1. Also, plugging the value of $p_{\circ}=\mathbb{P}(X=0)$
into (2) we deduce that

$\mathbb{E}[X]+\mathbb{E}[A]=2(1-p_{\circ}),\qquad\text{ or
equivalently}\qquad\mathbb{E}[\mathrm{F}]+\mathbb{E}[A]=1-p_{\circ}$

Now, by Remark Remark, on the subcritical regime we have
$p_{\circ}>\frac{1}{2}$, so that the LHS of the left identity is bounded by 1
and the LHS of the right identity by $1/2$; one can also show that these
bounds are sharp.

  * •

It will follow from our combinatorial decomposition that the clusters of void
vertices are actually Bienaymé–Galton–Watson trees with offspring distribution
$\xi$ given by

$\mathbb{P}(\xi=0)=\frac{p_{\bullet}^{2}}{(p_{\circ}+p_{\bullet})^{2}},\quad\mathbb{P}(\xi=1)=\frac{2p_{\bullet}p_{\circ}}{(p_{\circ}+p_{\bullet})^{2}},\quad\mathbb{P}(\xi=2)=\frac{p_{\circ}^{2}}{(p_{\circ}+p_{\bullet})^{2}}.$

Again, since by Remark Remark we have $p_{\circ}>\frac{1}{2}$, those trees are
supercritical, implying that at criticality there are (infinitely many)
infinite white clusters. On the contrary, we shall see in Proposition 1 that
in the subcritical regime (including the critical case), there are no infinite
black clusters.

Those phenomena underline the fact that the phase transition in the parking
process is _discontinuous_ contrary e.g. to the case of Bernoulli percolation
on $\mathbb{Z}^{2}$.

#### Fully parked trees and their enumeration.

The proofs of our main results rely on a simple combinatorial decomposition
into clusters of parked vertices and the enumeration thereof. More precisely,
a fully parked tree $\mathbf{f}$ is a subtree of $\mathbb{B}$ containing the
root, decorated with car arrivals, so that all those cars manage to park on
$\mathbf{f}$ and that reciprocally all vertices of $\mathbf{f}$ are parked. If
$F\equiv F_{\mu}(x)$ is the generating function of fully parked trees counted
with a weight $x$ per vertex and incorporating the $\mu$-weight of car
arrivals, see Section 3.1 for the precise definition, then the high-level idea
of the proof is to write the fixed point equations for $p_{\circ}$ and
$p_{\bullet}$, which are

$\displaystyle p_{\circ}=\mu_{0}(p_{\circ}+p_{\bullet})^{2}\quad\mbox{ and
}\quad p_{\bullet}=p_{\circ}F_{\mu}(p_{\circ}),$

and translate the idea that we decompose the structure into the (finite)
clusters of parked vertices. Theorem 1 boils down to deciding whether we have
a non trivial solution $p_{\circ}\neq 0$ to these equations (otherwise we are
in the supercritical regime). The critical regime corresponds to the case
where $p_{\circ}$ is exactly the radius of convergence of $F$. Thus the main
ingredient in the proof is the “computation” of the generating function $F$.
The enumeration of fully parked trees has already been considered in the
combinatorics literature [17, 6, 15, 10, 9] and it shares many similarities
with the enumeration of planar maps. The idea is to enumerate a more
complicated structure, namely fully parked trees with a possible flux of cars
at the origin. Those are defined as fully parked trees, except that now the
number of cars may be larger than the number of vertices of the tree so that
the number of cars $X$ visiting the root of the tree may be strictly larger
than $1$. If $F\equiv F_{\mu}(x,y)$ is the generating function of fully parked
trees with weight $x$ per vertex and $y$ per outgoing car, then writing a
recursive decomposition at the root vertex we obtain

$\displaystyle
F(x,y)=\frac{x}{y}\left(\big{(}1+F(x,y)\big{)}^{2}G(y)-\big{(}1+F(x,0)\big{)}^{2}G(0)\right).$
(3)

These equations are reminiscent of Tutte’s equation [19] in the realm of
planar maps where the perimeter of the external face plays the role of our
outgoing flux of cars. In this equation, the variable $y$ is called the
_catalytic variable_ since its role is to disappear to recover $F(x,0)\equiv
F(x)$, the generating function of fully parked trees with no flux. We apply
the standard kernel method [4] to solve those equations, see Section 4 for
details.

Once we have sufficient information on $F$, the proofs of our main results are
rather straightforward. Deciding whether $p_{\circ}$ is non trivial boils down
to an inequality on $F(x_{c},0)$ at its radius of convergence $x_{c}$, see
Proposition 2. Under the assumption $(\star)$, this inequality is equivalent
to (1) and the critical case corresponds to the case when $p_{\circ}$
coincides with the radius of convergence of $F(\cdot,0)$. Furthermore, in the
subcritical case the generating function of the outgoing flux of cars is given
by $p_{\circ}F(p_{\circ},y)$ (see (5)).

#### Growth-fragmentation trees.

It will follow from our decomposition that conditionally on $X=1$, i.e. on
$\varnothing$ being the root of a fully parked tree with no flux, then the
cluster of parked cars above $\varnothing$ is a random fully parked tree whose
size has generating function $F(p_{\circ}z)/F(p_{\circ})$. In the critical
regime, since $p_{\circ}$ corresponds to the radius of convergence of $F$, the
tail of the cluster size has a subexponential decay and in the generic
situation (e.g. when the car arrivals have bounded support), we actually have

$\displaystyle\mathbb{P}(\varnothing\mbox{ is a the root of a parked cluster
of size }n)\sim\mathrm{cst}\cdot n^{-5/2},$ (4)

the exponent $5/2$ being common in the theory of map enumeration. Furthermore,
we also believe that in the generic situation, rescaled large fully parked
trees converge after normalization towards the growth-fragmentation trees that
already appeared in the study of scaling limits of random planar maps and the
Brownian sphere, see [2, 3, 18] or [11, Chapter 14.3.2]. We already made a
similar conjecture for the scaling limits of parked components in the parking
process on large uniform Cayley trees [10, Conjecture 1]. It is interesting to
notice that although the phase transition in the parking on $\mathbb{B}$ is of
a different flavor (the phase transition in the case of critical Galton–Watson
trees is “continuous”), the large scale geometry of the critical components
should be the same. However, there are non-generic situations (with specific
car arrivals distributions having heavy-tail) where (4) does not hold and
where we expect different scaling limits. See Section 6 and [6] for a similar
phenomenon in the case of enumeration of non-binary plane fully parked trees.
We plan to address those questions in following works.

Acknowledgments. A.C and N.C. acknowledge the support from ERC 740943
GeoBrown. Part of this work was initiated during a conference in CIRM and we
thank our host for its hospitality.

##  2 Background

In this section we formally present the parking process on $\mathbb{B}$ and
gather a few “rough” probabilistic results (mostly adapted from [14, 1]).

###  2.1 Parking on infinite trees

Let $\tau$ be a rooted locally finite (plane) tree decorated with car arrivals
$(a_{u}:u\in\tau)$. As described in the introduction, cars try to park on
their arrival node, and if the spot is taken they travel downwards in search
of the first empty spot and, in case there is no such spot, exit at the root.
In the case $\tau$ is finite, an easy Abelian property shows that the number
of cars visiting each vertex of the tree does not depend on the order in which
we park the cars, see Section 2.1 of [17].

On infinite trees, to prevent cumbersome issues, we shall stick to a given
parking procedure: _park the lowest cars first_. More precisely, for each
$n\geqslant 0$ let us consider the finite tree $[\tau]_{n}$ made of the first
$n$ generations above the root $\varnothing$ (recall that $\tau$ is supposed
locally finite) together with the restriction of the car arrivals on these
vertices. We can then perform the parking on $[\tau]_{n}$ and construct
variables

$x_{n}(u)\quad u\in[\tau]_{n},$

representing the number of cars that visited the vertices of $[\tau]_{n}$ in
the parking process (recall that those variables do not depend on the order in
which we parked the cars on $[\tau]_{n}$). Notice that for a given vertex
$u\in\tau$, the function $n\mapsto x_{n}(u)$ is non-decreasing (it is defined
for $n$ larger than the height of $u$) so that we can let $n\to\infty$ and
define

$x(u)=\lim_{n\to\infty}x_{n}(u),$

as the limiting number of cars visiting $u$ in the parking process on $\tau$.
This morally corresponds to parking the lowest cars first111In fact, we could
equivalently fix an exhaustion of $\tau$ by finite trees
$\tau_{1}\subset\tau_{2}\subset\cdots$ and define the parking on $\tau$ as the
limit of the parking procedure over the $\tau_{n}$’s.. In particular we say
that $u$ is void if $x(u)=0$, that $u$ is occupied if $x(u)\geqslant 1$ and
the flux of outgoing cars at $u$ is $f(u)=(x(u)-1)_{+}$.

###  2.2 Rough phase transition

We now focus on the case of the binary tree $\mathbb{B}$ with i.i.d. car
arrivals $(A_{u}:u\in\mathbb{B})$ with law $\mu$ satisfying
$\mu(\\{0,1\\})<1$. We denote by $X(u)$ the number of cars that visited vertex
$u\in\mathbb{B}$ as defined in the preceding section and will use the
shorthand notation $X=X(\varnothing)$. We first establish a dichotomy on $X$
in the next lemma, which we then interpret in more geometric terms by proving
that there cannot be infinite black clusters with a finite flux.

######  Lemma 1 (Dichotomy subcritical/supercritical).

We have the following dichotomy:
Subcritical case. Either the sequence $(2^{n}\mathbb{P}(X>n):n\geqslant 0)$ is
bounded.
Supercritical case. Or $X=\infty$ a.s, in which case all vertices are parked
a.s.

###### Proof of the lemma..

Assume that $(2^{n}\mathbb{P}(X>n):n\geqslant 0)$ is not bounded, and observe
that the same is then true of the sequence $(2^{n}\mathbb{P}(X>n+k):n\geqslant
0)$ for any integer $k$. Then consider the collection of the $2^{n}$ i.i.d.
variables $X({u})$ attached to the vertices $u$ of $\mathbb{B}$ at height $n$.
We have the upper bound

$\mathbb{P}\Big{(}\bigcap_{u:|u|=n}\\{X(u)\leq
n+k\\}\Big{)}\leq\mathrm{e}^{-2^{n}\mathbb{P}(X>n+k))},$

with the right-hand side going to $0$ along a subsequence. But on the
complement of the event on the left-hand side, one of the variables $X(u)$ is
strictly larger $n+k$ and this contribution only suffices to imply that
$X=X(\varnothing)\geqslant k$. Combined with our assumption, this implies
that, almost surely, $X\geqslant k$, hence, $k$ being arbitrary, $X=\infty$.
This means that the root of $\mathbb{B}$ almost surely contains a car, and it
is the same for any other vertex. ∎

The next lemma says that the above dichotomy is equivalent to the existence of
infinite black clusters. In particular, it rules out the possibility of having
an infinite black cluster and a finite flux.

######  Proposition 1.

In the subcritical regime, there is no infinite black cluster.

###### Proof.

Suppose that $\mu$ is subcritical, so that all variables $X(u)$ are finite
after the parking process. It suffices to prove that the probability that the
cluster of the origin $\mathcal{C}(\varnothing)$ is infinite is $0$. Fix
$p\geqslant 0$ and let us consider the event
$\mathcal{E}=\\{X(\varnothing)=p\mbox{ and }\mathcal{C}(\varnothing)\mbox{ is
infinite}\\}$. We shall explore the process by parking on the first $n$ levels
of $\mathbb{B}$ as in the preceding section. More precisely, let
$\mathcal{F}_{n}$ be the sigma field generated by the variables $X_{n}(u)$ for
$X_{n}(u)$ the number of cars visiting the vertex $u$ when restricting the
parking on $[\mathbb{B}]_{n}$. We then construct a sequence of stopping times
$\theta_{1}<\theta_{2}<\cdots$ obtained as follows:
$\theta_{1}=\inf\\{n\geqslant 0:X_{n}(\varnothing)=p\\}$ and then by induction
$\theta_{i+1}=\inf\\{n>\theta_{i}:\varnothing\leftrightarrow\partial[\mathbb{B}]_{n}\\}$
where $\varnothing\leftrightarrow\partial[\mathbb{B}]_{n}$ means that
$\varnothing$ is connected to the level $n$ by a path whose vertices satisfy
$X_{n}(u)\geqslant 1$. A moment’s though shows that on the event $\mathcal{E}$
all these stopping times are finite for otherwise the black cluster of the
origin would not be infinite. For $n\geqslant 2$, on the event
$\\{\theta_{n}<\infty\\}$, let $v_{n}$ be the (first, for definiteness) vertex
of $\partial[\mathbb{B}]_{\theta_{n}}$ to be connected to the root when
parking on $[\mathbb{B}]_{\theta_{n}}$. Set
$\mathcal{D}_{n}=\\{A_{v_{n}0},A_{v_{n}1}\in\\{0,1\\}\\}$ the event that the
two children of $v_{n}$ have car arrivals $\leqslant 1$. Plainly,
$\mathcal{E}\subset\mathcal{D}_{n}\cap\\{\theta_{n}<\infty\\}$ since
otherwise, the flux coming from these two vertices would go down all the way
to $\varnothing$ and we would have $X(\varnothing)>p$. In particular we have

$\mathbb{P}(\mathcal{D}_{n}\mathbf{1}_{\theta_{n}<\infty}\mid\mathcal{F}_{\theta_{n}})=(\mu_{0}+\mu_{1})^{2}<1.$

Notice then that $\mathcal{D}_{1},...,\mathcal{D}_{n-1}$ are
$\mathcal{F}_{\theta_{n}}$-measurable so that by induction we have

$\mathbb{P}(\mathcal{E})\leqslant\mathbb{P}(\theta_{n}<\infty)\prod_{k=2}^{n}\mathbb{P}(\mathcal{D}_{k}|\theta_{n}<\infty)\leqslant(\mu_{0}+\mu_{1})^{2(n-1)},$

which implies $\mathbb{P}(\mathcal{E})=0$ since $n$ is arbitrary and we
assumed the distribution $\mu$ satisfies $\mu_{0}+\mu_{1}<1$. ∎

As a consequence of the (proof of) Lemma 1, there is no lower bound for
$\mathbb{E}[A]$ for supercritical parking, since one may cook up distributions
$\mu$ with arbitrarily small expectation but $\mathbb{E}[2^{A}]=\infty$.
However, if the car arrival distribution is bounded, one can obtain a lower
bound for the expectation $\mathbb{E}[A]$ of the car arrival distribution for
supercritical parking using a first moment method, see [14, Proposition 3.5]
and [1] for details.

To speak of a phase transition, one may imagine a family
$(\mu^{\alpha})_{\alpha\geqslant 0}$ of car arrival distributions that is
stochastically increasing in the mean $\alpha$. In this case, the subcritical
phase is identified with a _closed set_ $\alpha\in[0,\alpha_{c}]$, and the
supercritical phase with the set $]\alpha_{c},1]$. The fact that $\alpha_{c}$
is actually subcritical (i.e. satisfies the first alternative of the
dichotomy) can be seen by monotone convergence since the expectation of the
flux is bounded above by $2$ in the whole subcritical phase as recalled in the
introduction (see [1] for details).

##  3 Decomposition into fully-parked components

In this section we present our combinatorial decomposition which underlies our
main results. The idea is very simple: we decompose the final configuration on
$\mathbb{B}$ into the black clusters of parked vertices and the white empty
vertices. This shows that we can decompose the final configuration as a two-
type Bienaymé–Galton–Watson tree whose offspring distribution is related to
the generating function $F$ of fully parked trees studied in detail in the
next section.

###  3.1 Fully parked trees

Suppose that we performed the parking process on $\mathbb{B}$, and recall that
the black vertices are those $u\in\mathbb{B}$ satisfying $X(u)\geqslant 1$,
the other ones being the empty or white vertices. The _finite_ black connected
components are _fully parked trees_ $\mathbf{t}$, i.e. connected subsets of
the binary tree decorated by car arrivals $(a_{u})_{u\in\mathbf{t}}$ such that
after parking all vertices are occupied. If such a tree appears as the black
component of the root $\varnothing$, then the fully parked tree may have an
outgoing flux at the root (i.e. containing more cars than vertices), otherwise
it contains as many cars as vertices. See Figure 3.

Figure 3: Three examples of fully parked trees. Notice that the first two have
no outgoing flux and represent the same plane tree but their embeddings in
$\mathbb{B}$ is different. The last fully parked tree on the right has an
outgoing flux of $2$ cars.

For the enumeration of the fully parked trees we shall always consider that
their bottom vertex is $\varnothing$. Each plane rooted structure of a fully
parked tree with $m$ vertices with $1$ child actually corresponds to $2^{m}$
different embeddings as a subset of $\mathbb{B}$ (with $\varnothing$ as the
root): for this reason, later in the decomposition we shall put a weight of
$2$ for vertices with outdegree $1$. Let us denote by $\mathbb{T}_{n}^{(p)}$
the set of all fully parked trees with root $\varnothing$, with $n$ vertices
and having outgoing flux $p\geqslant 0$ (i.e. $p+1$ cars have visited the root
vertex). The weight $w({\mathbf{t}})$ of a fully parked tree
$\mathbf{t}\equiv(\mathbf{t}:(a_{u}:u\in\mathbf{t}))$ is the weight of its car
decoration, that is

$w({\mathbf{t}})=\prod_{u\in\mathbf{t}}\mu_{a_{u}}.$

We can then form the bivariate generating series of fully parked trees (with
flux) as

$\displaystyle F(x,y)\equiv F_{\mu}(x,y)$ $\displaystyle:=$
$\displaystyle\sum_{n\geqslant 1}\sum_{p\geqslant
0}\sum_{\mathbf{t}\in\mathbb{T}_{n}^{(p)}}x^{n}y^{p}w({\mathbf{t}})$
$\displaystyle=$ $\displaystyle
x\big{(}\mu_{1}+\mu_{2}y+\mu_{3}y^{2}+\cdots\big{)}+x^{2}\big{(}2(\mu_{2}+\mu_{1}^{2})+2y(\mu_{3}+2\mu_{1}\mu_{2})+\cdots\big{)}+\cdots$

Section 4 is devoted to the study of $F$ via a functional equation obtained by
splitting a fully parked tree at the root, see (10). But before doing so, let
us present the combinatorial decomposition and the characterization of
subcriticality in terms of $F$. It turns out that most equations simplify if
one introduces

$\mathbf{F}(x,y):=1+F(x,y)\quad\mbox{ and
}\quad\mathbf{F}_{0}(x):=\mathbf{F}(x,0):=1+F(x,0).$

###  3.2 Decomposition

Recall that the law of $X$ is $(p_{k}:k\geqslant 0)$ and that we gave a short-
hand notation $p_{\circ}=p_{0}$ for the probability that the root vertex is
empty. We write $\mathcal{C}(\varnothing)$ for the monochromatic cluster of
the origin in $\mathbb{B}$ after parking. Notice that the number of vertices
adjacent from above to a fully parked tree $\mathbf{t}\subset\mathbb{B}$ with
$n$ vertices is $n+1$, regardless of the shape of $\mathbf{t}$. Recalling
Proposition 1 we have for $k\geqslant 0$

$\displaystyle\mathbb{P}(X(\varnothing)=k+1)$
$\displaystyle\underset{\mathrm{Prop.}\ref{prop:noblack}}{=}$
$\displaystyle\mathbb{P}(X(\varnothing)=k+1\mbox{ and
}\\#\mathcal{C}(\varnothing)<\infty)$ (5) $\displaystyle=$
$\displaystyle\sum_{\mathbf{t}\in\mathbb{T}_{n}^{(k)}}\mathbb{P}(\mathcal{C}(\varnothing)=\mathbf{t})$
$\displaystyle=$ $\displaystyle\sum_{n\geqslant
1}\sum_{\mathbf{t}\in\mathbb{T}_{n}^{(k)}}w(\mathbf{t})p_{\circ}^{n+1}=p_{\circ}[y^{k}]F(p_{\circ},y).$

The other fundamental equation is obtained by noticing that the event
$\\{X(\varnothing)=0\\}$ occurs if and only if $A_{\varnothing}=0$ and
$\\{X(u)\in\\{0,1\\}:\mbox{ for }u\in\\{0,1\\}\\}$ which turns into

$\displaystyle p_{\circ}$ $\displaystyle=$
$\displaystyle\mu_{0}(p_{\circ}+p_{\bullet})^{2}.$ (6)

Specializing (5) to $k=0$, we recover together with the previous display the
fixed point equation $p_{\bullet}=p_{\circ}{F}(p_{\circ},0)$, mentioned in the
introduction. In particular, re-injecting in (6) we obtain

$\displaystyle\quad
p_{\circ}=\mu_{0}p_{\circ}^{2}\big{(}\mathbf{F}_{0}(p_{\circ})\big{)}^{2},\quad\mbox{
where we recall that }\mathbf{F}_{0}(x)=1+F(x,0).$

Notice that the function $x\mapsto\mu_{0}x^{2}(\mathbf{F}_{0}(x))^{2}$ is
strictly convex and that $p_{\circ}=0$ is a trivial solution to the above
equation, so there is at most one positive solution $p_{\circ}$. Under the
same hypothesis, splitting according to the values of $X(\varnothing)$ we also
obtain thanks to (5)

$\displaystyle 1$ $\displaystyle=$ $\displaystyle
p_{\circ}+p_{1}+p_{2}+\cdots\underset{\eqref{eq:funda1}}{=}p_{\circ}\mathbf{F}(p_{\circ},1).$
(7)

######  Proposition 2 ($F$-characterization of subcriticality).

The law $\mu$ is subcritical if and only if there is a positive solution to
the equation

$\displaystyle\quad 1=\mu_{0}x(\mathbf{F}_{0}(x))^{2}.$ (8)

###### Proof.

Let $\mu$ be a subcritical law for the parking on $\mathbb{B}$. Since
$p_{\circ}\neq 0$, the above calculations show that $p_{\circ}$ is indeed a
solution to the equation (8).

Conversely, suppose that there is a positive solution $x_{\circ}$ to (8). As a
special case of equation (10) below for $\mathbf{F}(x,y)$, we know that the
series $\mathfrak{f}(y)=\mathbf{F}(x_{\circ},y)$ is a solution to
$y+\mathfrak{f}^{2}x_{\circ}G(y)-y\mathfrak{f}-1=0$. Solving the quadratic
equation and taking the combinatorial solution we have

$\mathfrak{f}(y)=\frac{y+\sqrt{y^{2}+4x_{\circ}(1-y)G(y)}}{2x_{\circ}G(y)}.$

At first, the above equality holds only as a formal power series in $y$. But
notice that the function $y^{2}+4x_{\circ}(1-y)G(y)$ inside the square-root
does not vanish over $y\in[0,1]$ so that the solution above is analytic over
$[0,1]$. By Pringsheim’s theorem [13, Theorem IV.6 p.240], the function
$\mathfrak{f}$ has radius of convergence at least $1$ and we have
$\mathfrak{f}(1)=\frac{1}{x_{\circ}}$ which is
$x_{\circ}\mathbf{F}(x_{\circ},1)=1.$ This in turn ensures that there exists a
random variable $Z$ (the outgoing flux of cars) whose generating function is

$\mathbf{Z}(y)=x_{\circ}\mathbf{F}(x_{\circ},y).$

We then compute, using Tutte’s equation (3) (see (10) below) as well as (8):

$\displaystyle\frac{1}{y}\big{(}\mathbf{Z}(y)^{2}G(y)-\mathbf{Z}(0)^{2}G(0)\big{)}+\mathbf{Z}(0)^{2}G(0)$
$\displaystyle=$ $\displaystyle
x_{\circ}\left(\frac{x_{\circ}}{y}\big{(}\mathbf{F}(x_{\circ},y)^{2}G(y)-\mathbf{F}(x_{\circ},0)^{2}G(0)\big{)}\right)+x_{\circ}^{2}\mathbf{F}(x_{\circ},0)^{2}G(0)$
$\displaystyle=$ $\displaystyle
x_{\circ}F(x_{\circ},y)+x_{\circ}=\mathbf{Z}(y),$

but this identity is equivalent to the following recursive distributional
equation for $Z$:

$Z\overset{(d)}{=}(Z_{1}+Z_{2}+A-1)_{+},$

where on the right-hand side the variables are independent and $Z_{1},Z_{2}$
are two copies of law $Z$.

This recursive distributional equation enables us to decorate the vertices of
$\mathbb{B}$ by i.i.d. variables $A_{u}$ in such a way that for every $n$, the
parking on $[\mathbb{B}]_{n}$ together with i.i.d. fluxes on
$\partial[\mathbb{B}]_{n}$ yields a flux of law $Z$ at the root (in a coherent
manner). Replacing the i.i.d. fluxes on $\partial[\mathbb{B}]_{n}$ by null
fluxes on $\partial[\mathbb{B}]_{n}$, and writing $X_{n}=X([\mathbb{B}]_{n})$
for the number of cars visiting the root for the parking on
$[\mathbb{B}]_{n}$, we deduce by comparison that the flux at the root
$\mathrm{F_{n}}=(X_{n}-1)_{+}$ is dominated by the a.s. finite random variable
$Z$, which implies in particular that the parking on $\mathbb{B}$ with law
$\mu$ is subcritical. Et voilà. ∎

##  4 Enumeration of fully parked trees

This section is the analytic core of the paper. We write the recursive
equations (Tutte’s equation) for fully parked trees and solve them using the
kernel method of Bousquet-Mélou & Jehanne [4]. Combined with Proposition 2
this enables us to prove our main results easily. The results are similar to
the work of Chen [6] which considered plane fully-parked trees (as opposed to
our binary case). Notice also that the technical part of [6] consists in
obtaining asymptotics for the coefficients, a goal that we did not pursue in
these pages.

###  4.1 Solving Tutte’s equation

Recall that $F(x,y)$ is the bivariate generating function of the fully parked
trees where $x$ encodes the number of vertices of the tree and $y$ the flux of
cars and $G$ is the generating function of the car arrivals. To enumerate
fully parked trees, we decompose them at their root vertices. Take a fully
parked tree with $n\geqslant 1$ vertices and $n+p$ cars in total (the flux of
cars is $p$). Then

  * •

either $n=1$ which means that the root vertex has no vertex above it. In this
case, at least one car arrives on this vertex (since the root vertex should
contain a parked car) and the number of cars arriving on this vertex is $1+p$.
Summing over $p$ gives the term $x(G(y)-G(0))/y$.

  * •

Another possibility is that the root vertex has a unique child in the fully
parked tree, which can be the left or right neighbor in $\mathbb{B}$. In that
case, the subtree above this child is a fully parked tree with $n-1$ vertices
and a flux of cars $p_{1}$ where $p_{1}+\ell-1=p$ if there are $\ell$ cars
arriving on the initial root vertex. Notice that the case $p_{1}=\ell=0$ is
excluded since otherwise the root vertex is not parked. Summing over $p$
yields the term $2x(F(x,y)G(y)-F(x,0)G(0))/y$.

  * •

The last case is when the root vertex has two parked children, each carrying a
fully parked tree above it with respective sizes $k\geqslant 1$ and
$n-k-1\geqslant 1$ and flux of cars $p_{1}$ and $p_{2}$. To obtain a flux of
cars $p$ at the root, one must have $p_{1}+p_{2}+\ell-1=p$ where $\ell$ is the
number of cars arriving at the root vertex. Again the case
$p_{1}=p_{2}=\ell=0$ is excluded. We thus obtain a term
$x(F(x,y)^{2}G(y)-F(x,0)^{2}G(0))/y.$

Figure 4:  Illustration of Tutte’s recursive decomposition at the root vertex.
On the left a fully parked tree with flux $p$. If $n=1$, then the tree is just
a vertex with $p+1$ cars arriving on it. Otherwise, it has one or two children
which are the root of smaller fully parked tree.

Summing these three terms, we obtain the following recursive equation for $F$:

$yF(x,y)=x(G(y)-G(0))+2x(F(x,y)G(y)-F(x,0)G(0))+x(F(x,y)^{2}G(y)-F(x,0)^{2}G(0))$
(9)

With our notation $\mathbf{F}=F+1$ and
$\mathbf{F}_{0}(x)=\mathbf{F}(x,0)=F(x,0)+1$, this equation simplifies to

$\displaystyle P(\mathbf{F}(x,y),\mathbf{F}_{0}(x),x,y)=0\quad\mbox{ where
}\quad P(f,f_{0},x,y)=y+f^{2}xG(y)-fy-f_{0}^{2}xG(0).$ (10)

To solve this equation, we apply the kernel method of Bousquet-Mélou and
Jehanne [4] and look for a (formal) power series $Y=Y(x)$ such that
$\partial_{f}P(\mathbf{F}(x,Y(x)),\mathbf{F}_{0}(x),x,Y(x))=0$ so that
combined with (10) we also find automatically
$\partial_{y}P(\mathbf{F}(x,Y(x)),\mathbf{F}_{0}(x),x,Y(x))=0$. This
introduction may seem ad-hoc, but it enables us to find a system of three
equations on the three unknowns $\mathbf{F},\mathbf{F}_{0}$ and $Y$, so that
with a little luck we will find an “expression” for those. Actually, as we
will see below $x\mapsto Y(x)$ is a convenient change of variable which
simplifies our expressions. To summarize, we are looking for a solution
$Y\equiv Y(x)$ to the following system:

$\left\\{\begin{array}[]{l}Y-2x\mathbf{F}G(Y)=0,\\\
1+xG^{\prime}(Y)\mathbf{F}^{2}=\mathbf{F},\\\
Y+xG(Y)\mathbf{F}^{2}=Y\mathbf{F}+xG(0)\mathbf{F}_{0}^{2}.\end{array}\right.$
(11)

Thanks to the first equation, we know that $\mathbf{F}=Y/(2xG(Y)).$ Replacing
$\mathbf{F}$ by this quantity in the second equation, we obtain

$\displaystyle
1+\frac{Y^{2}G^{\prime}(Y)}{4xG(Y)^{2}}=\frac{Y}{2xG(Y)}\quad\mbox{ that is
}\quad Y=x\left(\frac{4G(Y)^{2}}{2G(Y)-YG^{\prime}(Y)}\right),$ (12)

which makes it clear that $Y\equiv Y(x)$ exists as a power series (and even
with a positive radius of convergence in a neighborhood of $0$). Once the
existence of $Y$ is granted, we use again the system of equations (11) to
obtain an equation that only involves $\mathbf{F}_{0}(x)$ and $Y(x).$ If we
replace in the third equation $\mathbf{F}$ by $Y/(2xG(Y))$ (which is a
consequence of the first equation) and $x$ by
$\frac{Y(2G(Y)-YG^{\prime}(Y))}{4G(Y)^{2}}$, we obtain

$\frac{4YG(Y)}{2G(Y)-YG^{\prime}(Y)}+\frac{\mathbf{F}_{0}^{2}YG(0)(2G(Y)-YG^{\prime}(Y))}{G(Y)^{2}}=4Y.$

This equation is quadratic in $\mathbf{F}_{0}(x)$ and using the fact that it
has non negative coefficients we obtain

$\mathbf{F}_{0}(x)=\frac{2G(Y)\sqrt{G(Y)-YG^{\prime}(Y)}}{(2G(Y)-YG^{\prime}(Y))\sqrt{G(0)}}\quad\mbox{with}\quad
Y\equiv Y(x)\mbox{ as in \eqref{eq:lagrange}}.$ (13)

We have found here an “explicit” solution for $\mathbf{F}_{0}(x)$ around
$x=0$. Coming back to Tutte’s equation, once $\mathbf{F}_{0}$ is known this
equation is quadratic in $\mathbf{F}$ and we can solve it into

$\displaystyle\mathbf{F}(x,y)=\frac{y\pm\sqrt{y^{2}+4G(y)x(G(0)\mathbf{F}_{0}(x)^{2}x-y)}}{2G(y)x}.$
(14)

The sign in front of the square root can actually change since the function
inside the square root vanishes when $y=Y(x)$ and we need to change branch to
keep an analytic function. But we shall not use the exact expression in what
follows.

###  4.2 Radius of convergence

In this section we use the explicit resolution of the functional equation (10)
to determine the radius of convergence $x_{c}$ of $\mathbf{F}_{0}$ and the
value of $\mathbf{F}_{0}(x_{c})$. The important fact for our application to
parking being that under the condition $(\star)$ on the existence of $t_{c}$
in Theorem 1 we have

$\mathbf{F}_{0}(x_{c})=\frac{2G(t_{c})\sqrt{G(t_{c})-t_{c}G^{\prime}(t_{c})}}{(2G(t_{c})-t_{c}G^{\prime}(t_{c}))\sqrt{G(0)}}.$

Recall from (13) that $\mathbf{F}_{0}(x)$ is an explicit function of $Y(x)$
itself given by the implicit equation (12).

#### Analyticity of $Y$.

We first determine the analytic properties of the change of variable $x\mapsto
Y(x)$. Recall from (12) that $x$ and $Y=Y(x)$ are linked by the equation

$x=\frac{Y(2G(Y)-YG^{\prime}(Y))}{4G(Y)^{2}},\quad\mbox{ equivalently}\quad
x=\psi(Y(x))\quad\mbox{ with
}\psi(y)=\frac{y(2G(y)-yG^{\prime}(y))}{4G(y)^{2}}.$ (15)

Note that

$\partial_{y}\psi(y)=\frac{2(G(y)-yG^{\prime}(y))^{2}-y^{2}G(y)G^{\prime\prime}(y)}{4G(y)^{3}}$

and in particular $\psi(0)=0$ and $\psi^{\prime}(0)>0$ so that by the implicit
function theorem, we can define $Y$ in a neighborhood of $0$ such that
$x=\psi(Y(x))$. Recall the condition $(\star)$ from Theorem 1 which says that
the function $y\mapsto
y^{2}G^{\prime\prime}(y)G(y)-2(G(y)-yG^{\prime}(y))^{2}$ at the numerator of
$\partial_{y}\psi(y)$ reaches $0$ at time $t_{c}\in(0,\infty)$, see Figure 5.

######  Remark.

In particular if $G$ has an infinite radius of convergence then $(\star)$
holds. Indeed, the quantity $G(y)-yG^{\prime}(y)=\sum_{k\geqslant
0}\mu_{k}(1-k)y^{k}$ equals $G(0)=\mu_{0}>0$ at $y=0$ and is bounded from
above by $\mu_{0}-(1-\mu_{0}-\mu_{1})y^{2}$ for $y>1$ which goes to $-\infty$
as $y\to+\infty$. Thus, there exists $z_{c}$ such that
$G(z_{c})-y_{c}G^{\prime}(z_{c})=0$ and the function $y\mapsto
y^{2}G^{\prime\prime}(y)G(y)-2(G(y)-yG^{\prime}(y))^{2}$ is positive at
$y=z_{c}$. Since it is negative at $y=0$, then ($\star$) holds and
$t_{c}\in(0,z_{c}).$
The assumption $(\star)$ is also satisfied when $G$ has a finite radius of
convergence $y_{c}$ and (at least) one of the three quantities $G(y_{c})$,
$G^{\prime}(y_{c})$, $G^{\prime\prime}(y_{c})$ is infinite. In case
$G(y_{c})=\infty$, starting from $yG^{\prime}(y)-G(y)=y\sum_{k\geqslant
0}\mu_{k}(k-1)y^{k-1}$, and noting that
$\mu_{k}(k-1)y^{k-1}\sim\mu_{k}ky^{k-1}$, we deduce that
$yG^{\prime}(y)-G(y)\sim yG^{\prime}(y)$ as $y\to y_{c}$, hence
$G(y)-yG^{\prime}(y)$ again has limit $-\infty$ as $y\to\infty$, and the same
argument as above applies. The last cases are obvious : in case
$G^{\prime}(y_{c})=\infty$ but $G(y_{c})<\infty$, $G(y)-yG^{\prime}(y)$
plainly has limit $-\infty$; last, in case $G^{\prime\prime}(y_{c})=\infty$
but $G^{\prime}(y_{c})<\infty$, we directly have $\lim_{y\to
y_{c}}y^{2}G^{\prime\prime}(y)G(y)-2(G(y)-yG^{\prime}(y))^{2}=+\infty.$

To clarify the reader’s spirit and for latter discussion, let us classify the
possible scenarios according to the three cases identified in Chen [6, Figure
1], see Figure 5:

  * •

the most common case is when $t_{c}$ exists and is strictly less than the
radius of convergence $y_{c}$ of $G$. At this point we have

$\left.\frac{\partial^{2}}{\partial y\partial
y}\psi(y)\right|_{y=t_{c}}=\frac{t_{c}}{4G(t_{c})^{3}}\left(2(t_{c}G^{\prime}(t_{c})-2G(t_{c}))G^{\prime\prime}(t_{c})-t_{c}G(t_{c})G^{\prime\prime\prime}(t_{c})\right),$

and since $G(t_{c})\geqslant t_{c}G^{\prime}(t_{c})$ this second derivative is
strictly negative so that the function $y\mapsto\psi(y)$ reaches a local
maxima at this point. We call this situation the generic situation.

  * •

it could also happen that $t_{c}$ exists and is equal to the radius of
convergence of $G$. In this case, although $y\mapsto\psi(y)$ reaches a maxima
at $t_{c}$, the local behavior around the maximum may not be quadratic. We
call this situation the non-generic situation.

  * •

Otherwise $t_{c}$ does not exists and in particular the radius $y_{c}$ of
convergence of $G$ is finite and $y\mapsto\psi(y)$ has a finite positive
derivative at $y_{c}$. This is the dense situation which leave aside for the
moment.

Figure 5: Illustration of the three scenarios for the change of variable
$x\mapsto Y(x)$. Our standing assumption $(\star)$ holds in the first two
cases.

Under the assumption $(\star)$ –i.e. except in the dense situation– we
introduce

$\displaystyle
x_{c}=\psi(t_{c})=\frac{t_{c}(2G(t_{c})-t_{c}G^{\prime}(t_{c}))}{4G(t_{c})^{2}}.$
(16)

######  Lemma 2.

Under assumption $(\star)$ the function $x\mapsto Y(x)$ is increasing and
analytic over $[0,x_{c})$ and furthermore

$\lim_{x\to x_{c}}Y^{\prime}(x)=\infty.$

###### Proof.

Under the assumption $(\star)$ the function $y\mapsto\psi(y)$ is increasing
and analytic over $[0,t_{c})$ so that by the analytic version of the implicit
function theorem one can define its increasing inverse function $x\mapsto
Y(x)$ over $[0,x_{c})$. Note that since $\psi^{\prime}(y)\to 0$ as $y\uparrow
y_{c}$ we have $Y^{\prime}(x)\to\infty$ as $x\uparrow x_{c}$.∎

#### Radius of convergence of $\mathbf{F}_{0}$.

We still suppose $(\star)$. Coming back to $\mathbf{F}_{0}$, notice that
$(G(Y(x))-Y(x)G^{\prime}(Y(x)))$ is always positive for $x\in[0,x_{c}]$, thus
by Equation (13) the function $\mathbf{F}_{0}$ is also analytic over
$[0,x_{c})$. Since $\mathbf{F}_{0}$ only has positive coefficients, by
Pringsheim’s Theorem (see for example [13, Theorem IV.6 p.240]), its radius of
convergence is _at least_ $x_{c}$. The following lemma shows that it actually
coincides with it

######  Lemma 3.

Suppose $(\star)$ then we have

$\lim_{x\to x_{c}}\mathbf{F}^{\prime\prime}_{0}(x)=\infty,$

in particular the radius of convergence of $\mathbf{F}_{0}$ is equal to
$x_{c}$.

###### Proof.

We use our explicit computations of $\mathbf{F}_{0}$ and $Y$ to derive
formulas for the first two derivatives of $x$. Even if we don’t need it for
this lemma, we start with the first derivative. We take the expression of
$\mathbf{F}_{0}$ given by Equation (13), differentiate it with respect to $x$
and replace the occurence of $Y^{\prime}(x)$ by $1/(\partial_{y}\psi(Y(x)))$
thanks to Equation (15). We obtain

$\mathbf{F}^{\prime}_{0}(x)=\frac{4G(Y(x))^{3}G^{\prime}(Y(x))}{\sqrt{G(Y(x))-Y(x)G^{\prime}(Y(x))}(2G(Y(x))-Y(x)G^{\prime}(Y(x)))^{2}}.$

This quantity has a finite limit when $Y(x)$ converges to $t_{c}$. We thus
need to compute the second derivative of $\mathbf{F}_{0}$. To do so, we
differentiate the above expression of $\mathbf{F}^{\prime}_{0}$ and again
replace the occurence of $Y^{\prime}(x)$ by $1/(\partial_{y}\psi(Y(x)))$. We
then obtain a fraction involving the derivatives of $G$ at $Y(x)$. Using the
definition of $t_{c}$ under assumption $(\star)$, we can show that

$\displaystyle\lim_{x\to x_{c}}\mathbf{F}_{0}^{\prime\prime}(x)=\lim_{t\to
t_{c}}\frac{16G(t)^{6}(2G(t)-tG^{\prime}(t))^{3}(G(t)-tG^{\prime}(t))(2G(t)-tG^{\prime}(t))^{2}}{t^{2}(G(t)-tG^{\prime}(t))^{3/2}\cdot(2(G(t)-tG^{\prime}(t))^{2}-t^{2}G(t)G^{\prime\prime}(t))}=+\infty,$

since all but the factor
$(2(G(t)-tG^{\prime}(t))^{2}-t^{2}G(t)G^{\prime\prime}(t)$ are positive for
$t<t_{c}$ and have a positive limit as $t\to t_{c}$. ∎

##  5 Probabilistic consequences

Armed with our enumeration results and the criterion of Proposition 2, we can
now proceed to the proof of our main results.

###  5.1 Theorem 1: Location of the threshold

Recall that by Proposition 2, the parking process is subcritical if and only
if there exists a positive solution to (8). When $(\star)$ holds, since the
function $x\mapsto G(0)x\mathbf{F}_{0}(x)$ is strictly increasing, Equation
(8) has a solution if and only if $G(0)x_{c}\mathbf{F}_{0}(x_{c})^{2}\geqslant
1$ where $x_{c}$ is the radius of convergence of $\mathbf{F}_{0}$ found in the
previous paragraph. Now, since $t_{c}=Y(x_{c})$ and plugging the value of
$\mathbf{F}_{0}(x_{c})$ given by Equation (13) in
$G(0)x_{c}\mathbf{F}_{0}(x_{c})^{2}\geqslant 1$, we obtain
$t_{c}+\frac{t_{c}G(t_{c})}{t_{c}G^{\prime}(t_{c})-2G(t_{c})}\geqslant 1$.

By definition of $t_{c}$ under Assumption ($\star$), the quantity
$t_{c}G^{\prime}(t_{c})-2G(t_{c})<t_{c}G^{\prime}(t_{c})-G(t_{c})$ is always
negative. Hence there is a solution $x$ to (8) if and only if $t_{c}$
satisfies

$(t_{c}-2)G(t_{c})\geqslant t_{c}(t_{c}-1)G^{\prime}(t_{c}),$

which together with Proposition 2 concludes the proof of Theorem 1.

######  Remark.

Notice that if $t_{c}$ satisfies the condition of Theorem 1, then it is
greater than $2$. This implies that if the parking process is subcritical,
then the radius of convergence of the generating function $G$ of the car
arrivals is at least $2$. To see it, first note that the inequality
$(t-2)G(t)\geqslant t(t-1)G^{\prime}(t)$ can not be satisfied for $t\in[1,2]$
since the left-hand side is non-positive and equals $0$ only for $t=2$,
whereas the right-hand side is non-negative and equals $0$ for $t=0$ and $t=1$
only. Neither can this inequality be satisfied for $t\in(0,1)$, because for
such $t$, we can bound from above the quantity $t(t-1)G^{\prime}(t)/(t-2)$ by
$(3-2\sqrt{2})G^{\prime}(1)\leqslant(3-2\sqrt{2})G^{\prime}(1)\leqslant 1/5$
since $G^{\prime}(1)=\mathbb{E}[A]\leqslant 1$ in the subcritical case. On the
other side, the quantity $G(t)$ is bounded from below by $G(0)\geqslant 1/2.$

###  5.2 Theorem 2: critical computations

Before moving on to the critical computation (Theorem 2) let us prove that the
critical case caracterized by the equality in the second display of Theorem 1
actually corresponds to the natural fact that one ”cannot increase the number
of cars” and stay subcritical:

######  Lemma 4 (Criticality).

Suppose $(\star)$. Then we have equality in (1) iff for any $\varepsilon>0$
the law with generating function $G_{\varepsilon}(t)=G(t)+\varepsilon
t-\varepsilon$ is supercritical.

###### Proof.

Suppose that $\mu$ is subcritical in the sense of Theorem 1 and look at the
probability measure $\mu_{\varepsilon}$ such that its generating function is
given by $G_{\varepsilon}(t)=G(t)+\varepsilon t-\varepsilon$ for some
$\varepsilon>0$. First notice that $\mu_{\varepsilon}$ satisfies Assumption
($\star$) for $\varepsilon$ small enough. Indeed the radius of convergence of
$G_{\varepsilon}$ is that of $G$ and the quantity

$\displaystyle
2(G_{\varepsilon}(t)-tG_{\varepsilon}^{\prime}(t))^{2}-t^{2}G_{\varepsilon}(t)G_{\varepsilon}^{\prime\prime}(t)$
$\displaystyle=$
$\displaystyle(2(G(t)-tG^{\prime}(t)-\varepsilon)^{2}-t^{2}(G(t)+\varepsilon(t-1))G^{\prime\prime}(t)$
$\displaystyle=$ $\displaystyle
2(G(t)-tG^{\prime}(t))^{2}-t^{2}G(t)G^{\prime\prime}(t)$
$\displaystyle\qquad+2\varepsilon^{2}-2\varepsilon(G(t)-tG^{\prime}(t))-\varepsilon
t^{2}(t-1)G^{\prime\prime}(t)$

is negative at $t_{c}$ when $\varepsilon$ is small enough, so that
$t_{c}^{\varepsilon}:=\min\\{t\geqslant 0,\
2(G_{\varepsilon}(t)-tG_{\varepsilon}^{\prime}(t))^{2}=t^{2}G_{\varepsilon}(t)G_{\varepsilon}^{\prime\prime}(t)\\}<t_{c}$
and the function $\varepsilon\mapsto t_{c}^{\varepsilon}$ is continuous in a
positive neighborhood of $0$. To determine whether $\mu_{\varepsilon}$ is
subcritical or not, we then need to determine the sign of

$(t_{c}^{\varepsilon}-2)G_{\varepsilon}(t_{c}^{\varepsilon})-t_{c}^{\varepsilon}(t_{c}^{\varepsilon}-1)G_{\varepsilon}^{\prime}(t_{c}^{\varepsilon}),$

which is then continuous is $\varepsilon$. Thus if Equation (1) is not an
equality, we can increase $\mu$ and remain subcritical.

Suppose now that (1) is an equality. We can show that

$\partial_{y}\varphi_{\varepsilon}(t_{c}-\delta)=\frac{6G(t_{c})+t_{c}^{2}G^{(3)}(t_{c})(t_{c}-1)^{3}}{4G(t_{c})^{2}(t_{c}-1)^{3}}\delta-\frac{3}{2(t_{c}-1)G(t_{c})^{2}}\varepsilon+o(\varepsilon)+o(\delta).$

When $t_{c}-\delta=t_{c}^{\varepsilon}$, then the left hand side is zero so
that the main asymptotic on the right hand side should be $0$. Hence
$\delta=t_{c}-t_{c}^{\varepsilon}$ is of order $\varepsilon.$ Moreover,

$(t_{c}^{\varepsilon}-2)G_{\varepsilon}(t_{c}^{\varepsilon})-t_{c}^{\varepsilon}(t_{c}^{\varepsilon}-1)G_{\varepsilon}^{\prime}(t_{c}^{\varepsilon})=-2\varepsilon(t_{c}^{\varepsilon}-1)+O((t_{c}^{\varepsilon}-t_{c})^{2}).$

is negative when $\varepsilon$ small enough and $\mu_{\varepsilon}$ is
supercritical by Theorem 1. ∎

###### Proof of Theorem 2.

. Let us focus now on the case when (1) is an equality. In that case, since
(8) is an equality for $x=x_{c}$, then $x_{c}=p_{\circ}.$ If $x$ satisfies
Equation (15) and the parking is critical, so that $y=t_{c}$ is solution of
$(t-2)G(t)=t(t-1)G^{\prime}(t)$, then

$x=x_{c}=\frac{t_{c}^{2}}{4(t_{c}-1)G(t_{c})}\qquad\mbox{and}\qquad\mathbf{F}_{0}(x_{c})^{2}=\frac{1}{p_{\circ}G(0)}=\frac{1}{p_{\circ}\mu_{0}}.$
(17)

Moreover, using Equation (6), we obtain

$p_{\bullet}=\sqrt{\frac{p_{\circ}}{\mu_{0}}}-p_{\circ},$

and this concludes the proof of Theorem 2. ∎

######  Remark.

The fact that $p_{\circ}>1/2$ is a consequence of the equation for $t$ given
by Theorem 1. Indeed, in the critical case, then
$p_{\circ}=x_{c}=t_{c}^{2}/(4(t_{c}-1)G(t_{c}))$ where $t_{c}$ is given by
Theorem 1. But since $t_{c}>1$, we have
$G(t_{c})-G(1)\leqslant(t_{c}-1)G^{\prime}(t_{c})=(t_{c}-2)G(t_{c})/t_{c}$.
Thus $G(t_{c})\leqslant t_{c}/2$ and

$p_{\circ}\geqslant\frac{2t_{c}}{t_{c}-1}>1/2.$

###  5.3 Examples

Let us proceed to the computation of the critical threshold for parking for
various families of stochastically increasing laws. In the first four cases
below, it is easy to check that condition $(\star)$ holds so that we can just
apply the general formulas. In the last example we explain how our techniques
can be applied even if $(\star)$ does not hold.

#### Binary0/2 car arrivals.

As a first example, we can imagine that either $0$ or $2$ cars arrive at each
spot, i.e. the law of the car arrivals is
$\mu=(1-\frac{\alpha}{2})\delta_{0}+\frac{\alpha}{2}\delta_{2}$, so that
$G(t)=(1-\frac{\alpha}{2})+\frac{\alpha}{2}t^{2}$. This is the example
considered in [14, Proposition 3.5] and [1, Proposition 4]. Explicit
computations show in this case that

$t_{c}=Y(x_{c})=\sqrt{\frac{2-\alpha}{3\alpha}},\qquad
x_{c}=\frac{3\sqrt{3}}{16\sqrt{\alpha(2-\alpha)}}\qquad\mbox{and}\qquad\mathbf{F}_{0}(x_{c})=\frac{4\sqrt{6}}{9}\cdot$

Note that $\mathbf{F}_{0}(x_{c})$ does not depend on $\alpha$, see the remark
below. We then see that for $t=t_{c}$, the Inequality (1) is quadratic in
$\alpha$ and is satisfied as soon as $\alpha<\alpha_{c}=1/14$.

#### Binary0/k car arrivals.

In the case when
$\mu=(1-\frac{\alpha}{k})\delta_{0}+\frac{\alpha}{k}\delta_{k}$, so that
$G(t)=(1-\frac{\alpha}{k})+\frac{\alpha}{k}t^{k}$ with $k\geqslant 3$, we have

$Y(x_{c})=\left(\frac{(k-a)(-4+k(3+k-\sqrt{(k-1)(k+7)})}{2a(k-2)(k-1)}\right)^{1/k},$
$\mathbf{F}_{0}(x_{c})=\frac{\sqrt{2}(3k-\sqrt{(k-1)(k+7)}-3)}{(k-2)(k-1)\sqrt{\frac{5-k+\sqrt{(k-1)(k+7)}}{(k-1)k}}}.$

so that the model is critical at

$\alpha_{c}(\mathrm{Binary}_{0/k})=\frac{k}{1+2^{-k-2}\left(3+\sqrt{\frac{k+7}{k-1}}\right)^{k}\left((k-1)(k+4)+k\sqrt{(k+7)(k-1)}\right)}.$

#### Poisson.

Suppose the law of the car arrivals is Poisson with mean $\alpha>0$, so that
in this case $G(t)=e^{\alpha(t-1)}.$ Again, explicit computation show that

$Y(x_{c})=\frac{2-\sqrt{2}}{\alpha},\qquad
x_{c}=\frac{(\sqrt{2}-1)\mathrm{e}^{\alpha-2+\sqrt{2}}}{2\alpha}\qquad\mbox{and}\qquad\mathbf{F}_{0}(x_{c})=\sqrt{2(\sqrt{2}-1)}\mathrm{e}^{1-1/\sqrt{2}},$

so that the model is subcritical for parking as long as
$\alpha\leqslant\alpha_{c}$ with

$\alpha_{c}=3-2\sqrt{2}.$

#### Geometric.

Consider here the case when $G(t)=1/(1+\alpha-\alpha t)$. Then

$Y(x_{c})=\frac{1+\alpha}{3\alpha},\qquad
x_{c}=\frac{(1+\alpha)^{2}}{12\alpha}\qquad\mbox{and}\qquad\mathbf{F}_{0}(x_{c})=\frac{2}{\sqrt{3}}\cdot$

so that the model is subcritical for parking as long as
$\alpha\leqslant\alpha_{c}$ with $\alpha_{c}=1/8.$

######  Remark (Combinatorial counting).

The reader may be puzzled by the fact that in the last four cases the value
$\mathbf{F}_{0}(x_{c})$ does not depend on the parameter $\alpha$. This is
because in each case, the dependence on $\alpha$ of the $\mu_{\alpha}$-weight
of a fully parked tree of size $n$ is of the form $(c_{\alpha})^{n}$, for a
constant $c_{\alpha}$ depending on $\alpha$ that cancels out at criticality.
To wit, consider fully-parked trees associated with $0/k$ arrivals : in this
case, for $n$ a multiple of $k$, fully parked trees of size $n$ have weight
$\prod_{v}\mu_{a(v)}=\mu_{0}^{n/k}\mu_{k}^{(1-1/k)n}=(\mu_{0}^{1/k}\mu_{k}^{(1-1/k)})^{n}$.

#### Without $(\star)$.

When hypothesis $(\star)$ is not satisfied we can still apply our method: If
the generating series $G$ has a radius of convergence $y_{c}$ then the value
$t_{c}$ is then replaced by

$\tilde{t}_{c}=\min\left\\{y_{c},\min\\{t\geqslant 0:\
2(G(t)-tG^{\prime}(t))^{2}=t^{2}G(t)G^{\prime\prime}(t)\\}\right\\},$

and we need to check that $\tilde{x}_{c}$ defined analogously by (16) is again
the radius of convergence of the series $\mathbf{F}_{0}$ (we did not try to
prove such a general statement here). Then using Proposition 2, the
subcriticality of the parking is equivalent to the fact that
$\mu_{0}\tilde{x}_{c}(\mathbf{F}_{0}(\tilde{x}_{c}))^{2}\geqslant 1$, the only
different point is that we cannot use the equality
$2(G(\tilde{t}_{c})-\tilde{t}_{c}G^{\prime}(\tilde{t}_{c}))^{2}=\tilde{t}_{c}^{2}G(\tilde{t}_{c})G^{\prime\prime}(\tilde{t}_{c})$
to further simplify the expression. As an example of such law, consider the
generating function

$\displaystyle
G(t)=1+\frac{1+t^{2}}{26}-\frac{1}{13}\left(\frac{3-t}{2}\right)^{7/3}.$ (18)

The radius of convergence of $G$ is equal to $3$ but $G^{\prime}(3)$ and
$G^{\prime\prime}(3)$ exist. An explicit computation shows that $(\star)$
holds with $t_{c}=y_{c}=\tilde{t}_{c}=3$ for $G$, and furthermore $G$ is
critical for the parking process. However if one considers
$\tilde{G}=0.9+0.1G$ then $\tilde{t}_{c}=3$ and $(\star)$ does not hold but
still $\tilde{G}$ is subcritical for the parking process.

##  6 Extensions and comments

In this work, we voluntarily stick to the simplest case of the binary tree
with i.i.d. arrivals without specific conditions to keep the paper accessible
to a wide audience. Let us mention a few perspectives that our approach opens:

###  6.1 Non-generic and dense case

In this work, we focused on the localization of the threshold and on the
computation of some critical quantities. One could also try to get scaling
limits of critical components and compute several critical or near-critical
exponents. As mentioned in the introduction, we expect that a large family of
critical car arrivals (say, with bounded support) belong to a common
universality class where we expect that the cluster size of the root has a
tail that decays as $n^{-5/2}$ as $n\to\infty$ and where the scaling limits of
the critical components are given by $3/2$-stable Growth-Fragmentation trees.
But when the car arrivals have a heavy tail (and when the parameters are fine-
tuned so that the law is critical), we hope to see different universality
classes. Actually, as seen in Section 4.2, the singular behavior of
$\mathbf{F}_{0}$ near its radius of convergence is linked to the behavior of
the $Y(x)$ near near $x_{c}$, see Figure 5. For instance, in the example (18)
an explicit computation shows that the singular behavior of
$\mathbf{F}_{0}(3-x)-\mathbf{F}_{0}(3)$ is of the form $Cx^{4/3}$ which
indicates a polynomial decay of the critical cluster with exponent $n^{-7/3}$.
This is very similar to the scenarios that happened in the enumeration of
plane fully parked trees in Chen [6], with the notable difference that in our
model the dense case can be critical for the parking process. See also [7,
Theorem 1.2] for the Derrida-Retaux model with heavy-tailed distributions
where the free-energy has a peculiar behavior. We plan on studying those
different behaviors in forthcoming works.

###  6.2 General case of $d$-ary tree and GW trees

Our work may be extended to parking on more general trees such as $d$-ary
trees and perhaps supercritical Bienaymé–Galton–Watson trees. The crux is of
course the enumeration of fully parked trees. In the case of supercritical
Bienaymé–Galton–Watson trees, one would probably need the addition of another
variable $z$ counting the number of adjacent vertices of the fully parked tree
inside the global tree (in our case, we had a fixed number $n+1$ of vertices
adjacent from above to a fully parked tree of $\mathbb{B}$ of size $n$). We
wonder whether the randomness of the underlying tree may yield to different
universality classes compared to the case of $d$-ary trees.

###  6.3 Links with Derrida-Retaux model

As mentioned several times in the paper, the Derrida-Retaux model is closely
related to the parking process on $\mathbb{B}$. We wonder whether a firm
connection can be made between the two models.

## References

  * [1] R. Bahl, P. Barnet, and M. Junge, Parking on supercritical Galton-Watson trees, arXiv:1912.13062, (2019).
  * [2] J. Bertoin, T. Budd, N. Curien, and I. Kortchemski, Martingales in self-similar growth-fragmentations and their connections with random planar maps, Probab. Theory Related Fields, 172 (2018), pp. 663–724.
  * [3] J. Bertoin, N. Curien, and I. Kortchemski, Random planar maps and growth-fragmentations, Ann. Probab., 46 (2018), pp. 207–260.
  * [4] M. Bousquet-Mélou and A. Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, J. Combin. Theory Ser. B, 96 (2006), pp. 623–672.
  * [5] P. Chassaing and G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence, Random Structures & Algorithms, 21 (2002), pp. 76–119.
  * [6] L. Chen, Enumeration of fully parked trees, arXiv preprint arXiv:2103.15770, (2021).
  * [7] X. Chen, V. Dagard, B. Derrida, Y. Hu, M. Lifshits, and Z. Shi, The Derrida–Retaux conjecture on recursive models, The Annals of Probability, 49 (2019), pp. 637–670.
  * [8] A. Contat, Sharpness of the phase transition for parking on random trees, Random Structures & Algorithms, (2020).
  * [9] , Last car decomposition of planar maps, arXiv preprint arXiv:2205.10285, (2022).
  * [10] A. Contat and N. Curien, Parking on Cayley trees & frozen Erdös-Rényi, arXiv:2107.02116.
  * [11] N. Curien, Peeling random planar maps, Saint-Flour course 2019, https://www.imo.universite-paris-saclay.fr/$\sim$curien/.
  * [12] N. Curien and O. Hénard, The phase transition for parking on Galton-Watson trees, Discrete Analysis, (2022).
  * [13] P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge University Press, 2009.
  * [14] C. Goldschmidt and M. Przykucki, Parking on a random tree, Combinatorics, Probability and Computing, 28 (2019), pp. 23–45.
  * [15] W. King and C. H. Yan, Prime parking functions on rooted trees, Journal of Combinatorial Theory, Series A, 168 (2019), pp. 1–25.
  * [16] A. G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM Journal on Applied Mathematics, 14 (1966), pp. 1266–1274.
  * [17] M.-L. Lackner and A. Panholzer, Parking functions for mappings, Journal of Combinatorial Theory, Series A, 142 (2016), pp. 1 – 28.
  * [18] J.-F. Le Gall and A. Riera, Growth-fragmentation processes in Brownian motion indexed by the Brownian tree, Annals of Probability, 48 (2020), pp. 1742–1784.
  * [19] W. T. Tutte, A census of planar triangulations, Canad. J. Math., 14 (1962), pp. 21–38.