ON THE EXCURSIONS OF TWO-DIMENSIONAL RANDOM WALK AND WIENER PROCESS

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

Antónia Földes^{∗∗} City University of New York, 2800 Victory Blvd., Staten Island, New York 10314, U.S.A. E-mail address: afoldes@email.gc.cuny.edu

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

Zhan Shi Laboratoire de Probabilités, Université Paris VI, 4 Place Jussieu, F-75252 Paris Cedex 05, France E-mail address: zhan@proba.jussieu.fr

Abstract

Consider a simple symmetric random walk on the plane. Its portion between two consecutive returns to zero are called excursions. We study the sum of the excursions when the two largest ones are eliminated from the sum. Similar investigations are carried out for two-dimensional Wiener process.

AMS 1991 Subject Classification: Primary 60J15; Secondary 60F15, 60J55. Keywords: Planar random walk; Local time; Excursions Short title: Excursions of random walk

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

T 019346 and T 029621.

∗∗Research supported by a PSC CUNY Grant, No. 6-67383.

1. Introduction and main results

Let X_{1}, X_{2},... be a sequence of independent identically distributed random vectors with

P\{X_{1} = (0, 1)\} = P\{X_{1} = (0, −1)\} = P\{X_{1} = (1, 0)\} = P\{X_{1} = (−1, 0)\} = \frac{1}{4}

and let S_{0} = 0, S_{n} = X_{1} + X_{2} + ... + X_{n} (n = 1, 2, ...) be a random walk on Z^{2} (0 = (0, 0)). Its local time is defined by

ξ(a, n) = #{k; 0 < k ≤ n, S_{k} = a},

where a = (a_{1}, a_{2}) is a lattice point on the plane. Put ξ(n) = ξ(0, n). Let log_{j} denote the j-th iterated logarithm.

Erdős and Taylor (1960) proved the following results:

Theorem A1 (Erdős and Taylor (1960)):

(1.1)  lim_{n→∞} P{ξ(n) < x log n} = 1 − e^{−πx}, x > 0.
(1.2)  lim sup_{n→∞} \frac{πξ(n)}{log n log_{3} n} = 1 a.s.
(1.3)  lim_{n→∞} \frac{ξ(n)(log_{2} n)^{1+ε}}{log n} = ∞ a.s., ε > 0.
(1.4)  lim inf_{n→∞} \frac{ξ(n) log_{2} n}{log n} = 0 a.s.

Introduce

ρ_{0} = 0,

ρ_{k} = inf{n; n > ρ_{k−1}, S_{n} = 0}, k = 1, 2, ... (1.5)

the consecutive return times of the planar random walk to the origin. Put τ_{k} = ρ_{k} − ρ_{k−1}, k = 1, 2, . . .. The portion of the random walk between ρ_{k−1} and ρ_{k} is called the k-th excursion.

Theorem A1 can be rewritten as Theorem A2 (Erdős and Taylor (1960)):

(1.6)  lim_{N→∞} P{log ρ_{N} < xN} = e^{−π/x}, x > 0.
(1.7)  lim inf_{N→∞} \frac{log_{2} N}{N} log ρ_{N} = π a.s.
(1.8)  lim_{N→∞} \frac{log ρ_{N}}{N(log N)^{1+ε}} = 0 a.s., ε > 0.
(1.9)  lim sup_{N→∞} \frac{log ρ_{N}}{N log N} = ∞ a.s.

We need also the following result. Theorem B (Dvoretzky and Erdős (1951), Erdős and Taylor (1960)): (1.10) P\{ρ_{1} > n\} = P\{ξ(n) = 0\} = \frac{π}{log n} + O((log n)^{−2}), as n → ∞.

Now let κ(n) be the last return to the origin before time n, i.e. κ(n) = max{j; j ≤ n, S_{j} = 0} = ρ_{ξ(n)}. (1.11)

Denote by

M_{n}^{(1)} ≥ M_{n}^{(2)} ≥ … ≥ M_{n}^{(ξ(n)+1)}

the order statistics of the sequence τ_{1}, τ_{2}, …, τ_{ξ(n)}, n − κ(n). It was shown in Csáki et al. (1998) that

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

Our aim here is to investigate the upper and lower functions of

