Internal DLA in a Random Environment

Gerard Ben Arous Department de Mathématiques Ecole Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland

Jeremy Quastel* Department of Mathematics and Statistics

University of Toronto, 100 St. George Street, Toronto, Ontario M5S 3G3, Canada

Alejandro F. Ramírez** Facultad de Matemáticas Pontificia Universidad Católica de Chile, Casilla 306-Correo 22, Santiago, Chile

Abstract. Internal DLA is studied with a random, homogeneous, distribution of traps. Particles are injected at the origin of a d-dimensional Euclidean lattice and perform independent random walks until they hit an unsaturated trap, at which time the particle dies and the trap becomes saturated. It is shown that the large scale effect of the randomness of the traps on the speed of growth of the set of saturated traps depends of the strength of the injection, and separates into several regimes. In the subcritical regime, the set of saturated traps is asymptotically a Euclidean ball whose radius is determined in a trivial way from the trap density. In the critical regime, there is a nontrivial interplay between the density of traps and the rate of growth of the ball. The supercritical regime is studied using order statistics for free random walks. This restricts us to d = 1. In the supercritical, subexponential regime, there is an overall effect of the traps, but their density does not affect the growth rate. Finally, in the supercritical, superexponential regime, the traps have no effect at all, and the asymptotics is governed by that of free random walks on the lattice.

0. Introduction

Internal DLA is a stochastic particle system in which traps are distributed on a ddimensional integer lattice, and particles are produced at the origin and move as independent random walks until they hit a trap, at which time the particle stops, and the trap becomes saturated.

The model arises in several applied problems, for example, nuclear waste management: Radioactive waste is placed in a container and buried, but, since even the best containers have some leakage, particles leave the container and as a rough approximation, perform independent random walks. In order to contain them, chemical traps are distributed around the area. When a radioactive particle hits a trap it is destroyed and the trap becomes saturated. Internal DLA also serves as a model for the behaviour of the chemical

* Partially supported by Natural Sciences and Engineering Research Council of Canada, and Alfred P. Sloan Foundation. ** Partially supported by Fundación Andes, DIPUC and Fondo Nacional de Desarrollo Científico y Tecnológico, grant 1990437. reaction A + B →Inert, in the special case where there is a source of A particles, and the B particles are fixed. It has also been used to model erosion processes, as well as melting processes, amoung others.

A basic problem in such a model is to understand the asymptotic shape and growth rate for the set of saturated traps. Fixing the rate of the walks, and the field of traps, we have as free parameter the rate of injection of particles at the origin. The way in which the growth rate is affected by the presence of the trap field depends on the rate of injection of particles at the origin. We identify four different regimes: Subcritical, critical, supercritical with subexponential injection, and supercritical with superexponential injection. The critical case is when N(t), the number of particles injected up to time t, is asymptotic to t^{d/2}, and the exponential case is when N(t) ∼ exp{ct}.

In the subcritical case, the asymptotic shape is a ball in any dimension. Asymptotically there is no density of live particles, and therefore the size of the ball can be determined easily: It has to contain as many traps as particles which have been injected, up to a negligible error. By the law of large numbers the volume of the ball is clearly N(t)/m where m is the mean number of traps per site, and the radius can be read off directly. Because the density of live particles is negligible, the model can be coupled to a discrete time version, as was done in [6]. The shape theorem follows from the analogous shape theorem for the discrete time case, following the methods of [6]. This was proved in [1].

In the critical case, the shape is still a ball in any dimension, but now there is a nontrivial density of live particles inside the ball. The boundary, and density of particles evolve together asymptotically according to a one-phase Stefan problem. This can be solved explicitly, yielding the shape and the rate of growth, which is a nontrivial function of the density of traps. This is proved here by an appropriate adaptation of the hydrodynamic limit method introduced in [4].

We also study here the supercritical case using order statistics. This restrict us to one dimension. Two regimes are identified. In the subexponential regime, there is still a net effect of the traps, but the density of traps plays no role. In the superexponential regime, the traps play no role at all and the speed of propagation is controlled by the range of free random walks. In dimensions greater than one, in the supercritical case, one expects similar results. However, here the shape will not be a sphere, but a certain level set of the rate function for large deviations of random walks on the lattice. This reflects the fact that as the strength of the injection is increased, the range of random walks becomes the dominant factor in the asymptotic shape and size of the saturated set. We do not prove it here, as we decided to use stress the application of order statistics: We study the n(t)th rightmost particle at time t in a system of random walks on the integer lattice, starting at the origin, at given times. Under quite general conditions it is shown that the asymptotics of this particle is governed by an appropriate transform of the large deviation rate function for a random walk on the lattice. This is then used to prove the asymptotics for the internal DLA model in the one dimensional supercritical case.

Section 1 contains a more precise description of the model, and the main results. We have stated these in the simplest cases in order to highlight the main point of the article which is the identification of the different regimes. In section 2 we explain how the methods of [GQ] need to be adapted in order to handle the random trap field in the critical case.

In Section 3 we state the main results about order statistics of random walks and from this obtain the asymptotics for internal DLA in the supercritical case in one dimension. Section 4 contains the technical proofs of the order statistics resuls.

1. Model and main results

We start with a field ζ of traps on Z^{d}. For each x ∈ Z^{d}, ζ_{x} ∈ {0, 1} denotes the absence or presence of a trap initially at x.

Particles are injected at the origin at times t_{1}, t_{2}, … and then perform independent continuous time random walks at rate 1. The rule is that the first particle which hits a trap stops moving.

The position at time t of the particle produced at time t_{n} will be denoted X_{n}(t). Sometimes it is convenient to use the convention that X_{n}(t) = 0 for 0 ≤ t ≤ t_{n}. Another way to describe the model is through the occupation number η_{x}(t) = ∑_{n} 1_{X_{n}(t)=x}, the number of particles at site x at time t. This includes the particles which have stopped moving, and clearly ξ_{x}(t) = (η_{x}(t) − ζ_{x})_{+} is the number of ‘live’ particles at x at time t, and

A_{t} = {x ∈ Z^{d} : ζ_{x} = 1, η_{x}(t) ≥ 1}

is the set of saturated traps. We will make a convention that the occupation number at 0 will not include particles which are not yet born, so at 0 we modify the definition to be η_{0}(t) = ∑_{n} 1_{X_{n}(t)=0,t≥t_{n}}.

Let N_{t} denote the number of particles created up to time t. We will call such an N_{t} an injection. For simplicity, in this article we will always take N_{t} to be deterministic, though it is certainly not necessary. For each field ζ of traps, and each injection N we have a process Y (t) = {X_{1}(t), X_{2}(t), …} which also has a reduced description η_{x}(t), x ∈ Z^{d}. We will denote the distribution of this process P_{ζ}.

In all cases we will assume that there is a positive density of traps – for simplicity we assume that ζ_{x}, x ∈ Z^{d} are independent, with P (ζ_{x} = 1) = m and P (ζ_{x} = 0) = 1 − m for some fixed m ∈ (0, 1].

Our main question is how the distribution of the traps affects the growth rate of the random set of saturated traps. We distinguish three cases, based on the strength of the injection: If t^{−d/2}N_{t} has a nontrivial limit as t → ∞ we say the model is critical, if t^{−d/2}N_{t} → 0 as t → ∞ we say the model is subcritical, and if t^{−d/2}N_{t} → ∞ as t → ∞ we say the model is supercritical.

In any dimension d, we denote by B(x, r) the Euclidean ball of radius r centered at x. Note that B(0, v^{1/d}a_{d}) has volume v, where a_{d} = dΓ(d/2)/2)^{1/d}/\sqrt{π}. Here Γ(·) is the Gamma function. We also use the notation a_{t} ≪ b_{t} when a_{t}/b_{t} → 0 as t → ∞.

We can now state our main results.

Theorem 1.1 . 1. In any dimension d, suppose that N_{t} ≪ t^{d/2}, so that we are in the subcritical case. Then,

A_{t} ∼ B(0, (N_{t}/m)^{1/d}a_{d})

in the sense that for any δ > 0, for almost every ζ, with P_{ζ} probability one, for sufficiently large t,

B(0, (1 − δ)(N_{t}/m)^{1/d}a_{d}) ∩ {ζ_{x} = 1} ⊂ A_{t} ⊂ B(0, (1 + δ)(N_{t}/m)^{1/d}a_{d}) ∩ {ζ_{x} = 1}.

2. In any dimension d, suppose that N_{t} = ⌊t^{d/2}⌋, the greatest integer less than or equal to t^{d/2}, so that we are in the critical case. Then

A_{t} ∼ B(0, K\sqrt{t})

where K is the unique solution of

Γ(d/2) exp{−K^{2}/4} = mπ^{d/2}K^{d}  (1.1)

in the sense that for almost every realization ζ of the trap field,

t^{−d/2}#[A_{t}△B(0, K\sqrt{t}a_{d}) ∩ \{ζ_{x} = 1\}] → 0,  (1.2)

in P_{ζ}-probability, where △ is the symmetric difference of sets, and # denotes the cardinality. Here Γ(α) = ∫_{0}^{∞} x^{α−1}e^{−x}dx is the Gamma function.

3. In dimension d = 1, suppose that either log N_{t} ≫ log t or that N_{t} = ⌊t^{α}⌋ for some α > 1/2 so that we are in the supercritical case. Furthermore, assume that there is a δ > 0 and a function f_{t} such that 1 ≪ f_{t} ≪ t and N(f_{t}) ≫ (log N_{t})^{1+δ}. Let

I(x) = sup_{λ∈R} \{λx − (cosh λ − 1)\} = x sinh^{−1} x − \sqrt{1 + x^{2}} + 1.  (1.3)

I : [0, ∞) → [0, ∞) is one to one and therefore has an inverse function I^{−1} : [0, ∞) → [0, ∞). If n_{t} is an increasing function define

w_{n_{·}}(t) = sup_{0≤y≤t}(t − y)I^{−1} (\frac{1}{t − y} log \frac{N_{y}}{n_{t}} )  (1.4)

Then

A_{t} ∼ B(0, w\sqrt{t}(t))

in the sense that if r_{t} and ℓ_{t} are the rightmost and leftmost particles, then

lim_{t→∞} r_{t}/w\sqrt{t}(t) = 1  and  lim_{t→∞} ℓ_{t}/w\sqrt{t}(t) = −1  (1.5)

