Large void zones and occupation times

for coalescing random walks

by

Endre Csáki^{1}, Pál Révész and Zhan Shi

Alfréd Rényi Institute of Mathematics, Technische Universität Wien & Université Paris VI

Summary. The basic coalescing random walk is a system of interacting particles. These particles start from every site of ℤ^{d}, and each moves independently as a continuous-time random walk. When two particles visit the same site, they coalesce into a single particle. We are interested in: (a) the radius R_{d}(T) of the largest ball centered at the origin which does not contain any particle at time T; and (b) the amount of time Λ_{d}(T) when the origin is occupied during [0, T]. We describe the almost sure asymptotic behaviours of R_{d}(T) and Λ_{d}(T) (when T → ∞), in three different regimes depending on whether d = 1, d = 2 or d ≥ 3.

Keywords. Coalescing random walk, void zone, occupation time.

2000 Mathematics Subject Classification. 60G50 60K35.

1Corresponding author

1 Introduction

We consider an elementary example of interacting particle systems: the basic model of coalescing random walk. Particles start at time t = 0 from every site of ℤ^{d}, and execute independent continuous-time simple random walks. Each particle jumps at the times of a rate one Poisson process, and when it jumps from position x ∈ ℤ^{d}, it jumps to any one of the (2d) neighbour sites of x with equal probability 1/(2d). The only interaction between the particles is when a particle jumps to a site which is already occupied by another particle: in this case, the two particles coalesce into one, which goes on to move as a continuous-time simple random walk.

It is known that there is a duality between the coalescing random walk and the linear voter model (Griffeath [13]).

For each x ∈ ℤ^{d}, let (ξ_{d}^{x}(t), t ≥ 0) denote the movement of the particle starting from position x. Let ξ_{d}(t) := {ξ_{d}^{x}(t), x ∈ ℤ^{d}}; it is the set of sites in ℤ^{d} which are occupied by a particle at time t.

In the present paper, we are interested in R_{d}(t), the radius of the largest ball centered at the origin which does not contain any site occupied by ξ_{d}(t), i.e.,

R_{d}(t) := inf_{x∈ξ_{d}(t)} ∥x∥,

where ∥x∥ denotes the Euclidean modulus of x ∈ ℤ^{d}.

The distributional behaviour of R_{d}(T) for large T is known. Indeed, Arratia [1] showed that ξ_{d}(T), suitably normalized, converges in distribution to a non-Poissonian point process for d = 1, and to a Poisson point process when d ≥ 2. Our aim is to study the almost sure asymptotic properties of R_{d}(T). Of course, since the origin is occupied infinitely often (this is clear for d = 1 or 2, and is a consequence of Theorem 1.3 below for d ≥ 3), it is meaningless to study the lim inf behaviour of R_{d}(T).

Theorem 1.1 We have

(1.1)  lim sup_{T →∞} \frac{R_{1}(T)}{(T log log T)^{1/2}} = 1,  a.s.,
(1.2)  c_{1} ≤ lim sup_{T →∞} \frac{R_{2}(T)}{T^{1/2}(log T)^{−1/2}(log log T)^{1/2}} ≤ c_{2},  a.s.,
(1.3)  c_{3} ≤ lim sup_{T →∞} \frac{R_{d}(T)}{(T log T)^{1/d}} ≤ c_{4},  a.s.,  d ≥ 3,

where c_{1}, c_{2}, c_{3} = c_{3}(d) and c_{4} = c_{4}(d) are finite positive constants.

In order to state our second theorem, we consider the occupation time defined by

Λ_{d}(T) := ∫_{0}^{T} 1_{{0∈ξ_{d}(t)}} dt, (1.4)

(1_{A} denoting the indicator of A). In words, Λ_{d}(T) stands for the total amount of time before T during which the origin is occupied by the coalescing random walk. Sometimes Λ_{d}(T) is also referred to as the local time at 0 of the random walk.

We recall what the “typical values” of Λ_{d}(T) are. Let

p_{d}(t) := ℙ{0 ∈ ξ_{d}(t)}, (1.5)

which denotes the probability that 0 (or any given site) is occupied by the coalescing walk at time t. By means of the duality with the voter model, Bramson and Griffeath [8] determined accurately the asymptotic behaviour of p_{d}(t).

Throughout the paper, we write a(t) ∼ b(t) (t → ∞) to denote lim_{t→∞} a(t)/b(t) = 1.

Fact 1.2 (Bramson and Griffeath [8]) Let p_{d}(t) be as in (1.5). As t → ∞,

(1.6)  p_{1}(t) ∼ \frac{1}{\sqrt{πt}},
(1.7)  p_{2}(t) ∼ \frac{log t}{2πt},
(1.8)  p_{d}(t) ∼ \frac{1}{γ_{d} t},  d ≥ 3,

where γ_{d}, d ≥ 3, denotes the probability that a d-dimensional simple symmetric random walk never returns to its starting point.

By Fubini’s theorem, 𝔼[ Λ_{d}(T) ] = ∫_{0}^{T} p_{d}(t) dt, from which it follows that, when T → ∞,

(1.9)  𝔼[ Λ_{1}(T) ] ∼ \frac{2\sqrt{T}}{\sqrt{π}} ,
(1.10)  𝔼[ Λ_{2}(T) ] ∼ \frac{(log T)^{2}}{4π} ,
(1.11)  𝔼[ Λ_{d}(T) ] ∼ \frac{log T}{γ_{d}} ,  d ≥ 3.

It is easy to determine the asymptotic behaviour of Λ_{1}(T). We have, almost surely Λ_{1}(T) = T^{(1/2)+o(1)} for T → ∞. Indeed, the lower bounds follows immediately by considering only a single particle (say the one starting from the origin), whereas the upper bound is a simple consequence of (1.9), Chebyshev’s inequality on taking a subsequence and applying the Borel–Cantelli lemma.

Our next result concerns the almost sure asymptotic behaviour of Λ_{d}(T) (for d ≥ 2), in the form of a law of large numbers.

Theorem 1.3 For d ≥ 2 we have

lim_{t→∞} \frac{Λ_{d}(T)}{𝔼[ Λ_{d}(T) ]} = 1, a.s. (1.12)

For an account of general properties of coalescing random walk, we refer to the books of Liggett [16] and [17], formulated in terms of the voter model. Other asymptotic properties of the occupation times of the voter model can be found in Cox and Griffeath [10], Bramson et al. [6]. Let us also mention a few recent papers. In van den Berg and Kesten [3]–[4], the exact asymptotic density of general coalescing random walks in high dimensions was determined. There is also an interesting relationship between the voter model and super-Brownian motion, recently discovered by Cox et al. [9] and Bramson et al. [7].

The rest of the paper is organized as follows. In Section 2, we prove probability estimates for coalescing random walks in any dimensions. These probability estimates will be used in the proof of the higher-dimensional parts — (1.2) and (1.3) — of Theorem 1.1 and in the proof of Theorem 1.3. More precisely, we prove in Section 3 the upper bounds in (1.2)–(1.3), and in Section 4 the corresponding lower bounds. In Section 5, we exploit some special onedimensional features to prove (1.1), and thus complete the proof of Theorem 1.1. Finally, Theorem 1.3 is proved in Section 6.

For any set A of ℤ^{d}, #(A) denotes the cardinality of A. The letter c with subscript denotes unimportant constants which are finite and positive.

2 Probability estimates for coalescing random walks

The main aim of the present section is to prove probability estimates (Propositions 2.1 and 2.2 below) for coalescing random walks in any dimensions. These estimates will be used in the next sections in the proof of (1.2), (1.3) and (1.12).

As before, ξ_{d}(t) denotes the set of all the sites which are occupied by the coalescing random walk at time t.

Here are the main probability estimates of the section.

Proposition 2.1 Let d ≥ 1, and let (a(x), x ∈ ℤ^{d}) be a collection of non-negative numbers such that ∑_{x∈ℤ^{d}} a(x) < ∞. For T > 0, let

ν_{T} := ∑_{x∈ξ_{d}(T)} a(x).

Then for any integer k ≥ 1,

𝔼{[ ν_{T} − 𝔼(ν_{T}) ]^{2k}} ≤ (2k)^{2k} ∑_{x∈ℤ^{d}} a^{2k}(x)p_{d}(T) + ( c_{5} k ∑_{x∈ℤ^{d}} a^{2}(x)p_{d}(T))^{k} , (2.1)

where c_{5} = c_{5}(d) ∈ (0, ∞) is a numerical constant, and p_{d}(T) is defined in (1.5).

Proposition 2.2 We have,

(2.2)  Var[Λ_{1}(T)] ≤ c_{6} T,  (T ≥ 1)
(2.3)  Var[Λ_{2}(T)] ≤ c_{7} (log T)^{3},  (T ≥ 2)
(2.4)  Var[Λ_{d}(T)] ≤ c_{8} log T,  d ≥ 3,  (T ≥ 2)