R(n) = n − M_{n}^{(1)} − M_{n}^{(2)} = ∑_{k=3}^{ξ(n)+1} M_{n}^{(k)}. (1.13)

Recall the following definitions (Révész (1990)): Definition 1. The function a_{1}(t) belongs to the upper-upper class of {Z(t)} (a_{1} ∈ UUC(Z(t))) if for almost all ω ∈ Ω there exists a t_{0} such that Z(t) < a_{1}(t) if t > t_{0}.

Definition 2. The function a_{2}(t) belongs to the upper-lower class of {Z(t)} (a_{2} ∈ ULC(Z(t))) if for almost all ω ∈ Ω there exists a sequence t_{1} < t_{2} < … such that lim_{k→∞} t_{k} = ∞ and Z(t_{k}) ≥ a_{2}(t_{k}), k = 1, 2, …

Definition 3. The function a_{3}(t) belongs to the lower-upper class of {Z(t)} (a_{3} ∈ LUC(Z(t))) if for almost all ω ∈ Ω there exists a sequence t_{1} < t_{2} < … such that lim_{k→∞} t_{k} = ∞ and Z(t_{k}) ≤ a_{3}(t_{k}), k = 1, 2, …

Definition 4. The function a_{4}(t) belongs to the lower-lower class of {Z(t)} (a_{4} ∈ LLC(Z(t))) if for almost all ω ∈ Ω there exists a t_{0} such that Z(t) > a_{4}(t) if t > t_{0}.

Concerning κ(n), the following result is proved in Erdős and Taylor (1960).

Theorem C (Erdős and Taylor (1960)): Let f(n) be a non-increasing function. Then

∑_{k=1}^{∞} f(2^{2^{k}}) < ∞ ⟹ n^{f(n)} ∈ LLC(κ(n)) (1.14)

and

∑_{k=1}^{∞} f(2^{2^{k}}) = ∞ ⟹ n^{f(n)} ∈ LUC(κ(n)). (1.15)

We prove the following results:

Theorem 1.1. For any ε > 0, c > 0

(1.16)  \frac{n}{exp (\frac{log n}{(log_{2} n)^{1+ε}} )} ∈ UUC(R(n)),
(1.17)  \frac{n}{exp (\frac{c log n}{log_{2} n})} ∈ ULC(R(n)),

(1.18)  exp (\frac{c log n}{log_{2} n}) ∈ LUC(R(n)),
(1.19)  exp (\frac{log n}{(log_{2} n)^{1+ε}} ) ∈ LLC(R(n)).

Similar investigations can be carried out also for two-dimensional Wiener process with slight modifications. This is necessary, since every point is polar for the Wiener process, and, on the other hand, local time (as occupation density) does not exist.

So there is no meaning to speak about excursions away from the point 0. Instead, we consider excursions away from the unit circle.

Let W (t) = (W_{1}(t), W_{2}(t)), t ≥ 0 be a two-dimensional Wiener process, where W_{1}(t) and W_{2}(t) are two independent one-dimensional standard Wiener processes with W_{1}(0) = W_{2}(0) = 0. Put ||W (t)|| = \sqrt{W_{1}^{2}(t) + W_{2}^{2}(t)}. It is well known that {||W (t)||, t ≥ 0} is a two-dimensional Bessel process, admitting countably many excursions away from the point 1. Let

V_{t}^{(1)} ≥ V_{t}^{(2)} ≥ … (1.20)

be the ordered lengths of these excursions up to time t, including the interval from the origin to the first hitting of the point 1 and the possibly incomplete last excursion (the interval from the last hitting of the point 1 to t). Then

∑_{i=1}^{∞} V_{t}^{(i)} = t

and we may consider

Q(t) = t − V_{t}^{(1)} − V_{t}^{(2)} = ∑_{i=3}^{∞} V_{t}^{(i)}. (1.21)

The upper and lower classes for Q(·) are in complete analogue to those for R(·).

Theorem 1.2. For any ε > 0, c > 0

(1.22)  \frac{t}{exp (\frac{log t}{(log_{2} t)^{1+ε}} )} ∈ UUC(Q(t)),
(1.23)  \frac{t}{exp (\frac{c log t}{log_{2} t})} ∈ ULC(Q(t)),