in P_{ζ}-probability, for almost every realization ζ of the trap field.

Remarks. 1. The main conclusion is that the effect of the traps depends on the strength of the injection.

In case 1, where the injection is subcritical, the occupied set is approximately a ball of volume m^{−1}N_{t}, which by the law of large numbers contains approximately N_{t} traps. Essentially all the particles at time t have been trapped. The influence of the random trap field on the speed of growth is a fairly trivial averaging.

In case 2, where the injection is critical, the randomness in the trap field enters only through the mean on a large scale but has a nontrivial effect (1.1) on the speed of growth.

In case 3, where the injection is supercritical, the density m ∈ (0, 1] of traps does not enter at all. However from the asymptotics of w\sqrt{t}(t) one finds a transition at exponential injections. If log N_{t} ≪ t then for almost every trap configuration ζ, in P_{ζ}-probability,

lim_{t→∞} \frac{r_{t}}{sup_{0≤y≤t} \sqrt{2(t − y) log(N_{y}/t^{1/2})}} = 1.  (1.6)

If t ≪ log N_{t} then for almost every trap configuration ζ in P_{ζ}-probability,

lim_{t→∞} \frac{r_{t}}{sup_{0≤y≤t} log N_{y}/log (\frac{log N_{y}}{t−y} )} = 1.  (1.7)

One can check that the latter corresponds to the rightmost particle for free random walks with the same injection, but the former does not (the final denominator t^{1/2} would be absent.) Hence for subexponential injections, the traps slow down the growth rate in a way which does not depend on the density. For superexponential injections, there is no slowdown effect at all. Note however, that for free random walks in the entire supercritical regime one sees a transition from large to small density at the same scale as the boundary in the internal DLA.

2. The transition at exponential injections is also seen in the effect of the lattice. We can replace the random walks in our model by Brownian motions. The traps live at the integers, as before, and the first Brownian motion at a trap stops there forever. One can check that in that case the asymptotic in case 3 is always as in (1.6). Hence for injections much weaker than exponential large scale lattice effects are not seen, but for stronger than exponential injection rates, the lattice acts increasing the speed of growth. The simple point is that as the rate of injection becomes larger, one has to look farther into the tails of the distribution of the particles for the main contribution to the asymptotics.

3. The difference in the formulation of the shape results in the three different regimes reflects the different techniques used. The subcritical case 1 is proved in [1] using the methods of [6]. In this article we prove the critical and supercritical cases. The critical case is proved in section 3 using the method of [4] where the theorem was proved before in the special case ζ_{x} = 1 for all x ∈ Z^{d}. The supercritical case is proved in section 4 using order statistics. This complements the proof in [4] in the special case of one dimension with injection N_{t} = t and ζ_{x} = 1 for all x.

4. The conclusion of case 3 (in particular concerning r(t)) is valid for any distribution of traps satisfying lim inf_{n→∞} ∑_{x=0}^{n} ζ_{x} = m > 0 and does not depend on the randomness of the trap distribution.

5. Using the methods of [4] one can study a variant of the model where live particles have a zero-range interaction, in the critical and subcritical case (see [4,8]). Analogous results hold.

6. If more than one trap is allowed at each site the same results hold, with analogous proofs, with m = E[ζ_{x}]. It would be interesting to know what happens in the case m = ∞.

2. Critical Case

Recall the reduced description η_{x}(t) = ∑_{n} 1_{X_{n}(t)=x} of our process. Since the field of traps ζ_{x} is fixed throughout, the variable

ξ_{x}(t) = η_{x}(t) − ζ_{x}

together with the initial condition ξ_{x}(0) = −ζ_{x} gives a full description of our Markov process. For any local function f,

f(ξ(t)) − ∫_{0}^{t} Lf(ξ(s))ds − ∑_{{i:t_{i}≤t}}(f(ξ^{0,+}(t_{i})) − f(ξ(t_{i}))),  ()

is a martingale, where the Markov generator is

Lf(ξ) = ∑_{x,e}(ξ_{x})_{+}(f(ξ^{x,x+e}) − f(ξ)),

where e are unit vectors in the lattice, x are sites in Z^{d}, ξ^{x,x+e} denotes the configuration obtained from ξ by moving one particle from site x to site x + e, and ξ^{0,+} denotes the configuration obtained from ξ by adding one particle at 0,

ξ^{x,x+e} = ξ − δ_{x} + δ_{x+e}, ξ^{0,+} = ξ + δ_{0}.

For any real number x we use (x)_{+} or x_{+} to denote max(x, 0). The last term of () corresponds to the deterministic injection of particles, and 0 ≤ t_{1} < t_{2} < ⋯ are the times when particles are added; the jumps of ⌊t^{d/2}⌋.

Let ϵ be a small parameter and introduce macroscopic space and time variables x = ϵx and t = ϵ^{2}t in R^{d} and [0, ∞). The main result of this section is

Theorem 2.1 . For almost every realization ζ of the trap field, as ϵ → 0,

[ξ_{⌊ϵ^{−1}x⌋}(ϵ^{−2}t)]_{+} ⇀ ρ(x, t)  (2.1)

and

1_{ζ_{⌊ϵ^{−1}x⌋}>0,ξ_{⌊ϵ^{−1}x⌋}(ϵ^{−2}t)≥0} ⇀ m1_{s(x)≤t}  (2.2)

weakly in probability, where ρ(x, t) ≥ 0 and s(x) are the unique solutions of the one-phase Stefan problem

