# Diffusion limited aggregation in the layers model

Colin Cooper
Department of Informatics
King’s College
London WC2B 4BG
England Research supported at the University of Hamburg, by a Mercator
fellowship from DFG Project 491453517 Alan Frieze
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh PA15213
U.S.A Research supported in part by NSF Grant DMS1952285

###### Abstract

In the classical model of Diffusion Limited Aggregation (DLA), introduced by
Witten and Sander, the process begins with a single particle cluster placed at
the origin of a space, and then, one at a time, particles make a random walk
from infinity until they collide with, and stick to, the existing cluster.

We consider an analogous version of this process on large but finite graphs
with a designated source and sink vertex. Initially the cluster of halted
particles contains a single particle at the sink vertex. Starting one at a
time from the source, each particle makes a random walk in the direction of
the sink vertex. The particle halts at the last unoccupied vertex before the
walk enters the cluster for the first time, thus increasing the size of the
cluster. This continues until the source vertex becomes occupied, at which
point the process ends.

We study the DLA process on several classes of layered graphs, including
Cayley trees of branching factor at least two with a sink vertex attached to
the leaves. We determine the finish time of the process for a given class of
graphs and show that the subcomponent of the final cluster linking source to
sink is essentially a unique path.

##  1 Introduction

#### Diffusion limited aggregation.

In the classical model of Diffusion Limited Aggregation (DLA), introduced by
Witten and Sander [11], [12], the process begins with a single particle
cluster placed at the origin of a space, and then, one-at-a-time, particles
make a random walk “from infinity” until they collide with, and stick to, the
existing cluster. The process is particularly natural in Euclidean space with
particles making Brownian motion, or on $d$–dimensional lattices. Simulations
of DLA in two dimensions show tree-like figures with long branches, and Kesten
[7] proved that for lattices, if $d=2$ the length of these arms is at most
order $n^{2/3}$ and if $d>2$, at most $n^{2/d}$. A similar process, Reaction
Limited Aggregation (RLA), differs in that particles stick with probability
less than one on each collision. Indicative publications on RLA include Ball
et al [2] or Meakin and Family [10].

A distinct but related process, Internal Diffusion Limited Aggregation (IDLA),
was introduced by Diaconis and Fulton [3], as a protocol for recursively
building a random aggregate of particles. In IDLA particles are added to the
source vertex of an infinite graph, and make a random walk (over occupied
vertices) until they visit an unoccupied vertex at which point they halt. Thus
the first particle occupies the source, and subsequent particles stick to the
outside of the component rooted at the source. Hence IDLA is the opposite of
DLA, in that the particles walk in the occupied vertices until they find a
space, rather than walking until they collide with the occupied component. The
focus in IDLA has been on the limiting shape of the component formed by the
occupied vertices. The formative work by Lawler et al [8], proved that, on
$d$-dimensional lattices the limiting shape approaches a Euclidean ball; a
result subsequently refined in [1], [6] and [9], amongst others.

As pointed out by Kesten in Remark 3 of [7], the concept of releasing a
particle ”from infinity” is somewhat informal. In [7] this is circumvented by
using the limiting distribution of the first visit to the boundary of the
current component from far away, conditional on making such a visit. We
consider an analogous version of this process on large but finite graphs with
a designated source and sink vertex. This model of DLA on finite graphs, was
previously studied by Hastings and Halsey [5] for binary trees, and Frieze and
Pegden [4] for the Boolean lattice ${\mathcal{B}}=\\{0,1\\}^{n}$. In [4] the
process evolves at discrete time steps $t=0,1,\dots$; each of which has an
associated cluster $C_{t}$. The initial cluster $C_{0}$ consists of a single
vertex ${\bf 0}=(0,\dots,0)\in{\mathcal{B}}$, the sink vertex. The cluster
$C_{t}$ is produced from $C_{t-1}$ by choosing a random decreasing walk
$\rho_{t}$ from the source vertex ${\bf 1}=(1,\dots,1)$. Let $v$ be the last
vertex of the initial segment of $\rho_{t}$ which is disjoint from $C_{t-1}$,
and set $C_{t}=C_{t-1}\cup\\{v\\}$. The process terminates at the first time
$t_{f}$ when ${\bf 1}\in C_{t_{f}}$. The current paper continues this analysis
of DLA on finite graphs with a layered structure, such as complete multi-
partite graphs and Cayley trees.

#### The layers model.

Let $S_{0},S_{1},\ldots,S_{k},S_{k+1}$ be disjoint sets of vertices, where
$S_{i}$ is connected to $S_{i+1}$ by a complete bipartite graph, with edges
directed from level $i$ to level $i+1$, to form a layered graph $G$. The set
$S_{i}$, at distance $i$ from the source, forms layer $i$ of $G$, at level
$i$. We assume $S_{0}$ contains a single vertex $v$, the source vertex of the
particles, and $S_{k+1}$ contains a single vertex $z$ the sink vertex of the
particle cluster. Initially $z$ is the only occupied vertex. The sink vertex
$z$ is an artificial vertex added to ensure connectivity of $C_{t}$, and to
maintain compatibility with the hypercube model of [4].

Let $N_{i}=|S_{i}|$ be the size of set $S_{i}$. For $i=1,\ldots,k$, the sizes
of $S_{i}$, are either taken to be the same size, $N_{i}=n/k$ (the equal
layers model), growing geometrically so that $N_{i}=d^{i}$ (the growing layers
model).

To simplify notation we assume that in the equal layers model $G$ is an
$(n+1)$–vertex graph with layer sizes $N_{i}=n/k$ for $i=1,..,k$ ; and that in
the growing layers model, $d^{k}=n$ and thus $G$ is a
$(d^{k+1}-1)/(d-1)n$–vertex graph. Similarly for trees of height $k$ and
branching factor $d$, we assume that the final level is of size $d^{k}=n$.

#### DLA in the layers model.

Initially, at step $t=0$ all vertices of $G$ are unoccupied. A step $t$
consists of placing an active particle on the (unoccupied) source vertex and
moving the particle forward level by level according to a random walk
$\rho_{t}$ from source to sink until it halts. To move forward from level
$i<k$, the active particle currently at vertex $u$ in level $i$ chooses a
random neighbour $w$ in level $i+1$. If the neighbour $w$ is unoccupied the
particle moves to $w$. If the neighbour $w$ is occupied, the particle halts at
vertex $u$ in level $i$, occupies that vertex and adds a directed edge $(u,w)$
to the edge induced component $C_{t}$ rooted at the sink. As the sink $z$ is
occupied at the start, a particle reaching level $i+1=k$ halts there.

At any step, the component $C_{t}$ is a rooted tree with edges directed
towards the root, the sink $z$. The process stops at step $t_{f}$, the finish
time, when the source vertex $v$ is occupied by a halted particle. Thus
$t_{f}$ is also the final number of particles occupying the graph.

At the finish time, there is a directed path connecting the source $v$ to the
sink $z$, all of whose vertices are occupied by halted particles. On deletion
of the sink vertex $z$, the digraph $D_{t}=C_{t}\\!\setminus\\!\\{z\\}$
consists of disjoint arborescences rooted at the occupied vertices in level
$k$. Let $v=u_{0}u_{1}\cdots u_{k}u_{k+1}=z$ be the connecting path, the path
connecting source and sink at the end of the process. Perhaps the most
surprising thing is that in the digraph $D_{t_{f}}$, with high probability the
arborescence rooted at $u_{k}$ containing the connecting path is precisely the
connecting path $v=u_{0}u_{1}\cdots u_{k}$, and contains no other vertices.

######  Theorem 1.

Let $v=u_{0}u_{1}\cdots u_{k}u_{k+1}=z$ be the path, connecting source and
sink at the end of the process. Let $w=u_{k}$ be the vertex at level $k$ on
this path. The following results hold with high probability.

  1. 1.

Equal layers model. For $i=1,...,k$ let $N_{i}=n/k$.
Let

$T_{f}=[(k+1)!(n/k)^{k}]^{1/(k+1)}=n^{k/(k+1)}\gamma_{k}$

where $\gamma_{k}=O(1)$ and $\gamma_{k}\rightarrow 1/e$ as
$k\rightarrow\infty$.

Provided $1\leq k\leq\sqrt{(\log n)/(\log\log n)}$, the finish time $t_{f}$
satisfies $T_{f}/\omega\leq t_{f}\leq\omega T_{f}$, where $\omega$ is any
function tending to $\infty$.

  2. 2.

Trees of branching factor $d$, and the growing layers model. For $i=0,...,k$
let $N_{i}=d^{i}$. Let

$T_{f}=\sqrt{k}\;d^{k+3/2-\sqrt{2k+2}}.$

    1. (a)

Provided $d\rightarrow\infty,\;k\rightarrow\infty$, (and $k\ll d$ for trees)
the finish time $t_{f}$ satisfies $T_{f}/(\omega d^{O(1/\sqrt{k})})\leq
t_{f}\leq\omega T_{f}$.

(The extra term $d^{O(1/\sqrt{k})}$ is there to deal with some rounding error
in $j^{*}$.)

    2. (b)

At $t_{f}$, levels $i=1,\ldots,k-\lceil\sqrt{2k+2}-1\rceil$ contain a single
occupied vertex, the vertex $u_{i}$ of the the connecting path.

  3. 3.

On termination, let $v=u_{0}u_{1},\cdots u_{k}z$ be the path connecting source
$v$ and sink $z$ in $C_{t_{f}}$, and let
$D_{t_{f}}=C_{t_{f}}\\!\setminus\\!\\{z\\}$. In either model, with high
probability, the vertices $\\{u_{1},\cdots,u_{k}\\}$ have in-degree one in
$C_{t_{f}}$. Thus the arborescence rooted at $u_{k}$ in $D_{t_{f}}$ is exactly
this connecting path.

By an indicative argument, Hastings and Halsey [5] derive an estimate of
$\sqrt{2k}\,2^{k-\sqrt{2k}}$ for the finish time of DLA on a binary tree of
height $k$. We confirm this estimate is of the correct order of magnitude, and
give a similar result for general Cayley trees.

######  Corollary 2.

For $d\geq 2$ constant, let

$T_{f}=\sqrt{k}\,d^{k-\sqrt{2k}}.$

With high probability the finish time $t_{f}$ of DLA on a tree of branching
factor $d$ and height $k$ satisfies $T_{f}/\omega\leq t_{f}\leq\omega T_{f}$.

#### Notation.

We use $A_{n}\sim B_{n}$ to denote $A_{n}=(1+o(1))B_{n}$ and thus
$\lim_{n\rightarrow\infty}A_{n}/B_{n}=1$. We use $\omega$ to denote a quantity
which tends to infinity with $n$ more slowly than any other variables in the
given expression. The expression $f(n)\ll g(n)$ indicates $f(n)=o(g(n))$. The
inequality $A\lesssim B$ which stands for $A\leq(1+o(1))B$ is used to
unclutter notation in some places.