(1.24)  exp (\frac{c log t}{log_{2} t}) ∈ LUC(Q(t)),
(1.25)  exp (\frac{log t}{(log_{2} t)^{1+ε}} ) ∈ LLC(Q(t)).

In Section 2 we prove Theorem 1.1, while Section 3 contains the proof of Theorem 1.2. Since the proof of Theorem 1.2 is similar to that of Theorem 1.1, except that the results of Erdős and Taylor (Theorems A,B,C) are not available for Wiener case, we give first the analogues of these results and then sketch the proof of Theorem 1.2.

2. Proof of Theorem 1.1.

First we prove (1.16). Let (2.1) f_{1}(n) = exp (\frac{log n}{(log_{2} n)^{1+ε}} ) with some ε > 0. It follows from Theorem A that we have almost surely ξ(n) ≤ log n log_{3} n for large enough n. Put

ν_{n} = ∑_{1≤i≤log n log_{3} n} I \{\frac{n}{f_{1}(n)} ≤ τ_{i} ≤ n\} , (2.2)

where I{} denotes the indicator of the event in the brackets. Let α = 1/(2 + ε), n_{k} = [exp (e^{k^{α}})], N_{k} = [log n_{k} log_{3} n_{k}] = [α(log k)e^{k^{α}}] + O(1) and

\overline{ν}_{k} = ∑_{i=1}^{N_{k+1}} I \{\frac{n_{k}}{f_{1}(n_{k})} ≤ τ_{i} ≤ n_{k+1}\} . (2.3)

Obviously, \overline{ν}_{k} has binomial distribution with parameters (N_{k+1}, p_{k}), where

p_{k} = P \{\frac{n_{k}}{f_{1}(n_{k})} ≤ τ_{1} ≤ n_{k+1}\} .

We obtain from Theorem B that as k → ∞

p_{k} = \frac{π}{log \frac{n_{k}}{f_{1}(n_{k})}} − \frac{π}{log n_{k+1}} + O((log n_{k})^{−2}) = \frac{π}{e^{k^{α}} (1 − \frac{1}{k^{(1+ε)α}} )} − \frac{π}{e^{(k+1)^{α}}} + O(e^{−2k^{α}})

= (\frac{π}{e^{k^{α}} (1 − \frac{1}{k^{(1+ε)α}} )} − \frac{π}{e^{k^{α}}} ) + (\frac{π}{e^{k^{α}}} − \frac{π}{e^{(k+1)^{α}}} ) + O(e^{−2k^{α}})

= (\frac{π}{k^{(1+ε)α}e^{k^{α}}} + \frac{απ}{k^{1−α}e^{k^{α}}} ) (1 + o(1)) = \frac{(1 + α)π}{k^{(1+ε)/(2+ε)}e^{k^{α}}} (1 + o(1)).

An easy calculation shows that

N_{k+1}^{2}p_{k}^{2} = O (\frac{log^{2} k}{k^{(2+2ε)/(2+ε)}} ) . (2.4)

For large k we have

P\{\overline{ν}_{k} ≥ 2\} = ∑_{j=2}^{N_{k+1}} \binom{N_{k+1}}{j}p_{k}^{j}(1 − p_{k})^{N_{k+1}−j} ≤ (2.5)

≤ ∑_{j=2}^{N_{k+1}} \frac{(N_{k+1}p_{k})^{j}}{2} ≤ (N_{k+1}p_{k})^{2} = O (\frac{log^{2} k}{k^{(2+2ε)/(2+ε)}} ) ,

hence by Borel-Cantelli lemma P\{\overline{ν}_{k} ≥ 2 i.o.\} = 0, (2.6) i.e. with probability 1 for large enough k we have \overline{ν}_{k} ≤ 1 and a fortiori for large enough n, ν_{n} ≤ 1. Hence

R(n) ≤ ξ(n)\frac{n}{f_{1}(n)} ≤ log n log_{3} n\frac{n}{f_{1}(n)} (2.7)

eventually. Since ε > 0 is arbitrary, this shows (1.16).

Now we turn to the proof of (1.17). Define the events