\{ \begin{matrix}\frac{∂ρ}{∂t} = Δρ + t^{(d−2)/2}δ_{0} & s(x) < t, \\ ρ = 0 & s(x) ≥ t, \\ ∇_{0}ρ · ∇s = −m & s(x) = t. \end{matrix}  (2.3)

Remarks. 1. The Stefan problem says that the expansion of the boundary is in the normal direction with velocity proportional to the density gradient ∇_{0}ρ taken from inside the region. The only large scale effect of the randomness of the traps is that this expansion is slowed down by a factor m = E[ζ_{x}].

2. The solution of (2.3) is given explicitly by ρ(x, t) = \frac{Γ(d/2)}{2π^{d/2}} ∫_{|x|/\sqrt{t}}^{K} s^{1−d}e^{−s^{2}/4} ds

and s(x) = K^{−2}|x|^{2} where Γ(d/2)e^{−K^{2}/4} = mπ^{d/2}K^{d}. Case 2 of Theorem 1.1 follows.

Theorem 2.1 is proved by suitably modifying the method of [4]. We indicate only the main steps and differences from the earlier proof and refer the reader to [4] when the proofs only require straightforward modifications.

1. Invariant measures. We consider the system without creation, i.e., with Markov generator L.

Lemma 2.2 . Let μ be any invariant measure for L. Then

μ( ∃ x, y ∈ Z^{d}, ξ_{x} > 0, ξ_{y} < 0) = 0.

Proof. It suffices to show that for arbitrary sites x and y, μ(ξ_{x} > 0, ξ_{y} < 0) = 0. We will prove it by induction on n, the lattice distance between x and y.

To start the induction let us take x and y to be nearest neighbour sites. Consider the function f = 1_{ξ_{y}<0}. Since f is a bounded local function and μ is an invariant measure we have E_{μ}[Lf] = 0. Now Lf = − ∑_{e}(ξ_{y+e})_{+}1_{ξ_{y}<0}. Since each term in the sum is nonnegative we have E_{μ}[(ξ_{x})_{+}1_{ξ_{y}<0}] = 0 which we rewrite as 0 = ∑_{k=1}^{∞} k_{+}μ(ξ_{x} = k, ξ_{y} < 0) = 0. This proves that μ(ξ_{x} > 0, ξ_{y} < 0) = 0.

Now suppose the statement holds for sites at distance n and let x be at distance n + 1 from y. Then there exists a site z of distance n from x and 1 from y. By the inductive hypothesis f = 1_{ξ_{z}>0,ξ_{x}<0} = 0 almost surely with respect to μ. Therefore for any lattice site u and unit e, L_{u,u+e}f = (ξ_{u})_{+}(f(ξ^{u,u+e}) − f(ξ)) ≥ 0 almost surely with respect to μ as well. However since f is a bounded local function and μ is invariant we have also E_{μ}[L_{0}f] = 0 and it follows that each L_{u,u+e}f = 0 almost surely with respect to μ. In particular, E_{μ}[L_{y,z}f] = 0, or

0 = E_{μ}[(ξ_{y})_{+}1_{ξ_{z}=0,ξ_{x}<0}] = ∑_{k=1}^{∞} k_{+}μ(ξ_{y} = k, ξ_{z} = 0, ξ_{x} < 0).

By the induction hypothesis, μ(ξ_{y} = k, ξ_{z} = 0, ξ_{x} < 0) = μ(ξ_{y} = k, ξ_{x} < 0). But then we must have μ(ξ_{y} = k, ξ_{x} < 0) = 0 for all k which completes the induction.

Corollary 2.3 . The set of extremal invariant measures for L consists of i. the Dirac mass on any configuration ξ with ξ_{x} ≤ 0 for all x ∈ Z^{d}, ii. product Poisson measures with density any ρ > 0.

Proof. All the measures in group i are clearly invariant. Suppose μ is some other extremal invariant measure. Then ξ_{x} > 0 for some x, and by the previous lemma, ξ_{x} ≥ 0 for all x, μ almost surely. Hence, L is the generator of independent random walks on the support of μ, and it therefore follows that μ must be an extremal invariant measure for independent random walks, which are known to be product Poisson measures [7].

2. Hydrodynamic limit. The H_{−1,ϵ} norm is defined on functions f : ϵZ^{d} → R of mean ϵ^{d} ∑_{x∈ϵZ^{d}} f_{x} = 0 by

∥f∥_{−1,ϵ}^{2} = sup_{ϕ} ϵ^{d} ∑_{x∈ϵZ^{d}} \{2f_{x}ϕ_{x} − \frac{1}{2}ϵ^{−2} ∑_{|e|=ϵ} |ϕ_{x+e} − ϕ_{x}|^{2}\} = ϵ^{2d} ∑_{x,y∈ϵZ^{d}} g_{y−x}^{ϵ}f_{x}f_{y} (2.4)

where g_{x}^{ϵ} = ϵ^{2} ∑_{n=0}^{∞} p_{x}^{n} in d ≥ 3 and g_{x}^{ϵ} = lim_{N→∞} ϵ^{2} ∑_{n=0}^{N} p_{x}^{n} − p_{0}^{n} in d = 1 or 2. Here p^{n} are the n step transition probabilities of a symmetric nearest neighbour discrete time random walk on ϵZ^{d}. Note that in [4] the factors ϵ^{2} are missing in the definition of g^{ϵ}.

We can observe our system on the lattice ϵZ^{d} by defining

ξ_{x}^{ϵ}(t) = ξ_{⌊ϵ^{−1}x⌋}(ϵ^{−2}t).

Lemma 2.4 . For almost every realization ζ of the traps, for each t ≥ 0, as ϵ → 0, ξ^{ϵ}(t) − ρ^{ϵ}(t) ⇀ 0 weakly, in probability, where ρ_{x}^{ϵ}(t), x ∈ ϵZ^{d}, t ≥ 0 is the solution of the lattice Stefan problem

\frac{∂ρ^{ϵ}}{∂t} = Δ_{ϵ}(ρ^{ϵ})_{+} + dP^{ϵ},  ρ^{ϵ}(t = 0) = −m.  (2.5)

Here Δ_{ϵ}ϕ_{x} = ϵ^{−2} ∑_{|e|=ϵ} ϕ_{x+e} − ϕ_{x} is the lattice Laplacian and ϵ^{2}P^{ϵ}(t) is the number of particles created in the microscopic system up to time t.

In Sections 2 and 4 of [4] it is explained in detail how part 2 of Theorem 1.1 follows from this lemma. The weak convergence (2.1) of the density field follows rather easily because the solution of (2.5) converges to the solution of (2.3) away from the creation points. However there is a fair amount of work to do to obtain the weak convergence (2.2) of the saturated set, as well as (1.2). This is done in [4].

Proof of lemma. Step 1. Fix a large time T. There is a finite B such that if the initial condition in (2.5) are replaced by ρ_{x}^{ϵ}(t = 0) = −ζ_{x} if |x| > BT and ρ_{x}^{ϵ}(t = 0) = −m if |x| ≤ BT then the solution remains the same up to time T (finite propagation speed). In the following we work with the modified initial conditions for ρ^{ϵ}.

Let q^{ϵ} be the solution of (2.5) with the initial condition changed to q^{ϵ}(t = 0) = −ζ everywhere. Note that ϵ^{d} ∑_{x∈ϵZ^{d}}[q_{x}^{ϵ} − ρ_{x}^{ϵ}] is constant in time and given by Z^{ϵ} = ϵ^{d} ∑_{|x|≤ϵ^{−1}BT}(m − ζ_{x}). Note that Z^{ϵ} = O(ϵ^{d/2}) and vanishes for almost every realization ζ of the traps, by the law of large numbers. Now the H_{−1,ϵ} norm of q^{ϵ} − ρ^{ϵ} − Z^{ϵ} makes sense and it is straightforward to check that

∥q^{ϵ} − ρ^{ϵ} − Z^{ϵ}∥_{−1,ϵ}^{2} |_{t=0}^{t=T} = − 2 ∫_{0}^{T} ∑_{x∈ϵZ^{d}}((q_{x}^{ϵ})_{+} − (ρ_{x}^{ϵ})_{+})(q_{x}^{ϵ} − ρ_{x}^{ϵ})dt

+ 2Z^{ϵ} ∫_{0}^{T} ∑_{x∈ϵZ^{d}}((q_{x}^{ϵ})_{+} − (ρ_{x}^{ϵ})_{+})dt.

The last integral is bounded uniformly in ϵ, for fixed T. Since Z^{ϵ} → 0, the last term goes to zero and we see that q^{ϵ} − ρ^{ϵ} tends weakly to 0. As in [4] it can be shown from this that q_{+}^{ϵ} converges strongly to the solution ρ of (2.3).

Step 2. By direct computation one shows that

∥ξ^{ϵ} − q^{ϵ}∥_{−1,ϵ}^{2} |_{t=0}^{t=T} = 2 ∫_{0}^{T} ϵ^{d} ∑_{x∈ϵZ^{d}} V (ξ_{x}^{ϵ}(t), q_{x}^{ϵ}(t))dt + M^{ϵ}(T)

where M^{ϵ}(T) is a martingale and

V (ξ, q) = −(ξ − q)(ξ_{+} − q_{+}) + ξ_{+}

Step 3. We cut off a small region around the creation site, as well as large values of V, and perform some time averaging using the strong convergence of ρ^{ϵ} to ρ , and the apriori smoothness of ρ away from 0. The result is that

E[∥ξ^{ϵ} − q^{ϵ}∥_{−1,ϵ}^{2}]|_{t=0}^{t=T} ≤2 ∫_{0}^{T} ∫_{|x|≥δ} E_{}_{μ̄_{x,t}^{ϵ,σ}}[V_{ℓ}(ξ_{0}, ρ(x, t))]dtdx + Ω(ϵ, ℓ, σ, δ)

where μ̄_{x,t}^{ϵ,σ} denotes the average over B_{σ}(t) = {, s ∈ [0, T] : |s − t| ≤ σ} of τ_{x}μ_{s} where μ_{s} is the distribution of ξ(s) and

lim sup_{δ↓0} lim sup_{σ↓0} lim sup_{ℓ↑∞} lim sup_{ϵ↓0} Ω(ϵ, ℓ, σ, δ) = 0.

Here

V_{ℓ}(ξ, ρ) = −ϕ_{ℓ}((ξ − ρ)(ξ_{+} − ρ_{+})) + ϕ_{ℓ}(ξ_{+})

where ϕ_{ℓ}(x) = x if x ≤ ℓ and ℓ otherwise. Finally one shows that the family μ̄_{x,t}^{ϵ,σ}, ϵ > 0 is tight.

Step 4. Let μ̄_{x,t}^{σ} be any weak limit of μ̄_{x,t}^{ϵ,σ} as ϵ → 0. Let f be any local function and |x| ≥ δ. Recall that L is the generator of the dynamics without creation, and σ is much smaller than δ. We have

E_{}_{μ̄_{x,t}^{σ}}[Lf] = lim_{ϵ→0} Av_{|s−t|≤σ}E[Lf(τ_{x}ξ_{s})].

The latter term can be written as the limit as ϵ → 0 of

|[t − σ, t + σ] ∩ [0, T]|^{−1} ∫_{[t−σ,t+σ]∩[0,T]} E[Lf(τ_{x}ξ_{s})]

By the definition of the generator this becomes,

ϵ^{2}|[t − σ, t + σ] ∩ [0, T]|^{−1}E[Av_{|y−x|≤σϵ^{−1}}f(τ_{y}ξ_{s})]|_{s=(t−σ)∧0}^{s=(t+σ)∨T}.

Note that τ_{y}f never depends on ξ_{0}, and therefore the creation part of the ξ dynamics does not appear in the last expression. Taking ϵ → 0 we obtain E_{}_{μ̄_{x,t}^{σ}}[Lf] = 0 for any bounded local f and therefore μ̄_{x,t}^{σ} is invariant for L.

Step 5. We arrive at

∫_{|x|≥δ} ∫_{0}^{T} ∫_{B} E_{μ_{β}}[V_{ℓ}(ξ_{0}, ρ(x, t)]Ψ_{x,t}(dβ)dtdx

where each Ψ_{x,t} is a probability measure on the parameter space B parametrizing the extremal invariant measures L. We let ℓ → ∞ and use the monotone convergence theorem to remove the cutoff ℓ on V. Since

E_{μ_{β}}[V (ξ_{0}, ρ)] ≤ 0

for any such μ_{β}, and any ρ, we have shown that E[∥ξ^{ϵ}(t) − q^{ϵ}(t)∥_{−1,ϵ}^{2}]|_{t=0}^{t=T} vanishes in the limit of small ϵ. Hence ξ^{ϵ} − q^{ϵ} tends to zero weakly in probability. From step 1, we know that for almost every realization ζ of the traps, q^{ϵ} − ρ^{ϵ} tend to zero weakly as well, and this completes the proof.

3. Asymptotics for order statistic of free random walks and supercritical IDLA in one dimension

In this section we state asymptotic estimates on the position of free random walks and use this to compute the size of supercritical IDLA in dimension d = 1.

We begin by defining an order statistics on a sequence of real numbers a_{1}, a_{2}, . . .. Let M ∈ N and a_{(1)}^{M} be the largest among the first M members of such sequence,

a_{(1)}^{M} = sup_{1≤n≤M}{a_{n}}

and recursively define the k-th largest a_{(k)}^{M} among the first M members of this sequence

a_{(k)}^{M} = sup_{1≤n≤M}{a_{n} : a_{n} ≠ a_{(j)}^{M} for 1 ≤ j ≤ k − 1}.

Let Y_{1}(t), Y_{2}(t), … be independent continuous time simple symmetric random walks on Z^{d} created at times t_{1}, t_{2}, … and jumping after that at rate 1. Let N_{t} = max{i : t_{i} ≤ t}. We can add a convention that Y_{n}(t) = 0 for 0 ≤ t ≤ t_{n}. Then, we have an order statistics on the first M born random walks at time t, given by {Y_{(k)}^{M}(t) : k ∈ N}. Similarly we have an order statistics on the rightmost positions attained by each random walk between time 0 and t, and denoted by {Ȳ_{(k)}^{M}(t) : k ∈ N}. The following asymptotics will be proved in Section 4.

Theorem 3.1 . Let n_{t} : [0, ∞) → N be increasing and assume that either log N_{t} ≫ log t or that N_{t} = ⌊t^{α}⌋ for some α > 1/2. Furthermore, assume that there is a δ > 0 and a function f_{t} such that 1 ≪ f_{t} ≪ t and N_{f_{t}} ≫ (log N_{t})^{1+δ} and that n_{t} ≤ C\sqrt{t} log N_{t}, for some constant C. Then i. In probability

lim_{t→∞} Y_{(n_{t})}^{N_{t}}(t)/w_{n_{·}}(t) ≥ 1.  (3.1)

ii. If we assume in addition that there is a β > 0 such that n_{t} ≪ t^{β}, then equality holds in (3.1). The theorem holds also if Y_{(n_{t})}^{N_{t}}(t) is replaced by Ȳ_{(n_{t})}^{N_{t}}(t).

Remarks. 1. The speed w_{n_{·}}(t) reflects an interplay on how the random walks Y_{i} affect the value of Y_{n_{t}}^{N_{t}}(t). At time s, N_{s} random walks have been born which by time t have evolved at least a time t − s. Suppose one wants to measure the effect of these N_{s} random walks on Y_{n_{t}}^{N_{t}}(t). For s small enough this effect should be negligible, since N_{s} → 0 when s → 0. On the other hand, if s is to close to t, there can be many random walks within the first N_{s} which evolved a time t − s, so that they do not contribute significantly to Y_{n_{t}}^{N_{t}}(t). The supremum in w_{n_{·}}(t) corresponds to choosing the optimal time s.

2. Most of the hypothesis of theorem 2 are of a more technical nature. The hypothesis log N_{t} ≫ log t or N_{t} = ⌊t^{α}⌋ is a restricition from the set of N’s such that N_{t} ≫ t^{1/2}, and basically discards injections that could oscillate between some polynomial injection and something much larger than a polynomial injection. The hypothesis concerning the function f_{t} such that 1 ≪ f_{t} ≪ t and N_{f_{t}} ≫ log N_{t} discards injections with a sudden big jump (for example N_{s} = O(e^{s}) for s ≤ t − 1/t and N_{t} = 0(e^{e^{s}})). These assumptions could be weakened, but we decided in favour of shorter proofs over the most general statements.

Proof of the lower bound of theorem 1. Here we prove that for almost every realization of the trap configuration ζ, in P_{ζ}-probability

lim_{t→∞} r_{t}/w\sqrt{t}(t) ≥ 1.  (3.2)

Note that r_{t} ≤ Ȳ_{(1)}(t). By theorem 2 part (ii) applied to the order statistics of the rightmost position Ȳ (t) in the time interval [0, t] of the random walks Y (t), with n_{t} = 1, for every ζ, in P_{ζ}-probability,

lim sup_{t→∞} r_{t}/w_{1}(t) ≤ 1.  (3.3)

By symmetry, the same statement holds for the (reflected) leftmost particle −l_{t}. The number of stopped random walks X_{i} at time t is given by ∑_{x=l(t)}^{r_{t}} ζ_{x}. Therefore if t is

sufficiently large, less than ∑_{x=−2w_{1}(t)}^{2w_{1}(t)} ζ_{x} ≤ 5w_{1}(t) random walks X_{i}(t) have been stopped. The smallest possible value of r_{t} then corresponds to stopping the rightmost 5w_{1}(t) random walks and hence for each ζ, in P_{ζ}-probability

lim sup_{t→∞} r_{t}/Y_{(⌊5w_{1}(t)⌋)}(t) ≥ 1.  (3.4)

Now w_{1}(t) ≤ C\sqrt{t} log N_{t}, for some C < ∞. Therefore, (1.5) together with an application of part (i) of theorem 2, this time with n_{t} = ⌊5w_{1}(t)⌋, shows that for every ζ, in P_{ζ}-probability

lim sup_{t→∞} r_{t}/w_{5w_{1}(·)}(t) ≥ 1.

The lower bound (3.2) now follows from the equality lim_{t→∞} w_{5w_{1}(·)}(t)/w\sqrt{t}(t) = 1, which is verified using the concavity property of the function I^{−1}(x) and considering separately the cases N_{t} = ⌊t^{α}⌋, α > 1/2, and log N_{t} ≫ log t.

Proof of the upper bound of theorem 1. First we claim that for each k ≥ 1,

r_{t} ≤ Ȳ_{(k)}(t) + M(k)  (3.5)

where M(k) represents the number of sites between Ȳ_{(k)}(t) and the position of the k −1-th trap strictly to the right of Ȳ_{(k)}(t).

Indeed for all j, X̄_{(j)}(t) ≤ Ȳ_{(j)}(t). Let us fix a t and renumber the particles according to their record values in [0, t]. More precisely, let n(j) be defined by X̄_{n(j)}(t) = X̄_{(j)}(t). Since X_{n(j)}(t) ≤ X̄_{n(j)}(t) we certainly have X_{n(j)}(t) ≤ Ȳ_{(j)}(t). Hence the only particles whose positions at time t could possibly be larger than Ȳ_{(k)}(t) are X_{n(1)}, …, X_{n(k−1)}. There are k − 1 such particles, so if one of them is stricly to the right of the (k − 1)th trap to the right of Ȳ_{(k)}(t), then by the pigeonhole principle one of the traps must be empty. Since there is a particle to the right of it, this contradicts the definition of the internal DLA dynamics. Hence (1.7) holds.

By the strong law of large numbers, for almost every realization of the trap configuration we have m = lim_{n→∞} \frac{1}{n} ∑_{x=1}^{n} ζ_{x} > 0. Therefore, for almost every realization of the trap configuration we have that M(k) ≤ \frac{2}{m}k, eventually in k. Choosing k = ⌊\sqrt{t}⌋ we can now conclude from (1.7) that for almost every realization of the trap configuration,

r_{t} ≤ Ȳ_{(⌊\sqrt{t}⌋)}(t) + \frac{2}{m}\sqrt{t},

eventually in t. By Theorem 2, for almost every realization of the trap configuration in P_{ζ}-probability, we have the upper bound lim_{t→∞} r_{t}/w\sqrt{t}(t) ≤ 1.

4. Asymptotics for order statistic of free random walks

In this section we prove Theorem 2. Although the methods are standard, we were unable to find relevant references in the literature. So complete proofs are included here. Our first step in section 4.1 will be to derive precise asymptotic estimates on the tail distribution of a continuous time symmetric simple random walk. In section 4.2 we will derive tail estimates on the order statistics of independent random walks born at the same time, and then on the right-most random walk from the set {Y_{i}(t) : 1 ≤ i ≤ N_{t}}. In section 4.3, we first derive the lower bound of part (i) of theorem 2. This is based in finding a time s for N_{s} independent random walks born at time s that maximizes their order statitics positions. Next, in section 4.3. we derive the upper bound of part (ii) of theorem 2. This will be an application of the estimates of section 4.2 analyzing separately the case log N_{t} ≫ log t and N_{t} = ⌊t^{α}⌋, with α > 1/2.

1. Asymptotics for a continuous time symmetric simple random walk. The main result of this subsection is Lemma 4.1.2 which gives the asymptotics for the tail distribution of a simple continuous time random walk. The result is standard in the sense that different versions of these estimates can be found in the literature, however, never in the particular form needed in this paper. Note in particular that in Lemma 4.1.2 the time α_{t} may even go to 0 as t → ∞.

Before we start we collect some basic information about the rate function (1.3).

Proposition 4.1 . i. I(x) is convex and I^{−1}(x) is concave. ii. I′(x) = sinh^{−1} x = log(x + \sqrt{1 + x^{2}}). iii. I^{−1}(x) ≥ \sqrt{2x}(1 − 4\sqrt{x})1_{x≤I(1/2)} + \frac{x}{3 log x}1_{x≥I(1/2)} ≥ \sqrt{x/2}. iv. I^{−1}(x) ≤ \sqrt{2x}(1 + \sqrt{x})1_{x≤I(1/2)} + 10x1_{x>I(1/2)}.

Proof. i and ii are clear. To prove iii, note that 1 + x^{2}/2 − x^{4}/8 ≤ \sqrt{1 + x^{2}} ≤ 1 + x^{2}/2, and log(1 + x) ≤ x. Therefore, I(x) ≤ x^{2}/2 + x^{3}/2 + x^{4}/8 ≤ x^{2}/2 + x^{4}, when x ≤ 1/2. Inverting this relationship we obtain the lower bound on I^{−1} for x ≤ I(1/2). For x ≥ 1/2, note that I(x) ≤ x log(6x). But the inverse of the function x log(6x) is larger than x/(6 log(x)) when x ≥ I(1/2). This finishes the proof of the lower bound. To prove iv, note that log(1 + x) ≥ x − x^{2}/2. Therefore, I(x) ≥ x log(1 + x) − \sqrt{1 + x^{2}} + 1 ≥ x(x − x^{2}/2) − x^{2}/2 ≥ x^{2}/2 − x^{3}/2 if x ≤ 1/2. Inverting we obtain the upper bound on I^{−1}(x) for x ≤ I(1/2). The large x upper bound is similar.

Lemma 4.2 . Let Z(t) be a continuous time symmetric simple random walk on Z, starting at the origin at time 0 and running at rate 1. Let α_{t}, β_{t} : [0, ∞) → (0, ∞) satisfy β_{t} ≫ 1 and β_{t} ≥ C\sqrt{α_{t} log(α_{t}^{2} + 1)} for some C > 0. Let a = (α^{2} + β^{2})^{1/4}. Then,

P (Z(α_{t}) ≥ β_{t}) = \frac{e^{−α_{t}I(β_{t}/α_{t})}}{\sqrt{2π} a_{t} (1 − e^{−I′(β_{t}/α_{t})})}[1 + R_{t}]

where |R_{t}| ≤ \frac{30}{C}(4 log a_{t})^{−1/6}.

Proof. We fix t and drop the subindex t on α and β temporarily. Let ν > 0 and n ∈ N be such that νn = α. For λ > 0, let V_{1}^{λ,ν}, V_{2}^{λ,ν}, …, be independent and identically distributed with P (V_{1}^{λ,ν} = k) = P (Z(ν) = k) exp{λk − ν(cosh λ − 1)} and S_{n}^{λ,ν} = ∑_{i=1}^{n} V_{i}^{λ,ν} so that for j ∈ Z,

P (Z(α) = j) = P (S_{n}^{0,ν} = j) = P (S_{n}^{λ,ν} = j) exp{−λj + α(cosh λ − 1)}.

The supremum in (1.3) is attained at λ = sinh^{−1} x so by 4.1 ii,

P (Z(α) = β + j) = P (S_{n}^{I′,ν} = β + j) exp{−jh − αI (β/α)}.  (4.1)

The characteristic function E[exp{iuS_{n}^{λ,ν}}] of S_{n}^{λ,ν} is given by

exp\{nν(cosh(λ + iu) − cosh λ)\} = exp \{α (iu sinh λ − \frac{1}{2}u^{2} cosh λ − \frac{1}{6}iu^{3} sinh λ + R_{u,λ})\} ,

where R_{u,λ} = \frac{1}{6} ∫_{γ}(z − λ)^{3} cosh z dz, the integral being taken over the contour γ = \{z ∈ C : z = λ + iy, 0 ≤ y ≤ u}. Since for z ∈ γ, | cosh z| ≤ cosh λ, we can write R_{u,λ} = (cosh λ)R_{1}(u), where |R_{1}(u)| ≤ u^{4}/24. By Fourier inversion, since α cosh I′ = a^{2},

P (S_{n}^{I′,ν} = β + j) = ∫_{−π}^{π} e^{−iuj} exp \{−\frac{1}{2}u^{2}a^{2} − \frac{1}{6}iu^{3}β + a^{2}R_{1}(u)\} \frac{du}{2π}.

After an elementary change of scale this becomes a^{−1} ∫_{−πa}^{πa} exp \{−ivj/a − \frac{1}{2}v^{2} + R_{2}(v)\} \frac{dv}{2π}, where R_{2}(v) = \frac{1}{6}iv^{3}βa^{−3} + O(v^{4}), and |O(v^{4})| ≤ \frac{1}{24}v^{4}a^{−2}. Substituting in equation (1.7), and summing over j we get that

P (Z(α) ≥ β) = \frac{1}{2πa}e^{−αI(β/α)} ∫_{−πa}^{πa}(1 − exp\{−I′ − iv/a\})^{−1}e^{− \frac{v^{2}}{2} +R_{2}(v)}dv  (4.2).

Let I_{1} denote the integration restricted to |v| ≤ (log a)^{1/3} and I_{2} the remainder. We now claim that if |v| ≤ (log a)^{1/3}, then

|\frac{1 − exp\{−I′\}}{1 − exp\{−I′ − iv/a\}} − 1| ≤ \frac{6}{C(log a)^{1/6}} .  (4.3)

In order to check this note that the left hand side is always bounded by \frac{v}{a} \frac{exp\{−I′\}}{|1−exp\{−I′−iv/a\}|}. We can bound the absolute value in the denominator below by (1 − exp{−1}) min(1, I′). So using 1−exp{−1} ≥ 1/3 and 4.1 ii and dropping a few terms, using (α+β)^{2} ≥ α^{2} +β^{2}, we see that the left hand side of (4.3) is bounded above by 3v\sqrt{α} a^{−2} max(1, 1/I′).

Now I′(β/α) ≥ log(1 + \frac{β}{α}). Note that for x ≥ 1/2, log(1 + x) ≥ log(3/2) and for 0 ≤ x ≤ 1/2, log(1 + x) ≥ x/2. Also 1/ log(3/2) ≤ 3. Hence we obtain an upper bound by replacing max(1, 1/I′) by max(3, 2α/β), or, since β ≥ C\sqrt{α log(1 + α^{2})}, by

max(3, 2C^{−1}\sqrt{α/ log(1 + α^{2})}). Now \sqrt{α/ log(1 + α^{2})}) ≤ \frac{(1+α^{2})^{1/4}}{(log(1+α^{2}))^{1/2}} ≤ \frac{(β^{2}+α^{2})^{1/4}}{(log(β^{2}+α^{2}))^{1/2}} .

Thus, for t large enough we have max(3, 2C^{−1}\sqrt{α/ log(1 + α^{2})}) ≤ 2\frac{(β^{2}+α^{2})^{1/4}}{C(log(β^{2}+α^{2}))^{1/2}} . This gives (4.3).

It is also not hard to check that if |v| ≤ (log a)^{1/3},

| exp{−v^{2}/2 + R_{2}(v)} − exp{−v^{2}/2}| ≤ 4a^{−1} log a,  (4.4)

and that

|\sqrt{2π} − ∫_{−(log a)^{1/3}}^{(log a)^{1/3}} exp\{−v^{2}/2\}dv| ≤ 2 exp\{−\frac{1}{2}(log a)^{2/3}\}.  (4.5)

Integrating (4.3), (4.4) and (4.5), we conclude that,

I_{1} = \frac{\sqrt{2π}}{1 − e^{−I′}} (1 + R_{3}(t)) ,  |R_{3}(t)| ≤ 20C^{−1}(log a)^{−1/6}.  (4.6)

On the other hand, we claim that

|(1 − exp\{−I′\})I_{2}| ≤ 8 exp\{−\frac{1}{12}(log a)^{2/3}\}.  (4.7)

In fact, first note that (1 − exp\{−I′\})I_{2} = ∫_{(log a)^{1/3}<|v|≤πa} |\frac{1−e^{−I′}}{1−e^{−I′−iv}} | e^{−v^{2}/2+R_{2}(v)}dv.

Now the term in absolute value is bounded by 1 and | exp R_{2}(v)| ≤ exp{v^{4}a^{−2}/24} so

|(1 − exp\{−I′\})I_{2}| ≤ ∫_{(log a)^{1/3}<|v|≤πa} e^{−v^{2}(\frac{1}{2} −(\frac{v}{a})^{2} \frac{1}{24})}dv. But, v/a ≤ π, so that the factor multiplying v^{2} in the exponent of this bound is larger than 1/2−π^{2}/24 ≥ 1/12. Hence, we get the bound |(1 − exp{−I′})I_{2}| ≤ ∫_{(log a)^{1/3}<|v|≤∞} e^{−v^{2}/12}dv, from which (4.7) follows.

Combining (4.6) and (4.7) with (4.2) gives a proof of the lemma.

2. Order statistics: independent identically distributed random walks. As discussed earlier, a main ingredient in the proof of theorem 2 will be to obtain asymptotic estimates on the order statistics of independent random walks born at the same time. Let M ∈ N and consider a set Z_{1}^{M}(t), Z_{2}^{M}(t), … of M independent continuous time random walks such that Z_{n}^{M}(0) = 0 for 1 ≤ n ≤ M. Consider the order statistics {Z_{(k)}^{M}(t) : k ∈ N} on this set of random walks at time t.

Proposition 4.3 . Let N_{t}, n_{t}, α_{t} : [0, ∞) → (0, ∞) be increasing functions. Assume that α_{t} ≤ t and that there is a 1 ≥ δ > 0 such that N_{t} ≫ t^{δ+ \frac{1}{2}} and n_{t} ≪ ⌊N_{t}⌋^{1−δ}. Furthermore, for −1 ≤ γ ≤ 1 define

Φ_{t}^{γ} = α_{t}I^{−1} (\frac{1 + γ}{α_{t}} log \frac{N_{t}}{n_{t}} )  (4.8)

and assume that N_{t}, n_{t} and α_{t} are such that Φ_{t}^{0} ≫ 1. Then, for every 1/2 ≥ ϵ > 0 for sufficiently large t,

i. P (Z_{(n_{t})}^{N_{t}}(α_{t}) ≥ Φ_{t}^{ϵ}) ≤ 8e^{2}N_{t}^{−δϵ/4}

ii. P (Z_{(n_{t})}^{N_{t}}(α_{t}) ≤ Φ_{t}^{−ϵ}) ≤ exp {−⌊N_{t}⌋^{δϵ/10}} .

Before proceeding with the proof of the proposition, we will need the following lemma, which states some properties of some expressions that will appear when applying the tail asymptotics of 4.2.

Lemma 4.4 . For −1/2 ≤ γ ≤ 1/2 let I^{−1}, α, Φ^{γ}, N_{t} and n_{t} be as in the previous proposition and define

r_{t}^{γ} = \sqrt{2π} (1 − exp \{−I′ (I^{−1} (Φ_{t}^{γ}))\}) (α_{t}^{2} + [Φ_{t}^{γ}]^{2})^{1/4},

Then r_{γ} is increasing in γ and for t large enough, i. \frac{1}{6} ≤ r_{t}^{−1/2} ≤ r_{t}^{1/2} ≤ 10t log N_{t},

ii. (\frac{N_{t}}{n_{t}} )^{γ} \frac{1}{r_{t}^{γ}} ≫ \frac{t^{δ/8}}{8 log t}.

Proof. The monotonicity can be checked directly. i. To prove the leftmost inequality,

by 4.1, r^{−1/2} = \sqrt{2π}^{\frac{I^{−1}+\sqrt{(I^{−1})^{2}+1}−1}{I^{−1}+\sqrt{(I^{−1})^{2}+1}}} (α^{2} + [Φ^{−1/2}]^{2})^{1/4}, where the argument of I^{−1}

is \frac{1}{2α} log(N/n), and this can be bounded below by \frac{(α)^{1/2}(I^{−1})^{3/2}}{(I^{−1}+\sqrt{(I^{−1})^{2}+1})}. For I^{−1} ≥ 1 and

t large enough this can be written as (Φ^{0})^{1/2} \frac{I^{−1}}{(I^{−1}+\sqrt{(I^{−1})^{2}+1})} ≥ 1 · \frac{1}{3}, where we have

used the hypothesis Φ_{t}^{0} ≫ 1. On the other hand, for I^{−1} < 1 we have the inequality \frac{α(I^{−1})^{2}}{\sqrt{αI^{−1}}} \frac{1}{I^{−1}+\sqrt{(I^{−1})^{2}+1}} ≥ \frac{1}{10}(log(N/n))^{1/2}, where we used 4.1.iii and 4.1.iv. This proves

that \frac{1}{3} ≤ r_{t}^{−1/2}. To prove the upper bound, note that since α_{t} ≤ t, we have that r_{t}^{1/2} ≤ 6(t + αI^{−1}). Now, by4.1.iv, we know that I^{−1} ≤ 10α^{−1} log N(t). Our upper bound now follows for t large enough.

ii. Since r_{t}^{γ} ≤ 10t log N_{t} for large t, if t satisfies N_{t} ≥ t^{log t}, the left hand side of ii is bounded below by t^{\frac{δγ log t}{4}} /10t(log t)^{2} which certainly dominates the right hand side of ii for large t. So we only need to consider the case N_{t} < t^{log t}. We divide it into two cases. If α_{t} ≥ (log t)^{3} and t is large enough then from the definition of r^{γ} it follows that r_{t}^{γ} ≤ 2I^{−1} (4(log t)^{2}/α_{t}) (α_{t}^{2} + [Φ_{t}^{γ}]^{2})^{1/4}. By 4.1.iv this can be bounded

by 4\sqrt{(4(log t)^{2}/α_{t})}(α_{t}^{2} + [Φ_{t}^{γ}]^{2})^{1/4} ≤ 4 log t (1 + [I^{−1} (4/ log t)]^{2})^{1/4}. This is bounded by 8 log t when t is large enough. On the other hand, if α_{t} < (log t)^{3}, we have r_{t}^{γ} ≤ 2((log t)^{3} + (log t)^{4})^{1/4} ≤ 8 log t. This concludes the proof of the lemma.

Proof of proposition 4.3. i. From the definition of the order statistics, for any s ≥ 0, x ≥ 0, and M, m ∈ N with m ≤ M,

P (Z_{(m)}^{M}(s) ≥ x) = ∑_{k=m}^{M} \binom{M}{k}P (Z(s) ≥ x)^{k} (1 − P (Z(s) ≥ x))^{M−k}.  (4.9)

We take M = N_{t}, m = n_{t}, s = α_{t} and x = Φ_{t}^{ϵ} and apply 4.2 with β_{t} = Φ_{t}^{ϵ}. We need to verify the hypothesis of that lemma. Since I^{−1} is increasing, Φ_{t}^{ϵ} ≥ Φ_{t}^{0} and by hypothesis Φ_{t}^{0} ≫ 1, so Φ_{t}^{ϵ} ≫ 1. By 4.2, Φ_{t}^{ϵ} ≥ Φ_{t}^{0} ≥ \frac{1}{\sqrt{2}} \sqrt{α_{t} log(N_{t}/n_{t})} and by our assumptions we have that for t large enough log(N/n) ≥ log N^{1−δ} ≥ log t^{1/4} so Φ_{t}^{0} ≥ \sqrt{α_{t} log t}/4\sqrt{2} ≥ \frac{1}{30} \sqrt{α_{t} log(α_{t}^{2} + 1)} for t large enough. So the hypothesis of 4.2 are satisfied.

Now we can apply 4.2 to (4.9). Then we use Stirling’s formula and N/[x(N −x)] ≤ 4/N on the binomial coefficients to get

P (Z_{(n_{t})}^{N_{t}}(α_{t}) ≥ Φ_{t}^{ϵ}) ≤ \frac{2e}{\sqrt{N_{t}}} ∑_{k=n_{t}}^{N_{t}} u_{k},  u_{k} = (\frac{a}{k} )^{k} (1 − \frac{k}{N_{t}} )^{k−N_{t}} b^{N_{t}−k}  (4.10)

where a = \frac{⌊n_{t}⌋^{1+ϵ}}{⌊N_{t}⌋^{ϵ}} \frac{1+R_{t}}{r_{t}^{ϵ}}, b = 1 − (\frac{n_{t}}{N_{t}} )^{1+ϵ} \frac{1+R_{t}}{r_{t}^{ϵ}} and |R_{t}| ≤ 30^{2}(log(α_{t}^{2} + [Φ_{t}^{0}]^{2}))^{−1/6}, which

goes to 0 by the hypothesis Φ_{t}^{0} ≫ 1. The function u is increasing for 0 < k ≤ a, decreasing for a ≤ k < N_{t}, so it attains a global maximum at k = a. Now a ≤ n (n/N)^{ϵ} (2/r^{ϵ}) ≤ 6n(n/N)^{ϵ} ≪ n, where in the second to last inequality we have applied 4.2. Since a ≪ n_{t}, the largest term in the summation of the right hand side of (4.10) corresponds to k = n_{t}. We now divide the sum in (4.10) in two parts: terms from k = n_{t} to k = max\{n_{t}, \sqrt{N_{t}}\} which we bound by max\{n_{t}, \sqrt{N_{t}}\}u_{n_{t}}, and terms from k = max\{n_{t}, \sqrt{N_{t}}\} to k = N_{t} which we bound by N_{t}u\sqrt{N_{t}}. Using (1 − x/N)^{x−N} ≤ e^{x}, we see that u_{n} ≤ (ea/n)^{n} and u\sqrt{N} ≤ (ea/\sqrt{N})^{\sqrt{N}}. Hence we can bound the sum in (4.10) by

2e\frac{max\{n_{t}, \sqrt{N_{t}}\}}{\sqrt{N_{t}}} ((\frac{n_{t}}{N_{t}} )^{ϵ} \frac{e(1 + R_{t})}{r_{t}^{ϵ}})^{n_{t}} + 2e\sqrt{N_{t}} ((\frac{1}{\sqrt{N_{t}}} )^{ϵ} \frac{e(1 + R_{t})}{r_{t}^{ϵ}})^{\sqrt{N_{t}}}

Now use |R_{t}| ≤ 1 and absorb the prefactor max\{n_{t}, \sqrt{N_{t}}\}/\sqrt{N_{t}} into a factor c^{n_{t}} and the prefactor \sqrt{N_{t}} into a factor c^{\sqrt{N_{t}}} to obtain that the left hand side of (4.10) is bounded by

4e ((\frac{n_{t}}{N_{t}} )^{ϵ} \frac{2e^{2}}{r_{t}^{ϵ}} )^{n_{t}} + 4e ((\frac{1}{\sqrt{N_{t}}} )^{ϵ} \frac{2e^{2}}{r_{t}^{ϵ}} )^{\sqrt{N_{t}}}

For t large, the first term dominates the second. Using the bound r_{t}^{ϵ} ≥ 1/6 proved in 4.2 we obtain i.

ii. We apply 4.2 to the analogue of (4.9) for P (Z_{(m)}^{M}(s) ≤ x) as in i. but with x = Φ_{t}^{−ϵ}, β_{t} = Φ_{t}^{−ϵ}. To apply the lemma we need to verify that for some C > 0 such that Φ_{t}^{−ϵ} ≥ C\sqrt{α_{t} log(α_{t}^{2} + 1)}. By the concavity of I^{−1} it follows that Φ_{t}^{−ϵ} ≥ (1−ϵ)Φ_{t}^{0}. So it is enough to show that Φ_{t}^{0} ≥ C\sqrt{α_{t} log(α_{t}^{2} + 1)} which is proved in the first paragraph of the proof i. Hence we can apply the lemma to obtain P (Z_{(n_{t})}^{N_{t}}(α_{t})) ≤ ∑_{k=0}^{n_{t}} \binom{N_{t}}{k}ρ^{k}(1 − ρ)^{N_{t}−k} where

ρ = (\frac{n_{t}}{N_{t}} )^{1−ϵ} \frac{1+R_{t}}{r_{t}^{−ϵ}} with |R_{t}| ≤ 50^{2}(2 log Φ_{t}^{0})^{−1/6}. Now \binom{N}{k} ≤ 2e(1 − \frac{k}{N} )^{k−N} (\frac{N}{k} )^{k} ≤

2e^{k+1} (\frac{N}{k} )^{k}.

Since |R_{t}| ≤ 2 and 1/r_{t}^{−ϵ} ≤ 6 for t sufficiently large, ρ ≤ 6 (n_{t}/N_{t})^{1−ϵ} ≤ 2. Also (1 − 1/x)^{−1} ≤ e^{2/x} whenever x ≥ 2 and hence (1 − ρ)^{−n_{t}} ≤ e^{6n_{t}(n_{t}/N_{t})^{1−ϵ}}.

Now (1 − 1/x) ≤ e^{−1/x} if x > 0, and therefore we also have (1 − ρ)^{N} ≤ e^{−n(\frac{N}{n})^{ϵ} \frac{1}{2r^{−ϵ}}}. For c > 0 the function f(x) = (\frac{c}{x})^{x} achieves its maximum at x = c/e. And the first term in the summation in (4.10) corresponds to f(x) with, c = en_{t}m_{t}(1 + R_{t}) where m_{t} = (\frac{N_{t}}{n_{t}} )^{ϵ} _{\frac{1}{r_{t}^{−ϵ}}}. By 4.2, c ≫ n_{t}. This implies that the maximum of the first factor in the

summation in (4.10) is attained at k = n_{t}. So for sufficiently large t, P (Z_{(n_{t})}^{N_{t}}(t) ≤ Φ_{t}^{ϵ}) ≤ 2en_{t} exp{n_{t}(1 − m_{t}/2 + log(2em_{t}))}. ii follows from this inequality using n_{t} ≤ exp n_{t} and 4.2.

3. Order statistics: rightmost random walk. We now state the second ingredient in the proof of theorem 2, a lower bound estimate on the position at time t of the rightmost random walk among the Y_{i}, 1 ≤ i ≤ N_{t}. For γ ∈ [−1, 1] define,

w_{n_{·}}^{γ}(t) = sup_{0≤y≤t}(t − y)I^{−1} (\frac{1 + γ}{t − y} log \frac{N_{y}}{n_{t}} ) ,  (4.11)

with the understanding that I^{−1}(x) = 0 if x < 0. Also, let g_{n_{·}}^{γ}(t) : [0, ∞) → [0, ∞) be the maximizer in (4.11) and define N_{n_{·}}^{γ}(t) = N_{g_{n·}^{γ} (t)}.

Proposition 4.5 . Let N_{t}, n_{t} : N → [0, ∞) be increasing functions such that for some δ > 0, ⌊N_{t}⌋^{1−δ} ≫ n_{t} and N_{t} ≫ t^{1/2+δ}. Then, for every 1 ≥ ϵ > 0, for sufficiently large t,

P (Y_{(1)}^{N_{t}}(t) > w_{1}^{ϵ}(t)) ≤ 4ϵ^{−1}(t log N_{t/2})^{−1/4}.

Proof. First note that for every x ≥ 0, P (Y_{(1)}^{N_{t}}(t) ≤ x) = ∏_{i=1}^{N_{t}} P (Z(t − T_{i}) ≤ x). We want to apply 4.2 to each multiplicand with α_{t} = t − t_{i} and β_{t} = w_{1}^{ϵ}(t). We need to verify that the hypothesis are satisfied. It is trivial to verify that w_{1,ϵ} ≫ 1. To show that there is a constant C such that w_{1}^{ϵ}(t) ≥ C\sqrt{(t − t_{i}) log((t − t_{i})^{2} + 1)} it is enough to verify that w_{1}^{ϵ}(t) ≥ C\sqrt{t log(t^{2} + 1)}. This is a consequence of the fact that w_{1}^{ϵ}(t) ≥ \frac{t}{2}I^{−1} (\frac{2}{t} log t^{δ/4}) (where we have used the assumptions ⌊N_{t}⌋^{1−δ} ≫ n_{t} and N_{t} ≫ t^{1/2+δ}) and the lower bound \sqrt{x/2} on the function I^{−1}(x) given in 4.1. Therefore,

P (Y_{(1)}^{N_{t}}(t) ≤ w_{1}^{ϵ}(t)) = ∏_{i=1}^{N_{t}} (1 − exp \{ − \frac{t − t_{i}}{v(t, t_{i})}I (\frac{w_{1}^{ϵ}(t)}{t − t_{i}}) \}(1 + R_{i,t}))  (4.12)

where

v(t, s) = \sqrt{2π}((t − s)^{2} + [w_{1}^{ϵ}(t)]^{2})^{1/4}(1 − exp\{−I′(w_{1}^{ϵ}(t)/(t − s)))

and |R_{i,t}| ≤ \frac{30}{C}(log w_{1}^{ϵ}(t))^{−1/6}. Using the definition of w_{1}^{ϵ}(t), we see that if u > 0, (t −

u)I (\frac{w_{1}^{ϵ}(t)}{t−u}) ≥ log⌊N_{u}⌋^{1+ϵ}. Using this in (4.12) and taking logarithms we get,

log P (Y_{(1)}^{N_{t}}(t) ≤ w_{1}^{ϵ}(t)) ≥ ∑_{i=1}^{N_{t}} log (1 − \frac{1 ∧ ⌊N_{t_{i}}⌋^{−(1+ϵ)}}{v(t, t_{i})} (1 + R_{i,t})) ≥ − ∑_{i=1}^{N_{t}} \frac{1 + R_{i,t}}{i^{1+ϵ}v(t, t_{i})}

(4.13)

In the last inequality we used N_{t_{i}} ≥ i. We want now to obtain a lower bound on the function v(t, t_{i}), uniform on i, to show that the rightmost hand side of (4.13) goes to

0. Using 4.1 ii, we see that v(t, s) ≥ \frac{w_{1,ϵ}((t−s)^{2}+w_{1,ϵ}^{2})^{1/4}}{w_{1,ϵ}+((t−s)^{2}+w_{1,ϵ}^{2})^{1/4}} . But for x and y positive, the

expression \frac{xy}{x+y} is increasing in x. Applying this to the previous inequality with y = w_{1}^{ϵ} and x decreasing from ((t − s)^{2} + [w_{1}^{ϵ}]^{2})^{1/4} to \sqrt{w_{1}^{ϵ}}, we see that v(t, s) ≥ \sqrt{w_{1}}/2. Also note that ∑_{i=1}^{N_{t}} \frac{1}{i^{1+ϵ}} ≤ 1 + ∫_{1}^{∞} \frac{1}{x^{1+ϵ}} dx ≤ \frac{2}{ϵ}, where in the last inequality we have used the hypothesis ϵ ≤ 1. Using these bounds together with the fact that |R_{i,t}| ≤ 1 for t large enough uniformly in i, we can conclude that for sufficiently large t,

log P (Y_{(1)}^{N_{t}}(t) ≤ w_{1,ϵ}(t)) ≥ −8ϵ^{−1}(w_{1}(t))^{−1/2},  (4.14)

Using the inequality w_{1}(t) ≥ \frac{t}{2}I^{−1} (\frac{2}{t} log N_{t/2}) and the lower bound I^{−1}(x) ≥ \sqrt{x/2}, we see that w_{1}(t) ≥ \frac{1}{2} \sqrt{t log N_{t/2}}. The proposition follows from this, the inequality 1−e^{−x} ≤ x for x ≥ 0 and (4.14).

Lemma 4.6 . Let N_{t}, n_{t} : [0, ∞) be increasing functions such that ⌊N_{t}⌋^{1−δ} ≫ n_{t}, for some δ > 0.

i. For every function f(t) = o(t) and κ > 0, we have N_{n_{·}}^{γ}(t) ≫ ⌊N_{f(t)}⌋^{1−κ}, ii. Assume that N_{t} = ⌊t^{α}⌋ for some α > 1/2. Then, t/(log t)^{2} ≪ g_{n_{·}}^{γ}(t) ≪ t(log t)^{−1/2}.

Proof. i. First note that for any function f(t) such that 0 ≤ f(t) ≤ t one has (t − g)I^{−1} (\frac{1+γ}{t−g} log \frac{N_{n·}^{γ}}{n} ) ≥ (t − f)I^{−1} (\frac{1+γ}{t−f} log \frac{N_{f}}{n} ), where g, n, N_{n_{·}}^{γ}, and f stand for g_{n_{·}}^{γ}(t), n_{t}, N_{n_{·}}^{γ}(t) and f(t), respectively. Therefore,

\frac{1 + γ}{t − g} log \frac{N_{n}^{γ}}{n} ≥ I((1 − \frac{f}{t} )I^{−1}(\frac{1 + γ}{t − f} log \frac{N_{f}}{n} )) ≥ \frac{1 + γ}{t − f} log \frac{N_{f}}{n} − R_{3,t},  (4.15)

where R_{3,t} = \frac{f}{t} I^{−1} (\frac{1+γ}{t−f} log \frac{N_{f}}{n} ) I′ (I^{−1} (\frac{1+γ}{t−f} log \frac{N_{f}}{n} )) and we have used the lower bound

I(y) ≥ I(x) − (x − y)I′(x) valid for 0 ≤ y ≤ x. We now claim that |R_{3}(t)| ≤ 2\frac{f}{t} \frac{1+γ}{t−f} log \frac{N_{f}}{n}. For this it is enough to prove that for y > 0, yI′(y) ≤ 2I(y) which can be checked directly. We can then conclude from (4.15) that, log \frac{N_{n·}^{γ} (t)}{n_{t}} ≥ (1 − \frac{g_{n·}^{γ} (t)}{t}) (1 − \frac{f(t)}{t}) log \frac{N_{f(t)})}{n_{t}}. Therefore if g_{n_{·}}^{γ}(t) < f(t), since f(t) = o(t), for every κ > 0 we have that, N_{n_{·}}^{γ}(t)/n_{t} ≫ (N_{f(t)}/n_{t})^{1−κ}. On the other hand if g_{n_{·}}^{γ}(t) ≥ f(t) there is nothing to prove since N_{n_{·}}^{γ}(t) = N_{g_{n·}^{γ} (t)} ≥ N_{f(t)}. This completes the proof of i.

ii. By 4.1 we have w_{n_{·}}^{γ}(t) ≥ \sqrt{\frac{t}{2} log N_{t/2}/n_{t}} for sufficiently large t. Since N_{t} = t^{α},

with α > 1/2 and n_{t} ≪ ⌊N_{t}⌋^{1−δ}, this implies that for some c > 0, for t large enough w_{n(·),γ}(t) ≥ c\sqrt{t log t}. We now claim that this implies

lim_{t→∞} \frac{log N_{n_{·}}^{γ}(t)/n_{t}}{t − g_{n_{·}}^{γ}(t)} = 0.  (4.16)

In fact, note that by the definition of N_{n_{·}}^{γ} and g_{n_{·}}^{γ}, the expression whose limit is taken in (4.16), is positive. Thus, if (4.16) is false, there is a subsequence t_{m} such that either log N_{n_{·}}^{γ}(t_{m})/n_{t_{m}} ∼ C(t_{m} − g_{n_{·}}^{γ}(t_{m})) for some C > 0 or log N_{n_{·}}^{γ}(t_{m})/n_{t_{m}} ≫ t_{m} − g_{n_{·}}^{γ}(t_{m}).

In this first case, this implies that for m large enough w_{n_{·}}^{γ}(t_{m}) ≤ \frac{2I^{−1}(C)}{C} log \frac{N_{n·}^{γ} (t_{m})}{n_{tm}} ≤

\frac{2I^{−1}(C)}{C}(log t_{m})^{2}, a contradiction. Similarly in the second case, using the upper bound I^{−1}(x) ≤ 10x for large x 4.1, , we would conclude that w_{n_{·}}^{γ}(t_{m}) ≪ (log t_{m})^{2}, a contradiction. This proves (4.16).

Now, from 4.3,

w_{n_{·}}^{γ}(t) = \sqrt{2(1 + γ)(t − g_{n_{·}}^{γ}(t)) log(⌊g_{n_{·}}^{γ}(t)⌋^{α}/n)} + R_{t},  (4.17)

where |R_{t}| ≤ 10(log t)^{2} and we used the assumption N_{t} = ⌊t^{α}⌋. One can check that for t large enough the supremum over y ∈ [0, t] of the function \sqrt{(t − y) log(⌊t^{α}⌋/n)} is achieved at some y = O(t/ log t) + o(t log t) and that the supremum itself is O(\sqrt{t log t}) ≫ R_{t}. Together with (4.17), this proves ii.

4. Proof of theorem 2. Proof of i. Step 1. Let ϵ > 0. First we check that N_{−ϵ,n}(t) ≫ ⌊n(t)⌋^{1+δ/4}, which will enable us to apply 4.3. Assume first that N(t) = t^{1/2+δ_{0}} for some δ_{0} > 0. Then, by (1.7), N_{−ϵ,n}(t) ≥ N_{t/(log t)^{2}} ≫ t^{1/2+δ_{0}/2}. On the other hand n_{t} ≤ \sqrt{t} log N_{t}. Therefore, N_{−ϵ,n}(t) ≫ n_{t}^{1/2+δ_{0}/4}. Choosing δ_{0} ≥ δ we have that N_{−ϵ,n}(t) ≫ ⌊n(t)⌋^{1+δ/4}. Now assume that log N_{t} ≫ log t. Then, for t large enough, by (1.7) applied with f(t) = t/ log t, we have that for any δ_{1} > 0, ⌊N_{−ϵ,n}(t)⌋^{δ_{1}} ≫ ⌊N_{t/ log t}⌋^{δ_{1}/2} ≫ t^{(1+δ_{1}/4)/2}. Now remark that by hypothesis, there is a function 1 ≪ f_{0}(t) ≪ t and a δ > 0 such that N_{f_{0}(t)} ≫ (log N_{t})^{1+δ}. By (1.7) with f(t) = f_{0}(t), we have N_{−ϵ,n}(t) ≫ ⌊N_{f_{0}(t)}⌋^{1−δ/2} ≫ (log N_{t})^{1+δ/2}. Thus, when log N_{t} ≫ log t, we have that N_{−ϵ,n}(t) ≫ (\sqrt{t} log N_{t})^{(1+δ/4)} ≫ n_{t}.

Step 2. If H_{t} = inf{y ≥ 0 : N_{y} = N_{n_{·}}^{−ϵ}(t)} is the first time that N_{n_{·}}^{−ϵ}(t) = N_{g^{ϵ}(t)} random walks have been born then we want to show that

P (Y^{N_{n·}^{−ϵ}(t)}(t) ≤ w_{n_{·}}^{−ϵ}(t)) ≤ P (Z^{N_{n·}^{−ϵ}(t)}(t − H_{t}) ≤ w_{n_{·}}^{−ϵ}(t).  (4.18)

Write M and n for N_{n_{·}}^{−ϵ}(t) and n_{t}, and note that P (Y_{(n)}^{N}(t) ≤ w_{n_{·}}^{−ϵ}(t)) = f_{M−n}(p_{1}, …, p_{M})

and P (Z_{(n)}^{N_{n·}^{−ϵ}}(t − H_{t}) ≤ w_{n_{·}}^{−ϵ}(t)) = f_{M−n}(q_{1}, …, q_{M}) with p_{i} = P (Y_{i}(t) ≤ w_{n_{·}}^{−ϵ}(t)) and q_{i} = P (Z_{i}(t − H_{t}) ≤ w_{n_{·}}^{−ϵ}(t)) for 1 ≤ i ≤ N. But for 1 ≤ i ≤ N the birth times t_{i} of the random walks Y_{i} have the property that t_{i} ≤ H_{t}. Thus, p_{i} = P (Y_{i}(t) ≤ w_{n_{·}}^{−ϵ}(t))

= P (Z_{i}(t − t_{i}) ≤ w_{n_{·}}^{−ϵ}(t)) ≤ P (Z_{i}(t − H_{t}) ≤ w_{n_{·}}^{−ϵ}(t)) = q_{i}. Note that f is a function of the form

f_{M}(p_{1}, …, p_{N}) = ∑_{n=M}^{N} ∑_{π∈Π(n)} p_{π_{1}} ⋯ p_{π_{n}}(1 − p_{π_{n+1}}) ⋯ (1 − p_{π_{N}}).  (4.19)

where Π(n) is the set of permutations of \{1, …, n\}. Any derivative is given by \frac{∂f_{M}}{∂p_{i}} = ∑_{π∈Π(i,M−1)} p_{π_{1}} ⋯ p_{π_{M−1}}(1 − p_{π_{M}}) ⋯ (1 − p_{π_{N−1}}) ≥ 0, where Π(i, M − 1) are the permutations of {1, …, i − 1, i + 1, …, N}. Hence f_{M−n}(p_{1}, …, p_{M}) ≤ f_{M−n}(q_{1}, …, q_{M}), which proves (4.18).

Step 3. Since n_{t}^{1+δ/2} ≪ N_{n_{·}}^{−ϵ}(t), we can apply 4.3 to the right hand side of (4.18), with α_{t} = t − g_{n_{·}}^{ϵ}(t). This, together with the fact that H_{t} ≤ g_{n_{·}}^{ϵ}(t) leads to the conclusion that for every ϵ > 0 for sufficiently large t, P (Y_{(n_{t})}^{N_{t}}(t) ≤ w_{n_{·}}^{−ϵ}(t)) ≤ exp{−t^{δϵ/20}}. Finally note that the concavity of the function I^{−1}(x), implies that w_{n_{·}}^{−ϵ}(t) ≥ (1 − ϵ)w_{n_{·}}(t). Thus, for every ϵ > 0 for sufficiently large t,

P (Y_{(n_{t})}^{N_{t}}(t) ≤ (1 − ϵ)w_{n_{·}}(t)) ≤ exp{−t^{ϵδ/20}},  (4.20)

This completes the proof of i.

Proof of ii. By i. it is enough to prove that in probability, lim_{t→∞} Y_{(n_{t})}^{N_{t}}/w_{n_{·}}(t) ≤ 1. To prove this we show that for every ϵ > 0, for sufficiently large t,

P (Y_{(n_{t})}^{N_{t}}(t) ≥ w_{n_{·}}^{ϵ}(t)) ≤ U_{t},  (4.21)

where U_{t} = \frac{2}{ϵ}(t log N_{t/2})^{−1/4} when log N_{t} ≫ log t and U_{t} = 80/⌊N_{t}⌋^{δϵ/8} when N_{t} = ⌊t^{α}⌋ with α > 1/2. Note that the concavity of the function I^{−1}(x) which gives us that w_{n_{·}}^{ϵ}(t) ≤

(1+ϵ)w_{n_{·}}(t), implies from (4.21) that for sufficiently large t, P (Y_{(n_{t})}^{N_{t}}(t) ≥ (1 + ϵ)w_{n_{·}}(t)) ≤ U_{t}.

Consider first the case log N_{t} ≫ log t. Note that Y_{(n_{t})}^{N_{t}}(t) ≤ Y_{(1)}^{N_{t}}(t). Since n_{t} ≤ t^{β}, by

(1.7), for sufficiently large t we have w_{1}^{ϵ/2}(t) ≤ w_{n_{·}}^{ϵ}(t). In fact, by the definitions of g_{1}^{ϵ} and N_{1}^{ϵ} we have that

w_{n_{·}}^{ϵ} ≥ (t − g_{1}^{ϵ})I^{−1}(\frac{1 + ϵ}{t − g_{1}^{ϵ}} log \frac{N_{1}^{ϵ}}{n} ) = (t − g_{1}^{ϵ})I^{−1}(\frac{1 + ϵ}{t − g_{1}^{ϵ}} log N_{1}^{ϵ}(1 − \frac{log n}{log N_{1}^{ϵ}} )). (4.22)

But by 4.6.i with f(t) = t/ log t, we have that N_{1}^{ϵ}(t) ≫ ⌊N_{t/ log t}⌋^{1/2} ≫ t^{\frac{u(t/ log t)}{4}} , where u(t) = log N_{t}/ log t ≫ 1. Therefore, since n_{t} ≪ t^{β}, we have \frac{log n}{log N_{1}^{ϵ}} = o(t). Combin-

ing this with (4.22), for sufficiently large t we have w_{1}^{ϵ/2}(t) ≤ w_{n_{·}}^{ϵ}(t). Using this we

can now conclude that if log N_{t} ≫ log t, for sufficiently large t, P (Y_{(n_{t})}^{N_{t}}(t) ≥ w_{n_{·}}^{ϵ}(t)) ≤

\frac{2}{ϵ}(t log N_{t/2})^{−1/4}.

We now analyze the case N_{t} = ⌊t^{α}⌋, α > 1/2. First note that by (1.7) for sufficiently large t, tI^{−1} (\frac{1+ϵ}{t} log \frac{N_{t}}{n_{t}} ) ≤ w_{n_{·}}^{2ϵ}(t). Therefore by 4.3, P (Z_{(n_{t})}^{N_{t}}(t) ≥ w_{n_{·}}^{ϵ}(t)) ≤ 80/⌊N_{t}⌋^{δϵ/8}. If P (Y_{(n)}^{N}(t) ≥ w_{n_{·}}^{ϵ}(t)) = 1 − f_{N−n}(p_{1}, …, p_{N}) and P (Z_{(n)}^{N}(t) ≥ w_{n_{·}}^{ϵ}(t)) = 1 − f_{N−n}(q_{1}, …, q_{N_{t}}) with p_{i} = P (Y_{i}(t) < w_{n_{·}}^{ϵ}(t)) ≥ q_{i} = P (Z_{i}(t) < w_{n(·}^{ϵ}(t)) for 1 ≤ i ≤ N. Thus f has the form (4.19) and hence f_{N−n}(p_{1}, …, p_{N}) ≥ f_{N−n}(q_{1}, …, q_{N}), or P (Y_{(n)}^{N}(t) ≥ w_{n_{·}}^{ϵ}(t)) ≤ P (Z_{(n)}^{N}(t) ≥ w_{n_{·}}^{ϵ}(t)) which gives P (Y_{(n_{t})}^{N_{t}}(t) ≥ w_{n_{·}}^{ϵ}(t)) ≤ 80⌊N_{t}⌋^{−δϵ/8}. This proves (4.21) and hence ii.

To extend this to Ȳ_{(n_{t})}^{N_{t}}(t), note that by the reflection principle the tail estimate for P (Z(t) ≥ x), changes by a factor of 2 if we replace Z by Z̄. Thus, all the results of section 3.2 remain valid, and the proof of ii is a repetition of the above argument.

Bibliography.

1. G. Ben Arous and A. F. Ramírez, Asymptotic Survival Probabilities in the Random Saturation Process, Ann. Probab. 28(4), 1470-1527 (2000) .

2. G. Ben Arous and A. F. Ramírez, Growth and saturation in random media, Stochastic Processes, Physics and Geometry: New Interplays. I: A Volume in Honor of Sergio Albeverio, F. Gesztesy, et. al., eds. AMS (2000).

3. S. Blachère, Agrégation limitée par diffusion interne sur Z^{d}, preprint.

4. J. Gravner and J. Quastel, Internal DLA and the Stefan problem, Ann. Probab. 28, No. 4 (2000) .

5. G. Lawler, Subdiffusive fluctuations for internal diffusion limited aggregation, Ann. Probab. 23 (1995), no. 1, 71–86.

6. G. Lawler, M. Bramson and D. Griffeath, Internal diffusion limited aggregation, Ann. Probab. 20, 2117-2140 (1992).

7. T.M. Liggett, Random invariant measures for Markov chains and independent particle systems, Z.Wahr. verw. Geb. 45 (1978), 297–313.

8. J. Quastel, Free boundary problem and hydrodynamic limit, in Hydrodynamic limits and related topics, S.Feng, A.T. Lawniczak, S.R.S. Varadhan, eds. American Mathematical Society (2000).