Long excursions of a random walk

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

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

Summary. In [1] and [9] it was proved that the length of the longest excursion among the first n excursions of a plane random walk is nearly equal to the total sum of the lengths of these excursions. In this paper several results are proved in the same spirit, for plane random walks and for random walks in higher dimensions.

Keywords. Random walk, excursion length.

2000 Mathematics Subject Classification. 60G50.

1. Introduction

Consider a simple symmetric random walk on the lattice ZZ^{2}. This means that if the moving particle is in x ∈ ZZ^{2} at the moment n then at the moment n + 1 the particle moves with equal probabilities to any of the 4 neighbours of x independently of how the particle achieved x. Let S_{n} be the location of the particle after n steps and assume that S_{0} = 0. Introduce the following notations:

(i) ξ(x, n) := #{k : 0 < k ≤ n, S_{k} = x}, (x ∈ ZZ^{2}, n = 1, 2, …)

(ii) ξ(x, t) (x ∈ ZZ^{2}, t ≥ 0) is the continuous process obtained by linear interpolation from ξ(x, n) with ξ(x, 0) = 0,

(iii) ρ_{0} := 0, ρ_{k} := min{n : n > ρ_{k−1}, S_{n} = 0}, k ≥ 1,

(iv) r(k) := ρ_{k} − ρ_{k−1}, (v) M_{n}(1) ≥ M_{n}(2) ≥ … ≥ M_{n}(ξ(0, n) + 1) are the order statistics of the sequence

∗Research supported by the Hungarian National Foundation for Scientific Research, Grant No. T 029621.

r(1), r(2), …, r(ξ(0, n)), n − ρ_{ξ(0,n)},

(vi) H is the set of functions