B_{N} = ⋃_{1≤i≠j≤N} B_{N;i,j} (2.8)

with

B_{N; i,j} = \{ (1 − \frac{c}{log N} ) log τ_{j} < log τ_{i} < log τ_{j},

(2.9) 3N/2 < log τ_{j} < 2N, max_{1≤r≤N;r≠i,j} log τ_{r} ≤ N}.

We show that P{B_{N} i.o.} = 1. Clearly, for N large enough,

P{B_{N}} = N(N − 1)q_{N} (P{log τ_{1} < N})^{N−2} ,

where

q_{N} = P \{(1 − \frac{c}{log N} ) log τ_{1} < log τ_{2} < log τ_{1}, 3N/2 < log τ_{1} < 2N\} .

To estimate q_{N}, one can condition on log τ_{1} = x ∈ (3N/2, 2N) and use Theorem B to see

P \{(1 − \frac{c}{log N} ) x < log τ_{2} < x\} ∼ \frac{cπ}{x log N} ,

which implies for large N

\frac{cπ}{4N^{2} log N} ≤ q_{N} ≤ \frac{2cπ}{N^{2} log N} .

Using Theorem B again, it can be seen that

lim_{N→∞} (P{log τ_{1} < N})^{N−2}

is finite and positive, so we arrive at

\frac{C_{1}}{log N} ≤ P\{B_{N}\} ≤ \frac{C_{2}}{log N} (2.10)

with some positive constants C_{1} and C_{2}.

Put N_{k} = [e^{k}], then P{B_{N_{k}}} > C_{1}/k, therefore ∑_{k} P{B_{N_{k}}} = ∞. Now we estimate P{B_{N_{k}}B_{N_{l}}}.

For large enough k + 1 ≤ l we have

2N_{k} < \frac{3N_{l}}{2} (1 − \frac{c}{log N_{l}} ) ,

and it is easy to see that

P{B_{N_{k}}B_{N_{l}}} ≤ P{B_{N_{k}}}P{B̃_{N_{k},N_{l}}}, (2.11)

where

B̃_{N_{k},N_{l}} = ⋃_{N_{k}<i≠j≤N_{l}} B_{N_{k},N_{l};i,j} (2.12)

with

B_{N_{k},N_{l};i,j} = \{ (1 − \frac{c}{log N_{l}} ) log τ_{j} < log τ_{i} < log τ_{j},

(2.13) 3N_{l}/2 < log τ_{j} < 2N_{l}, max_{N_{k}<r≤N_{l};r≠i,j} log τ_{r} ≤ N_{l}}.

We obtain similarly to (2.10) that with some positive constants C_{3}, C_{4}, C_{5}

P\{B̃_{N_{k},N_{l}}\} ≤ (N_{l} − N_{k})^{2} \frac{C_{3}}{N_{l}^{2} log N_{l}} ≤ \frac{C_{4}}{l} ≤ C_{5}P\{B_{N_{l}}\},

i.e.

P{B_{N_{k}}B_{N_{l}}} ≤ C_{5}P{B_{N_{k}}}P{B_{N_{l}}},

hence by Borel-Cantelli lemma, P{B_{N} i.o.} > 0, consequently P{B_{N} i.o.} = 1 by 0−1 law.

Now let n = 2ρ_{N}. Then B_{N} implies n = 2ρ_{N} ≤ e^{3N} for large N and since there must be a large excursion between ρ_{N} and 2ρ_{N} by (1.12), also

log R(n) = log R(2ρ_{N}) ≥ log τ_{2,N} ≥ (1 − \frac{c}{log N} ) log τ_{1,N},

where τ_{1,N} ≥ τ_{2,N} are the two largest excursions among τ_{1}, …, τ_{N}. Thus B_{N} implies

log R(n) ≥ (1 − \frac{c}{log N} ) log τ_{1,N} ≥ (1 − \frac{2c}{log N} ) log(2ρ_{N}) ≥ (1 − \frac{3c}{log log n}) log n,

consequently we have this inequality infinitely often with probability 1, proving (1.17).

For the proof of (1.18) we note that R(n) ≤ κ(n) and hence it follows from Theorem C.

It remains to prove (1.19).

