The Annals of Probability 2001, Vol. 00, No. 00, 000–000

Laws of the iterated logarithm for the range of random walks in two and three dimensions

By Richard F. Bass ^{1} and Takashi Kumagai^{2} University of Connecticut and Kyoto University

Let S_{n} be a random walk in Z^{d} and let R_{n} be the range of S_{n}. We prove an almost sure invariance principle for R_{n} when d = 3 and a law of the iterated logarithm for R_{n} when d = 2.

1. Introduction. Let S_{n} be a random walk taking values in Z^{d} and let R_{n} be the range of S_{n}. That means that R_{n} is the number of points visited at least once by S_{k}, k ≤ n. The subject of the asymptotics of R_{n} has a long history in probability. Despite this, the problem of proving a law of the iterated logarithm for dimensions d = 2, 3 has remained open, even for the case of simple symmetric random walk. Our purpose in this paper is to provide such LIL’s.

The strong law of large numbers for R_{n} was proved in Dvoretzky-Erdös [5]. The central limit theorem for d ≥ 3 can be found in Jain-Pruitt [13] and [16], for example, while the case d = 2 was proved by Le Gall [18]. See Le Gall-Rosen [20] for a central limit theorem when the random walk is in the domain of attraction of a stable law. The LIL for d ≥ 4 can be found in Jain-Pruitt [14]. An almost sure

Received 000

1Supported in part by NSF 9988496 and Grant-in-Aid for Scientific Research (A)(1) 11304003 of Japan.

2Supported in part by Grant-in-Aid for Scientific Research (C)(2) 11640713 of Japan.

AMS 2000 subject classifications. Primary 60J10; Secondary 60F15, 60G17

Key words and phrases. Range of random walk, Law of the iterated logarithm, Almost sure invariance principle, Intersection local time.

2 R. F. BASS AND T. KUMAGAI

invariance principle for R_{n} in the case d ≥ 4 was recently proved by Hamana [8]. For information on large deviations, see Donsker-Varadhan [4] and Hamana-Kesten [10], [11]. Questions about the range have as analogues questions about the volume of the Wiener sausage. See, for example, Le Gall [19].

In this paper we first consider the case of dimension 3. We show that under some moment assumptions on S_{n} an almost sure invariance principle holds. Changing the probability space if necessary, we show there exists a Brownian motion B_{t}, an explicit constant σ, and another constant q < 1/2 such that

\frac{R_{n} − ER_{n}}{σ} − B_{n log n} = O(\sqrt{n}(log n)^{q}) a.s.

Our rate is quite poor and can probably be improved. However our results are strong enough to yield the analogues of the usual LIL’s for Brownian motion. For example, we show

lim sup_{n→∞} \frac{R_{n} − ER_{n}}{\sqrt{n log n log log n}} = c_{1.1}, a.s.

where c_{1.1} is an explicitly determined constant. The extra log n term in the almost sure invariance principle and in the LIL is a consequence of the fact that Var R_{n} ≍ n log n, where f_{n} ≍ g_{n} means the ratio f_{n}/g_{n} is bounded above and below by positive constants not depending on n.

The case d = 2 is considerably harder. Under somewhat stronger assumptions on the random walk, we show there exists a constant c_{1.2} such that

lim sup_{n→∞} \frac{R_{n} − ER_{n}}{n log log log n/(log n)^{2}} = c_{1.2}, a.s.

In the case d = 2 it is known (see [15]) that Var R_{n} ≍ n^{2}/(log n)^{4}, which explains part of the rate. The presence of a log log log n term instead of the expected log log n term is perhaps surprising.

LIL FOR THE RANGE OF RANDOM WALKS 3

In Section 2 we give a precise statement of our results. We prove the three dimensional case in Section 3 and the two dimensional case in Section 4. Overviews of the proofs of Theorems 2.1 and 2.5 are given near the beginning of Section 3 and after the statements of Propositions 4.1 and 4.4. Throughout the paper c_{n.i} will denote the i-th fixed constant in Section n; other positive finite constants c_{i} will be also be used, but will be fixed within a given proof.

2. Main theorems and known results In this section, we will recall several known results and state our main theorems. We first explain the setting. Let {X_{j}} be an i.i.d. sequence of random variables taking values in Z^{d} (d = 3 in Subsection 2.1 and d = 2 in Subsection 2.2) such that EX_{1} = 0 and E[|X_{1}|^{2+δ}] < ∞ for some δ > 0 and set S_{n} = ∑_{j=1}^{n} X_{j}. Let R_{n} be the range of S_{0}, ⋯, S_{n}, i.e. R_{n} is the cardinality of the set {S_{0}, S_{1}, ⋯, S_{n}}.

Define

p = P (S_{k} ≠ 0 for all k ∈ N).

Throughout this paper, we assume p < 1 as otherwise R_{n} = n + 1 a.s. and there is no interest in this case. We also assume that the random walk {S_{n}} is genuinely d-dimensional, i.e., if

R^{+} = {x ∈ Z^{d} : P^{0}(S_{n} = x) > 0 for some n ≥ 0},
R̂ = {x ∈ Z^{d} : x = y − z for some y ∈ R^{+} and z ∈ R^{+}},

then R̂ is d-dimensional. When R̂ is a proper subgroup of Z^{d}, it is isomorphic to Z^{d}, so by a suitable transformation we can suppose R̂ = Z^{d}, i.e., the transformed random walk is aperiodic. As the transformation does not change R_{n} and p, there is no loss of generality in considering the case R̂ = Z^{d}.

4 R. F. BASS AND T. KUMAGAI

For sequences {f_{n}} and {g_{n}}, we write f_{n} ∼ g_{n} when lim_{n→∞} f_{n}/g_{n} = 1. Define log_{2} a = log log a and log_{3} a = log log log a.

2.1. Main Theorem: Three dimensional case When d = 3, our main theorem is an almost sure invariance principle for R_{n}.

Theorem 2.1. Suppose d = 3. Let q = \frac{15}{32}. Changing the probability space if necessary, there exist a one-dimensional Brownian motion and a constant σ > 0 such that

(2.1) \frac{R_{n} − ER_{n}}{σ} − B_{n log n} = O(\sqrt{n}(log n)^{q}) a.s.

As we will see in the proof, σ^{2} = 2p^{4}(2π)^{−2}|Q|^{−1} where Q is the covariance matrix for X_{1}.

Using the laws of the iterated logarithm for Brownian motion, we have the following LIL’s for R_{n} as an immediate corollary of the theorem.

Corollary 2.2. Suppose d = 3. The following hold P -a.s.:

lim sup_{n→∞} \frac{R_{n} − ER_{n}}{\sqrt{n log n log_{2} n}} = \sqrt{2}σ,

lim inf_{n→∞} \frac{R_{n} − ER_{n}}{\sqrt{n log n log_{2} n}} = −\sqrt{2}σ,

lim inf_{n→∞} \frac{sup_{m≤n} |R_{m} − ER_{m}|}{\sqrt{n log n/ log_{2} n}} = \frac{πσ}{\sqrt{8}}.

An analogue of Strassen’s LIL also holds.

Remark 2.3. Let Q_{n}^{(p)} be the number of distinct sites that {S_{i} : 0 < i ≤ n} has visited exactly p times. Y. Hamana [9] has informed us that by using our arguments and some estimates for Q_{n}^{(p)}, one can prove the analogue of Theorem 2.1 for Q_{n}^{(p)} (with a different constant for σ). We will briefly sketch the argument in Remark 3.4.

2.2. Main Theorem: Two dimensional case When d = 2, our main theorem is a law of the iterated logarithm for R_{n}. In this case, we need the following further assumptions for X_{1}.

Assumption 2.4.

(a) X_{1} is mean 0 and has covariance matrix equal to σI for some σ > 0.

(b) X_{1} is bounded: there exists Λ > 0 such that P (|X_{1}| > Λ) = 0.

We note that (a) is equivalent to (H3) in [18]. Under these conditions, we have the following.

Theorem 2.5. Suppose d = 2. There exists c_{2.1} > 0 such that the following holds P -a.s.

(2.2)  lim sup_{n→∞} \frac{sup_{j≤n}(R_{j} − ER_{j})}{n log_{3} n/(log n)^{2}} = c_{2.1}.

Remark 2.6. 1) As we will see from the proof, the same result holds with R_{n} − ER_{n} instead of sup_{j≤n}(R_{j} − ER_{j}).

2) We do not know the exact value of c_{2.1}. Also, we have not obtained the LIL for the lim inf of R_{n} − ER_{n}.

2.3. Known Results Before giving the proofs, we recall some known results. The results in this subsection hold for aperiodic random walks with EX_{1} = 0 and E[|X_{1}|^{2}] < ∞. Further estimates will be introduced in the next section.

For the three dimensional case, the following is known.

ER_{n} = pn + O(\sqrt{n}) (2.3)

6 R. F. BASS AND T. KUMAGAI

E[(R_{n} − ER_{n})^{4}] = O(n^{2}(log n)^{2}) (2.4)

\frac{R_{n} − ER_{n}}{\sqrt{n log n}} → c_{2.2}N (2.5)

where N is the standard normal distribution. The convergence in (2.5) is in the sense of distribution. (2.3) was proved by Dvoretzky-Erdös [5], (2.4) is from Jain-Pruitt [13] (Theorem 4), and (2.5) is from Jain-Pruitt [13].

For the two dimensional case, the following is known.

ER_{n} = κ\frac{n}{log n} + O(\frac{n}{(log n)^{2}} ) (2.6)

Var (R_{n}) = O(\frac{n^{2}}{(log n)^{4}} ) (2.7)

\frac{(log n)^{2}}{n} (R_{n} − ER_{n}) → −c_{2.3}γ (2.8)