##  2 Bounds on occupancy in the layers model

For $t\geq 0$, let $L_{i}(t)$ be the number of particles halted in level $i$
at the end of step $t$. Thus $L_{i}(0)=0$ for all $i\leq k$, and
$t=\sum_{i=0}^{k}L_{i}(t)$. We refer to $L_{i}$ as the occupancy of level $i$.
Note that $L_{k}(t)\leq t$, and $L_{i}(t)\leq\min(t,N_{i})$.

The first step is to prove the following proposition.

######  Proposition 3.

Let

$\mu_{k-j}(t)=\frac{1}{N_{k}N_{k-1}\cdots N_{k-j+1}}\;\frac{t^{j+1}}{(j+1)!}.$
(1)

Assume $t<t_{f}$, and thus the process has not stopped. Provided
$\mu_{k-\ell}(t)\rightarrow\infty$ for all $\ell\leq j$, then
$L_{k-j}(t)\sim\mu_{k-j}(t)$ in all models.

Let ${\cal H}(t)=(L_{0}(t),L_{1}(t),\ldots,L_{k}(t))$ be the history of the
process up to and including step $t$.

$\displaystyle\mathbb{E}\,(L_{i}(t+1)\mid{\mathcal{H}}(t))$
$\displaystyle=\;L_{i}(t)+\frac{L_{i+1}(t)}{N_{i+1}}\prod_{j=0}^{i}\left(1-\frac{L_{j}(t)}{N_{j}}\right),\qquad
i<k,$ (2) $\displaystyle\mathbb{E}\,(L_{k}(t+1)\mid{\mathcal{H}}(t))$
$\displaystyle=\;L_{k}(t)+\prod_{j=0}^{k}\left(1-\frac{L_{j}(t)}{N_{j}}\right).$
(3)

Note that (3) follows from (2) as $L_{k+1}(t)/N_{k+1}=1$ for all $t$, and that
if $L_{0}(t)=1$, the above recurrences give $L_{i}(t+1)=L_{i}(t)$.

To simplify matters for small $t$, we can condition on the event that
$L_{k}(s)=s$ for $s\leq\sqrt{N_{k}/\omega}$, an event of probability
$1-1/\omega$, and use the fact that the evolution of
$(L_{0}(t),L_{1}(t),\ldots,L_{k}(t))$ is Markovian. Whatever happens,
$L_{i}(t)$ is monotone non-decreasing in $t$.

###  2.1 Upper bound on occupancy at step $t$

The underlying random walk $\rho_{t}$, from source $v$ to sink $z$ defines a
$(v,z)$-path given by $v=u_{0}u_{1},...,u_{k}z=v_{k+1}$. Particle $t$ follows
this walk until halting at a vertex $u_{i}$, where $u_{i+1}$ is the first
occupied vertex encountered on the path.

Let $B_{i}(t)$ denote the occupied (blocked) vertices in level $i$ at time
$t$. We define an upper-blocked process which we use to upper bound
$L_{i}(t)$. This process gives rise to sets $\widehat{B}_{i}(t)\supseteq
B_{i}(t)$ and random variables $\widehat{L}_{i}(t)=|\widehat{B}_{i}(t)|\geq
L_{i}(t)$. For every vertex $u_{j}$, $j\leq k$ on the walk $\rho_{t}$, if
$u_{j+1}$ is occupied add a vertex to $\widehat{B}_{j}(t)$ as follows. If
$u_{j}\not\in\widehat{B}_{j}(t)$ add $u_{j}$ to $\widehat{B}_{j}(t+1)$. If
$u_{j}\in\widehat{B}_{j}(t)$ add some other $u^{\prime}_{j}\in
S_{j}\\!\setminus\\!\widehat{B}_{j}(t)$ to $\widehat{B}_{j}(t+1)$.

In particular if particle $t+1$ halts at vertex $u_{i}$ in the DLA process,
then either $u_{i}$ is added to both $B_{i}(t+1)$ and $\widehat{B}_{i}(t+1)$,
or $u_{i}$ is already a member of $\widehat{B}_{i}(t)$. In either case
$B_{i}(t)\subseteq\widehat{B}_{i}(t)$ for all $i$ and $t\geq 0$. It follows
(among other things) that $L_{i}(t)\leq\widehat{L}_{i}(t)$, and
$\widehat{L}_{k}(t)=t$. The next lemma gives w.h.p. bounds for
$\widehat{L}_{i}(t)$.

######  Lemma 4.

Let $\mu_{k-j}(t)$ as be given by (1).

  1. 1.

The expectations $\mathbb{E}\,\widehat{L}_{i}(t)$ satisfy the recurrence

$\displaystyle\mathbb{E}\,(\widehat{L}_{i}(t+1)\mid\widehat{H}(t))$
$\displaystyle=\;\widehat{L}_{i}(t)+\frac{\widehat{L}_{i+1}(t)}{N_{i+1}}.$ (4)

  2. 2.

If $j^{2}/t=o(1)$ then $\mathbb{E}\,\widehat{L}_{k-j}(t)\sim\mu_{k-j}(t)$.

  3. 3.

If $t\geq t_{k-j}(\omega)$ as defined in (12) then w.h.p.
$\widehat{L}_{k-j}(t)\sim\mu_{k-j}(t)$.

###### Proof.

Equation (4) follows because the upper bound process increases the size of
$\widehat{B}_{j}(t)$ whenever the walk $\rho_{t}$ contains a vertex of
$\widehat{B}_{j+1}(t)$, this being true at all levels $j=0,...,k$. We have

$\mathbb{E}\,(L_{i}(t+1)\mid{\mathcal{H}}(t))\leq
L_{i}(t)+\frac{L_{i+1}(t)}{N_{i+1}}\leq\widehat{L}_{i}(t)+\frac{\widehat{L}_{i+1}(t)}{N_{i+1}}=\mathbb{E}\,(\widehat{L}_{i+1}(t+1)\mid\widehat{\mathcal{H}}(t)).$

Iterating (4) backwards for $0\leq s\leq t$, and using $\widehat{L}_{i}(0)=0$,
gives

$\mathbb{E}\,\widehat{L}_{i}(t)=\frac{1}{N_{i+1}}\;\sum_{s=0}^{t-1}\mathbb{E}\,\widehat{L}_{i+1}(s).$
(5)

We claim for $j\geq 0$ that

$\displaystyle\,\mathbbm{1}_{\\{{t\geq
j}\\}}\;\frac{(t-j)^{j+1}}{(j+1)!}\leq(N_{k}N_{k-1}\cdots
N_{k-j+1})\;\mathbb{E}\,\widehat{L}_{k-j}(t)\leq\frac{t^{j+1}}{(j+1)!}.$ (6)

For given $t$, the induction is backwards on $k-j$ from $j=0$. Now $N_{k+1}=1$
and $\widehat{L}_{k+1}(t)=1$ which implies that $\widehat{L}_{k}(s)=s$ for
$0\leq s\leq t$. So, (6) is true when $j=0$ and the first non-trivial case is
$j=1$. From (5) we see that

$\mathbb{E}\,\widehat{L}_{k-1}(t)=\frac{1}{N_{k}}\sum_{s=0}^{t-1}s,$ (7)

which illustrates how (6) arises from bounding this sum.

For the general induction put $i=k-(j+1)$, and multiply (5) by
$M_{j-1}=N_{k}N_{k-1}\cdots N_{k-j+1}$. Insert (6) with $i+1=k-j$ into this,
to give

$\frac{1}{N_{k-j}}\sum_{s=j}^{t-1}\ \frac{(s-j)^{j+1}}{(j+1)!}\leq
M_{j-1}\;\mathbb{E}\,\widehat{L}_{k-(j+1)}(t)\leq\frac{1}{N_{k-j}}\sum_{{s=1}}^{t-1}\
\frac{s^{j+1}}{(j+1)!}\\\ $ (8)

By comparison of the sum with the related integral we have that

$\frac{(t-1)^{m+1}}{m+1}\leq
1^{m}+2^{m}+\cdots+(t-1)^{m}\leq\frac{t^{m+1}}{m+1}.$ (9)

Use (9) in (8) with $m=j+1$, giving

$\frac{\,\mathbbm{1}_{\\{{t\geq
j+1}\\}}}{N_{k-j}}\;\frac{(t-(j+1))^{j+2}}{(j+2)!}\leq
M_{j}\;\mathbb{E}\,\widehat{L}_{k-(j+1)}(t)\leq\frac{1}{N_{k-j}}\frac{t^{j+2}}{(j+2)!},\\\
$

which completes the induction for (6). Moreover, provided $j^{2}/t=o(1)$,

$\mathbb{E}\,\widehat{L}_{k-j}(t)=\frac{1}{N_{k}N_{k-1}\cdots
N_{k-j+1}}\frac{t^{j+1}}{(j+1)!}\left(1-O\left(j^{2}/t\right)\right)=\mu_{k-j}(t)(1+o(1)).$
(10)

This completes the proof of Lemma 4.(1) and Lemma 4.(2) . Note that
$t_{k-j}(\omega)\gg(n/k)^{1/k}\gg k^{2}$ for $j\geq 1$, ensuring that
$j^{2}/t=o(1)$ for $j,t$ of interest.

###  2.2 Concentration of $\widehat{L}_{i}(t)$ for sufficiently large $t$.

We now prove Lemma 4.(3) .

By definition, $\widehat{L}_{k}(t)=t=\mu_{k}(t)$, establishing Lemma 4.(3) for
$j=0$.

We next consider $\widehat{L}_{k-j}(t)$ for $1\leq j\leq k-1$. The random
variable $\widehat{L}_{k-j}(t)$ is obtained by choosing a random vertex $u\in
S_{k-j}$ irrespective of the current occupancy of $u$, and choosing a random
neighbour $w\in S_{k-j+1}$. If $w$ is occupied then
$\widehat{L}_{k-j}(t+1)=\widehat{L}_{k-j}(t)+1$. Thus,
$\widehat{L}_{k-j}(t+1)=\widehat{L}_{k-j}(t)+Q_{k-j}(t)$ where
$\mathbb{P}(Q_{k-j}(t)=1)=(\widehat{L}_{k-j+1}(t)/N_{k-j})$ independently of
any previous outcomes.

In particular, $\mathbb{E}\,Q_{k-1}(t)=t/N_{k}$, and by equation (7),
$\mathbb{E}\,\widehat{L}_{k-1}(t)=t(t-1)/(2N_{k})\sim\mu_{k-1}(t)$. By
Hoeffding’s Inequality,