Lemma 2.1. For N ≥ 1, let τ_{1,N} ≥ … ≥ τ_{N,N} be the order statistics of {τ_{i}}_{1≤i≤N}. Then for each fixed k ≥ 1,

lim inf_{N→∞} \frac{log_{2} N}{N} log τ_{k,N} = π a.s.

Proof. According to Theorem A2

lim inf_{N→∞} \frac{log_{2} N}{N} log ρ_{N} = π a.s.

So we only have to prove the lower bound.

Fix ε > 0, and consider

p_{N} = P \{log τ_{1} ≥ (1 − ε)\frac{πN}{log_{2} N} \} .

By Theorem B, for 0 < ε_{1} < ε and large N,

\frac{log_{2} N}{(1 − ε_{1})N} ≤ p_{N} ≤ \frac{2 log_{2} N}{N} .

Therefore

P \{log τ_{k,N} < (1 − ε)\frac{πN}{log_{2} N} \}

= ∑_{i=0}^{k−1} \binom{N}{i}p_{N}^{i}(1 − p_{N})^{N−i}

≤ 2 ∑_{i=0}^{k−1}(Np_{N})^{i}(1 − p_{N})^{N}

≤ 2k(2 log_{2} N)^{k}(1 − p_{N})^{N}

≤ 2k(2 log_{2} N)^{k} exp(−(1 − ε_{1})^{−1} log_{2} N).

Taking a geometric subsequence, using Borel-Cantelli lemma and monotonicity concludes the lemma. □

Now let ρ_{N} ≤ n < ρ_{N+1}. Since R(n) is non-decreasing, we have

log R(n) ≥ log R(ρ_{N}) ≥ log τ_{3,N} ≥ (1 − ε)\frac{πN}{log_{2} N} .

By (1.7),

lim_{N→∞} \frac{log ρ_{N}}{N(log N)^{1+ε}} = 0 a.s.

Thus

log R(n) ≥ \frac{log ρ_{N+1}}{(log_{2} ρ_{N+1})^{1+2ε}} ≥ \frac{log n}{(log_{2} n)^{1+2ε}} .

This proves (1.19) completing the proof of Theorem 1.1. □

3. Proof of Theorem 1.2.

Define two increasing sequences of stopping times (σ_{n}) and (θ_{n}) by:

(3.1)  σ_{0} = inf {t > 0; ||W (t)|| = 1} ,
(3.2)  θ_{n} = inf {t > σ_{n−1}; ||W (t)|| = 2} , n ≥ 1,
(3.3)  σ_{n} = inf {t > θ_{n}; ||W (t)|| = 1} , n ≥ 1.

Then {σ_{n}−θ_{n}}_{n=1}^{∞} is a sequence of i.i.d. random variables and so is {σ_{n}−σ_{n−1}}_{n=1}^{∞}.

Lemma 3.1. (3.4) P \{σ_{1} − θ_{1} > x\} = \frac{2 log 2}{log x} + O((log x)^{−2})

and (3.5) P \{σ_{1} − σ_{0} > x\} = \frac{2 log 2}{log x} + O((log x)^{−2})

as x → ∞.

Proof. According to Kent (1978), for any λ > 0

E \{exp (−λ(σ_{1} − θ_{1}))\} = \frac{K_{0}(\sqrt{8λ})}{K_{0}(\sqrt{2λ})} (3.6)

and

E \{exp (−λ(θ_{1} − σ_{0}))\} = \frac{I_{0}(\sqrt{2λ})}{I_{0}(\sqrt{8λ})}, (3.7)

where I_{0} and K_{0} are the modified Bessel functions. We have (cf. Gradshteyn and Ryzhik, p. 961, Formula 8.447)

K_{0}(z) = log(1/z) + log 2 − C + O(z), z → 0^{+},

where C is Euler’s constant and

I_{0}(z) = 1 + O(z^{2}), z → 0^{+}.

Hence

\frac{K_{0}(\sqrt{8λ})}{K_{0}(\sqrt{2λ})} = \frac{log(1/λ) − log 2 − 2C + O(\sqrt{λ})}{log(1/λ) + log 2 − 2C + O(\sqrt{λ})}

(3.8) = 1 − \frac{2 log 2}{log(1/λ)} + O((log(1/λ))^{−2})