where γ is renormalized self-intersection local time of planar Brownian motion and κ is a constant. The convergence in (2.8) is again in distribution. (2.6) is from Jain-Pruitt [12] Lemma 2.6 with the estimates (2.2) and (2.3) in [7], (2.7) is from Jain-Pruitt [15] (Theorem 4.2) , and (2.8) is from Le Gall [18].

3. Proof: Three dimensional case In this section, we will prove Theorem 2.1. We set ⟨x⟩ = n if x ∈ (n − \frac{1}{2}, n + \frac{1}{2}] throughout the paper. Let α be a positive constant that we will choose later. We form a sequence {n_{j}} of positive integers by taking all positive integers in each interval [2^{k}, 2^{k+1}) which are of the form 2^{k} + ⟨i2^{k}/k^{α}⟩, k = 1, 2, …, i = 0, 1, …, k^{α}. This choice of the sequence will be important in the proof. Let n_{0} = 0. For 2^{k} ≤ n_{i} < 2^{k+1}, we have 2^{k}/k^{α} − 1 ≤ n_{i+1} − n_{i} ≤ 2^{k}/k^{α} + 1, so that the following hold:

lim_{n→∞} n_{i+1}/n_{i} = 1, n_{i+1} − n_{i} = O(n_{i}/(log n_{i})^{α}).

LIL FOR THE RANGE OF RANDOM WALKS 7

We write #A for the cardinality of the set A. For any random variable Y we write \overline{Y} for Y − EY. Let

U_{j} = #{S_{k} : k ∈ [n_{j−1}, n_{j})}

Fix i < j and let

V_{j} = V_{j}^{(i)} = #({S_{k} : k ∈ [n_{j−1}, n_{j})} ∩ {S_{k} : k ∈ [n_{j}, n_{i}]})

Then R_{n_{i}} = ∑_{j=1}^{i} U_{j} − ∑_{j=1}^{i−1} V_{j}, so that

\overline{R}_{n_{i}} = ∑_{j=1}^{i} \overline{U}_{j} − ∑_{j=1}^{i−1} \overline{V}_{j}. (3.1)

Let us now give a overview of the proof of Theorem 2.1. We will need three lemmas (Lemma 3.1, Lemma 3.2 and Lemma 3.3) for the proof. Using Lemma 3.1, we show

∑_{j=1}^{i−1} \overline{V}_{j} = o(\sqrt{n_{i}}(log n_{i})^{q}) a.s.

As the \{\overline{U}_{j}\}_{j=1}^{i} are independent, by Skorohod embedding ([22]) there exist a Brownian motion B_{t} and a sequence of non-negative independent random variables {T_{j}}_{j=1}^{∞} such that

\frac{1}{σ} ∑_{j=1}^{i} \overline{U}_{j} ∼^{L} B(∑_{k=1}^{i} T_{k}).

We then use Lemma 3.2 and after some computations derive

B(∑_{k=1}^{i} T_{k}) = B(n_{i} log n_{i}) + O(\sqrt{n_{i}}(log n_{i})^{q}) a.s.

Thus, by (3.1), we have (2.1) for the subsequence {n_{i}}. Lemma 3.3 will then be used to show the result for all n.

Before stating the lemmas, we give some notation. For x, y ∈ Z^{3}, n ≥ 0, and A ⊂ Z^{3}, define

P^{(n)}(x, y) = P^{x}(S_{n} = y),

8 R. F. BASS AND T. KUMAGAI

P_{A}^{(n)}(x, y) = P^{x}(S_{1}, ⋯, S_{n−1} ∉ A, S_{n} = y),

F (x, y) = ∑_{n=1}^{∞} P_{y}^{(n)}(x, y) = P^{x}(T_{y} < ∞),

G_{n}(x, y) = ∑_{k=0}^{n} P^{(k)}(x, y),

G(x, y) = ∑_{k=0}^{∞} P^{(k)}(x, y),

where T_{A} = inf{n > 0 : S_{n} ∈ A}.

Let

Z_{i}^{n} = 1_{{S_{i}≠S_{i+1},···,S_{i}≠S_{n}}} for 0 ≤ i < n, Z_{n}^{n} = 1,
Z_{i} = 1_{{S_{i}≠S_{i+1},S_{i}≠S_{i+2},···}} for i ≥ 0,
W_{i}^{n} = Z_{i}^{n} − Z_{i} for 0 ≤ i < n,
Y_{n} = ∑_{i=0}^{n−1} Z_{i},
W_{n} = ∑_{i=0}^{n−1} W_{i}^{n}.

Note that R_{n} = ∑_{i=0}^{n} Z_{i}^{n} = Y_{n} + W_{n} + 1. We now state the lemmas. The proofs will be given at the end of this section.

Lemma 3.1. For non-negative integers a < b, let V_{a,b} = #({S_{j} : j ∈ [a, b)} ∩ {S_{k} : k ∈ [b, ∞)}). There exists c_{3.1} > 0 such that E[V_{a,b}^{4}] ≤ c_{3.1}(b − a)^{2}. (3.2) Further, for each l ≥ 3, there exists c_{3.2} = c_{3.2}(l) > 0 such that E[(W_{n})^{2l}] ≤ c_{3.2}n^{l}(log n)^{l}. (3.3)

Lemma 3.2. There exists σ > 0 such that for all n ∈ N, (3.4) Var (R_{n}) = σ^{2}n log n + O(n\sqrt{log n}).

LIL FOR THE RANGE OF RANDOM WALKS 9

Further, for each l ∈ N, E[|R_{n} − ER_{n}|^{l}] = O((n log n)^{l/2}). (3.5)

Lemma 3.3. (a) For non-negative integers a < b and l, there exists c_{3.3} = c_{3.3}(l) such that

E[|(R_{b} − ER_{b}) − (R_{a} − ER_{a})|^{l}] ≤ c_{3.3}((b − a) log(b − a))^{l/2}.

(b) For non-negative integers a < b and l > 2, there exists c_{3.4} = c_{3.4}(l) such that

P ( max_{a≤n≤b} |(R_{n} − ER_{n}) − (R_{a} − ER_{a})| > λ) ≤ c_{3.4} \frac{((b − a) log(b − a))^{l/2}}{λ^{l}} .

We now give a proof of Theorem 2.1, assuming the above lemmas.

Proof of Theorem 2.1. Let

α = \frac{9}{32}, β = \frac{15}{32} − ϵ, γ = \frac{7}{8}, ϵ = 10^{−6}.

Recall that for i fixed and for j ≤ i, V_{j} = V_{j}^{(i)} is the cardinality of {S_{k} : k ∈ [n_{j−1}, n_{j})} ∩ {S_{k} : k ∈ [n_{j}, n_{i}]}. We have

P (∑_{j=1}^{i} V_{j} ≥ c_{1}\sqrt{n}_{i}(log n_{i})^{β}) ≤ \frac{E[(∑_{j=1}^{i} V_{j})^{4}]}{c_{1}^{4}n_{i}^{2}(log n_{i})^{4β}}. (3.6)

By Hölder’s inequality and (3.2),

E[V_{j_{1}}V_{j_{2}}V_{j_{3}}V_{j_{4}}] ≤ \{ ∏_{m=1}^{4} E[V_{j_{m}}^{4}]\}^{1/4} ≤ c_{2} ∏_{m=1}^{4} \sqrt{n_{j_{m}} − n_{j_{m}−1}}.

Thus, when 2^{k_{0}} ≤ n_{i} < 2^{k_{0}+1},

E[(∑_{j=1}^{i} V_{j})^{4}] = ∑_{j_{1},j_{2},j_{3},j_{4}=1}^{i} E[V_{j_{1}}V_{j_{2}}V_{j_{3}}V_{j_{4}}] ≤ c_{3} ∑_{j_{1},j_{2},j_{3},j_{4}=1}^{i} ∏_{m=1}^{4} \sqrt{n_{j_{m}} − n_{j_{m}−1}}
≤ c_{4}(∑_{k=1}^{k_{0}} k^{α}\sqrt{2^{k}/k^{α}})^{4} ≤ c_{5}k_{0}^{2α}2^{2k_{0}}

where in the last inequality we use the elementary fact that

∑_{k=1}^{n} k^{p}q^{k} ∼ n^{p}q^{n} (3.7)

10 R. F. BASS AND T. KUMAGAI

as n → ∞ for each p > 0, q > 1. Thus the right hand side of (3.6) is bounded from above by c_{5}k_{0}^{2α−4β}. The number of n_{i} in [2^{k_{0}}, 2^{k_{0}+1}) is less than c_{6}k_{0}^{α}. Since 3α − 4β < −1, then ∑_{k_{0}=1}^{∞} k_{0}^{3α−4β} < ∞, and by Borel-Cantelli we see that

(3.8)  lim sup_{i→∞} \frac{∑_{j=1}^{i} V_{j}^{(i)}}{\sqrt{n}_{i}(log n_{i})^{β}} ≤ c_{1} a.s.

Since α/2 < β and EV_{j} ≤ c_{7}\sqrt{n_{j} − n_{j−1}}, we have by similar calculations that

∑_{j=1}^{i} EV_{j} ≤ c_{8} ∑_{k=1}^{k_{0}} k^{α}\sqrt{2^{k}/k^{α}} ≤ k_{0}^{α/2}2^{k_{0}/2} = o(\sqrt{n}_{i}(log n_{i})^{β}).

Thus we obtain

(3.9)  lim sup_{i} \frac{| ∑_{j=1}^{i−1}(V_{j} − EV_{j})|}{\sqrt{n}_{i}(log n_{i})^{β}} ≤ c_{9} a.s.