$\mathbb{P}\left(\widehat{L}_{k-1}(t)\notin\mu_{k-1}(t)\left(1\pm\frac{1}{\omega}\right)\right)\leq
2\exp\left\\{-\frac{(1-o(1))t^{2}}{6\omega^{2}N_{k}}\right\\}\leq
2e^{-\omega}$ (11)

if $t\geq 2\omega^{3/2}\sqrt{2N_{k}}$.

For $j\geq 0$ we proceed as follows: let $t_{1}=t_{1}(k-j)$ be such that
$\mu_{k-j}(t_{1})=1$. Thus $t_{1}(k)=1$ and

$t_{1}(k-j)=[(j+1)!N_{k}N_{k-1}\cdots N_{k-j+1}]^{1/(j+1)}.$

The fact that $t_{1}(k-j+1)\ll t_{1}(k-j)$ so that $\mu_{k-j+1}(t_{1}(k-j))$
is sufficiently large, is a model dependent calculation given in subsequent
sections. The statement of Lemma 4 assumes the truth of this.

Let $t_{k}(\omega)=1$, and for $j\geq 1$, let
$t_{k-j}(\omega)=(4\omega^{3})^{1/(j+1)}t_{1}(k-j)$ so that

$t_{k-j}(\omega)=(4\omega^{3})^{1/(j+1)}[(j+1)!N_{k}N_{k-1}\cdots
N_{k-j+1}]^{1/(j+1)},$ (12)

and $\mu_{k-j}(t_{k-j}(\omega))=4\omega^{3}$.

Let ${\mathcal{E}}_{j}$ denote the event that
$\widehat{L}_{k-j}(t)\in\mu_{k-j}(t)(1\pm 1/\omega)$ for $t\geq
t_{k-j}(\omega)$. We claim that $\mathbb{P}({\mathcal{E}}_{j})\geq
1-2je^{-\omega}$ and we verify this by induction.

For $j=0$, $\mathbb{P}({\mathcal{E}}_{0})=1$, and for $j=1$,
$\mathbb{P}({\mathcal{E}}_{1})\geq 1-2e^{-\omega}$ follows from equation (11).
For $j\geq 2$, by Hoeffding’s inequality, we have that for $t\geq
t_{k-j}(\omega)$,

$\mathbb{P}(\neg{\mathcal{E}}_{j}\mid{\mathcal{E}}_{j-1})\leq
2\exp\left\\{-\frac{\mu_{k-j}(t)}{3\omega^{2}}\left(1-\delta\right)\right\\}\leq
2\exp\left\\{-\frac{\mu(t_{k-j}(\omega))}{3\omega^{2}}\left(1-o(1)\right)\right\\}\leq
2e^{-\omega},$

where $\delta=O(1/{\omega}+j^{2}/t)$, includes the correction from (10).

We complete the induction, on the assumption that $\log k\ll\omega$, via

$\mathbb{P}(\neg{\mathcal{E}}_{j})\leq\mathbb{P}(\neg{\mathcal{E}}_{j}\mid{\mathcal{E}}_{j-1})+\mathbb{P}(\neg{\mathcal{E}}_{j-1})\leq
2e^{-\omega}+2(j-1)e^{-\omega}=2je^{-\omega}=o(1).$ (13)

∎

###  2.3 Lower bound on occupancy at step $t$

A lower bound $\widetilde{L}_{i}(t)$ on $L_{i}(t)$ can be found as follows. We
consider a process in which a particle halts at level $i$ whenever it chooses
an out neighbour in $\widehat{B}_{i+1}(t)$. Let $L^{*}_{j}(t)$ bound
$\widehat{L}_{j}(t)$ from above w.h.p. Let $\widetilde{L}_{i}(t)$ be obtained
by replacing $L$ by $L^{*}$ in in the bracketed terms on the RHS of (2)–(3).
Then $\widetilde{L}\leq L\leq\widehat{L}$ w.h.p., and we have the following
recurrences.

$\displaystyle\mathbb{E}\,\widetilde{L}_{i}(t+1)$
$\displaystyle=\;\mathbb{E}\,\widetilde{L}_{i}(t)+\frac{\mathbb{E}\,\widetilde{L}_{i+1}(t)}{N_{i+1}}\prod_{j=0}^{i}\left(1-\frac{L^{*}_{j}(t)}{N_{j}}\right),$
(14) $\displaystyle\mathbb{E}\,\widetilde{L}_{k}(t+1)$
$\displaystyle=\;\mathbb{E}\,\widetilde{L}_{k}(t)+\prod_{j=0}^{k}\left(1-\frac{L^{*}_{j}(t)}{N_{j}}\right).$
(15)

The solution to these recurrences is given in Section 3.2 for the equal layers
model, and in Section 4 for the growing layers model.

##  3 Analysis of DLA in the equal layers model

The first subsection below shows that provided $k$ is not too large, then
w.h.p. there exists a large gap in the number of steps between the time for
which $\mathbb{E}\,\widehat{L}_{k-j}=1$ with all lower values zero, and the
time for which $\mathbb{E}\,\widehat{L}_{k-(j+1)}=1$. This gap allows
$\widetilde{L}_{k-j}$ to increase and become concentrated, whilst at the same
time all lower values remain zero w.h.p. This allows us to conclude that
provided $\mu_{i}(t)$ is sufficiently large, $L_{i}(t)$ is concentrated around
$\mu_{i}(t)$. We use this to conclude that $L_{0}(t)=0$ until
$L_{1}(t)\rightarrow\infty$ suitably fast, and thus estimate the finish time
of the DLA process in the equal layers model.

###  3.1 Evolution of the state vector $\widehat{L}$ in the equal layers
model.

Let $\widehat{L}=(\widehat{L}_{0},\widehat{L}_{1},\ldots,\widehat{L}_{k})$ be
the state vector of the upper-blocked process. The entries in $\widehat{L}$
are non-negative integers, and if $\widehat{L}_{i}=0$, then
$\widehat{L}_{i-1}=0$. Let

$T_{f}=\left[(k+1)!N_{1}\cdots N_{k}\right]^{1/(k+1)},$ (16)

where $N_{1}=\cdots=N_{k}=n/k$. It will be shown below that $T_{f}$ is
asymptotically the expected finish time. The following argument for
$t\leq\omega T_{f}$ proves there is a large enough gap $t^{\prime\prime}-t$
between $\mu_{k-j}(t)=1$ and $\mu_{k-(j+1)}(t^{\prime\prime})=1$ for
$\widehat{L}_{k-j}(t^{\prime\prime})$ to be concentrated.

Define $\beta=\beta_{k}=N_{k}/\omega T_{f}$. As

$[(k+1)!]^{1/(k+1)}=k\Theta(1+k^{3/2k})=k\Theta(1),$

then

$\beta=\frac{N_{k}}{\omega
T_{f}}=\frac{n/k}{\omega[(k+1)!(n/k)^{k}]^{1/(k+1)}}=\Theta(1)\frac{1}{\omega
k}\left(\frac{n}{k}\right)^{1/(k+1)}.$ (17)

We can assume that $\beta\geq(\log n)^{k/2}$. This will be true if
$\omega\leq\log n$ since we assume that $k\leq\sqrt{(\log n)/\log\log n}$.

We have for any $t\leq\omega T_{f}$, using that $N_{k-j}=N_{k}=n/k$ in the
equal layers model, that

$\displaystyle\mu_{k-(j+1)}(t)$
$\displaystyle=\frac{t}{(j+2){N_{k-j}}}\cdot\mu_{k-j}(t)\leq\frac{1}{j\beta}\mu_{k-j}(t),$
(18) $\displaystyle\mu_{k-(j+\ell)}(t)$
$\displaystyle=\frac{t}{(j+\ell+1){N_{k-\ell-1}}}\cdot\mu_{k-(j+\ell)-1}(t)\leq\frac{1}{(j\beta)^{\ell}}\mu_{k-j}(t),\qquad\text{for
}1\leq\ell\leq k-j.$ (19)

Consider $\mathbb{E}\,\widehat{L}_{k-j}(t)$. When $\mu_{k-j}(t)\sim 1$, then
$\mathbb{E}\,\widehat{L}_{k-j}(t)\sim 1$ and the Markov inequality implies
that w.h.p. $\widehat{L}_{k-j}(t)\in I_{\omega}=[0,1,...,\omega]$. From
(18)–(19), when $\mu_{k-j}(t)\sim 1$,

$\mu_{k-(j+\ell)}(t)\leq\frac{1+o(1)}{(j\beta)^{\ell}},\qquad\text{for
}1\leq\ell\leq k-j,$ (20)

and thus w.h.p.
$\widehat{L}_{0}=0,\widehat{L}_{1}=0,\ldots,\widehat{L}_{k-(j+1)}=0$.

By arguments similar to that for (18), (19), we see that

$\mu_{k-j+\ell}(t)\geq\mu_{k-j}(t)\;j(j-1)\cdots(j-\ell+1)\,\beta^{\ell}\qquad\text{for
}\ell\leq j.$

So if $\mu_{k-j}(t)\sim 1$ then for $\ell\leq j$, $\mu_{k-j+\ell}(t)\to\infty$
and $\widehat{L}_{k-j+\ell}$ is equal to
$(1+o(1))\mathbb{E}\,\widehat{L}_{k-j+\ell}$ w.h.p. (As already remarked at
the end of Section 2.1, $k^{2}/t=o(1)$ for $t$ of interest here and we can
invoke Lemma 4.) Thus at times $t$ such that $\mu_{k-j}(t)\sim 1$ (implying
that $t\leq\omega T_{f}$), w.h.p., the state vector $\widehat{L}$ is such that
$\mu_{k-\ell}\rightarrow\infty$ for $\ell\leq j-1$, and

$\widehat{L}(t)=(0,\ldots,0,\;\widehat{L}_{k-j}\in
I_{\omega},\;(1+o(1))\mu_{k-j+1},\;(1+o(1))\mu_{k-j+2},\ldots,\;(1+o(1))\mu_{k}).$
(21)

Define $t^{\prime}>t$ so that
$\mathbb{E}\,\widehat{L}_{k-j}(t^{\prime})\sim\mu_{k-j}(t^{\prime})=\omega$
where $\omega\rightarrow\infty$ but $\omega\ll\beta$. It follows from (1) that
$t^{\prime}\sim\omega^{1/(j+1)}t$. Using $T_{f}=\gamma_{k}n^{k/(k+1)}$ from
Proposition 5.1, for $j<k$ we have $t^{\prime}\leq\omega T_{f}$ which follows
from $t^{\prime}=\Theta(1)\omega^{1/(j+1)}N_{k}^{j/(j+1)}\ll\omega T_{f}$ for
$\omega$ growing sufficiently slowly,

$\mu_{k-(j+1)}(t^{\prime})=\frac{t^{\prime}}{(j+2)N_{k}}\omega\leq\frac{\omega}{\beta},\qquad\mu_{k-j}(t^{\prime})=\omega,\qquad\mu_{k-j+1}(t^{\prime})=\frac{(j+1)N_{k}}{t^{\prime}}\omega\geq\omega\beta.$