as λ → 0^{+}. From this we would obtain the main term in (3.4) by applying a Tauberian theorem (cf. Doetsch (1950), p. 511). Following its proof, we can also obtain the remainder as follows.

Start from the elementary inequalities

\frac{ev^{2} − v}{e − 1} ≤ 1 ≤ (1 + e)v − ev^{2} for 1/e ≤ v ≤ 1,

\frac{ev^{2} − v}{e − 1} ≤ 0 ≤ (1 + e)v − ev^{2} for 0 ≤ v ≤ 1/e.

Putting v = e^{−uλ}, denoting by H(u) the distribution function of σ_{1} −θ_{1}, with x = 1/λ we get

∫_{0}^{x} dH(u) ≤ ∫_{0}^{∞}((1 + e)e^{−λu} − ee^{−2λu})dH(u) = (1 + e)\frac{K_{0}(\sqrt{8λ})}{K_{0}(\sqrt{2λ})} − e\frac{K_{0}(\sqrt{16λ})}{K_{0}(\sqrt{4λ})}

and similarly,

∫_{0}^{x} dH(u) ≥ ∫_{0}^{∞} \frac{ee^{−2λu} − e^{−λu}}{e − 1} dH(u) = \frac{e}{e − 1} \frac{K_{0}(\sqrt{16λ})}{K_{0}(\sqrt{4λ})} − \frac{1}{e − 1} \frac{K_{0}(\sqrt{8λ})}{K_{0}(\sqrt{2λ})}.

Both the upper and the lower bounds are of the form

A\frac{K_{0}(\sqrt{8λ})}{K_{0}(\sqrt{2λ})} + B \frac{K_{0}(\sqrt{16λ})}{K_{0}(\sqrt{4λ})}

with A + B = 1. We obtain from (3.8)

1 − A\frac{K_{0}(\sqrt{8λ})}{K_{0}(\sqrt{2λ})} − B \frac{K_{0}(\sqrt{16λ})}{K_{0}(\sqrt{4λ})} = \frac{2 log 2}{log(1/λ)} + O((log(1/λ))^{−2}).

Since P{σ_{1} − θ_{1} > x} = 1 − ∫_{0}^{x} dH(u), this proves (3.4).

The proof of (3.5) is similar, since independence of σ_{1} − θ_{1} and θ_{1} − σ_{0} gives

E \{exp (−λ(σ_{1} − σ_{0}))\} = \frac{I_{0}(\sqrt{2λ})K_{0}(\sqrt{8λ})}{I_{0}(\sqrt{8λ})K_{0}(\sqrt{2λ})}. □

Now put τ̃_{i} = σ_{i} − σ_{i−1}, η(n) = max{N; σ_{N} − σ_{0} ≤ n}. (Here n can be considered as a continuous variable, taking real numbers.) Then one can define the ordered ”excursions” M̃_{n}^{(1)} ≥ M̃_{n}^{(2)} ≥ … ≥ M̃_{n}^{η(n)+1} in terms of τ̃ exactly in the same way as M_{n} were defined in terms of τ. Accordingly, we define R̃(n) = n−M̃_{n}^{(1)} −M̃_{n}^{(2)}. Following Erdős and Taylor (1960) one can easily see from Lemma 3.1 that all the results in Theorem A1 and Theorem A2 remain true if πξ(n) is replaced by (2 log 2)η(n) and (log ρ_{N})/π is replaced by (log(σ_{N} − σ_{0}))/(2 log 2). For R̃ we have

Proposition 3.1. Theorem 1.1 remains true if R(n) is replaced by R̃(n).

Proof. In fact, (1.16), (1.17) and (1.19) with R replaced by R̃ can be proved exactly the same way as in Section 2. We have only to show (1.18) for R̃.

Fix any constant c > 0, and let

B_{N} = ⋃_{j=N+1}^{2N}{ 3c^{−1} N log N < log τ̃_{j} < 4c^{−1} N log N, max_{1≤i≤2N, i≠j} log τ̃_{i} < N}.

Since (τ̃_{i}) are iid,

P{B_{N}} = N ( P{log τ̃_{1} < N})^{2N−1} P{3c^{−1} N log N < log τ̃_{1} < 4c^{−1} N log N},