where c_{6}, c_{7} and c_{8} = c_{8}(d) are (finite) constants.

The estimate (2.2) for Var[Λ_{1}(T)] is not of any use. It is stated in Proposition 2.2 only for the sake of completeness.

The rest of the section is devoted to the proofs of Propositions 2.1 and 2.2, which rely on the van den Berg–Kesten–Reimer (BKR) correlation inequality. We however do not need in this paper the full strength of the BKR inequality, and state it here only for the special binary case.

Let V be a finite set and let Ω = {0, 1}^{V}. For ω ∈ Ω and K ⊂ V, let [ω]_{K} denote the set of all ω′ which agree with ω on K: ω′_{i} = ω_{i}, i ∈ K. For A, B ⊂ Ω, A□B is defined as the set of all ω ∈ Ω for which there exist disjoint K, L ⊂ V with [ω]_{K} ⊂ A, and [ω]_{L} ⊂ B. The BKR inequality is recalled as follows.

Fact 2.3 (van den Berg and Kesten [4], Reimer [19]) Let μ be a product measure on Ω. For any A, B ⊂ Ω,

μ(A □ B) ≤ μ(A)μ(B).

The BKR correlation inequality allows us to overcome some dependence difficulty in the study of coalescing random walks. Here is an application. We say that two ℝ-valued random variables X and Y are negatively dependent, if ℙ{X ≥ a, Y ≥ b} ≤ ℙ{X ≥ a} ℙ{Y ≥ b} for all real numbers a and b. In the literature, this negative dependence bears the more technical name of “negative upper orthant dependence” (Joag-Dev and Proschan [14]).

Lemma 2.4 Let d ≥ 1, and n ≥ 1. Let x_{1}, ⋯, x_{n} and y be distinct sites in ℤ^{d}, and let a_{1}, ⋯, a_{n} be non-negative numbers. Then for any T > 0, ∑_{i=1}^{n} a_{i}1_{{x_{i}∈ξ_{d}(T)}} and 1_{{y∈ξ_{d}(T)}} are negatively dependent.

Proof of Lemma 2.4. When n = 1, this was proved by Arratia [1] and is also a special case of Lemma 2.4 of van den Berg and Kesten [4], p. 8. In [4] the model of coalescing random walk is more general, than in the present paper. We outline the proof of our Lemma 2.4, following the same discretisation schema and proof of Lemma 2.4 of van den Berg and Kesten [4]. For each x ∈ ℤ^{d} and v ∈ ℤ^{d} with ∥x − v∥ = 1 consider a Poisson point process (in time) with intensity 1/(2d) and for each Poisson point draw an arrow from x to v. These Poisson processes are assumed to be independent of each other. Now the coalescing random walk can be described as follows: a particle starting from site x ∈ ℤ^{d} at time t = 0 stays in that position until there is an outgoing arrow from that position and jumps to the other endpoint of that arrow. It stays in this new position until there is an outgoing arrow from this new position and again jumps to the other endpoint of this arrow, etc. If two particles are in the same position at the same time, they stay together forever (they coalesce). Now for fixed T consider a partition [ℓδ, (ℓ + 1)δ) ℓ = 1, 2, …, k of [0, T] such that kδ = T. Consider the slight modification of the coalescing random walk in discrete time setting as follows. The particles postpone their jumps until the end of the time interval in which the corresponding arrow is located. Moreover, if the time interval has more than one outgoing arrow from a site in which a particle is located, the particle will stay in that location forever. For a fixed positive integer N such that ∥x_{i}∥ ≤ N, i = 1, ⋯, n, let X_{N} := {x ∈ ℤ^{d} : ∥x∥ ≤ 2N}. We define V := X_{N} × K × Q, where K := {1, 2, …, k} and Q := {v ∈ ℤ^{d}, ∥v∥ = 1}. For (z, ℓ, v) ∈ V let ω_{(z,ℓ,v)} = 1 if there is an outgoing arrow from z to z + v in the time interval [ℓδ, (ℓ + 1)δ) and ω_{z,ℓ,v} = 0 otherwise. We clearly have

ℙ\{ω_{z,ℓ,v} = 1\} = 1 − exp (−\frac{δ}{2d}) ,

and ω_{z,ℓ,v}, z ∈ X_{N}, ℓ ∈ K, v ∈ Q are i.i.d. random variables. Let ξ̃_{d}(T) be the set of occupied sites in this modified model. Fix a > 0 and let

A_{i} := {x_{i} ∈ ξ̃_{d}(T)},  i = 1, ⋯, n,
B := {y ∈ ξ̃_{d}(T)},
A := {∑_{i=1}^{n} a_{i}1_{{x_{i}∈ξ̃_{d}(T)}} ≥ a} ,

and let D be the event that for all x ∈ X_{N} and ℓ ∈ K there is at most one outgoing arrow from x in the interval [ℓδ, (ℓ + 1)δ). Since a_{1}, ⋯, a_{n} are non-negative, there exists J = J(a, a_{1}, ⋯, a_{n}), a set of subsets of {1, 2, ⋯, n} (depending on a and on a_{i}) such that

A = ⋃_{{j_{1},···,j_{k}}∈J}(A_{j_{1}} ∩ ⋯ ∩ A_{j_{k}}).

According to [4], pp. 9-10, there are sets Ã_{i}, i = 1, ⋯, n, B̃, which are union of cylinders, such that A_{i} ∩ D = Ã_{i} ∩ D and (A_{i} ∩ B ∩ D) ⊂ (Ã_{i} □ B̃), i = 1, ⋯, n. Therefore,

A ∩ B ∩ D = ⋃_{{j_{1},···,j_{k}}∈J} [(A_{j_{1}} ∩ B ∩ D) ∩ ⋯ ∩ (A_{j_{k}} ∩ B ∩ D)]
⊂ ⋃_{{j_{1},···,j_{k}}∈J} [(Ã_{j_{1}} □ B̃) ∩ ⋯ ∩ (Ã_{j_{k}} □ B̃)] .

The sites x_{1}, ⋯, x_{n} and y being distinct, we can choose a common L ⊂ V in the definition of Ã_{i} □ B̃ such that [ω]_{K_{i}} ⊂ Ã_{i}, and [ω]_{L} ⊂ B̃. Thus [(Ã_{j_{1}} □ B̃) ∩ ⋯ ∩ (Ã_{j_{k}} □ B̃)] ⊂ [(Ã_{j_{1}} ∩ ⋯ ∩ Ã_{j_{k}}) □ B̃]. Accordingly, by Lemma 3.1(iv) of van den Berg and Fiebig [2],

A ∩ B ∩ D ⊂ ⋃_{{j_{1},···,j_{k}}∈J} [(Ã_{j_{1}} ∩ ⋯ ∩ Ã_{j_{k}}) □ B̃]

⊂ [ ⋃_{{j_{1},···,j_{k}}∈J}(Ã_{j_{1}} ∩ ⋯ ∩ Ã_{j_{k}}) ] □ B̃
= Ã□ B̃,

where

Ã = ⋃_{{j_{1},···,j_{k}}∈J}(Ã_{j_{1}} ∩ ⋯ ∩ Ã_{j_{k}}).

By the BKR inequality (Fact 2.3), this implies

ℙ(A ∩ B) ≤ ℙ(Ã□ B̃) + ℙ(D^{c}) ≤ ℙ(Ã)ℙ(B̃) + ℙ(D^{c})
≤ (ℙ(A) + ℙ(D^{c}))(ℙ(B) + ℙ(D^{c})) + ℙ(D^{c}).

Now one can go back to infinitely many particles and continuous time case by letting δ → 0 and N → ∞ as in van den Berg and Kesten [4], p. 10. □

Lemma 2.5 Let d ≥ 1, n ≥ 1 and k ≥ 1. For any distinct sites x_{1}, ⋯, x_{n} in ℤ^{d}, and any non-negative numbers a_{1}, ⋯, a_{n}, we have

𝔼 {( ∑_{i=1}^{n} a_{i} [ 1_{{x_{i}∈ξ_{d}(T)}} − p_{d}(T)])^{2k} } ≤ 𝔼 {( ∑_{i=1}^{n} a_{i} [ Y_{i}(T) − p_{d}(T)])^{2k} } , (2.5)

where p_{d}(T) is defined in (1.5), and Y_{1}(T), ⋯, Y_{n}(T) are independent random variables such that for any i, Y_{i}(T) is distributed as 1_{{x_{i}∈ξ_{d}(T)}}.

Proof of Lemma 2.5. According to Theorem 2 of Shao [20], if X_{1} and X_{2} are negatively dependent such that 𝔼(|X_{1}|^{2k} + |X_{2}|^{2k}) < ∞, then