Choosing $\log\log n\leq\omega\ll\beta$, we have that w.h.p.
$\widehat{L}_{k-(j+1)}(t^{\prime})=0$ as before and $\mu_{k-j+1}\geq\omega\log
n$. But now

$\widehat{L}(t^{\prime})=(0,...,0,\;(1+o(1))\mu_{k-j},\;(1+o(1))\mu_{k-j+1},...,\;(1+o(1))\mu_{k}).$
(22)

This condition persists until $t^{\prime\prime}$ such that
$\mu_{k-(j+1)}(t^{\prime\prime})\sim 1$. Equating $\mu_{k-j}(t)\sim
1\sim\mu_{k-(j+1)}(t^{\prime\prime})$ and using $t\leq\omega T_{f}$ gives

$(t^{\prime\prime})^{j+2}\sim t^{j+1}(j+2)N_{k}\quad\implies\quad
t^{\prime\prime}\geq
t\left(\frac{N_{k}}{t}\right)^{1/(j+2)}\geq\;t\beta^{1/k}\geq t(\log
n)^{1/2},$

by our choice of $\beta$. We conclude that $t^{\prime\prime}\geq(\log
n)^{1/2}t$, so the claimed gap exists.

###  3.2 Lower bound on occupancy in the equal layers model.

Let $L^{*}_{j}(t)=\omega\mu_{j}(t)$. By (21), (22) of the previous section,
this is a w.h.p. upper bound on $\widehat{L}_{j}(t)$ for $t\leq\omega T_{f}$.
Referring to (14)–(15), we claim that

$\prod_{j=0}^{i}\left(1-\frac{L^{*}_{j}(t)}{N_{j}}\right)\geq
1-\sum_{j=0}^{i}\left(\frac{L^{*}_{j}(t)}{N_{j}}\right)\geq
1-\frac{iL^{*}_{i}(t)}{N_{i}}=1-o(1).$ (23)

Note first that as $T_{f}=O(kn^{k/(k+1)})$ and $N_{k}=n/k$, then provided
$k\leq\sqrt{\log n/\log\log n}$ and $\omega$ grows sufficiently slowly,

$\frac{k\omega^{2}T_{f}}{N_{k}}=O\left(\frac{\omega^{2}k^{2+1/(k+1)}}{n^{1/(k+1)}}\right)=o(1);$
(24)

and as $N_{k-j+1}=N_{k}$ and
$\mu_{k-j}(t)/\mu_{k-j+1}(t)=t/(j+1)N_{k-j+1}=o(1)$ by (24), it follows that

$\mu_{k-j}(t)/N_{k-j}\leq t/N_{k}.$ (25)

Thus (23) follows from (24), (25) and

$\frac{jL^{*}_{j}(t)}{N_{j}}=\frac{j\omega\mu_{j}(\omega
T_{f})}{N_{j}}\leq\frac{k\omega\mu_{k}(\omega
T_{f})}{N_{k}}\leq\frac{k\omega^{2}T_{f}}{N_{k}}=o(1).$ (26)

Let $t_{i}(\omega)$ be given by (12). For those $i\leq k$, and $t\geq
t_{i}(\omega)$, so that $\mu_{i}(t)\rightarrow\infty$ suitably fast, we obtain
that
$\mathbb{E}\,\widetilde{L}_{i}(t)\sim\mu_{i}(t)\sim\mathbb{E}\,\widehat{L}_{i}(t)$
and thus w.h.p.,

$\mathbb{E}\,L_{k-j}(t+1)\sim\mathbb{E}\,\widehat{L}_{k-j}(t+1)\sim\frac{t^{j+1}}{(j+1)!}\frac{1}{N_{k}N_{k-1}\cdots
N_{k-j+1}}.$ (27)

As $L_{i}(t)\leq\widehat{L}_{i}(t)$ by construction, and w.h.p.
$\widehat{L}_{i}(t)\leq(1+o(1))\mathbb{E}\,\widehat{L}_{i}(t)$, this implies
$L_{i}(t)\leq(1+o(1))\mu_{i}(t)$ w.h.p., if $\mu_{i}(t)\rightarrow\infty$.

At step $t+1$, equation (23) implies that, in the DLA-process, particle $t+1$
arrives at level $i$ with probability $(1-o(1))$. It halts at this level with
probability $L_{i+1}(t)/N_{i+1}=o(1)$, (see (2), (25)), and thus w.h.p. all
but $t(1-o(1))$ particles arrive at level $k$, the $o(1)$ term being given in
(26).

It is an induction on $\ell=k-1,\ldots,i$ in that order, that provided $t\geq
t_{\ell}(\omega)$, then $\mu_{\ell}(t)\rightarrow\infty$ sufficiently fast,
the values $L_{k}(t),L_{k-1}(t),\ldots,L_{i}(t)$ are concentrated in the lower
tail, according to the arguments in Section 2.2. Thus
$L_{i}(t)\sim\mu_{i+1}(t)$ w.h.p..

In the case that $\mathbb{E}\,\widehat{L}_{i}(t)=o(1)$ then a fortiori
$L_{i}(t)=0$ w.h.p., and if $\mathbb{E}\,\widehat{L}_{i}(t)=O(1)$ then w.h.p.
$L_{i}(t)\leq\omega\mu_{i}(t)$. We can thus argue that a gap theorem similar
to that in Section 3.1 holds for the state vector
$L=(L_{0},L_{1},\ldots,L_{k})$.

In particular, and most importantly, let $t_{1}=t_{1}(0)$ be such that
$\mu_{0}(t_{1})=1$, and thus $t_{1}\sim T_{f}$. Let $t^{\prime}=t_{1}/\omega$.
Then w.h.p., $L_{0}(t^{\prime})=O(1/\omega)$ and
$\mathbb{E}\,L_{1}(t^{\prime})\geq\beta/\omega$ where $\beta$ is given in
(17). It follows that for $t\geq t^{\prime}$, $L_{1}(t)$ is concentrated
around $\mu_{1}(t)$.

This completes the proof of Proposition 3 for the equal layers model.

###  3.3 Finish time of DLA in the equal layers model.

######  Proposition 5.

For $k\geq 2$, let $G$ be an equal layers graph with level sizes $N_{i}=n/k$,
$i=1,...,k$. Let $T_{f}$ be given by (16), then

  1. 1.

$T_{f}=n^{k/(k+1)}e^{-1}(1+O(\log k/k))$

  2. 2.

With high probability, the finish time $t_{f}$ of the DLA process in $G$
satisfies
$T_{f}/\omega\leq t_{f}\leq\omega T_{f}$, where $\omega\rightarrow\infty$
arbitrarily slowly.

###### Proof.

Note that

$\frac{(k+1)!}{k^{k}}\sim\frac{1}{k^{k}}\sqrt{2\pi}e^{-(k+1)}k^{k+3/2}(1+1/k)^{k+3/2}=e^{-(k+1)}\;\Theta_{k},$

where $\Theta_{k}\sim(e^{1-1/k+O(1/k^{2})}\sqrt{2\pi}k^{3/2})$. Thus

$T_{f}=\left[(k+1)!N_{1}\cdots
N_{k}\right]^{1/(k+1)}=\left(\frac{(k+1)!}{k^{k}}{n}^{k}\right)^{1/(k+1)}=n^{\frac{k}{k+1}}e^{-1}(\Theta_{k})^{1/(k+1)},$
(28)

where $(\Theta_{k})^{1/k+1}=e^{O(\log k/k})$ is bounded for $k\geq 2$ and
tends to one as $k\rightarrow\infty$.

The choice of $T_{f}$ is such that $\mathbb{E}\,\widehat{L}_{0}(T_{f})\sim 1$,
indeed from (10)

$\displaystyle\mathbb{E}\,\widehat{L}_{0}(T_{f})$
$\displaystyle=\;1+O\left(\frac{k^{2}}{T_{f}}\right)=\;1+O\left(\frac{k^{2}}{n^{k/(k+1)}}\right),$
(29)

which is $1+o(1)$, provided $k=o(\sqrt{n})$ say. Moreover
$\mathbb{E}\,\widehat{L}_{0}(T_{f}/\omega)\sim 1/\omega^{k+1}$ proving that
$t_{f}=\Omega(T_{f})$ w.h.p.

The value of $\mathbb{E}\,\widehat{L}_{k-j}(t)$ is monotone decreasing with
increasing $j$. This follows from (18) because $T_{f}=o(N_{k})$, making
$\beta$ large, see (28). We next investigate the concentration of
$L_{1}(T_{f})$, which continues the discussion in the last paragraph of the
previous section.

$\displaystyle\mathbb{E}\,L_{1}(T_{f})$
$\displaystyle\sim\mu_{1}(T_{f})\sim\;\frac{(T_{f})^{k}}{k!(n/k)^{k-1}}=\frac{1}{k!}[(k+1)!)^{k}(n/k)]^{\frac{1}{k+1}}=\Theta(n^{1/(k+1)}k^{-{3/2(k+1)}}).$
(30)

For concentration of $\widehat{L}_{1}(T_{f})$ we require
$\mathbb{E}\,L_{1}(T_{f})\to\infty$, which occurs whenever $k=o(\log n)$.

At this point in the process, even if $L_{0}(T_{f})=0$, the expected waiting
time for a particle to hit $L_{1}(T_{f})$ is $O(n^{k/(k+1)}/k)=O(T_{f})$, so
w.h.p. this will occur by time $\omega T_{f}$, completing the proof of
Proposition 5, and hence Theorem 1.1. ∎

###  3.4 Existence of a unique connecting path component.

We regard occupied vertices as coloured either red or blue, with all occupied
vertices in level $k$ coloured blue.

A particle halts at vertex $u$ in level $i$, if it chooses an edge $uw$ to an
occupied neighbour $w$ in level $i+1$. We consider this edge $uw$ as being
directed from $u$ to $w$ in the component rooted at the sink. If $u$ is the
first in-neighbour of $w$ then $u$ is coloured blue. If however $w$ already
has an in-neighbour $u^{\prime}$, then $u,u^{\prime}$ and all other in-
neighbours are (re)coloured red. At any step, the red vertices in a level are
those with siblings, and the blue ones are the unique in-neighbour of some
vertex in the next level. The process halts when there is a directed path of
occupied vertices $v=u_{0}u_{1}\cdots u_{k}$ from the source to level $k$.

######  Lemma 6.

With high probability, the path $v=u_{0}u_{1}\cdots u_{k}=w$ from the source
to level $k$ is blue and thus the in-arborescence of halted particles rooted
at $w=u_{k}$ is exactly this $(v,w)$-path.

###### Proof.