Set H_{j} = (U_{j} − EU_{j})/σ. As the {H_{j}}_{j=1}^{∞} are independent there exist ([22]) a Brownian motion B_{t} and a sequence of non-negative independent random variables {T_{j}}_{j=1}^{∞} such that

{B(∑_{k=1}^{j} T_{k}) − B(∑_{k=1}^{j−1} T_{k})}_{j} ∼^{L} {H_{j}}_{j} (3.10)

E[T_{j}] = E[|H_{j}|^{2}] (3.11) E[T_{j}^{l}] ≤ c_{10}E[|H_{j}|^{2l}] for all l ≥ 2. (3.12)

From (3.10), we see that ∑_{j=1}^{i} H_{j} is equal in law to B(∑_{k=1}^{i} T_{k}).

We now prove

(3.13)  lim sup_{i→∞} \frac{∑_{j=1}^{i}(T_{j} − ET_{j})}{n_{i}(log n_{i})^{γ}} < ∞ a.s.

It is clear that ∑_{j=1}^{i} \overline{T}_{j} is a martingale. So by Doob’s inequality, for each l ∈ N

(3.14) P (sup_{r≤i} | ∑_{j=1}^{r} \overline{T}_{j}| ≥ n_{i}(log n_{i})^{γ}) ≤ c_{11} \frac{E[(∑_{j=1}^{i} \overline{T}_{j})^{2l}]}{n_{i}^{2l}(log n_{i})^{2lγ}}.

Note that

E[(∑_{j=1}^{i} \overline{T}_{j})^{2l}] = ∑_{j_{1},j_{2},···,j_{2l}=1}^{i} E[\overline{T}_{j_{1}} ⋯ \overline{T}_{j_{2l}}]

LIL FOR THE RANGE OF RANDOM WALKS 11

(3.15)  = ∑_{(∗)} \frac{(2l)!}{ζ_{1}! ⋯ ζ_{p}!} ∑_{j_{1},···,j_{p}=1}^{i} E[\overline{T} _{j_{1}}^{ζ_{1}}] ⋯ E[\overline{T} _{j_{p}}^{ζ_{p}}]

where (∗) ranges over all (ζ_{1}, ⋯, ζ_{p}), 1 ≤ p ≤ 2l, such that ζ_{i} ≥ 2 for all 1 ≤ i ≤ p and ∑_{t=1}^{p} ζ_{t} = 2l. The second equality holds because E[\overline{T}_{j_{1}} ⋯ \overline{T}_{j_{2l}}] = 0 when one of j_{1}, j_{2}, ⋯, j_{2l} is different from all the others, as the \{\overline{T}_{j}\}_{j} are independent and mean 0.

Observe also that

|E[\overline{T} _{j}^{m}]| = |ET_{j}^{m} − mET_{j}^{m−1}ET_{j} + ⋯ + (−1)^{m}(ET_{j})^{m}|
≤ c_{12}{(n_{j} − n_{j−1}) log(n_{j} − n_{j−1})}^{m}

by (3.11), (3.12) and (3.5).

Then when 2^{k_{0}} ≤ n_{i} < 2^{k_{0}+1}

∑_{j=1}^{i} |E[\overline{T} _{j}^{m}]| ≤ c_{12} ∑_{j=1}^{i}\{(n_{j} − n_{j−1}) log(n_{j} − n_{j−1})\}^{m}
≤ c_{13} ∑_{k=1}^{k_{0}} k^{α} \frac{2^{km}}{k^{αm}} k^{m} ≤ c_{14}k_{0}^{m(1−α)+α}2^{mk_{0}},

where we used (3.7) for the last inequality. (Note that c_{12} = c_{12}(m), c_{13} = c_{13}(m), c_{14} = c_{14}(m) depend on m.) Using this, (3.15) is estimated from above by c_{15} ∑_{(∗)} k_{0}^{2l(1−α)+αp}2^{2lk_{0}} for some c_{15} = c_{15}(l) > 0. As the term is the biggest when p = l, combining with (3.14),

∑_{i=1}^{∞} P (sup_{r≤i} | ∑_{j=1}^{r} \overline{T}_{j}| ≥ n_{i}(log n_{i})^{γ}) ≤ c_{16} ∑_{k_{0}=1}^{∞} k_{0}^{α} \frac{k_{0}^{l(2−α)}2^{2lk_{0}}}{2^{2lk_{0}}k_{0}^{2lγ}} = c_{16} ∑_{k_{0}=1}^{∞} k_{0}^{2l(1− \frac{α}{2} −γ)+α},

for some c_{16} = c_{16}(l) > 0. The last term is finite if we choose l large enough so that 2l(1 − \frac{α}{2} − γ) + α < −1. This proves (3.13).

Let J_{i} = ∑_{k=1}^{i} T_{k}. Let ξ_{i} = n_{i}(log n_{i})^{γ}. Then,

P (|B(J_{i}) − B(EJ_{i})| > ξ_{i}^{1/2}(log n_{i})^{ϵ}; |J_{i} − EJ_{i}| ≤ 2ξ_{i})

12 R. F. BASS AND T. KUMAGAI

≤ P (  sup_{EJ_{i}−2ξ_{i}≤s,t≤EJ_{i}+2ξ_{i}} |B_{t} − B_{s}| ≥ ξ_{i}^{1/2}(log n_{i})^{ϵ})
≤ c_{17}e^{−(log n_{i})^{2ϵ}/2}.

There are at most c_{18}k_{0}^{α} values of n_{i} such that 2^{k_{0}−1} ≤ n_{i} ≤ 2^{k_{0}}, so the above is summable in k_{0}. Combining with (3.13), we deduce

B(J_{i}) − B(EJ_{i}) = O(n_{i}^{1/2}(log n_{i})^{(γ/2)+ϵ}).

By (3.11) ∑_{j=1}^{i} ET_{j} = ∑_{j=1}^{i}(n_{j} − n_{j−1}) log(n_{j} − n_{j−1}) + O(n_{i}\sqrt{log n_{i}}) and we have by elementary computations that

∑_{j=1}^{i} ET_{j} = n_{i} log n_{i} + o(n_{i}(log n_{i})^{2β−ϵ}).

We thus have

(3.16) B(∑_{k=1}^{i} T_{k}) − B(n_{i} log n_{i}) = O(\sqrt{n}_{i}(log n_{i})^{β}) a.s.

Putting together what we have so far, we have

(R_{n_{i}} − ER_{n_{i}}) − B(n_{i} log n_{i}) = O(\sqrt{n}_{i}(log n_{i})^{β}) a.s.

It remains to take care of values of n that are not one of the n_{i}. By Lemma 3.3 (b),

P ( max_{{n_{i}≤n≤n_{i+1} \atop n∈N}} |\overline{R}_{n} − \overline{R}_{n_{i}}| > \sqrt{n}_{i}(log n_{i})^{β})

≤ c_{19} \frac{((n_{i+1} − n_{i}) log(n_{i+1} − n_{i}))^{l/2}}{(n_{i})^{l/2}(log n_{i})^{βl}}
≤ c_{20}k^{l(1−α−2β)/2}

if 2^{k} ≤ n_{i} ≤ 2^{k+1}. There are at most c_{21}k^{α} values of n_{i} such that 2^{k} ≤ n_{i} ≤ 2^{k+1}, so taking l large enough, this will be summable and we obtain

max_{n_{i}≤n≤n_{i+1}} |\overline{R}_{n} − \overline{R}_{n_{i}}| = O(\sqrt{n}_{i}(log n_{i})^{β}) a.s.

LIL FOR THE RANGE OF RANDOM WALKS 13

Finally, standard estimates on Brownian motion show that

P ( sup_{n_{i} log n_{i}≤t≤n_{i+1} log n_{i+1}} |B_{t} − B_{n_{i} log n_{i}}| > \sqrt{n}_{i}(log n_{i})^{β})

is summable in i so that

sup_{n_{i} log n_{i}≤t≤n_{i+1} log n_{i+1}} |B_{t} − B_{n_{i} log n_{i}}| = O(\sqrt{n}_{i}(log n_{i})^{β}) a.s.

The proof of Theorem 2.1 is complete.

Remark 3.4. As we pointed out in Remark 2.3, similar arguments allow one to deduce Theorem 2.1 for Q_{n}^{(p)}, which is the number of distinct sites that {S_{i} : 0 < i ≤ n} has visited exactly p times. We sketch how to prove this. For 0 ≤ a < b, let S(a, b] = {S_{k} : a < k ≤ b} and S^{p}(a, b] be the set of distinct sites where S(a, b] visited exactly p times. (For simplicity we do not count S_{0}.) Clearly, Q_{n}^{(p)} = #S^{p}(0, n]. Now take a sequence {n_{j}} as in the proof of this section, fix i, and define

U_{j}^{p} = #S^{p}(n_{j−1}, n_{j}],
L_{j}^{(i)} = #{S^{p}(n_{j−1}, n_{j}] ∩ S(n_{j}, n_{i}]}
M_{j}^{(i)} = #{S(n_{j−1}, n_{j}] ∩ S^{p}(n_{j}, n_{i}]},
N_{j}^{(i)} = ∑_{l=1}^{p−1} #{S^{l}(n_{j−1}, n_{j}] ∩ S^{p−l}(n_{j}, n_{i}]}.

Then

0 ≤ L_{j}^{(i)}, M_{j}^{(i)}, N_{j}^{(i)} ≤ V_{j}, (3.17)

where V_{j} is the same as above. By a simple calculation similar to [7] (3.1), we have

Q_{t}^{(p)} = ∑_{j=1}^{i} U_{j}^{p} − ∑_{j=1}^{i−1}(L_{j}^{(i)} + M_{j}^{(i)} − N_{j}^{(i)}). (3.18)

14 R. F. BASS AND T. KUMAGAI

