# On the radial growth of ballistic aggregation and other aggregation models

Tillmann Bosch Tillmann Bosch, Langstr. 43, 68169 Mannheim Germany
<EMAIL_ADDRESS>and  Steffen Winter Steffen Winter, Institute of
Stochastics, Karlsruhe Institute of Technology, Englerstr. 2, D-76131
Karlsruhe, Germany<EMAIL_ADDRESS>
###### Abstract.

For a class of aggregation models on the integer lattice ${\mathbb{Z}}^{d}$,
$d\geq 2$, in which clusters are formed by particles arriving one after the
other and sticking irreversibly where they first hit the cluster, including
the classical model of diffusion-limited aggregation (DLA), we study the
growth of the clusters. We observe that a method of Kesten used to obtain an
almost sure upper bound on the radial growth in the DLA model generalizes to a
large class of such models. We use it in particular to prove such a bound for
the so-called ballistic model, in which the arriving particles travel along
straight lines. Our bound implies that the fractal dimension of ballistic
aggregation clusters in ${\mathbb{Z}}^{2}$ is 2, which proves a long standing
conjecture in the physics literature.

###### Key words and phrases:

diffusion-limited aggregation, incremental aggregation, growth rate, fractal
dimension, ballistic aggregation

###### 2020 Mathematics Subject Classification:

Primary: 82B24, 60J10; Secondary: 60D05, 28A80

Steffen Winter was supported by the DFG grant 433621248.

##  1\. Introduction

Consider a process of cluster formation on the hypercubic lattice
${\mathbb{Z}}^{d}$, $d\geq 2$, which starts at time one with a single particle
placed at the origin. Then at each time step $n=2,3,\ldots$, a particle
arrives and is added to the cluster by placing it at a site neighbouring the
existing cluster. The position of the new particle is chosen at random
independently of all previous choices and according to some distribution which
only depends on the existing cluster at that time. We will call such
aggregation models _incremental aggregation_ in the sequel. Many such models
are known and have been studied intensively in the physics literature. They
differ only by the choice of the distributions governing the selection of the
locations for the arriving particles.

The most popular among these models is certainly _diffusion-limited
aggregation (DLA)_ , suggested by Witten and Sander [21] in 1981 as a model
for metal-particle aggregation. Particles arrive from ‘far away’ and perform
symmetric random walks until they hit the cluster for the first time. The
distribution specifying the resulting cluster formation mechanism is known as
the harmonic measure. The formed clusters have a dendrite-like structure and
show a fractal behaviour, see Figure 1. Another even older model is the _Eden
growth model_ due to Murray Eden [7], in which the position of the next
particle is chosen uniformly out of all sites neighboring the current cluster.
The clusters formed in this model tend to be very dense and appear ball like
with a rough boundary. Another variation is _diffusion-limited annihilation_
due to Meakin and Deutch [15], nowadays better known as _internal DLA_. Here
the particles start at the origin, i.e. within the cluster, perform symmetric
random walks and are attached where they exit the cluster. As in the Eden
model, the formed clusters tend to be ball-like with a rough boundary.

Another popular model in the physics literature is the _Vold-Sutherland model_
or _ballistic aggregation_ , in which arriving particles travel along straight
lines (ballistic trajectories) and stick where they hit the cluster. It can be
traced back to the work of the colloid chemists Marjorie J. Vold and David N.
Sutherland, see e.g. [14, 20]. It has been suggested for situations in which
molecules move in a low density vapour such that thermal interactions can be
disregarded. The clusters formed by this model are denser than the ones formed
by DLA, but have a similar dendritic structure, see Figure 1.

Figure 1. Typical realization of an aggregation cluster of DLA (left) and the
ballistic aggregation model (right) of size $n=10000$.

All these models and many variants have been studied intensively in physics
and have found numerous applications, we refer to the surveys and books [20,
19, 8, 11, 3] for further details and references. Most results have been
obtained either from simulations or from intriguing but non-rigorous
theoretical considerations. Some of these models have also inspired
mathematical research and a number of results have been obtained. However, the
progress up to now is far behind what physicists have discovered.

One of the most basic questions (to which we will mainly restrict our
attention in this paper) is the speed of growth of the radius (or diameter) of
the cluster as the number of particles tends to $\infty$. Regarding DLA, some
rigorous almost sure bounds are due to Kesten [9, 10] (with some improvements
for dimension 3 in [12] and recently in [4]), which we will recall in Section
3 below. They imply in particular that DLA clusters are not full-dimensional
(in a discrete sense) and thus exhibit some fractal behaviour. For internal
DLA (and the Eden model), the growth rate is $n^{1/d}$ in ${\mathbb{Z}}^{d}$,
as the number of particles tends to $\infty$ and thus the clusters are full-
dimensional. For internal DLA even some shape theorems have been established
showing that asymptotically the clusters are balls [13]. For the Eden model
the existence of a limit shape is also known, due to some relation of this
model to first passage percolation, cf. [1] and the references therein. The
limit shape is conjectured to deviate from a Euclidean ball. Up to now this
has only been established in very high dimensions. We refer to the survey
article [17] for an overview of further results regarding DLA und internal
DLA. In particular, in this article, attention is also given to results
obtained on graphs other than the hypercubic lattices ${\mathbb{Z}}^{d}$ that
we restrict ourselves to here. (It is obvious that the models may be
transferred to any infinite connected graph.) In contrast to the situation for
the other mentioned models, it seems that the ballistic model has not been
investigated in the maths literature so far. To the best of our knowledge, the
only paper, where it is mentioned (but not analyzed very far) is the article
[16], in which also a number of new aggregation models are proposed and
simulated.

In this article we make a first attempt to investigate rigorously the growth
behaviour of the ballistic model. To this end, we start from a more general
viewpoint and set up a natural class of models (incremental aggregation),
which includes the models mentioned above (and many more). We revisit the
argument of Kesten that he used in [9] to obtain an upper bound on the growth
rates of DLA in ${\mathbb{Z}}^{2}$ and observe that the same argument may be
applied to any incremental aggregation model. In a nutshell, the ‘method’
reduces the problem of finding a bound for the radial growth to the much
easier task to establish an upper bound on the local mass of the distributions
determining the model. We do not claim much originality here, as once the
class of incremental aggregation models is set up it is fairly easy to see
that Kesten’s argument works in general. Then we apply this new method to the
ballistic model. First we give a rigorous definition of the ballistic model
using some notions from geometric probability. Then we state some bound on the
local mass for the ballistic measures (i.e., the distributions defining the
ballistic model) and finally we apply Kesten’s method to obtain the desired
growth rates. It turns out that the method has power in particular in
dimension $d=2$. For the ballistic model in ${\mathbb{Z}}^{2}$ we establish
that the growth exponent is $1/2$ (i.e., the fractal dimension is 2), which is
the value conjectured in the physics literature. For $d\geq 3$, our results
imply that the fractal dimension is bounded from below by 2 (while the
conjectured value is $d$).

In order to illustrate our results, we have also simulated aggregation
clusters of the ballistic model (as we define it here) and DLA for comparison.
The Python code is freely available, cf. [6], together more pictures of large
simulated clusters.

The paper is organized as follows. In Section 2, we introduce incremental
aggregation and show that this class of models includes DLA and the Eden
model. In Section 3 we provide some definitions regarding radial growth and
state some trivial facts about growth exponents and fractal dimensions of our
models. We also recall the results of Kesten on the radial growth of DLA. In
Section 4, we state Kesten’s method (Theorem 4.1) for general incremental
aggregation and demonstrate how it can be applied to recover Kesten’s growth
bounds for DLA and the known bounds for the Eden model. In Section 5, we
define the ballistic model and apply Kesten’s method to obtain the mentioned
results on the growth of these models. Finally, in Section 6 we provide a
proof of our main tool, Kesten’s method.

##  2\. Incremental aggregation

We set up a framework in which all the models can be treated in a unified way.
Let $\mathcal{P}^{d}_{f}$ denote the family of finite subsets of
${\mathbb{Z}}^{d}$, i.e.

$\displaystyle\mathcal{P}^{d}_{f}:=\\{A\subset{\mathbb{Z}}^{d}\ |\ \text{A is
finite}\\},$

which we equip with the discrete $\sigma$-algebra. We consider the nearest
neighbor graph on ${\mathbb{Z}}^{d}$, i.e., the graph $({\mathbb{Z}}^{d},E)$
with vertex set ${\mathbb{Z}}^{d}$ and edge set
$E:=\\{\\{x,y\\}\subset{\mathbb{Z}}^{d}:\|x-y\|=1\\}$. (Here and throughout
$\|\cdot\|$ denotes the Euclidean norm.) A set $A\in\mathcal{P}^{d}_{f}$ is
called connected, if the subgraph of $({\mathbb{Z}}^{d},E)$ generated by $A$
is. For $A\in\mathcal{P}^{d}_{f}$, the (outer) boundary of $A$ is the set

$\displaystyle\partial A:=\\{y\in{\mathbb{Z}}^{d}\setminus A:\exists x\in
A\text{ such that }\\{x,y\\}\in E\\}.$

Throughout let $(\Omega,\mathcal{A},{\mathbb{P}})$ be some suitable
probability space. For $A\in\mathcal{P}^{d}_{f}\setminus\\{\emptyset\\}$, a
random point in $A$ is a measurable mapping $y_{A}:\Omega\to{\mathbb{Z}}^{d}$
with ${\mathbb{P}}(y_{A}\in A)=1$. Denote by $\mathcal{D}(A)$ the family of
all probability measures on $A$, i.e., of all possible distributions of a
random point in $A$. Moreover, a random finite set is a measurable mapping
$F:\Omega\to\mathcal{P}^{d}_{f}$.

######  Definition 2.1.

Let $\mathcal{M}:=(\mu_{A})_{A\in\mathcal{P}^{d}_{f}}$ be a family of
distributions s.t. $\mu_{A}\in\mathcal{D}(A)$ for each
$A\in\mathcal{P}^{d}_{f}$. A sequence $(F_{n})_{n\in{\mathbb{N}}}$ of random
finite sets $F_{n}\subset{\mathbb{Z}}^{d}$ is called incremental aggregation
(with distribution family $\mathcal{M}$), if it satisfies the following
conditions:

  1. (i)

$F_{1}:=\\{y_{1}\\}$, where $y_{1}:=0\in{\mathbb{Z}}^{d}$;

  2. (ii)

for any $n\in{\mathbb{N}}$, $F_{n+1}:=F_{n}\cup\\{y_{n+1}\\}$, where $y_{n+1}$
is a random point in ${\mathbb{Z}}^{d}$ whose conditional distribution given
$F_{n}$ is $\mu_{\partial F_{n}}$, i.e.,

$\displaystyle{\mathbb{P}}\left(y_{n+1}=y\ |F_{n}=A\right):=\mu_{\partial
A}(y)\qquad\text{ for any }A\in\mathcal{P}_{f}^{d}\text{ and
}y\in{\mathbb{Z}}^{d}.$

$F_{n}$ is called cluster or aggregate at time $n$, and
$F_{\infty}:=\bigcup_{n\in{\mathbb{N}}}F_{n}$ the infinite cluster. Observe
that

$0\in F_{1}\subset F_{2}\subset F_{3}\subset\ldots\subset
F_{\infty}\subseteq{\mathbb{Z}}^{d}.$

Moreover, for any $n\in{\mathbb{N}}$, almost surely $F_{n}$ is connected and
$\\#F_{n}=n$. It is easy to see that $(F_{n})_{n}$ is a Markov chain, in
particular, $F_{n+1}$ depends on $F_{n}$, but not on the order, in which the
points have been added to $F_{n}$. Different aggregation models arise now by
choosing different families $\mathcal{M}$ of distributions. We start with the
simple example of the Eden growth model.