As before, let $B_{i}$ be the set of occupied vertices in level $i$, where
$L_{i}=|B_{i}|$. As each $u\in B_{i}$ has a unique out-neighbour, the subset
Out$(B_{i})$ of $B_{i+1}$ with at least one in-neighbour has size at most
$L_{i}$.

Let $\,\mathbbm{1}_{\\{{k-j,s}\\}}$ be the indicator that particle $s$ halts
in level $k-j$ and is coloured red due to a pre-existing sibling. In this case
particle $s$ has chosen an out-neighbour in the existing set
Out$(B_{k-j})\subseteq B_{k-j+1}$, and thus

$\mathbb{E}\,\,\mathbbm{1}_{\\{{k-j,s}\\}}\leq\frac{\mathbb{E}\,\widehat{L}_{k-j}(s)}{(n/k)}\sim\frac{\mu_{k-j}(s)}{(n/k)}.$

If $Z_{k-j}(t)$ is the number of red vertices in level $k-j$, then

$\mathbb{E}\,Z_{k-j}(t)\lesssim
2\sum_{s=1}^{t}\frac{\mu_{k-j}(s)}{(n/k)}=\frac{2}{(n/k)}\sum_{s=1}^{t}\frac{s^{j+1}}{(j+1)!(n/k)^{j}}\\\
\sim 2\frac{t^{j+2}}{(j+2)!(n/k)^{j+1}}=2\mu_{k-(j+1)}(t).$ (31)

The factor 2 covers the case where the pre-existing sibling was blue but is
recoloured red.

Define a random variable $\widehat{Z}_{k-j}(t)=Z_{k-j}(t)+Q_{k-j}(t)\geq
Z_{k-j}(t)$, where $Q_{k-j}$ is Bernoulii $Be(p_{k-j})$, with
$p_{k-j}=(\widehat{L}_{k-j}-|\mbox{\rm Out}(B_{k-j})|)/(n/k)$. As
$\mu_{i}\rightarrow\infty$ at $t_{f}$ for all $i\geq 1$, for $i\geq 2$,
$\widehat{Z}_{i}(t_{f})=(1+o(1))\mathbb{E}\,\widehat{Z}_{i}(t_{f})$ w.h.p.,
since $Z_{i}(t_{f})\leq\widehat{Z}_{i}(t_{f})\leq\widehat{L}_{i}(t_{f})$. On
the other hand, by definition $\mathbb{E}\,L_{0}(T_{f})=1$, so by the Markov
Inequality $Z_{1}(t_{f})\leq\widehat{Z}_{1}(t_{f})\leq\omega$.

Consider the colour of the path $v=u_{0}u_{1}u_{2}\cdots u_{k}$ at $t\leq
t_{f}$. Vertex $v$ is blue as it is the first neighbour of $u_{1}$. Let
$R_{i}(s)$ be the red vertices in level $i$ at step $s$. Vertex $u_{1}$ was
chosen u.a.r. so, as $\mu_{0}(T_{f})\sim 1$ (see (29)),
$\mu_{1}(T_{f})=\Theta(1)n^{1/(k+1)}$ (see (30)), and $t_{f}\geq
T_{f}/\omega$,

$\mathbb{P}(u_{1}\in
R_{1}(t))=\frac{Z_{1}(t)}{L_{1}(t)}\leq\frac{\omega}{\mu_{1}(t)}\leq\frac{\omega^{2}}{n^{1/(k+1)}}.$
(32)

Let $s_{1}$ be the step at which $u_{1}=u_{1}(s_{1})$ was occupied by a halted
particle. This happened because $s_{1}$ chose an occupied out-neighbour
$u_{2}=u_{2}(s_{2})$, where $s_{2}<s_{1}$. If $u_{2}$ is red at step $t$, then
either it became red before step $s_{1}$, or at some later step. As $u_{2}$
was chosen u.a.r. by the particle $s_{1}$ at $u_{1}$ from among the
$L_{2}(s_{1})$ occupied vertices in level 2,

$\mathbb{P}(u_{2}\in R_{2}(s_{1}))=\frac{Z_{2}(s_{1})}{L_{2}(s_{1})}\lesssim
2\omega\frac{\mu_{1}(s_{1})}{\mu_{2}(s_{1})}=\frac{2\omega
s_{1}}{k(n/k)}=\frac{2\omega s_{1}}{n}.$

The factor of $2$ is from (31) and $\omega$ covers lack of concentration of
$\widehat{Z}_{2}$ or $L_{2}$, if $s_{1}$ is early. If $u_{3}$ is the chosen
out-neighbour of $u_{2}$,

$\mathbb{P}(u_{2}\in
R_{2}(t)\\!\setminus\\!R_{2}(s_{1}))\leq\frac{1}{(n/k)}\sum_{\tau=s_{1}+1}^{t}\mathbb{E}\,\,\mathbbm{1}_{\\{{u_{3}\text{
chosen at }\tau}\\}}=\frac{t-s_{1}}{(n/k)}.$

Thus

$\mathbb{P}(u_{2}\in R_{2}(t))\leq\frac{\omega kt}{n},$

and similarly for $u_{3},\ldots,u_{k-1}$. Thus

$\mathbb{P}((v,u_{k})\text{--path is
blue})\geq\prod_{i=1}^{k-1}\left(1-\frac{\omega
kt}{n}\right)=1-O\left(\frac{\omega k^{2}t}{n}\right),$

where $t\leq t_{f}\leq\omega n^{k/(k+1)}$. Provided $\omega
k^{2}/n^{1/(k+1)}=o(1)$, which holds for $3k\log k\leq n$, the path from the
source to vertex $w=u_{k}$ level $k$ is blue, and thus the in-arborescence
root at $w$ is exactly this path. ∎

##  4 Analysis of DLA in the growing layers model

######  Proposition 7.

Let $G$ be a growing layers graph with level sizes $N_{i}=d^{i}$, for
$i=0,...,k$. Let

$T_{f}=\sqrt{k}\;d^{k+3/2-\sqrt{2k+2}}.$ (33)

Let $j=\max\\{i:(2k+2)\geq i(i+1)\\}$, and let $j^{*}=\sqrt{2k+2}-1$ be the
solution to $2k+2=i(i+1)$.

  1. 1.

Provided $d\rightarrow\infty,\;k\rightarrow\infty$, and $j=j^{*}$ the finish
time $t_{f}$ satisfies $T_{f}/\omega\leq t_{f}\leq\omega T_{f}$, where
$\omega\rightarrow\infty$ arbitrarily slowly.

  2. 2.

If $j\neq j^{*}$ the error in finish time $t_{f}$ above introduced by ignoring
rounding is $d^{-O(1/\sqrt{k})}$, and thus $T_{f}d^{-O(1/\sqrt{k})}/\omega\leq
t_{f}\leq\omega T_{f}$.

  3. 3.

At $t_{f}$, levels $i=1,\ldots,k-\lceil\sqrt{2k+2}-1\rceil$ contain a single
occupied vertex, the vertex $u_{i}$ of the the connecting path.

###### Proof.

The size $N_{i}$ of layer $i$ is defined as $d^{i}$. It follows that the
product of the set sizes in the denominator of $\mu_{k-j}(t)$ in (1) is given
by

$N_{k}N_{k-1}\cdots N_{k-j+1}=d^{k}d^{k-1}\cdots d^{k-j+1}=d^{kj-j(j-1)/2},$

and thus (1) becomes

$\mu_{k-j}(t)=\frac{t^{j+1}}{(j+1)!\;d^{kj-j(j-1)/2}}.$ (34)

Assume $d$ is sufficiently large. The upper bound
$\mathbb{E}\,\widehat{L}_{k-j}$ is obtained in Section 2. However, a problem
can arise in the growing layers model in the upper bound calculations. The
value of $\mu_{k-j}$ can decrease with increasing $j$ and then (anomalously)
increase again. This is presumably because the recurrence used to establish it
assumes $\mu_{k-\ell}\rightarrow\infty$ for all $\ell<j$, which is not the
case.

Let $t$ be such that $\mu_{k-j}(t)=1$, and let $t_{1}=t_{1}(k-j)$ be $\lceil
t\rceil$, so that $\mu_{k-j}(t)\sim 1$ at step $t_{1}$. From (34),

$\mu_{k-j}(t_{1})=\frac{t_{1}^{j+1}}{(j+1)!\;d^{kj-j(j-1)/2}}\sim
1\quad\implies\quad
t_{1}\sim[(j+1)!]^{1/(j+1)}\;d^{\frac{2kj-j(j-1)}{2(j+1)}}.$ (35)

From (1)

$\frac{\mu_{k-j+1}(t)}{\mu_{k-j}(t)}=\frac{(j+1)d^{k-j+1}}{t},$ (36)

so setting $\mu_{k-j}(t_{1}(k-j))\sim 1$ gives

$\displaystyle\mu_{k-j+1}(t_{1})\sim$
$\displaystyle\;\frac{j+1}{[(j+1)!]^{1/j+1}}\;d^{k-j+1-\frac{2kj-j(j-1)}{2(j+1)}}$
$\displaystyle\sim$
$\displaystyle\;\frac{e}{(2\pi(j+1))^{1/2(j+1)}}\;d^{\frac{2k+2-j(j+1)}{2(j+1)}}.$
(37)

The leading term on the RHS is bounded, and the exponent of $d$ on the RHS is
positive provided $2k+2>j(j+1)$, which ensures that
$\mathbb{E}\,\widehat{L}_{k-j+1}(t)$ is sufficiently large close to
$t_{1}(k-j)$.

What value of $k-j$ maximizes the step $t_{1}=t_{1}(k-j)$ at which
$\mu_{k-j}(t)\sim 1$? Write the exponent of $d$ on the RHS of (35) as $f(j)/2$
where

$f(j)=\frac{2kj-j(j-1)}{(j+1)}=(2k+2)-j-\frac{2k+2}{j+1}.$

The maximum of $f(j)$ occurs when $(j^{*}+1)^{2}=(2k+2)$, giving
$f(j^{*})=(j^{*})^{2}$. The (not necessarily integer) value of $j^{*}$,
$k-j^{*}$ and $d^{f(j^{*})/2}$ are

$j^{*}=\sqrt{2k+2}-1,\qquad k-j^{*}=k+1-\sqrt{2k+2},\qquad
d^{f(j^{*})/2}=d^{k+3/2-\sqrt{2k+2}}.$ (38)

Integer solutions to $(j^{*}+1)^{2}=(2k+2)$ exist for some values of $k$. Let
$a$ be a positive integer, and put $j^{*}+1=2a$ so that $k=2a^{2}-1$; this
holds for example for $k=1,5,17,31$. In the case that $j^{*}$ is not integer,
we address the rounding error at the end of this section.

Ignoring rounding for now, we evaluate $t_{1}=t_{1}(k-j)$, at $j=j^{*}$ where
$f(j)=j^{2}$, to find