𝔼{(X_{1} + X_{2})^{2k}} ≤ 𝔼{(Y_{1} + Y_{2})^{2k}}, (2.6)

where Y_{1} and Y_{2} are independent random variables such that Y_{i} is distributed as X_{i} (for i = 1 and 2). We mention that Shao [20] proved (2.6) for negatively associated random variables, and that for a pair of random variables (which is the case here), the properties of negative association and negative dependence are equivalent (Joag-Dev and Proschan [14]).

If n = 1, (2.5) is trivial. For n ≥ 2, we note that according to Lemma 2.4, the random variables ∑_{i=1}^{n−1} a_{i}[ 1_{{x_{i}∈ξ_{d}(T)}} − p_{d}(T)] and a_{n}[ 1_{{x_{n}∈ξ_{d}(T)}} − p_{d}(T)] are negatively dependent. Therefore, Lemma 2.5 follows from (2.6) by induction. □

We now recall the well-known Rosenthal’s inequality (see for example Petrov [18], p. 59).

Fact 2.6 (Rosenthal’s inequality) Let k ≥ 1 be an integer, and let Z_{1}, ⋯, Z_{N} be independent mean-zero random variables such that 𝔼[ Z_{i}^{2k}] < ∞ for all i ≤ N. Then

𝔼 [( ∑_{i=1}^{N} Z_{i})^{2k} ] ≤ c_{9} ∑_{i=1}^{N} 𝔼[Z_{i}^{2k}] + c_{10} ( ∑_{i=1}^{N} 𝔼[Z_{i}^{2}] )^{k} , (2.7)

where c_{9} = c_{9}(k) and c_{10} = c_{10}(k) are finite constants whose values depend only on k.

In order to prove Proposition 2.1, we will need to know in (2.7) the dependence on k of the constants c_{9} and c_{10}. So let us recall a refined version of (2.7) in Petrov [18], p. 62, which states that (2.7) holds with c_{9} := r^{2k} and c_{10} := 2kr^{k}e^{r}B(k, r − k), for any r > k, where B is the beta function. Taking r = 2k, and (2.7) becomes:

𝔼 [( ∑_{i=1}^{N} Z_{i})^{2k} ] ≤ (2k)^{2k} ∑_{i=1}^{N} 𝔼[ Z_{i}^{2k}] + (c_{11} k)^{k} ( ∑_{i=1}^{N} 𝔼[ Z_{i}^{2} ] )^{k} , (2.8)

where c_{11} ∈ (0, ∞) is an absolute constant.

We have now all the ingredients to prove Proposition 2.1.

Proof of Proposition 2.1. Let A be a finite subset of ℤ^{d}, and consider the random variable ν_{T}^{A} := ∑_{x∈A} a(x)1_{{x∈ξ_{d}(T)}}. By Lemma 2.5 and (2.8), we have

𝔼{[ ν_{T}^{A} − 𝔼(ν_{T}^{A}) ]^{2k}} ≤ (2k)^{2k} ∑_{x∈A} a^{2k}(x) 𝔼 {[1_{{x∈ξ_{d}(T)}} − p_{d}(T)]^{2k}}

+(c_{11} k)^{k} ( ∑_{x∈A} a^{2}(x) 𝔼 {[1_{{x∈ξ_{d}(T)}} − p_{d}(T)]^{2}})^{k} .

Since 𝔼{ [ 1_{{x∈ξ_{d}(T)}} − p_{d}(T) ]^{2k} } ≤ 𝔼{ 1_{{x∈ξ_{d}(T)}} } = p_{d}(T), this implies

𝔼{[ ν_{T}^{A} − 𝔼(ν_{T}^{A}) ]^{2k}} ≤ (2k)^{2k} ∑_{x∈ℤ^{d}} a^{2k}(x)p_{d}(T) + (c_{11} k ∑_{x∈ℤ^{d}} a^{2}(x) p_{d}(T))^{k} .

Take A = A_{n} := {x ∈ ℤ^{d} : ∥x∥ ≤ n} and let n → ∞. The monotone convergence theorem ensures that 𝔼(ν_{T}^{A_{n}}) → 𝔼(ν_{T}). Therefore, we obtain the proposition by an application of Fatou’s lemma, with c_{5} := c_{11}. □

We now turn to the proof of Proposition 2.2. We first need a simple correlation result. Recall that ξ_{d}^{x}(t) denotes the position at time t of the particle starting from x.

Lemma 2.7 Let d ≥ 1. For t > s ≥ 0,

ℙ ( ⋃_{x∈ℤ^{d}} {ξ_{d}^{x}(s) = 0, ξ_{d}^{x}(t) ≠ 0, 0 ∈ ξ_{d}(t)}) ≤ p_{d}(s) p_{d}(t), (2.9)

where p_{d}(·) is defined in (1.5).

Proof of Lemma 2.7. Recall that in case n = 1 our Lemma 2.4 is equivalent to the inequality

ℙ ( ⋃_{x∈ℤ^{d}} {ξ_{d}^{x}(t) = y, 0 ∈ ξ_{d}(t)}) ≤ ℙ ( ⋃_{x∈ℤ^{d}} {ξ_{d}^{x}(t) = y}) ℙ {0 ∈ ξ_{d}(t)}

for y ≠ 0, the proof of which was given in Lemma 2.4 of van den Berg and Kesten [4], p. 8. The very same proof shows also that for s < t and y ≠ 0,

ℙ ( ⋃_{x∈ℤ^{d}} {ξ_{d}^{x}(s) = 0, ξ_{d}^{x}(t) = y, 0 ∈ ξ_{d}(t)})

≤ ℙ ( ⋃_{x∈ℤ^{d}} {ξ_{d}^{x}(s) = 0, ξ_{d}^{x}(t) = y}) ℙ {0 ∈ ξ_{d}(t)} .

Now (2.9) follows by summing over y ∈ ℤ^{d}\{0}. □

The section ends with the proof of Proposition 2.2.

Proof of Proposition 2.2. Observe that

𝔼{[Λ_{d}(T)]^{2}} = 2 ∫∫_{0≤t_{1}<t_{2}≤T} ℙ{0 ∈ ξ_{d}(t_{1}), 0 ∈ ξ_{d}(t_{2})} dt_{1} dt_{2}.

Moreover, for t_{1} < t_{2},

ℙ {0 ∈ ξ_{d}(t_{1}), 0 ∈ ξ_{d}(t_{2})} = ℙ {ξ_{d}^{x}(t_{1}) = ξ_{d}^{x}(t_{2}) = 0 for some x ∈ ℤ^{d}}
+ℙ {ξ_{d}^{x}(t_{1}) = 0 ≠ ξ_{d}^{x}(t_{2}) for some x ∈ ℤ^{d}, 0 ∈ ξ_{d}(t_{2})} .

Let q_{t}(0, 0) := ℙ{S_{d}^{0}(t) = 0}, where S_{d}^{0} denotes a continuous-time rate one random walk starting from 0 ∈ ℤ^{d}. (We have ignored the dependence of q_{t}(0, 0) in d.) Then

ℙ {ξ_{d}^{x}(t_{1}) = ξ_{d}^{x}(t_{2}) = 0 for some x ∈ ℤ^{d}} = p_{d}(t_{1}) q_{t_{2}−t_{1}}(0, 0),

whereas by Lemma 2.7,

ℙ {ξ_{d}^{x}(t_{1}) = 0 ≠ ξ_{d}^{x}(t_{2}) for some x ∈ ℤ^{d}, 0 ∈ ξ_{d}(t_{2})} ≤ p_{d}(t_{1}) p_{d}(t_{2}).

Therefore,

𝔼{[Λ_{d}(T)]^{2}} ≤ 2 ∫∫_{0≤t_{1}<t_{2}≤T} p_{d}(t_{1})q_{t_{2}−t_{1}}(0, 0) dt_{1} dt_{2} + ( ∫_{0}^{T} p_{d}(t) dt)^{2} ,

or, equivalently,

Var[Λ_{d}(T)] ≤ 2 ∫∫_{0≤t_{1}<t_{2}≤T} p_{d}(t_{1})q_{t_{2}−t_{1}}(0, 0) dt_{1} dt_{2}.

Now the proposition follows from Fact 1.2 and the well-known estimate q_{t}(0, 0) ≤ \frac{c_{12}}{(t+1)^{d/2}} (for any d ≥ 1 and some c_{12} = c_{12}(d)). □

3 Proof of (1.2) and (1.3): upper bounds

This section is devoted to the proof of the upper bounds in the higher-dimensional parts (d = 2 and d ≥ 3) of Theorem 1.1. We start with a preliminary estimate which holds in any dimension.

Lemma 3.1 Let d ≥ 1, and let A ∈ ℤ^{d} be a finite non-empty set. For any T > 0 and any integer k ≥ 1,