h(m_{1}, m_{2}, τ, x) = \{ \begin{matrix}m_{1} if & 0 ≤ x < τ, \\ m_{2} if & τ ≤ x ≤ 1, \end{matrix}

where 0 ≤ m_{1} ≤ m_{2} ≤ 1, 0 ≤ τ ≤ 1.

In words, ξ(x, n) counts the number of visits to the site x during the first n steps and is called the local time of the random walk; ρ_{n}, which denotes the time of the n-th return to zero, is the “inverse” of ξ(0, k) in some sense. The sections between two consecutive returns are called excursions and so {r(k), k = 1, 2, …} denotes the sequence of the lengths of the excursions. Clearly, the sequence {M_{n}(1), …} denotes the ordered lengths of the excursions. In this paper we study some properties of the “long” excursions, which in spite of the recurrence of the random walk behaves quite differently from the case of dimension 1.

In [1] we proved the following Strassen type

THEOREM A. With probability one, the set of limit points of the sequence

\{\frac{πξ(0, nt)}{(log n) log_{3} n}, 0 ≤ t ≤ 1\}

is H.

Here and in what follows, log n := log max(n, e), and log_{p} n is the p-th iteration of log. The proof of Theorem A is based on the following

LEMMA A.

lim_{n→∞} \frac{M_{n}(1) + M_{n}(2)}{n} = 1 a.s.

We note that by the proof of Theorem A (cf. [1]) we easily get the following

THEOREM 1. With probability one, the set of limit points of the sequence

\{\frac{ξ(0, nt)}{ξ(0, n)}, 0 ≤ t ≤ 1\}

is H.

Lemma A easily implies

PROPOSITION A. ρ_{n+1} − ρ_{n} is either much smaller or much bigger than ρ_{n}.

In order to give a more accurate form of Proposition A, let {α_{n}} and {β_{n}} be sequences of positive numbers with

∑_{n=1}^{∞} \frac{1}{nα_{n}} < ∞, α_{n} ≥ log_{2} n, (1.1)

∑_{n=1}^{∞} \frac{1}{nβ_{n}} = ∞,  inf_{n≥1} β_{n} > 0. (1.2)

Further let

(1.3)  a_{n} = exp (\frac{n}{α_{n}} ) , b_{n} = exp (\frac{n}{β_{n}} ) , c_{n} = exp (\frac{n}{(1 + ε)β_{n}} ) (ε > 0).

Finally let

T_{n} = \frac{ρ_{n+1} − ρ_{n}}{ρ_{n}} .

Then we have

THEOREM 2. T_{n} ∉ (a_{n}^{−1}, a_{n}) a.s. (i)

for all but finitely many n, T_{n} ∈ (b_{n}^{−1}, c_{n}^{−1}) i.o. a.s. (ii)

T_{n} ∈ (c_{n}, b_{n}) i.o. a.s. (iii)

EXAMPLE 1.

α_{n} = (log n)^{1+δ} (δ > 0), β_{n} = log n

i.e.,

a_{n} = exp (\frac{n}{(log n)^{1+δ}} ) , b_{n} = exp (\frac{n}{log n}) , c_{n} = exp (\frac{n}{(1 + ε) log n})

satisfy the above conditions.

Theorem 2 clearly implies:

COROLLARY 1. Let

T_{n}^{∗} = \frac{ρ_{n+1} − ρ_{n}}{ρ_{n+1}} (n = 0, 1, 2, …).

Then

T_{n}^{∗} ∉ (a_{n}^{−1}, 1 − a_{n}^{−1}) a.s.,

for all but finitely many n,

T_{n}^{∗} ∈ (0, c_{n}^{−1}),  i.o. a.s.
T_{n}^{∗} ∈ (1 − c_{n}^{−1}, 1)  i.o. a.s.

Lemma A also implies that ρ_{n+k} − ρ_{n} for any k = 1, 2, …, is either much bigger or much smaller than ρ_{n}. A refined form of this statement is given in the next corollary.

COROLLARY 2. Let {a_{n}} be defined as above and assume that {a_{n}} is a non-decreasing sequence. Further let

a_{n}^{∗} = exp ( ∑_{j=n}^{∞} a_{j}^{−1}) − 1,
T_{n}^{(k)} = \frac{ρ_{n+k} − ρ_{n}}{ρ_{n}} , (k = 1, 2, …)
B_{n} = ⋃_{k=1}^{∞}{T_{n}^{(k)} ∈ (a_{n}^{∗}, a_{n})}.

Then among the events B_{n} only finitely many might occur with probability 1.

Note that if

a_{n} = exp (\frac{n}{(log n)^{1+δ}} ) (δ > 0)

then

a_{n}^{∗} ≤ exp (−\frac{n}{(log n)^{1+2δ}} ) .

The above results also imply that the waiting time

ν(n) = min{k : k ≥ n, ρ_{k+1} − ρ_{k} ≥ ρ_{n}}

is finite with probability 1 for any finite n. In fact we prove

THEOREM 3. Let {f_{n}} be a positive sequence such that n ↦ f_{n}/n is non-decreasing, then

lim sup_{n→∞} \frac{ν(n)}{f_{n}} = \{ \begin{matrix}0 \\ ∞ \end{matrix} , a.s. ⟺ ∑_{n} \frac{1}{f_{n}} \{ \begin{matrix}< ∞ \\ = ∞ \end{matrix} .

Corollary 1 claims that T_{n}^{∗} is either nearly 0 or nearly 1. At the same time Theorem 3 suggests that between n and 2n there exists about 1 integer k for which T_{k}^{∗} is nearly 1. This idea is formulated in our following

THEOREM 4.

(i)  lim_{n→∞} \frac{1}{log n} ∑_{k=0}^{n} T_{k}^{∗} = 1  a.s.,
(ii)  lim_{n→∞} P \{\frac{∑_{k=0}^{n} T_{k}^{∗} − log n}{\sqrt{log n}} ≤ x\} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{x} e^{−u^{2}/2} du,
(iii)  lim sup_{n→∞} \frac{∑_{k=0}^{n} T_{k}^{∗} − log n}{\sqrt{2(log n)(log_{3} n)}} = 1  a.s.

Now consider a simple symmetric random walk on the lattice ZZ^{d}, which means that at each step, the moving particle visits each of its (2d) neighbours (on ZZ^{d}) with equal probability 1/(2d). Let S_{n} be the location of the particle after n steps and assume that S_{0} = 0. Since the random walk in ZZ^{d}, d ≥ 3, is transient, the above results cannot be true. However if we consider the longest excursion away from some x ∈ ZZ^{d} completed by the time n, then it can be long. For i ≥ 0, define the random variable κ(i) by

S_{i+j} ≠ S_{i}, j = 1, 2, …, κ(i) − 1, S_{i+κ(i)} = S_{i}.

(If such κ(i) does not exist, we set κ(i) := ∞). Let

R(n) := max{κ(i) : i + κ(i) ≤ n},

which in words denotes the length of the longest completed excursion (away from any point) at time n.

THEOREM 5. Let d ≥ 3. With probability one,

lim_{n→∞} \frac{log R(n)}{log n} = \{ \begin{matrix}1 if d = 3, 4, \\ \frac{2}{d−2} if d ≥ 5. \end{matrix}

2. Preliminary results

THEOREM B. ([2]) For any δ > 0 we have

exp ((1 − δ)\frac{πn}{log_{2} n}) ≤ ρ_{n} ≤ exp(n(log n)^{1+δ}) a.s.,

for all but f initely many n. When n goes to infinity,

P{ρ_{1} > n} = P{ξ(0, n) = 0} = π(log n)^{−1} + O((log n)^{−2}),

and

P{ξ(0, n) ≥ x log n} = e^{−πx}(1 + O((log n)^{−1/4}))

uniformly for x ∈ (0, (log n)^{3/4}).

Since {ρ_{n} ≤ k} = {ξ(0, k) ≥ n}, Theorem B implies

PROPOSITION B. For any 2 ≤ m < n we have

|P\{m < ρ_{1} < n\} − \frac{π log (n/m)}{(log n) log m}| ≤ C (\frac{1}{(log m)^{2}} + \frac{1}{(log n)^{2}} )

where C > 0 is an absolute constant. Furthermore,

P{ρ_{n} ≤ e^{n/z}} = e^{−πz}(1 + O(n^{−1/7}))

uniformly for z ∈ (0, n^{3/7}) and

P{ρ_{n} > e^{n/z}} ≤ C(1 − e^{−πz}) ≤ Cπz, z ∈ [n^{−1/7}, 1].

Similarly for any 0 ≤ z_{1} < z_{2} < n^{3/7} and z_{2} − z_{1} ≤ 1 we have

|P \{exp (\frac{n}{z_{2}} ) ≤ ρ_{n} < exp (\frac{n}{z_{1}} )\} − πe^{−πz_{1}}(z_{2} − z_{1})| ≤ \frac{C}{n^{1/7}} .

In the proof of Theorem 4 we use results of Rényi [6], [7] concerning extreme elements. Let {ξ_{k}}_{k=1}^{∞} be a sequence of i.i.d. random variables having continuous distribution. ξ_{k} is called an extreme element if ξ_{k} > max_{1≤j≤k−1} ξ_{j}. By convention, ξ_{1} is counted as an extreme element. Let μ_{n} be the number of extreme elements among ξ_{1}, …, ξ_{n}.

THEOREM C. ([6], [7])

(i)  lim_{n→∞} \frac{μ_{n}}{log n} = 1  a.s.,
(ii)  lim_{n→∞} P \{\frac{μ_{n} − log n}{\sqrt{log n}} ≤ x\} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{x} e^{−u^{2}/2} du,
(iii)  lim sup_{n→∞} \frac{μ_{n} − log n}{\sqrt{2(log n)(log_{3} n)}} = 1  a.s.

In the proof of Theorem 5, we need the following two results concerning the simple symmetric random walk on ZZ^{d} (d ≥ 3).

THEOREM D. ([4]) Let d ≥ 3. Then as n → ∞

P{ρ_{1} = 2n} ∼ (1 − γ(d))^{2}P{S_{2n} = 0},

where γ(d) = P{ρ_{1} < ∞}.

THEOREM E. ([3]) Let f(n) ↑ ∞ be a positive integer valued function and let E_{n} be the event that the paths

{S_{0}, S_{1}, …, S_{n}} and {S_{n+f(n)+1}, S_{n+f(n)+2}, …}

have points in common. Then

(i) for d = 3, if f(n) = n(φ(n))^{2} and φ(n) is non-decreasing, then

(2.1)  P{E_{n} i.o.} = 0 or 1

depending on whether ∑_{k=1}^{∞}(φ(2^{k}))^{−1} converges or diverges,

(ii) for d = 4, if f(n) = nψ(n) and ψ(n) is non-decreasing, then we have (2.1) depending on whether ∑_{k=1}^{∞}(kψ(2^{k}))^{−1} converges or diverges,

(iii) for d ≥ 5, if

sup_{m≥n} \frac{f(m)}{m} ≥ C \frac{f(n)}{n}

(for some C > 0) then we have (2.1) depending on whether ∑_{k=1}^{∞}(f(k))^{(2−d)/d} converges or diverges.

3. Proof of Theorem 2

Let {α_{n}} and {β_{n}} satisfy (1.1) and (1.2), respectively, and let {a_{n}}, {b_{n}} and {c_{n}} be as in (1.3). Fix a constant δ ∈ (0, 1/3). Introduce the following notations:

d_{n} = exp ((1 − δ)\frac{πn}{log_{2} n}) ,
e_{n} = exp(n(log n)^{1+δ}),
A_{n}^{(1)} = {T_{n} ∈ (a_{n}^{−1}, a_{n})},
A_{n}^{(2)} = {T_{n} ∈ (b_{n}^{−1}, c_{n}^{−1})},
A_{n}^{(3)} = {T_{n} ∈ (c_{n}, b_{n})}.

Clearly we have

A_{n}^{(1)} = {A_{n}^{(1)} ∩ B_{n}} ∪ {A_{n}^{(1)} ∩ B_{n}^{c}},

where B_{n} := {ρ_{n} ∈ (d_{n}, e_{n})} and B_{n}^{c} denotes its complementary. By Theorem B among the events

A_{n}^{(i)} ∩ B_{n}^{c} ,

only finitely many might occur with probability 1.

Another application of Theorem B yields that

P {A_{n}^{(1)} ∩ B_{n}} = E [1_{B_{n}}P {A_{n}^{(1)} | ρ_{n}}] =
= E [1_{B_{n}} (\frac{2π log a_{n}}{log(a_{n}^{−1}ρ_{n}) · log(a_{n}ρ_{n})} + O (\frac{1}{log^{2}(a_{n}^{−1}ρ_{n})}))] .

On B_{n}, we have (recalling that α_{n} ≥ log_{2} n)

(3.1)  log(a_{n}^{−1}ρ_{n}) = log ρ_{n} − \frac{n}{α_{n}} ≥ (1 − δ)\frac{πn}{log_{2} n} − \frac{n}{log_{2} n} ≥ \frac{n}{log_{2} n},

so that

E [1_{B_{n}} · O (\frac{1}{log^{2}(a_{n}^{−1}ρ_{n})})] = O (\frac{(log_{2} n)^{2}}{n^{2}} ) .

On the other hand, since (3.1) also tells that log(a_{n}^{−1}ρ_{n}) ≥ (log ρ_{n})/2 on B_{n}, we have

E [1_{B_{n}} · \frac{log a_{n}}{log(a_{n}^{−1}ρ_{n}) · log(a_{n}ρ_{n})}] ≤ 2(log a_{n}) E [\frac{1_{B_{n}}}{(log ρ_{n})^{2}} ] ,

which, by writing N := ⌊(log_{2} n)/((1 − δ)π)⌋ and using Proposition B, is

≤ 2(log a_{n}) ∑_{i=0}^{N} E [\frac{1_{\{exp(n/(i+1))≤ρ_{n}<exp(n/i)\}}}{(n/(i + 1))^{2}} ] =
= 2(log a_{n}) ∑_{i=0}^{N} \frac{π exp(−πi) + O(n^{−1/7})}{(n/(i + 1))^{2}} =
= O (\frac{log a_{n}}{n^{2}} ) =
= O (\frac{1}{nα_{n}} ) .

Therefore,

P \{A_{n}^{(1)} ∩ B_{n}\} = O (\frac{(log_{2} n)^{2}}{n^{2}} ) + O (\frac{1}{nα_{n}} ) ,

which is summable for n. We obtain (i) of Theorem 2 by an application of the Borel–Cantelli lemma.

Now, we turn to the proof of (ii) and (iii). We first assume that for some n_{0},

β_{n} ≤ (log n)^{2}, n ≥ n_{0}.

We fix a constant θ > 1/(inf_{n≥1} β_{n}). Introduce the following notations:

E_{n} = {ρ_{n} ∈ (e^{θn}, e^{2θn})},
p_{n}^{(2)}(x) = P \{\frac{ρ_{1}}{x} ∈ (b_{n}^{−1}, c_{n}^{−1})\} ,
p_{n}^{(3)}(x) = P \{\frac{ρ_{1}}{x} ∈ (c_{n}, b_{n})\} .

We have, for i = 2 or 3,

P {E_{n} ∩ A_{n}^{(i)}} = E [1_{E_{n}} P {A_{n}^{(i)} | ρ_{n}}] = E [1_{E_{n}} · p_{n}^{(i)}(ρ_{n})] .

By Proposition B, there exist two positive constants C_{1} and C_{2} such that for all n,

(3.2)  \frac{C_{1}}{nβ_{n}} ≤ p_{n}^{(i)}(e^{nz}) ≤ \frac{C_{2}}{nβ_{n}} ,  i = 2 or 3,

uniformly for z ∈ (θ, 2θ). Therefore,

\frac{C_{1}}{nβ_{n}} P\{E_{n}\} ≤ P\{E_{n} ∩ A_{n}^{(i)}\} ≤ \frac{C_{2}}{nβ_{n}} P\{E_{n}\}.

Since C_{3} ≤ P{E_{n}} ≤ C_{4} for some positive constants C_{3} and C_{4}, we obtain:

(3.3)  \frac{C_{5}}{nβ_{n}} ≤ P\{E_{n} ∩ A_{n}^{(i)}\} ≤ \frac{C_{6}}{nβ_{n}} .

As a consequence, ∑_{n} P{E_{n} ∩ A_{n}^{(i)}} = ∞, for i = 2 or 3.

In order to complete the proof of (ii) and (iii) of Theorem 2 (in case β_{n} ≤ (log n)^{2}), we prove that the events A_{n}^{(i)} are nearly pairwise independent. Let 0 < n < N. Then we have

P{A_{n}^{(i)}E_{n}A_{N}^{(i)}E_{N}} = E [1_{A_{n}^{(i)}E_{n}E_{N}} · p_{N}^{(i)}(ρ_{N})] ,

which, according to (3.2), is

≤ C_{2} E [ \frac{1_{A_{n}^{(i)}E_{n}E_{N}}}{Nβ_{N}} ] ≤ \frac{C_{2}}{Nβ_{N}} P\{A_{n}^{(i)}E_{n}\}.

This, jointly considered with (3.3) and the fact that ∑_{n} P{E_{n} ∩ A_{n}^{(i)}} = ∞, yields

lim inf_{m→∞} \frac{∑_{n=1}^{m} ∑_{N=1}^{m}P\{A_{n}^{(i)}E_{n}A_{N}^{(i)}E_{N}\}}{( ∑_{n=1}^{m}P\{A_{n}^{(i)}E_{n}\})_{2}} < ∞.

According to the Kochen and Stone’s version ([5]) of the Borel–Cantelli lemma, we have, for i = 2 or 3, P{A_{n}^{(i)}E_{n} i.o.} > 0. Consequently,

P{A_{n}^{(i)} i.o.} > 0.

Since the event {A_{n}^{(i)} i.o.} is invariant under any finite permutation between the i.i.d.r.v.’s {ρ_{n+1} − ρ_{n}}_{n=0}^{∞}, an immediate application of the Hewitt–Savage zero-one law yields that P{A_{n}^{(i)} i.o.} = 1 for i = 2 or 3. This completes the proof of Theorem 2 (ii) and (iii) in case β_{n} ≤ (log n)^{2}.

For general {β_{n}}, we define

β̃_{n} := min (β_{n}, (log n)^{2}) ,

which satisfies (1.2), such that β̃_{n} ≤ (log n)^{2}. According to what we have just proved, with probability one,

(3.4)  T_{n} ∈ (exp (\frac{n}{(1 + ε)β̃_{n}} ) , exp (\frac{n}{β̃_{n}} )) ,

along a (random) subsequence {n(i)}_{i≥1}. If there existed a sub-subsequence of {n(i)}_{i≥1}, say {n(i(k))}_{k≥1}, such that β_{n(i(k))} > log^{2}(n(i(k))) for k ≥ 1, then β̃_{n(i(k))} = log^{2}(n(i(k))), and according to (i) of Theorem 2,

T_{n(i(k))} ∉ (exp (−\frac{n(i(k))}{β̃_{n(i(k))}}) , exp (\frac{n(i(k))}{β̃_{n(i(k))}})) ,

for all large k. This would contradict (3.4). As a consequence, β_{n(i)} ≤ log^{2}(n(i)) for all large i, say i ≥ i_{0}. Thus β̃_{n(i)} = β_{n(i)} for i ≥ i_{0}, which in view of (3.4) implies

T_{n(i)} ∈ (exp (\frac{n(i)}{(1 + ε)β̃_{n(i)}} ) , exp (\frac{n(i)}{β̃_{n(i)}} )) , i ≥ i_{0}.

This proves Theorem 2 (iii). A similar argument yields Theorem 2 (ii) for general {β_{n}}. □

Corollary 2 follows easily from Theorem 2 and the next lemma.

LEMMA 1. Let {g_{n}} be a positive non-decreasing sequence such that ∑_{n} (1/g_{n}) < ∞. If {ρ_{n}}_{n=1}^{∞} is an increasing sequence with ρ_{0} := 0, satisfying

\frac{ρ_{n+1} − ρ_{n}}{ρ_{n}} ∉ (g_{n}^{−1}, g_{n}), n ≥ n_{0},

then

\frac{ρ_{n+k} − ρ_{n}}{ρ_{n}} ∉ (g_{n}^{∗}, g_{n}), n ≥ n_{0}, k ≥ 1,

where g_{n}^{∗} := exp ( ∑_{j=n}^{∞} g_{j}^{−1}) − 1.

4. Proof of Theorem 3

At first we prove two lemmas.

LEMMA 2. For all integers n ≥ 1 and a ≥ 2n,

P\{ν(n) > a\} ≤ \frac{Cn}{a} + \frac{C}{n^{1/7}} ,

where C is an absolute, positive constant.

Proof. Clearly we have

P{ν(n) > a} = P{r(n + 1) < ρ_{n}, …, r(a) < ρ_{n}}.

Since r(n + 1), …, r(a), ρ_{n} are independent, we get

P{ν(n) > a} = E(F^{a−n}(ρ_{n})),

where F (x) = P{ρ_{1} < x} is the distribution function of ρ_{1}. By Theorem B, F (x) ≤ 1 − C_{7}/ log x for all x ≥ 2 if C_{7} > 0 is small enough. Hence

P\{ν(n) > a\} ≤ E (1 − \frac{C_{7}}{log ρ_{n}} )^{a−n} ≤ E exp (−\frac{C_{7}(a − n)}{log ρ_{n}}) ≤
≤ exp (−\frac{C_{7}(a − n)}{n}) + P\{log ρ_{n} > n^{8/7}\} +

+ E (exp (−\frac{C_{7}(a − n)}{log ρ_{n}}) 1_{\{n≤log ρ_{n}≤n^{8/7}\}}) .

Proposition B with z = n^{−1/7} gives

P\{log ρ_{n} > n^{8/7}\} ≤ \frac{C_{8}}{n^{1/7}} .

Integration by parts yields

E (exp (−\frac{C_{7}(a − n)}{log ρ_{n}}) 1_{\{n≤log ρ_{n}≤n^{8/7}\}}) =

= − ∫_{[n, n^{8/7}]} exp (−\frac{C_{7}(a − n)}{x}) d_{x}P\{log ρ_{n} > x\} =
= exp (−\frac{C_{7}(a − n)}{n}) P\{log ρ_{n} > n\} −

− exp (−\frac{C_{7}(a − n)}{n^{8/7}}) P\{log ρ_{n} > n^{8/7}\} +

+ ∫_{[n, n^{8/7}]} \frac{C_{7}(a − n)}{x^{2}} exp (−\frac{C_{7}(a − n)}{x}) P\{log ρ_{n} > x\} dx.

Hence we obtain

P\{ν(n) > a\} ≤ 2 exp (−\frac{C_{7}(a − n)}{n}) + \frac{C_{8}}{n^{1/7}} +

+ \frac{C_{7}(a − n)}{n} ∫_{n^{−1/7}}^{1} exp (−\frac{C_{7}(a − n)z}{n} ) P\{ρ_{n} > e^{n/z}\} dz,

which, by Proposition B, yields

P\{ν(n) > a\} ≤ 2 exp (−\frac{C_{7}(a − n)}{n}) + \frac{C_{8}}{n^{1/7}} +

+ \frac{C_{9}(a − n)}{n} ∫_{0}^{∞} exp (−\frac{C_{7}(a − n)z}{n} ) (1 − e^{−πz}) dz =

= 2 exp (−\frac{C_{7}(a − n)}{n}) + \frac{C_{8}}{n^{1/7}} + \frac{(C_{9}/C_{7}) πn}{C_{7}(a − n) + πn}.

Since a ≥ 2n and sup_{x>0}(xe^{−x}) < ∞, this yields the lemma. □

LEMMA 3. If n ≥ n_{0} is even, and if a is an integer with n < a ≤ n^{8/7}, then

P\{e^{a} < ρ_{n} − ρ_{n/2} < e^{2a}, ρ_{n/2} < e^{n}, r(i) < e^{a} for n + 1 ≤ i ≤ a\} ≥ \frac{C_{10} n}{a},

for some absolute constant C_{10} > 0.

Proof. By the strong Markov property,

P{e^{a} < ρ_{n} − ρ_{n/2} < e^{2a}, ρ_{n/2} < e^{n}, r(i) < e^{a} for n + 1 ≤ i ≤ a} =
= P{e^{a} < ρ_{n/2} < e^{2a}}P{ρ_{n/2} < e^{n}}(P{ρ_{1} < e^{a}})^{a−n}.

By Proposition B and Theorem B,

P\{e^{a} < ρ_{n/2} < e^{2a}\} ≥ \frac{C_{11} n}{a},
P{ρ_{n/2} < e^{n}} ≥ C_{12},
(P\{ρ_{1} < e^{a}\})^{a−n} ≥ (P\{ρ_{1} < e^{a}\})^{a} ≥ (1 − \frac{C_{13}}{a} )^{a} ≥ C_{14}.

The last inequality holds in the case a > C_{13} but is trivially true if a ≤ C_{13} (possibly with a smaller value of C_{14}) since min_{1≤a≤C_{13}}(P{ρ_{1} < e^{a}})^{a} > 0. Assembling these pieces completes the proof of Lemma 3. □

Now, we turn to the proof of Theorem 3.

Let {f_{n}} be a positive sequence such that n ↦ f_{n}/n is non-decreasing.

First, assume ∑_{n}(1/f_{n}) < ∞. Thus (f_{n}/n) → ∞. Let n_{k} = 2^{k} for all k ≥ 1, which implies ∑_{k}(n_{k}/f_{n_{k}}) < ∞. By Lemma 2, for all large k,

P\{ν(n_{k+1}) > f_{n_{k}}\} ≤ \frac{C_{15} n_{k+1}}{f_{n_{k}}} + \frac{C_{15}}{n_{k+1}^{1/7}} .

Therefore ∑_{k} P{ν(n_{k+1}) > f_{n_{k}}} < ∞. By the Borel–Cantelli lemma and the monotonicity of n ↦ ν(n), we have

lim sup_{n→∞} \frac{ν(n)}{f_{n}} ≤ 1 a.s.

Since replacing f_{n} by a constant multiple of f_{n} does not change the nature of the test, we conclude that the “lim sup” expression vanishes almost surely. This yields the first part of Theorem 3.

To prove the other part, we assume ∑_{n}(1/f_{n}) = ∞. Let again n_{k} = 2^{k}, which implies ∑_{k}(n_{k}/f_{n_{k}}) = ∞. It is well-known for the proof of this kind of integral test that we can assume without loss of generality that

n < f_{n} ≤ n^{8/7},

when n is sufficiently large. (For a rigorous justification, we may use a similar argument as the one at the end of Section 3). Define for large k (say k ≥ k_{0}) the events

A_{k} = {e^{f_{n_{k}}} < ρ_{n_{k}} − ρ_{n_{k}/2} < e^{2f_{n_{k}}} , ρ_{n_{k}/2} < e^{n_{k}},
r(i) < e^{f_{n_{k}}} for all n_{k} + 1 ≤ i ≤ f_{n_{k}}}.

By Lemma 3, for all k ≥ k_{0},

P\{A_{k}\} ≥ \frac{C_{10} n_{k}}{f_{n_{k}}} ,

which implies ∑_{k≥k_{0}} P{A_{k}} = ∞.

We now estimate P{A_{k} ∩ A_{ℓ}} for ℓ ≥ k + 2 (and k ≥ k_{0}). Observe that on A_{k}, we have

ρ_{f_{n_{k}}} < e^{2f_{n_{k}}} + e^{n_{k}} + (f_{n_{k}} − n_{k})e^{f_{n_{k}}} < e^{f_{n_{ℓ}}},

using the fact that 4f_{n_{k}} ≤ f_{n_{ℓ}} (which is a consequence of the monotonicity of n ↦ f_{n}/n). On the other hand, ρ_{n_{ℓ}} > e^{f_{n_{ℓ}}} on A_{ℓ}. This means that f_{n_{k}} < n_{ℓ} if A_{k} ∩ A_{ℓ} ≠ ∅. Write

ℓ_{0} = ℓ_{0}(k) := inf{ℓ ≥ k : n_{ℓ} > f_{n_{k}}},

and we have just proved that A_{k} ∩ A_{ℓ} = ∅ for ℓ < ℓ_{0}.

When ℓ ≥ ℓ_{0} + 1, we have n_{ℓ}/2 > f_{n_{k}}, so that the event A_{k} is independent of the variable ρ_{n_{ℓ}} − ρ_{n_{ℓ}/2}. Accordingly, for ℓ ≥ ℓ_{0} + 1,

P{A_{k} ∩ A_{ℓ}} ≤ P{A_{k}} P{ρ_{n_{ℓ}} − ρ_{n_{ℓ}/2} > e^{f_{n_{ℓ}}}} ≤
≤ P{ρ_{n_{k}} − ρ_{n_{k}/2} > e^{f_{n_{k}}} } P{ρ_{n_{ℓ}} − ρ_{n_{ℓ}/2} > e^{f_{n_{ℓ}}}} =
= P{ρ_{n_{k}/2} > e^{f_{n_{k}}} } P{ρ_{n_{ℓ}/2} > e^{f_{n_{ℓ}}}},

which yields that for ℓ ≥ ℓ_{0} + 1,

P\{A_{k} ∩ A_{ℓ}\} ≤ C_{16} \frac{n_{k}}{f_{n_{k}}} \frac{n_{ℓ}}{f_{n_{ℓ}}} ≤ C_{17} P\{A_{k}\}P\{A_{ℓ}\}.

Therefore,

∑_{k_{0}≤k≤ℓ≤n} P{A_{k} ∩ A_{ℓ}} = ∑_{k=k_{0}}^{n} (P{A_{k}} + P{A_{k} ∩ A_{k+1}} + P{A_{k} ∩ A_{ℓ_{0}}}) +

+ ∑_{k=k_{0}}^{n} ∑_{ℓ=ℓ_{0}+1}^{n} P{A_{k} ∩ A_{ℓ}} ≤

≤ 3 ∑_{k=k_{0}}^{n} P{A_{k}} + C_{17} ∑_{k=k_{0}}^{n} ∑_{ℓ=k}^{n} P{A_{k}}P{A_{ℓ}}.

Since ∑_{k≥k_{0}} P{A_{k}} = ∞, this yields

lim inf_{n→∞} \frac{∑_{k=k_{0}}^{n} ∑_{ℓ=k_{0}}^{n}P\{A_{k} ∩ A_{ℓ}\}}{( ∑_{k=k_{0}}^{n}P\{A_{k}\})_{2}} < ∞.

According to Kochen and Stone’s version of the Borel–Cantelli lemma ([5]), P{A_{k} i.o.} > 0. Since A_{k} ⊂ {ν(n_{k}) > f_{n_{k}}}, we obtain:

P \{lim sup_{n→∞} \frac{ν(n)}{f_{n}} ≥ 1\} > 0.

Clearly, {lim sup_{n→∞}(ν(n)/f_{n}) ≥ 1} is invariant under any finite permutation between the i.i.d.r.v.’s {ρ_{n+1} − ρ_{n}}_{n=0}^{∞}, the Hewitt–Savage zero-one law yields that

lim sup_{n→∞} \frac{ν(n)}{f_{n}} ≥ 1 a.s.

Replacing f_{n} by an arbitrary multiple of f_{n} implies that the “lim sup” expression is infinity almost surely. This completes the proof of Theorem 3. □

5. Proof of Theorem 4

First we define continuous random variables which are close to the discrete variables r_{k} = ρ_{k} − ρ_{k−1}. Let {ζ_{k}}_{k=1}^{∞} be an i.i.d. sequence of random variables, uniformly distributed on (0, 1) and also independent of the sequence {r_{k}}_{k=1}^{∞}. Define

r̂_{k} = r_{k} + ζ_{k}, ρ̂_{k} = ∑_{i=1}^{k} r̂_{i}, T̂_{k} = \frac{r̂_{k+1}}{ρ̂_{k+1}} , k = 1, 2, …

Then {r̂_{k}}_{k=1}^{∞} is a sequence of i.i.d. random variables with continuous distribution. Now let Ẑ_{1} = 1 and for k > 1 put Ẑ_{k} = 1 if r̂_{k+1} is an extreme element, i.e. r̂_{k+1} > max_{1≤i≤k} r̂_{i} and let Ẑ_{k} = 0 otherwise .

LEMMA 4. As k → ∞, we have

|Ẑ_{k} − T_{k}^{∗}| = O (exp (−\frac{k}{log^{2} k} )) a.s.

Proof. We have

|Ẑ_{k} − T_{k}^{∗}| ≤ |Ẑ_{k} − T̂_{k}| + |T̂_{k} − T_{k}^{∗}|.

Simple algebra shows, using 0 ≤ ζ_{k} ≤ 1, that

|T̂_{k} − T_{k}^{∗}| = |\frac{r̂_{k+1}}{ρ̂_{k+1}} − \frac{r_{k+1}}{ρ_{k+1}} | ≤ \frac{k + 1}{ρ_{k+1}} = O (exp (−\frac{k}{log^{2} k} )) a.s.,

the last identity following from Theorem B. This combined with Corollary 1 yields

T̂_{k} ∉ (exp (−\frac{k}{log^{2} k} ) , 1 − exp (−\frac{k}{log^{2} k} ))  a.s.,

for all but finitely many k. This means that for k large enough, Ẑ_{k} = 1 implies T̂_{k} ∈ (1 − exp (−\frac{k}{log^{2} k} ) , 1), while Ẑ_{k} = 0 implies T̂_{k} ∈ (0, exp (−\frac{k}{log^{2} k} )), so we have also

|Ẑ_{k} − T̂_{k}| = O (exp (−\frac{k}{log^{2} k} )) ,

proving Lemma 4. □ As a consequence, we have

|∑_{k=1}^{n} Ẑ_{k} − ∑_{k=1}^{n} T_{k}^{∗}| = O(1) a.s.,

as k → ∞. Since ∑_{k=1}^{n} Ẑ_{k} is the number of extreme elements up to n from a continuous distribution, Theorem 4 follows from Theorem C. □

6. Proof of Theorem 5

In this section, {S_{n}}_{n=0}^{∞} denotes a simple symmeric random walk on ZZ^{d} (d ≥ 3), starting from 0. Let E_{n} be the event as in Theorem E. Then P{E_{n} i.o.} = 0 if

(6.1) f(n) ≥ f^{∗}(n) := \{ \begin{matrix}n(log n)^{1+ε} & if d = 3 \\ n(log_{2} n)^{1+ε} & if d = 4 \\ n^{2/(d−2)}(log n)^{2(1+ε)/(d−2)} & if d ≥ 5. \end{matrix}

Observe that if there exists an excursion of length g(n) away from S_{n}, i.e. if

S_{n+j} ≠ S_{n}, j = 1, 2, …, g(n), S_{n+g(n)+1} = S_{n},

then E_{n} does not hold with f(n) = g(n), i.e. g(n) must be less than f^{∗}(n) of (6.1). Let N := n + f^{∗}(n) = h(n), i.e. n = h^{−1}(N). Hence

R(N) ≤ f^{∗}(n) = f^{∗}(h^{−1}(N)),

which, in turn, easily implies that

lim sup_{n→∞} \frac{log R(n)}{log n} ≤ \{ \begin{matrix}1 if d = 3, 4, \\ \frac{2}{d−2} if d ≥ 5, \end{matrix}

almost surely.

Now we turn to the proof of the lower bound in Theorem 5. Fix 0 < a < min(\frac{2}{d−2}, 1). Note that a < 1. It suffices to show that

(6.2)  lim inf_{n→∞} \frac{log R(n)}{log n} ≥ a a.s.

To this end, recall (see for example [8] p. 183) that P{S_{2n} = 0} ∼ 2(d/4π)^{d/2}n^{−d/2} (n → ∞). Therefore, an application of Theorem D reveals that for all n ≥ 1,

\frac{C_{18}}{n^{(d−2)/2}} ≤ P\{n ≤ ρ_{1} < ∞\} ≤ \frac{C_{19}}{n^{(d−2)/2}} , (6.3)

where C_{18} and C_{19} are two positive constants depending only on d. Define for n > j ≥ 0,

τ_{j} := inf{k > j : S_{k} = S_{j}},
A_{j}(n) := {j + n^{a} < τ_{j} ≤ j + Θn^{a}},

where the constant Θ = Θ(d) > 1 is chosen to satisfy Θ > (C_{19}/C_{18})^{2/(d−2)}.

For all j ≤ n − Θn^{a}, we have

P{A_{j}(n)} = P{n^{a} < ρ_{1} ≤ Θn^{a}} =
= P{n^{a} < ρ_{1} < ∞} − P{Θn^{a} < ρ_{1} < ∞},

which, in view of (6.3), yields

P\{A_{j}(n)\} ≥ \frac{C_{18}}{n^{a(d−2)/2}} − \frac{C_{19}}{(Θn^{a})^{(d−2)/2}} = \frac{C_{20}}{n^{a(d−2)/2}} ,

with C_{20} := C_{18} − C_{19}/Θ^{(d−2)/2} ∈ (0, ∞). On the other hand, for all j ≤ n − Θn^{a},

P\{A_{j}(n)\} ≤ P\{n^{a} < ρ_{1} < ∞\} ≤ \frac{C_{19}}{n^{a(d−2)/2}} ,

the last inequality following from (6.3). As a consequence,

C_{21} n^{1−a(d−2)/2} ≤ E { ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)}} ≤ C_{19} n^{1−a(d−2)/2}. (6.4)

Note that 1 − a(d − 2)/2 > 0.

Assume for the moment that we can show that

Var ( ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)}) = O (n^{2−a(d−2)−δ}) , (6.5)

for some δ > 0. Then by Chebyshev’s inequality and (6.4),

P \{| ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)} − E ( ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)})| > \frac{1}{2}E ( ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)})\} ≤