$\displaystyle t_{1}\sim$ $\displaystyle\;[(j+1)!]^{1/(j+1)}\;d^{f(j)/2}$
$\displaystyle\sim$
$\displaystyle\;e^{-1}(\sqrt{2\pi})^{1/(j+1)}\;(j+1)^{1+1/2(j+1)}\;\;d^{j^{2}/2}$
$\displaystyle=$
$\displaystyle\;C_{k-j}\;\sqrt{2k+2}\;\;d^{k+3/2-\sqrt{2k+2}},$ (39)

where $C_{k-j}=\Theta(1)$. Note that $t_{1}=\Theta(T_{f})$. From (34),

$\frac{\mu_{k-(j+1)}(t)}{\mu_{k-j}(t)}=\frac{t}{(j+2)d^{k-j}}$

so that at $t_{1}$, for some $C,\,C^{\prime}=\Theta(1)$,

$\mu_{k-j^{*}}(t_{1})\sim
1,\qquad\mu_{k-(j^{*}-1)}(t_{1})=Cd^{1/2},\qquad\mu_{k-(j^{*}+1)}(t_{1})=C^{\prime}d^{1/2}.$
(40)

At first this seems confusing, as one would expect to have
$\mu_{k-(j^{*}-1)}(t_{1})=Cd^{1/2}=o(1)$ here. But assuming
$d^{1/2}\rightarrow\infty$,
$\mathbb{E}\,\widehat{L}_{k-j^{*}+1}=C^{\prime\prime}d^{1/2}$, which is the
last value at which the condition $\mu_{k-j+1}\rightarrow\infty$ is valid in
the recurrence from $k-j+1$ to $k-j$; and is where the assumption in
Proposition 3 breaks down.

Note that at $t_{1}/\omega$,
$\mu_{k-j^{*}}(t_{1}/\omega)=O(\omega^{-(j^{*}+1)})$ from the definition of
$t_{1}(k-j^{*})$. Thus w.h.p. $\widehat{L}_{k-j^{*}}(t_{1}/\omega)=o(1)$ in
the upper process. Consequently all levels $k-\ell$, $\ell\geq j^{*}$, are
zero, w.h.p. in both the upper and the DLA process. In which case, as
occupancy is monotone non-decreasing, this holds in the state vector $L(t)$ of
the DLA process, for all $t\leq t_{1}/\omega$ and all $\ell\geq j^{*}$.

For $\ell<j^{*}$, as in the equal layers model we will use (23) to obtain
(27). To do this we check conditions (24) and (25) for $t\leq t_{f}$. Provided
$k\rightarrow\infty$, but $k=o((\log n/\log\log n)^{2})$,

$\frac{k\omega^{2}T_{f}}{N_{k}}=\frac{\omega^{2}k^{3/2}d^{k+3/2-\sqrt{2k+2}}}{d^{k}}=\omega^{2}k^{3/2}d^{3/2-\sqrt{2k+2}}=o(1);$
(41)

and as $N_{k-j}=d^{k-j}$, and $j^{*}+1=\sqrt{2k+2}$,

$\frac{\mu_{k-\ell}(t)}{\mu_{k-\ell+1}(t)}=\frac{t}{(\ell+1)d^{k-\ell+1}}\leq{\omega\sqrt{k}}d^{1/2-\sqrt{2k+2}+\ell}\leq{\omega\sqrt{k}}d^{1/2-\sqrt{2k+2}+j^{*}-1}=\omega\sqrt{k}d^{-3/2},$

provided $t\leq\omega T_{f}$. Thus provided $d>k\omega^{2}$,

$\frac{\mu_{k-\ell}(t)}{N_{k-\ell}}\leq\frac{\omega\sqrt{k}}{d^{3/2}}\frac{\mu_{k-\ell+1}(t)}{N_{k-\ell}}=\frac{\omega\sqrt{k}}{d^{1/2}}\frac{\mu_{k-\ell+1}(t)}{N_{k-\ell+1}}\leq\frac{\mu_{k-\ell+1}(t)}{N_{k-\ell+1}}.$

As $\mu_{k}(t)=t$, it follows that

$\mu_{k-j}(t)/N_{k-j}\leq t/N_{k},$ (42)

and thus (26) holds. As before, let $t_{i}(\omega)$ be given by (12). For
those $i\leq k$, and $t\geq t_{i}(\omega)$, so that
$\mu_{i}(t)\rightarrow\infty$ suitably fast, we obtain that
$\mathbb{E}\,\widetilde{L}_{i}(t)\sim\mu_{i}(t)\sim\mathbb{E}\,\widehat{L}_{i}(t)$,
and we have $L_{k-\ell}(t)\sim\widehat{L}_{k-\ell}(t)\sim\mu_{k-\ell}(t)$.

Let $t_{0}$ be the first step at which $L_{k-j^{*}}(t)=1$. Then either
$t_{0}\leq t_{1}$, or, as the probability a particle halts at level $k-j^{*}$
is

$\phi=\frac{L_{k-(j^{*}-1)}(t_{1})}{N_{k-(j^{*}-1)}}\sim\frac{Cd^{1/2}}{d^{k-j^{*}+1}}=\frac{C}{d^{k+3/2-\sqrt{2k+2}}};$

the probability this does not occur in a further $t_{1}$ steps is, see (39),

$(1-\phi)^{t_{1}}\leq e^{-t_{1}\phi}=e^{-{(1+o(1))}C\sqrt{2k+2}}=o(1),$

assuming $k\rightarrow\infty$. As
$\widehat{L}_{k-j^{*}}(\max(t_{0},t_{1}))\leq\omega$, w.h.p.; we assume that
$L_{k-j^{*}}(\max(t_{0},t_{1}))\leq\omega$, and for $\ell>j^{*}$,
$L_{k-\ell}=0$.

Let $u$ be the vertex in level $k-j^{*}$ containing the unique particle halted
at $t_{0}$. Construct a path back from $u$ to the source as follows. Wait
until a particle halts at $w_{k-j^{*}-1}$ in level $k-j^{*}-1$ by choosing
edge $w_{k-j^{*}-1}u$. The expected time for this is $d^{k-j^{*}}$. In a
further expected time $d^{k-j^{*}-1}$, the path will extend backwards, as a
particle will halt in level $k-j^{*}-2$ by choosing edge to $w_{k-j^{*}-1}$
etc. Thus in a further

$T=d^{k-j^{*}}+d^{k-j^{*}-1}+\cdots+d=d^{k-j^{*}}\left(\frac{1-1/d^{k-j^{*}}}{1-1/d}\right)=\Theta(d^{k-j^{*}})=\Theta(d^{k+1-\sqrt{2k+2}})$

expected steps there will be a path $vw_{1}\cdots w_{k-j^{*}-1}u$ of halted
particles extending from the source $v$ to vertex $u$ thus stopping the DLA
process (if it has not already halted). This path should be unique, as the
expected time for it to branch backwards at any level $i$ is $d^{i}\gg
d^{i-1}$ if $d\rightarrow\infty$.

On the other hand the time to create another halted particle in level
$k-j^{*}$ has expected value

$\frac{1}{\phi}=\Theta(d^{k+3/2-\sqrt{2k+2}})=\Theta(Td^{1/2}).$

On the assumption that $d\rightarrow\infty$, in at most $\omega(t_{1}+T)$
steps the process has halted w.h.p., as claimed.

#### The effect of rounding error in $j^{*}$.

In the case that $j^{*}$ is not integer, we require the maximum $j$ such that
$2k+2>j(j+1)$. Clearly $j=\lfloor j^{*}\rfloor$ satisfies $2k+2>j(j+1)$, but
what about $j=\lceil j^{*}\rceil$? Put $j=j^{*}+\varepsilon$. Further
analysis, not given here, shows that the condition $2k+2\geq j(j+1)$, is
satisfied by $j=\lceil j^{*}\rceil$ up to some $\varepsilon\in(1/2,1)$.

Let $j=\max\\{i:(2k+2)\geq i(i+1)\\}$ and suppose that $j=\lfloor
j^{*}\rfloor$ so that $j^{*}=j+\varepsilon$. Let $T_{M}=\Theta(t_{1}(k-j))$ be
given by

$T_{M}=\sqrt{k}d^{\frac{1}{2}(2k+2-j-(2k+2)/(j+1))},$

be a revised estimate of the order of the halting time, where $T_{M}\leq
T_{f}$ as $j^{*}$ maximizes $T_{f}$. As $j^{*}=\sqrt{2k+2}-1$,
$T_{f}=\sqrt{k}d^{({j^{*}}^{2}/2)}$, see (38), and
$2k+2-j^{*}-(j^{*})^{2}=\sqrt{2k+2}$,

$\displaystyle\frac{T_{M}}{T_{f}}=$ $\displaystyle
d^{\frac{1}{2}\left((2k+2)-j^{*}+\varepsilon-\frac{2k+2}{j^{*}+1-\varepsilon}-(j^{*})^{2}\,\right)}$
$\displaystyle=$ $\displaystyle
d^{\frac{1}{2}\left(\sqrt{2k+2}-\frac{\sqrt{2k+2}}{1-\varepsilon/(\sqrt{2k+2})}+\varepsilon\right)}$
$\displaystyle=$ $\displaystyle
d^{-\frac{\varepsilon^{2}}{2\sqrt{2k+2}}(1+O(1/\sqrt{k}))}.$

Choosing $j=\lceil j^{*}\rceil=j^{*}+\varepsilon$ gives the same result. Thus
the effect of rounding is to alter $T_{f}$ by $\Theta(1)d^{-O(1/\sqrt{k})}$. ∎

#### Existence of a unique connecting path component.

Finally, we prove that the arborescence rooted at level $k$ containing the
connecting path from source to sink, consists uniquely of that path. The proof
is similar to Lemma 6 for the equal layers model. At $t_{f}$, w.h.p. there is
a unique path from level $k-j^{*}$ to level zero, so that level $k-j^{*}+1$
plays the role of level one. By analogy with (30),

$\mathbb{P}(u_{k-j^{*}+1}\in
R_{k-j^{*}+1}(t))=\frac{Z_{k-j^{*}+1}(t)}{L_{k-j^{*}+1}(t)}\leq\frac{\omega}{\mu_{k-j^{*}+1}(t)}\leq
O\left(\frac{\omega^{2}}{d^{1/2}}\right),$

where we used an earlier result that $\mu_{k-(j^{*}-1)}(t_{1})=Cd^{1/2}$.

Thus as $t_{f}\leq\omega t_{1}(j^{*})$, where $j^{*}=\sqrt{2k+2}-1$ and
$t_{1}(k-j^{*})$ is given by (39)

