A strong invariance principle for two-dimensional

random walk in random scenery

Endre Csáki^{a,}^{*}, Pál Révész^{b}, Zhan Shi^{c}

aAlfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, P.O.B. 127, H-1364 Budapest, Hungary

                        E-mail address: csaki@renyi.hu

bInstitut für Statistik und Wahrscheinlichkeitstheorie, Technische Universität Wien, Wiedner Hauptstrasse 8-10/107, Vienna, Austria

                    E-mail address: revesz@ci.tuwien.ac.at

cLaboratoire de Probabilités UMR 7599, Université Paris VI, 4 Place Jussieu, F-75252 Paris Cedex 05, France

                     E-mail address: zhan@proba.jussieu.fr

Abstract

We present a strong approximation of two-dimensional Kesten–Spitzer random walk in random scenery by Brownian motion.

MSC: 60G50; 60F17

Keywords: Random walk in random scenery; Invariance principle; Skorokhod embedding.

*Corresponding author.

1 Introduction

The following model originates from Kesten and Spitzer (1979): Every lattice site x ∈ ℤ^{d} is attached to a price value Y (x), and a random walker moves on ℤ^{d} (in this paper: d = 2), whose movement is denoted by {S_{n}; n ≥ 0}, with say S_{0} = 0. Each time the random walker visits x ∈ ℤ^{d}, he increases (or decreases, if the price is negative) his fortune by Y (x). Thus at step n, the total amount of prices he gets is

Z(n) =^{def} ∑_{j=0}^{n} Y (S_{j}). (1.1)

Throughout the paper, it is assumed that {Y (x); x ∈ ℤ^{d}} is a collection of independent and identically distributed random variables with 𝔼(Y (0)) = 0 and σ^{2} =^{def} 𝔼(Y^{2}(0)) ∈ (0, ∞). The collection of these variables is referred to as random scenery, and is furthermore supposed to be independent of the random walk {S_{n}; n ≥ 0}. The process Z =^{def} {Z(n); n ≥ 0} is the so-called random walk in random scenery.

When d = 1, Kesten and Spitzer (1979) proved that, under some appropriate regularity conditions upon Y (0), n^{−3/4}Z(⌊nt⌋) (as a process indexed by t ∈ ℝ_{+}) converges weakly in D[0, ∞) (space of càdlàg functions endowed with the locally uniform convergence topology) to a non-Gaussian process. For d ≥ 3, it was noted by Bolthausen (1989) that n^{−1/2}Z(⌊nt⌋) converges weakly to (a constant multiple of) the Wiener process. In Khoshnevisan and Lewis (1998) (for Gaussian sceneries), Csáki et al. (1999) and Révész and Shi (2000) these weak limit assertions were strengthened to strong approximation results.

Not surprisingly, the dimension d = 2 is critical which separates the asymptotic Gaussian and non-Gaussian behaviours of Z. For this case, Kesten and Spitzer (1979) conjectured that Z still converges weakly to a Wiener process, but with the slightly non-standard normalizer (n log n)^{−1/2}. The conjecture was later proved by Bolthausen (1989) (see also Borodin, 1980): in D[0, ∞),

(1.2) \{\frac{Z(⌊nt⌋)}{(n log n)^{1/2}} ; t ∈ ℝ_{+}\} converges weakly to \{σ(2/π)^{1/2} W (t); t ∈ ℝ_{+}\} ,

where W denotes a standard one-dimensional Wiener process.

The aim of this paper is to present a version of strong invariance principle for (1.2). Throughout, we assume that {S_{n}; n ≥ 0} is a simple symmetric random walk on ℤ^{2} (with S_{0} = 0), i.e., in each step the walker moves to any of the nearest neighbour sites with equal probability 1/4.

Theorem 1.1 Let d = 2 and assume that 𝔼(|Y (0)|^{q}) < ∞ for some q > 2. Possibly in an enlarged probability space, there exist a version of {Z(n); n ≥ 0} and a standard onedimensional Wiener process {W (t); t ≥ 0}, such that for any ε > 0 as n goes to infinity,

(1.3)  Z(n) − σ(2/π)^{1/2} W (n log n) = o (n^{1/2}(log n)^{3/8+ε}) ,  a.s.

Remark. It is important to note that 3/8 < 1/2. As consequences, Theorem 1.1 implies the weak convergence in (1.2), and also the following iterated logarithm law due to Lewis (1993):

(1.4)  lim sup_{n→∞} \frac{Z(n)}{n^{1/2}(log n)^{1/2}(log log n)^{1/2}} = \frac{2σ}{π^{1/2}} ,  a.s.

There are, however, many other consequences of Theorem 1.1. For example, it follows that Strassen’s law holds: let

Z_{n}(t) =^{def} \frac{π^{1/2}Z(⌊nt⌋)}{σ(n log n log log n)^{1/2}} ; t ∈ [0, 1].

Then {Z_{n}(·)}_{n≥3} is almost surely relatively compact in C[0, 1] and the set of its limit points consists of all absolutely continuous functions f(·) such that f(0) = 0 and ∫_{0}^{1}(f′(u))^{2} du ≤ 1.

The Chung-type law of the iterated logarithm

(1.5)  lim inf_{n→∞} \frac{(log log n)^{1/2}}{(n log n)^{1/2}} sup_{0≤k≤n} |Z(k)| = \frac{σπ^{1/2}}{2^{1/2}} ,  a.s.,

is also a consequence of Theorem 1.1. Moreover, (1.4) and (1.5) can be extended to upper– lower class results. □

The rest of the paper is organized as follows. In Section 2, Theorem 1.1 is proved by means of four technical lemmas. The proofs of these lemmas are postponed to Sections 3–6.

2 Proof of Theorem 1.1

This section is devoted to the proof of Theorem 1.1. We shall use some technical lemmas (Lemmas 2.1–2.4 below), whose proofs are provided in Sections 3–6, respectively.

Let {S_{n}; n ≥ 0} be a simple symmetric random walk on ℤ^{2} as in the Introduction, and let

ξ(n, x) =^{def} ∑_{i=0}^{n} 1_{{S_{i}=x}}, n ≥ 0, x ∈ ℤ^{2}.

The process ξ(· , ·) is often referred to as the local time of the random walk. The random walk in random scenery Z defined in (1.1) can now be written as

Z(n) = ∑_{x∈ℤ^{2}} ξ(n, x)Y (x).

Define the truncated scenery {Ŷ(x); x ∈ ℤ^{2}} and the associated random walk in random scenery {Ẑ(n); n ≥ 0} by

Ŷ(x) =^{def} Y (x)1_{{|Y (x)|≤∥x∥}} − 𝔼(Y (x)1_{{|Y (x)|≤∥x∥}}),
Ẑ(n) =^{def} ∑_{x∈ℤ^{2}} ξ(n, x)Ŷ(x).

Our first technical lemma says that Ẑ(n) is reasonably close to Z(n).

Lemma 2.1 Under the conditions of Theorem 1.1, there exists δ > 0 such that when n → ∞,

Z(n) − Ẑ(n) = O (n^{1/2−δ}) , a.s. (2.1)

We now work on the process {Ẑ(n); n ≥ 0}. We first look at this process along the subsequence {n_{k}} defined as follows. Fix ϱ ∈ (1/2, 1), and let the sequence {n_{k}}_{k≥1} of non-decreasing numbers be given by

n_{k} =^{def} ⌊exp(k^{ϱ})⌋.

We shall frequently use the following relations without further mention: when k → ∞,

(2.2) n_{k+1} ∼ n_{k}, log(n_{k+1} − n_{k}) ∼ log n_{k}, n_{k+1} − n_{k} ∼ \frac{ϱ n_{k}}{(log n_{k})^{(1−ϱ)/ϱ}} ,

where a_{k} ∼ b_{k} means lim_{k→∞} a_{k}/b_{k} = 1. Also,

∑_{k=1}^{ℓ} n_{k}^{a}(log n_{k})^{b} = O (n_{ℓ}^{a}(log n_{ℓ})^{b−1+1/ϱ}) , ℓ → ∞. (2.3)

Let us consider

U_{k} =^{def} Ẑ(n_{k+1}) − Ẑ(n_{k}).

For brevity, we write

ξ_{k}(x) =^{def} ξ(n_{k+1}, x) − ξ(n_{k}, x), k ≥ 1, x ∈ ℤ^{2},