≤ \frac{4 Var ( ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)})}{(E(∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)}))^{2}} ≤ \frac{C_{22}}{n^{δ}} ,

which, by the Borel–Cantelli lemma, implies that almost surely for all large k,

∑_{j=1}^{n_{k}−Θn_{k}^{a}} 1_{A_{j}(n_{k})} ≥ \frac{1}{2}E ( ∑_{j=1}^{n_{k}−Θn_{k}^{a}} 1_{A_{j}(n_{k})}) ,

where n_{k} := ⌊k^{2/δ}⌋. By (6.4), E ( ∑_{j=1}^{n_{k}−Θn_{k}^{a}} 1_{A_{j}(n_{k})}) ≥ 2, so that for large k, there exists j ∈ [1, n_{k} − Θn_{k}^{a}] such that 1_{A_{j}(n_{k})} = 1. This yields R(n_{k}) ≥ n_{k}^{a}, and will complete the proof of (6.2), using the monotonicity of n ↦ R(n).

It remains to check (6.5). We have

E [( ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)})^{2} ] = E ( ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)}) + 2 ∑_{1≤i<j≤n−Θn^{a}} P{A_{i}(n)A_{j}(n)} =

= E ( ∑_{j=1}^{n−Θn^{a}} 1_{A_{j}(n)}) +