$\mathbb{P}((v,u_{k})\text{--path is
blue})\geq\left(1-\frac{\omega^{2}}{d^{1/2}}\right)\;\prod_{j=1}^{j^{*}-2}\left(1-\frac{\omega
t_{f}}{d^{k-j}}\right)=1-O\left(\frac{\omega^{2}}{d^{1/2}}\right)-O\left(\frac{\omega\sqrt{k}}{d^{3/2}}\right).$

##  5 DLA on trees with large branching factor

Let $G=G(n,d)$ be a labelled tree with branching factor $d$ and final level
$k$, such that $d^{k}=n$. As before, the source of the particles is the unique
vertex $v$ at level zero, an artificial sink vertex $z$ is attached to the
vertices at level $k$, and $S_{i}$ denotes the set of vertices in level $i$.

Let $j^{*}=\sqrt{2k+2}-1$, and let $T_{f}$ be given by

$T_{f}=\sqrt{k}\;d^{k+3/2-\sqrt{2k+2}}.$ (43)

The expected number of particles arriving at a vertex in level $k-j^{*}$ by
step $T_{f}$ is order $T_{f}d^{-(k-j^{*})}=\sqrt{kd}$. However, the expected
number of particles arriving at a vertex $w$ at level $k-j^{*}+1$ by step
$T_{f}$ is

$\frac{T_{f}}{d^{k-j^{*}+1}}=\sqrt{\frac{k}{d}}=o(1),$ (44)

provided $k\ll d$, which we assume to be true. In order for $w$ to be
occupied, the sub-tree rooted at $w$ must contain a path from $w$ to level $k$
consisting of $j^{*}$ occupied vertices. By the Markov inequality the event
that $j^{*}=\Theta(\sqrt{k})$ particles have arrived at $w$ by step $T_{f}$,
has probability $O(1/\sqrt{d})$. So there should be few vertices in level
$k-j^{*}+1$ with a path to level $k$ containing $j^{*}$ halted particles.

Let $X_{w}=X_{w}(k-j,\ell,t)$ be the indicator for the event that exactly
$\ell$ particles reach vertex $w$ in level $k-j$ at or before step $t$. Say a
path in $G$ is open if it contains no occupied vertices. If the path from the
source $v$ to vertex $w$ is open at the end of step $t$, then
$\mathbb{E}\,X_{w}=p_{t}(w,\ell)$ where

$p_{t}(w,\ell)={t\choose\ell}\left(\frac{1}{d^{k-j}}\right)^{\ell}\left(1-\frac{1}{d^{k-j}}\right)^{t-\ell}.$
(45)

explanation. Let $Q=vw_{1}\cdots w_{k-j-1}w$ be the path in question. If $Q$
is open at step $s\leq t$, the probability particle $s$ ends up at $w$ is
$1/d^{k-j}$, and the probability it exits from $Q$ before reaching $w$ is
$1-1/d^{k-j}$. Let $x=w_{m}$, $m<k-j$ be the last vertex which the particle
shares with the path, and let $y\neq w_{m+1}$ be the child of $x$ chosen by
the particle. If $y$ was already occupied, the particle would halt at $x$, so
the path $Q$ would no longer be open at the end of step $t$.

#### The existence of exact paths.

The following analysis assumes all levels from level one to $k-j$ are empty at
step $t$, an event we denote by ${\cal E}(t)$. Let $X=X(k-j,j+1,t)$ where
$X=\sum_{w\in S_{k-j}}X_{w}$ is the number of vertices at level ${k-j}$ which
have exactly $\ell=j+1$ particles reaching them. Thus
$\mathbb{E}\,X=d^{k-j}\mathbb{E}\,X_{w}$, and

$\displaystyle\mathbb{E}\,X(X-1)=$ $\displaystyle(d^{k-j})(d^{k-j}-1){t\choose
2\ell}{2\ell\choose\ell}\left(\frac{1}{d^{k-j}}\right)^{\ell}\left(\frac{1}{d^{k-j}-1}\right)^{\ell}\left(1-\frac{2}{d^{k-j}}\right)^{t-2\ell}$
$\displaystyle=$
$\displaystyle\left(1+O\left(\frac{\ell}{d^{k-j}}\right)\right)(\mathbb{E}\,X)^{2}.$

Assume $t\leq t_{f}\leq\omega T_{f}$ as in Theorem 1. As $X\leq t_{f}/\ell$
deterministically,

${\bf
Var}X=\mathbb{E}\,X+O\left(\frac{\ell}{d^{k-j}}\right)(\mathbb{E}\,X)^{2}=(1+O(\omega\sqrt{k/d}))\;\mathbb{E}\,X=(1+o(1))\mathbb{E}\,X.$
(46)

We used (44), and $k\ll d$ to obtain the $o(1)$ term.

Let $\ell=j+1$. The probability the particles arriving at $w$ form a path
$w=w_{0}w_{1}w_{2}\cdots w_{j}=u$ of halted particles from level $k-j$ to
vertex $u$ in level $k$ is obtained as follows. Let $1\leq s_{0}\leq s_{1}\leq
s_{2}\leq\cdots\leq s_{j}\leq t$ be the steps (and particle labels) of the
halted particles forming this path. Thus $s_{0}$ reaches $w_{j}=u$ an event of
probability $1/d^{j}$, $s_{1}$ reaches $w_{j-1}$ and picks $u$ as a neighbour,
an event also of probability $1/d^{j}$ and so on, and finally $s_{j}$ picks
$w_{1}$ as a neighbour and halts at $w$, an event of probability $1/d$. Thus

$\mathbb{P}(\text{path }w_{0}w_{1}\cdots w_{j}\mid(j+1)\text{ arrivals at
}w)=\frac{1}{d^{j}}\frac{1}{dd^{2}\cdots d^{j}}.$ (47)

We call such a path exact if the halted particles on the path are the only
particles in the sub-tree from level $k-j$ to level $k$ rooted at $w$. Let
$Y_{w}$ be the number of exact paths from $w$ to level $k$ at step $t$. As
there are $d^{j}$ choices for $u$ given $w$, we have

$\displaystyle\mathbb{E}\,Y_{w}=$ $\displaystyle
d^{j}\frac{1}{d^{j}}\frac{1}{dd^{2}\cdots d^{j}}{t\choose
j+1}\left(\frac{1}{d^{k-j}}\right)^{j+1}\left(1-\frac{1}{d^{k-j}}\right)^{t-(j+1)}$
$\displaystyle=$ $\displaystyle(1-O(j^{2}/t))\;\frac{1}{d^{k}\cdots
d^{k-j}}\frac{t^{j+1}}{(j+1)!}e^{-t/d^{k-j}}$ (48)

Assume henceforth that $j\leq j^{*}-1$ and use (44) to replace the exponential
term in (48) by $1+o(1)$. Thus

$\displaystyle\mathbb{E}\,Y_{w}\sim$
$\displaystyle\frac{t^{j+1}}{(j+1)!}\frac{1}{d^{k}\cdots
d^{k-j}}=\frac{\mu_{k-j}(t)}{d^{k-j}},$ (49)

where $\mu_{k-j}(t)$ is given by (34).

Let $Y(k-j,j+1,t)=\sum Y_{w}$ be the number of exact paths from level $k-j$ to
$k$ at step $t$. There are $d^{k-j}$ choices for $w$, so
$\mathbb{E}\,Y\sim\mu_{k-j}(t)$. As $\mathbb{E}\,Y$ was obtained from
$\mathbb{E}\,X$ by dividing by $dd^{2}\cdots d^{j}$, we see that
$\mathbb{E}\,X=\mathbb{E}\,Yd^{j(j+1)/2}$.

Henceforth let $j=j^{*}-1$. The value $t_{1}(k-j^{*})$ from (39) satisfies
$\mu_{k-j^{*}}(t_{1})=1$. Using (40) we obtain that

$\mu_{k-j^{*}+1}(t_{1})=\Theta(d^{1/2}).$

As $\mathbb{E}\,Y(k-j^{*}+1,j^{*},t_{1}(k-j^{*}))\sim\mu_{k-j^{*}+1}(t_{1})$,
then
$\mathbb{E}\,X(k-j^{*}+1,j^{*}+1,t_{1}(k-j^{*}))=\Theta(d^{1/2+j^{*}(j^{*}-1)/2})$.
For $t\geq t_{1}$, w.h.p. $X\sim\mathbb{E}\,X(k-j^{*}+1,j^{*},t)$ by the
Chebychev inequality, see (46).

The events of exact path construction at vertices $w,w^{\prime}$ of any level
$k-j$ are independent, given exactly $j+1$ particles arrive at each of
$w,w^{\prime}$. As $\mathbb{E}\,Y(k-j^{*}+1,j^{*},t)\geq\Theta(d^{1/2})$ where
$d\rightarrow\infty$, then, for some small $\varepsilon>0$, w.h.p.
$(1-\varepsilon)\mathbb{E}\,Y\leq Y\leq(1+\varepsilon)\mathbb{E}\,Y$.
Conditional on this, $Y=\Theta(d^{1/2})$.

Finally consider that $\ell\geq j+2$ particles reach vertex $w$, so that the
path is not exact, as at least one other halted particle occupies the sub-tree
rooted at $w$. Let $Q(k-j,\ell,t)$ be the number of these events. Then
provided (44) holds, and $t\leq\omega T_{f}$

$\sum_{\ell\geq
j^{*}+1}\mathbb{E}\,Q(k-j^{*}+1,\ell,t)=\Theta(1)\frac{t}{d^{k-j^{*}+1}}\mathbb{E}\,Y=O(\omega)\sqrt{\frac{k}{d}}\;\mathbb{E}\,Y=o(\mathbb{E}\,Y).$

#### Lower and upper bounds on the finish time.

Lower bound on $t_{f}$. Let ${\cal E}(t)$ be the event that all levels from
level one to $k-j^{*}$ are empty at step $t$. If ${\cal E}(t)$ does not hold
then there must be a step $s\leq t$ when some vertex in level $k-j^{*}$
becomes occupied for the first time. This in turn can only occur after the
formation of the corresponding occupied path from level $k-j^{*}+1$ to level
$k$. Let $\,\mathbbm{1}_{\\{{s}\\}}$ be the indicator that ${\cal E}(s)$ fails
because a vertex in level $k-j^{*}$ becomes occupied at step $s$.

Let $t_{1}(k-j^{*})$ (from (39) of Section 4) be such that
$\mu_{k-j^{*}}(t_{1})=1$, and let $t^{\prime}=t_{1}/\omega$. Let $R(s)$ count
the occupied vertices in level $k-j^{*}+1$ at $s\leq t^{\prime}$, given ${\cal
E}(s)$ holds. Then for a given evolution of the process occupancy

