On the local time of the asymmetric Bernoulli walk

Dedicated to Professor Sándor Csörgő on his sixtieth birthday

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^{1} 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: We study some properties of the local time of the asymmetric Bernoulli walk on the line. These properties are very similar to the corresponding ones of the simple symmetric random walks in higher (d ≥ 3) dimension, which we established in the recent years. The goal of this paper is to highlight these similarities.

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

Keywords: transient random walk, local time, occupation time, strong theorems.

1Research supported by the Hungarian National Foundation for Scientific Research, Grant No. K 61052 and K 67961.

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

1. Introduction

The study of the local time (number of visits) of transient random walks started with the landmark papers of Dvoretzky and Erdős [8] and Erdős and Taylor [9], who investigated the properties of simple symmetric random walk in dimension d ≥ 3, in which case the random walk is transient by Pólya theorem. For further results we mention the books by Feller [10], [11], Spitzer [15] and Révész [14]. In the recent years our investigations were concentrated on some of the fine properties of the local and occupation times of these walks. It is well known that the simple asymmetric Bernoulli walk on the line is also transient and as such it behaves similarly to other transient walks. The goal of the present paper to put into evidence that many of the fine properties of the local and occupation times which we studied for the d(≥ 3) dimensional transient symmetric walks are really shared by the asymmetric one dimensional Bernoulli walk.

Here we would like to discuss only the following three major topics.

• limit theorems for multiple visited points

• joint behavior of local and occupation times

• the local time around frequently visited points

These results in higher dimension were presented in our papers [2], [3], [4].

In [5], a recent survey paper on these topics some of our present results were given without proof. In this paper we would like to collect all the results which we are having so far on the asymmetric Bernoulli walk. Clearly to give full proofs for all these results are very tedious but saying only, that proofs are similar to the symmetric d-dimensional walk case is unfair. So we take the middle way, namely we give some of the proofs with an emphasis on the differences between the two situations.

The organization of the paper is as follows. In Section 2 we collect the relevant results on the simple symmetric d-dimensional walk. In Section 3 we present the new results on the local and occupation times of the asymmetric one dimensional Bernoulli walk. In Section 4 we will present some lemmas needed later in the proofs. In Section 5 we prove Theorem 3.2. The proofs of Theorems 3.3 and 3.4 will be given in Section 6, while in Section 7 the proofs of Theorems 3.5 and 3.6 are presented. Finally, Section 8 contains some remarks.

2. Random walk in higher dimension

Let {S_{n}}_{n=1}^{∞} be a symmetric random walk starting at the origin 0 on the d-dimensional integer lattice Z_{d} where d ≥ 3, 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}) = \frac{1}{2d}, i = 1, 2, …, 2d

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

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

where z is any lattice point of Z_{d}. Let ξ(z, ∞) := lim_{n→∞} ξ(z, n) be the total local time at z of the infinite path.

The maximal local time of the walk up to time n is defined as

ξ(n) := max_{z∈Z_{d}} ξ(z, n), n = 1, 2, …  (2.2)

Define also the following quantities:

η(n) := max_{0≤k≤n} ξ(S_{k}, ∞), n = 1, 2, …  (2.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.  (2.4)

It was proved in [8] that

Theorem A (Dvoretzky and Erdős [8]) For d ≥ 3

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

and

γ < γ(n) < γ + O(n^{1−d/2}).  (2.6)

Consequently

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

as n → ∞.

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

For d ≥ 3 (see Erdős and Taylor [9]) ξ(0, ∞) has geometric distribution:

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

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

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

where

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

We remark that (2.9) is also true if ξ(n) is replaced by η(n).

Now we present some of our results for the local and occupation times for simple symmetric random walk in Z_{d}, d ≥ 3. We note however that Theorems E and H and the Proposition below are true for more general symmetric aperiodic random walk in Z_{d}, d ≥ 3.

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

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

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

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

This was extended in [2] to a uniform law of large numbers: Theorem D (Csáki, Földes and Révész [2]) Let d ≥ 3, and define

μ = μ(t) := γ(1 − γ)^{t−1},  (2.12)
t_{n} := [λ log n − λB log log n], B > 2.  (2.13)

Then we have

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

We introduce the following notations. For z ∈ Z_{d} let T_{z} be the first hitting time of z, i.e. T_{z} := min{i ≥ 1 : S_{i} = z} with the convention that T_{z} = ∞ if there is no i with S_{i} = z.

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_{z∈A} T_{z}. Let P_{z}(·) denote the probability of the event in the brackets under the condition that the random walk starts from z ∈ Z_{d}. We denote P(·) = P_{0}(·). Define

γ_{z} := P(T_{z} = ∞).  (2.15)

Let B(r) be the sphere of radius r centered at the origin, i.e.

B(r) := {z ∈ Z_{d} : ∥z∥ = r},

and B := B(1) where ∥ · ∥ is the Euclidean norm.

Introduce further

p := P_{e_{1}}(T_{B} < T).  (2.16)

In words, p is the probability that the random walk, starting from e_{1} (or any other points of B), returns to B before reaching 0 (including the case T_{B} < T = ∞). It is not hard to show that

p = 1 − \frac{1}{2d(1 − γ)}.  (2.17)

For a set A ⊂ Z_{d} the occupation time of A is defined by

Ξ(A, n) := ∑_{z∈A} ξ(z, n).  (2.18)

Consider the translates of A, i.e. A + u = {z + u : z ∈ A} with u ∈ Z_{d} and define the maximum occupation time by

Ξ^{∗}(A, n) := max_{u∈Z_{d}} Ξ(A + u, n).  (2.19)

It was shown in [6]

Theorem E (Csáki, Földes, Révész, Rosen and Shi [6]) For d ≥ 3 and for any fixed finite

set A ⊂ Z_{d}

lim_{n→∞} \frac{Ξ^{∗}(A, n)}{log n} = \frac{−1}{log(1 − 1/Λ_{A})}  a.s.,  (2.20)

where Λ_{A} is the largest eigenvalue of the |A| × |A| matrix with elements

G(z − u), z, u ∈ A,

and

G(z) = ∑_{i=0}^{∞} P(S_{i} = z), z ∈ Z_{d}

is the Green function of the walk.

As a major tool for the above result it was proved that

Proposition A (Csáki, Földes, Révész, Rosen and Shi [6])

P(Ξ(A, ∞) > k) = ∑_{j} h_{j} (\frac{λ_{j} − 1}{λ_{j}})^{k} , k = 0, 1, …,  (2.21)

where λ_{j} are the eigenvalues of the matrix G_{A} and h_{j} are certain coefficients calculated in terms of the eigenvectors.

In particular, it was shown in [6]

lim_{n→∞} \frac{max_{z∈Z_{d}} Ξ(z, n)}{log n} = \frac{−1}{log (p + \frac{1}{2d})} =: κ  a.s.,  (2.22)

where

Ξ(z, n) := Ξ(B + z, n),  (2.23)

i.e. the occupation time of the unit sphere centered at z. Note that in this notation z stands for the center of the unit sphere not for the one element set {z}.

Furthermore if A = {0, z} is a two-point set, then the constant in (2.20) of Theorem E is

c_{A} = \frac{−1}{log(1 − 1/Λ_{A})} = \frac{−1}{log (1 − \frac{γ}{2−γ_{z}} )},

where γ_{z} is the probability that the random walk, starting from zero, never visits z. It can be seen that in this case c_{A} < 2λ, showing that for large n any point with fixed distance from a maximally visited point can not be maximally visited. This suggests to investigate the behavior of local and occupation times around frequently visited points.

Naturally it would be interesting to investigate the joint behavior of the local time and/or occupation time of two sets in general. However this is a very difficult proposition. From the two special cases we discussed in [3] we mention here the following one. Consider the joint behavior of local time of a point and the occupation time of the unit sphere centered at the point.

Define the set B on the plane as

B := {(x, y) : y ≥ x ≥ 0; −y log y + x log(2dx) + (y − x) log((y − x)/p) ≤ 1}, (2.24)

where p was defined in (2.16) and its value in terms of γ is given by (2.17).

Theorem F (Csáki, Földes and Révész [3]) Let d ≥ 4. For each ε > 0 with probability 1 there exists an n_{0} = n_{0}(ε) such that if n ≥ n_{0} then

• (i) (ξ(z, n), Ξ(z, n)) ∈ ((1 + ε) log n)B, ∀z ∈ Z_{d}

• (ii) for any (k, ℓ) ∈ ((1 − ε) log n)B ∩ Z_{2} there exists a random z ∈ Z_{2} for which

(ξ(z, n), Ξ(z, n)) = (k, ℓ + 1).

Theorem G (Csáki, Földes and Révész [3]) Let d ≥ 3. For each ε > 0 with probability 1 there exists an n_{0} = n_{0}(ε) such that if n ≥ n_{0} then

• (i) (ξ(S_{j}+e_{i}, ∞), Ξ(S_{j}+e_{i}, ∞)) ∈ ((1+ε) log n)B, ∀j = 1, 2, …, n, ∀i = 1, 2, …, 2d

• (ii) for any (k, ℓ) ∈ ((1 − ε) log n)B ∩ Z_{2} and for arbitrary i ∈ {1, 2, …, 2d} there exists a random integer j = j(k, ℓ) ≤ n for which

(ξ(S_{j} + e_{i}, ∞), Ξ(S_{j} + e_{i}, ∞)) = (k, ℓ + 1).

It follows from these results that if the local time of a point is close to λ log n, then the local times of each of its neighbors should be asymptotically equal to λ(1 − γ) log n which is strictly less than λ log n. In [4] we investigated whether similar results are true in a wider neighborhood, i.e. whether the local times of points on a certain sphere centered at a heavy point are asymptotically determined. As a positive answer we proved

Theorem H (Csáki, Földes and Révész [4]) Let d ≥ 5 and k_{n} = (1 − δ_{n})λ log n. Let r_{n} > 0 and δ_{n} > 0 be selected such that δ_{n} is non-increasing, r_{n} is non-decreasing, and for any c > 0 r_{[cn]}/r_{n} < C with some C > 0 and for

β_{n} := r_{n}^{2d−4} \frac{log log n}{log n}  (2.25)
lim_{n→∞} β_{n} = 0,  lim_{n→∞} δ_{n}r_{n}^{2d−4} = 0.  (2.26)

Define the random set of points

A_{n} = {z ∈ Z^{d} : ξ(z, n) ≥ k_{n}}.  (2.27)

Then we have

lim_{n→∞} max_{z∈A_{n}} max_{u∈S(r_{n})} |\frac{ξ(z + u, n)}{m_{u}λ log n} − 1| = 0 a.s.,  (2.28)

where

S(r) := \{u ∈ Z_{d} : ∥u∥ ≤ r\} and m_{u} := E(ξ(u, ∞) | T < ∞) = \frac{(1 − γ_{u})^{2}}{1 − γ} .

Theorem I (Csáki, Földes and Révész [4]) Let d ≥ 3 and k_{n} = (1 − δ_{n})λ log n. Let r_{n} > 0 and δ_{n} > 0 be selected such that δ_{n} is non-increasing, r_{n} is non-decreasing, and for any c > 0 r_{[cn]}/r_{n} < C for some C > 0 and for

β_{n} := r_{n}^{2d−4} \frac{log log n}{log n}  (2.29)
lim_{n→∞} β_{n} = 0,  lim_{n→∞} δ_{n}r_{n}^{2d−4} = 0.  (2.30)

Define the random set of indices

B_{n} = {j ≤ n : ξ(S_{j}, ∞) ≥ k_{n}}.  (2.31)

Then we have

lim_{n→∞} max_{j∈B_{n}} max_{u∈S(r_{n})} |\frac{ξ(S_{j} + u, ∞)}{m_{u}λ log n} − 1| = 0 a.s.  (2.32)

3 Simple asymmetric random walk on the line

Consider a simple asymmetric random walk on the line {S_{n}}_{n=0}^{∞} starting at the origin, 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} = 1) = p and P(X_{1} = −1) = q (= 1 − p).  (3.1)