+2 ∑_{1≤i<j≤n−Θn^{a}} P{A_{i}(n), A_{j}(n), τ_{i} ≤ j}+

+2 ∑_{1≤i<j≤n−Θn^{a}} P{A_{i}(n), A_{j}(n), τ_{i} > j}.

By the Markov property,

P{A_{i}(n), A_{j}(n), τ_{i} ≤ j} ≤ P{A_{i}(n)} P{A_{j}(n)}.

On the other hand, if A_{i}(n)∩{τ_{i} > j} ≠ ∅, then j < τ_{i} ≤ i+Θn^{a}, which implies j −i ≤ Θn^{a}. The proof of (6.5) is thus reduced to showing the following: for some δ > 0,

∑_{(i,j)∈Ω(n)} P\{A_{i}(n), A_{j}(n), τ_{i} > j\} = O (\frac{n^{2−a(d−2)}}{n^{δ}} ) , (6.6)

where Ω(n) := {(i, j) : 1 ≤ i < j ≤ n − Θn^{a}, j − i ≤ Θn^{a}}.

The proof of (6.6) will be carried out in a few steps, namely, we will show that

(6.7)  ∑_{(i,j)∈Ω(n)} P \{A_{i}(n), A_{j}(n), τ_{j} > τ_{i} > j + \frac{n^{a}}{2} \} = O (n^{1−a(d−2)/2}b_{n}) ,