Thanks to (3.17), we can apply (3.3) to derive moment bounds for L_{j}^{(i)}, M_{j}^{(i)} and N_{j}^{(i)}. Also, an estimate of the variance for Q_{n}^{(p)} is obtained in [6] Theorem 3.1, so that (3.4) still holds (with a different constant for σ) for Q_{n}^{(p)}. Thus, our proof can be applied to Q_{n}^{(p)}.

In the rest of this section, we will give proofs of Lemmas 3.1, 3.2, and 3.3.

Proof of Lemma 3.1. First, note that because V_{0,n+1} = 1 − Z_{n} + W_{n}, then V_{0,n} and W_{n} have the same asymptotics. Also by the Markov property, V_{a,b} and V_{0,b−a} have the same distribution. As E[(W_{n})^{4}] = O(n^{2}) by Lemma 6.1 of [16], (3.2) follows.

We next prove (3.3) by induction. When l = 2 this is from (3.2). Assume that (3.3) holds up to l − 1. By the same argument as in the proof of Lemma 6.1 of [16], we have

∑ E[W_{i_{1}}^{n} ⋯ W_{i_{2l}}^{n}] ≤ ∑ c_{1}(n − i_{2l})^{−1/2}G_{n}(0, x_{1})G_{n}(x_{1}, x_{2}) ⋯ ×
G_{n}(x_{2l−2}, x_{2l−1})G(α_{1}, α_{2})G(α_{2}, α_{3}) ⋯ G(α_{2l−1}, α_{2l}),

where i_{2l} is fixed and the first sum is over all 0 ≤ i_{1} < i_{2} < ⋯ < i_{2l−1} ≤ n − 1. The second sum is over all x_{1}, x_{2}, ⋯, x_{2l−1} ∈ Z^{3} \ {0} such that they are all distinct and over all permutations (α_{1}, ⋯, α_{2l}) of (0, x_{1}, ⋯, x_{2l−1}). We will sum over i_{2l}, so what we need to show is the following:

∑ G_{n}(0, x_{1})G_{n}(x_{1}, x_{2}) ⋯ G_{n}(x_{2l−2}, x_{2l−1})

×G(α_{1}, α_{2})G(α_{2}, α_{3}) ⋯ G(α_{2l−1}, α_{2l}) = O(n^{l− \frac{1}{2}} (log n)^{l}). (3.19) By Lemma 3 of [13] we have

(3.20)  ∑_{x} G_{n}(0, x){G(u, x) + G(x, u)} = O(n^{1/2}),
(3.21)  ∑_{x} G_{n}(0, x)G(u, x)G(x, v) = O(log n),

LIL FOR THE RANGE OF RANDOM WALKS 15

uniformly over u, v ∈ Z^{3}. First we sum over x_{2l−1} in the left hand side of (3.19). Depending whether either of α_{1} or α_{2l} is x_{2l−1} or not, we use either (3.20) or (3.21). Then we sum over x_{2l−2}, x_{2l−3}, · · ·. (When (3.21) is used, there is the possibility that for some j, no x_{j} term will be left as we proceed with our summation. In that case, we use the estimate ∑_{x_{j}} G_{n}(x_{j−1}, x_{j}) = ∑_{k=0}^{n} ∑_{x_{j}} P^{(k)}(x_{j−1}, x_{j}) ≤ n.) As a result, we obtain (3.19).

We must also consider the case where at least two of i_{1}, ⋯, i_{2l−1} are equal, say i_{j} = i_{j+1}. In this case, as W_{i_{j}}^{n} ≤ 1,

∑_{{i_{1},···,i_{2l−1} \atop i_{j} =i_{j+1}}} E[W_{i_{1}}^{n} ⋯ W_{i_{2l}}^{n}] = n ∑_{i_{3},···,i_{2l−1}} E[W_{i_{3}}^{n} ⋯ W_{i_{2l}}^{n}],

so that by the induction hypothesis, we again obtain the desired estimate. Combining these facts, the proof of (3.3) is complete.

Remark 3.5. We believe that the right hand side of (3.3) can be replaced by c_{2}n^{l}. As (3.3) is enough for our use, we did not try to prove this.

The next lemma will be used in the proof of Lemma 3.2. The proof is due to D. Khoshnevisan.

Lemma 3.6. Let EX_{1} = 0 and E|X_{1}|^{2+δ} < ∞ for some δ ∈ (0, 1). Let Q be the covariance matrix of X_{1} and let ϵ = δ/(4 + δ). Then

G(0, x) = \frac{1}{2π|Q|^{1/2}(xQ^{−1}x)^{1/2}} (1 + O(|x|^{−ϵ})).

Proof. Let B_{t} be a standard 3-dimensional Brownian motion and let p_{s}(x) be the transition density for Q^{1/2}B_{s}, where Q^{1/2} is the nonnegative definite symmetric square root of Q.

16 R. F. BASS AND T. KUMAGAI

Considering the cases |y| ≤ 1 and |y| > 1 separately for y ∈ R, note

|e^{iy} − (1 + iy − \frac{y^{2}}{2} )| ≤ c_{1}(|y|^{2} ∧ |y|^{3}) ≤ c_{2}|y|^{2+δ}.

If φ is the characteristic function of X_{1}, then

|φ(α) − (1 − \frac{1}{2}α · Qα)| ≤ c_{2}E|X_{1}|^{2+δ}|α|^{2+δ}.

Let B > 0. Since E|X_{1}|^{2+δ} < ∞ and |a^{n} − b^{n}| ≤ n|a − b|(|a| ∨ |b|)^{n−1}, for |α| ≤ B\sqrt{log n}, we can deduce

|φ^{n}(α/\sqrt{n}) − e^{−α·Qα/2}| ≤ c_{3}n^{−δ/2}|α|^{2+δ}.

Using this estimate, we now proceed as in the proof of Proposition 3.1 of [1] to obtain |P (S_{n} = x) − p_{n}(x)| ≤ c_{4}n^{−(3+δ)/2}(log n)^{(5+δ)/2} ≤ c_{5}n^{−(3/2)−(δ/4)}. (3.22)

It is well known (see [23]) that P (S_{n} = x) ≤ c_{6}n^{−3/2}. (3.23) When |x| > n^{1/2} we can get a better estimate on P (S_{n} = x). Let A = {z ∈ Z^{3} : |z| ≤ |x − z|}. Write P (S_{n} = x) = P (S_{n} = x, S_{⟨n/2⟩} ∈ A) + P (S_{n} = x, S_{⟨n/2⟩} ∈ A^{c}). (3.24) By the Markov property, (3.23), and Chebyshev’s inequality,

P (S_{n} = x, S_{⟨n/2⟩} ∈ A^{c}) = ∑_{z∈A^{c}} P (S_{⟨n/2⟩} = z)P (S_{n−⟨n/2⟩} = x − z)
≤ c_{6}n^{−3/2} ∑_{z∈A^{c}} P (S_{⟨n/2⟩} = z)
≤ c_{6}n^{−3/2}P (|S_{⟨n/2⟩}| ≥ |x|/2)
≤ c_{7}n^{−3/2} \frac{⟨n/2⟩}{|x|^{2}} ≤ \frac{c_{8}}{n^{1/2}|x|^{2}} .

LIL FOR THE RANGE OF RANDOM WALKS 17

If S̃_{k} = S_{n−k}, then

P (S_{n} = x, S_{⟨n/2⟩} ∈ A) = P (S̃_{n} = 0, S̃_{n−⟨n/2⟩} ∈ A | S̃_{0} = x).

Since S̃_{k} satisfies the same hypotheses as S_{k}, then by the same argument the first term on the right hand side of (3.24) is also bounded by c_{8}/(n^{1/2}|x|^{2}). We thus have

P (S_{n} = x) ≤ \frac{2c_{8}}{n^{1/2}|x|^{2}} . (3.25)

That p_{n}(x) satisfies the same bound is easy, using Gaussian tail estimates. Let r = 2/(1+δ/4) and ϵ = δ/(4+δ). By (3.22), (3.25), and the bound on p_{n}(x),

∑_{n=1}^{∞} |P (S_{n} = x) − p_{n}(x)| ≤ ∑_{n=1}^{|x|^{r}} P (S_{n} = x) + ∑_{n=1}^{|x|^{r}} p_{n}(x)

+ ∑_{n=|x|^{r}+1}^{∞} |P (S_{n} = x) − p_{n}(x)|

≤ \frac{4c_{8}}{|x|^{2}} ∑_{n=1}^{|x|^{r}} n^{−1/2} + c_{5} ∑_{n=|x|^{r}}^{∞} n^{−(3/2)−(δ/4)}
≤ c_{9}|x|^{(r/2)−2} + c_{9}|x|^{−r((1/2)+(δ/4))}
≤ c_{10}|x|^{−1−ϵ}.

It is easy to see that

| ∑_{n=1}^{∞} p_{n}(x) − ∫_{0}^{∞} p_{s}(x) ds| ≤ ∑_{n=1}^{∞} |p_{n}(x) − ∫_{n−1}^{n} p_{s}(x) ds|

is o(|x|^{−1−ϵ}). A direct calculation of ∫_{0}^{∞} p_{s}(x) ds, now proves the lemma.

Proof of Lemma 3.2. We first prove (3.4) which is a refinement of Theorem 2 in [13]. Note that in the proof of Theorem 2 in [13], the following fact is obtained:

Var (R_{n}) = 2 ∑_{j=1}^{n−1} a_{j} + O(n\sqrt{log n}), (3.26)

18 R. F. BASS AND T. KUMAGAI

where