Without restricting generality we will suppose throughout the paper that

p > q and introduce h := \frac{q}{p}.

As it is well-known, this random walk is transient, i.e. with probability one we have lim_{n→∞} S_{n} = ∞. There is a huge literature on such transient random walk. Some basic results are given in Feller [10], [11], Jordan [12], Spitzer [15], etc., some of these will be given in the next section.

Let Z = Z_{1}, i.e. the set of integers on the line. We define the local time by

ξ(z, n) := #{k : 0 < k ≤ n, S_{k} = z}, z ∈ Z, n = 1, 2, …,  (3.2)

ξ(z, ∞) := lim_{n→∞} ξ(z, n), ξ(n) := max_{z∈Z} ξ(z, n), η(n) := max_{0≤j≤n} ξ(S_{j}, ∞),

and the occupation time of a set A ⊂ Z by

Ξ(A, n) := #{k : 0 < k ≤ n, S_{k} ∈ A} = ∑_{z∈A} ξ(z, n), n = 1, 2, …

Concerning limit theorems for the local time, the analogue of Theorem A is simple, it will be given as Fact 2 in Section 4. It seems that no analogue of Theorem B can be found in the literature, though the following result can be proved from (4.11)- (4.13) just as Theorem B above of Erdős and Taylor. It will be also a trivial consequence of Theorem 3.3 and Theorem 3.4.

Theorem 3.1. For the simple asymmetric random walk

lim_{n→∞} \frac{ξ(n)}{log n} = lim_{n→∞} \frac{η(n)}{log n} = \frac{−1}{log(2q)} =: λ_{0} a.s.  (3.3)

We do not know analogues of (2.20) and (2.21), but in certain particular cases the distribution can be expressed in a simple form. In the next section we give a version of the joint distribution of ξ(z, ∞) and ξ(0, ∞) and the distribution of Ξ({0, z}, ∞) (Proposition 4.1). Furthermore, we present the joint distribution of ξ(0, ∞) and Ξ(0, ∞) (Proposition 4.2). Let

Ξ^{∗}(A, n) := max_{a∈Z} Ξ(A + a, n).

From (4.18) in Section 4, similarly to the proof of (2.20) via (2.21) in [6], we will show the following result.

Theorem 3.2. For z > 0 integer

lim_{n→∞} \frac{Ξ^{∗}(\{0, z\}, n)}{log n} = \frac{−1}{log (\frac{2q+h^{z/2}}{1+h^{z/2}} )} a.s.  (3.4)

Concerning Theorem C, define

Q̃(k, n) := #{z ∈ Z : ξ(z, n) = k}.

We have from Pitt [13] that

Theorem K (Pitt [13]) For k = 1, 2, …

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

The analogue of Theorem D, i.e. uniform law of large numbers for Q̃(k, n) remains an open problem.

Next we formulate two theorems which correspond to Theorems F and G for the transient walk on the line.

Let B := {−1, 1}, the one dimensional unit sphere around the origin. Just like in the higher dimensional situation we will denote

Ξ(z, n) := Ξ(B + z, n) = Ξ({z − 1, z + 1}, n) = ξ(z − 1, n) + ξ(z + 1, n),

i.e. the occupation time of the unit sphere centered at z ∈ Z.

Introduce

g(x, y) := x log x − y log y + (y − x) log(y − x) − x log(2p) − y log q  (3.5)

and define the set D by

D := {(x, y) : y ≥ x ≥ 0; g(x, y) ≤ 1}.  (3.6)

Theorem 3.3. For each ε > 0 with probability 1 there exists an n_{0} = n_{0}(ε) such that if n ≥ n_{0} then

(i) (ξ(z, n), Ξ(z, n)) ∈ ((1 + ε) log n)D, ∀z ∈ Z

(ii) for any (k, ℓ) ∈ ((1 − ε) log n)D ∩ Z_{2} there exists a random z ∈ Z for which

(ξ(z, n), Ξ(z, n)) = (k + 1, ℓ + 2).

Theorem 3.4. For each ε > 0 with probability 1 there exists an n_{0} = n_{0}(ε) such that if n ≥ n_{0} then

(i) (ξ(S_{j}, ∞), Ξ(S_{j}, ∞)) ∈ ((1 + ε) log n)D, ∀j = 1, 2, …, n

(ii) for any (k, ℓ) ∈ ((1 − ε) log n)D ∩ Z_{2} there exists a random integer j = j(k, ℓ) ≤ n

for which

(ξ(S_{j}, ∞), Ξ(S_{j}, ∞)) = (k + 1, ℓ + 2).

From Theorem 3.3 the following consequence is easily obtained.

Corollary 3.1 With probability 1 for all possible sequence of integers {z_{n}} the set of all possible limit points of

(\frac{ξ(z_{n}, n)}{log n}, \frac{Ξ(z_{n}, n)}{log n}) , n → ∞

is equal to D.

Finally, we state the following analogues of Theorems H and I: Theorem 3.5. Define the random set of indices

A_{n} := {u ∈ Z : ξ(u, n) ≥ (1 − δ_{n})λ_{0} log n}.  (3.7)

Let α = log(1/h), and select c > 0 such that αc < 1. If