so that

U_{k} = ∑_{x∈ℤ^{2}} ξ_{k}(x)Ŷ(x).

The random variables U_{k}, k = 1, 2, … are the increments of Ẑ(n_{k}). Unfortunately, these are not independent variables given the random walk {S_{n}; n ≥ 0}. The idea is to replace these variables by another sequence of variables which are conditionally independent given the random walk.

Let {Y (x), Y_{1}(x), Y_{2}(x), ⋯, x ∈ ℤ^{2}} be a collection of iid random variables. (It is always possible to define these on the same probability space by working in a product space). For any k ≥ 1, let (2.4) V_{k} =^{def} ∑_{x∉A_{k}} ξ_{k}(x)Ŷ(x) + ∑_{x∈A_{k}} ξ_{k}(x)Ŷ_{k}(x),

where

Ŷ_{k}(x) =^{def} Y_{k}(x)1_{{|Y_{k}(x)|≤∥x∥}} − 𝔼(Y_{k}(x)1_{{|Y_{k}(x)|≤∥x∥}}),

and

A_{k} =^{def} {x ∈ ℤ^{2} : ξ(n_{k+1}, x) > ξ(n_{k}, x) > 0} .

In words, A_{k} is the set of sites which are visited by the random walk during [0, n_{k}] and again during (n_{k}, n_{k+1}].

It turns out that V_{k} is close to U_{k}. More precisely, the following estimate holds:

Lemma 2.2 Under the conditions of Theorem 1.1, for any ε > 0, we have, when k → ∞,

U_{k} − V_{k} = o (n_{k}^{1/2}(log n_{k})^{1/2−1/(2ϱ)+ε}) , a.s. (2.5)

By means of Lemma 2.2 (and in light of (2.3)), we can sum over k ≤ ℓ − 1, and use the relation Ẑ(n_{ℓ}) = Ẑ(n_{1}) + ∑_{k=1}^{ℓ−1} U_{k}, to see that for any ε > 0, when ℓ → ∞,

Ẑ(n_{ℓ}) − ∑_{k=1}^{ℓ−1} V_{k} = o (n_{ℓ}^{1/2}(log n_{ℓ})^{−1/2+1/(2ϱ)+ε}) , a.s. (2.6)

Since {V_{k}}_{k≥1} are (conditionally) independent variables (given the random walk), it is possible to embed ∑_{k=1}^{ℓ−1} V_{k} into a Wiener process, via the following lemma.

Lemma 2.3 Under the conditions of Theorem 1.1, possibly in an enlarged probability space, there exists a standard Wiener process {W (t); t ≥ 0}, such that for any ε > 0, when ℓ → ∞,

∑_{k=1}^{ℓ−1} V_{k} − W (b_{n_{ℓ}}) = o (n_{ℓ}^{1/2}(log n_{ℓ})^{β+ε}) , a.s., (2.7)

where

(2.8)  b_{n} =^{def} \frac{2σ^{2}}{π} n log n,
(2.9)  β =^{def} max (\frac{3}{4} − \frac{1}{4ϱ}, \frac{1}{4ϱ}) .

Assembling (2.1), (2.6) and (2.7), we arrive at: for any ε > 0, when ℓ → ∞,

Z(n_{ℓ}) − W (b_{n_{ℓ}}) = o (n_{ℓ}^{1/2}(log n_{ℓ})^{β+ε}) , a.s. (2.10)

(We have used the fact that −1/2 + 1/(2ϱ) ≤ β). This is a strong approximation for Z along the subsequence {n_{ℓ}}. To claim that it holds for all large n, we need to control the increments of Z and W.

Lemma 2.4 Under the conditions of Theorem 1.1, with probability one, for any ε > 0, as ℓ → ∞,

(2.11)  max_{n_{ℓ}≤n≤n_{ℓ+1}} |Z(n) − Z(n_{ℓ})| = o (n_{ℓ}^{1/2}(log n_{ℓ})^{1−1/(2ϱ)+ε}) ,
(2.12)  sup_{b_{n_{ℓ}}≤t≤b_{n_{ℓ+1}}} |W (t) − W (b_{n_{ℓ}})| = O (n_{ℓ}^{1/2}(log n_{ℓ})^{1−1/(2ϱ)}(log log n_{ℓ})^{1/2}) .

It is now easy to complete the proof of Theorem 1.1. Indeed, since 1 − 1/(2ϱ) < 3/4 − 1/(4ϱ), we can bring (2.10), (2.11) and (2.12) together to see that for any ε > 0 and 1/2 < ϱ < 1,

Z(n) − W (b_{n}) = o (n^{1/2}(log n)^{β+ε}) , a.s.

Taking ϱ = 2/3 yields β = 3/8. Theorem 1.1 is proved. □

We prove the four lemmas in the next sections.

3 Proof of Lemma 2.1

Throughout, we assume q < 3 without loss of generality.

Since 𝔼(Y (x)) = 0 for any x ∈ ℤ^{2}, we have

(3.1) |Z(n) − Ẑ(n)| ≤ ∑_{x∈ℤ^{2}} ξ(n, x) [|Y (x)| 1_{{|Y (x)|>∥x∥}} + 𝔼(|Y (x)| 1_{{|Y (x)|>∥x∥}})] .

By Chebyshev’s inequality, for x ≠ 0,

ℙ(|Y (x)| > ∥x∥) ≤ \frac{𝔼(|Y (x)|^{q})}{∥x∥^{q}} = \frac{𝔼(|Y (0)|^{q})}{∥x∥^{q}}.

Since q > 2, this yields

∑_{x∈ℤ^{2}} ℙ(|Y (x)| > ∥x∥) < ∞.

Consequently, in the expression ∑_{x∈ℤ^{2}} ξ(n, x) |Y (x)| 1_{{|Y (x)|>∥x∥}} on the right hand side of (3.1), only finitely many terms are different from zero. Moreover, for x ≠ 0,

𝔼(|Y (x)| 1_{\{|Y (x)|>∥x∥\}}) ≤ \frac{𝔼(|Y (x)|^{q})}{∥x∥^{q−1}} ≤ \frac{2 𝔼(|Y (0)|^{q})}{1 + ∥x∥^{q−1}}.

Hence, as n → ∞, we have almost surely

(3.2) |Z(n) − Ẑ(n)| ≤ O ( max_{x∈ℤ^{2}}ξ(n, x)) + c_{1} ∑_{x∈ℤ^{2}} \frac{ξ(n, x)}{1 + ∥x∥^{q−1}} .

Observe that

∑_{x∈ℤ^{2}, ∥x∥>n^{1/2}} \frac{ξ(n, x)}{1 + ∥x∥^{q−1}} ≤ n^{−(q−1)/2} ∑_{x∈ℤ^{2}} ξ(n, x) = n^{(3−q)/2},

and that

∑_{x∈ℤ^{2}, ∥x∥≤n^{1/2}} \frac{ξ(n, x)}{1 + ∥x∥^{q−1}} ≤ ( max_{x∈ℤ^{2}}ξ(n, x)) ∑_{∥x∥≤n^{1/2}} \frac{1}{1 + ∥x∥^{q−1}}
≤ c_{2} max_{x∈ℤ^{2}}ξ(n, x) ∫_{0}^{n^{1/2}} \frac{r}{1 + r^{q−1}} dr
≤ c_{3} n^{(3−q)/2} max_{x∈ℤ^{2}}ξ(n, x).

Plugging these into (3.2) gives that, when n → ∞,

Z(n) − Ẑ(n) = O ( n^{(3−q)/2} max_{x∈ℤ^{2}}ξ(n, x)) , a.s.

According to Erdős and Taylor (1960), max_{x∈ℤ^{2}} ξ(n, x) = O(log^{2} n) almost surely, and since q > 2, this yields Lemma 2.1. □

4 Proof of Lemma 2.2

We start with a preliminary estimate (Lemma 4.1 below), which will be of frequent use later. Recall that ξ(n, x) is the local time of the two-dimensional random walk {S_{n}; n ≥ 0}. It is well-known (see for example Révész, 1990, p. 183) that

ℙ(S_{2k} = 0) = \frac{1}{kπ} + O (\frac{1}{k^{2}} ) , k → ∞, (4.1)