(3.27)  a_{j} = p ∑_{x∈B_{j}∩Z^{3}} G(0, x)b(x) + O(1),
(3.28)  B_{j} = {z ∈ R^{3} : 1 ≤ zQ^{−1}z ≤ j},
(3.29)  b(x) = \frac{1 − F (x, 0)}{1 − F (x, 0)F (0, x)}pF (x, 0)F (0, x),
(3.30)  F (x, y) = pG(x, y),

and Q is the covariance matrix for X_{1}. ((3.29) is proved in Lemma 5 of [13].) We have by (3.27) and (3.29) that

a_{j} = p^{4} ∑_{x∈B_{j}∩Z^{3}} G(0, x)^{2}G(x, 0) + O({ ∑_{x∈B_{j}∩Z^{3}} G(0, x)^{3}G(x, 0)} ∨ 1). (3.31)

By Lemma 3.6 with ϵ = δ/(4 + δ),

G(0, x) = \frac{1}{2π|Q|^{1/2}(xQ^{−1}x)^{1/2}} (1 + O(x^{−ϵ})). (3.32)

Note that by translation invariance, G(−x, 0) = G(0, x), so that G(x, 0) has the same asymptotics as G(0, x). Substituting (3.32) in (3.31), we have

a_{j} = p^{4}(2π)^{−3}|Q|^{−3/2} ∑_{x∈B_{j}∩Z^{3}}(xQ^{−1}x)^{−3/2} + O({ ∑_{x∈B_{j}∩Z^{3}}(xQ^{−1}x)^{−(3/2)−ϵ}} ∨ 1).

Since

∑_{x∈B_{j}∩Z^{3}}(xQ^{−1}x)^{−3/2} = ∫_{B_{j}}(zQ^{−1}z)^{−3/2}dz + O(1)

= ∫_{{1≤|y|^{2}≤j}} |y|^{−3}|Q|^{1/2}dy + O(1) = 2π|Q|^{1/2} log j + O(1),

and ∑_{x∈B_{j}∩Z^{3}}(xQ^{−1}x)^{−(3/2)−ϵ} = O(1) by a similar computation, we have

a_{j} = σ^{2}(log j)/2 + O(1),

where σ^{2} = 2p^{4}(2π)^{−2}|Q|^{−1}. Substituting this into (3.26), we obtain (3.4).

We next prove (3.5). The basic idea is the same as the proof of Lemma 4.1 in [16]. Set ρ_{n} = \sqrt{n log n} and define for each m, n ∈ N,

L_{n,m} = \frac{1}{ρ_{n}} \{E[(R_{n} − ER_{n})^{2m}]\}^{\frac{1}{2m}} .

Our goal is to prove

L_{n,m} ≤ M_{m} for all m, n ∈ N (3.33)

where {M_{m}} is a sequence of positive bounded numbers independent of n. Once (3.33) is proved, it leads to (3.5) for l odd by using Hölder’s inequality.

As seen in (2.4) and (3.4), (3.33) holds for m = 1, 2. Now we assume that (3.33) holds for all m ≤ m_{0} (thus, by Hölder inequality, (3.5) holds for all l ≤ 2m_{0}), and we will show {L_{n,m_{0}+1}} is bounded for all n. Note that

R_{2n} = ∑_{i=0}^{n} Z_{i}^{n} + ∑_{i=n}^{2n} Z_{i}^{2n} − ∑_{i=0}^{n−1}(Z_{i}^{n} − Z_{i}^{2n}) − 1 (3.34)

and by (3.3)

E[(∑_{i=0}^{n−1}(Z_{i}^{n} − Z_{i}^{2n}))^{2(m_{0}+1)}] ≤ E[W_{n}^{2(m_{0}+1)}] = O(ρ_{n}^{2(m_{0}+1)}). (3.35)

Recall \overline{Y} = Y −EY for any random variable Y. Noting that ∑_{i=0}^{n} \overline{Z}_{i}^{n} and ∑_{i=n}^{2n} \overline{Z}_{i}^{2n} are independent and have the same distribution as \overline{R}_{n}, we have

E[(∑_{i=0}^{n} \overline{Z}_{i}^{n} + ∑_{i=n}^{2n} \overline{Z}_{i}^{2n})^{2(m_{0}+1)}]

= 2E[\overline{R}_{n}^{2(m_{0}+1)}] + 2 ( \begin{matrix}2(m_{0} + 1) \\ 2 \end{matrix} ) E[\overline{R}_{n}^{2m_{0}}]E[\overline{R}_{n}^{2}] + ⋯

+ ( \begin{matrix}2(m_{0} + 1) \\ m_{0} + 1 \end{matrix} ) E[\overline{R}_{n}^{m_{0}+1}]^{2}

(3.36)  ≤ ρ_{n}^{2(m_{0}+1)}(2L_{n,m_{0}+1}^{2(m_{0}+1)} + c_{1}),

20 R. F. BASS AND T. KUMAGAI

for some c_{1} = c_{1}(m_{0}) > 0, where the last inequality is due to the induction hypothesis. By (3.34), (3.35) and (3.36), we have

\{E[\overline{R}_{2n}^{2(m_{0}+1)}]\}^{\frac{1}{2(m_{0}+1)}} ≤ ρ_{n}(2L_{n,m_{0}+1}^{2(m_{0}+1)} + c_{1})^{\frac{1}{2(m_{0}+1)}} + O(ρ_{n}).

Dividing both sides by ρ_{2n} ∼ \sqrt{2}ρ_{n}, we have

L_{2n,m_{0}+1} ≤ (\frac{1}{2^{m_{0}}} L_{n,m_{0}+1}^{2(m_{0}+1)} + c_{2})^{\frac{1}{2(m_{0}+1)}} + c_{3}. (3.37)

Now choose N large so that

(\frac{1}{2^{m_{0}}} + \frac{c_{2}}{N^{2(m_{0}+1)}} )^{\frac{1}{2(m_{0}+1)}} + \frac{c_{3}}{N} ≤ 1.

Either L_{m,m_{0}+1} ≤ N for every m that is a power of 2 or for some m ∈ N that is a power of 2, we have L_{m,m_{0}+1} ≥ N. In the latter case, for n ≥ m, we have by (3.37) that

\frac{L_{2n,m_{0}+1}}{L_{m,m_{0}+1}} ≤ (\frac{1}{2^{m_{0}}} (\frac{L_{n,m_{0}+1}}{L_{m,m_{0}+1}} )^{2(m_{0}+1)} + \frac{c_{2}}{(L_{m,m_{0}+1})^{2(m_{0}+1)}} )^{\frac{1}{2(m_{0}+1)}} + \frac{c_{3}}{L_{m,m_{0}+1}} .

Thus L_{2m,m_{0}+1} ≤ L_{m,m_{0}+1} and by induction it follows that L_{n,m_{0}+1} ≤ L_{m,m_{0}+1} for all n > m which are powers of 2. Thus {L_{2^{n},m_{0}+1}} is bounded.

Next consider n/2 < m < n where n is a power of 2. We can write

R_{n} = ∑_{i=0}^{m} Z_{i}^{m} + ∑_{i=m}^{n} Z_{i}^{n} − ∑_{i=0}^{m−1}(Z_{i}^{m} − Z_{i}^{n}) − 1.

By a similar argument to the above, we obtain

L_{m,m_{0}+1} ≤ c_{4}L_{n,m_{0}+1} + c_{5}.

The boundedness of {L_{n,m_{0}+1}} follows.

Remark 3.7. Y.Hamana [9] has informed us that (3.26) holds with O(n) (instead of O(n\sqrt{log n})). Using this, the extra term in (3.4) can be sharpened to O(n).

LIL FOR THE RANGE OF RANDOM WALKS 21

Proof of Lemma 3.3. Let

A = #{S_{k} : a < k ≤ b},
B = #({S_{k} : a < k ≤ b} ∩ {S_{k} : 0 ≤ k ≤ a}).

Then

\overline{R}_{b} − \overline{R}_{a} = \overline{A} − \overline{B}.

The law of A is equal to the law of R_{b−a}, so by Lemma 3.2 we have

E[(\overline{A})^{l}] ≤ c_{1}((b − a) log(b − a))^{l/2}.

Consider the sequence {S̃_{k}} = {S_{b}, S_{b−1}, …, S_{0}}. Then S̃_{k} is a random walk satisfying the same conditions as S_{k} and

B = #({S̃_{k} : 0 ≤ k < b − a} ∩ {S̃_{k} : b − a ≤ k ≤ b}).

By Lemma 3.1,

E[B^{l}] ≤ c_{2}((b − a) log(b − a))^{l/2}.

Since (EB)^{l} ≤ E[B^{l}] by Jensen’s inequality, combining with the estimate for \overline{A} proves (a).

Let D = b − a and

G_{k} = \frac{(R_{k+a} − ER_{k+a}) − (R_{a} − ER_{a})}{(D log D)^{1/2}}.

To show (b) we need to show

P (max_{k≤D} |G_{k}| > λ) ≤ \frac{c_{3}}{λ^{l}} . (3.38)

Note from (a) that E|G_{k} − G_{j}|^{l} ≤ c_{4}(|k − j|/D)^{l/2}. (3.39)

22 R. F. BASS AND T. KUMAGAI

For each k let k_{j} be the largest element of {⟨mD/2^{j}⟩ : m ≤ 2^{j}} that is less than or equal to k. We have

G_{k} = G_{k_{0}} + (G_{k_{1}} − G_{k_{0}}) + (G_{k_{2}} − G_{k_{1}}) + · · · .

The sum is actually finite because from some point on all the k_{j} are equal to k. Thus, in order for |G_{k}| to be larger than λ for some k ≤ D there must be a j ≥ 0 and an m ≤ 2^{j} such that

|G_{⟨(m+1)D/2^{j}⟩} − G_{⟨mD/2^{j}⟩}| ≥ \frac{λ}{40(j + 1)^{2}} .