######  Example 2.2 (Eden growth model).

For each $A\in\mathcal{P}^{d}_{f}$, let $\mu_{A}$ be the uniform distribution
on $A$. Then incremental aggregation with distribution family
$\mathcal{M}=(\mu_{A})_{A\in\mathcal{P}^{d}_{f}}$ is known as _Eden growth
model_. Here, given $F_{n}=A\in\mathcal{P}^{d}_{f}$, each point $y$ in the
outer boundary $\partial A$ of $A$ has exactly the same chance (namely
$1/{\\#\partial A}$) of being the next point $y_{n+1}$ added to the cluster.
From simulations one can observe that large clusters look ball-like with few
holes and a rough boundary.

Our second example of incremental aggregation is diffusion limited
aggregation. It has been introduced by Witten and Sander [21] as a model for
metal-particle aggregation and became soon very popular in physics as a simple
model for many different phenomena, where particles aggregate irreversibly and
diffusion (thermal motion) is the means of particle transport.

######  Example 2.3 (Diffusion limited aggregation (DLA)).

Let $(S^{x}_{n})_{n\in{\mathbb{N}}_{0}}$ be a symmetric random walk on
${\mathbb{Z}}^{d}$ started at $x\in{\mathbb{Z}}^{d}$, i.e.,
${\mathbb{P}}(S^{x}_{0}=x)=1$ and for each $n\in{\mathbb{N}}$ and each
$z\in{\mathbb{Z}}^{d}$

${\mathbb{P}}(S^{x}_{n}=y|S^{x}_{n-1}=z)=\frac{1}{2d},\text{ for all neighbors
}y\text{ of }z.$

For $A\subset{\mathbb{Z}}^{d}$, let
$T^{x}_{A}:=\min\\{n\in{\mathbb{N}}:S^{x}_{n}\in A\\}$ be the hitting time of
$A$. It is well known that in ${\mathbb{Z}}^{2}$, a random walk started at $x$
is recurrent, i.e. ${\mathbb{P}}(T^{x}_{\\{x\\}}<\infty)=1$, and in
${\mathbb{Z}}^{d}$, $d\geq 3$ it is transient, i.e.
${\mathbb{P}}(T^{x}_{\\{x\\}}<\infty)<1$. For $A\in\mathcal{P}^{d}_{f}$ and
any point $x\in{\mathbb{Z}}^{d}\setminus A$, define a distribution on $A$ by

$H^{x}_{A}(y):={\mathbb{P}}(S^{x}_{T^{x}_{A}}=y|T^{x}_{A}<\infty),\qquad y\in
A.$

It is a nontrivial but well established fact that by setting

$h_{A}(y):=\lim_{\|x\|\to\infty}H^{x}_{A}(y),\qquad y\in A$

a probability measure $h_{A}$ is defined on $A$. It is called the harmonic
measure of $A$. DLA is now defined to be incremental aggregation with
distribution family $(h_{A})_{A\in\mathcal{P}^{d}_{f}}$. So in the DLA model
particles perform random walks started at infinity and stick where they first
hit the existing cluster. This produces sparse dendrite-like structures as
simulations show.

Below in Section 5 we will discuss another class of models called ballistic
aggregation. In these models the particles travel along straight lines instead
of random walk paths. In order to introduce them properly, we will need some
concepts from geometric probability.

##  3\. Growth of arms

Our aim is to study the speed of growth of aggregation clusters in incremental
aggregation models. For any finite set $A\subset{\mathbb{Z}}^{d}$ with $0\in
A$, let

(3.1) $\displaystyle{\rm rad}(A):=\max_{x\in A}\|x\|$

denote its radius, where $\|\cdot\|$ denotes the Euclidean norm. Observe that

${\rm rad}(A)=\inf\\{r>0:A\subset B(0,r)\\},$

justifying the terminology. Denote by $\operatorname{diam}(A)$ the _diameter_
of $A$ and note that

(3.2) $\displaystyle\frac{1}{2}\operatorname{diam}(A)\leq{\rm
rad}(A)\leq\operatorname{diam}(A).$

Instead of the radius one could similarly work with the diameter in the
sequel, which might be more natural in any more general setting. Since we are
only interested in incremental aggregation, which is started at $0$, we stick
to the radius for historic reasons. The following simple observation bounding
the radius of a finite set $A\subset{\mathbb{Z}}^{d}$ in terms of its
cardinality $\\#A$ turns out to very useful.

######  Lemma 3.1.

Let $A\subset{\mathbb{Z}}^{d}$ be a finite, connected set with $0\in A$. Then

(3.3) $\displaystyle\frac{1}{2}(\\#A)^{1/d}\leq{\rm rad}(A)\leq\\#A.$

###### Proof.

Let $r:={\rm rad}(A)$. Then all points of $A\subset{\mathbb{Z}}^{d}$ are
contained in the ball $B(0,r)\subset[-r,r]^{d}$. Hence $\\#A\leq(2r)^{d}$,
implying the first inequality in (3.3). For the second one note that since
$0\in A$ and $A$ is connected, $A$ must contain a path $P$ from $0$ to some
point $y\in A$ with $\|y\|=r$. Such a path contains at least $r$ points and
thus $\\#A\geq\\#P\geq r$, showing the second inequality in (3.3). ∎

Note that the constant $\frac{1}{2}$ in (3.3) could be improved but we do not
need it in the sequel. Note also that for the first inequality the assumption
that $A$ is connected and contains $0$ is not needed.

Let $(A_{n})_{n\in{\mathbb{N}}}$ be an increasing sequence of finite subsets
of ${\mathbb{Z}}^{d}$. We are looking for a suitable exponent $\alpha$ (the
‘growth rate’ of the sequence) and a suitable constant $c>0$ such that

${\rm rad}(A_{n})\sim c\cdot(\\#A_{n})^{\alpha},\quad\text{ as }n\to\infty.$

(Here $a_{n}\sim b_{n}$ means that the quotient $a_{n}/b_{n}$ converges to 1
as $n\to\infty$.) Since such exponent $\alpha$ might not exist in general, we
define the lower and upper growth rate of the sequence $(A_{n})$ by

$\displaystyle\underline{\alpha}_{f}:=\underline{\alpha}_{f}((A_{n})):=\liminf_{n\to\infty}\frac{\log({\rm
rad}(A_{n}))}{\log(\\#A_{n})}\quad\text{ and
}\quad\overline{\alpha}_{f}:=\limsup_{n\to\infty}\frac{\log({\rm
rad}(A_{n}))}{\log(\\#A_{n})}.$

Alternatively, the lower and upper fractal dimension are defined by

$\displaystyle\underline{\delta}_{f}:=\liminf_{n\to\infty}\frac{\log(\\#A_{n})}{\log({\rm
rad}(A_{n}))}\quad\text{ and
}\quad\overline{\delta}_{f}:=\limsup_{n\to\infty}\frac{\log(\\#A_{n})}{\log({\rm
rad}(A_{n}))}.$

It is immediately clear from the definitions that fractal dimension and growth
rate are directly connected. In general one has
$\underline{\delta}_{f}=1/\overline{\alpha}_{f}$ and
$\overline{\delta}_{f}=1/\underline{\alpha}_{f}$. This means in particular
that an upper bound on the growth rate implies a lower bound on the fractal
dimension and vice versa.

$\\#A_{n}$ may be interpreted as the _volume_ of the cluster $A_{n}$. (We may
identify $\\#A_{n}$ with the union $\square A_{n}:=\bigcup_{y\in A_{n}}C_{y}$,
where $C_{y}:=y+[-\frac{1}{2},\frac{1}{2}]^{d}$ is the unit cube centered at
$y$. Then the volume of $\square A_{n}$ is exactly $\\#A_{n}$.) Moreover,
${\rm rad}(A_{n})$ may be interpreted as the diameter, cf. (3.2), which
justifies calling the exponents $\underline{\delta}_{f}$ and
$\overline{\delta}_{f}$ fractal dimensions.

The trivial bounds on the radius stated in Lemma 3.1 imply immediately some
general bounds on the fractal dimensions and growth rates.

######  Proposition 3.2.

Let $(A_{n})_{n\in{\mathbb{N}}}$ be an increasing sequence of finite,
connected subsets of ${\mathbb{Z}}^{d}$ with $0\in A_{1}$. Then

$1\leq\underline{\delta}_{f}\leq\overline{\delta}_{f}\leq d\qquad\text{ and
hence }\qquad 1/d\leq\underline{\alpha}_{f}\leq\overline{\alpha}_{f}\leq 1.$

###### Proof.

The lower bound 1 for $\underline{\delta}_{f}$ follows by applying the right
hand side inequality in (3.3) to $A_{n}$ and taking the $\liminf$. The upper
bound for $\overline{\delta}_{f}$ follows similarly by applying the left hand
side inequality in (3.3) to $A_{n}$ and taking the $\limsup$. ∎

In incremental aggregation models, the sequence $(F_{n})_{n\in{\mathbb{N}}}$
consists of random sets and therefore, for each $n\in{\mathbb{N}}$, ${\rm
rad}(F_{n})$ is a nonnegative random variable (while $\\#F_{n}=n$ is constant
almost surely). Hence the fractal dimensions and growth rates are random
variables, too. Observe that they satisfy almost surely the bounds stated in
Proposition 3.2.

Let now $(F_{n})_{n\in{\mathbb{N}}}$ be DLA in ${\mathbb{Z}}^{d}$, $d\geq 2$
as defined in Example 2.3. The following celebrated result due to Kesten
provides an almost sure upper bound on the radii of DLA clusters. For $d=3$, a
log-term appears which was improved slightly by Lawler [12] and later again by
Benjamini and Yadin [4].

######  Theorem 3.3 (cf. [9, 10, 4]).

For DLA $(F_{n})_{n}$ in ${\mathbb{Z}}^{d}$ there exists a constant $c>0$
(depending only on $d$) such that almost surely for $n$ sufficiently large

$\displaystyle{\rm rad}(F_{n})\leq\begin{cases}c\,n^{2/3},&\text{if }d=2,\\\
c\,n^{1/2}(\log n)^{1/2},&\text{if }d=3,\\\ c\,n^{2/(d+1)},&\text{if }d\geq
4.\end{cases}$

Theorem 3.3 implies the following lower bounds on the fractal dimension.

######  Corollary 3.4.

For DLA $(F_{n})_{n\in{\mathbb{N}}}$ in ${\mathbb{Z}}^{d}$, $d\geq 2$, one has
almost surely

$\displaystyle\underline{\delta}_{f}\geq\frac{d+1}{2}\quad\text{ and
}\quad\overline{\alpha}_{f}\leq\frac{2}{d+1}.$

###### Proof.

This follows immediately by inserting the estimate in Theorem 3.3 into the
definition of the lower fractal dimension (and the upper growth exponent). For
$d=2$, for instance, this yields almost surely

$\displaystyle\underline{\delta}_{f}=\liminf_{n\to\infty}\frac{\log
n}{\log({\rm rad}(F_{n}))}\geq\lim_{n\to\infty}\frac{\log
n}{\log(cn^{2/3})}=\frac{3}{2}.\qquad\qed$

Simulations of the model suggest that the above bounds are not sharp. In
${\mathbb{Z}}^{2}$ they suggest that the fractal dimension exists and equals
$\delta_{f}=\frac{5}{3}\approx 1.66$, which is strictly larger than the
rigorous bound stated above. For general $d\geq 2$, it is conjectured, cf.
e.g. [20], that for DLA in ${\mathbb{Z}}^{d}$ the dimension is given by

$\delta_{f}=\frac{d^{2}+1}{d+1}.$

##  4\. DLA and Kesten’s method

In his paper [9], Kesten used a certain strategy of proof for his bounds for
the DLA model in ${\mathbb{Z}}^{2}$, which is also described in Lawler’s book,
see [12, § 2.6], and generalized to arbitrary graphs with bounded degree in
[4]. It turns out that this method can be adapted to provide some bounds for
any incremental aggregation model. The next theorem below describes this
general method. Its proof will be discussed later in Section 6. Let
$\mathcal{P}^{d}_{\partial}$ be the family of outer boundaries of aggregation
clusters in ${\mathbb{Z}}^{d}$, that is, let

$\displaystyle\mathcal{P}^{d}_{\partial}:=\\{B\in\mathcal{P}^{d}_{f}:\exists
A\in\mathcal{P}^{d}_{f}\text{ such that }A\text{ is connected, }0\in A\text{
and }\partial A=B\\}.$

Recall that in any incremental aggregation model, at any time step $n$ the
next point $y_{n+1}$ to be attached is chosen from the outer boundary
$\partial F_{n}$ of the current cluster $F_{n}$. Therefore, it is in fact
sufficient to specify the distributions $\mu_{B}$ for all
$B\in\mathcal{P}^{d}_{\partial}$ in order to determine an incremental
aggregation model completely. As a consequence, it is sufficient to impose
conditions on the distribution family only for the distributions of outer
boundary sets as in the statement below. Other sets are not relevant for the
model.

######  Theorem 4.1 (Kesten’s method).

Let $\mathcal{M}=(\mu_{A})_{A\in\mathcal{P}^{d}_{f}}$ be some family of
distributions such that $\mu_{A}\in\mathcal{D}_{A}$ for each
$A\in\mathcal{P}^{d}_{f}$. Suppose there exist some positive constants $q$ and
$C$ such that for all $r>1$, any $B\in\mathcal{P}^{d}_{\partial}$ with radius
at least $r$ and any $z\in B$,

(4.1) $\displaystyle\mu_{B}(z)\leq C\,r^{-q}.$

Then there is a constant $c$, such that incremental aggregation
$\mathcal{F}=(F_{n})_{n\in{\mathbb{N}}}$ with distribution family
$\mathcal{M}$ satisfies almost surely

$\displaystyle{\rm rad}(F_{n})\leq c\,n^{1/(q+1)}$

for $n$ sufficiently large.

The method is rather crude. Roughly it says that if for all relevant
distributions in the family $\mathcal{M}$ the mass concentrated on single
vertices is not too large compared to the radius of the corresponding cluster
(implying that the probability mass must be spread out over a significant
number of vertices), then some bound on the radial growth follows. This is
plausible. The more spread out distributions are, the more options there are
for the next particle to be placed. As only few of the possible locations are
extremal in the sense that they lead to radial growth of the cluster, this
limits the speed of growth.

In [4], the assumption (4.1) is called a $\varphi$-_radius Beurling estimate_
in the context of the DLA model (for the function $\varphi(r)=cr^{-q}$). Our
proof of Theorem 4.1 in Section 6 below follows essentially the proof of
Lawler [12, § 2.6] but one might also want to compare it with [4, Lemma 2.4
and Theorem 2.6]. The important observation is that the relevant arguments in
these proofs do not only apply to DLA but to any incremental aggregation.

To illustrate Kesten’s method, we briefly describe how it is applied to obtain
the known bounds in ${\mathbb{Z}}^{2}$ for DLA and the Eden model. In the next
section, we will use it to study ballistic aggregation. For the DLA model in
${\mathbb{Z}}^{2}$, one can use the following well known estimate for harmonic
measures.

######  Proposition 4.2.

(cf. e.g. [12, Proposition 2.5.2]) For any $r>1$, any connected set
$A\subset\mathcal{P}^{d}_{f}$ with $0\in A$ and radius at least $r$, and any
$z\in A$, one has

$\displaystyle h_{A}(z)\leq\begin{cases}C\,r^{-1/2},&\text{if }d=2,\\\
C\,(\log r)^{1/2}r^{-1},&\text{if }d=3,\\\ C\,r^{-1},&\text{if }d\geq
4.\end{cases}$

Observe that outer boundaries need not be connected such that the above
estimates are not directly applicable. However, since any random walk started
outside a set $A$ will first hit $\partial A$ before hitting $A$, we have

$\displaystyle h_{\partial A}=h_{A\cup\partial A}\quad\text{ for any
}A\in\mathcal{P}^{d}_{f}.$

Hence the above estimates hold also for any boundary set
$B\in\mathcal{P}^{d}_{\partial}$. Applying Theorem 4.1 to DLA in
${\mathbb{Z}}^{2}$, for which, by Proposition 4.2, the hypothesis is satisfied
for $q=1/2$, we conclude the existence of a constant $c>0$ such that almost
surely ${\rm rad}(F_{n})\leq c\,n^{3/2}$ for $n$ sufficiently large. This is
the bound stated in Theorem 3.3 above.

######  Remark 4.3.

For DLA in ${\mathbb{Z}}^{3}$, the bound for the harmonic measure stated in
Proposition 4.2 implies that the hypothesis of Theorem 4.1 is satisfied for
any $q<1$. Thus, this theorem yields for any $p>\frac{1}{2}$ the existence of
a constant $c_{p}$ such that a.s. the bound ${\rm rad}(F_{n})\leq
c_{p}\,n^{p}$ holds for $n$ sufficiently large. This is enough to conclude (by
letting $p\to 1/2$) that a.s. $\underline{\delta}_{f}\geq 2$, as stated in
Corollary 3.4, but it is not enough to get the logarithmic correction for the
bound on the radius stated in Theorem 3.3 for the case $d=3$. For this a
slight refinement of Kesten’s method is necessary, see e.g. [4].

For $d\geq 4$, Theorem 4.1 yields the existence of some $c>0$ such that a.s.
the bound ${\rm rad}(F_{n})\leq c\,n^{1/2}$ holds for $n$ sufficiently large.
This is not as good as the bound stated in Theorem 3.3 and shows the rather
poor performance of the method in higher dimensions. It is known that the
exponent $q=1$ in Proposition 4.2 is optimal. There are sets $A$ (e.g.
(discrete) line segments) for which the harmonic measure has atoms of this
order, cf. e.g. [12, §2.4] for details. Hence Theorem 4.1 cannot provide a
better bound for the growth rate in this case.

For the Eden growth model in ${\mathbb{Z}}^{d}$ (as defined in Example 2.2
above), we have the following estimate for the defining family of
distributions $(\mu_{A})$:

######  Lemma 4.4.

For any $r>1$, any boundary set $B\in\mathcal{P}^{d}_{\partial}$ with ${\rm
rad}(B)\geq r$ and any $z\in B$,

$\displaystyle\mu_{B}(z)\leq\sqrt{d}(2(d-1))^{-1}r^{-1}.$

###### Proof.

Denote by $e_{1},\ldots,e_{d}$ the coordinate directions. For
$B\in\mathcal{P}^{d}_{\partial}$ there is a finite connected set
$A\in\mathcal{P}^{d}_{f}$ with $0\in A$ and ${\rm rad}(A)\geq r-1$, such that
$\partial A=B$. Because of its radius $A$ must contain a point $y$ with
$\|y\|\geq r-1$. Hence there is a coordinate direction $e_{i}$ such that the
$i$-th coordinate of $y$ satisfies $|y_{i}|\geq(r-1)/\sqrt{d}$. Without loss
of generality we can assume $i=1$ and $y_{1}>0$. Since $y_{1}$ is an integer,
we have $y_{1}\geq\lfloor(r-1)/\sqrt{d}\rfloor+1$ (where $\lfloor x\rfloor$
denotes the integer part of $x>0$) such that $y_{1}+1\geq(r-1)/\sqrt{d}+1\geq
r/\sqrt{d}$.

Since $A$ is connected, also its projection onto the $e_{1}$-axis must be
connected. Hence, for each $k=0,\ldots,y_{1}$ there is a vertex $z_{k}$ in $A$
whose first coordinate is $k$. If one moves from $z_{k}$ in direction $\pm
e_{i}$, $i=2,\ldots,d$ to the first vertex outside $A$, then this new vertex
will be in $\partial A=B$. It is clear that all the $2(d-1)(y_{1}+1)$ vertices
of $B$ reached in this way are distinct, which implies that

$\\#B\geq 2(d-1)(y_{1}+1)\geq\frac{2(d-1)}{\sqrt{d}}r.$

Hence $\mu_{B}(z)=(\\#A)^{-1}\leq\sqrt{d}(2(d-1))^{-1}r^{-1}$ as asserted. ∎

Applying now Kesten’s method to the Eden growth model $(F_{n})_{n}$ in
${\mathbb{Z}}^{d}$ using the estimate provided in Lemma 4.4 (for the exponent
$q=1$), we infer that there is a constant $c>0$, such that almost surely

$\displaystyle{\rm rad}(F_{n})\leq c\,n^{1/2}$

for $n$ sufficiently large. This implies $\underline{\delta}_{f}\geq 2$ for
the lower fractal growth dimension of the Eden model in ${\mathbb{Z}}^{d}$.
For $d=2$, by Proposition 3.2, we therefore recover

$\delta_{f}=2.$

It is also well known that $\delta_{f}=d$ for the Eden model in
${\mathbb{Z}}^{d}$, $d\geq 3$, but Kesten’s method as stated in Theorem 4.1 is
not capable of providing such a result, as this would require an estimate of
the form (4.1) with $q=d-1$, which is simply not true. Indeed, for any
$r\in{\mathbb{N}}$ there is a cluster $A$ such that for $B=\partial A$, ${\rm
rad}(B)=r$ and $\mu_{B}(z)\geq(2(d-1))^{-1}r^{-1}$. (Take e.g.
$A:=\\{(k,0,\ldots,0)\in{\mathbb{Z}}^{d}:k\in\\{0,1,\ldots,r-1\\}$. Then
$\\#B=2+2(d-1)r\leq 2(d-1)r$ and so $\mu_{B}(z)\geq(2(d-1))^{-1}r^{-1}$.) This
precludes an estimate of the form (4.1) to hold for any $q>1$.

The hypothesis in Kesten’s method is rather restrictive. Requiring some
deterministic estimate to be satisfied for all outer boundaries and at all
locations $z$ leads to an exponent $q$ that is often too small in order to
provide a good bound for the radial growth. Although the methods is able to
provide lower bounds on radial growth in any dimension $d$, it seems that the
method is strong only in ${\mathbb{Z}}^{2}$.

It seems plausible, that it should be enough to have a bound on $\mu_{\partial
A}(z)$ available for outer boundaries of ’typical’ aggregation clusters $A$
(or for ’most of them’). However, this will require further investigation and
is not covered by Theorem 4.1 above. Another approach (which leads in fact to
the growth bounds for DLA stated above) are estimates in terms of the volume
of the clusters rather than its radius, which will be a topic of further
investigation.

##  5\. Ballistic aggregation

We now introduce the ballistic model rigorously and discuss its growth
properties. Ballistic aggregation in ${\mathbb{Z}}^{d}$ will be defined as
incremental aggregation $(F_{n})_{n\in{\mathbb{N}}}$ with a suitable
distribution family $\mathcal{M}=(b_{A})_{A\in\mathcal{P}^{d}_{f}}$. In order
to determine the model all we have to do is to choose the family
$\mathcal{M}$, i.e., to fix a distribution $b_{A}$ on each finite set
$A\in\mathcal{P}^{d}_{f}$. Roughly, for each $z\in A$, $b_{A}(z)$ will be
determined by the probability that a ‘directed random line through $A$ hits
$z$ first’. In order to define this properly, we recall some ideas from
stochastic geometry, in particular the concept of an _isotropic random line_.
In what follows, we will view ${\mathbb{Z}}^{d}$ also as a subset of
${\mathbb{R}}^{d}$ embedded in the natural way.

Let $A(d,1)$ be the space of lines in ${\mathbb{R}}^{d}$ (i.e., the affine
Grassmannian of $1$-flats). We equip it with the usual hit-or-miss topology
and the associated Borel $\sigma$-algebra $\mathcal{A}(d,1)$, see e.g. [18,
Chapter 13] for details. For any compact set $K\subset{\mathbb{R}}^{d}$ let

$[K]:=\\{L\in A(d,1):L\cap K\neq\emptyset\\}.$

Then $\mathcal{A}(d,1)=\sigma(\\{[K]:K\in\mathcal{K}^{d}\\})$, where
$\mathcal{K}^{d}$ denotes the family of all _convex bodies_ , that is,
compact, convex sets in ${\mathbb{R}}^{d}$.

It is well known, cf. e.g. [18], that there is a unique Euclidean motion-
invariant Radon measure $\mu_{1}$ on $A(d,1)$ such that

$\mu_{1}([B_{d}])=\kappa_{d-1}.$

Here $B_{n}$ is the unit ball in ${\mathbb{R}}^{n}$ and
$\kappa_{n}:=\lambda_{n}(B_{n})$ denotes its volume.

Observe that, by the Crofton formula, cf. e.g. [18, Theorem 5.1.1], for any
convex body $K\in\mathcal{K}^{d}$,

(5.1) $\displaystyle\mu_{1}([K])$
$\displaystyle=\int_{A(d,1)}\mathbf{1}\\{K\cap L\neq\emptyset\\}\mu_{1}(dL)$
$\displaystyle=\int_{A(d,1)}V_{0}(K\cap L)\mu_{1}(dL)=\alpha_{d}\,V_{d-1}(K),$

where the constant is given by
$\alpha_{d}:=\frac{2(d-1)!\kappa_{d-1}}{d!\kappa_{d}}=\frac{2\kappa_{d-1}}{d\kappa_{d}}$
and $V_{j}(K)$ is the intrinsic volume of $K$ of degree $j$. If $K$ has
nonempty interior, then $V_{d-1}(K)$ is half the surface area of $K$. This
means, the measure of lines hitting a given convex body $K$ is up to some
universal constant given by the surface area of $K$. Following [18, Definition
8.4.2], for any convex body $K\in\mathcal{K}^{d}$ with $V_{d-1}(K)>0$, an
isotropic random line through $K$ is defined to be a random variable
$L:\Omega\to A(d,1)$ with distribution given by

${\mathbb{P}}(L\in\mathcal{A}):={\mathbb{P}}^{K}(\mathcal{A}):=\frac{\mu_{1}(\mathcal{A}\cap[K])}{\mu_{1}([K])},\qquad\mathcal{A}\in\mathcal{A}(d,1).$

This definition extends without any problem to arbitrary compact sets
$K\subset{\mathbb{R}}^{d}$, provided that $\mu_{1}([K])>0$. However, the
convenient interpretation (5.1) of $\mu_{1}$ in terms of $V_{d-1}$ (or the
surface area) is no longer valid if $K$ is not convex. Observe that for any
compact $K\subset{\mathbb{R}}^{d}$, one has
$\mu_{1}([K])\leq\mu_{1}\left(\left[\operatorname{conv}(K)\right]\right)<\infty$,
where $\operatorname{conv}(K)$ denotes the convex hull of $K$. Thus, for any
compact set $K\subset{\mathbb{R}}^{d}$ with $\mu_{1}([K])>0$, the distribution
${\mathbb{P}}^{K}$ is well defined and so is an _isotropic random line through
$K$_. In ${\mathbb{R}}^{2}$ one has the following additional property, which
turns out to simplify the analysis significantly: for any connected, compact
set $C\subset{\mathbb{R}}^{2}$,

$[C]=[\operatorname{conv}(C)].$

Therefore, ${\mathbb{P}}^{C}={\mathbb{P}}^{\operatorname{conv}(C)}$ (provided
$V_{1}(\operatorname{conv}(C))>0$, i.e., $C$ not a singleton). Thus in
dimension 2 one can work with convex hulls instead of the original sets.
Unfortunately, this is not possible in any higher dimension.

For any finite set $A\in\mathcal{P}^{d}_{f}$ denote by $\square A$ the union
of grid boxes centered in $A$, that is, let

$\square A:=\bigcup_{z\in A}C_{z}\qquad\text{ where
}C_{z}=\left[-\frac{1}{2},\frac{1}{2}\right]^{d}+z.$

Then, for any $d\geq 2$ and $A\in\mathcal{P}^{d}_{f}\setminus\\{\emptyset\\}$,
the distribution ${\mathbb{P}}^{\square A}$ of an isotropic random line
through $\square A$ is well defined. The idea for the definition of the
ballistic measure $b_{A}$ is now as follows: We identify $A$ with $\square A$
and generate an isotropic random line $L$ through $\square A$. We choose
randomly a direction on $L$. Then for any $z\in A$, we let $\mu_{A}(z)$ be the
probability that, when traveling along $L$ in the chosen direction, the square
$C_{z}$ is the first square in $\square A$ visited by $L$. More formally, we
fix for each $L\in A(d,1)$ a direction $v_{L}\in\mathbb{S}^{d-1}$. (We choose
$v_{L}$ such that the mapping $L\mapsto v_{L}$ is measurable.) For
$A\in\mathcal{P}^{d}_{f}$ and $L\in A(d,1)$, let

$L^{A}:=\\{z\in A:C_{z}\cap L\neq\emptyset\\},$

that is, $L^{A}$ is the set of those points in $A$ whose associated boxes are
intersected by $L$. Traversing $L$ in direction $v_{L}$ induces an order in
$L^{A}$. (For certain lines the order in which the boxes are visited is not
well defined, namely if $L$ hits a box first at an intersection point of two
or several boxes not visited before. In such a case the order can be made
unique by fixing some order of the boxes $C_{z}$ in $z\in{\mathbb{Z}}^{d}$,
such as the one induced by the lexicographic order in ${\mathbb{Z}}^{d}$.
However, for $\mu_{1}$-almost all lines $L$ the order in $L^{A}$ is well
defined without this.) Denote by $\min(L^{A})$ and $\max(L^{A})$ the first and
last point in $L^{A}$ ‘visited’ by $L$.

######  Definition 5.1.

(Ballistic measure) Let $A\in\mathcal{P}^{d}_{f}\setminus\\{\emptyset\\}$. For
$z\in{\mathbb{Z}}^{d}$ and $L\in A(d,1)$ define

$\displaystyle b_{A}(z,L)$ $\displaystyle:=\begin{cases}1,&\text{if
}L^{A}=\\{z\\},\\\ \frac{1}{2},&\text{if }\\#(L^{A})>1\text{ and
}z\in\\{\min(L^{A}),\max(L^{A})\\},\\\ 0,&\text{otherwise}.\end{cases}$

Then a probability measure $b_{A}$ on $A$ is well defined by setting

$\displaystyle b_{A}(z)$
$\displaystyle:=\int_{A(d,1)}b_{A}(z,L){\mathbb{P}}^{\square A}(dL),\qquad
z\in{\mathbb{Z}}^{d}.$

We call $b_{A}$ the _ballistic measure_ on $A$.

Observe that $b_{A}(z)=0$ for $z\notin A$ and $\sum_{z\in A}b_{A}(z)=1$.
Hence, $b_{A}$ is indeed a probability measure which is concentrated on $A$,
that is, $b_{A}\in\mathcal{D}(A)$. Note also that, for any $z\in A$,

(5.2) $\displaystyle b_{A}(z)$
$\displaystyle=\int_{A(d,1)}b_{A}(z,L){\mathbb{P}}^{\square
A}(dL)\leq\int_{A(d,1)}\mathbf{1}\\{L\in[C_{z}]\\}{\mathbb{P}}^{\square
A}(dL)={\mathbb{P}}^{\square A}([C_{z}]).$

This gives a first upper bound of the probability mass of $b_{A}$ at single
vertices. Ballistic aggregation (BA) on ${\mathbb{Z}}^{d}$ is now defined to
be incremental aggregation with distribution family
$(b_{A})_{A\in\mathcal{P}^{d}_{f}}$, where $b_{A}$ is the ballistic measure on
$A$.

For the ballistic model in ${\mathbb{Z}}^{d}$, $d\geq 2$, we have the
following main result concerning the radial growth of clusters, which
parallels the one obtained by Kesten for DLA.

######  Theorem 5.2.

Let $d\in{\mathbb{N}}$, $d\geq 2$ and $(F_{n})_{n\in{\mathbb{N}}}$ be
ballistic aggregation in ${\mathbb{Z}}^{d}$. There exists a constant $c>0$
such that almost surely for $n$ sufficiently large

$\displaystyle{\rm rad}(F_{n})\leq c\,n^{1/2}.$

Combining this bound with the trivial lower bound provided by Propositon 3.2,
we conclude that in ${\mathbb{Z}}^{2}$ the fractal dimension $\delta_{f}$ of
BA clusters exists and equals $2$. This confirms a long standing conjecture in
the physics literature, cf. [5, 14, 2, 20].

######  Corollary 5.3.

For the ballistic model in ${\mathbb{Z}}^{2}$, one has $\delta_{f}=2$ almost
surely.

###### Proof.

On the one hand, by Propositon 3.2, $\overline{\delta}_{f}\leq 2$ almost
surely. On the other hand, Theorem 5.2 implies

$\displaystyle\underline{\delta}_{f}=\liminf_{n\to\infty}\frac{\log
n}{\log({\rm rad}(F_{n}))}\geq\lim_{n\to\infty}\frac{\log
n}{\log(cn^{1/2})}=2.\qquad\qed$

######  Remark 5.4.

We can even get a slightly stronger conclusion from the above theorem
regarding the asymptotic size of BA clusters. The ballistic model in
${\mathbb{Z}}^{2}$ satisfies almost surely

$\liminf_{n\to\infty}\frac{\\#F_{n}}{({\rm
rad}(F_{n}))^{2}}\geq\liminf_{n\to\infty}\frac{n}{c^{2}n}=c^{-2}>0.$

This may be interpreted as saying that asymptotically BA clusters cover a
positive portion of the plane. (More precisely, the quotient of the area
covered by the cluster $\square F_{n}$ (given by $\\#F_{n}$) and the area of
the smallest ball containing $\square F_{n}$ ($\approx\pi\cdot{\rm
rad}(F_{n})^{2}$) is asymptotically bounded from below, as $n\to\infty$.)

For $d\geq 3$, the conclusion regarding the fractal dimension of the BA model
is not quite as strong as for $d=2$.

######  Corollary 5.5.

For the ballistic model in ${\mathbb{Z}}^{d}$, $d\geq 3$, one has
$\underline{\delta}_{f}\geq 2$ almost surely.

As in the case $d=2$, this can be directly deduced from Theorem 5.2.
Unfortunately, this lower bound for the fractal dimension is far from the
conjectured value $\delta_{f}=d$ in this case.

The proof of Theorem 5.2 will be based on Kesten’s method (Theorem 4.1 above).
In order to apply it, a suitable estimate for the local growth of the
ballistic measures $b_{A}$ is required, which we state now.

######  Proposition 5.6.

For any $d\in{\mathbb{N}}$, $d\geq 2$, there exists a constant $C_{d}>0$ such
that, for any $r\geq 1$, any connected set $A\in\mathcal{P}^{d}_{f}$ with
$0\in A$ and ${\rm rad}(A)\geq r$, and any $z\in A$,

$\displaystyle b_{A}(z)\leq C_{d}\,r^{-1}.$

For $d=2$, $C_{2}=2$ is a suitable constant.

Before we provide a proof of Proposition 5.6, we first clarify that Theorem
5.2 easily follows from this statement.

###### Proof of Theorem 5.2.

By Proposition 5.6, the hypothesis in Kesten’s method (Theorem 4.1) is
satisfied for the exponent $q=1$ for the ballistic model
$(F_{n})_{n\in{\mathbb{N}}}$ on ${\mathbb{Z}}^{d}$ for any $d\geq 2$. Hence
from this theorem, the stated bounds on the radial growth of this model (with
the exponent $1/(1+q)=1/2$) follow at once. ∎

Observe that any improvement on the exponent $q=1$ in Proposition 5.6 (i.e.,
any larger $q$) would allow to deduce from Kesten’s method a better bound for
the radial growth. Unfortunately, the exponent $q=1$ in Proposition 5.6 turns
out to be optimal in any dimension $d\geq 2$, as the following remark
clarifies.

######  Remark 5.7.

The exponent $q=1$ in Proposition 5.6 is optimal (largest possible) in any
space dimension $d\geq 2$. Consider for any $d\in{\mathbb{Z}}$, $d\geq 2$ and
any integer $r\geq 1$ the set

$A=A_{r}:=\left\\{(s,0,\ldots,0)\in{\mathbb{Z}}^{d}:s\in\\{0,...,r\\}\right\\}.$

Observe that $\square A$ is a union of $r+1$ unit size boxes placed side by
side in a row. Hence $\square A$ is convex and ${\rm rad}(A)=r$. Moreover,
noting that for any directed line $L$ hitting the cube $C_{0}$ at all, $C_{0}$
is always the first or the last cube of $\square A$ visited by $L$, we obtain
for the ballistic measure at $z=0$ (and similarly at $z=(r,0,\ldots,0)$)

$\displaystyle b_{A}(z)$
$\displaystyle=\int_{A(d,1)}b_{A}(z,L){\mathbb{P}}^{\square
A}(dL)\geq\frac{1}{2}\int_{A(d,1)}\mathbf{1}\\{L\in[C_{z}]\\}{\mathbb{P}}^{\square
A}(dL)=\frac{1}{2}{\mathbb{P}}^{\square A}([C_{z}])$
$\displaystyle=\frac{1}{2}\frac{\mu_{1}([C_{z}])}{\mu_{1}([\square
A])}=\frac{1}{2}\frac{V_{d-1}(C_{z})}{V_{d-1}(A_{r})}=\frac{1}{2}\cdot\frac{d}{1+(d-1)(r+1)}=\frac{1}{2}\cdot\frac{d}{(d-1)r+d}.$

For any $r\geq d$, the denominator in the last expression is bounded from
above by $d\,r$ and therefore we obtain $b_{A}(z)\geq 1/2\cdot r^{-1}$. Hence
a bound as in Proposition 5.6 valid for the ballistic measures $b_{A}$ of all
finite sets $A\in{\mathbb{P}}^{d}_{f}$ cannot be true for any $q>1$.

###### Proof of Proposition 5.6.

We first discuss the case $d=2$, for which our argument is much simpler than
for the general case. Fix $r\geq 1$. Let $A\in\mathcal{P}^{2}_{f}$ be a
connected set with $0\in A$ and ${\rm rad}(A)\geq r$. Note that the
connectedness implies $[\square A]=[\operatorname{conv}(\square A)]$. The set
$\square A$ contains the square $C_{0}$ and another unit square $C_{y}$ with
$y\in{\mathbb{Z}}^{2}$ and $\|y\|\geq r$. Hence $\operatorname{conv}(\square
A)$ contains $\operatorname{conv}(C_{0}\cup C_{y})$ and thus a rectangle
$R_{r}$ with sidelengths $r$ and $1$. (Choose one side of $R_{r}$ parallel to
the vector $y$.) Using (5.2) and the properties of the measure $\mu_{1}$, we
conclude that, for any $z\in A$,

$\displaystyle b_{A}(z)$ $\displaystyle\leq{\mathbb{P}}^{\square
A}([C_{z}])=\frac{\mu_{1}([C_{z}])}{\mu_{1}([\operatorname{conv}(\square
A)])}\leq\frac{\mu_{1}([C_{0}])}{\mu_{1}([R_{r}])}=\frac{V_{1}(C_{0})}{V_{1}(R_{r})}=\frac{2}{1+r}\leq
2r^{-1}.$

This shows the claimed estimate for $d=2$ and also that $C_{2}=2$ is a
suitable constant in this case.

Now let us turn to the case $d\geq 3$. We start similary as for $d=2$. Let
$r\geq 1$ and let $A\in\mathcal{P}^{d}_{f}$ be a connected set with $0\in A$
and ${\rm rad}(A)\geq r$. As before, the set $\square A$ contains the square
$C_{0}$ and another unit square $C_{y}$ with $y\in{\mathbb{Z}}^{d}$ and
$\|y\|\geq r$, but now we can not simply replace $\square A$ by its convex
hull, since the latter set may be hit by significantly many more lines than
$\square A$.

Since $A$ is connected, it must contain a path from $0$ to $y$, that is, there
are $m\in{\mathbb{N}}$ and points $p_{0}:=0,p_{1},\ldots,p_{m-1},p_{m}:=y\in
A$ such that $||p_{i}-p_{i-1}||=1$ for $i=1,\ldots,m$. Let
$\Gamma:=\\{p_{0},\ldots,p_{m}\\}$ and let $G$ denote (the graph of) the
shortest curve connecting these points in the given order. Notice that $G$
consists of axis-parallel segments of length 1. For $F\subset{\mathbb{R}}^{d}$
and $r>0$ let

$F_{\oplus r}:=\left\\{x\in{\mathbb{R}}^{d}:\inf_{y\in F}||x-y||\leq
r\right\\}$

denote the $r$-parallel set of $F$. Observe that $G_{\oplus
1/2}\subset\square\Gamma$. (Indeed, any point in $G_{\oplus 1/2}$ is contained
in some ball $B(x,\frac{1}{2})$ with $x\in G$. If $x\in\Gamma$, then
$B(x,\frac{1}{2})\subset C_{x}$ and if $x$ is on the segment
$S(p_{k},p_{k+1})$ connecting $p_{k}$ and $p_{k+1}$, then obviously
$B(x,\frac{1}{2})\subset C_{p_{k}}\cup C_{p_{k+1}}$.) This yields

$\mu_{1}([G_{\oplus 1/2}])\leq\mu_{1}([\square\Gamma])\leq\mu_{1}([\square
A]).$

We claim now that there is a constant $\widetilde{C}_{d}$ (independent of $G$
and $r$) such that

(5.3) $\displaystyle\mu_{1}([G_{\oplus 1/2}])\geq\widetilde{C}_{d}\,r.$

Using (5.2), the properties of the measure $\mu_{1}$ and (5.1), we conclude
from (5.3) that, for any $z\in A$,

$\displaystyle b_{A}(z)$ $\displaystyle\leq{\mathbb{P}}^{\square
A}([C_{z}])=\frac{\mu_{1}([C_{z}])}{\mu_{1}([\square
A])}\leq\frac{\mu_{1}([C_{0}])}{\mu_{1}([G_{\oplus
1/2}])}\leq\frac{\alpha_{d}V_{d-1}(C_{0})}{\widetilde{C}_{d}\,r}=\frac{\alpha_{d}\,d}{\widetilde{C}_{d}}r^{-1}.$

This shows the estimate stated in Proposition 5.6 (for the constant
$C_{d}:=\alpha_{d}d/\widetilde{C}_{d}$).

It remains to provide a proof of (5.3). The rough idea here is to compare the
measure of lines through the tube $G_{\oplus 1/2}$ with the measure of lines
through the tube $S_{\oplus 1/2}$, where $S:=S(0,y)$ is the segment connecting
$0$ and $y$, and to observe that the latter is of order $r$. Observe that any
hyperplane hitting $S$ does also hit the curve $G$, since both curves have the
same endpoints. (Indeed, if the hyperplane contains an endpoint of $S$ then it
obviously intersects also $G$. Otherwise the hyperplane contains an inner
point of $S$ and separates the common endpoints of $S$ and $G$. But then the
curve $G$ must also intersect the hyperplane when passing from one side to the
other.) This will be useful for decomposing $\mu_{1}([G_{\oplus 1/2}])$.

Let $A(d,d-1)$ denote the set of all $(d-1)$-flats and $\mu_{d-1}$ the unique
Euclidean motion invariant measure on $A(d,d-1)$ such that
$\mu_{d-1}(\left[B^{d}\right])=2$, see [18, Ch. 13.2] for details. For $H\in
A(d,d-1)$ denote by $A(H,1)$ the set of lines in $H$ and let $\mu_{1}^{H}$ be
the invariant line measure on $A(H,1)$ (which is the image measure of
$\mu_{1}$ on ${\mathbb{R}}^{d-1}$ under some isometry from
${\mathbb{R}}^{d-1}$ to $H$. Recall that for $d\geq 3$ the measure of any set
$\mathcal{A}$ of lines may be determined by computing its line measure in
hyperplanes and then integrating over all hyperplanes. More precisely, for any
$\mathcal{A}\in\mathcal{A}(d,1)$,

$\displaystyle\mu_{1}(\mathcal{A})=\int_{A(d,d-1)}\mu_{1}^{H}(\mathcal{A})\mu_{d-1}(dH),$

see e.g. [18, Thm. 7.1.2 and the subsequent Remark].

Let $s:=y/||y||$ be the direction of the segment $S$. For any $H\in A(d,d-1)$,
denote by $v_{H}\in{\mathbb{S}}^{d-1}$ some unit normal of $H$ and by $p_{H}$
the corresponding (signed) distance to $0$ (such that
$H=\\{x\in{\mathbb{R}}^{d}:\langle x,v_{H}\rangle=p_{H}\\}$). Note that
$v_{H}$ is uniquely determined for a.a. $H$ if we require additionally
$\langle s,v_{H}\rangle\geq 0$. For a lower bound, we do not need to compute
the line measure in all hyperplanes. We restrict our attention to the
following set. Fix some $\delta>0$ and let

$\displaystyle\mathcal{H}:=\left\\{H\in A(d,d-1):\langle
v_{H},s\rangle\geq\delta\text{ and }H\cap S\neq\emptyset\right\\}.$

Observe that, for each $H\in\mathcal{H}$, we have $G\cap H\neq\emptyset$, i.e.
there is some point $x\in G\cap H$, implying that $G_{\oplus 1/2}$ contains
the closed ball $B(x,\frac{1}{2})$ with radius $\frac{1}{2}$ and center $x$.
Hence, by (5.1),

$\displaystyle\mu_{1}^{H}\left(\left[G_{\oplus
1/2}\right]\right)\geq\mu_{1}^{H}\left(\left[B(x,1/2)\right]\right)=\alpha_{d-1}V_{d-2}(B^{d-1}(1/2))=:\widetilde{c}_{d},$

where $B^{k}(t)$ denotes a ball in ${\mathbb{R}}^{k}$ with radius $t$
(centered at $0$). The most important thing to note here is that
$\widetilde{c}_{d}$ is some positive constant independent of $H$ and $r$.
Therefore, we infer

(5.4) $\displaystyle\mu_{1}\left(\left[G_{\oplus 1/2}\right]\right)$
$\displaystyle=\int_{A(d,d-1)}\mu_{1}^{H}\left(\left[G_{\oplus
1/2}\right]\right)\mu_{d-1}(dH)$
$\displaystyle\geq\int_{\mathcal{H}}\mu_{1}^{H}\left(\left[G_{\oplus
1/2}\right]\right)\mu_{d-1}(dH)\geq\widetilde{c}_{d}\,\mu_{d-1}(\mathcal{H}).$

Employing [18, Theorem 13.2.12], we conclude that

$\displaystyle\mu_{d-1}(\mathcal{H})$
$\displaystyle=\int_{G(d,d-1)}\int_{F^{\perp}}\mathbf{1}_{\mathcal{H}}(F+z)\lambda_{1}(dz)\nu_{d-1}(dF)$
$\displaystyle=\int_{G(d,d-1)}\mathbf{1}\\{\langle
s,v_{F}\rangle\geq\delta\\}\int_{F^{\perp}}\mathbf{1}\\{(F+z)\cap
S\neq\emptyset\\}\lambda_{1}(dz)\nu_{d-1}(dF),$

where $G(d,d-1)$ denotes the Grassmannian of hyperplanes in ${\mathbb{R}}^{d}$
and $\nu_{d-1}$ the invariant measure on $G(d,d-1)$. Moreover, as before
$v_{F}$ denotes the unit normal of $F$ such that $\langle s,v_{F}\rangle\geq
0$ and $\lambda_{1}$ is the $1$-dim. Lebesgue measure on $F^{\perp}$. Now
observe that the inner integral in the last term is bounded from below by
$r\delta$. Indeed, we have $(F+z)\cap S\neq\emptyset$ if and only if $\langle
y,v_{F}\rangle\geq\langle z,v_{F}\rangle\geq 0$. Moreover, if the first
indicator is 1, then $\langle y,v_{F}\rangle=||y||\langle s,v_{F}\rangle\geq
r\delta$. Hence $\lambda_{1}(\\{z\in F^{\perp}:(F+z)\cap
S\neq\emptyset\\})\geq\lambda_{1}(\\{z\in F^{\perp}:r\delta\geq\langle
z,v_{F}\rangle\geq 0\\})=r\delta$ as claimed.

It follows that

(5.5) $\displaystyle\mu_{d-1}(\mathcal{H})$ $\displaystyle\geq
r\delta\cdot\nu_{d-1}(\\{F\in G(d,d-1):\langle
v_{F},s\rangle\geq\delta\\})=:\hat{c}_{d}\,r,$

where the constant $\hat{c}_{d}$ is positive and independent of $r$. Now the
claim (5.3) follows (for the constant
$\widetilde{C}_{d}:=\widetilde{c}_{d}\,\hat{c}_{d}$) by combining (5.4) and
(5.5). ∎

##  6\. Proof of Kesten’s method

The first step towards a proof of Theorem 4.1 is an equivalent reformulation
of the conclusion in a more convenient form. Let $(F_{n})_{n\in{\mathbb{N}}}$
be some incremental aggregation. Recall the definition of the radius ${\rm
rad}(F_{n})$ from (3.1). We define the two random functions

$\displaystyle R:{\mathbb{N}}\to[0,\infty),\quad n\mapsto{\rm rad}(F_{n})$

and

$\displaystyle T:[0,\infty)\to{\mathbb{N}},\quad
r\mapsto\min\\{j\in{\mathbb{N}}\ |\ R(j)\geq r\\}.$

Clearly, $T(r)$ is the first time step at which the growing cluster has radius
at least $r$. It is easy to see that almost surely the functions $R$ and $T$
are non-decreasing. Moreover, one has almost surely the relations $T(R(n))\leq
n$ for each $n\in{\mathbb{N}}$, and $R(T(r))\geq r$ for each $r\in[0,\infty)$.
Note also that almost surely

$\displaystyle R(n)\to\infty\text{ as }n\to\infty\quad\text{ and }\quad
T(r)\to\infty\text{ as }r\to\infty.$

The conclusion in Theorem 4.1 is an almost sure upper bound on the random
function $R$. Our aim is to reformulate this upper bound on $R$ equivalently
as a lower bound on the waiting time $T$. The following statement provides
this link. Recall that a function $h:[0,\infty)\to[0,\infty)$ is called
multiplicative if and only if $h(xy)=h(x)h(y)$ for all $x,y\geq 0$. Note that
multiplicativity implies $h(0)=0$ and $h(1)=1$. (The functions $x\mapsto
x^{p}$, $p>0$ are generic examples for such $h$.)

######  Lemma 6.1.

Let $a>0$ and $h:[0,\infty)\to[0,\infty)$ be a bijective, multiplicative and
increasing function. For $c>0$ define the events

$\displaystyle A_{c}:=\\{\omega\in\Omega\ |\ \exists
N\in{\mathbb{N}}:R(\omega)(n)\leq c\,h(n)\text{ for all }n\geq N\\}$

and

$\displaystyle D_{c}:=\\{\omega\in\Omega\ |\ \exists
r_{0}\in{\mathbb{N}}:T(\omega)(ar)\geq c\,h^{-1}(r)\text{ for all }r\geq
r_{0}\\}.$

Then the following assertions are equivalent:

  1. (i)

There exists a constant $c>0$ such that ${\mathbb{P}}(A_{c})=1$.

  2. (ii)

There exists a constant $\bar{c}>0$ such that ${\mathbb{P}}(D_{\bar{c}})=1$.

###### Proof.

Fix some $c>0$ and let $\omega\in A_{c}$. Choose $N\in{\mathbb{N}}$ such that
$R(n)\leq c\,h(n)$ holds for all $n\geq N$. (Here and in the sequel $N$, $R$
and $T$ depend on $\omega$, which we suppress in the notation.) Since $h$ is
bijective and multiplicative, the last inequalities are equivalent to
$\tilde{c}\,h^{-1}(R(n))\leq n$ being satisfied for all $n\geq N$, where
$\tilde{c}:=h^{-1}(1/c)$. Since $T(s)\to\infty$ as $s\to\infty$, we can find
$r_{0}\in{\mathbb{N}}$ large enough such that $T(ar_{0})>N$. Obviously this
implies $T(ar)\geq T(ar_{0})>N$ for all $r\geq r_{0}$, since $T$ is
increasing. Hence we infer that $\tilde{c}h^{-1}(R(T(ar)))\leq T(ar)$ holds
for each $r\geq r_{0}$. Observe now that $h^{-1}$ is increasing and
multiplicative since $h$ is. Taking into account that $R(T(ar))\geq ar$, we
conclude that for each $r\geq r_{0}$

$T(ar)\geq\tilde{c}h^{-1}(ar)=\tilde{c}h^{-1}(a)\cdot h^{-1}(r)=:\bar{c}\cdot
h^{-1}(r).$

Hence $\omega\in D_{\bar{c}}$. It is now important to note that
$\bar{c}=h^{-1}(a/c)$ does not depend on $\omega$ (but only on $h$, $a$ and
$c$). Therefore we have proved that $A_{c}\subseteq D_{\bar{c}}$.

With a completely analogous argument one can show that $D_{\bar{c}}\subseteq
A_{c}$. Hence $A_{c}=D_{\bar{c}}$ for any $c>0$ (and $\bar{c}=h^{-1}(a/c)$).
In particular, if ${\mathbb{P}}(A_{c})=1$ for some $c>0$, then
${\mathbb{P}}(D_{\bar{c}})=1$. Similarly, if ${\mathbb{P}}(D_{\hat{c}})=1$ for
some $\hat{c}>0$, then $c:=a/h(\hat{c})>0$, $\bar{c}=h^{-1}(a/c)=\hat{c}$ and
therefore ${\mathbb{P}}(A_{c}=1)=1$. This completes the proof. ∎

Assume now that the hypothesis of Theorem 4.1 is satisfied for some $q>0$.
Consider for any $c>0$ the events

$\displaystyle A_{c}:=\\{\omega\in\Omega\ |\ \exists
N\in{\mathbb{N}}:R(\omega)(n)\leq c\,n^{\frac{1}{1+q}}\text{ for all }n\geq
N\\}$

and

$\displaystyle D_{c}:=\\{\omega\in\Omega\ |\ \exists
r_{0}\in{\mathbb{N}}:T(\omega)(2r)\geq cr^{1+q}\text{ for all }r\geq
r_{0}\\}.$

It is clear that the conclusion of Theorem 4.1 may be formulated as follows in
terms of the events $A_{c}$: _There exists a constant $c>0$ such that
${\mathbb{P}}(A_{c})=1$._

Note that $A_{c}$ and $D_{c}$ are the same as the corresponding events defined
in Lemma 6.1 for the choices $a=2$ and

$\displaystyle h:[0,\infty)\to[0,\infty),\quad x\mapsto x^{\frac{1}{1+q}}.$

Clearly, $h$ is bijective, multiplicative and increasing as required. Hence,
by Lemma 6.1, the conclusion of Theorem 4.1 holds if and only if there exists
a constant $\beta>0$ such that

(6.1) $\displaystyle{\mathbb{P}}(D_{\beta})=1.$

Therefore, in order to prove Theorem 4.1 it clearly suffices to prove that its
hypothesis implies the existence of some constant $\beta>0$ such that (6.1)
holds.

In order to achieve this we introduce some more notation. For
$n\in{\mathbb{N}}$ we write $F_{n}=\\{y_{1},\dots,y_{n}\\}$, where $y_{j}$
denotes the (random) point added to the cluster at time $j\in{\mathbb{N}}$.
Fix some $\beta>0$, which will be determined later on. For $r\in{\mathbb{N}}$
let $\widetilde{m}_{r}:=\beta r^{1+q}$ and define

$\displaystyle V_{r}:=\\{\omega\in\Omega\ |\
T(\omega)(2r)<\widetilde{m}_{r}\\}.$

Let $S_{r}:=\\{x\in{\mathbb{Z}}^{d}\ |\ r\leq|x|<r+1\\}$ be the _discrete
sphere_ in ${\mathbb{Z}}^{d}$ of radius $r$ centered at the origin. (It is
easy to see that any connected set $A\in{\mathbb{Z}}^{d}$ with $0\in A$ and
${\rm rad}(A)\geq r$ will contain at least one point of $S_{r}$, since there
will be a path in $A$ connecting $0$ to some point at distance at least $r$
which can not avoid intersecting the set $S_{r}$.) Further we define the set
of all possible (self-avoiding) paths in ${\mathbb{Z}}^{d}$ of length $r$
(i.e., passing $r$ edges) with starting point in $S_{r}$ by

$\displaystyle
Z_{r}:=\big{\\{}\mathbf{z}:=(z_{0},\dots,z_{r})\in({\mathbb{Z}}^{d})^{r}\ |\ $
$\displaystyle z_{1}\in S_{r},\\{z_{i},z_{i+1}\\}\in E\text{ for
}i=0,\ldots,r-1$ (6.2) $\displaystyle\text{ and }z_{i}\neq z_{j}\text{ for
}i\neq j\big{\\}}.$

For any $\mathbf{z}\in Z_{r}$ we define the event

$\displaystyle W_{r}(\mathbf{z}):=\left\\{\omega\in\Omega\ |\ \exists
j_{0}<\dots<j_{r}\leq\widetilde{m}_{r}\ \text{ such that
}y_{j_{i}}(\omega)=z_{i}\text{ for }i=0,\ldots,r\right\\}$

and the union of these events by

$\displaystyle W_{r}:=\bigcup_{\mathbf{z}\in Z_{r}}W_{r}(\mathbf{z}).$

Note that this is a finite union, as for any $r\in{\mathbb{N}}$ there are only
finitely many paths in $Z_{r}$. Note also that $W_{r}$ as well as $V_{r}$
depend (via $\widetilde{m}_{r}$) on the choice of $\beta$, which is suppressed
in the notation but which will become important later. We claim that for each
$r\in{\mathbb{N}}$

(6.3) $\displaystyle V_{r}\subseteq W_{r}.$

Indeed, if $\omega\in V_{r}$, then $T(\omega)(2r)<\widetilde{m}_{r}$. For
$m_{r}:=\max\\{j\in{\mathbb{N}}\ |\ j\leq\widetilde{m}_{r}\\}$ this implies
$T(\omega)(2r)\leq m_{r}$, and hence ${\rm rad}(F_{m_{r}}(\omega))\geq 2r$.
Thus $F_{m_{r}}(\omega)$ contains a point $x$ with $\|x\|\geq 2r$. Since
$F_{m_{r}}(\omega)$ is connected and contains the origin, there exists a path
$\mathbf{p}=(y_{i_{1}},\ldots,y_{i_{\ell}})$ in $F_{m_{r}}(\omega)$ connecting
$0$ and $x$ (i.e., $y_{i_{0}}=0$ and $y_{i_{\ell}}=x$) with the additional
property that $i_{0}<i_{1}\ldots<i_{\ell}$, that is, the points of
$\mathbf{p}$ have been added to the cluster in the right order. (Not every
path between $0$ and $x$ might satisfy this, but such a path must exist, since
otherwise the cluster would be disconnected at some time.) $\mathbf{p}$
contains a point $z_{0}$ of $S_{r}$ and thus a subpath $\mathbf{p}^{\prime}$
connecting $z_{0}$ to $x$. Since $\|z_{1}-x\|>r-1$, $\mathbf{p}^{\prime}$ has
length at least $r$. Hence, by taking the first $r$ steps of
$\mathbf{p}^{\prime}$, we find some path $\mathbf{z}$ of length exactly $r$,
that is, some $\mathbf{z}\in Z_{r}$ in $F_{m_{r}}(\omega)$. This means
$\omega\in W_{n}(\mathbf{z})\subset W_{n}$ which proves the set inclusion
(6.3).

The following estimate will allow to complete the proof of (6.1).

######  Lemma 6.2.

There is some $\beta>0$ and constants $c_{1}>0$, $q\in(0,1)$ and
$r_{0}\in{\mathbb{N}}$ (which depend on $\beta$) such that for all
$r\in{\mathbb{N}}$ with $r\geq r_{0}$

$\displaystyle{\mathbb{P}}(W_{r})\leq c_{1}r^{d-1}q^{r}.$

Before we prove Lemma 6.2 let us discuss how it is used to complete the proof
of (6.1). Let us fix $\beta>0$ as required for applying the lemma. Then,
clearly, since $p<1$, we have

$\displaystyle\sum_{r=1}^{\infty}{\mathbb{P}}(W_{r})\leq r_{0}+\sum_{r\geq
r_{0}}{\mathbb{P}}(W_{r})\leq r_{0}+\sum_{r\geq
r_{0}}c_{1}r^{d-1}p^{r}<\infty$

and thus, by (6.3),

$\displaystyle\sum_{r=1}^{\infty}{\mathbb{P}}(V_{r})<\infty.$

Hence, by the Borel-Cantelli lemma,
${\mathbb{P}}(\limsup_{r\to\infty}V_{r})=0.$ Since

$\displaystyle(\limsup_{r\to\infty}V_{r})^{c}$
$\displaystyle=\\{\omega\in\Omega\ |\ \exists r_{0}\in{\mathbb{N}}\text{ s.t.
}\omega\in V_{r}^{c}\text{ for all }r>r_{0}\\}$
$\displaystyle=\\{\omega\in\Omega\ |\ \exists r_{0}\in{\mathbb{N}}\text{ s.t.
}T(\omega)(2r)\geq\beta r^{1+q}\text{ for all }r\geq r_{0}\\}=D_{\beta}$

we conclude that ${\mathbb{P}}(D_{\beta})=1$. This completes the proof of
(6.1) and thus of Kesten’s method (up to a proof of Lemma 6.2).

In order to prepare the proof of Lemma 6.2, we introduce some more notation
and provide a few auxiliary results. For any $r\in{\mathbb{N}}$, any path
$\mathbf{z}=(z_{0},\ldots,z_{r})\in Z_{r}$ (cf. (6)) and any
$i\in\\{0,\dots,r\\}$, we define random variables

$\displaystyle\tau^{\mathbf{z}}_{i}:\Omega\to{\mathbb{N}}_{\infty},\quad\tau^{\mathbf{z}}_{i}(\omega)=\begin{cases}j,&\text{
if }j\in{\mathbb{N}}\text{ and }y_{j}(\omega)=z_{i},\\\ \infty,&\text{ if
}z_{i}\notin F_{\infty}(\omega),\end{cases}$

that is, $\tau^{\mathbf{z}}_{i}$ is either the time point $j$ at which $z_{i}$
is added to the cluster or $\infty$ if this never happens. Further, for
$i\in\\{1,\dots,r\\}$, we define waiting times

$\displaystyle\sigma^{\mathbf{z}}_{i}:\Omega\to{\mathbb{N}}_{\infty},\quad\omega\mapsto\begin{cases}\tau^{\mathbf{z}}_{i}(\omega)-\tau^{\mathbf{z}}_{i-1}(\omega),&\text{
if }\tau^{\mathbf{z}}_{i-1}(\omega)<\tau^{\mathbf{z}}_{i}(\omega)<\infty,\\\
\infty,&\text{ else},\end{cases}$

so $\sigma^{\mathbf{z}}_{i}$ is the waiting time between adding $z_{i-1}$ and
$z_{i}$ to the cluster, if both are added and $z_{i-1}$ is added before
$z_{i}$. We also consider the event

$\displaystyle
U_{\mathbf{z}}:=\\{\tau^{\mathbf{z}}_{0}<\ldots<\tau^{\mathbf{z}}_{r}<\infty\\}$

that all the vertices of the path $\mathbf{z}$ are added to the cluster in the
right order (i.e., $z_{\ell}$ before $z_{\ell+1}$). Note that
${\mathbb{P}}(U_{\mathbf{z}})>0$. We will now prove that the random variable
$\sigma^{\mathbf{z}}_{i}$ conditioned on $U_{\mathbf{z}}$ always dominates a
geometrically distributed random variable with parameter

(6.4) $\displaystyle p_{r}:=Cr^{-q},$

where the constants $C$ and $q$ are the ones from the hypothesis in
Theorem4.1. In particular, they are the same for all $i\in\\{0,\dots,r-1\\}$
and independent of $r\in{\mathbb{N}}$.

######  Lemma 6.3.

For any $r\in{\mathbb{N}}$ and $i=1,\ldots,r$, we have

$\displaystyle{\mathbb{P}}(\sigma^{\mathbf{z}}_{i}>k|U_{\mathbf{z}})\geq{\mathbb{P}}(Y>k)$

for any $k\in{\mathbb{N}}$, where $Y$ is geometrically distributed with
parameter $p_{r}$ as in (6.4).

###### Proof.

Fix $i\in\\{1,\ldots,r\\}$. Let
$U_{\mathbf{z}}^{i,j}:=U_{\mathbf{z}}\cap\\{\tau^{\mathbf{z}}_{i}=j\\}$,
$j\in{\mathbb{N}}$ and let $k\in{\mathbb{N}}$. It suffices to show that for
any $j$ such that ${\mathbb{P}}(U_{\mathbf{z}}^{i,j})>0$

(6.5)
$\displaystyle{\mathbb{P}}(\sigma^{\mathbf{z}}_{i}>k|U_{\mathbf{z}}^{i,j})\geq{\mathbb{P}}(Y>k).$

Indeed, since $U_{\mathbf{z}}=\bigcup_{j\in{\mathbb{N}}}U_{\mathbf{z}}^{i,j}$
is a disjoint decomposition, we infer that

$\displaystyle{\mathbb{P}}(\sigma^{\mathbf{z}}_{i}>k|U_{\mathbf{z}})$
$\displaystyle=\sum_{j\in{\mathbb{N}}}{\mathbb{P}}(\\{\sigma^{\mathbf{z}}_{i}>k\\}\cap\\{\tau^{\mathbf{z}}_{i}=j\\}|U_{\mathbf{z}})$
$\displaystyle=\sum_{j\in{\mathbb{N}}}\frac{{\mathbb{P}}(\\{\sigma^{\mathbf{z}}_{i}>k\\}\cap
U_{\mathbf{z}}^{i,j})}{{\mathbb{P}}(U_{\mathbf{z}})}=\sum_{j:{\mathbb{P}}(U_{\mathbf{z}}^{i,j})>0}\frac{{\mathbb{P}}(\\{\sigma^{\mathbf{z}}_{i}>k\\}\cap
U_{\mathbf{z}}^{i,j})}{{\mathbb{P}}(U_{\mathbf{z}})}$
$\displaystyle=\sum_{j:{\mathbb{P}}(U_{\mathbf{z}}^{i,j})>0}{\mathbb{P}}(\sigma^{\mathbf{z}}_{i}>k|U_{\mathbf{z}}^{i,j})\frac{{\mathbb{P}}(U_{\mathbf{z}}^{i,j})}{{\mathbb{P}}(U_{\mathbf{z}})}.$

Now, by (6.5), the first probability in each summand can be bounded from below
by ${\mathbb{P}}(Y>k)$ and taking this factor out of the summation, the
remaining summands sum to 1. Hence, we obtain
${\mathbb{P}}(\sigma^{\mathbf{z}}_{i}>k|U_{\mathbf{z}})\geq{\mathbb{P}}(Y>k)$
as asserted in the lemma.

For a proof of (6.5), fix $j\in{\mathbb{N}}$ and define for any
$\ell\in{\mathbb{N}}$ the event
$A_{\ell}:=\\{\omega\in\Omega:y_{j+\ell}(\omega)\neq z_{i}\\}$. Set
$A_{0}:=U_{\mathbf{z}}^{i,j}$. Then, by the multiplication formula of
conditional probabilities, we have for any $k\in{\mathbb{N}}$

$\displaystyle{\mathbb{P}}(\sigma^{\mathbf{z}}_{i}>k|U_{\mathbf{z}}^{i,j})$
$\displaystyle={\mathbb{P}}(\bigcap_{\ell=1}^{k}A_{\ell}|A_{0})=\prod_{m=1}^{k}{\mathbb{P}}(A_{m}|\bigcap_{\ell=0}^{m-1}A_{\ell}).$

Now observe that the condition in the $m$-th factor implies, that at time
$j+m$ the cluster $F_{j+m}$ has radius at least $r$ and contains $z_{i-1}$ but
not $z_{i}$. (And thus, due to the choice of $\mathbf{z}$, $z_{i}$ is in the
outer boundary of $F_{j+m}$.) Hence, by the hypothesis (4.1) in Kesten’s
method (Theorem 4.1), we get

$\displaystyle{\mathbb{P}}(A_{m}|\bigcap_{\ell=0}^{m-1}A_{\ell})\geq 1-p_{r}.$

We conclude that
${\mathbb{P}}(\sigma^{\mathbf{z}}_{i}>k|U_{\mathbf{z}}^{i,j})\geq(1-p_{r})^{k}={\mathbb{P}}(Y>k)$
holds for any $k\in{\mathbb{N}}$, proving (6.5). ∎

Since we want to sum geometric random variables in a moment, we also provide
the following standard bound, which can e.g. be found in [12, Lemma 2.6.2].

######  Lemma 6.4.

Let $n\in{\mathbb{N}}$, $n\geq 2$ and let $Y_{1},\dots,Y_{n}$ be independent
geometrically distributed random variables with parameter $0<p<\frac{1}{2}$.
Then for every $a\geq 2p$,

$\displaystyle{\mathbb{P}}\left(\sum_{i=1}^{n}Y_{i}\leq
a\frac{n}{p}\right)\leq(2ae^{2})^{n}.$

Based on this important observation we obtain the following bound for the
waiting time $\tau^{\mathbf{z}}_{r}$ until the path $\mathbf{z}\in Z_{r}$ is
completely added to the cluster conditioned on the event that it is added.

######  Lemma 6.5.

For any $\beta>0$ there is some $r_{0}\in{\mathbb{N}}$ such that for all
$r\in{\mathbb{N}}$ with $r\geq r_{0}$ and all $\mathbf{z}\in Z_{r}$

$\displaystyle{\mathbb{P}}(W_{r}(\mathbf{z}))\leq(2\beta Ce^{2})^{r},$

where $C$ is the constant in the hypothesis of Theorem 4.1.

###### Proof.

Fix some $\beta>0$ and set $a:=\beta C$. Choose $r_{0}\in{\mathbb{N}}$ large
enough such that $p_{r_{0}}<\min\\{\frac{1}{2},\frac{a}{2}\\}$. Note that this
implies $a=\beta C\geq 2p_{r}$ for all $r\geq r_{0}$.

Observe that
$W_{r}(\mathbf{z})\subset\\{\tau^{\mathbf{z}}_{r}\leq\tilde{m}_{r}\\}\cap
U_{\mathbf{z}}$ and thus

$\displaystyle{\mathbb{P}}(W_{r}(\mathbf{z}))\leq{\mathbb{P}}(W_{r}(\mathbf{z})|U_{\mathbf{z}})\leq{\mathbb{P}}(\tau^{\mathbf{z}}_{r}\leq\tilde{m}_{r}|U_{\mathbf{z}})$

Note that under the condition $U_{\mathbf{z}}$, $\tau^{\mathbf{z}}_{r}$ may be
represented as
$\tau^{\mathbf{z}}_{r}=\tau^{\mathbf{z}}_{0}+\sum_{i=1}^{r}\sigma^{\mathbf{z}}_{i}$.
Hence, for any $t>0$, we obtain

$\displaystyle{\mathbb{P}}(\tau^{\mathbf{z}}_{r}\leq t|U_{\mathbf{z}})$
$\displaystyle\leq{\mathbb{P}}(\tau^{\mathbf{z}}_{r}-\tau^{\mathbf{z}}_{0}\leq
t|U_{\mathbf{z}})={\mathbb{P}}(\sum_{i=1}^{r}\sigma^{\mathbf{z}}_{i}\leq
t|U_{\mathbf{z}}).$

Now recall from Lemma 6.3 that, conditioned on $U_{\mathbf{z}}$, each of the
random variables $\sigma^{\mathbf{z}}_{i}$ dominates a geometric random
variable $Y$ with parameter $p_{r}$. Moreover, given $\tau_{i}^{\mathbf{z}}$,
the randomness in the variable $\sigma^{\mathbf{z}}_{i+1}$ will only depend on
the subsequent steps of the construction. Hence their sum dominates a sum
$\sum_{i-1}^{r}Y_{i}$ of independent geometric random variables $Y_{i}$ with
parameter $p_{r}$. That is, for any $t>0$

$\displaystyle{\mathbb{P}}(\tau^{\mathbf{z}}_{r}\leq t|U_{\mathbf{z}})$
$\displaystyle\leq{\mathbb{P}}\left(\sum_{i=1}^{r}Y_{i}\leq t\right).$

Specializing now to $t=\tilde{m}_{r}$ and recalling from the definition of
$\tilde{m}_{r}$ and (6.4) that $\tilde{m}_{r}=\beta r^{1+q}=\beta
C\frac{r}{p_{r}}=a\frac{r}{p_{r}}$, we can apply Lemma 6.4 with $n=r$,
$p=p_{r}$ and $a=\beta C$. (Note that the hypothesis $a\geq 2p_{r}$ is
satisfied for $r\geq r_{0}$.) We obtain that for any $r\in{\mathbb{N}}$ with
$r\geq r_{0}$,

$\displaystyle{\mathbb{P}}(W_{r}(\mathbf{z}))$
$\displaystyle\leq{\mathbb{P}}(\tau^{\mathbf{z}}_{r}\leq\tilde{m}_{r}|U_{\mathbf{z}})\leq{\mathbb{P}}(\tau^{\mathbf{z}}_{r}\leq\frac{ar}{p_{r}}|U_{\mathbf{z}})\leq(2\beta
Ce^{2})^{r},$

which completes the proof. ∎

Now we have all the ingredients to provide a proof of Lemma 6.2.

###### Proof of Lemma 6.2.

Choose $\beta>0$ small enough that $4d\beta Ce^{2}<1$. By definition of
$W_{r}$ and Lemma 6.5, there exists $r_{0}\in{\mathbb{N}}$ such that, for any
$r\geq r_{0}$,

$\displaystyle{\mathbb{P}}(W_{r})$ $\displaystyle\leq\sum_{\mathbf{z}\in
Z_{r}}{\mathbb{P}}(W_{r}(\mathbf{z}))\leq\\#Z_{r}\cdot(2\beta Ce^{2})^{r}.$

Recall that the paths of $Z_{r}$ start in $S_{r}$ and observe that there is
some constant $c_{1}$ such that $\\#S_{r}\leq c_{1}r^{d-1}$. Hence there are
at most $c_{1}r^{d-1}$ starting points for paths in $Z_{r}$. Moreover, since
each point in ${\mathbb{Z}}^{d}$ has $2d$ neighbors and paths in $Z_{r}$ have
length $r$, there are at most $(2d)^{r}$ possible paths with a given starting
point. Hence $\\#Z_{r}\leq c_{1}r^{d-1}(2d)^{r}$. We infer that for any $r\geq
r_{0}$

$\displaystyle{\mathbb{P}}(W_{r})$ $\displaystyle\leq
c_{1}r^{d-1}(2d)^{r}\cdot(2\beta Ce^{2})^{r}=c_{1}r^{d-1}q^{r},$

where $q:=4d\beta Ce^{2}<1$, due to the choice of $\beta$, and $c_{1}>0$.
Hence we have found some $\beta>0$ (and suitable constants $c_{1}$, $q$ and
$r_{0}$) such that the asserted bound in Lemma 6.2 holds for all
$r\in{\mathbb{N}}$ with $r\geq r_{0}$. ∎

## References

  * [1] A. Auffinger, M. Damron, and J. Hanson.  50 years of first-passage percolation, volume 68 of University Lecture Series.  American Mathematical Society, Providence, RI, 2017.  doi:10.1090/ulect/068.
  * [2] R. C. Ball and T. A. Witten.  Causality bound on the density of aggregates.  Phys. Rev. A, 29:2966–2967, May 1984.  URL: https://link.aps.org/doi/10.1103/PhysRevA.29.2966, doi:10.1103/PhysRevA.29.2966.
  * [3] A.-L. Barabási and H. E. Stanley.  Fractal Concepts in Surface Growth.  Cambridge University Press, 1995.  doi:10.1017/CBO9780511599798.
  * [4] I. Benjamini and A. Yadin.  Upper bounds on the growth rate of diffusion limited aggregation, 2017\.  arXiv:1705.06095.
  * [5] D. Bensimon, E. Domany, and A. Aharony.  Crossover of fractal dimension in diffusion-limited aggregates.  Phys. Rev. Lett., 51:1394–1394, Oct 1983.  URL: https://link.aps.org/doi/10.1103/PhysRevLett.51.1394, doi:10.1103/PhysRevLett.51.1394.
  * [6] T. Bosch.  Incremental-aggregations.  https://github.com/tillmanntristanbosch/incremental-aggregations, 2021.  Accessed: 2023-08-23.
  * [7] M. Eden.  A two-dimensional growth process.  In Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Vol. IV, pages 223–239. Univ. California Press, Berkeley, Calif., 1961.
  * [8] R. Jullien and R. Botet.  Aggregation and fractal aggregates.  World Scientific Publishing Co., Inc., Teaneck, NJ, 1987.
  * [9] H. Kesten.  How long are the arms in DLA?  J. Phys. A, 20(1):L29–L33, 1987.  doi:10.1088/0305-4470/20/1/007.
  * [10] H. Kesten.  Upper bounds for the growth rate of DLA.  Phys. A, 168(1):529–535, 1990.  doi:10.1016/0378-4371(90)90405-H.
  * [11] M. Kolb.  Structure Formation by Aggregation: Models and Applications, pages 381–389.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.  doi:10.1007/3-540-44946-9_31.
  * [12] G. F. Lawler.  Intersections of random walks.  Probability and its Applications. Birkhäuser Boston, Inc., Boston, MA, 1991.
  * [13] G. F. Lawler, M. Bramson, and D. Griffeath.  Internal diffusion limited aggregation.  Ann. Probab., 20(4):2117–2140, 1992.  URL: http://links.jstor.org/sici?sici=0091-1798(199210)20:4<2117:IDLA>2.0.CO;2-K&origin=MSN.
  * [14] P. Meakin.  The Vold-Sutherland and Eden models of cluster formation.  Journal of Colloid and Interface Science, 96(2):415–424, 1983.  URL: https://www.sciencedirect.com/science/article/pii/0021979783900449, doi:10.1016/0021-9797(83)90044-9.
  * [15] P. Meakin and J. M. Deutch.  The formation of surfaces by diffusion limited annihilation.  The Journal of Chemical Physics, 85(4):2320–2325, 08 1986.  arXiv:https://pubs.aip.org/aip/jcp/article-pdf/85/4/2320/11207514/2320\\_1\\_online.pdf, doi:10.1063/1.451129.
  * [16] I. S. Molchanov.  Diffusion-limited aggregation with jumps and flights.  J. Statist. Comput. Simulation, 64(4):357–381, 1999.  doi:10.1080/00949659908811985.
  * [17] E. Sava-Huss.  From fractals in external DLA to internal DLA on fractals.  In Fractal Geometry and Stochastics VI, volume 76 of Progr. Probab., pages 273–298. Birkhäuser/Springer, 2021.  URL: https://doi.org/10.1007/978-3-030-59649-1_12, doi:10.1007/978-3-030-59649-1\\_12.
  * [18] R. Schneider and W. Weil.  Stochastic and integral geometry.  Probability and its Applications (New York). Springer-Verlag, Berlin, 2008\.  doi:10.1007/978-3-540-78859-1.
  * [19] H. E. Stanley and N. Ostrowsky, editors.  On growth and form, volume 100 of NATO Advanced Science Institutes Series E: Applied Sciences.  Martinus Nijhoff Publishers, Dordrecht, 1986.  Fractal and nonfractal patterns in physics, Papers from a course given as part of the NATO-ASI series at the Cargèse summer school, Cargèse, June 26–July 6, 1985.
  * [20] T. Vicsek.  Fractal growth phenomena.  World Scientific Publishing Co., Inc., Teaneck, NJ, 1989.  With a foreword by Benoit B. Mandelbrot.  doi:10.1142/0511.
  * [21] T. A. Witten and L. M. Sander.  Diffusion-limited aggregation, a kinetic critical phenomenon.  Phys. Rev. Lett., 47:1400–1403, Nov 1981.  URL: https://link.aps.org/doi/10.1103/PhysRevLett.47.1400, doi:10.1103/PhysRevLett.47.1400.