which implies the existence of a finite and positive constant c_{4} such that ℙ(S_{n} = 0) ≤ c_{4}/n, for all n ≥ 1. Since ξ(n, 0) = ∑_{i=0}^{n} 1_{{S_{i}=0}}, we arrive at: for any integer m ≥ 1, there exists c_{5} = c_{5}(m) such that

𝔼 (ξ^{m}(n, 0)) ≤ c_{5} (log n)^{m}, n ≥ 2.

For any fixed x ∈ ℤ^{2}, ξ(n, x) is stochastically smaller than or equal to ξ(n, 0). Accordingly,

(4.2)  sup_{x∈ℤ^{2}} 𝔼 (ξ^{m}(n, x)) ≤ c_{5} (log n)^{m},  n ≥ 2.

An immediate consequence of (4.2) together with Hölder’s inequality is that, for any positive integers ℓ and m_{1}, ⋯, m_{ℓ},

(4.3)  sup_{x_{1}∈ℤ^{2}, ···, x_{ℓ}∈ℤ^{2}} 𝔼 (ξ^{m_{1}}(n, x_{1}) ⋯ ξ^{m_{ℓ}}(n, x_{ℓ})) ≤ c_{6} (log n)^{m_{1}+···+m_{ℓ}},  n ≥ 2,

where c_{6} = c_{6}(ℓ, m_{1}, ⋯, m_{ℓ}).

Lemma 4.1 Let {η(n, x); n ≥ 1, x ∈ ℤ^{2}} be a set of random variables independent of the random walk {S_{n}}_{n≥0}, such that for some α ≥ 0,

ℙ (0 ≤ η(n, x) ≤ ∥x∥^{α}; n ≥ 1, x ∈ ℤ^{2}) = 1.

Then for any integers m ≥ 1 and ℓ ≥ 1, and any ε > 0 and 0 < ν < ε/(2ℓ), there exist c_{7} = c_{7}(m, ℓ, ε, ν, α) and c_{8} = c_{8}(ℓ, ν, α) such that for all n ≥ 2,

(4.4) 𝔼 [ ( ∑_{x∈ℤ^{2}} ξ^{m}(n, x)η(n, x))^{ℓ} ] ≤ c_{7} n^{ℓ} (n^{αℓ/2}e^{−c_{8}(log n)^{ν}} + φ_{n,ℓ,ν}) (log n)^{(m−1)ℓ+ε},

where

(4.5)  φ_{n,ℓ,ν} =^{def} sup_{∥x_{i}∥<n^{1/2}(log n)^{ν}, 1≤i≤ℓ} 𝔼 ( ∏_{i=1}^{ℓ} η(n, x_{i})) .

In particular, we have

𝔼 [ ( ∑_{x∈ℤ^{2}} ξ^{m}(n, x) ∥x∥^{α})^{ℓ} ] ≤ c_{9} n^{ℓ+αℓ/2}(log n)^{(m−1)ℓ+ε}, n ≥ 2, (4.6)

for some c_{9} = c_{9}(m, ℓ, α, ε). Proof. Write

Ω_{1} =^{def} {x ∈ ℤ^{2} : ∥x∥ ≥ n^{1/2}(log n)^{ν}} ,
Ω_{2} =^{def} {x ∈ ℤ^{2} : ∥x∥ < n^{1/2}(log n)^{ν}} .

Then

∑_{x∈ℤ^{2}} ξ^{m}(n, x)η(n, x) = ( ∑_{x∈Ω_{1}} + ∑_{x∈Ω_{2}} ) ξ^{m}(n, x)η(n, x)
(4.7) =^{def} I_{1} + I_{2},

with obvious notation. Observe that for j = 1 or 2,

𝔼(I_{j}^{ℓ}) = ∑_{x_{1}∈Ω_{j}} ⋯ ∑_{x_{ℓ}∈Ω_{j}} 𝔼 ( ∏_{i=1}^{ℓ} ξ^{m}(n, x_{i})) 𝔼 ( ∏_{i=1}^{ℓ} η(n, x_{i})) . (4.8)

We now estimate 𝔼(I_{1}^{ℓ}) and 𝔼(I_{2}^{ℓ}) separately. Define

R_{n} =^{def} {S_{0}, S_{1}, …, S_{n}} ,

which is the range of the random walk up to step n. When ∥x∥ ≥ n^{1/2}, we have

(4.9) ℙ (x ∈ R_{n}) ≤ ℙ ( max_{0≤k≤n} ∥S_{k}∥ ≥ ∥x∥) ≤ c_{10} exp (−c_{11} \frac{∥x∥^{2}}{n} ) ,

for some absolute constants c_{10} and c_{11}.

Since ξ^{m}(n, x) = ξ^{m}(n, x)1_{{x∈R_{n}}} for any x ∈ ℤ^{2}, we can apply Hölder’s inequality to see that, if ∥x_{i}∥ ≥ n^{1/2}(log n)^{ν} for all 1 ≤ i ≤ ℓ,

𝔼 ( ∏_{i=1}^{ℓ} ξ^{m}(n, x_{i})) ≤ ( ∏_{i=1}^{ℓ} 𝔼(ξ^{2ℓm}(n, x_{i})))^{1/(2ℓ)} ( ∏_{i=1}^{ℓ} ℙ(x_{i} ∈ R_{n}))^{1/(2ℓ)}
≤ c_{12} (log n)^{mℓ} exp (−\frac{c_{11}}{2ℓ} \frac{∑_{i=1}^{ℓ} ∥x_{i}∥^{2}}{n} ) ,

the last inequality following from (4.2) and (4.9). Therefore, by (4.8) and the assumption η(n, x) ≤ ∥x∥^{α},

𝔼(I_{1}^{ℓ}) ≤ c_{12} (log n)^{mℓ} [ ∑_{∥x∥≥n^{1/2}(log n)^{ν}} ∥x∥^{α} exp (−\frac{c_{11}}{2ℓ} \frac{∥x∥^{2}}{n} )]^{ℓ}
(4.10)  ≤ c_{13} n^{ℓ+αℓ/2} exp (−c_{8} (log n)^{2ν}) .

In the last inequality, we used the fact that for any fixed constant c > 0, when n → ∞, ∑_{∥x∥≥n^{1/2}(log n)^{ν}} ∥x∥^{α} exp(−c∥x∥^{2}/n) = O(n^{α/2+1}(log n)^{αν} exp(−c(log n)^{2ν})).

To estimate 𝔼(I_{2}^{ℓ}), we recall Lemma 22.5 of Révész (1990, p. 224) (with slightly different notation): for any sites x_{1}, ⋯, x_{ℓ} in ℤ^{2},

ℙ (x_{1} ∈ R_{n}, ⋯, x_{ℓ} ∈ R_{n}) ≤ (μ(n))^{ℓ−1} max_{1≤i≤ℓ} ℙ (x_{i} ∈ R_{n}) , (4.11)

where μ(n) =^{def} max_{1≤i<j≤n} ℙ(x_{i} − x_{j} ∈ R_{n}). We take this opportunity to correct a misprint in page 224 of Révész (1990), where the definition of μ(n) is mistakenly stated as max_{1≤i≤n} ℙ(x_{i} ∈ R_{n}).

We now apply Hölder’s inequality. Let a > 1. It is possible to find p > 1 such that 1/a + 1/p = 1. Then (writing A =^{def} {x_{1} ∈ R_{n}, ⋯, x_{ℓ} ∈ R_{n}} for brevity)

𝔼 ( ∏_{i=1}^{ℓ} ξ^{m}(n, x_{i})) = 𝔼 (ξ^{m}(n, x_{1}) ⋯ ξ^{m}(n, x_{ℓ}) 1_{A})
≤ [𝔼 (ξ^{mp}(n, x_{1}) ⋯ ξ^{mp}(n, x_{ℓ}))]^{1/p} [ℙ(A)]^{1/a} ,

which, according to (4.3) and (4.11), is

≤ c_{14} (log n)^{mℓ} ∑_{1≤i<j≤ℓ} ℙ(x_{i} − x_{j} ∈ R_{n})^{(ℓ−1)/a} ∑_{k=1}^{ℓ} ℙ(x_{k} ∈ R_{n})^{1/a}.

Plugging this into (4.8) (and using symmetry) yields that for some c_{15} = c_{15}(m, ℓ, a),