(6.8)  ∑_{(i,j)∈Ω(n)} P \{A_{i}(n), A_{j}(n), j < τ_{i} ≤ j + \frac{n^{a}}{2} \} = O (\frac{n^{2−a(d−2)/2}}{n^{1−a}} ) ,
(6.9)  ∑_{(i,j)∈Ω(n)} P {A_{i}(n), A_{j}(n), τ_{j} ≤ τ_{i}} = O (n^{1−a(d−2)/2}b_{n}) ,

where b_{n} := ∑_{k=1}^{Θn^{a}} k^{−(d−2)/2}. Since b_{n} = O(n^{1−a(d−2)/2−δ}) for some δ > 0 (recalling that a < min(\frac{2}{d−2}, 1)), the estimates (6.7)–(6.9) together suffice to yield (6.6), hence the lower bound in Theorem 5.

To check (6.7), observe that

I_{1} := P \{A_{i}(n), A_{j}(n), τ_{j} > τ_{i} > j + \frac{n^{a}}{2} \}
≤ P {τ_{i} ∈ (j + n^{a}/2, i + Θn^{a}], τ_{j} > τ_{i}} .

Applying the strong Markov property at τ_{i} gives that

I_{1} ≤ E (1_{{τ_{i}∈(j+n^{a}/2,i+Θn^{a}]}}p_{1}(S_{i}, S_{j})) ,

