Heavy points of a d-dimensional

simple random walk

Endre Csáki^{1} Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, P.O.B. 127, H-1364, Hungary. E-mail address: csaki@renyi.hu

Antónia Földes^{2} Department of Mathematics, College of Staten Island, CUNY, 2800 Victory Blvd., Staten Island, New York 10314, U.S.A. E-mail address: foldes@mail.csi.cuny.edu

Pál Révész^{3} Institut für Statistik und Wahrscheinlichkeitstheorie, Technische Universität Wien, Wiedner Hauptstrasse 8-10/107 A-1040 Vienna, Austria. E-mail address: reveszp@renyi.hu

Abstract: For a simple symmetric random walk in dimension d ≥ 3, a uniform strong law of large numbers is proved for the number of sites with given local time up to time n.

AMS 2000 Subject Classification: Primary 60G50; Secondary 60F15, 60J55.

Keywords: local time, simple random walk in d-dimension, strong theorems.

1Corresponding author. Research supported by the Hungarian National Foundation for Scientific Research, Grant No. T 037886 and T 043037.

2Research supported by a PSC CUNY Grant, No. 66494-0035.

3Research supported by the Hungarian National Foundation for Scientific Research, Grant No. T 037886 and T 043037.

1. Introduction and main results

Consider a simple symmetric random walk {S_{n}}_{n=1}^{∞} starting at the origin 0 on the ddimensional integer lattice Z_{d}, i.e. S_{0} = 0, S_{n} = ∑_{k=1}^{n} X_{k}, n = 1, 2, …, where X_{k}, k = 1, 2, … are i.i.d. random variables with distribution

P(X_{1} = e_{i}) = P(X_{1} = −e_{i}) = \frac{1}{2d}, i = 1, 2, ..., d

and {e_{1}, e_{2}, ...e_{d}} is a system of orthogonal unit vectors in Z_{d}. Define the local time of the walk by

ξ(x, n) := #{k : 0 < k ≤ n, S_{k} = x}, n = 1, 2, …,  (1.1)

where x is any lattice point of Z_{d}. The maximal local time of the walk is defined as

ξ(n) := max_{x∈Z_{d}} ξ(x, n).  (1.2)

Define also

η(n) := max_{0≤k≤n} ξ(S_{k}, ∞).  (1.3)

Denote by γ(n) = γ(n; d) the probability that in the first n − 1 steps the d-dimensional path does not return to the origin. Then

1 = γ(1) ≥ γ(2) ≥ ... ≥ γ(n) ≥ ... > 0.  (1.4)

It was proved in [2] that Theorem A (Dvoretzky and Erdős [2]) For d ≥ 3

lim_{n→∞} γ(n) = γ = γ(∞; d) > 0,  (1.5)

and

γ < γ(n) < γ + O(n^{1−d/2}),  (1.6)

or equivalently

P(ξ(0, n) = 0, ξ(0, ∞) > 0) = O (n^{1−d/2})  (1.7)

as n → ∞.

So γ is the probability that the d-dimensional simple symmetric random walk never returns to its starting point.

Let ξ(x, ∞) be the total local time at x of the infinite path in Z_{d}. Then (see Erdős and Taylor [3]) ξ(0, ∞) has geometric distribution:

P(ξ(0, ∞) = k) = γ(1 − γ)^{k},  k = 0, 1, 2, ...  (1.8)

Erdős and Taylor [3] proved the following strong law for the maximal local time: Theorem B (Erdős and Taylor [3]) For d ≥ 3

lim_{n→∞} \frac{ξ(n)}{log n} = λ a.s., (1.9)

where

λ = λ_{d} = −\frac{1}{log(1 − γ)}.  (1.10)

Following the proof of Erdős and Taylor, without any new idea, one can prove that

lim_{n→∞} \frac{η(n)}{log n} = λ a.s. (1.11)

We can present a stronger lower estimate of ξ(n). Theorem C (Révész [10]) Let d ≥ 4 and

ψ(n) = ψ(n, B) = λ log n − λB log log n.  (1.12)