𝔼(I_{2}^{ℓ}) ≤ c_{15} φ_{n,ℓ,ν} (log n)^{mℓ}(n(log n)^{2ν})^{ℓ−2}I_{3}

+c_{15} φ_{n,ℓ,ν} (log n)^{mℓ}(n(log n)^{2ν})^{ℓ−3}I_{4}, (4.12)

where

I_{3} =^{def} ∑_{x_{1}∈Ω_{2}} ∑_{x_{2}∈Ω_{2}} ℙ(x_{1} − x_{2} ∈ R_{n})^{(ℓ−1)/a} ℙ(x_{1} ∈ R_{n})^{1/a},

I_{4} =^{def} ∑_{x_{1}∈Ω_{2}} ∑_{x_{2}∈Ω_{2}} ∑_{x_{3}∈Ω_{2}} ℙ(x_{1} − x_{2} ∈ R_{n})^{(ℓ−1)/a} ℙ(x_{3} ∈ R_{n})^{1/a}.

(When ℓ = 1, we simply have 𝔼(I_{2}^{ℓ}) ≤ c_{15} φ_{n,ℓ,ν} (log n)^{m} ∑_{x∈Ω_{2}} ℙ(x ∈ R_{n})^{1/a}. When ℓ = 2, I_{4} should be considered as 0).

If (x_{1}, x_{2}) ∈ Ω_{2} × Ω_{2} , then

x_{1} − x_{2} ∈ Ω̃_{2} =^{def} {x ∈ ℤ^{2} : ∥x∥ < 2n^{1/2}(log n)^{ν}} .

Thus

I_{3} ≤ ∑_{x_{1}∈Ω_{2}} ℙ(x_{1} ∈ R_{n})^{1/a} ∑_{x∈Ω̃_{2}} ℙ(x ∈ R_{n})^{(ℓ−1)/a}
(4.13)  ≤ ∑_{x_{1}∈Ω̃_{2}} ℙ(x_{1} ∈ R_{n})^{1/a} ∑_{x∈Ω̃_{2}} ℙ(x ∈ R_{n})^{(ℓ−1)/a}.

Similarly,

(4.14) I_{4} ≤ c_{16} n(log n)^{2ν} ∑_{x_{3}∈Ω̃_{2}} ℙ(x_{3} ∈ R_{n})^{1/a} ∑_{x∈Ω̃_{2}} ℙ(x ∈ R_{n})^{(ℓ−1)/a}.

To see how ∑_{x∈Ω̃_{2}} ℙ(x ∈ R_{n})^{b} behaves, we recall the following result of Erdős and Taylor (1960): for n ≥ 2 and n^{1/6} < ∥x∥ < n^{1/2}/20,

ℙ (x ∈ R_{n}) ≤ c_{17} \frac{log(n^{1/2}/∥x∥)}{log n}.

This clearly also yields ℙ(x ∈ R_{n}) ≤ c_{18}/ log n for ∥x∥ ≥ n^{1/2}/20. When ∥x∥ ≤ n^{1/6}, log(n^{1/2}/∥x∥)/ log n is of constant order (except for the special case x = 0). Therefore,

(4.15)  ℙ (x ∈ R_{n}) ≤ c_{19} \frac{log_{∗}(n^{1/2}/(∥x∥ + 1))}{log n},  n ≥ 2, x ∈ ℤ^{2},

where log_{∗} u =^{def} log max(u, e) for all u ∈ ℝ.

Accordingly, for any b ≥ 0,

∑_{x∈Ω̃_{2}} ℙ(x ∈ R_{n})^{b} ≤ c_{20} ∑_{x∈Ω̃_{2}} (\frac{log_{∗}(n^{1/2}/(∥x∥ + 1))}{log n})^{b}
≤ c_{21} ∫_{0}^{2n^{1/2}(log n)^{ν}} (\frac{log_{∗}(n^{1/2}/(r + 1))}{log n})^{b} r dr
≤ c_{22} n(log n)^{−b+2ν},

where c_{22} = c_{22}(b, ν). Plugging this into (4.13) and (4.14) gives I_{3} ≤ c_{23} n^{2}(log n)^{−ℓ/a+4ν} and I_{4} ≤ c_{24} n^{3}(log n)^{−ℓ/a+6ν}. Going back to (4.12), we obtain: for some c_{25} = c_{25}(m, ℓ, ν, a),

𝔼(I_{2}^{ℓ}) ≤ c_{25} φ_{n,ℓ,ν} n^{ℓ}(log n)^{mℓ+2νℓ−ℓ/a}.

Since ν < ε/(2ℓ) and since a > 1 is arbitrary, combining this estimate with (4.7) and (4.10) completes the proof of Lemma 4.1. □

Now we are ready to prove Lemma 2.2.

Proof of Lemma 2.2. By definition,

V_{k} − U_{k} = ∑_{x∈A_{k}} ξ_{k}(x)(Ŷ_{k}(x) − Ŷ(x)).

Let ℙ^{S}( ·) = ℙ( · |{S_{n}}_{n≥0}), the conditional probability given the random walk. We write 𝔼^{S} for the expectation associated with this conditional probability. Under ℙ^{S}, for each k, {Ŷ_{k}(x) − Ŷ(x), x ∈ A_{k}} are independent mean-zero variables.

Recall Rosenthal’s inequality (see for example Petrov, 1995, p. 59): if X_{1}, ⋯, X_{n} are independent mean-zero variables and if p ≥ 2, then

𝔼 ( | ∑_{i=1}^{n} X_{i}|^{p} ) ≤ C(p) [ ∑_{i=1}^{n} 𝔼(|X_{i}|^{p}) + ( ∑_{i=1}^{n} 𝔼(X_{i}^{2}))^{p/2} ] , (4.16)

where C(p) ∈ (0, ∞) is a constant depending only on p.

Let q be the constant in Theorem 1.1, and let p > q be an even integer. Note that

𝔼^{S}(|Ŷ(x)|^{p}) ≤ c_{26} (1 + ∥x∥^{p−q}), (4.17)

for some constant c_{26} = c_{26}(q) > 0.

Applying (4.16) to our conditional probability ℙ^{S} yields

𝔼 [|V_{k} − U_{k}|^{p}] = 𝔼 [𝔼^{S} ( | ∑_{x∈A_{k}} ξ_{k}(x)(Ŷ_{k}(x) − Ŷ(x))|^{p} )]

(4.18)  ≤ c_{27} 𝔼 ( ∑_{x∈A_{k}} ξ_{k}^{p}(x) ∥x∥^{p−q}) + c_{28} 𝔼 [ ( ∑_{x∈A_{k}} ξ_{k}^{2}(x))^{p/2} ] .

We write ∥x∥^{p−q} instead of 1 + ∥x∥^{p−q} on the right hand side because ∑_{x∈A_{k}} ξ_{k}^{p}(x) ≤ (∑_{x∈A_{k}} ξ_{k}^{2}(x))^{p/2}.

We now estimate the two expectation expressions on the right hand side. For the second expression, we note that ∑_{x∈A_{k}} ξ_{k}^{2}(x) = ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x)1_{{x∈R_{n_{k}} }}, where R_{n} denotes as before the range of the random walk up to step n. Let S̃_{j} =^{def} S_{j+n_{k}} − S_{n_{k}}. Then {S̃_{j}}_{j≥0} is again a simple symmetric random walk on ℤ^{2}, independent of {S_{n}}_{0≤n≤n_{k}}. If we define ξ̃(j, y) =^{def} ∑_{i=0}^{j} 1_{{S̃_{i}=y}}, the local time of the new random walk, then ξ_{k}(x) = ξ̃(n_{k+1} − n_{k}, x − S_{n_{k}}). By a change of variables y = x − S_{n_{k}},

∑_{x∈A_{k}} ξ_{k}^{2}(x) = ∑_{y∈ℤ^{2}} ξ̃^{2}(n_{k+1} − n_{k}, y)1_{{y+S_{n_{k}} ∈R_{n_{k}} }}.

Note that {1_{{y+S_{n_{k}} ∈R_{n_{k}} }}; y ∈ ℤ^{2}} is independent of {S̃_{j}}_{j≥0} (thus of its local times), and is distributed as {1_{{y∈R_{n_{k}} }}; y ∈ ℤ^{2}} (this is easily seen using time reversal). As a consequence,