where p_{1}(y, x) := P^{y}{ρ_{1}(x) < ∞} for x ∈ Z^{d} and y ∈ Z^{d}, and P^{y} is the probability under which the random walk starts from y. According to Erdős and Taylor [2], there exists a constant C_{23} = C_{23}(d) such that for all (x, y) ∈ ZZ^{d} × ZZ^{d},

P^{y} \{ρ_{1}(x) < ∞\} ≤ \frac{C_{23}}{(∥x − y∥ + 1)^{d−2}} . (6.10)

Therefore

I_{1} ≤ C_{23} E [ \frac{1_{\{τ_{i}∈(j+n^{a}/2,i+Θn^{a}]\}}}{(∥S_{j} − S_{i}∥ + 1)^{d−2}} ] = C_{23} E [ \frac{p_{2}(S_{j}, S_{i})}{(∥S_{j} − S_{i}∥ + 1)^{d−2}} ] ,

where p_{2}(y, x) := P^{y}{n^{a}/2 < ρ_{1}(x) ≤ i+Θn^{a}−j} (and we have applied the Markov property at j).

We now estimate p_{2}(y, x). According to [8] p. 184, sup_{x∈ZZ^{d}} P{S_{n} = x} ≤ C_{24}/n^{d/2}, so that for m < n,