$Z(t^{\prime})=\sum_{s\leq
t^{\prime}}\mathbb{P}(\,\mathbbm{1}_{\\{{s}\\}})\leq\sum_{s\leq
t^{\prime}}\frac{R(s-1)}{d^{k-j^{*}+1}}\leq
R(t^{\prime})\frac{t^{\prime}}{d^{k-j^{*}+1}}.$

We use (36), and the fact that $t_{1}=\Theta(T_{f})$ in (44) to evaluate
$\mu_{k-j^{*}+1}(t^{\prime})$. This gives

$\mu_{k-j^{*}+1}(t^{\prime})=(j^{*}+1)\frac{d^{k-j^{*}+1}}{t^{\prime}}\mu_{k-j^{*}}(t^{\prime})=O(1)\frac{d^{1/2}}{\omega^{j^{*}}}.$

Thus as $\mathbb{E}\,R(t^{\prime})=\mu_{k-j^{*}+1}(t^{\prime})$ we have

$\mathbb{E}\,(Z(t^{\prime}))\leq\mathbb{E}\,R(t^{\prime})\frac{t^{\prime}}{d^{k-j^{*}+1}}=\mu_{k-j^{*}+1}(t^{\prime})\frac{t_{1}}{\omega
d^{k-j^{*}+1}}=O(1)\frac{d^{1/2}}{\omega^{j^{*}}}\frac{\sqrt{k}}{\omega
d^{1/2}}=O\left(\frac{\sqrt{k}}{\omega^{\sqrt{2k+2}}}\right).$

As $\sqrt{k}\leq e^{\sqrt{k}}$ for any $k\geq 1$, then if
$\omega\rightarrow\infty$,

$\mathbb{P}(Z(t^{\prime})\geq 1)\leq
O\left(\frac{1}{\omega^{\sqrt{k}}}\right)\qquad\text{which
implies}\qquad\mathbb{P}({\cal E}(t^{\prime}))=1-o(1).$

Upper bound on $t_{f}$. At $t_{1}$, if ${\cal E}(t_{1})$ holds, level
$k-j^{*}$ is currently unoccupied. In which case there are $\Theta(d^{1/2})$
paths from $k-j^{*}+1$ to level $k$, of which $o(d^{1/2})$ are not exact. The
probability a given particle extends some exact path from level $k-j^{*}+1$ to
$k-j^{*}$ is order $d^{1/2}/d^{k-j^{*}+1}$. Let $T(\text{hit})$ be the time
for the first such extension to happen. Then

$\mathbb{E}\,T(\text{hit})=d^{k-j^{*}+1/2}=d^{k+3/2-\sqrt{2k+2}}=O(T_{f}).$

By analogy with the analysis in Section 4, w.h.p. this selected exact path of
occupied vertices from $k-j^{*}$ to $k$ will extend back to the source $v$, in

$T=O(d^{k-j^{*}})=O(d^{k+1-\sqrt{2k+2}})=O\left(\mathbb{E}\,T(\text{hit})/\sqrt{d}\right)$

expected steps; whereas the expected wait for a second exact path to extend to
level $k-j^{*}$ is $\mathbb{E}\,T(\text{hit})$. On the other hand, if ${\cal
E}(t_{1})$ does not hold, let $x$ be the first vertex in level $k-j^{*}$ to
become occupied. By the argument above, a path of occupied vertices would
extend back from $x$ to the source in $T$ expected steps. In either case
$t_{f}\leq\omega^{1/2}T\leq\omega T_{f}$ w.h.p. This completes the proof of
Theorem 1 for trees.

###  5.1 The finish time of DLA for trees with branching factor $d\geq 2$

######  Proposition 8.

Let For $d\geq 2$, let $G=G(n,d)$ be the Cayley tree with branching factor $d$
and height $k$, where $d^{k}=n$. Let $T=T(G)$ be given by

$T=\sqrt{k}d^{k+3/2-\sqrt{2k+2}}.$

Let $t_{f}$ be the finish time of DLA on $G$. Then w.h.p. $T/\omega\leq
t_{f}\leq\omega d^{1/2}T$.

###### Proof.

Upper bound. Let $j=j^{*}-h$ where $h=\lceil 1/2+1/2\log_{d}k\rceil$. In
Section 5 we assumed that $k\ll d$ so that $h=1$, but this may no longer be
the case. Note that $j$ is such that $d^{k-j}\geq T$ so that
$e^{-T/d^{k-j}}=\Theta(1)$ in the calculation of $\mathbb{E}\,Y$ (see (48) and
(49)).

At $T\sim t_{1}(k-j^{*})$ where $t_{1}$ is from (39) in the growing layers
model

$\frac{\mu_{k-j^{*}+h}}{\mu_{k-j^{*}}}=\Theta(1)2^{h/2}d^{h^{2}/2}.$

This ratio is $\omega(1)$, as either (i) $d\rightarrow\infty$, or (ii) $d$ is
constant and then $\log_{d}k=\log_{d}\log_{d}n$, implying that $h=\omega(1)$.
Either some path of halted particles already extends to a level $i$ where
$i<k-j^{*}+h$, or all vertices in these levels are unoccupied. In the latter
case, w.h.p. there exists a (not necessarily exact) path of length $j^{*}-h+1$
from this level to level $k$. Pick some longest occupied path $P(w)$ where $w$
is in level ${k-\ell}$, $\ell\geq j^{*}-h$. It takes at most

$\Theta(1)\frac{d^{k-j^{*}+h}}{2^{h}d^{h^{2}/2}}=T/\omega$

expected steps to extend $P(w)$ back to the source. Failing this either the
path from $v$ to $w$ is no longer open, so there is a longer occupied path
$P^{\prime}$, or some disjoint occupied path $P^{\prime\prime}$ has become
longer. Either way, w.h.p. the process halts in a further $\omega
d^{k-j*+h}=\omega d^{1/2}T$ steps.

Lower bound. Let $t=t_{1}/\omega$ where $t_{1}$ is given by (39). We prove
that at $t$, w.h.p. there does not exist a sub-tree rooted at a vertex $w$ in
level $k-j^{*}$ with a path of occupied vertices (exact or otherwise) from the
root $w$ to level $k$.

Given no vertex in level $i<k-j^{*}$ is occupied at step $t$, the distribution
of the number of particles arriving at $w$ up to and including step $t$ is
$p_{t}(w,\ell)$ as given by (45). It can be checked that $p_{t}(w,\ell)$ is
monotone increasing in $t$ provided $\ell\,d^{k-j}\geq t+1$. As $\ell\geq
j+1$, $j=j^{*}$, and $t=t_{1}/\omega$ this is equivalent to
$\sqrt{2}\gg\sqrt{d}/\omega$, which is true. Thus $p_{t}(w,\ell)$ is also an
upper bound if the path from $v$ to $\ell$ became blocked at some earlier
step.

Let $Y_{t}(\ell)$ be the number of occupied paths exact or otherwise from
vertices in level $k-j^{*}$ to level $k$ arising from $\ell$ particles
arriving at that vertex111In (45) we had $\ell=j+1$ and $j=j^{*}-1$.. Then
with $j=j^{*}$, $\mathbb{E}\,Y_{t}$ is upper bounded by

$\displaystyle\mathbb{E}\,Y\leq$ $\displaystyle\;\;\frac{d^{k-j}}{dd^{2}\cdots
d^{j}}\sum_{\ell\geq j+1}{t\choose\ell}{\ell\choose
j+1}\left(\frac{1}{d^{k-j}}\right)^{\ell}\left(1-\frac{1}{d^{k-j}}\right)^{t-\ell}$
$\displaystyle\leq$ $\displaystyle\;\frac{t^{j+1}}{(j+1)!d^{k-j+1}\cdots
d^{k}}e^{-t/d^{k-j}}\sum_{\ell\geq
j+1}\frac{1}{(\ell-(j+1))!}\left(\frac{t}{d^{k-j}}\right)^{\ell-(j+1)}$
$\displaystyle\sim$
$\displaystyle\;\;\mu_{k-j}(t)\;\;=\;\;\frac{\mu_{k-j}(t_{1})}{\omega^{j+1}}\;\;=O\left(\frac{1}{\omega^{\sqrt{2k+2}}}\right).$

The last line follows from $j^{*}+1=\sqrt{2k+2}$, see (38), $t=t_{1}/\omega$,
and the fact that $\mu_{k-j^{*}}(t_{1})=1$, see (39). Thus by the Markov
inequality, at $t$, w.h.p. no vertex in any level $i\leq k-j^{*}$ is occupied.
∎

#### Proof of of Corollary 2.

If $d$ is constant, $d^{k}=n$ implies $k=\Theta(\log n)$ and
$\sqrt{2k+2}=\sqrt{2k}+\Theta(1)$, and $d^{3/2}=\Theta(1)$. Thus $t_{1}$, $T$
are both $\Theta(T_{f})$, where $T_{f}$ is given in Corollary 2.

## References

  * [1] A. Asselah and A. Gaudilliere. Sub-logarithmic fluctuations for internal DLA. The Annals of Probability, 41(3), 1160-1179 (2013).
  * [2] R. C. Ball, D. A. Weitz, T. A. Witten, and F. Leyvraz. Universal kinetics in reaction-limited aggregation, Phys. Rev. Lett. 58, 274, (1987).
  * [3] P. Diaconis and W. Fulton. A growth model, a game, an algebra, lagrange inversion, and characteristic classes. Rend. Sem. Mat. Univ. Pol. Torino, 49(1):95–119, (1991).
  * [4] A. M. Frieze and W. Pegden. Diffusion limited aggregation on the Boolean lattice, Annals of Applied Probability Vol. 28(6), 3528–3557, (2018).
  * [5] M. B. Hastings and T. C. Halsey. High-dimensional diffusive growth, Europhys. Lett., 55(5), 679–-685 (2001).
  * [6] D. Jerison, L. Levine, and S. Sheffield. Logarithmic fluctuations for Internal DLA. Journal of the American Mathematical Society Vol. 25(1), pp. 271-301 (2012)
  * [7] H. Kesten. How long are the arms in DLA? Journal of Physics A: Mathematical and General, 20(1), L29–L33, (1987).
  * [8] G. F. Lawler, M. Bramson and D. Griffeath. Internal Diffusion Limited Aggregation, Ann. Probab. 20 (4) 2117–2140, (1992).
  * [9] G. F. Lawler. Subdiffusive fluctuations for internal diffusion limited aggregation. Ann. Probab., 23(1):71–86, (1995).
  * [10] P. Meakin and F. Family. Structure and dynamics of reaction-limited aggregation, Phys. Rev. A 36, 5498(R), (1987).
  * [11] T. A. Witten and L. M. Sander. Diffusion-limited aggregation, a kinetic critical phenomenon, Physics Review Letters, Vol. 47, No. 19, 1400–1403, (1981).
  * [12] T. A. Witten and L. M. Sander. Diffusion-limited aggregation, Phys. Rev. B 27, 5686–5697, (1983).