𝔼 [ ( ∑_{x∈A_{k}} ξ_{k}^{2}(x))^{p/2} ] = 𝔼 [ ( ∑_{x∈ℤ^{2}} ξ̃^{2}(n_{k+1} − n_{k}, x)1_{{x∈R_{n_{k}} }})^{p/2} ] .

For the expression on the right hand side, we can apply Lemma 4.1 to n = n_{k+1} − n_{k} and ν = min((1 − ϱ)/(3ϱ), ε/(2p)). To see how φ_{n,ℓ,ν} (defined in (4.5)) behaves in this setting, we observe that by (4.11), if ∥x_{i}∥ < n^{1/2}(log n)^{ν} (for all 1 ≤ i ≤ ℓ), then

ℙ (x_{1} ∈ R_{n_{k}}, ⋯ x_{ℓ} ∈ R_{n_{k}}) ≤ sup_{∥x∥<2n^{1/2}(log n)^{ν}} (ℙ(x ∈ R_{n_{k}}))^{ℓ} ,

which, according to (4.15), is

≤ c_{29} (\frac{log\{n_{k}^{1/2}/(2n^{1/2}(log n)^{ν})\}}{log n_{k}})^{ℓ} ≤ c_{30} (\frac{log log n_{k}}{log n_{k}} )^{ℓ} .

(We have used (2.2) and the fact that (1 − ϱ)/(2ϱ) > ν). Therefore, by (4.4) (taking m = 2 and ℓ = p/2 there; this is the place where we need p to be an even integer),

(4.19) 𝔼 [ ( ∑_{x∈A_{k}} ξ_{k}^{2}(x))^{p/2} ] ≤ c_{31} n_{k}^{p/2}(log n_{k})^{p/2−p/(2ϱ)+ε}(log log n_{k})^{p/2}.

We now estimate the expression 𝔼(∑_{x∈A_{k}} ξ_{k}^{p}(x)∥x∥^{p−q}) on the right hand side of (4.18). For further applications in Section 5, we estimate 𝔼 {(∑_{x∈A_{k}} ξ_{k}^{p}(x)∥x∥^{α})^{ℓ}} for α ≥ 0 and integer ℓ ≥ 1.

By the same argument as before, we see that the random variable ∑_{x∈ℤ^{2}} ξ_{k}^{p}(x)∥x∥^{α} is distributed as ∑_{x∈ℤ^{2}} ξ̃^{p}(n_{k+1} − n_{k}, x) ∥x − S_{n_{k}}∥^{α}, where ξ̃ is independent of the variable S_{n_{k}}. Thus,

𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{p}(x)∥x∥^{α})^{ℓ} = 𝔼 ( ∑_{x∈ℤ^{2}} ξ̃^{p}(n_{k+1} − n_{k}, x) ∥x − S_{n_{k}}∥^{α})^{ℓ}
≤ c_{32} 𝔼 ( ∑_{x∈ℤ^{2}} ξ̃^{p}(n_{k+1} − n_{k}, x) ∥x∥^{α})^{ℓ}

+c_{32} 𝔼 {∥S_{n_{k}}∥^{αℓ} ( ∑_{x∈ℤ^{2}} ξ̃^{p}(n_{k+1} − n_{k}, x))^{ℓ}}

≤ c_{32} 𝔼 ( ∑_{x∈ℤ^{2}} ξ^{p}(n_{k+1} − n_{k}, x) ∥x∥^{α})^{ℓ}

+c_{33} n_{k}^{αℓ/2} 𝔼 ( ∑_{x∈ℤ^{2}} ξ^{p}(n_{k+1} − n_{k}, x))^{ℓ} .

We can apply (4.6) to see that for any ε > 0,

𝔼 ( ∑_{x∈ℤ^{2}} ξ^{p}(n_{k+1} − n_{k}, x) ∥x∥^{α})^{ℓ} ≤ c_{34} n_{k}^{ℓ+αℓ/2}(log n_{k})^{−c_{35} ℓ(1−ϱ)/ϱ+(p−1)ℓ+ε},
n_{k}^{αℓ/2} 𝔼 ( ∑_{x∈ℤ^{2}} ξ^{p}(n_{k+1} − n_{k}, x))^{ℓ} ≤ c_{36} n_{k}^{ℓ+αℓ/2}(log n_{k})^{−ℓ(1−ϱ)/ϱ+(p−1)ℓ+ε},

where c_{35} =^{def} 1 + α/2 ≥ 1. Note that −ℓ(1 − ϱ)/ϱ + (p − 1)ℓ = −ℓ/ϱ + pℓ. Consequently, for any ε > 0,

𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{p}(x) ∥x∥^{α})^{ℓ} ≤ c_{37} n_{k}^{ℓ+αℓ/2}(log n_{k})^{−ℓ/ϱ+pℓ+ε}, (4.20)

for some c_{37} = c_{37}(p, ℓ, α, ϱ, ε). This is a general estimate which we shall use for several times in Section 5.

Take α = p−q and ℓ = 1, and since ∑_{x∈A_{k}} ξ_{k}^{p}(x)∥x∥^{p−q} ≤ ∑_{x∈ℤ^{2}} ξ_{k}^{p}(x)∥x∥^{p−q}, we obtain:

𝔼 ( ∑_{x∈A_{k}} ξ_{k}^{p}(x) ∥x∥^{p−q}) ≤ c_{38} n_{k}^{1+(p−q)/2}(log n_{k})^{−1/ϱ+p+ε}.

Plugging this into (4.19) and (4.18) yields that, for any ε > 0,

𝔼 [ |V_{k} − U_{k}|^{p}] ≤ c_{39} n_{k}^{p/2}(log n_{k})^{p/2−p/(2ϱ)+ε}.

Lemma 2.2 now follows by means of an application of Chebyshev’s inequality and the Borel– Cantelli lemma. □

5 Proof of Lemma 2.3

We use the Skorokhod embedding schema (for more details, see Skorokhod, 1965) summarized as follows. Let X be a random variable with 𝔼(X) = 0 and 𝔼(|X|^{p}) < ∞ for some p ≥ 2, and let {W (t); t ≥ 0} be any given Wiener process starting from 0. The Skorokhod embedding ensures the existence of (finite) stopping time τ such that W (τ) is distributed as X, and that 𝔼(τ) = 𝔼(X^{2}). Moreover, for any a ∈ [1, p/2],

𝔼(τ^{a}) ≤ C(p) 𝔼(|X|^{2a}),

where C(p) ∈ (0, ∞) is a constant whose value depends only on p. By iterating the construction and using the strong Markov property, this yields an embedding of independent but not necessarily identically distributed variables into a Wiener process: if {X_{k}}_{k≥1} is a sequence of independent random variables, with 𝔼(X_{k}) = 0 and 𝔼(|X_{k}|^{p}) < ∞ for some p ≥ 2 and all k ≥ 1, then there exists a non-decreasing sequence of finite stopping times 0 = τ_{0} ≤ τ_{1} ≤ τ_{2} ≤ ⋯ with 𝔼(τ_{k} − τ_{k−1}) = 𝔼(X_{k}^{2}) for any k ≥ 1, such that

{X_{k}}_{k≥1} =^{(law)} {W (τ_{k}) − W (τ_{k−1})}_{k≥1} ,

where “ =^{(law)}” stands for identity in law. Moreover, for any k ≥ 1 and any 1 ≤ a ≤ p/2,

𝔼 ((τ_{k} − τ_{k−1})^{a}) ≤ C(p) 𝔼(|X_{k}|^{2a}).

Proof of Lemma 2.3. Let ℙ^{S}( ·) = ℙ( · |{S_{n}}_{n≥0}) as before, and let {V_{k}}_{k≥1} be the sequence of random variables defined in (2.4). Under ℙ^{S}, these are mean-zero independent variables with 𝔼^{S}(|V_{k}|^{p}) < ∞ (for all p ≥ 0), so that by the aforementioned Skorokhod-type embedding, there exist finite stopping times 0 = τ_{0} ≤ τ_{1} ≤ τ_{2} ≤ ⋯ satisfying 𝔼^{S}(τ_{k} − τ_{k−1}) = 𝔼^{S}(V_{k}^{2}) and 𝔼^{S}((τ_{k} − τ_{k−1})^{p}) ≤ c_{40} 𝔼^{S}(|V_{k}|^{2p}) for any k ≥ 1 and p ≥ 1, such that