Then with probability 1 for any ε > 0 there is a random variable n_{0} such that

ξ(n) ≥ ψ(n, 3 + ε)

if n ≥ n_{0}.

Erdős and Taylor [3] also investigated the properties of

Q(k, n) := #{x : x ∈ Z_{d}, ξ(x, n) = k},

i.e. the cardinality of the set of points visited exactly k times in the time interval [1, n]. They proved Theorem D (Erdős and Taylor [3]) For d ≥ 3 and for any k = 1, 2, …

lim_{n→∞} \frac{Q(k, n)}{n} = γ^{2}(1 − γ)^{k−1} a.s. (1.13)

Let

U(k, n) := #{j : 0 < j ≤ n, ξ(S_{j}, ∞) = k, S_{j} ≠ S_{ℓ} (ℓ = 1, 2, …, j − 1)}
= #{x ∈ Z_{d} : 0 < ξ(x, n) ≤ ξ(x, ∞) = k}.  (1.14)

Repeating the proof of Theorem D one can get

lim_{n→∞} \frac{U(k, n)}{n} = γ^{2}(1 − γ)^{k−1}  a.s.  (1.15)

for any k = 1, 2, . . ..

Define furthermore

R(k, n) := ∑_{j=k}^{∞} Q(j, n),  (1.16)
V (k, n) := ∑_{j=k}^{∞} U(j, n).  (1.17)

It follows that for fixed k ≥ 1

lim_{n→∞} \frac{R(k, n)}{n} = γ(1 − γ)^{k−1}  a.s.  (1.18)
lim_{n→∞} \frac{V (k, n)}{n} = γ(1 − γ)^{k−1}  a.s.  (1.19)

The properties of these quantities were further investigated (for fixed k) by Pitt [8] who proved (1.13), (1.15) and (1.18), (1.19) for general random walk and by Hamana [5], [6] who proved central limit theorems (in general case for d ≥ 3).

In this paper we study the question whether k can be replaced by a sequence t(n) = t_{n} ↗ ∞ of positive integers in (1.13), (1.15), (1.18) and (1.19).

Theorem Let d ≥ 3, and define

μ = μ(t) := γ(1 − γ)^{t−1},  (1.20)
t_{n} := [ψ(n, B)], B > 2,  (1.21)

where ψ(n, B) is defined by (1.12). Then we have

lim_{n→∞} sup_{t≤t_{n}} |\frac{U(t, n)}{nγμ(t)} − 1| = 0  a.s.  (1.22)

lim_{n→∞} sup_{t≤t_{n}} |\frac{Q(t, n)}{nγμ(t)} − 1| = 0  a.s.  (1.23)
lim_{n→∞} sup_{t≤t_{n}} |\frac{V (t, n)}{nμ(t)} − 1| = 0  a.s.  (1.24)
lim_{n→∞} sup_{t≤t_{n}} |\frac{R(t, n)}{nμ(t)} − 1| = 0  a.s.  (1.25)

Here in sup_{t≤t_{n}}, t runs through positive integers.

(1.25) of Theorem clearly implies (compare to Theorem C)

Corollary Let d ≥ 3. Then with probability 1 for any ε > 0 there is a random variable n_{0} such that

ξ(n) ≥ λ log n − (2 + ε) log log n

if n ≥ n_{0}.

First we present some more notations. For x ∈ Z_{d} let T_{x} be the first hitting time of x, i.e. T_{x} = min{i ≥ 1 : S_{i} = x} with the convention that T_{x} = ∞ if there is no i with S_{i} = x. Let T = T_{0}. In general, for a subset A of Z_{d}, let T_{A} denote the first time the random walk visits A, i.e. T_{A} = min{i ≥ 1 : S_{i} ∈ A} = min_{x∈A} T_{x}. Let P_{x}(·) denote the probability of the event in the bracket under the condition that the random walk starts from x ∈ Z_{d}. We denote P(·) = P_{0}(·).

Introduce further

q_{x} := P(T < T_{x}),  (1.26)
s_{x} := P(T_{x} < T).  (1.27)