ℙ \{ A ∩ ξ_{d}(T) = ∅ \} ≤ \frac{(2k)^{2k}}{[ p_{d}(T) #(A) ]^{2k−1}} + \frac{(c_{5} k)^{k}}{[ p_{d}(T) #(A) ]^{k}} ,

where c_{5} is the numerical constant in (2.1), and p_{d}(T) is defined in (1.5).

Proof of Lemma 3.1. Write ν_{T} := #{A ∩ ξ_{d}(T)} = ∑_{x∈ξ_{d}(T)} 1_{{x∈A}}. Then { A ∩ ξ_{d}(T) = ∅ } = { ν_{T} = 0 }. Note that

𝔼(ν_{T}) = 𝔼 (∑_{x∈ℤ^{d}} 1_{{x∈A}} 1_{{x∈ξ_{d}(T)}}) = p_{d}(T) #(A).

By Chebyshev’s inequality,

ℙ {ν_{T} = 0} ≤ ℙ { |ν_{T} − 𝔼(ν_{T})| ≥ 𝔼(ν_{T})}
≤ \frac{𝔼 \{ [ ν_{T} − 𝔼(ν_{T}) ]^{2k}\}}{[ 𝔼(ν_{T}) ]^{2k}}
= \frac{𝔼 \{ [ ν_{T} − 𝔼(ν_{T}) ]^{2k}\}}{[ p_{d}(T) #(A) ]^{2k}}.

It suffices now to apply Proposition 2.1 to a(x) := 1_{{x∈A}}. □

Proof of (1.3): upper bound. Assume d ≥ 3. Let λ ≥ 1 be a constant whose value will be determined later on, and let

C_{d}(T) := {x ∈ ℤ^{d} : |x| ≤ (λT log T)^{1/d}} ,

where |x| := max_{1≤i≤d} |x^{(i)}| denotes the L^{∞}-norm of x := (x^{(1)}, ⋯, x^{(d)}) ∈ ℤ^{d}. In words, C(T) denotes the set of lattice points in the cube centered at the origin with side length 2⌊(λT log T)^{1/d}⌋.

Note that #(C_{d}(T)) ∼ 2^{d}λT log T (for T → ∞). On the other hand, according to (1.8), p_{d}(T) ∼ 1/(γ_{d}T), T → ∞. Thus, for all sufficiently large T (how large depending on d and λ),

p_{d}(T)#(C_{d}(T)) ≥ \frac{2^{d−1}λ}{γ_{d}} log T := c_{13} λ log T,

where c_{13} = c_{13}(d) := 2^{d−1}/γ_{d}. Applying Lemma 3.1 to A := C_{d}(T) and k := ⌊log T ⌋, we obtain that for large T,

ℙ \{ C_{d}(T) ∩ ξ_{d}(T) = ∅ \} ≤ \frac{(2k)^{2k}}{[ c_{13} λ log T ]^{2k−1}} + \frac{(c_{5} k)^{k}}{[ c_{13} λ log T ]^{k}}
= c_{13} λ(log T) (\frac{2k}{c_{13} λ log T} )^{2k} + (\frac{c_{5} k}{c_{13} λ log T} )^{k}
≤ c_{13} λ(log T) (\frac{2}{c_{13} λ})^{2k} + (\frac{c_{5}}{c_{13} λ})^{k}

We now choose the constant λ so large that \frac{2}{c_{13} λ} ≤ e^{−1} and \frac{c_{5}}{c_{13} λ} ≤ e^{−2}. Then for large T,

ℙ \{ C_{d}(T) ∩ ξ_{d}(T) = ∅ \} ≤ \frac{c_{13} λ log T + 1}{e^{2k}} ≤ \frac{(c_{13} λ log T + 1)e^{2}}{T^{2}} ,

the last inequality following from the fact that k ≥ log T − 1.

By the Borel–Cantelli lemma, almost surely for all large integer n, C_{d}(n) ∩ ξ_{d}(n) ≠ ∅. There exists thus at least a particle, say ξ_{d}^{x_{n}}(n), such that ξ_{d}^{x_{n}}(n) ∈ C_{d}(n). Since (ξ_{d}^{x_{n}}(n + t) − ξ_{d}^{x_{n}}(n), t ≥ 0) is a continuous-time random walk, we have

ℙ { sup_{t∈[0,1]} ∥ξ_{d}^{x_{n}}(n + t) − ξ_{d}^{x_{n}}(n)∥ ≥ (3 log n)^{1/2}}

= ℙ { sup_{t∈[0,1]} ∥ξ_{d}^{0}(t)∥ ≥ (3 log n)^{1/2}}
≤ \frac{1}{n^{3/2}} ,

for all large n. Therefore, sup_{t∈[0,1]} ∥ξ_{d}^{x_{n}}(n + t) − ξ_{d}^{x_{n}}(n)∥ ≤ (3 log n)^{1/2} almost surely. This implies that almost surely for all large T, there is at least a particle which lies in the cube centered at the origin with side length 2⌊(λT log T)^{1/d}⌋ + (3 log T)^{1/2}. As a consequence,

lim sup_{T →∞} \frac{R_{d}(T)}{(T log T)^{1/d}} ≤ d^{1/2}λ^{1/d}, a.s.,

yielding the upper bound in (1.3). □

Proof of (1.2): upper bound. The proof of the upper bound in (1.2) is along similar lines as in the case d ≥ 3, so let us outline the argument, and emphasize on the modifications. First, the size of the cube C_{d}(T) is changed: we should replace C_{d}(T) by C_{2}(T) := {x ∈ ℤ^{2} : |x| ≤ (λT)^{1/2}(log T)^{−1/2}(log log T)^{1/2}}. The reason for this change in the choice of C_{d}(T) is that the estimate p_{d}(T) ∼ 1/(γ_{d}T) for d ≥ 3 is now replaced by p_{2}(T) ∼ (log T)/(2πT), as stated in (1.7). For the new choice of C_{2}(T), we apply Proposition 2.1 to k := ⌊log log T ⌋ (instead of ⌊log T ⌋ in dimension d ≥ 3) to see that, if the constant λ > 0 is chosen sufficiently large, then for all large T,

ℙ \{C_{2}(T) ∩ ξ_{2}(T) = ∅\} ≤ \frac{c_{14} λ log log T}{(log T)^{4}} ,

where c_{14} ∈ (0, ∞) is a constant. Taking the subsequence T_{n} := exp(n^{1/3}) and applying the Borel–Cantelli lemma, this yields that almost surely for all large n, C_{2}(T_{n}) ∩ ξ_{2}(T_{n}) ≠ ∅. On the other hand, a Borel–Cantelli argument says that for large n, the increment size of a given particle during [T_{n}, T_{n+1}] cannot exceed (T_{n+1} − T_{n})^{1/2}(3 log n)^{1/2} (thus cannot exceed c_{15} T_{n}^{1/2}(log T_{n})^{−1}(log log T_{n})^{1/2} a fortiori, for some constant c_{15}). Consequently, almost surely for all large T, there is at least a particle lying in the cube centered at the origin with side length 2⌊(λT)^{1/2}(log T)^{−1/2}(log log T)^{1/2}⌋ + c_{15} T^{1/2}(log T)^{−1}(log log T)^{1/2}. This yields the upper bound in (1.2). □

Remark. The argument in this section of course applies also in dimension d = 1, and gives that

lim sup_{T →∞} \frac{R_{1}(T)}{T^{1/2} log log T} ≤ c_{16}, a.s.,

for some constant c_{16} > 0. However, this is a poor estimate, since by considering only the particle starting from the origin and using the usual iterated logarithm law, we know that lim sup_{T →∞} \frac{R_{1}(T)}{T^{1/2}(log log T)^{1/2}} ≤ 2^{1/2} almost surely. □

4 Proof of (1.2) and (1.3): lower bounds

To prove the lower bounds in (1.2) and (1.3), we first study a single particle (S_{d}^{x}(t), t ≥ 0) which is a continuous-time rate one random walk starting from x ∈ ℤ^{d}. We write q_{t}(x, y) for the probability density of the random walk: q_{t}(x, y) := ℙ{S_{d}^{x}(t) = y}.

For any non-empty subset A of ℤ^{d}, let diam(A) := sup{∥x − y∥ : x ∈ A, y ∈ A} denote the diameter of A, and let q_{t}(x, A) := ℙ{S_{d}^{x}(t) ∈ A}. We start with two preliminary estimates.

Lemma 4.1 Let d ≥ 1, and let A be a non-empty subset of ℤ^{d}. Let 0 < s < T be such that (T − s)^{1/2} ≥ diam(A). Then

ℙ {ξ_{d}(T) ∩ A = ∅ | F_{s}} ≥ exp {−c_{17} ∑_{x∈ξ_{d}(s)} q_{T −s}(x, A)} , a.s., (4.1)

where c_{17} = c_{17}(d) ∈ (0, ∞) is a constant depending only on d, and F_{s} := σ{ξ_{d}^{x}(t) t ∈ [0, s], x ∈ ℤ^{d}}.

Proof of Lemma 4.1. Consider the following modified model of particle system: until time s, it is our coalescing random walk (ξ_{d}^{x}(t); t ∈ [0, s]), and for t ∈ [s, T], the particles keep moving independently without coalescence. We denote by \overline{ξ}_{d}(T) (which of course depends on s) the set of all the sites which are occupied at time T by the new system of particles.

Without loss of generality, we make a coupling for the two models into a same probability space, so that \overline{ξ}_{d}(T) ⊃ ξ_{d}(T). Thus

ℙ \{ξ_{d}(T) ∩ A = ∅ | F_{s}\} ≥ ℙ \{ \overline{ξ}_{d}(T) ∩ A = ∅ | F_{s}\} . (4.2)

Given F_{s}, \overline{ξ}_{d}(T) is by definition the set of all the sites in ℤ^{d} occupied by independent random walks (without coalescence) at time (T − s) starting from every site of ξ_{d}(s). Accordingly,

ℙ \{ \overline{ξ}_{d}(T) ∩ A = ∅ | F_{s}\} = ∏_{x∈ξ_{d}(s)}[ 1 − q_{T −s}(x, A) ]. (4.3)

Since (T − s)^{1/2} ≥ diam(A), we have sup_{x∈ℤ^{d}} q_{T −s}(x, A) ≤ c_{18} < 1 for some constant c_{18} = c_{18}(d). As a consequence, there exists c_{19} = c_{19}(d) ∈ (0, ∞) such that 1 − q_{T −s}(x, A) ≥ exp{−c_{19} q_{T −s}(x, A)} for all x ∈ ℤ^{d}. Plugging this into (4.3) and (4.2) yields the lemma. □

Lemma 4.2 Let d ≥ 1, and let A be a subset of ℤ^{d} containing at least two points. Let u > 0 and v > 0, and let Ξ := ∑_{x∈ξ_{d}(v)} q_{u}(x, A). Then

𝔼(Ξ) = p_{d}(v) #(A). (4.4)

Furthermore, for any integer k ≥ 1,

𝔼 \{ [ Ξ − 𝔼(Ξ) ]^{2k} \} ≤ k^{2k}p_{d}(v) #(A) (c_{20} \frac{diam(A)}{u^{1/2}})^{2k−1}

+ (c_{20} k p_{d}(v) #(A) \frac{diam(A)}{u^{1/2}})^{k} , (4.5)

where c_{20} = c_{20}(d) ∈ (0, ∞) is a constant depending only on d.

Proof of Lemma 4.2. Since Ξ = ∑_{x∈ℤ^{d}} q_{u}(x, A) 1_{{x∈ξ_{d}(v)}}, it follows from Fubini’s theorem that

𝔼(Ξ) = ∑_{x∈ℤ^{d}} q_{u}(x, A) ℙ{x ∈ ξ_{d}(v)} = ∑_{x∈ℤ^{d}} q_{u}(x, A) p_{d}(v). (4.6)

By symmetry, q_{u}(x, y) = q_{u}(y, x), so that

∑_{x∈ℤ^{d}} q_{u}(x, A) = ∑_{x∈ℤ^{d}} ∑_{y∈A} q_{u}(x, y) = ∑_{y∈A} ∑_{x∈ℤ^{d}} q_{u}(y, x) = ∑_{y∈A} 1 = #(A), (4.7)

which, in view of (4.6), implies (4.4).

To check (4.5), we apply Proposition 2.1 to T := v and a(x) := q_{u}(x, A) to see that, for any integer k ≥ 1,

𝔼 { [ Ξ_{n} − 𝔼(Ξ_{n}) ]^{2k}} ≤ (2k)^{2k} ∑_{x∈A} q_{u}^{2k}(x, A) p_{d}(v) + ( c_{5} k ∑_{x∈A} q_{u}^{2}(x, A)p_{d}(v))^{k} .

For any b > 1, in view of (4.7), we have

∑_{x∈A} q_{u}^{b}(x, A) ≤ ( sup_{x∈ℤ^{d}} q_{u}^{b−1}(x, A)) ∑_{x∈ℤ^{d}} q_{u}(x, A) ≤ #(A) sup_{x∈ℤ^{d}} q_{u}^{b−1}(x, A).

Since sup_{x∈ℤ^{d}} q_{u}(x, A) ≤ c_{21} u^{−1/2}diam(A) for some c_{21} = c_{21}(d) ∈ (0, ∞), this yields (4.5), and completes the proof of Lemma 4.2. □

Proof of (1.3): lower bound. Assume d ≥ 3. Consider the subsequence T_{n} := n^{α}, where α > (d + 2)/(d − 2). Let C_{d}(T) := { x ∈ ℤ^{d} : |x| ≤ (λT log T)^{1/d} }. Here,

λ = λ(d, α) := \frac{γ_{d}}{2^{d+1}c_{17} α}, (4.8)

where c_{17} is the constant in (4.1). Let

A_{n} := { ξ_{d}(T_{n}) ∩ C_{d}(T_{n}) = ∅ } .

For each n, A_{n} is measurable with respect to F_{T_{n}}. If we could show that

∑_{n} ℙ { A_{n+1} | F_{T_{n}} } = ∞, a.s., (4.9)

then according to Lévy’s version of the Borel–Cantelli lemma (see for example Shiryaev [21], p. 486), we would have ℙ{A_{n} i.o. } = 1, which, in turn, would imply that for d ≥ 3,

lim sup_{T →∞} \frac{R_{d}(T)}{(T log T)^{1/d}} ≥ λ^{1/d}, a.s.

This would yield the lower bound in (1.3).

It remains to verify (4.9). Applying Lemma 4.1 to s := T_{n}, T := T_{n+1} and A := C_{d}(T_{n+1}) implies that, when n is sufficiently large (so that the condition (T − s)^{1/2} ≥ diam(A) is fulfilled; recalling that α > (d + 2)/(d − 2))

ℙ { A_{n+1} | F_{T_{n}} } ≥ exp {−c_{17} ∑_{x∈ξ_{d}(T_{n})} q_{T_{n+1}−T_{n}}(x, C_{d}(T_{n+1}))}
:= exp {−c_{17} Ξ_{n}} ,

with obvious notation. Applying Lemma 4.2 to u := T_{n+1} − T_{n}, v := T_{n}, A := C_{d}(T_{n+1}) and k = 1, and in light of Chebyshev’s inequality, we obtain:

ℙ \{ |Ξ_{n} − 𝔼(Ξ_{n})| > 𝔼(Ξ_{n}) \} ≤ \frac{Var(Ξ_{n})}{[ 𝔼(Ξ_{n}) ]^{2}} ≤ \frac{2c_{20} diam(C_{d}(T_{n+1}))}{(T_{n+1} − T_{n})^{1/2}p_{d}(T_{n}) #(C_{d}(T_{n+1}))}.

In view of (1.8), this yields

ℙ \{ |Ξ_{n} − 𝔼(Ξ_{n})| > 𝔼(Ξ_{n}) \} ≤ \frac{c_{22}}{n^{(α−1)/2−(α/d)}(log n)^{(d−1)/d}} .

Since (α − 1)/2 − (α/d) > 1 (recalling that α > (d + 2)/(d − 2)), the expression on the right hand side is summable in n. By the Borel–Cantelli lemma (and (4.4) for the expression of 𝔼(Ξ_{n})), almost surely for all large n,

Ξ_{n} ≤ 2𝔼(Ξ_{n}) = 2p_{d}(T_{n}) #(C_{d}(T_{n+1})) ∼ \frac{2^{d+1}αλ}{γ_{d}} log n.

Therefore, almost surely for all large n, Ξ_{n} ≤ (2^{d+2}αλ/γ_{d}) log n. Since ℙ{ A_{n+1} | F_{T_{n}} } ≥ exp{−c_{17} Ξ_{n} }, and in view of (4.8), we obtain:

∑_{n} ℙ { A_{n+1} | F_{T_{n}} } = ∞, a.s.

This yields (4.9), and completes the proof of the lower bound in (1.3). □

Proof of (1.2): lower bound. The proof of the lower bound in (1.2) follows similar lines as in the case of d ≥ 3. We feel free to write only an outline of the argument. Take T_{n} := e^{n}, and let C_{2}(T) := { x ∈ ℤ^{d} : |x| ≤ (λT)^{1/2}(log T)^{−1/2}(log log T)^{1/2} }. Consider A_{n} := { ξ_{d}(T_{n}) ∩ C_{d}(T_{n}) = ∅ }. Again, as in the case of d ≥ 3, we get via Lemma 4.1 that ℙ{ A_{n+1} | F_{T_{n}} } ≥ exp(−c_{17} Ξ_{n}), where Ξ_{n} := ∑_{x∈ξ_{d}(T_{n})} q_{T_{n+1}−T_{n}}(x, C_{d}(T_{n+1})). This time, we apply Lemma 4.2 to k = 3 to see that

ℙ \{ |Ξ_{n} − 𝔼(Ξ_{n})| > 𝔼(Ξ_{n}) \} ≤ \frac{𝔼\{ [ Ξ_{n} − 𝔼(Ξ_{n}) ]^{6}\}}{[ 𝔼(Ξ_{n}) ]^{6}} ≤ \frac{c_{23}(log n)^{9/2}}{n^{3/2}} ,

which is summable for n. The Borel–Cantelli lemma yields that almost surely for all large n, Ξ_{n} ≤ 2𝔼(Ξ_{n}) = 2p_{d}(T_{n})#(C_{d}(T_{n+1})) ∼ (4λe/π) log n. It is therefore possible to choose the constant λ > 0 to be so small that ∑_{n} exp(−c_{17} Ξ_{n}) = ∞ almost surely. This yields ∑_{n} ℙ{ A_{n+1} | F_{T_{n}} } = ∞ a.s., and implies the lower bound in (1.2). □

Remark. Applying Lemmas 4.1 and 4.2 in dimension d = 1 gives that

lim sup_{T →∞} \frac{R_{1}(T)}{T^{1/2}} ≥ c_{24}, a.s.,

for some constant c_{24} > 0. Again, this does not yield the optimal rate function for R_{1}(T), which should be (T log log T)^{1/2}. Therefore, the argument using Proposition 2.1 leads to the correct rate function for R_{d}(T) for all dimensions except for d = 1. Fortunately, in the next Section, we will use some special features in dimension d = 1 to obtain not only the correct rate function for R_{1}(T), but also the correct constant. □

5 Proof of Theorem 1.1: the one-dimensional case

In this section, we assume d = 1, and prove the one-dimensional part (i.e., identity (1.1)) in Theorem 1.1. In dimension d = 1, if ξ_{1}^{x} and ξ_{1}^{y} (particles starting from x and y, respectively) coalesce together before time T, then any particle whose starting position is between x and y also coalesces with them before time T. This special property will considerably simplify the study, and will allow us to obtain even the correct constant in the iterated logarithm law for R_{1}(T).

The proof of (1.1) is divided into two parts.

Proof of (1.1): upper bound. Fix δ ∈ (0, 1/2) and let

φ(t) = φ_{δ}(t) := \sqrt{(1 + 4δ)t log log t} ,
a_{k} = a_{k}(T) := k⌊δφ(T)⌋,  k = 0, 1, 2, ⋯

We first estimate ℙ{E(T)}, where

E(T) := ⋂_{k=0}^{N} {|ξ_{1}^{−a_{k}}(T)| > φ(T)} ∩ ⋂_{k=0}^{N} {|ξ_{1}^{a_{k}}(T)| > φ(T)}

with N := ⌊\frac{1}{δ}⌋. Clearly, \{R_{1}(T) > φ(T)\} ⊂ E(T).

By symmetry,

ℙ{E(T)} = 2ℙ {ξ_{1}^{0}(T) > φ(T), E(T)}
= 2ℙ {ξ_{1}^{0}(T) > φ(T), |ξ_{1}^{−a_{k}}(T)| > φ(T), ∀1 ≤ k ≤ N} .

It turns out to be more convenient to estimate ℙ{E(T)} in terms of independent random walks (without coalescence), instead of the original coalescing random walks (ξ_{1}(t), t ≥ 0).

Let (S_{1}^{x}(t) + x, t ≥ 0)_{x∈ℤ} be a family of independent (continuous-time) simple random walks with S_{1}^{x}(0) = 0. We will be working on the independent random walks (S_{1}^{x} +x)_{x∈ℤ^{d}} (without coalescence) instead of the original coalescing random walks (ξ_{1}(t), t ≥ 0).

Let I = I(T) := max{i ≥ 1 : S_{1}^{−a_{i}}(t) − a_{i} ≥ S_{1}^{0}(t) for some t ∈ [0, T]} + 1. In words, S_{1}^{−a_{I}} − a_{I} is the random walk starting from the largest point (among S_{1}^{−a_{i}} − a_{i}, i ≥ 1) which does not meet S_{1}^{0} during time interval [0, T]. We have

ℙ{E(T)} ≤ 2 ∑_{k=1}^{N} r_{k}(T) + 2ℙ {S_{1}^{0}(T) > φ(T), I > N} ,

where

r_{k}(T) := ℙ {S_{1}^{0}(T) > φ(T), I = k, |S_{1}^{−a_{k}}(T) − a_{k}| > φ(T)} .

It is easy to estimate ℙ{S_{1}^{0}(T) > φ(T), I > N}. Indeed, if I > N, then the random walks S_{1}^{−a_{N}} − a_{N} and S_{1}^{0} meet during [0, T], so that

ℙ {S_{1}^{0}(T) > φ(T), I > N} ≤ ℙ {S_{1}^{−a_{N}} (T) − a_{N} > φ(T)}
= ℙ {S_{1}^{0}(T) > a_{N} + φ(T)}
≤ exp (−(1 + o(1))\frac{(a_{N} + φ(T))^{2}}{2T} ) .

Therefore,

ℙ\{E(T)\} ≤ 2 ∑_{k=1}^{N} r_{k}(T) + 2 exp (−(1 + o(1))\frac{(a_{N} + φ(T))^{2}}{2T} ) .

We now estimate r_{k}(T) for 1 ≤ k ≤ N. The term r_{1}(T) is special. Indeed, if I = 1, then

r_{1}(T) ≤ ℙ {S_{1}^{0}(T) > φ(T), |S_{1}^{−a_{1}}(T) − a_{1}| > φ(T)}
= ℙ {S_{1}^{0}(T) > φ(T)} ℙ {|S_{1}^{−a_{1}}(T) − a_{1}| > φ(T)}
≤ exp (−(1 + o(1))\frac{(φ(T) − a_{1})^{2}}{T} ) .

Accordingly,

ℙ\{E(T)\} ≤ 2 ∑_{k=2}^{N} r_{k}(T) + 2 exp (−(1 + o(1))\frac{(φ(T) − a_{1})^{2}}{T} )

+2 exp (−(1 + o(1))\frac{(a_{N} + φ(T))^{2}}{2T} ) . (5.1)

To estimate r_{k}(T) for 2 ≤ k ≤ N, we note that if 2 ≤ I < ∞, then sup_{t∈[0,T]}[S_{1}^{−a_{j}}(t) − S_{1}^{0}(t)] ≥ a_{j} for all j ≤ I − 1. In particular,

r_{k}(T) ≤ ℙ {S_{1}^{0}(T) > φ(T), sup_{t∈[0,T]}[S_{1}^{−a_{k−1}}(t) − S_{1}^{0}(t)] ≥ a_{k−1}, |S_{1}^{−a_{k}}(T) − a_{k}| > φ(T)} .

Recall that S_{1}^{0}, S_{1}^{−a_{k−1}} and S_{1}^{−a_{k}} are three independent random walks on ℤ all starting from 0. So the probability of |S_{1}^{−a_{k}}(T) − a_{k}| > φ(T) can be splitted from the right hand side. It is easily seen that

ℙ {|S_{1}^{−a_{k}}(T) − a_{k}| > φ(T)} ≤ 2ℙ {S_{1}^{−a_{k}}(T) > φ(T) − a_{k}}
≤ 2 exp (−(1 + o(1))\frac{(φ(T) − a_{k})^{2}}{2T} ) .

Therefore, if we write X and Y for two independent random walks on ℤ both starting from 0, then

r_{k}(T) ≤ 2 exp (−(1 + o(1))\frac{(φ(T) − a_{k})^{2}}{2T} ) ×

×ℙ {X(T) > φ(T), sup_{t∈[0,T]}[Y (t) − X(t)] ≥ a_{k−1}}

(5.2)  := 2 exp (−(1 + o(1))\frac{(φ(T) − a_{k})^{2}}{2T} ) r̃_{k}(T),

with obvious notation.

Let us estimate r̃_{k}(T). According to a result of Csörgő et al. [11] (cf. also Csörgő and Horváth [12]), which is the continuous time version of the well-known Komlós–Major– Tusnády [15] approximation theorem, there exists a coupling for X and a standard Wiener process W such that

ℙ { sup_{t∈[0,T]} |X(t) − W (t)| ≥ A log T + x} ≤ B exp(−Cx),

for all T ≥ 1, x ≥ 0 and some constants A, B, C. From this we can conclude that

ℙ \{ sup_{t∈[0,T]} |X(t) − W (t)| ≥ T^{1/2}\} ≤ \frac{c_{25}}{T} ,

for all T ≥ 1 and some constant c_{25}. Similar result is true for Y (t) with another Wiener process, independent of W. Therefore, if W_{1} and W_{2} denote a pair of independent standard Wiener processes, then

r̃_{k}(T) ≤ ℙ \{W_{1}(T) > (1 + o(1))φ(T), sup_{t∈[0,T]}[W_{2}(t) − W_{1}(t)] ≥ (1 + o(1))a_{k−1}\} + \frac{c_{25}}{T}
:= ℙ \{W_{1}(T) > φ̃(T), sup_{t∈[0,T]}[W_{2}(t) − W_{1}(t)] ≥ ã_{k−1}\} + \frac{c_{25}}{T} ,

where we have written φ̃(T) := (1 + o(1))φ(T) and ã_{k−1} := (1 + o(1))a_{k−1} for brevity. Let B_{1} := (W_{2} − W_{1})/\sqrt{2} and B_{2} := (W_{2} + W_{1})/\sqrt{2}, so that B_{1} and B_{2} are also independent Wiener processes. Accordingly,

r̃_{k}(T) ≤ ℙ \{B_{2}(T) − B_{1}(T) > \sqrt{2} φ̃(T), sup_{t∈[0,T]} B_{1}(t) ≥ \frac{ã_{k−1}}{\sqrt{2}} \} + \frac{c_{25}}{T}
≤ ℙ \{B_{2}(T) + (2 sup_{t∈[0,T]} B_{1}(t) − B_{1}(T)) ≥ \sqrt{2} φ̃(T) + \sqrt{2} ã_{k−1}\} + \frac{c_{25}}{T}
= ℙ \{B_{2}(1) + (2 sup_{t∈[0,1]} B_{1}(t) − B_{1}(1)) ≥ \frac{\sqrt{2} (φ̃(T) + ã_{k−1})}{\sqrt{T}}\} + \frac{c_{25}}{T} .

The joint density of B_{1}(1) and sup_{t∈[0,1]} B_{1}(t) is known (cf., e.g., Borodin and Salminen [5], p. 147): ℙ\{B_{1}(1) ∈ dx, sup_{t∈[0,1]} B_{1}(t) ∈ dy\} = (\frac{2}{π})^{1/2}(2y − x) exp(−\frac{(2y−x)^{2}}{2} ) 1_{\{y>0, y>x\}}, from which we deduce that for λ → ∞,

ℙ \{2 sup_{t∈[0,1]} B_{1}(t) − B_{1}(1) > λ\} ≤ exp (−(1 + o(1))\frac{λ^{2}}{2} ) , λ → ∞.

(Alternatively, this can be proved by means of the fact that s ↦ 2 sup_{t∈[0,1]} B_{1}(s)−B_{1}(s), for s ≥ 0, is a three-dimensional Bessel process; that is, the Euclidean modulus of an ℝ^{3}-valued Wiener process.) On the other hand, we trivially have

ℙ \{B_{2}(1) > λ\} ≤ exp (−\frac{λ^{2}}{2} ) , ∀λ ≥ 0.

Since B_{2}(1) is independent of 2 sup_{t∈[0,1]} B_{1}(t) − B_{1}(1), it follows that

r̃_{k}(T) ≤ exp (−(1 + o(1))\frac{(φ̃(T) + ã_{k−1})^{2}}{2T} ) + \frac{c_{25}}{T}
≤ exp (−(1 + o(1))\frac{(φ(T) + a_{k−1})^{2}}{2T} ) .

In view of (5.2), we get that

r_{k}(T) ≤ 2 exp (−(1 + o(1))\frac{(φ(T) − a_{k})^{2}}{2T} − (1 + o(1))\frac{(φ(T) + a_{k−1})^{2}}{2T} )
≤ 2 exp (−(1 − δ + o(1))(1 + 4δ) log log T) .

Plugging this into (5.1), and we obtain that for all large T,

ℙ\{E(T)\} ≤ \frac{1}{(log T)^{1+2δ}} . (5.3)

This is the main probability estimate we need in the proof of the upper bound for (1.1).

To complete the proof of the upper bound in question, we consider the subsequence T_{n} := exp(n^{1−δ}). According to (5.3), ∑_{n} ℙ{E(T_{n})} < ∞, so that by the Borel–Cantelli lemma, almost surely for all large n,

min_{k: 0≤k≤N} {|ξ_{1}^{−a_{k}}(T_{n})| ∧ |ξ_{1}^{−a_{k}}(T_{n})|} ≤ φ(T_{n}), (5.4)

with the usual notation a ∧ b := min{a, b}. On the other hand, by the usual estimate for Gaussian tails,

ℙ { max_{k: 0≤k≤N} sup_{T ∈[T_{n},T_{n+1}]} {|ξ_{1}^{−a_{k}}(T) − ξ_{1}^{−a_{k}}(T_{n})| ∨ |ξ_{1}^{a_{k}}(T) − ξ_{1}^{a_{k}}(T_{n})|} > δφ(T_{n})}

≤ 2(N + 1)ℙ { sup_{s∈[0,T_{n+1}−T_{n}]} |ξ_{1}^{0}(s)| > δφ(T_{n})}
≤ 2(N + 1) exp (−\frac{δ^{2}φ^{2}(T_{n})}{2(T_{n+1} − T_{n})}) ,

which is summable for n, so that by the Borel–Cantelli lemma, almost surely for all large n, all k ≤ N and all T ∈ [T_{n}, T_{n+1}], we have |ξ_{1}^{−a_{k}}(T)−ξ_{1}^{−a_{k}}(T_{n})| ≤ δφ(T_{n}) and |ξ_{1}^{a_{k}}(T)−ξ_{1}^{a_{k}}(T_{n})| ≤ δφ(T_{n}).

In view of (5.4), we deduce that almost surely for all large T,

min_{k: 0≤k≤N} {|ξ_{1}^{−a_{k}}(T)| ∧ |ξ_{1}^{−a_{k}}(T)|} ≤ (1 + δ) φ(T),

so that a fortiori,

inf_{x∈ℤ}|ξ_{1}^{x}(T)| ≤ (1 + δ) φ(T).

By definition, this implies

lim sup_{T →∞} \frac{R_{1}(T)}{φ(T)} ≤ 1 + δ, a.s.

Since δ can be arbitrarily close to 0, we obtain the upper bound in (1.1). □

Proof of (1.1): lower bound. Fix δ ∈ (0, 1) and let ψ(t) = ψ_{δ}(t) := (1 − δ)\sqrt{t log log t}. According to Arratia [1], T^{−1/2}ξ_{1}(T) converges weakly (as T → ∞) to a (non-Poisson) limit point process. In particular, if we write R^{+}(T) := inf{x > 0 : x ∈ ξ_{1}(T)} and R^{−}(T) := sup\{x < 0 : x ∈ ξ_{1}(T)\}, then ℙ\{R^{+}(δT) ∈ [\sqrt{δ}T, 2\sqrt{δ}T], R^{−}(δT) ∈ [−2\sqrt{δ}T, −\sqrt{δ}T]\} converges to a (strictly) positive constant, so that

c_{26} := inf_{T ≥1} ℙ \{R^{+}(δT) ∈ [\sqrt{δ}T, 2\sqrt{δ}T], R^{−}(δT) ∈ [−2\sqrt{δ}T, −\sqrt{δ}T]\} > 0.

Consider the situation at time δT. Two particles (referred to as ξ_{1}^{+}(·) and ξ_{1}^{−}(·), respectively) occupy the sites R^{+}(δT) ∈ ℤ_{+} and R^{−}(δT) ∈ ℤ_{−} respectively whereas no site in (R^{+}(δT), R^{−}(δT)) is occupied. Let us consider the events

E_{+}(T) := {ξ_{1}^{+}(T) ≥ ψ(T), inf_{t∈[δT,T]} ξ_{1}^{+}(t) > 0} ,
E_{−}(T) := {ξ_{1}^{−}(T) ≤ −ψ(T), sup_{t∈[δT,T]} ξ_{1}^{−}(t) < 0} .

Clearly, (E_{+}(T) ∩ E_{−}(T)) ⊂ {R_{1}(T) ≥ ψ(T)}. Therefore

ℙ \{R_{1}(T) ≥ ψ(T)\} ≥ ℙ \{E_{+}(T), E_{−}(T), R^{+}(δT) ∈ [\sqrt{δ}T, 2\sqrt{δ}T],
R^{−}(δT) ∈ [−2\sqrt{δ}T, −\sqrt{δ}T]\}
(5.5)  ≥ c_{26} inf_{x∈[\sqrt{δ}T,2\sqrt{δ}T]} (ℙ \{ξ_{1}^{x}((1 − δ)T) ≥ ψ(T), inf_{t∈[0,(1−δ)T]} ξ_{1}^{x}(t) > 0\})^{2} .

For any x > 0, t > 0 and a > 0, we have, by the reflection principle,

ℙ {ξ_{1}^{x}(t) ≥ a} = ℙ {ξ_{1}^{x}(t) ≥ a, inf_{u∈[0,t]} ξ_{1}^{x}(u) > 0} + ℙ {ξ_{1}^{x}(t) ≥ a, inf_{u∈[0,t]} ξ_{1}^{x}(u) ≤ 0}
= ℙ {ξ_{1}^{x}(t) ≥ a, inf_{u∈[0,t]} ξ_{1}^{x}(u) > 0} + ℙ {ξ_{1}^{−x}(t) ≥ a} .

Taking t := (1 − δ)T and a := ψ(T) yields that

inf_{x∈[\sqrt{δ}T,2\sqrt{δ}T]} ℙ \{ξ_{1}^{x}((1 − δ)T) ≥ ψ(T), inf_{t∈[0,(1−δ)T]} ξ_{1}^{x}(t) > 0\}

≥ exp (−(1 + o(1))\frac{(ψ(T) − \sqrt{δ}T)^{2}}{2T} ) .

Plugging this into (5.5), and we get that

ℙ \{R_{1}(T) ≥ ψ(T)\} ≥ exp (−(1 + o(1))\frac{ψ^{2}(T)}{T})
≥ exp (−(1 − 2δ) log log T)
(5.6)  = \frac{1}{(log T)^{1−2δ}} .

Let T_{n} := n^{n}, and consider a sequence of independent random variables (R_{1}^{(n)}(T_{n} − T_{n−1}), n ≥ 2), such that for any n, R_{1}^{(n)}(T_{n} − T_{n−1}) is distributed as R_{1}(T_{n} − T_{n−1}). We can make a coupling for (R_{1}^{(n)}(T_{n} − T_{n−1}), n ≥ 2) and the coalescing random walk (ξ_{1}(t), t ≥ 0) such that R_{1}(T_{n}) ≥ R_{1}^{(n)}(T_{n} − T_{n−1}) for all n ≥ 2.

By (5.6) and the Borel–Cantelli lemma, almost surely there exists infinitely many n such that R_{1}^{(n)}(T_{n} − T_{n−1}) ≥ ψ(T_{n} − T_{n−1}). Therefore,

lim sup_{n→∞} \frac{R_{1}(T_{n})}{ψ(T_{n} − T_{n−1})} ≥ 1, a.s.

Since ψ(T_{n} − T_{n−1}) ∼ ψ(T_{n}) = (1 − δ)\sqrt{T_{n} log log T_{n}}, and since δ > 0 can be as close to 0 as possible, this yields the lower bound in (1.1). □

Remark. Let as before R^{+}(T) := inf{x > 0 : x ∈ ξ_{1}(T)} and R^{−}(T) := sup{x < 0 : x ∈ ξ_{1}(T)}. In words, R^{+}(T) (resp. R^{−}(T)) is the smallest positive (resp. largest negative) site occupied by the coalescing random walk at time T. By definition, R_{1}(T) = R^{+}(T)∧|R^{−}(T)|. Our proof of (1.1) also shows that

lim sup_{T →∞} \frac{X(T)}{\sqrt{T log log T}} = 1, a.s.

where X(T) can be either R^{+}(T), or |R^{−}(T)|, or R^{+}(T) ∨ |R^{−}(T)|, or (R^{+}(T) + |R^{−}(T)|)/2.

6 Proof of Theorem 1.3

Let d ≥ 2. By (1.10)–(1.11), Proposition 2.2 and Chebyshev’s inequality, we have, for ε > 0 and T ≥ 3,

ℙ \{|Λ_{d}(T) − 𝔼[Λ_{d}(T)]| ≥ ε 𝔼[Λ_{d}(T)]\} ≤ \frac{c_{27}}{log T} ,

for some constant c_{27} depending on (d, ε). Taking the subsequence T = T_{k} := exp{k(log k)^{2}}, and by means of the Borel–Cantelli lemma, we have, almost surely for all large k,

(1 − ε)𝔼[Λ_{d}(T_{k})] ≤ Λ_{d}(T_{k}) ≤ (1 + ε)𝔼[Λ_{d}(T_{k})].

By the monotonicity of T ↦ Λ_{d}(T) and again in view of (1.10)–(1.11), this implies that almost surely for all large T,

(1 − 2ε)𝔼[Λ_{d}(T)] ≤ Λ_{d}(T) ≤ (1 + 2ε)𝔼[Λ_{d}(T)].

Since ε > 0 can be arbitrarily close to 0, this yields Theorem 1.3. □

Acknowledgements

The authors are grateful to an anonymous referee for useful remarks. Research of E. Csáki and P. Révész was supported by the Hungarian National Foundation for Scientific Research, grant no. T 029621 and T 037886. Cooperation between the authors was supported by the joint French–Hungarian Intergovernmental Grant “Balaton”, grant no. F-39/2000.

References

[1] Arratia, R. (1981). Limiting point processes for rescalings of coalescing and annihilating random walks on Z^{d}. Ann. Probab. 9, 909–936.

[2] van den Berg, J. and Fiebig, U. (1987). On a combinatorial conjecture concerning disjoint occurrences of events. Ann. Probab. 15, 354–374.

[3] van den Berg, J. and Kesten, H. (2000). Asymptotic density in a coalescing random walk model. Ann. Probab. 28, 303–352.

[4] van den Berg, J. and Kesten, H. (2002). Randomly coalescing random walk in dimension ≥ 3. In: In and Out of Equilibrium: Probability with a Physics Flavor (V. Sidoravicius, ed.), pp. 1–45. Birkhäuser, Boston.

[5] Borodin, A.N. and Salminen, P. (1996). Handbook of Brownian Motion–Facts and Formulae. Birkhäuser, Basel.

[6] Bramson, M., Cox, J.T. and Griffeath, D. (1988). Occupation time large deviations of the voter model. Probab. Theory Related Fields 77, 401–413.

[7] Bramson, M., Cox, J.T. and Le Gall, J.-F. (2001). Super-Brownian limits of voter model clusters. Ann. Probab. 29, 1001–1032.

[8] Bramson, M. and Griffeath, D. (1980). Asymptotics for interacting particle systems on Z^{d}. Z. Wahrsch. verw. Gebiete 53, 183–196.

[9] Cox, J.T., Durrett, R.T. and Perkins, E.A. (2000). Rescaled voter models converge to super-Brownian motion. Ann. Probab. 28, 185–234.

[10] Cox, J.T. and Griffeath, D. (1983). Occupation time limit theorems for the voter model. Ann. Probab. 11, 876–893.

[11] Csörgő, M., Deheuvels, P. and Horváth, L. (1987). An approximation of stopped sums with applications in queuing theory. Adv. Appl. Probab. 19, 674–690.

[12] Csörgő, M. and Horváth, L. (1993). Weighted Approximations in Probability and Statistics. Wiley, Chichester.

[13] Griffeath, D. (1979). Additive and Cancellative Interacting Particle Systems. Lecture Notes in Mathematics 724. Springer, New York.

[14] Joag-Dev, K. and Proschan, F. (1983). Negative association of random variables with applications. Ann. Statist. 11, 286–295.

[15] Komlós, J., Major, P. and Tusnády, G. (1975). An approximation of partial sums of independent r.v.’s and the sample df. I. Z. Wahrsch. verw. Gebiete 32, 111–131.

[16] Liggett, T.M. (1985). Interacting Particle Systems. Springer, New York.

[17] Liggett, T.M. (1999). Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer, New York.

[18] Petrov, V.V. (1995). Limit Theorems of Probability Theory. Clarendon Press, Oxford.

[19] Reimer, D. (2000). Proof of the van den Berg-Kesten conjecture. Combin. Probab. Comput. 9, 27–32.

[20] Shao, Q.-M. (2000). A comparison theorem on moment inequalities between negatively associated and independent random variables. J. Theoretical Probab. 13, 343–356.

[21] Shiryaev, A.N. (1996). Probability (second edition). Springer, New York.

Endre Csáki  Pál Révész
Alfréd Rényi Institute of Mathematics  Institut für Statistik und Wahrscheinlichkeitstheorie
Hungarian Academy of Sciences  Technische Universität Wien
P.O. Box 127  Wiedner Hauptstrasse 8-10/107
H-1364 Budapest  A-1040 Vienna
Hungary  Austria

   csaki@renyi.hu                          revesz@ci.tuwien.ac.at

Zhan Shi

Laboratoire de Probabilités UMR 7599 Université Paris VI 4 place Jussieu F-75252 Paris Cedex 05 France

   zhan@proba.jussieu.fr