{V_{k}}_{k≥1} =^{(law)} {W (τ_{k}) − W (τ_{k−1})}_{k≥1}.

Without loss of generality, we assume that {V_{k}}_{k≥1} = {W (τ_{k}) − W (τ_{k−1})}_{k≥1} (otherwise, by a usual coupling argument, we can work in an enlarged probability space, with redefined variables and processes; see for example page 53 of Berkes and Philipp, 1979 for more details). Therefore, for any ℓ ≥ 1,

W (τ_{ℓ−1}) = ∑_{k=1}^{ℓ−1} V_{k}. (5.1)

In order to show Lemma 2.3 we state and prove several lemmas.

Let

T_{k} =^{def} 𝔼^{S}(τ_{k} − τ_{k−1}) = 𝔼^{S}(V_{k}^{2}) = ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x)𝔼(Ŷ^{2}(x)).

Lemma 5.1 For any ε > 0, as ℓ → ∞ we have

τ_{ℓ−1} − ∑_{k=1}^{ℓ−1} T_{k} = o (n_{ℓ}(log n_{ℓ})^{3/2−1/(2ϱ)+ε}) , a.s. (5.2)

Proof. We can write

τ_{ℓ−1} − ∑_{k=1}^{ℓ−1} T_{k} = ∑_{k=1}^{ℓ−1} ((τ_{k} − τ_{k−1}) − T_{k}) =^{def} ∑_{k=1}^{ℓ−1} Δ_{k},

and note that {Δ_{k}}_{k≥1} is a sequence of independent mean-zero variables under ℙ^{S}. By Rosenthal’s inequality recalled in (4.16), for any p ≥ 4,

𝔼^{S} ( |τ_{ℓ−1} − ∑_{k=1}^{ℓ−1} T_{k}|^{p/2} ) ≤ c_{41} [ ∑_{k=1}^{ℓ−1} 𝔼^{S}(|Δ_{k}|^{p/2}) + ( ∑_{k=1}^{ℓ−1} 𝔼^{S}(Δ_{k}^{2}))^{p/4} ] .

Since 𝔼^{S}(|Δ_{k}|^{p/2}) ≤ c_{42} 𝔼^{S}((τ_{k} − τ_{k−1})^{p/2}) ≤ c_{42}c_{40} 𝔼^{S}(|V_{k}|^{p}), and 𝔼^{S}(Δ_{k}^{2}) ≤ 𝔼^{S}((τ_{k} − τ_{k−1})^{2}) ≤ c_{40} 𝔼^{S}(V_{k}^{4}), this leads to:

𝔼^{S} ( |τ_{ℓ−1} − ∑_{k=1}^{ℓ−1} T_{k}|^{p/2} ) ≤ c_{43} ∑_{k=1}^{ℓ−1} 𝔼^{S}(|V_{k}|^{p}) + c_{44} ( ∑_{k=1}^{ℓ−1} 𝔼^{S}(V_{k}^{4}))^{p/4} . (5.3)

At this stage, we need to estimate 𝔼^{S}(|V_{k}|^{p}). This can be done by another application of Rosenthal’s inequality in (4.16), for V_{k} is sum of independent mean-zero variables under ℙ^{S}:

𝔼^{S}(|V_{k}|^{p}) ≤ c_{45} ∑_{x∈ℤ^{2}} ξ_{k}^{p}(x)∥x∥^{p−q} + c_{46} ( ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{p/2} .

We have used (4.17) and the fact that ∑_{x∈ℤ^{2}} ξ_{k}^{p}(x) ≤ (∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{p/2}.

Plugging this into (5.3), and taking expectation (with respect to 𝔼) on both sides, we obtain:

𝔼 ( |τ_{ℓ−1} − ∑_{k=1}^{ℓ−1} T_{k}|^{p/2} ) ≤ c_{47} ∑_{k=1}^{ℓ−1} 𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{p}(x)∥x∥^{p−q}) + c_{48} ∑_{k=1}^{ℓ−1} 𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{p/2}

+c_{49} 𝔼 ( ∑_{k=1}^{ℓ−1} ∑_{x∈ℤ^{2}} ξ_{k}^{4}(x) ∥x∥^{4−q} + ∑_{k=1}^{ℓ−1} ( ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{2} )^{p/4}

(5.4)  =^{def} I_{5} + I_{6} + I_{7}.

We now assume that p > 4 is an even integer. By (4.20),

𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{p}(x) ∥x∥^{p−q}) ≤ c_{50} n_{k}^{1+(p−q)/2}(log n_{k})^{−1/ϱ+p+ε},
𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{p/2} ≤ c_{51} n_{k}^{p/2}(log n_{k})^{−p/(2ϱ)+p+ε},

which yields

I_{5} ≤ c_{52} I_{6} ≤ c_{53} ∑_{k=1}^{ℓ−1} n_{k}^{p/2}(log n_{k})^{−p/(2ϱ)+p+ε}
(5.5)  ≤ c_{54} n_{ℓ}^{p/2}(log n_{ℓ})^{1/ϱ−p/(2ϱ)+p−1+ε}.

To estimate I_{7}, we first note that

I_{7} ≤ c_{55} 𝔼 ( ∑_{k=1}^{ℓ−1} ∑_{x∈ℤ^{2}} ξ_{k}^{4}(x) ∥x∥^{4−q})^{p/4} + c_{56} 𝔼 ( ∑_{k=1}^{ℓ−1} ( ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{2} )^{p/4} .

Observe that for any b and α, {∑_{x∈ℤ^{2}} ξ_{k}^{b}(x) ∥x∥^{α}}_{k≥1} is a sequence of independent random variables. Now we make use of another inequality of Rosenthal, which can be found in Petrov (1995, p. 63): let p > 1 and let X_{1}, X_{2}, ⋯ be independent variables with 𝔼(|X_{k}|^{p}) < ∞ for all k ≥ 1. Then there exists a constant c(p) depending only on p, such that for all n ≥ 1,

𝔼 ( | ∑_{k=1}^{n} X_{k}|^{p} ) ≤ c(p) [ ∑_{k=1}^{n} 𝔼(|X_{k}|^{p}) + ( ∑_{k=1}^{n} 𝔼(|X_{k}|))^{p} ] .

Applying this inequality to X_{k} = ∑_{x∈ℤ^{2}} ξ_{k}^{4}(x) ∥x∥^{4−q} and to X_{k} = (∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{2}, respectively, and we obtain:

I_{7} ≤ c_{57} ∑_{k=1}^{ℓ−1} 𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{4}(x) ∥x∥^{4−q})^{p/4} + c_{58} (∑_{k=1}^{ℓ−1} 𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{4}(x) ∥x∥^{4−q}) )^{p/4}

+c_{59} ∑_{k=1}^{ℓ−1} 𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{p/2} + c_{60} (∑_{k=1}^{ℓ−1} 𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{2} )^{p/4} .

By applying (4.20) we can see that the dominating term is

(∑_{k=1}^{ℓ−1} 𝔼 ( ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x))^{2} )_{p/4} ≤ c_{61} ( ∑_{k=1}^{ℓ−1}(n_{k+1} − n_{k})^{2}(log n_{k})^{2+ε})^{p/4}
≤ c_{62} n_{ℓ}^{p/2}(log n_{ℓ})^{3p/4−p/(4ϱ)+pε/4},

which means

I_{7} = O (n_{ℓ}^{p/2}(log n_{ℓ})^{3p/4−p/(4ϱ)+pε/4}) , ℓ → ∞.

Combining this with (5.4) and (5.5) yields that, for any ε > 0,

𝔼 ( |τ_{ℓ−1} − ∑_{k=1}^{ℓ−1} T_{k}|^{p/2} ) ≤ c_{63} n_{ℓ}^{p/2}(log n_{ℓ})^{3p/4−p/(4ϱ)+ε}.

By choosing p sufficiently large and applying the Borel–Cantelli lemma, we obtain (5.2). □

The next lemma says that T_{k} is close to H_{k} defined by

H_{k} =^{def} σ^{2} ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x). (5.6)

Lemma 5.2 As ℓ → ∞,

∑_{k=1}^{ℓ−1}(H_{k} − T_{k}) = O(n_{ℓ}), a.s. (5.7)