P^{y} \{m ≤ ρ_{1}(x) < n\} ≤ ∑_{k=m}^{n−1} P^{y} \{S_{k} = x\} ≤ ∑_{k=m}^{n−1} \frac{C_{24}}{k^{d/2}} ≤ C_{24} \frac{n − m}{m^{d/2}}.

Therefore, for all m < n,

sup_{x∈ZZ^{d}} sup_{y∈ZZ^{d}} P^{y} \{m ≤ ρ_{1}(x) < n\} ≤ C_{24} \frac{n}{m^{d/2}} . (6.11)

In particular, p_{2}(y, x) ≤ C_{24}Θn^{a}/(n^{a}/2)^{d/2} for all x and y, so that

I_{1} ≤ \frac{C_{25}}{n^{a(d−2)/2}} E [ \frac{1}{(∥S_{j} − S_{i}∥ + 1)^{d−2}} ] .

Recall Lemma 16.5 of [8] p. 184: P{S_{n} = x} ≤ C_{26} n^{−d/2} exp(−∥x∥^{2}/2n) for all x ∈ ZZ^{d} and n ≥ 1, from which it follows that

E ((∥S_{n}∥ + 1)^{−(d−2)}) ≤ C_{27} n^{−(d−2)/2}, n ≥ 1. (6.12)