which, in view of Lemma 3.1, gives

P\{B_{N}\} ∼ \frac{c_{1}}{log N} .

Put N_{k} = 2^{k} to see that ∑_{k} P{B_{N_{k}}} = ∞. Let k < l, then 2N_{k} < N_{l} + 1. Accordingly, with some positive constants c_{2} and c_{3}

P{B_{N_{k}}B_{N_{l}}} = N_{k} ( P{log τ̃_{1} < N_{k}})^{2N_{k}−1} ×

×P{3c^{−1} N_{k} log N_{k} < log τ̃_{1} < 4c^{−1} N_{k} log N_{k}} ×

×N_{l} ( P{log τ̃_{1} < N_{l}})^{2(N_{l}−N_{k})−1} ×

×P{ 3c^{−1} N_{l} log N_{l} < log τ̃_{1} < 4c^{−1} N_{l} log N_{l}}

≤ \frac{c_{2}}{(log N_{k}) (log N_{l})} ≤ c_{3} P\{B_{N_{k}}\} P\{B_{N_{l}}\}.

It follows from the Borel–Cantelli lemma that P{B_{N} i.o.} > 0. Since the event {B_{N} i.o.} is invariant under finite permutations of (τ̃_{i}), the Hewitt–Savage 0–1 law confirms that its probability equals 1.

Almost surely, there are infinitely many N such that, simultaneously,

σ_{2N} − σ_{0} − max_{1≤i≤2N}(σ_{i} − σ_{i−1}) ≤ (2N − 1)e^{N} ≤ e^{2N},

log(σ_{2N} − σ_{0}) ≥ 3c^{−1} N log N.

Therefore, infinitely often,

R̃(σ_{2N}) ≤ σ_{2N} − σ_{0} − max_{1≤i≤2N}(σ_{i} − σ_{i−1}) ≤ e^{2N} ≤ exp(\frac{c log σ_{2N}}{log log σ_{2N}} ),

which yields (1.18) for R̃. □

For the proof of Theorem 1.2 note the following inequalities valid for large enough n:

V_{n}^{(1)} + V_{n}^{(2)} ≤ M̃_{n}^{(1)} + M̃_{n}^{(2)} ≤ V_{n}^{(1)} + V_{n}^{(2)} + σ_{0} + ∑_{i≤η(n)}(θ_{i} − σ_{i−1}),

from which

R̃(n) ≤ Q(n) ≤ R̃(n) + σ_{0} + ∑_{i≤η(n)}(θ_{i} − σ_{i−1}).

It follows from (3.7) that E{θ_{1} − σ_{0}} < ∞, hence by the law of large numbers,

∑_{i≤η(n)}(θ_{i} − σ_{i−1}) = O(η(n)) = O(log n log_{3} n) a.s.

as n → ∞.

This completes the proof of Theorem 1.2.

Acknowledgement. Cooperation between E. Csáki and Z. Shi was supported by the joint French-Hungarian Intergovernmental Grant ’Balaton’ (grant no. F25/97). The authors would also like to acknowledge the support of Paul Erdős Summer Research Center of Mathematics.

References

[1] CSÁKI, E., RÉVÉSZ, P. and ROSEN, J., Functional laws of the iterated logarithm for local times of recurrent random walks on Z^{2}, Ann. Inst. H. Poincaré, Probab. Statist. 34 (1998), 545–563.

[2] DOETSCH, G., Handbuch der Laplace-Transformation. Band 1, Theorie der Laplace-Transformation, Birkhäuser, Basel, 1950.

[3] DVORETZKY, A. and ERDŐS, P., Some problems on random walk in space, Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability (1950) University of California Press, Berkeley and Los Angeles, 1951, 353–367.

[4] ERDŐS, P. and TAYLOR, S.J., Some problems concerning the structure of random walk paths, Acta Math. Acad. Sci. Hungar. 11 (1960), 137–162.

[5] GRADSHTEYN, I.S. and RYZHIK, I.M., Table of Integrals, Series, and Products, Academic Press, New York, 1980.

[6] KENT, J., Some probabilistic properties of Bessel functions, Ann. Probab. 6 (1978), 760–770.

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