Proof. By definition,

𝔼|H_{k} − T_{k}| = 𝔼 |∑_{x∈ℤ^{2}} ξ_{k}^{2}(x)(σ^{2} − 𝔼(Ŷ^{2}(x)))| = ∑_{x∈ℤ^{2}} 𝔼 (ξ_{k}^{2}(x)) (σ^{2} − 𝔼(Ŷ^{2}(x))).

For each x ∈ ℤ^{2},

σ^{2} − 𝔼(Ŷ^{2}(x)) = 𝔼 (Y^{2}(x)1_{{Y (x)>∥x∥}}) + [ 𝔼 (Y (x)1_{{Y (x)>∥x∥}})]^{2}
≤ \frac{c_{64}}{1 + ∥x∥^{q−2}} ,

whereas 𝔼 (ξ_{k}^{2}(x)) ≤ 𝔼 (ξ^{2}(n_{k+1}, x)). Therefore,

𝔼|H_{k} − T_{k}| ≤ c_{64} 𝔼 ( ∑_{x∈ℤ^{2}} \frac{ξ^{2}(n_{k+1}, x)}{1 + ∥x∥^{q−2}}) . (5.8)

It is easy to estimate the expression on the right hand side. Indeed, sup_{x∈ℤ^{2}} 𝔼(ξ^{2}(n, x)) ≤ c_{65} (log n)^{2}, cf. (4.2). On the other hand, by (4.6), for any ε > 0, there exists c_{66} = c_{66}(ε) such that 𝔼[∑_{x∈ℤ^{2}} ξ^{2}(n, x)] ≤ c_{66} n(log n)^{1+ε}. Accordingly,

𝔼 ( ∑_{x∈ℤ^{2}} \frac{ξ^{2}(n, x)}{1 + ∥x∥^{q−2}} ) = ∑_{∥x∥≤n^{1/2}} \frac{𝔼(ξ^{2}(n, x))}{1 + ∥x∥^{q−2}} + 𝔼 ( ∑_{∥x∥>n^{1/2}} \frac{ξ^{2}(n, x)}{1 + ∥x∥^{q−2}} )
≤ ∑_{∥x∥≤n^{1/2}} \frac{c_{65} (log n)^{2}}{1 + ∥x∥^{q−2}} + n^{1−q/2} 𝔼 ( ∑_{x∈ℤ^{2}} ξ^{2}(n, x))
≤ c_{67} n^{2−q/2}(log n)^{2} + c_{66} n^{2−q/2}(log n)^{1+ε}
(5.9)  ≤ c_{68} n^{2−q/2}(log n)^{2}.

Plugging this into (5.8) yields that

𝔼|H_{k} − T_{k}| = O (n_{k}^{2−q/2}(log n_{k})^{2}) , k → ∞.

By Chebyshev’s inequality,

ℙ(|H_{k} − T_{k}| ≥ n_{k+1} − n_{k}) ≤ c_{69} n_{k}^{1−q/2}(log n_{k})^{1+1/ϱ},

which is summable for k. Hence, by the Borel–Cantelli lemma, when k → ∞, H_{k} − T_{k} = O(n_{k+1} − n_{k}), a.s. This immediately yields (5.7). □

Finally, we need the following lemma to estimate ∑_{k=1}^{ℓ−1} H_{k}.

Lemma 5.3 For any ε > 0, as ℓ → ∞,

(5.10)  ∑_{k=1}^{ℓ−1} H_{k} − \frac{2σ^{2}}{π} n_{ℓ} log n_{ℓ} = o (n_{ℓ}(log n_{ℓ})^{1/(2ϱ)+ε}) ,  a.s.

Proof. We now estimate the first two moments of H_{k}. First, by writing ∑_{x∈ℤ^{2}} ξ^{2}(n, x) = ∑_{i=0}^{n} ∑_{j=0}^{n} 1_{{S_{i}=S_{j}}}, we have 𝔼 (∑_{x∈ℤ^{2}} ξ^{2}(n, x)) = n + 1 + 2 ∑_{i=0}^{n−1} ∑_{m=1}^{n−i} ℙ(S_{m} = 0), which, in view of (4.1), yields that

𝔼 ( ∑_{x∈ℤ^{2}} ξ^{2}(n, x)) = \frac{2}{π} n log n + O(n), n → ∞. (5.11)

For the second moment of ∑_{x∈ℤ^{2}} ξ^{2}(n, x), Bolthausen (1989) proved (cf. also Lewis, 1993) that

Var ( ∑_{x∈ℤ^{2}} ξ^{2}(n, x)) = O(n^{2}), n → ∞. (5.12)

Recall from (5.6) that H_{k} = σ^{2} ∑_{x∈ℤ^{2}} ξ_{k}^{2}(x), which is distributed as σ^{2} ∑_{x∈ℤ^{2}} ξ^{2}(n_{k+1} − n_{k}, x). Therefore, by (5.11),

∑_{k=1}^{ℓ−1} 𝔼(H_{k}) = \frac{2σ^{2}}{π} ∑_{k=1}^{ℓ−1}(n_{k+1} − n_{k}) log(n_{k+1} − n_{k}) + O (n_{ℓ})
= \frac{2σ^{2}}{π} n_{ℓ} log n_{ℓ} + O (n_{ℓ} log log n_{ℓ}) ,

whereas according to (5.12),

𝔼 ( ∑_{k=1}^{ℓ−1}(H_{k} − 𝔼(H_{k})))^{2} = ∑_{k=1}^{ℓ−1} Var(H_{k}) = O (n_{ℓ}^{2}(log n_{ℓ})^{1−1/ϱ}) .

Consequently,

𝔼 ( ∑_{k=1}^{ℓ−1} H_{k} − \frac{2σ^{2}}{π} n_{ℓ} log n_{ℓ})^{2} = O (n_{ℓ}^{2}(log log n_{ℓ})^{2}) , ℓ → ∞.

Now (5.10) follows by means of the Borel–Cantelli lemma. □

We are now ready to complete the proof of Lemma 2.3. Indeed, Lemmas 5.1, 5.2 and 5.3 together imply that for any ε > 0, almost surely when ℓ → ∞,

τ_{ℓ−1} − \frac{2σ^{2}}{π} n_{ℓ} log n_{ℓ} = o (n_{ℓ}(log n_{ℓ})^{2β+ε}) , (5.13)

where β is as in (2.9). Note that β < 1/2 and 2ϱ > 1.

Let us recall the following result in Csörgő and Révész (1981), p. 30: let t ↦ a_{t} be a non-decreasing function on ℝ_{+} such that 0 < a_{t} ≤ t and that t ↦ t/a_{t} is non-decreasing. Then

(5.14)  lim sup_{t→∞} \frac{sup_{0≤u≤a_{t}} sup_{0≤s≤t−a_{t}} |W (s + u) − W (s)|}{\sqrt{2a_{t}(log(t/a_{t}) + log log t)}} = 1,  a.s.

Applying (5.14) to t = (3σ^{2}/π)n_{ℓ} log n_{ℓ} and a_{t} = c_{70} t/(log t)^{1−2β−ε} (for ε ∈ (0, 1 − 2β), of course), and in view of (5.13), we obtain: for any ε > 0,

W (τ_{ℓ−1}) − W (\frac{2σ^{2}}{π} n_{ℓ} log n_{ℓ}) = o (n_{ℓ}^{1/2}(log n_{ℓ})^{β+ε}) , a.s.

In light of (5.1), this yields Lemma 2.3. □

6 Proof of Lemma 2.4

We start with two moment estimates for Z(n) and Z̃(n). Recall that 2 < q < 3.

Lemma 6.1 There exists a finite and positive constant c_{71} such that

𝔼 [(Z(n) − Ẑ(n))^{2}] ≤ c_{71} n^{2−q/2}(log n)^{2}, n ≥ 2.

Proof. By definition,

Z(n) − Ẑ(n) = ∑_{x∈ℤ^{2}} ξ(n, x) (Y (x)1_{{|Y (x)|>∥x∥}} − 𝔼 [Y (x)1_{{|Y (x)|>∥x∥}}]) .

Let ℙ^{S}(·) =^{def} ℙ( · |{S_{n}}_{n≥0}) be as before the conditional probability given the random walk. Then