Therefore, using (3.39),

P (max_{k≤D} |G_{k}| > λ) ≤ ∑_{j=0}^{∞} ∑_{m=0}^{2^{j}} P (|G_{⟨(m+1)D/2^{j}⟩} − G_{⟨mD/2^{j}⟩}| ≥ \frac{λ}{40(j + 1)^{2}} )
≤ c_{5} ∑_{j=0}^{∞} 2^{j} \frac{(1/2^{j})^{l/2}(j + 1)^{2l}}{λ^{l}}
≤ \frac{c_{6}}{λ^{l}}

as long as l > 2. This proves (3.38).

4. Proof: Two dimensional case We split the proof of Theorem 2.5 into two parts. The first is the following.

Proposition 4.1. Suppose d = 2. There exists c_{4.1} > 0 such that

(4.1)  lim sup_{n→∞} \frac{sup_{j≤n}(R_{j} − ER_{j})}{n log_{3} n/(log n)^{2}} ≤ c_{4.1} a.s.

We do not require Assumption 2.4 here.

Using (2.6), it is enough to prove the theorem when we replace ER_{n} with κn/ log n. We fix n and for each j ∈ N with j ≤ n, set

φ_{j} = \{ \begin{matrix}1, & j = 1 \\ \frac{j}{log j} , & j > 1 \end{matrix}

LIL FOR THE RANGE OF RANDOM WALKS 23

F_{j} = R_{j} − κφ_{j},
G_{j} = G_{j}^{n} = F_{j} \frac{(log n)^{2}}{n} ,
K = [log_{2} n] + 1.

We will show that max_{j≤k} G_{j} is almost subadditive. If it had been subadditive, we could have used the technique in [2], Section 3. Here we must modify the ideas in [2] appropriately.

Lemma 4.2. There exists c_{4.2} such that if A, B ∈ N, C = A + B, and α = (A ∧ B)/C, then

|φ_{C} − φ_{A} − φ_{B}| ≤ c_{4.2} \frac{C}{(log C)^{2}} α^{1/2}. (4.2)

Proof. The cases where A or B equal 1 are easy, so we suppose A, B > 1. We start with the identity

φ_{C} − φ_{A} − φ_{B} = \frac{C}{log C} [ − \frac{A}{C} \frac{log C − log A}{log A} − \frac{B}{C} \frac{log C − log B}{log B} ].

If 2 ≤ A ≤ C^{1/2}, then log A ≥ \frac{1}{3} and

0 ≤ \frac{A}{C} \frac{log C − log A}{log A} ≤ 3(\frac{A}{C} )^{1/2} \frac{1}{log C} \frac{(log C)^{2}}{C^{1/4}} ≤ \frac{c_{1}}{log C} (\frac{A}{C} )^{1/2}.

If C^{1/2} ≤ A ≤ C/2, then

0 ≤ \frac{A}{C} \frac{log C − log A}{log A} ≤ 2\frac{A}{C} \frac{log(C/A)}{log C} ≤ \frac{c_{2}}{log C} (\frac{A}{C} )^{1/2}.

If A ≥ C/2, then

0 ≤ \frac{A}{C} \frac{log C − log A}{log A} ≤ \frac{c_{3}}{log A}| log(1 − (B/C))| ≤ \frac{c_{4}}{log C} (\frac{B}{C} )^{1/2}.

We similarly bound (B/C)((log C − log B)/log B).

The following lemma is similar to Lemma 3.3, but here there are no absolute values and the estimates are one-sided.

24 R. F. BASS AND T. KUMAGAI

Lemma 4.3. (a) There exists M > 0 not depending on n such that

P ( max_{1≤j≤n} G_{j} > M) < \frac{1}{2}. (4.3)

(b) There exist c_{4.3}, c_{4.4} > 0 not depending on n such that

E[exp(c_{4.3} max_{1≤j≤n} G_{j})] ≤ c_{4.4}. (4.4)

Proof. Let θ_{j} be the usual shift operators. Since R_{n} − R_{m} ≤ R_{n−m} ∘ θ_{m}, then by Lemma 4.2

G_{n} − G_{m} ≤ G_{n−m} ∘ θ_{m} + c_{1}(\frac{m}{n} ∧ \frac{n − m}{n})^{1/2}. (4.5)

By the Markov property, (2.6) and (2.7),

E[(G_{j} ∘ θ_{m})^{2}] = E^{S_{m}}G_{j}^{2} = EG_{j}^{2} ≤ c_{2}(j/n)^{2}(\frac{log n}{log j})^{4} ≤ c_{3}(j/n)^{3/2}. (4.6)

In particular EG_{j}^{2} ≤ c_{3}(j/n)^{3/2}. (4.7) For each k let k_{j} be the largest element of {⟨mn/2^{j}⟩ : m ≤ 2^{j}} that is less than or equal to k. We have

G_{k} = G_{k_{0}} + (G_{k_{1}} − G_{k_{0}}) + (G_{k_{2}} − G_{k_{1}}) + ⋯,

where the sum is a finite one. If max_{k≤n} G_{k} ≥ M, then for some j ≥ 0 the following must hold:

G_{⟨(m+1)n/2^{j}⟩} − G_{⟨mn/2^{j}⟩} > \frac{M}{40(j + 1)^{2}} for some m ≤ 2^{j}. (4.8)

Let I(m, j) = ⟨(m + 1)n/2^{j}⟩ − ⟨mn/2^{j}⟩. If m ≤ 2^{j/8}, then by (4.7)

P (G_{⟨(m+1)n/2^{j}⟩} − G_{⟨mn/2^{j}⟩} > \frac{M}{40(j + 1)^{2}} )

≤ \frac{3200(j + 1)^{4}}{M^{2}} (EG_{⟨(m+1)n/2^{j}⟩}^{2} + EG_{⟨mn/2^{j}⟩}^{2})
≤ c_{4}(j + 1)^{4}(m/2^{j})^{3/2}/M^{2}

LIL FOR THE RANGE OF RANDOM WALKS 25

≤ c_{5}/(2^{5j/4}M^{2}).

If m > 2^{j/8}, then using (4.5)

G_{⟨(m+1)n/2^{j}⟩} − G_{⟨mn/2^{j}⟩} ≤ G_{I(m,j)} ∘ θ_{⟨mn/2^{j}⟩} + c_{1}(m + 1)^{−1/2}
≤ G_{I(m,j)} ∘ θ_{⟨mn/2^{j}⟩} + \frac{M}{80(j + 1)^{2}}

if M is large enough. In this case, using (4.6),

P (G_{⟨(m+1)n/2^{j}⟩} − G_{⟨mn/2^{j}⟩} > \frac{M}{40(j + 1)^{2}} )

≤ P (G_{I(m,j)} ∘ θ_{⟨mn/2^{j}⟩} > \frac{M}{80(j + 1)^{2}} )
≤ c_{6} \frac{(j + 1)^{4}}{M^{2}} \frac{1}{2^{3j/2}}
≤ c_{7}/(2^{5j/4}M^{2}).

We thus have

P (max_{j≤n} G_{j} > M) ≤ ∑_{j=0}^{∞} ∑_{m=1}^{2^{j}} P (G_{⟨(m+1)n/2^{j}⟩} − G_{⟨mn/2^{j}⟩} > \frac{M}{40(j + 1)^{2}} )
≤ ∑_{j=0}^{∞} c_{8} \frac{2^{j}}{M^{2}} \frac{1}{2^{5j/4}}
≤ \frac{c_{8}}{M^{2}} ≤ \frac{1}{2}

if M is large enough.

We next prove (4.4). Note that by (4.5), we have G_{n} − G_{m} ≤ G_{n−m} ∘ θ_{m} + c_{9}. (4.9) Now, choose c_{10} large so that c_{10}/2 > c_{9} and (4.10) P ( max_{1≤j≤n} G_{j} > (c_{10}/2) − c_{9}) < 1/2 for all n ∈ N, which is possible by (4.3). Let T_{k} = min{j : G_{j} > c_{10}k}. Then

P (max_{j≤n} G_{j} > c_{10}(k + 1)) = P (T_{k+1} ≤ n)

26 R. F. BASS AND T. KUMAGAI

≤ P (T_{k} ≤ n, max_{T_{k}≤j≤n}(G_{j} − G_{T_{k}}) > c_{10}/2)
= E[P ( max_{T_{k}≤j≤n}(G_{j} − G_{T_{k}}) > c_{10}/2|F_{T_{k}}); T_{k} ≤ n]
≤ E[P (max_{j≤n} G_{j} > (c_{10}/2) − c_{9}); T_{k} ≤ n]
≤ \frac{1}{2}P (T_{k} ≤ n),

where the second inequality follows by (4.9) and the third inequality by (4.10). By induction we obtain P (T_{k} ≤ n) ≤ 2^{−n}, which yields (4.4).

Proof of Proposition 4.1. Let

C_{j} = max_{⟨jn/K⟩≤i<⟨(j+1)n/K⟩} [R_{i} − R_{⟨jn/K⟩} − κφ_{i−⟨jn/K⟩}]

and

D_{j} = \frac{C_{j}}{(n/K)/(log(n/K))^{2}} .

By Lemma 4.3 there exist c_{1}, c_{2} such that Ee^{c_{1}D_{j}} ≤ c_{2}. Moreover, the D_{j} are independent. Let

e_{K,n} = |φ_{n} − Kφ_{⟨n/K⟩}|/(n/(log n)^{2}).

An elementary computation shows that

e_{K,n} ≤ c_{3} log K.

Since

max_{m≤n} \frac{(R_{m} − κφ_{m})}{n/(log n)^{2}} ≤ \frac{c_{4}}{K} ∑_{j=1}^{K} D_{j} + κe_{K,n}

for A ≥ 2c_{3}κ, we have

P (max_{m≤n} \frac{R_{m} − κφ_{m}}{n/(log n)^{2}} > A log K) ≤ P (\frac{c_{4}}{K} ∑_{j=1}^{K} D_{j} > A log K − κe_{K,n})
≤ P (∑_{j=1}^{K} D_{j} > AK(log K)/(2c_{4}))

LIL FOR THE RANGE OF RANDOM WALKS 27

≤ e^{−c_{1}AK(log K)/(2c_{4})}Ee^{c_{1} ∑ D_{j}}
≤ e^{−c_{5}AK(log K)/2}c_{2}^{K}
≤ e^{−c_{5}AK(log K)/2}

if K is large enough. Using this inequality for n = n_{i} = 2^{i} and K = ⟨log_{2} n⟩, the right hand side is summable in i , and we can apply Borel-Cantelli. Since

\frac{sup_{j≤n}(R_{j} − κφ_{j})}{n log_{3} n/(log n)^{2}} ≤ 2\frac{sup_{j≤n_{i+1}}(R_{j} − κφ_{j})}{n_{i+1} log_{3} n_{i+1}/(log n_{i+1})^{2}}

for n_{i} ≤ n < n_{i+1} if i is large, we obtain (4.1).

We next work on the lower bound.

Proposition 4.4. Suppose d = 2. Under Assumption 2.4, there exists c_{4.5} > 0 such that

(4.11)  lim sup_{n→∞} \frac{sup_{j≤n}(R_{j} − ER_{j})}{n log_{3} n/(log n)^{2}} ≥ c_{4.5}  a.s.

The idea of the proof of Proposition 4.4 is to split S_{0}, S_{1}, …, S_{n} into about log_{2} n blocks of approximately equal length. We show that there is sufficiently large probability that the j-th and k-th blocks will not overlap if |j − k| > 1. If J_{j} is the range of the j-th block and H_{j} is the cardinality of the overlap of the (j − 1)-st and j-th blocks, we can then write

R_{n} − ER_{n} = ∑_{j}(J_{j} − EJ_{j}) + (∑_{j} EJ_{j} − ER_{n}) − ∑_{j} H_{j}.

We estimate the first term on the right using the central limit theorem of [18]. The second term is a straightforward computation. To bound the final term, we first need to develop some estimates for the intersections of two random walks.

In order to prove Proposition 4.4, we need two lemmas. Let I_{n} be the cardinality of {S_{k} : k ∈ [0, n]} ∩ {S′_{k} : k ∈ [0, n]} where S_{k} and S′_{k} are two independent random

28 R. F. BASS AND T. KUMAGAI

walks with S_{0} = y, S′_{0} = y′ for some y, y′ ∈ Z^{2}. Note that the initial points y, y′ can be chosen arbitrarily in Z^{2}. Denote by α_{t} the intersection local time of two independent 2-dimensional Brownian motions up to time t.

Lemma 4.5. Under Assumption 2.4, there exists c_{4.6} > 0 such that

(4.12)  E[(\frac{I_{n}}{n/(log n)^{2}} )^{p}] ≤ c_{4.6}^{p}Eα_{1}^{p}  for all p ∈ N.

Proof. Let T_{y} = inf{k > 0 : S_{k} = y}. We will show

(4.13)  (log(|y|^{2}T))P^{0}(T_{y} ≤ |y|^{2}T) ≤ c_{1}ν([0, T])  for all y ∈ Z^{2},

where ν is the measure on R with density (1/t) exp(−1/(c_{2}t)), with some c_{2} > 0 to be chosen later. We first prove the lemma assuming (4.13). Using (5.a), (5.b), and (5.c) of Le Gall [18],

\frac{(log n)^{2p}}{n^{p}} E[I_{n}^{p}] ≤ ∑_{σ,σ′∈S_{p}} ∫_{(R^{2})^{p}} du_{1} … du_{p}θ_{n}(u_{1}, …, u_{p})θ′_{n}(u_{1}, …, u_{p}),

for all p ∈ N where S_{p} is the set of permutations of {1, …, p} and θ_{n} is defined by

θ_{n}(u_{1}, ⋯, u_{p}) = (log n)^{p}P^{0}(T_{[n^{1/2}u_{σ(1)}]} ≤ ⋯ ≤ T_{[n^{1/2}u_{σ(p)}]} ≤ n)

for each u_{1}, ⋯, u_{p} ∈ R^{2}. Similarly to the proof just before equation (5.d) in [18], and using (4.13), we have

θ_{n}(u_{1}, ⋯, u_{p}) ≤ c_{1}^{p} ∫_{0}^{1} \frac{dt_{1}}{t_{1}} exp(−\frac{|u_{σ(1)}|^{2}}{c_{2}t_{1}} )

· ∫_{0}^{1−t_{1}} \frac{dt_{2}}{t_{2}} exp(−\frac{|u_{σ(2)} − u_{σ(1)}|^{2}}{c_{2}t_{2}} )

⋯ ∫_{0}^{1−(t_{1}+···+t_{p−1})} \frac{dt_{p}}{t_{p}} exp(−\frac{|u_{σ(p)} − u_{σ(p−1)}|^{2}}{c_{2}t_{p}}).

As in (5.d) in [18], this is less than

c_{3}^{p} ∫ ⋯ ∫_{0≤s_{1}≤···≤s_{p}≤1} ds_{1} … ds_{p} ∏_{i=1}^{p} q_{s_{i}−s_{i−1}}(u_{σ(i−1)}, u_{σ(i)}),

LIL FOR THE RANGE OF RANDOM WALKS 29

where q_{s} be the transition density of a 2-dimensional Brownian motion, with the variance at time t not tI but c_{4}tI (where c_{4} = c_{2}/2); in other words, a speeded up Brownian motion. Also we set σ(0) = 0. Following Le Gall’s argument on page 495 in [18], this in turn is less than c_{5}^{p}Eℓ_{c_{6}}^{p}, but now ℓ_{c_{6}} is the intersection local time of two independent Brownian motions that each have covariance matrix c_{6}tI. By scaling, this will be less than c_{5}^{p}c_{6}^{p}Eα_{1}^{p}, which completes the proof of the lemma.

It remains to show (4.13). For the proof of this, we observe two facts. One is Theorem 3.6 in [18]:

(log n)P^{y}(T_{0} ≤ n) ≤ c_{7}\{(log \sqrt{n}/|y|)^{+} + \frac{n}{|y|^{2}} 1_{\{|y|/\sqrt{n}≥1/2\}}\}. (4.14)

The other is Bernstein’s inequality:

P (max_{k≤n} |S_{k}| > λ) ≤ exp(−\frac{λ^{2}}{c_{8}(n + Λλ)}),

where Λ is given in Assumption 2.4 (b); see [3].

Using (4.14) with n = |y|^{2}T, (4.13) is clear for T > (32Λ^{2})^{−1} (note that replacing y by −y in (4.14) and using translation invariance, (4.14) holds for P^{0}(T_{y} ≤ n)). If T ≤ (32Λ^{2})^{−1} and |y| ≤ 4Λ, then |y|^{2}T ≤ \frac{1}{2} and (4.13) follows trivially. So we look at the case where T ≤ (32Λ^{2})^{−1} and |y| > 4Λ. It is easy to see that ν([0, T]) ≥ c_{9} exp(−1/(c_{10}T)) for T ≤ (32Λ^{2})^{−1}. Denote by τ_{B(0,r)} the first exit time from the ball centered at 0 and radius r. By the strong Markov property we have

P^{0}(T_{y} ≤ |y|^{2}T) = P^{0}(τ_{B(0,|y|/2)} ≤ |y|^{2}T, T_{y} ≤ |y|^{2}T)
(4.15)  ≤ E^{0}[P^{S_{τ_{B(0,|y|/2)}}} (T_{y−S_{τ_{B(0,|y|/2)}}} ≤ |y|^{2}T); τ_{B(0,|y|/2)} ≤ |y|^{2}T].

By (4.14)

P^{S_{τ_{B(0,|y|/2)}}} (T_{y−S_{τ(B(0,|y|/2))}} ≤ |y|^{2}T) ≤ c_{11}/ log(|y|^{2}T), (4.16)

30 R. F. BASS AND T. KUMAGAI

when |y|/2 > 2Λ. By Assumption 2.4 (b) the random walk cannot go a distance more than Λ|y|^{2}T in time |y|^{2}T. So if T < 1/(4Λ|y|), then Λ|y|^{2}T < |y|/4 and P^{0}(τ_{B(0,|y|/2)} < |y|^{2}T) = 0. If T > 1/(4Λ|y|), then by Bernstein’s inequality

P^{0}(τ_{B(0,|y|/2)} ≤ |y|^{2}T) ≤ exp(−\frac{|y|^{2}}{4c_{8}(|y|^{2}T + Λ|y|/2)}) ≤ e^{−1/(c_{12}T)}

if c_{12} is chosen sufficiently large. Putting this and (4.16) in (4.15) yields (4.13).

Lemma 4.6. There exists c_{4.7} > 0 such that

Eα_{1}^{p} ≤ c_{4.7}^{p}p! for all p ∈ N. (4.17)

Further, there exists c_{4.8}, c_{4.9} > 0 such that

(4.18)  E[exp(\frac{c_{4.8}I_{n}}{n/(log n)^{2}} )] < c_{4.9}  for all n ∈ N.

Proof. (4.17) is proved in Lemma 2 of [21]. (4.18) is then deduced by combining (4.17) with Lemma 4.5.

Proof of Proposition 4.4. Fix n. Let K = ⟨β log_{2} n⟩, where β is a number we will choose later. Let M = n/K. Set

J_{j} = #{S_{k} : k ∈ [⟨jM⟩, ⟨(j + 1)M⟩)},
H_{j} = #({S_{k} : k ∈ [⟨jM⟩, ⟨(j + 1)M⟩)} ∩ {S_{k} : k ∈ [⟨(j − 1)M⟩, ⟨jM⟩)}).

Let e be a vector of length \sqrt{M}. We denote by B(x, r) the ball of radius r centered at x. Let A_{j} be the event that S_{⟨jM⟩} ∈ B(je, \frac{1}{8} \sqrt{M}) and

\{S_{k} : k ∈ [⟨jM⟩, ⟨(j + 1)M⟩)\} ⊂ B((j + \frac{1}{2})e, \sqrt{M}).

Let B_{j} be the event that \overline{J}_{j}(log M)^{2}/M is greater than some number −c_{1}. By the usual central limit theorem we know P (A_{j}) ≥ c_{2} if n is large. Thanks to (2.8), if

LIL FOR THE RANGE OF RANDOM WALKS 31

we take c_{1} sufficiently large, then P (A_{j} ∩ B_{j}) > c_{2}/2. By the Markov property, P (F) ≥ (c_{2}/2)^{K}, (4.19) where F = ∩_{j=1}^{K}(A_{j} ∩ B_{j}).

On the set F we have that {S_{k} : k ∈ [⟨jM⟩, ⟨(j + 1)M⟩)} is disjoint from {S_{k} : k ∈ [⟨iM⟩, ⟨(i + 1)M⟩)} if |i − j| > 1, and so

\overline{R}_{n} = ∑_{j=1}^{K} \overline{J}_{j} + ( ∑_{j=1}^{K} EJ_{j} − ER_{n}) − ∑_{j=1}^{K} H_{j}. (4.20)

On the set F the event B_{j} holds for each j, and so

∑_{j=1}^{K} \overline{J}_{j} ≥ −c_{1}KM/(log M)^{2} ≥ −c_{3}n/(log n)^{2}. (4.21)

We have

∑_{j=1}^{K} EJ_{j} − ER_{n} = K \frac{n/K}{log(n/K)} − \frac{n}{log n} + O(\frac{n}{(log n)^{2}} )
= \frac{n}{log n}[\frac{1}{1 − (log K/ log n)} − 1] + O(\frac{n}{(log n)^{2}} )
≥ c_{4} \frac{n log K}{(log n)^{2}} + O(\frac{n}{(log n)^{2}} )
(4.22)  ≥ c_{5} \frac{n log_{3} n}{(log n)^{2}}

if n is large.

Let C_{1} be the event that

∑_{\{j odd\}} H_{j} ≥ \frac{c_{5}}{3} \frac{n log_{3} n}{(log n)^{2}}

and C_{2} the event that

∑_{\{j even\}} H_{j} ≥ \frac{c_{5}}{3} \frac{n log_{3} n}{(log n)^{2}}.

Set G = F ∩ C_{1}^{c} ∩ C_{2}^{c}. For j odd the H_{j} are independent. By Lemma 4.6

P (C_{1}) = P ( ∑_{\{j odd\}} \frac{H_{j}}{M/(log M)^{2}} ≥ c_{6}K log K)

32 R. F. BASS AND T. KUMAGAI

≤ e^{−c_{6}c_{7}K log K}Ee^{c_{7} ∑ H_{j}(log M)^{2}/M}
≤ e^{−c_{8}K log K}(c_{9})^{K}.

When n is large, K will be large, and then P (C_{1}) ≤ P (F)/3. We have a similar estimate for P (C_{2}), so using (4.19), we have

P (G) ≥ (c_{2}/2)^{K}/3. (4.23)

On the event G

∑_{j=1}^{K} H_{j} ≤ \frac{2c_{5}}{3} \frac{n log_{3} n}{(log n)^{2}}. (4.24)

Combining (4.20), (4.21), (4.22), and (4.24), on the event G

\overline{R}_{n} ≥ c_{10}n log_{3} n/(log n)^{2}. (4.25)

Now let n_{ℓ} = ⟨exp(ℓ^{2})⟩, let K_{ℓ} = ⟨β log_{2}(n_{ℓ+1} − n_{ℓ})⟩, let S′_{k} = S_{k+n_{ℓ}} − S_{n_{ℓ}}, k = 0, 1, 2, …, n_{ℓ+1} − n_{ℓ}, and let R′_{ℓ} = #{S′_{k} : 0 ≤ k < n_{ℓ+1} − n_{ℓ}}. If we apply the above results to the random walk S′_{k}, we see there exist events G′_{ℓ} which are independent, which have probability at least \frac{1}{3}(c_{2}/2)^{K_{ℓ}}, and on which

(4.26) \overline{R′}_{ℓ} ≥ c_{10} \frac{(n_{ℓ+1} − n_{ℓ}) log_{3}(n_{ℓ+1} − n_{ℓ})}{(log(n_{ℓ+1} − n_{ℓ}))^{2}} ≥ c_{11} \frac{n_{ℓ+1} log_{3} n_{ℓ+1}}{(log n_{ℓ+1})^{2}} .

If we choose β small enough, then ∑_{ℓ} P (G′_{ℓ}) = ∞, and by Borel-Cantelli G′_{ℓ} occurs infinitely often with probability 1. Now R′_{ℓ} differs from R_{n_{ℓ+1}} by at most n_{ℓ} = o(n_{ℓ+1} log_{3} n_{ℓ+1}/(log n_{ℓ+1})^{2}) and the same holds for the difference of their expectations. Together with (4.26) this proves the proposition.

Proof of Theorem 2.5. We use Proposition 4.1, Proposition 4.4, and the Hewitt-Savage 0-1 law (see for example, Theorem 2.15 of [17]).

Acknowledgments. The authors are grateful to J.-F. Le Gall, Y. Hamana, N. Jain, H. Kesten, D. Khoshnevisan and Z. Shi for helpful advice and comments.

REFERENCES

[1] Bass, R.F. and Khoshnevisan, D. (1992). Local times on curves and uniform invariance principles. Probab. Theory Relat. Fields 92 465–492.

[2] Bass, R.F. and Kumagai, T. (2000). Laws of the iterated logarithm for some symmetric diffusion processes. Osaka J. Math. 37 625–650.

[3] Bennett, G. (1962). Probability inequalities for the sum of independent random variables. J. Amer. Stat. Assoc. 57 33-45.

[4] Donsker, M.D. and Varadhan, S.R.S. (1979). On the number of distinct sites visited by a random walk. Comm. Pure Appl. Math. 32 721–747.

[5] Dvoretzky, A. and Erdös, P. (1951). Some problems on random walk in space. Proc. Second Berkeley Symp. 353–367.

[6] Hamana, Y. (1995). On the multiple point range of three-dimensional random walks. Kobe J. Math. 12 95–122.

[7] Hamana, Y. (1997). The fluctuation result for the multiple point range of two-dimensional recurrent random walks. Ann. Probab. 25 598–639.

[8] Hamana, Y. (1998). An almost sure invariance principle for the range of random walks. Stochastic Process. Appl. 78 131–143.

[9] Hamana, Y. (2000). Personal communication.

[10] Hamana, Y. and Kesten, H. (2001). Large deviations for the range of an integer-valued random walk. Ann. Inst. H. Poincaré, to appear.

[11] Hamana, Y. and Kesten, H. (2001). A large-deviation result for the range of random walk and for the Wiener sausage. Probab. Theory Relat. Fields 120 183–208.

[12] Jain, N.C. and Pruitt, W.E. (1970). The range of recurrent random walk in the plane. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 16 279–292.

[13] Jain, N.C. and Pruitt, W.E. (1971). The range of transient random walk. J. Analyse Math. 24 369–393.

34 R. F. BASS AND T. KUMAGAI

[14] Jain, N.C. and Pruitt, W.E. (1972). The law of the iterated logarithm for the range of random walk. Ann. Math. Statist. 43 1692–1697.

[15] Jain, N.C. and Pruitt, W.E. (1972). The range of random walk. Proc. Sixth Berkeley Symp. Math. Stat. Probab., (Univ. California, Berkeley, Calif., 1970/1971), Vol. III: Probability theory, pp. 31–50, Univ. California Press, Berkeley, California.

[16] Jain, N.C. and Pruitt, W.E. (1974). Further limit theorems for the range of random walk. J. Analyse Math. 27 94–117.

[17] Kallenberg, O. (1997). Foundations of Modern Probability. Springer, New York.

[18] Le Gall, J.-F. (1986). Propriétés d’intersection des marches aléatoires. I. Convergence vers le temps local d’intersection. Comm. Math. Phys. 104 471–507.

[19] Le Gall, J.-F. (1988). Fluctuation results for the Wiener sausage. Ann. Probab. 16 991–1018.

[20] Le Gall, J.-F. and Rosen, J. (1991). The range of stable random walks. Ann. Probab. 19 650–705.

[21] Le Gall, J.-F. (1994). Exponential moments for the renormalized self-intersection local time of planar Brownian motion. Séminaire de Probabilités, XXVIII, pp. 172–180, Lecture Notes in Math. 1583, Springer, Berlin.

[22] Skorohod, A.V. (1965). Studies in the theory of random processes. Addison-Wesley, Massachusetts.

[23] Spitzer, F. (1976). Principles of Random Walk. Springer, Berlin.

R. F. Bass Department of Mathematics University of Connecticut Storrs, CT 06269, U.S.A. E-mail: bass@math.uconn.edu T. Kumagai Research Institute for Mathematical Sciences Kyoto University Kyoto 606-8502, Japan Email: kumagai@kurims.kyoto-u.ac.jp