lim_{n→∞} δ_{n}(log n)^{αc} = 0,

then we have

lim_{n→∞} max_{u∈A_{n}} max_{|z|≤c log log n} |\frac{ξ(u + z, n)}{m_{z}λ_{0} log n} − 1| = 0 a.s.,  (3.8)

where

m_{z} := \{ \begin{matrix}\frac{h^{|z|}}{2q} if z ≠ 0, \\ 1  if z = 0. \end{matrix}  (3.9)

Theorem 3.6. Define the random set of indices

B_{n} := {j ≤ n : ξ(S_{j}, ∞) ≥ (1 − δ_{n})λ_{0} log n}.  (3.10)

Let α = log(1/h), and select c > 0 such that αc < 1. If

lim_{n→∞} δ_{n}(log n)^{αc} = 0,

then we have

lim_{n→∞} max_{j∈B_{n}} max_{|z|≤c log log n} |\frac{ξ(S_{j} + z, ∞)}{m_{z}λ_{0} log n} − 1| = 0 a.s.,  (3.11)

where m_{z} is defined in (3.9). Corollary 3.2 Let A ⊂ Z be a fixed set.

(i) If u_{n} ∈ A_{n}, n = 1, 2, …, then

lim_{n→∞} \frac{Ξ(A + u_{n}, n)}{log n} = lim_{n→∞} \frac{∑_{x∈A} ξ(x + u_{n}, n)}{log n} = λ_{0} ∑_{x∈A} m_{x} a.s.

(ii) If j_{n} ∈ B_{n}, n = 1, 2, …, then

lim_{n→∞} \frac{Ξ(A + S_{j_{n}}, ∞)}{log n} = lim_{n→∞} \frac{∑_{x∈A} ξ(x + S_{j_{n}}, ∞)}{log n} = λ_{0} ∑_{x∈A} m_{x} a.s.

4 Preliminary facts and results

Fact 1. For the probability of no return we have (cf. Feller [10])

P(S_{i} ≠ 0, i = 1, 2, …) = 1 − 2q = p − q =: γ_{0}

Let

T_{z} := min{i ≥ 1 : S_{i} = z}, T_{0} =: T, z ∈ Z,

the first hitting time of z. Denote by γ_{0}(n) the probability that in the first n − 1 steps S_{n} does not return to the origin. Then just like in (2.4), we have

1 = γ_{0}(1) ≥ γ_{0}(2) ≥ ... ≥ γ_{0}(n) ≥ ... > γ_{0} > 0.  (4.1)

Fact 2. For T, the first return time to 0 we have (cf. Feller [10])

P(T = 2n) = \binom{2n}{n}\frac{1}{2n − 1}(pq)^{n} ∼ \frac{(4pq)^{n}}{2\sqrt{π}n^{3/2}} , n → ∞,  (4.2)

from which one can easily obtain that

γ_{0}(n) − γ_{0} = P(n ≤ T < ∞) = O (\frac{(4pq)^{n/2}}{n^{3/2}} ) , n → ∞.  (4.3)

Remark: This is the analogue of Theorem A.

It can be seen furthermore that

P(T = 2n, S_{1} = 1) = P(T = 2n, S_{1} = −1) = \frac{1}{2}\binom{2n}{n}\frac{1}{2n − 1}(pq)^{n} = \frac{1}{2}P(T = 2n), (4.4)

from which one easily obtains

P(T < ∞, S_{1} = 1) = P(T < ∞, S_{1} = −1) = \frac{1}{2}P(T < ∞) = q,  (4.5)

and

P(n ≤ T < ∞, S_{1} = 1) = P(n ≤ T < ∞, S_{1} = −1) = \frac{1}{2}P(n ≤ T < ∞).  (4.6)

Now introduce

q(n) := P(T < n, S_{1} = 1) = P(T < ∞, S_{1} = 1) − P(n ≤ T < ∞, S_{1} = 1)

= P(T < n, S_{1} = −1) = P(T < ∞, S_{1} = −1) − P(n ≤ T < ∞, S_{1} = −1).  (4.7)

Then we have

0 < q − q(n) = O (\frac{(4pq)^{n/2}}{n^{3/2}} ) , n → ∞  (4.8)

as well.

Recall the notation h = q/p(< 1).

Fact 3. (see e.g. Feller [10]) For z ∈ Z we have

P(T_{z} < ∞) = \{ \begin{matrix}h^{−z} if z < 0, \\ 2q if z = 0, \\ 1  if z > 0. \end{matrix}  (4.9)

Fact 4. (see e.g. Spitzer [15], page 10) For the Green function G(z) we have for z ∈ Z :

G(z) = ∑_{i=0}^{∞} P(S_{i} = z) = \{ \begin{matrix}\frac{1}{p−q}h^{−z} if z ≤ 0, \\ \frac{1}{p−q}  if z > 0. \end{matrix}  (4.10)

Lemma 4.1. For n ≥ 1, |j| ≤ n we have

P(S_{n} = j) ≤ C_{1} exp(−C_{2}n + C_{3}j),

where the constants C_{i} > 0, i = 1, 2, 3, depend only on p.

Proof. Clearly P(S_{n} = j) differs from 0 only if j and n have the same parity. So we will suppose that in the proof.

P(S_{n} = j) = \binom{n}{\frac{n+j}{2}}p^{\frac{n+j}{2}} q^{\frac{n−j}{2}} ≤ \binom{n}{[n/2]}(pq)^{n/2} (\frac{p}{q})^{j/2}

≤ C_{1}(4pq)^{n/2} (\frac{p}{q})^{j/2} = C_{1} exp(−C_{2}n + C_{3}j),

where

C_{2} = −\frac{1}{2} log(4pq), C_{3} = \frac{1}{2} log \frac{p}{q}.

□ For the distribution of the local time we have Fact 5. (cf. Dwass [7])

P(ξ(0, ∞) = k) = (2q)^{k}(1 − 2q), k = 0, 1, 2, … (4.11)

For z > 0 integer

P(ξ(z, ∞) = k) = (2q)^{k−1}(1 − 2q), k = 1, 2, … (4.12)

and

P(ξ(−z, ∞) = k) = \{ \begin{matrix}1 − h^{z} if k = 0, \\ h^{z}(2q)^{k−1}(1 − 2q) if k = 1, 2, … \end{matrix} (4.13)

For the joint distribution of ξ(z, ∞) and ξ(0, ∞) we have Proposition 4.1. For z > 0, k ≥ 0 integers we have

E (e^{vξ(z,∞)}, ξ(0, ∞) = k) = (1 − 2q)(2q)^{k}φ^{k}(v)ψ(v),  (4.14)
E (e^{vξ(−z,∞)}, ξ(0, ∞) = k) = (1 − 2q)(2q)^{k}φ^{k}(v),  (4.15)

for

v < − log (1 − \frac{1 − 2q}{1 − h^{z}} ) ,

where

φ(v) := \frac{1 − \frac{4q^{2}−h^{z}}{2q(1−2q)} (e^{v} − 1)}{1 − \frac{2q−h^{z}}{(1−2q)} (e^{v} − 1)},  (4.16)
ψ(v) := \frac{e^{v}}{1 − \frac{2q−h^{z}}{(1−2q)} (e^{v} − 1)}.  (4.17)

Moreover,

P(Ξ(\{0, z\}, ∞) = k) = \frac{1 − 2q}{2h^{z/2}} ((\frac{2q + h^{z/2}}{1 + h^{z/2}} )^{k} − (\frac{2q − h^{z/2}}{1 − h^{z/2}} )^{k}) ,  (4.18)

k = 1, 2, …

P(Ξ(\{0, −z\}, ∞) = k) = \frac{1 − 2q}{2} ((\frac{2q + h^{z/2}}{1 + h^{z/2}} )^{k} + (\frac{2q − h^{z/2}}{1 − h^{z/2}} )^{k}) ,  (4.19)

k = 0, 1, 2, … Proof. Let us recall the gambler ruin (cf. Feller [10] or Jordan [12]): for 0 ≤ a < b < c

P_{b}(T_{a} < T_{c}) = 1 − \frac{1 − h^{b−a}}{1 − h^{c−a}} .  (4.20)

Let z > 0 be an integer. Then by (4.20)

s_{z} := P(T_{z} < T) = p P_{1}(T_{z} < T) = p\frac{1 − h}{1 − h^{z}} =: P_{z}.

On the other hand,

s_{−z} = P(T_{−z} < T) = P_{z}(T < T_{z}) = q \frac{h^{z−1} − h^{z}}{1 − h^{z}} = h^{z}P_{z}.

Similarly, a simple calculation shows q_{z} := P(T < T_{z}) = P_{z}(T_{z} < T) = 1 − P_{z} =: Q_{z}, and q_{−z} = P(T < T_{−z}) = q_{z}. Let Z(A) be the number of visits in the set A ⊂ Z in the first excursion away from 0. In

particular, for the one point set {z}

Z({z}) = ξ(z, T).

Note that T = ∞ is possible. Fact 6. (Baron and Rukhin [1]) For z > 0 integer

P(Z(\{z\}) = j, T < ∞) = P(Z(\{−z\}) = j, T < ∞) = \{ \begin{matrix}Q_{z} if j = 0, \\ h^{z}P_{z}^{2}Q_{z}^{j−1} if j = 1, 2, … \end{matrix}

(4.21)

P(Z({z}) = j, T = ∞) = (1 − 2q)P_{z}Q_{z}^{j−1}, j = 1, 2, … (4.22)
P(Z({−z}) = 0, T = ∞) = (1 − 2q).  (4.23)

It can be seen furthermore that

E(ξ(z, T), T < ∞) = E(Z({z}), T < ∞) = E(Z({−z}), T < ∞) = h^{z},

hence

E(ξ(z, T)|T < ∞) = E(Z({z})|T < ∞) = E(Z({−z})|T < ∞) = m_{z},

where m_{z} is defined by (3.9).

Now (4.14) can be calculated from (4.21) and (4.22) by using that

E (e^{vξ(z,∞)}, ξ(0, ∞) = k) = (E(e^{vZ({z})}, T < ∞))^{k} E(e^{vZ({z})}, T = ∞).

It is easy to see that

E(e^{vZ(\{z\})}, T < ∞) = Q_{z} + \frac{h^{z}P_{z}^{2}e^{v}}{1 − Q_{z}e^{v}} = 2qφ(v),

and

E(e^{vZ(\{z\})}, T = ∞) = (1 − 2q)\frac{e^{v}P_{z}}{1 − Q_{z}e^{v}} = (1 − 2q)ψ(v).

To ease the computation we remark that

h^{z}P_{Z}^{2} − Q_{z}^{2} = \frac{h^{z} − 4q^{2}}{1 − h^{z}.}

Similarly we get (4.15) from (4.21) and (4.23).

From (4.14) - (4.15), substituting w = e^{v}, one can find

E(w^{ξ(0,∞)+ξ(z,∞)}) = \frac{(1 − 2q)P_{z}w}{1 − 2Q_{z}w + (Q_{z}^{2} − h^{z}P_{z}^{2})w^{2}} ,  (4.24)

and

E(w^{ξ(0,∞)+ξ(−z,∞)}) = \frac{(1 − 2q)(1 − Q_{z}w)}{1 − 2Q_{z}w + (Q_{z}^{2} − h^{z}P_{z}^{2})w^{2}} ,  (4.25)

consequently (4.18) and (4.19) can be obtained by expanding the right-hand side into powers of w. □

The next result concerns the joint distribution of the local time of the origin and the occupation time of the unit sphere B.

Proposition 4.2. For K = 0, 1, …, L = K + 1, K + 2, … we have

P(Ξ(0, ∞) = L, ξ(0, ∞) = K) = \binom{L − 1}{K}(2p)^{K}q^{L−1}p(1 − 2q) =: p(L, K).  (4.26)
P(Ξ(0, n) = L, ξ(0, n) = K) ≤ p(L, K),  (4.27)
P(Ξ(0, ∞) = L) = (q + 2pq)^{L−1}p(1 − 2q), L = 1, 2, …  (4.28)

Moreover, for the occupation time of the set A_{0} := {−1, 0, 1} we have

P(Ξ(A_{0}, ∞) = ℓ) = p(1 − 2q) (\frac{q}{2})^{ℓ−1} \frac{(1 + β)^{ℓ} − (1 − β)^{ℓ}}{2β} ,  ℓ = 1, 2, …,  (4.29)

where

β = \sqrt{1 + \frac{8p}{q}}.

Proof. The probability that the walk goes to B and returns to 0 immediately, is 2pq. However, before returning, the walk can make one or more outward excursions. If the walk starts outward from B, it returns with probability q, independently whether it starts from 1 or −1. Altogether we need K trips from zero to B and back to 0 and L − K − 1 outward excursions. Every such arrangement, independently of the order of occurrences, has probability (2pq)^{K}q^{L−K−1}. The number of ways how we can order the outward excursions and the inward ones is \binom{L−1}{K}. After the K-th return to zero the walk must go to 1 (some of the outward excursion might happen at this time) and then to infinity which has probability p(1 − 2q), proving our first statement. Now (4.27) follows from (4.26) and (4.8).

With a similar argument one can show that if we start the walk at −1, then for K = 1, 2, …, L = K, K + 1, …

p_{−1}(L, K) := P_{−1}(Ξ(0, ∞) = L, ξ(0, ∞) = K) = \binom{L}{K}(2p)^{K−1}q^{L−1}p^{2}(1 − 2q)  (4.30)

(which does not include the very first visit at −1).

Similarly for K = 1, 2, …, L = K, K + 1, …

p_{1}(L, K) := P_{1}(Ξ(0, ∞) = L, ξ(0, ∞) = K) = \binom{L}{K}(2p)^{K−1}q^{L}p(1 − 2q)  (4.31)

(which does not include the very first visit at 1), and for L = 0, 1, …

p_{1}(L, 0) := P_{1}(Ξ(0, ∞) = L, ξ(0, ∞) = 0) = q^{L}(1 − 2q).  (4.32)

Finally, we get (4.29) from

E(w^{Ξ(A_{0},∞)}) = E(w^{(Ξ(0,∞)+ξ(0,∞))}) = \frac{p(1 − 2q)w}{1 − qw − 2pqw^{2}}

which follows from

E(e^{vZ(B)}, T < ∞) = \frac{2pqe^{v}}{1 − qe^{v}}

and

E(e^{vZ(B)}, T = ∞) = p(1 − 2q)\frac{e^{v}}{1 − qe^{v}} ,

similarly as we got (4.18) in Proposition 4.1. □

We will need some basic observations about the reversed walk. By the reversed path of (S_{0}, S_{1}, …, S_{j}) we mean the path (0, S_{j−1} − S_{j}, S_{j−2} − S_{j}, …, S_{0} − S_{j}) =: (S_{0}^{∗}, S_{1}^{∗}, …, S_{j}^{∗}), e.g. X_{i}^{∗} = S_{j−i} − S_{j−i+1} for 1 ≤ i ≤ j. Then of course X_{i}^{∗}, 1 ≤ i ≤ j are i.i.d. random variables with

P(X_{1}^{∗} = 1) = q and P (X_{1}^{∗} = −1) = p = 1 − q, p > q.  (4.33)

If needed this can be extended to an infinite path (S_{0}^{∗}, S_{1}^{∗}, …, S_{n}^{∗}, …), i.e. {S_{n}^{∗}}_{n=0}^{∞} is a walk starting at the origin S_{0}^{∗} = 0, with S_{n}^{∗} = ∑_{k=1}^{n} X_{k}^{∗}, n = 1, 2, …, where X_{k}^{∗}, are defined above for k ≤ j and for k > j they are an arbitrary sequence of i.i.d. random variables (also independent from the previous ones) with the above distribution. Then we clearly have for all z

Fact 7.

P(ξ^{∗}(−z, ∞) = k) = P(ξ(z, ∞) = k).  (4.34)

Consequently, under the conditions of Proposition 4.1 we have for z = 1, 2, …, k = 0, 1, 2, … and v < − log Q_{z}

E (e^{vξ^{∗}(−z,∞)}, ξ^{∗}(0, ∞) = k) = (2q)^{k}(1 − 2q)φ^{k}(v)ψ(v),  (4.35)
E (e^{vξ^{∗}(z,∞)}, ξ^{∗}(0, ∞) = k) = (2q)^{k}(1 − 2q)φ^{k}(v).  (4.36)

5 Proof of Theorem 3.2

Lemma 5.1. Let

θ = − log \frac{2q + h^{z/2}}{1 + h^{z/2}} .

There exist u_{0} > 0, c_{1} > 0, c_{2} > 0 such that for all u ≥ u_{0}, n ≥ u^{2} we have

c_{1}e^{−θu} ≤ P(Ξ({0, z}, n) ≥ u) ≤ P(Ξ({0, z}, ∞) ≥ u) ≤ c_{2}e^{−θu}.  (5.1)

Proof. The second inequality in (5.1) is obvious, and since from (4.18) we can see

P(Ξ({0, z}, ∞) ≥ u) ∼ ce^{−θu}, u → ∞,

with some constant c, we have also the third inequality in (5.1). To show the first inequality in (5.1), we note that

P(Ξ({0, z}, ∞) ≥ u) ≤ P(Ξ({0, z}, n) ≥ u) + P(∪_{k=n+1}^{∞}{S_{k} = 0}) + P(∪_{k=n+1}^{∞}{S_{k} = z}).

By Lemma 4.1 for j = 0, z

P(∪_{k=n+1}^{∞}{S_{k} = j}) ≤ C_{1}e^{−Cn},

with some C > 0, C_{1} > 0. Thus, by (4.18) we have

P(Ξ({0, z}, n) ≥ u) ≥ P(Ξ({0, z}, ∞) ≥ u) − 2C_{1}e^{−Cn} ≥ ce^{−θu} − 2C_{1}e^{−Cu^{2}} ≥ C_{2}e^{−θu}

for large enough u with some C_{2} > 0. □

Now we turn to the proof of Theorem 3.2. First we prove an upper bound in (3.4). Since

∑_{a=−∞}^{z} ξ(a, ∞) < ∞ and  ∑_{a=n+1}^{∞} ξ(a, n) = 0

almost surely, it suffices to show the upper bound with Ξ^{∗}({0, z}, n) replaced by

Ξ̃^{∗}({0, z}, n) := max_{0≤a≤n} Ξ({a, a + z}, n).

Since P(Ξ({a, a + z}, n) > u) ≤ P(Ξ({0, z}, n) > u − 1) for a = 1, 2, …, we have by Lemma 5.1 for large enough n

P (Ξ̃^{∗}(\{0, z\}, n) ≥ \frac{1 + ε}{θ} log n) ≤ (n + 1)P (Ξ(\{0, z\}, n) ≥ \frac{1 + ε}{θ} log n − 1)

≤ (n + 1)P (Ξ(\{0, z\}, ∞) ≥ \frac{1 + ε}{θ} log n − 1) ≤ \frac{c}{n^{ε}} .

Applying this for the subsequence n_{k} = k^{2/ε}, using Borel-Cantelli lemma and the monotonicity of Ξ^{∗}({0, z}), ε being arbitrary, we obtain

lim sup_{n→∞} \frac{Ξ̃^{∗}(\{0, z\}, n)}{log n} ≤ \frac{−1}{log (\frac{2q+h^{z/2}}{1+h^{z/2}} )} a.s.

implying the upper bound in (3.4).

Now we show the lower bound in (3.4). Let k(n) = [log n]^{3}, N_{n} = [n/k(n)], t_{i,n} = ik(n), i = 0, 1, …, N_{n} − 1. We have

Ξ^{∗}({0, z}, n) ≥ max_{0≤i≤N_{n}−1} Z_{i},

where

Z_{i} := Ξ({S_{t_{i,n}}, S_{t_{i,n}} + z}, t_{i+1,n}) − Ξ({S_{t_{i,n}}, S_{t_{i,n}} + z}, t_{i,n}).

Z_{i}, i = 0, 1, … N_{n} − 1 are i.i.d. random variables, distributed as Ξ({0, z}, k(n)), so we get by Lemma 5.1

P (Ξ^{∗}(\{0, z\}, n) ≤ \frac{1 − ε}{θ} log n) ≤ P ( max_{0≤i≤N_{n}−1} Z_{i} ≤ \frac{1 − ε}{θ} log n)

≤ (1 − P (Ξ(\{0, z\}, k(n)) ≥ \frac{1 − ε}{θ} log n))^{N_{n}} ≤ (1 − c_{1}e^{−(1−ε) log n})^{N_{n}} ≤ e^{−c_{1}n^{ε}/k(n)}.

The lower bound in (3.4) follows by Borel-Cantelli lemma. □

6 Proof of Theorems 3.3 and 3.4

From (4.26) (4.30), (4.31) and Stirling formula we conclude the following limit relations.

Lemma 6.1. For y ≥ x ≥ 0 we have

lim_{n→∞} \frac{log p([y log n] + 1, [x log n])}{log n} = lim_{n→∞} \frac{log p_{1}([y log n], [x log n])}{log n}

= lim_{n→∞} \frac{log p_{−1}([y log n] + 1, [x log n] + 1)}{log n} = −g(x, y),  (6.1)

where g(x, y) is defined by (3.5).

Consequently, the probability P(Ξ(0, ∞) = [y log n] + 1, ξ(0, ∞) = [x log n]) is of order 1/n, if (x, y) satisfies the basic equation

g(x, y) = 1,  y ≥ x ≥ 0.  (6.2)

The following lemma describes the main properties of the boundary of the set D.

Lemma 6.2.

(i) For the maximum value of x, y, satisfying (6.2), we have

x_{max} = \frac{−1}{log(2q)} = λ_{0},  (6.3)
y_{max} = \frac{−1}{log(q(1 + 2p))} =: κ_{0}.  (6.4)

(ii) If x = x_{max} = \frac{−1}{log(2q)}, then y = \frac{−1}{p log(2q)}. If y = y_{max} = κ_{0}, then x = (2κ_{0}p)/(2p + 1). If x = 0, then y = −1/ log q.

(iii) For given x, the equation (6.2) has one solution in y for 0 ≤ x < −1/ log(2pq) and for x = λ_{0}, and two solutions in y for −1/ log(2pq) ≤ x < λ_{0}.

Proof. (i) First consider x as a function of y satisfying (6.2). We seek the maximum, where the derivative x′(y) = 0. Differentiating (6.2) and putting x′ = 0, a simple calculation leads to

− log y + log(y − x) − log q = 0,

i.e.

y = x/p.

It can be seen that this is the value of y when x takes its maximum. Substituting this into (6.2), we get

x_{max} = \frac{−1}{log(2q)},

verifying (6.3).

Next consider y as a function of x and maximize y subject to (6.2). Again, differentiating (6.2) with respect to x and putting y′ = 0, we get

− log(y − x) + log x − log(2p) = 0

from which x = (2py)/(1 + 2p). Substituting in (6.2) we get y_{max} = κ_{0}.

This completes the proof of Lemma 6.2(i) and the first two statements in Lemma 6.2(ii). A simple calculation shows that if x = 0 then y = −1/ log q.

Now we turn to the proof of Lemma 6.2(iii). For given 0 ≤ x ≤ λ_{0} consider g(x, y) as a function of y. We have

\frac{∂g}{∂y} = log \frac{y − x}{qy}

and this is equal to zero if y = x/p. It is easy to see that g takes a minimum here and is decreasing if y < x/p and increasing if y > x/p. Moreover,

\frac{∂^{2}g}{∂y^{2}} = \frac{1}{y − x} − \frac{1}{y} > 0,

hence g is convex from below. We have for 0 < x < λ_{0}, that this minimum is

g (x, \frac{x}{p}) = x log(1/(2q)) = \frac{x}{λ_{0}} < 1,

and

g(x, x) = −x log(2pq) \{ \begin{matrix}< 1 if x < −1/ log(2pq), \\ = 1 if x = −1/ log(2pq), \\ > 1 if x > −1/ log(2pq). \end{matrix}

This shows that equation (6.2) has one solution if 0 ≤ x < −1/ log(2pq) and two solutions if −1/ log(2pq) ≤ x < λ_{0}.

For x = λ_{0}, it can be seen that y = λ_{0}/p is the only solution of g(x, y) = 1.

The proof of Lemma 6.2 is complete. □

Proof of Theorem 3.4(i). Obviously, for z = 1, 2, … we have for K = 1, 2, …, L = K + 1, K + 2, …

P(Ξ(z, ∞) = L, ξ(z, ∞) = K) = P_{−1}(Ξ(0, ∞) = L − 1, ξ(0, ∞) = K)

and for K = 0, 1, …, L = K + 1, K + 2, …

P(Ξ(−z, ∞) = L, ξ(−z, ∞) = K) ≤ P_{1}(Ξ(0, ∞) = L − 1, ξ(0, ∞) = K).

Hence for (k, ℓ) ∉ ((1 + ε) log n)D and z ∈ Z, as g(cx, cy) = cg(x, y) for any c > 0, we have by (4.26)–(4.31) and Lemma 6.1

P(ξ(z, ∞) = k, Ξ(z, ∞) = ℓ) ≤ \frac{c}{n^{1+ε}} .  (6.5)

Consequently, by Fact 5, (4.28), (6.5) we have

P(ξ(S_{j}, ∞), Ξ(S_{j}, ∞)) ∉ ((1 + ε) log n)D)

≤ ∑_{{(k,ℓ)∉((1+ε) log n)D \atop k≤(1+ε)λ_{0} log n} ℓ≤(1+ε)κ_{0} log n} P(ξ(S_{j}, ∞) = k, Ξ(S_{j}, ∞) = ℓ)

+ ∑_{k>(1+ε)λ_{0} log n} P(ξ(S_{j}, ∞) = k) + ∑_{ℓ>(1+ε)κ_{0} log n} P(Ξ(S_{j}, ∞) = ℓ)

≤ \frac{c log^{2} n}{n^{1+ε}} + ∑_{k>(1+ε)λ_{0} log n} c(2q)^{k} + ∑_{ℓ>(1+ε)κ_{0} log n} c(q + 2pq)^{ℓ} ≤ \frac{c}{n^{1+ε/2}} .

where in the above computation c is an unimportant constant. We continue denoting such constants by the same letter c, the value of which might change from line to line. Selecting n_{r} = r^{4/ε}, we have

P(∪_{j≤n_{r+1}}\{(ξ(S_{j}, ∞), Ξ(S_{j}, ∞)) ∉ ((1 + ε) log n_{r})D\}) ≤ \frac{c}{n_{r}^{ε/2}} = \frac{c}{r^{2}} .  (6.6)

This combined with the Borel-Cantelli lemma shows that with probability 1 for all large r and j ≤ n_{r+1}

(ξ(S_{j}, ∞), Ξ(S_{j}, ∞)) ∈ ((1 + ε) log n_{r})D.

It follows that with probability 1 there exists an n_{0} such that if n ≥ n_{0} then

(ξ(S_{j}, ∞), Ξ(S_{j}, ∞)) ∈ ((1 + ε) log n)D

for all j ≤ n.

This proves (i) of Theorem 3.4. □

Proof of Theorem 3.3(i). The proof is similar to that of Theorem 1.1(i) in [3]. Define the following events for j ≤ n:

B(j, n) := {(ξ(S_{j}, n), Ξ(S_{j}, n)) ∉ ((1 + ε) log n)D},  (6.7)
B^{∗}(j, n) := {(ξ(S_{j}, j), Ξ(S_{j}, j)) ∉ ((1 + ε) log n)D},  (6.8)
C(j, n) := {S_{m} ≠ S_{j}, m = j + 1, …, n },  (6.9)
D(j, n) := {Ξ(S_{j}, ∞) > Ξ(S_{j}, n)}.  (6.10)

Considering the reverse random walk starting from S_{j}, i.e. S′_{r} = S_{j−r} −S_{j}, r = 0, 1, …, j, we remark ξ(S_{j}, j) = ξ′(0, j), if S_{j} = 0, ξ(S_{j}, j) = ξ′(0, j) + 1, if S_{j} ≠ 0, Ξ(S_{j}, j) = Ξ′(0, j), where Ξ′ is the occupation time of the unit sphere of the random walk S′.

From this we can follow the proof of Theorem 1.1(i) in [3], using (4.27) and (6.1) instead of (2.18) and (3.1) in [3] and applying Theorem 3.4(i) instead of Theorem 1.2(i) in [3]. □

Proof of Theorems 3.3(ii) and 3.4(ii). We will say that S_{i} is new if

max_{0≤m<i} S_{m} < S_{i}.  (6.11)

Lemma 6.3. Let ν_{n} denote the number of new points up to time n. Then

lim_{n→∞} \frac{ν_{n}}{n} = 1 − 2q a.s.

Proof: Let

Z_{i} := \{ \begin{matrix}1 & if S_{i} is new \\ 0 & otherwise. \end{matrix}

Then ν_{n} = ∑_{i=1}^{n} Z_{i}.

E(ν_{n}^{2}) = E (∑_{j=1}^{n} ∑_{i=1}^{n} Z_{j}Z_{i}) = E (∑_{j=1}^{n} Z_{j}) + 2E (∑_{j=1}^{n} ∑_{i=1}^{j−1} Z_{j}Z_{i})

≤ n + 2 ∑_{j=1}^{n} ∑_{i=1}^{j−1} P(Z_{i} = 1)P(Z_{j−i} = 1).

Considering the reverse random walk from S_{i} to S_{0} = 0, we see that the event {Z_{i} = 1} is equivalent to the event that this reversed random walk starting from 0 does not return to 0 in time i. We remark that for the reversed walk the probability of stepping to the right is q and stepping to left is p. Using (4.3) and observing that it remains true for the reversed random walk as well, we get

P(Z_{i} = 1) = γ_{0} + O((4pq)^{i/2}) = 1 − 2q + O((4pq)^{i/2}).

Hence

E(ν_{n}^{2}) ≤ n + 2 ∑_{j=1}^{n} ∑_{i=1}^{j−1} (1 − 2q + O(4pq)^{i/2}) ((1 − 2q) + O(4pq)^{(j−i)/2})

= n(n − 1)(1 − 2q)^{2} + O(n).

As E(ν_{n}) = n(1 − 2q) + O(1), we have

V ar(ν_{n}) = O(n).

By Chebyshev’s inequality we get that

P |ν_{n} − n(1 − 2q)| > εn) ≤ O (\frac{1}{n}) .

Considering the subsequence n_{k} = k^{2} and using the Borel-Cantelli lemma and monotonicity of ν_{n}, we obtain the lemma. □

To show Theorem 3.4(ii), let {a_{n}} and {b_{n}} (a_{n} log n ≪ b_{n} ≪ n ) be two sequences to be chosen later. Define

θ_{1} = min{i > b_{n} : S_{i} is new},
θ_{m} = min{i > θ_{m−1} + b_{n} : S_{i} is new}, m = 2, 3, …

and let ν′_{n} be the number of θ_{m} points up to time n − b_{n}. Obviously ν′_{n}(b_{n} + 1) ≥ ν_{n}, hence ν′_{n} ≥ ν_{n}/(b_{n} +1) and it follows from Lemma 6.3 that for c < 1−2q, we have with probability 1 that ν′_{n} > u_{n} := cn/(b_{n} + 1) except for finitely many n.

Recall that B = {−1, 1} denotes the unit sphere around 0. Let

ρ_{0}^{i} = 0, ρ_{h}^{i} = min{j > ρ_{h−1}^{i} : S_{θ_{i}+j} ∈ S_{θ_{i}} + B}, h = 1, 2, …,

i.e. ρ_{h}^{i}, h = 1, 2, … are the times when the random walk visits the unit sphere around S_{θ_{i}}. For a fixed pair of integers (k, ℓ) define the following events:

A_{i} := A_{i}(k, ℓ) = {ξ(S_{θ_{i}} + 1, θ_{i} + ρ_{ℓ+1}^{i}) = k + 1, Ξ(S_{θ_{i}} + 1, θ_{i} + ρ_{ℓ+1}^{i}) = ℓ + 2,
ρ_{h}^{i} − ρ_{h−1}^{i} < a_{n}, h = 1, …, ℓ + 1, S_{j} ∉ S_{θ_{i}} + B, j = θ_{i} + ρ_{ℓ+1}^{i} + 1, …, θ_{i} + b_{n}},
B_{i} := B_{i}(k, ℓ) = {S_{j} ∉ S_{θ_{i}} + B, j > θ_{i} + b_{n}},
C_{n} := C_{n}(k, ℓ) = A_{1}B_{1} + \overline{A_{1}}A_{2}B_{2} + \overline{A_{1}} \overline{A_{2}}A_{3}B_{3} + … + \overline{A_{1}} … \overline{A_{u_{n}−1}}A_{u_{n}}B_{u_{n}},

where \overline{A} denotes the complement of A.

Then we have P(A_{i}) = P(A_{1}) and P(A_{i}B_{i}) = P(A_{1}B_{1}), i = 2, 3, … and

P(C_{n}) = P(A_{1}B_{1}) ∑_{j=0}^{u_{n}−1}(1 − P(A_{1}))^{j} = \frac{P(A_{1}B_{1})}{P(A_{1})}(1 − (1 − P(A_{1}))^{u_{n}}),

P(\overline{C_{n}}) ≤ 1 − \frac{P(A_{1}B_{1})}{P(A_{1})} + e^{−u_{n}P(A_{1})}.

A_{1}B_{1} is the event that starting from the new point S_{θ_{1}}, the random walk visits S_{θ_{1}} +1 exactly k + 1 times, while it visits the unit sphere around this point exactly ℓ + 2 times (including the initial visit at S_{θ_{1}}) and all the time intervals between consecutive visits are less than a_{n}. Since the return to the sphere via its center takes only 2 steps, we have to control only the returns from outside. Similarly to (4.30), one can see

P(A_{1}B_{1}) = \binom{ℓ + 1}{k + 1}(q(a_{n}))^{ℓ−k}(2pq)^{k}p^{2} (1 − 2q) ,

= \binom{ℓ + 1}{k + 1}(q + O((4pq)^{a_{n}}))^{ℓ−k}(2pq)^{k}p^{2} (1 − 2q)

and

P(A_{1}) = \binom{ℓ + 1}{k + 1}(2pq)^{k}(q + O((4pq)^{a_{n}}))^{ℓ−k}p^{2} (1 − 2q + O((4pq)^{b_{n}−ℓa_{n}})) ,

where q(n) is given in (4.7).

Using a_{n} log n ≪ b_{n} ≪ n

\frac{P(A_{1}B_{1})}{P(A_{1})} = 1 + O ((4pq)^{c_{1}b_{n}/2}) ,

for some c_{1} > 0 depending only on p, hence

P(\overline{C_{n}}) ≤ e^{−c_{1}b_{n}} + e^{−cnP(A_{1})/b_{n}}.

For fixed ε > 0 introduce the notation G_{n} = ((1 − ε) log n)D ∩ Z_{2}. Choosing b_{n} = n^{δ/2}, a_{n} = n^{δ/4}, we can prove using Stirling formula that for (k, ℓ) ∈ G_{n}

P(A_{1}) ≥ \frac{1}{n^{1−δ}}

for some δ > 0. Since the cardinality of G_{n} is O(log^{2} n), we can verify that

∑_{n} ∑_{(k,ℓ)∈G_{n}} P(\overline{C}_{n}) < ∞.

By Borel-Cantelli lemma, with probability 1, ∩_{(k,ℓ)∈G_{n}}C_{n}(k, ℓ) occurs for all but finitely many n. This completes the proof of the statements (ii) of both Theorems 3.3 and 3.4. □

7 Proof of Theorems 3.5 and 3.6

We start with the proof of Theorem 3.6 which is similar to the proof of Theorem I. So we do not give all the details. Recall the notations of the theorem, Proposition 4.1 and Fact 6.

For m_{z}, given in (3.9), we have

m_{z} = E(ξ(z, T)| T < ∞).  (7.1)

Lemma 7.1. For log(1 − 2q(1 − 2q)) < v < log(1 + 2q(1 − 2q)) we have

φ(v) = exp(m_{z}(v + O(v^{2})),  v → 0,  (7.2)

where O is uniform in z, and

ψ(v) < \frac{1 + |e^{v} − 1|}{1 − \frac{|e^{v}−1|}{1−2q}}.  (7.3)

Proof: The proof of this lemma is based on Proposition 4.1 and goes along the same lines as Lemma 2.3 in [4]. □

Let k_{n} := (1 − δ_{n})λ_{0} log n ∼ λ_{0} log n, r_{n} := c log log n, and I(r) := [−r, r]. Furthermore, let n_{ℓ} = [e^{ℓ}], ξ(z) = ξ(z, ∞) and define the events

A_{j} = \{ξ(S_{j}) ≥ k_{n_{ℓ}}, max_{x∈I(r_{n_{ℓ+1}})} (\frac{ξ(S_{j} + x)}{m_{x}k_{n_{ℓ}}} − 1) ≥ ε\} .

Then

P ( ⋃_{j=0}^{n_{ℓ+1}} A_{j}) ≤ ∑_{j=0}^{n_{ℓ+1}} P(A_{j}) ≤ ∑_{j=0}^{n_{ℓ+1}} ∑_{x∈I(r_{n_{ℓ+1}})} P(A_{j}^{(x)}),

where

A_{j}^{(x)} = {ξ(S_{j}) ≥ k_{n_{ℓ}}, ξ(S_{j} + x) ≥ (1 + ε)m_{x}k_{n_{ℓ}}} .

Consider the random walk obtained by reversing the original walk at S_{j}, i.e. let S′_{i} := S_{j−i} − S_{j}, i = 0, 1, …, j and extend it to infinite time, and also the forward random walk S′′_{i} := S_{j+i} − S_{j}, i = 0, 1, 2, … Then {S′_{0}, S′_{1}, …} and {S′′_{0}, S′′_{1}, …} are independent random walks and so are their respective local times ξ′ and ξ′′. Moreover,

ξ(S_{j}) = ξ′′(0) + ξ(S_{j}, j) ≤ ξ′′(0) + ξ′(0) + 1,
ξ(S_{j} + x) = ξ′′(x) + ξ(S_{j} + x, j) ≤ ξ′′(x) + ξ′(x).

Here ξ′ and ξ′′ are independent and ξ′ has the same distribution as ξ^{∗} (see Fact 7) and ξ′′ has the same distribution as ξ.

Hence

P(A_{j}^{(x)}) ≤ P(ξ′′(0) + ξ′(0) ≥ k_{n_{ℓ}} − 1, ξ′′(x) + ξ′(x) ≥ (1 + ε)m_{x}k_{n_{ℓ}})
= ∑ P(ξ′′(0) = k_{1}, ξ′(0) = k_{2}, ξ′′(x) + ξ′(x) ≥ (1 + ε)m_{x}k_{n_{ℓ}}),

where the summation goes for {(k_{1}, k_{2}) : k_{1} + k_{2} ≥ k_{n_{ℓ}} − 1}. Using exponential Markov inequality, Proposition 4.1, Fact 7, the independence of ξ′′ and ξ′ and elementary calculus, we get

P(A_{j}^{(x)}) ≤ ∑ E (e^{v(ξ′′(x)+ξ′(x))}, ξ′′(0) = k_{1}, ξ′(0) = k_{2}) e^{−v(1+ε)m_{x}k_{n_{ℓ}}}
= ∑(φ(v))^{k_{1}+k_{2}}(1 − 2q)^{2}(2q)^{k_{1}+k_{2}}ψ(v)e^{−v(1+ε)m_{x}k_{n_{ℓ}}}
= (1 − 2q)^{2}ψ(v)e^{−v(1+ε)m_{x}k_{n_{ℓ}}} ∑(2qφ(v))^{k_{1}+k_{2}}
= (1 − 2q)^{2}ψ(v)e^{−v(1+ε)m_{x}k_{n_{ℓ}}}(2qφ(v))^{k_{n_{ℓ}}}
× (\frac{k_{n_{ℓ}}}{2qφ(v)(1 − 2qφ(v))} + \frac{1}{(1 − 2qφ(v))^{2}} ) .  (7.4)

Observe that even though the moment generating functions in Proposition 4.1 and Fact 7 are slightly different for positive and negative values of x, in (7.4) we get the same expression while working with ξ′ + ξ′′.

By (7.2), we obtain for all j ≥ 0

P(A_{j}^{(x)}) ≤ (1 − 2q)^{2}ψ(v) (\frac{k_{n_{ℓ}}}{2qφ(v)(1 − 2qφ(v))} + \frac{1}{(1 − 2qφ(v))^{2}} )
× e^{−m_{x}vk_{n_{ℓ}}(ε+O(v))}(2q)^{k_{n_{ℓ}}}.

Choose v_{0} > 0 small enough such that

ε + O(v_{0}) > 0, e^{v_{0}} < 1 + 2q(1 − 2q), \frac{1}{2} < φ(v_{0}) < \frac{1}{2q} .

Using x ∈ I(r_{n_{ℓ+1}}), we get

m_{x}k_{n_{ℓ}} = \frac{h^{|x|}}{2q} (1 − δ_{n_{ℓ}})λ_{0} log n_{ℓ} ≥ \frac{h^{r_{n_{ℓ+1}}}}{2q} (1 − δ_{n_{ℓ}})λ_{0} log n_{ℓ}.

In the sequel C_{1}, C_{2}, … denote positive constants whose values are unimportant in our proofs. By the above assumptions

P(A_{j}^{(x)}) ≤ C_{2}k_{n_{ℓ}}e^{−m_{x}v_{0}k_{n_{ℓ}}(ε+O(v_{0}))}(2q)^{k_{n_{ℓ}}}
≤ C_{2}k_{n_{ℓ}} exp (−(1 − δ_{n_{ℓ}}) log n_{ℓ} (C_{3}h^{r_{n_{ℓ+1}}} + 1)) .

Hence

∑_{j=0}^{n_{ℓ+1}} ∑_{x∈I(r_{n_{ℓ+1}})} P(A_{j}^{(x)}) ≤ C_{4}n_{ℓ+1}r_{n_{ℓ+1}}k_{n_{ℓ}} exp (−(1 − δ_{n_{ℓ}}) log n_{ℓ} (C_{3}h^{r_{n_{ℓ+1}}} + 1))
≤ C_{5} \frac{n_{ℓ+1}}{n_{ℓ}} k_{n_{ℓ}}r_{n_{ℓ+1}} exp (−C_{6}h^{r_{n_{ℓ+1}}} log n_{ℓ} + δ_{n_{ℓ}} log n_{ℓ})
= C_{5} \frac{n_{ℓ+1}}{n_{ℓ}} k_{n_{ℓ}}r_{n_{ℓ+1}} exp (−h^{r_{n_{ℓ}}} log n_{ℓ} (C_{6}h^{r_{n_{ℓ+1}}−r_{n_{ℓ}}} − \frac{δ_{n_{ℓ}}}{h^{r_{n_{ℓ}}}} ))
≤ C_{5} \frac{n_{ℓ+1}}{n_{ℓ}} k_{n_{ℓ}}r_{n_{ℓ+1}} exp (−C_{7}h^{r_{n_{ℓ}}} log n_{ℓ})
≤ C_{8}(log n_{ℓ}) log log n_{ℓ} exp(−C_{7}(log n_{ℓ})^{1−αc}),

where in the last two lines we used the conditions of the Theorem. Consequently,

P( ⋃_{j=0}^{n_{ℓ+1}} A_{j}) ≤ ∑_{j=0}^{n_{ℓ+1}} ∑_{x∈I(r_{n_{ℓ+1}})} P(A_{j}^{(x)}) ≤ C_{8}ℓ log ℓ exp(−C_{7}ℓ^{1−αc})

for large enough ℓ, which is summable in ℓ when αc < 1. By Borel-Cantelli lemma for large ℓ if ξ(S_{j}) ≥ k_{n_{ℓ}}, then ξ(S_{j} + x) ≤ (1 + ε)m_{x}k_{n_{ℓ}} for all x ∈ I(r_{n_{ℓ+1}}).

Let now n_{ℓ} ≤ n < n_{ℓ+1} and x ∈ I(r_{n_{ℓ+1}}). ξ(S_{j}) ≥ k_{n}, j ≤ n implies ξ(S_{j}) ≥ k_{n_{ℓ}}, i.e.

ξ(S_{j} + x) ≤ (1 + ε)m_{x}k_{n_{ℓ}} ≤ (1 + ε)m_{x}k_{n}.  (7.5)

The lower bound is similar, with slight modifications. However we do not present it. The interested reader should look at the corresponding proof of Theorem 1.2 in [4]. □

The proof of Theorem 3.5 again goes similarly to the proof of Theorem H. As the main ingredient is the following lemma, which is somewhat different from the d-dimensional situation, we give a complete proof.

Lemma 7.2. Let 0 < α < 1, j ≤ n − n^{α}, |x| ≤ c log n with any c > 0. Then with probability 1 there exists an n_{0}(ω) such that for n ≥ n_{0} we have

ξ(S_{j} + x, n) = ξ(S_{j} + x, ∞).

Proof. Let

A_{n} = ⋃_{j≤n−n^{α}}  ⋃_{ℓ≥n} ⋃_{|x|≤c log n}{S_{ℓ} − S_{j} = x}.

By our Lemma 4.1

P(S_{ℓ} − S_{j} = x) = P(S_{ℓ−j} = x) ≤ C_{1} exp(−C_{2}(ℓ − j) + C_{3}x).  (7.6)

Consequently,

P(A_{n}) ≤ C_{1} ∑_{j≤n−n^{α}} ∑_{ℓ≥n} ∑_{|x|≤c log n} exp(−C_{2}ℓ + C_{2}j + C_{3}x)

≤ C exp(−C_{2}n + C_{2}(n − n^{α}) + C_{3}c log n) = C_{4}n^{C_{5}} exp(−C_{2}n^{α}).

Since this is summable, we have the lemma. □

To prove Theorem 3.5, observe that it suffices to consider points visited before time n − n^{α}, (0 < α < 1), since in the time interval (n − n^{α}, n) the maximal local time is less than α(1 + ε)λ_{0} log n, hence this point cannot be in A_{n}. Consequently, Theorem 3.5 follows from Theorem 3.6 and Lemma 7.2. □

8 Concluding remarks

First observe that the following points are on the curve g(x, y) = 1.

(0, \frac{1}{log(1/q)}) , (−\frac{1}{log(2pq)}, −\frac{1}{log(2pq)}) , (\frac{2κ_{0}p}{2p + 1}, κ_{0}) , (λ_{0}, \frac{λ_{0}}{p} ) .  (8.1)

Consequently, there are points x_{n} such that

ξ(x_{n}, n) = 1 and Ξ(x_{n}, n) ∼ \frac{log n}{log(1/q)}

which in fact means that

Ξ(x_{n}, n) = ξ(x_{n} + 1, n) ∼ \frac{log n}{log(1/q)}.

On the other hand, if for a point x_{n},

Ξ(x_{n}, n) > (1 + ϵ)\frac{log n}{log(1/q)},

then we have ξ(x_{n}, n) > c log n with some c > 0.

If ξ(x_{n}, n) ∼ λ_{0} log n then for the unit sphere centered at x_{n}, that is to say for its two neighbors we have

Ξ(x_{n}, n) ∼ \frac{λ_{0}}{p} log n.

Since m_{−1} = m_{1}, it follows from Corollary 3.1 that the two neighbors of the nearly maximally visited points have asymptotically equal local time.

On the other hand, if the occupation time is asymptotically maximal,

Ξ(x_{n}, n) ∼ κ_{0} log n then ξ(x_{n}, n) ∼ \frac{2p}{2p + 1}κ_{0} log n.

With some extra calculation one can find the maximal weight of the unit ball:

w(x_{n}, n) := ξ(x_{n}, n) + Ξ(x_{n}, n), w(n) := max_{x_{n}∈Z}(ξ(x_{n}, n) + Ξ(x_{n}, n)).

We get

lim_{n→∞} \frac{w(n)}{log n} = \frac{2 β}{log ((\frac{2q}{β+1})^{β+1} (p(β − 1))^{β−1})} =: \frac{2 β}{C} , a.s.

where β is the constant defined in (4.29). In this case we have

ξ(x_{n}, n) ∼ \frac{β − 1}{C} log n, and Ξ(x_{n}, n) ∼ \frac{β + 1}{C} log n.

As a final conclusion if any of the three quantities of ξ(x_{n}, n), Ξ(x_{n}, n), w(x_{n}, n), is asymptotically maximal, it uniquely determines the asymptotic values of the other two quantities, an interesting phenomenon which we proved for d > 4 in the symmetric walk case.

References

[1] Baron, M. and Rukhin, A.L.: Distribution of the number of visits of a random walk. Commun. Statist.-Stochastic Models 15(3) (1999), 593–597.

[2] Csáki, E., Földes, A. and Révész, P.: Heavy points of a d-dimensional simple random walk. Statist. Probab. Lett. 76 (2006), 45–57.

[3] Csáki, E., Földes, A. and Révész, P.: Joint asymptotic behavior of local and occupation times of random walk in higher dimensions. Studia Sci. Math. Hungar. 44 (2007), 535– 563.

[4] Csáki, E., Földes, A. and Révész, P.: On the behavior of random walk around heavy points. J. Theor. Probab. 20 (2007), 1041–1057.

[5] Csáki, E., Földes, A. and Révész, P.: On the local times of transient random walks. Acta Applicandae Mathematicae 96 (2007), 147–158.

[6] Csáki, E., Földes, A., Révész, P., Rosen, J. and Shi, Z.: Frequently visited sets for random walks. Stoch. Process. Appl. 115 (2005), 1503–1517.

[7] Dwass, M.: Simple random walk and rank order statistics. Ann. Math. Statist. 38 (1967), 1042–1053.

[8] Dvoretzky, A. and Erdős, P.: Some problems on random walk in space. Proc. Second Berkeley Symposium (1951), 353–367.

[9] Erdős, P. and Taylor, S.J.: Some problems concerning the structure of random walk paths. Acta Math. Acad. Sci. Hung. 11 (1960), 137–162.

[10] Feller, W.: An Introduction to Probability Theory and Its Applications, Vol. I, 3rd ed. John Wiley, New York, 1968.

[11] Feller, W.: An Introduction to Probability Theory and Its Applications, Vol. II, 2nd ed. John Wiley, New York, 1971.

[12] Jordan, K.: Chapters on the Classical Calculus of Probability, Disquisitiones Mathematicae Hungaricae, No. 4. Akadémiai Kiadó, Budapest, 1972.

[13] Pitt, J.H.: Multiple points of transient random walk. Proc. Amer. Math. Soc. 43 (1974), 195-199.

[14] Révész, P.: Random Walk in Random and Non-Random Environments, 2nd ed. World Scientific, Singapore, 2005.

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