𝔼^{S} [(Z(n) − Ẑ(n))^{2}]
= ∑_{x∈ℤ^{2}} ξ^{2}(n, x) {𝔼 [Y^{2}(x)1_{{|Y (x)|>∥x∥}}] − [𝔼 (Y (x)1_{{|Y (x)|>∥x∥}})]^{2}}
≤ c_{72} ∑_{x∈ℤ^{2}} \frac{ξ^{2}(n, x)}{1 + ∥x∥^{q−2}} .

Taking expectation (with respect to 𝔼) on both sides, and the lemma follows from (5.9). □

Lemma 6.2 For any p ≥ q and ε > 0, there exists a finite and positive constant c_{73} satisfying

𝔼 (|Ẑ(n)|^{p}) ≤ c_{73} n^{p/2}(log n)^{p/2+ε}, n ≥ 2.

Proof. By Rosenthal’s inequality (cf. (4.16)), for any p ≥ q,

𝔼^{S} (|Ẑ(n)|^{p}) ≤ c_{74} ∑_{x∈ℤ^{2}} ξ^{p}(n, x) 𝔼(|Ŷ(x)|^{p}) + c_{74} ( ∑_{x∈ℤ^{2}} ξ^{2}(n, x) 𝔼(Ŷ^{2}(x)))^{p/2}
≤ c_{75} ∑_{x∈ℤ^{2}} ξ^{p}(n, x) ∥x∥^{p−q} + c_{76} ( ∑_{x∈ℤ^{2}} ξ^{2}(n, x))^{p/2} .

Taking expectation (with respect to 𝔼) on both sides, and applying (4.6) to α = p − q and α = 0 respectively, we obtain: for any ε > 0,

𝔼 (|Ẑ(n)|^{p}) ≤ c_{77} n^{1+(p−q)/2}(log n)^{p−1+ε} + c_{78} n^{p/2}(log n)^{p/2+ε}
≤ c_{79} n^{p/2}(log n)^{p/2+ε},

as desired. □

We have now all the ingredients to prove Lemma 2.4.

Proof of Lemma 2.4. Taking t = b_{n_{ℓ+1}} and a_{t} = c_{80} t/(log t)^{(1−ϱ)/ϱ} in (5.14) yields the estimate (2.12). So we only have to check (2.11). We use the following maximal inequality due to Bolthausen (1989): let X_{m} =^{def} ∑_{x∈ℤ^{2}} ξ^{2}(m, x), then for any a > \sqrt{2} σ and any m ≥ 1,

ℙ ( max_{0≤i≤m} Z(i) ≥ a\sqrt{X_{m}} ) ≤ 2ℙ (Z(m) ≥ (a − \sqrt{2} σ)\sqrt{X_{m}} ) .

Therefore, writing n =^{def} n_{ℓ+1} − n_{ℓ} for brevity,

I_{8} =^{def} ℙ ( max_{n_{ℓ}≤j≤n_{ℓ+1}}(Z(j) − Z(n_{ℓ})) > (n_{ℓ+1} − n_{ℓ})^{1/2}(log n_{ℓ})^{1/2+ε})
≤ ℙ ( max_{0≤i≤n} Z(i) > n^{1/2}(log n)^{1/2+ε})
≤ ℙ ( max_{0≤i≤n} Z(i) > (log n)^{ε}\sqrt{\frac{π}{3} X_{n}} ) + ℙ (X_{n} > \frac{3}{π} n log n)
≤ 2ℙ (Z(n) > (\sqrt{π/3} (log n)^{ε} − \sqrt{2} σ)\sqrt{X_{n}} ) + ℙ (X_{n} > \frac{3}{π} n log n) .

When n is sufficiently large, \sqrt{π/3} (log n)^{ε} − \sqrt{2} σ ≥ \sqrt{π} (log n)^{ε}/2. Thus

I_{8} ≤ 2ℙ (Z(n) > \frac{\sqrt{π} (log n)^{ε}}{2} \sqrt{X_{n}} ) + ℙ (X_{n} > \frac{3}{π} n log n)
≤ 2ℙ (Z(n) > \frac{1}{2}n^{1/2}(log n)^{1/2+ε})

+2ℙ (X_{n} < \frac{n log n}{π}) + ℙ (X_{n} > \frac{3}{π} n log n)

(6.1)  =^{def} 2I_{9} + 2I_{10} + I_{11}.

Observe that by Lemmas 6.1 and 6.2, for any p ≥ 2 and ε > 0,

I_{9} ≤ ℙ (Z(n) − Ẑ(n) > \frac{1}{4}n^{1/2}(log n)^{1/2+ε})

+ℙ (Ẑ(n) > \frac{1}{4}n^{1/2}(log n)^{1/2+ε})

≤ 16c_{71} n^{1−q/2}(log n)^{1−2ε} + c_{81} (log n)^{−pε/2}
≤ c_{82} (log n)^{−pε/2},

whereas according to (5.11) and (5.12),

I_{10} + I_{11} = ℙ (|X_{n} − \frac{2}{π} n log n| > \frac{n log n}{π}) ≤ \frac{c_{83} n^{2}}{[(n log n)/π]^{2}} = \frac{π^{2}c_{83}}{(log n)^{2}} .

We can choose p sufficiently large such that pε/2 ≥ 2. Plugging these estimates into (6.1) yields

ℙ ( max_{n_{ℓ}≤j≤n_{ℓ+1}}(Z(j) − Z(n_{ℓ})) > (n_{ℓ+1} − n_{ℓ})^{1/2}(log n_{ℓ})^{1/2+ε}) ≤ \frac{c_{84}}{(log(n_{ℓ+1} − n_{ℓ}))^{2}} ,

which is summable for ℓ. By the Borel–Cantelli lemma, and since ε > 0 is arbitrary, we have, almost surely for ℓ → ∞,

max_{n_{ℓ}≤j≤n_{ℓ+1}}(Z(j) − Z(n_{ℓ})) = o ((n_{ℓ+1} − n_{ℓ})^{1/2}(log n_{ℓ})^{1/2+ε})
= o (n_{ℓ}^{1/2}(log n_{ℓ})^{1−1/(2ϱ)+ε}) .

The same estimate holds for (−Z) in place of Z. This yields (2.11), and completes the proof of Lemma 2.4. □

Acknowledgements

We are indebted to the 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. Cooperation between the authors was supported by the joint French–Hungarian Intergovernmental Grant “Balaton” (grant no. F25/97).

References

[1] Berkes, I., Philipp, W., 1979. Approximation theorems for independent and weakly dependent random vectors. Ann. Probab. 7, 29–54.

[2] Bolthausen, E., 1989. A central limit theorem for two-dimensional random walks in random sceneries. Ann. Probab. 17, 108–115.

[3] Borodin, A.N., 1980. Limit theorems for sums of independent random variables defined on a two-dimensional random walk. LOMI Preprint E-6-80, Steklov Institute, Leningrad.

[4] Csáki, E., König, W., Shi, Z., 1999. An embedding for the Kesten–Spitzer random walk in random scenery. Stochastic Process. Appl. 82, 283–292.

[5] Csörgő, M., Révész, P., 1981. Strong Approximations in Probability and Statistics. Academic, New York.

[6] Erdős, P., Taylor, S.J., 1960. Some problems concerning the structure of random walk path. Acta Math. Acad. Sci. Hung. 11, 137–162.

[7] Kesten, H., Spitzer, F., 1979. A limit theorem related to a new class of self similar processes. Z. Wahrsch. Verw. Gebiete 50, 5–25.

[8] Khoshnevisan, D., Lewis, T.M., 1998. A law of the iterated logarithm for stable processes in random scenery. Stochastic Process. Appl. 74, 89–121.

[9] Lewis, T.M., 1993. A law of the iterated logarithm for random walk in random scenery with deterministic normalizers. J. Theoretical Probab. 6, 209–230.

[10] Petrov, V.V., 1995. Limit Theorems of Probability Theory. Clarendon Press, Oxford.

[11] Révész, P., 1990. Random Walk in Random and Non–Random Environments. World Scientific, Singapore.

[12] Révész, P., Shi, Z., 2000. Strong approximation of spatial random walk in random scenery. Stochastic Process. Appl. 88, 329–345.

[13] Skorokhod, A.V., 1965. Studies in the Theory of Random Processes. Addison-Wesley, Reading.