In words, q_{x} is the probability that the random walk, starting from 0, returns to 0, before reaching x (including T < T_{x} = ∞), and s_{x} is the probability that the random walk, starting from 0, hits x, before returning to 0 (including T_{x} < T = ∞).

2. Preliminary facts and results

First we present some lemmas needed to prove Theorem.

Introduce the following notations:

X_{i}(t) = X_{i} =
= \{ \begin{matrix}1 & if S_{j} ≠ S_{i} (j = 1, 2, …, i − 1), ξ(S_{i}, ∞) ≥ t, \\ 0 & otherwise, \end{matrix}
Y_{i}(t, n) = Y_{i} =
= \{ \begin{matrix}1 & if S_{j} ≠ S_{i} (j = 1, 2, …, i − 1), ξ(S_{i}, n) ≥ t, \\ 0 & otherwise, \end{matrix}
ρ_{i} = ρ_{i}(t) = I{X_{i} = 1}(min{j : ξ(S_{i}, j) ≥ t} − i),
μ_{i} = μ_{i}(t) = γ(i)(1 − γ)^{t−1},

t = 1, 2, …, i = 1, 2, …, where I{·} denotes the usual indicator function. Recall the definitions of γ(i), γ and μ = μ(t) in (1.4) (1.5) and (1.20). Furthermore let

σ_{n}^{2} = σ_{n}^{2}(t) := E (∑_{i=1}^{n} X_{i} − nμ)^{2} .  (2.1)

Clearly we have

R(t, n) = ∑_{i=1}^{n} Y_{i},

V (t, n) = ∑_{i=1}^{n} X_{i}.

Lemma 2.1. (Dvoretzky and Erdős [2])

P(S_{i} ≠ S_{j}, j = 1, 2, …, i − 1) = P(ξ(0, i − 1) = 0) = γ(i).

The following lemma is a trivial consequence of Theorem A.

Lemma 2.2.

P(n < ρ_{i}(t) < ∞) ≤ \frac{O(1)t^{d/2}}{n^{d/2−1}} ,

μ ≤ μ_{i} ≤ (1 + \frac{O(1)}{i^{d/2−1}} ) μ,

EX_{i} = μ_{i}.

The next lemma can be obtained by elementary calculations. Lemma 2.3.

nμ ≤ E ∑_{i=1}^{n} X_{i} = ∑_{i=1}^{n} μ_{i} ≤ nμ + μa_{n}O(1),

where

a_{n} = ∑_{i=1}^{n} \frac{1}{i^{d/2−1}} = \{ \begin{matrix}O(1) & if d > 4, \\ O(1) log n & if d = 4, \\ O(1)n^{1/2} & if d = 3. \end{matrix}

Lemma 2.4. Let n > 3^{3}. Then

σ_{n}^{2} ≤ nμ + μa_{n}O(1) − n^{2}μ^{2} + 2(I + II + III),  (2.2)

where

I = ∑_{1≤i<j≤n} P(X_{i} = 1, X_{j} = 1, ρ_{i} ≥ n^{α}),
II = ∑_{1≤i<j≤min(i+3n^{α},n)} P(X_{i} = 1, X_{j} = 1, ρ_{i} < n^{α}),
III = ∑_{1≤i<i+3n^{α}<j≤n} P(X_{i} = 1, X_{j} = 1, ρ_{i} < n^{α}),
α = 2/d.

Proof. Clearly we have

σ_{n}^{2} = E (∑_{i=1}^{n} X_{i})^{2} + n^{2}μ^{2} − 2nμE ∑_{i=1}^{n} X_{i} =
= E ∑_{i=1}^{n} X_{i} + 2 ∑_{1≤i<j≤n} EX_{i}X_{j} + n^{2}μ^{2} − 2nμ ∑_{i=1}^{n} μ_{i} ≤
≤ nμ + μa_{n}O(1) + 2 ∑_{1≤i<j≤n} EX_{i}X_{j} − n^{2}μ^{2}.

Further

∑_{1≤i<j≤n} EX_{i}X_{j} = ∑_{1≤i<j≤n} P{X_{i} = 1, X_{j} = 1} = I + II + III.

Hence Lemma 2.4 is proved.

Now let A^{(x)} denote the two-point set {0, x} and let Ξ(A^{(x)}, ∞) = ξ(0, ∞) + ξ(x, ∞) denote its total occupation time.

Lemma 2.5. For x ∈ Z_{d}, x ≠ 0, define γ_{x} := P(T_{x} = ∞) and recall the definitions of q_{x} and s_{x} in (1.26) and (1.27). Then

γ_{e_{i}} = γ_{−e_{i}} = γ, i = 1, 2, …, d,  (2.3)
γ_{x} ≥ γ,  (2.4)
q_{x} = 1 − \frac{γ}{1 − (1 − γ_{x})^{2}} ,  (2.5)
s_{x} = (1 − γ_{x})(1 − q_{x}),  (2.6)
q_{x} + s_{x} = 1 − \frac{γ}{2 − γ_{x}} ,  (2.7)
P(Ξ(A^{(x)}, ∞) = j) = (1 − q_{x} − s_{x})(q_{x} + s_{x})^{j}, j = 0, 1, ….  (2.8)

Proof. We show (2.3) first. For symmetric reason, γ_{±e_{i}} = γ_{±e_{j}}, i, j = 1, …, d. Hence

1 − γ = ∑_{i=1}^{d} P(S_{1} = e_{i})(1 − γ_{e_{i}}) + ∑_{i=1}^{d} P(S_{1} = −e_{i})(1 − γ_{−e_{i}}) = 2 ∑_{i=1}^{d} \frac{1}{2d}(1 − γ_{e_{1}}) = 1 − γ_{e_{1}},

proving (2.3).

To show (2.4), observe that starting from the origin, before hitting x with ∥x∥ > 1, the random walk should hit first the sphere S(x, 1) := {y : ∥y − x∥ = 1}. Hence

1 − γ_{x} = P(T_{S(x,1)} < ∞)(1 − γ) ≤ 1 − γ.  (2.9)

Now let Z(A) denote the number of visits in the set A up to the first return to zero, i.e.

Z(A) = ∑_{n=1}^{T} I{S_{n} ∈ A}.  (2.10)

Observe that

P(Z(A^{(x)}) = j + 1, T < ∞) = \{ \begin{matrix}q_{x} & if j = 0, \\ s_{x}^{2}q_{x}^{j−1} & if j = 1, 2, ... \end{matrix}  (2.11)

Summing up in (2.11) we get

∑_{j=0}^{∞} P(Z(A^{(x)}) = j + 1, T < ∞) = q_{x} + \frac{s_{x}^{2}}{1 − q_{x}} = P(T < ∞) = 1 − γ.  (2.12)

On the other hand, one can easily see that

1 − γ = P(T < ∞) = P(T < T_{x}) + P(T > T_{x}, T < ∞)
= P(T < T_{x}) + P(T > T_{x})P_{x}(T < ∞)
= P(T < T_{x}) + P(T > T_{x})P(T_{x} < ∞) = q_{x} + s_{x}(1 − γ_{x}),

i.e.

1 − γ = q_{x} + s_{x}(1 − γ_{x})  (2.13)

Now (2.12) and (2.13) easily imply (2.5) and (2.6), hence also (2.7).

Equation (2.8) was proved in [1] for general random walk. For completeness a short proof is presented here. The probability that the random walk, starting from 0, returns to 0 without hitting x, is q_{x}, while s_{x} is the probability that the random walk starting from 0 hits x without returning to 0. Similarly, for symmetric reason, q_{x} is also the probability of the random walk starting from x returns to x without hitting 0, and s_{x} is also the probability of the random walk starting from x hits 0 in finite time, without returning to x. Hence, the probability that the random walk starting from any point of A^{(x)}, returns to A^{(x)} in finite time, is q_{x} + s_{x}. This gives (2.8).

Similarly to Theorem A, we prove

Lemma 2.6.

1 − γ_{x}(n) := P(T_{x} < n) = 1 − γ_{x} + \frac{O(1)}{n^{d/2−1}} ,  (2.14)
q_{x}(n) := P(T < min(n, T_{x})) = q_{x} + \frac{O(1)}{n^{d/2−1}} ,  (2.15)
s_{x}(n) := P(T_{x} < min(n, T)) = s_{x} + \frac{O(1)}{n^{d/2−1}} ,  (2.16)

and O(1) is uniform in x.

Proof. For the proof of (2.14) see Jain and Pruitt [7].

To prove (2.15) and (2.16), observe that

q_{x} − q_{x}(n) = P(T < T_{x}, n ≤ T < ∞) ≤ P(n ≤ T < ∞) = γ(n) − γ,
s_{x} − s_{x}(n) = P(T_{x} < T, n ≤ T_{x} < ∞) ≤ P(n ≤ T_{x} < ∞) = γ_{x}(n) − γ_{x}.

Lemma 2.7. Let i < j. Then for t ≥ 1 integer we have

P(X_{i} = 1, X_{j} = 1) ≤ Cμ^{2} (1 + \frac{t^{d/(d−2)}}{(j − i)^{d/2}} (\frac{2}{2 − γ} )^{2t}) ,  (2.17)

where C is a constant, independent of i, j, t and μ = μ(t) = γ(1 − γ)^{t−1}.

Proof. Using (2.8) of Lemma 2.5, we get

P(X_{i} = 1, X_{j} = 1)

≤ ∑_{x∈Z_{d}} P(S_{j} − S_{i} = x, ξ(S_{i}, ∞) − ξ(S_{i}, i) + ξ(S_{j}, ∞) − ξ(S_{j}, i) ≥ 2t − 1)

= ∑_{x∈Z_{d}} P(S_{j−i} = x)P(Ξ(A^{(x)}, ∞) ≥ 2t − 1)

= ∑_{x∈Z_{d}} P(S_{j−i} = x)(q_{x} + s_{x})^{2t−1} = ∑_{x∈Z_{d},∥x∥≤R} + ∑_{x∈Z_{d},∥x∥>R},

where R will be chosen later. For estimating the first sum, we use γ_{x} ≥ γ (cf. (2.4) of Lemma 2.5), hence by (2.7)

q_{x} + s_{x} = 1 − \frac{γ}{2 − γ_{x}} ≤ \frac{2(1 − γ)}{2 − γ}.

On the other hand

P(S_{j−i} = x) ≤ \frac{C_{1}}{(j − i)^{d/2}} , x ∈ Z_{d}

with some constant C_{1}, not depending on x (cf. Spitzer [11], page 72).

Since the cardinality of the set {∥x∥ ≤ R} is a constant multiple of R^{d}, we have

∑_{x∈Z_{d},∥x∥≤R} ≤ \frac{C_{2}R^{d}}{(j − i)^{d/2}} (\frac{2(1 − γ)}{2 − γ})^{2t}  (2.18)

with some constant C_{2}.

For estimating the second sum, we use 1 − γ_{x} ≤ C_{3}R^{−d+2} for ∥x∥ > R (cf. Révész [9], page 241), hence

q_{x} + s_{x} ≤ 1 − γ + C_{4}R^{−d+2} = (1 − γ) (1 + \frac{C_{4}}{(1 − γ)R^{d−2}} ) .

Now choose R = t^{1/(d−2)}. Then

(q_{x} + s_{x})^{2t−1} ≤ C_{5}(1 − γ)^{2t}.

Here the constant C_{5} is independent of both x and t. Since

∑_{x∈Z_{d}} P(S_{j} − S_{i} = x) = 1,

we have

∑_{x∈Z_{d}, ∥x∥>R} ≤ C_{5}(1 − γ)^{2t} = C_{6}μ^{2}.

this together with (2.18) (putting R = t^{1/(d−2)} there) proves Lemma 2.7.

In the subsequent lemmas t_{n} is defined by (1.21).

Lemma 2.8. For t ≤ t_{n}, any ε > 0 and large enough n we have

I ≤ O(1)n^{2/d+ε} (n + (\frac{2}{2 − γ} )^{2t_{n}} ) μ^{2}(t).  (2.19)

Proof. Now we need to estimate the probability

P(X_{i} = 1, X_{j} = 1, ρ_{i} ≥ n^{α}).

Define the events B_{k} by

B_{k} = {ξ(S_{i}, ∞) − ξ(S_{i}, i) + ξ(S_{j}, ∞) − ξ(S_{j}, i) = k}

and consider the k time intervals between the consecutive visits of {S_{i}, S_{j}}. Then at least one of these intervals is larger than

\frac{ρ_{i}(t)}{k} ≥ \frac{n^{α}}{k}  (2.20)

(provided that {X_{i} = 1, X_{j} = 1, ρ_{i} ≥ n^{α}}). Denote this event by D_{k}. Similarly to the proof of Lemma 2.7 we have

P(X_{i} = 1, X_{j} = 1, ρ_{i} ≥ n^{α}) ≤ ∑_{x∈Z_{d}} P(S_{j} − S_{i} = x, ∪_{k≥2t−1}B_{k}D_{k})

≤ ∑_{x∈Z_{d}} P(S_{j−i} = x) ∑_{k≥2t−1} P(B_{k}D_{k} | S_{j} − S_{i} = x).

The event B_{k}D_{k}, under the condition S_{j} − S_{i} = x, means that placing a new origin at the point S_{i}, and starting the time at i, there are exactly k visits in the set A^{(x)}, and at least one time interval between consecutive visits is larger than n^{α}/k. Hence applying (2.8) of Lemma 2.5 and (2.15), (2.16) of Lemma 2.6, we get

P(B_{k}D_{k} | S_{j} − S_{i} = x) ≤ k(1 − q_{x} − s_{x})(q_{x} + s_{x})^{k−1} (q_{x} + s_{x} − q_{x} (\frac{n^{α}}{k} ) − s_{x} (\frac{n^{α}}{k} ))

≤ O(1)k (\frac{k}{n^{α}} )^{d/2−1} (1 − q_{x} − s_{x})(q_{x} + s_{x})^{k−1} ≤ O(1)k^{d/2}n^{2/d−1}(q_{x} + s_{x})^{k−1},

where O(1) is uniform in k and x, hence

∑_{k≥2t−1} P(B_{k}D_{k} | S_{j} − S_{i} = x) ≤ O(1)n^{2/d−1} ∑_{k≥2t−1} k^{d/2}(q_{x} + s_{x})^{k−1}
≤ O(1)n^{2/d−1}t^{d/2}(q_{x} + s_{x})^{2t−2}.

Proceeding now as in the proof of Lemma 2.7, we can estimate

P(X_{i} = 1, X_{j} = 1, ρ_{i} ≥ n^{α}) ≤ O(1)t^{d/2}n^{2/d−1}μ^{2}(t) (1 + \frac{t^{d/(d−2)}}{(j − i)^{d/2}} (\frac{2}{2 − γ} )^{2t})

and summing up for 1 ≤ i < j ≤ n, we get

I ≤ O(1)n^{2/d}t_{n}^{d/2} (n + t_{n}^{d/(d−2)} (\frac{2}{2 − γ} )^{2t_{n}} ) μ^{2}(t),

since t ≤ t_{n}. But t_{n} < λ log n, therefore any power of t_{n} can be estimated by n^{ε}, hence (2.19) follows.

Lemma 2.9. For t ≤ t_{n}, any ε > 0 and large enough n we have

II ≤ O(1)n^{2/d+ε} (n + n^{1−2/d} (\frac{2}{2 − γ} )^{2t_{n}} ) μ^{2}(t).  (2.21)

Proof. Using the estimate in Lemma 2.7 and summing up for i, j with 1 ≤ i < j ≤ min(i + 3n^{α}, n), using again that t_{n} < λ log n, a simple calculation shows (2.21).

Lemma 2.10. For t ≤ t_{n}, any ε > 0 and large enough n we have

III ≤ \frac{μ^{2}(t)n^{2}}{2} + O(1)n^{3/2}μ^{2}(t).  (2.22)

Proof. Let

A = {S_{i} is a new point i.e. S_{i} ≠ S_{j} j = 1, 2, …, i − 1},
B = {ξ(S_{i}, i + n^{α}) − ξ(S_{i}, i) ≥ t − 1},
D = {S_{j} is a new point},
E = {ξ(S_{j}, ∞) − ξ(S_{j}, j) ≥ t − 1},
D ⊂ G = \{ξ(S_{j}, j) − ξ (S_{j}, i + \frac{2(j − i)}{3}) = 0\} ,
B ⊂ H = {ξ(S_{i}, ∞) − ξ(S_{i}, i) ≥ t − 1}.

Recall the definition of γ(n) in Section 1 and let j > i + 3n^{α}. Then P{X_{i} = 1, X_{j} = 1, ρ_{i} < n^{α}} ≤ P{ABDE} ≤

≤ P(ABGE) = P(A)P(B)P(G)P(E) ≤
≤ P(A)P(H)P(G)P(E) =
= γ(i + 1)(1 − γ)^{t−1}γ((j − i)/3)(1 − γ)^{t−1}.

Clearly we have

III ≤ ∑ γ(i + 1)(1 − γ)^{t−1}γ((j − i)/3)(1 − γ)^{t−1} ≤
≤ γ^{2}(1 − γ)^{2t−2} ∑ (1 + \frac{O(1)}{(j − i)^{d/2−1}} ) (1 + \frac{O(1)}{i^{d/2−1}} ) ≤
≤ γ^{2}(1 − γ)^{2t−2} [\binom{n}{2} + O(1)(K + L + M)]

where the summations above and below go for {i, j : 1 ≤ i < i + 3n^{α} < j ≤ n} and

K = ∑ \frac{1}{i^{d/2−1}} ≤ na_{n},
L = ∑ \frac{1}{(j − i)^{d/2−1}} ≤ na_{n},
M = ∑ \frac{1}{i^{d/2−1}} \frac{1}{(j − i)^{d/2−1}} ≤ na_{n}.

Using a_{n} = O(1)n^{1/2} (see Lemma 2.3) we have (2.22).

Lemma 2.11. For t ≤ t_{n}, any ε > 0 and large enough n we have

σ_{n}^{2} = O(1)[nμ(t) + μ^{2}(t)n^{1.8}].  (2.23)

Proof is based on Lemmas 2.4, 2.8, 2.9 and 2.10. The numerical values of λ can be obtained by a result of Griffin [4]:

1 − γ_{3} = 0.341,
1 − γ_{4} = 0.193,
1 − γ_{5} = 0.131,
1 − γ_{6} = 0.104.

Consequently

λ_{3} = 0.929,
λ_{4} = 0.608,
λ_{5} = 0.492,
λ_{6} = 0.442.

By using t_{n} < λ log n, one can verify (numerically)

(\frac{2}{2 − γ} )^{2t_{n}} < n^{2λ log(2/(2−γ))} < n^{0.75}

for d = 3 and hence also for all d ≥ 3. By choosing an appropriate ε and putting the estimations (2.19), (2.21), (2.22) into (2.2), we can see, that the term n^{2}μ^{2} cancels out and all the other terms are smaller than the right hand side of (2.23), proving Lemma 2.11.

Lemma 2.11 implies

Lemma 2.12. For any 0 < C < B, t ≤ t_{n} and large enough n we have

σ_{n}(log n)^{C/2} ≤ O(1)((nμ(t))^{1/2}(log n)^{C/2} + μ(t)n^{0.9}(log n)^{C/2}) = o(1)nμ(t).

3. Proof of the Theorem

First we prove (1.24).

By Markov’s inequality for any C > 0 we have

P(|V (t, n) − nμ(t)| ≥ σ_{n}(log n)^{C/2}) ≤ (log n)^{−C}.

By Lemma 2.12, if C < B,

P(|V (t, n) − nμ(t)| ≥ o(1)nμ(t)) ≤ (log n)^{−C}.

Consequently, since t_{n} < λ log n,

P ( sup_{t≤t_{n}+1} \frac{|V (t, n) − nμ(t)|}{nμ(t)} ≥ o(1)) ≤ O(1)(log n)^{−C+1}.  (3.1)

Choose C > 2, n(k) = exp(k/ log k). (3.1) and Borel-Cantelli lemma imply

lim_{k→∞} sup_{t≤t(n(k))+1} |\frac{V (t, n(k))}{n(k)μ(t)} − 1| = 0 a.s.  (3.2)

Let n(k) ≤ n < n(k + 1). Then for t ≤ t_{n} we have

V (t, n(k)) ≤ V (t, n) ≤ V (t, n(k + 1))

and

lim_{k→∞} \frac{n(k + 1)}{n(k)} = 1.

Hence for any ε > 0 and large enough n,

\frac{V (t, n)}{nμ(t)} ≤ \frac{V (t, n(k + 1))}{n(k + 1)μ(t)} \frac{n(k + 1)}{n} ≤ (1 + ε) a.s.,

since t ≤ t_{n} ≤ t(n(k + 1)). Similarly,

\frac{V (t, n)}{nμ(t)} ≥ \frac{V (t, n(k))}{n(k)μ(t)} \frac{n(k)}{n} ≥ (1 − ε) a.s.

Hence we have (1.24).

Now we turn to the proof of (1.25).

Let

M(t, n) = V (t, n) − R(t, n) = ∑_{i=1}^{n}(X_{i} − Y_{i}).

Observe that X_{i} ≥ Y_{i} and hence M(t, n) is non-negative and non-decreasing in n. Moreover, by Lemma 2.2

E(X_{i} − Y_{i}) = P(X_{i} − Y_{i} = 1) ≤ P(X_{i} = 1, n − i ≤ ρ_{i}(t) < ∞) ≤ \frac{O(1)μ(t)t^{d/2}}{(n − i)^{d/2−1}} .

Consequently

0 ≤ \frac{EM(t, n)}{nμ(t)} ≤ \frac{O(1)(log n)^{d/2}}{n^{1/2}} .

By Markov’s inequality

P (sup_{t≤t_{n}} \frac{M(t, n)}{nμ(t)} > ε) ≤ \frac{O(1)(log n)^{d/2+1}}{n^{1/2}} .

On choosing n_{k} = k^{2+δ}, δ > 0, Borel-Cantelli lemma implies

lim_{k→∞} sup_{t≤t_{n_{k}}} \frac{M(t, n_{k})}{n_{k}μ(t)} = 0 a.s.

Using the monotonicity of M(t, n) in n, interpolating between n_{k} and n_{k+1} we get

lim_{n→∞} sup_{t≤t_{n}} \frac{M(t, n)}{nμ(t)} = 0 a.s.

This combined with (1.24) gives (1.25).

(1.23) and (1.22) are immediate from (1.25) and (1.24), since Q(t, n) = R(t, n)−R(t+1, n) and U(t, n) = V (t, n) − V (t + 1, n).

This completes the proof of the Theorem.

References

[1] Csáki, E., Földes, A., Révész, P., Rosen, J., Shi, Z., 2005. Frequently visited sets for random walks. Stochastic Process. Appl., to appear.

[2] Dvoretzky, A., Erdős, P., 1951. Some problems on random walk in space. Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley, pp. 353–367.

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

[4] Griffin, P., 1990. Accelerating beyond the third dimension: returning to the origin in simple random walk. Math. Scientist 15, 24–35.

[5] Hamana, Y., 1992. On the central limit theorem for the multiple point range of random walk. J. Fac. Sci. Univ. Tokyo 39, 339–363.

[6] Hamana, Y., 1995. On the multiple point range of three dimensional random walk. Kobe J. 12, 95–122.

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

[8] Pitt, J.H., 1974. Multiple points of transient random walk. Proc. Amer. Math. Soc. 43, 195–199.

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

[10] Révész, P., 2004. The maximum of the local time of a transient random walk. Studia Sci. Math. Hungar. 41, 379–390.

[11] Spitzer, F., 1976. Principles of Random Walk, 2nd. ed. Van Nostrand, Princeton.