Accordingly,

I_{1} ≤ \frac{C_{25}}{n^{a(d−2)/2}} \frac{C_{27}}{(j − i)^{(d−2)/2}} .

This implies (6.7).

Now let us check (6.8). Clearly,

I_{2} := P \{A_{i}(n), A_{j}(n), j < τ_{i} ≤ j + \frac{n^{a}}{2} \} ≤
≤ P {τ_{i} ∈ (i + n^{a}, j + n^{a}/2], j < τ_{i}, τ_{j} ∈ (j + n^{a}, j + Θn^{a}]} .

Applying the strong Markov property at τ_{i} gives

I_{2} ≤ E ( 1_{{τ_{i}∈(i+n^{a},j+n^{a}/2], j<τ_{i}}} p_{3}(S_{i}, S_{j}, τ_{i})) ,

where p_{3}(y, x, ℓ) := P^{y}{ρ_{1}(x) ∈ (j + n^{a} − ℓ, j + Θn^{a} − ℓ]}. By (6.11), on the event {τ_{i} ∈ (i + n^{a}, j + n^{a}/2]}, we have p_{3}(S_{i}, S_{j}, τ_{i}) ≤ C_{24}Θn^{a}/(n^{a}/2)^{d/2}, so that

I_{2} ≤ \frac{C_{28}}{n^{a(d−2)/2}} P\{τ_{i} ∈ (i + n^{a}, j + n^{a}/2]\} =
= \frac{C_{28}}{n^{a(d−2)/2}} P\{n^{a} < ρ_{1} ≤ j + n^{a}/2 − i]\} ≤
≤ \frac{C_{28}}{n^{a(d−2)/2}} \frac{C_{29}}{n^{a(d−2)/2}} ,

the last inequality following from (6.11) (recalling that j − i ≤ Θn^{a}). Therefore,

∑_{(i,j)∈Ω(n)} I_{2} ≤ n Θn^{a} \frac{C_{28}C_{29}}{n^{a(d−2)}} = ΘC_{28}C_{29} \frac{n^{2−a(d−2)}}{n^{1−a}} ,

proving (6.8).

Finally, to verify (6.9), we observe that

I_{3} := P {A_{i}(n), A_{j}(n), τ_{j} ≤ τ_{i}} ≤
≤ P {τ_{j} ∈ (j + n^{a}, j + Θn^{a}], τ_{i} ≥ τ_{j}} =
= E (1_{{τ_{j}∈(j+n^{a},j+Θn^{a}]}} p_{1}(S_{j}, S_{i})) ,

where p_{1}(y, x) = P^{y}{ρ_{1}(x) < ∞} as before, and we have applied in the last equality the strong Markov property at τ_{j}. By (6.10), p_{1}(S_{j}, S_{i}) ≤ C_{23}/(∥S_{j} − S_{i}∥ + 1)^{d−2}, so that

I_{3} ≤ C_{23} E [\frac{1_{\{τ_{j}∈(j+n^{a},j+Θn^{a}]\}}}{(∥S_{j} − S_{i}∥ + 1)^{d−2}} ] .

Using the Markov property at j, we get

I_{3} ≤ C_{23} E [\frac{p_{4}(S_{j}, S_{j})}{(∥S_{j} − S_{i}∥ + 1)^{d−2}} ] ,

where p_{4}(y, y) := P^{y}{ρ_{1}(y) ∈ (n^{a}, Θn^{a}]} = P{n^{a} < ρ_{1} ≤ Θn^{a}} ≤ C_{24}Θn^{−a(d−2)/2} by means of (6.11). Combined with (6.12), it follows that

I_{3} ≤ \frac{C_{23}C_{24}ΘC_{27}}{(j − i)^{(d−2)/2}n^{a(d−2)/2}} .

This yields (6.9), and completes the proof of the lower bound in Theorem 5. □

Acknowledgements

Cooperation between the authors was supported by the joint French–Hungarian Intergovernmental Grant “Balaton” (grant no. F25/97).

References

[1] CSÁKI, E. - RÉVÉSZ, P. - ROSEN, J. (1998) Functional laws of the iterated logarithm for local times of recurrent random walks on ZZ^{2}. Ann. Inst. Henri Poincaré, Probabilités et Statistiques 34, 545-563.

[2] ERDŐS, P. - TAYLOR, S.J. (1960) Some problems concerning the structure of random walks paths. Acta Math. Acad. Sci. Hung. 11, 137-162.

[3] ERDŐS, P. - TAYLOR, S.J. (1960) Some intersection properties of random walk paths. Acta Math. Acad. Sci. Hung. 11, 231–248.

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

[5] KOCHEN, S.B. - STONE, C.J. (1964) A note on the Borel-Cantelli lemma. Illinois J. Math. 8, 248-251.

[6] RÉNYI, A. (1962) On the extreme elements of observations. MTA III. Oszt. Közl. 12, 105–121 (in Hungarian). English translation: Selected Papers of Alfréd Rényi Vol. 3, pp. 50–65. Publishing House of the Hungarian Academy of Sciences, Budapest, 1976.

[7] RÉNYI, A. (1962) Théorie des éléments saillants d’une suite d’observations. Annales Fac. Sci. Univ. Clermont-Ferrand 2, No. 8, 7–12.

[8] RÉVÉSZ, P. (1990) Random Walk in Random and Non-Random Environments, World Scientific, Singapore, 1990.

[9] RÉVÉSZ, P. - WILLEKENS, E. (1988) On the maximal distance between two renewal epochs. Stochastic Process. Appl. 27, 21-41.

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

  csaki@math-inst.hu                            revesz@ci.tuwien.ac.at

Zhan Shi

Laboratoire de Probabilités UMR 7599

Université Paris VI

4 Place Jussieu

F-75252 Paris Cedex 05

France

  zhan@proba.jussieu.fr