Maximal Local Time of a d-dimensional Simple Random Walk on Subsets.

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} City University of New York, 2800 Victory Blvd., Staten Island, New York 10314, U.S.A. E-mail address: afoldes@gc.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: Strong theorems are given for the maximal local time on balls and subspaces for the d-dimensional simple symmetric random walk.

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

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

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

2Research supported by a PSC CUNY Grant, No. 65685-0034.

1. Introduction and main results

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

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

and {e_{1}, e_{2}, ...e_{d}} is a system of orthogonal unit vectors in Z_{d}. Define the local time of the walk by ξ^{(d)}(x, n) := #{k : 0 < k ≤ n, S_{k} = x}. (1.1)

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

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

The properties of ξ^{d}(n) were extensively studied in the cases d = 1, d = 2 and d ≥ 3 separately. For d = 1 the interested reader should consult the monograph of P. Révész [9]. In this paper we are interested in investigating the maximum local time for d ≥ 2 in a restricted sense, namely we want to investigate the maximum on certain subsets of the state space. It is easy to see that these maximums depend on both of the size and the shape of the selected subset. We will only investigate two types of subsets: balls centered at the origin and subspaces.

1.1 Two dimension.

In what follows we present the most important results on local time for d = 2 which are relevant to our investigation.

Theorem A (Erdős and Taylor [7])

lim_{n→∞} P(ξ^{(2)}(0, n) < x log n) = 1 − e^{−πx}.

Let f(x) resp. g(x) be a decreasing resp. increasing function for which f(x) log x ↑ ∞, g(x)(log x)^{−1} ↓ 0. Then

π^{−1}g(n) log n ≤ ξ^{(2)}(0, n)

finitely often with probability one if and only if

∫_{1}^{∞} \frac{g(x)}{x log x}e^{−g(x)} dx < ∞,

f(n) log n ≥ ξ^{(2)}(0, n)

finitely often with probability one if and only if

∫_{1}^{∞} \frac{f(x)}{x log x} dx < ∞.

Theorem B (Erdős and Taylor [7])

\frac{1}{4π} ≤ lim inf_{n→∞} \frac{ξ^{(2)}(n)}{(log n)^{2}} ≤ lim sup_{n→∞} \frac{ξ^{(2)}(n)}{(log n)^{2}} ≤ \frac{1}{π} a.s.

They also conjectured that the upper bound in the above theorem is the correct limit. This was confirmed recently by Dembo et al. [5]. In fact they proved the following more general result:

Theorem C ([5]) Let S_{n} = ∑_{k=1}^{n} X_{k} be an aperiodic random walk with i.i.d. increments X_{k} ∈ Z_{2} that satisfy EX_{1} = 0 and E|X_{1}|^{m} < ∞ for all m < ∞. Denote by Γ = EXX′ the covariance matrix of the increments, and write π_{Γ} := 2π(detΓ)^{1/2}. Define the local time and maximum local time as in the simple walk case. Let M(n, α) denote the number of points in the set {x : ξ(x, n) ≥ α(log n)^{2}}. Then

lim_{n→∞} \frac{ξ^{(2)}(n)}{(log n)^{2}} = π_{Γ}^{−1} a.s.

and for α ∈ (0, π_{Γ}^{−1}]

lim_{n→∞} \frac{log M(n, α)}{log n} = 1 − απ_{Γ} a.s.

Moreover any (random) sequence {x_{n}} such that ξ^{(2)}(x_{n}, n)/ξ^{(2)}(n) → 1, must satisfy

lim_{n→∞} \frac{log |x_{n}|}{log n} = \frac{1}{2} a.s.

For the simple symmetric random walk π_{Γ}^{−1} = π.

As the above results show, the local time of every fixed point is roughly around log n but the maximal local time is around (log n)^{2}. This phenomenon suggests that taking the maximum local time on appropriate subsets, one might get orders in between log n and (log n)^{2}. The following result of Auer is in fact telling us that such a set needs to be quite big.

Theorem D (Auer [1]) For any ε > 0 we have

lim_{n→∞} sup_{||x||≤r_{n}} |\frac{ξ^{(2)}(x, n)}{ξ^{(2)}(0, n)} − 1| = 0 a.s.,

where

r_{n} = exp((log n)^{1/2}(log log n)^{−1/2−ε})

and ||x|| stands for the usual Euclidean norm.

Now let A be a subset of Z_{2} and define

ξ_{A}^{(2)}(n) := max_{x∈A} ξ^{(2)}(x, n). (1.3)

Let moreover B(r) denote the set of lattice points in the disc of radius r centered at the origin, i.e. B(r) := {x ∈ Z_{2} : ||x|| ≤ r}. (1.4)

Then with r_{n} as in Theorem D, for any subset A ⊆ B(r_{n}), ξ_{A}^{(2)}(n)/ξ^{(2)}(0, n) → 1 as n → ∞. Hence for ξ_{A}^{(2)}(n) we have the same asymptotic results as for ξ^{(2)}(0, n).

Denote by L = L(a_{1}, a_{2}) the lattice points x = (x_{1}, x_{2}) on the line a_{1}x_{1} + a_{2}x_{2} = 0, where a_{1} and a_{2} are integers not both of them zero. Now we formulate our results for the two-dimensional case. Our first theorem is telling us that for any line going through the origin which contains lattice points at all, the maximal local time has the same order of magnitude as for the whole plane.

Theorem 1.1. For any line L = L(a_{1}, a_{2}) such that a_{1}, a_{2} are integers, not both of them zero, we have

(1.5)  \frac{1}{8π} ≤ lim inf_{n→∞} \frac{ξ_{L}^{(2)}(n)}{(log n)^{2}} ≤ lim sup_{n→∞} \frac{ξ_{L}^{(2)}(n)}{(log n)^{2}} ≤ \frac{1}{2π}  a.s.

The next two theorems contain our results about discs centered at the origin.

Theorem 1.2. Let r_{n} = n^{α}, 0 < α ≤ 1/2. Then

(1.6)  \frac{4α^{2}}{π} ≤ lim inf_{n→∞} \frac{ξ_{B(r_{n})}^{(2)}(n)}{(log n)^{2}} ≤ lim sup_{n→∞} \frac{ξ_{B(r_{n})}^{(2)}(n)}{(log n)^{2}} ≤ \frac{2α}{π}  a.s.

Theorem 1.3. Let r_{n} = exp((log n)^{β}). For any ε > 0, 1/2 ≤ β < 1, and large enough n we have

\frac{4(1 − ε)}{π}(log n)^{2β} ≤ ξ_{B(r_{n})}^{(2)}(n) ≤ (log n)^{2β+ε} a.s. (1.7)

Corollary 1.1 If L and B(r_{n}) are the sets in Theorems 1.1, 1.2 and 1.3 respectively, then for r_{n} = n^{α}, 0 < α ≤ 1/2 we have

(1.8) \frac{α^{2}}{2π} ≤ lim inf_{n→∞} \frac{ξ_{B(r_{n})∩L}^{(2)}(n)}{(log n)^{2}} ≤ lim sup_{n→∞} \frac{ξ_{B(r_{n})∩L}^{(2)}(n)}{(log n)^{2}} ≤ \frac{1}{π} min (\frac{1}{2}, 2α) a.s.

and for r_{n} = exp((log n)^{β}) with 1/2 ≤ β < 1 we have for any ε > 0 and large n

\frac{1 − ε}{2π}(log n)^{2β} ≤ ξ_{B(r_{n})∩L}^{(2)}(n) ≤ (log n)^{2β+ε} a.s. (1.9)

1.2 Three and higher dimension.

Just like in two dimension, for a subset A ⊆ Z_{d} we define

ξ_{A}^{(d)}(n) := max_{x∈A} ξ^{(d)}(x, n). (1.10)

To formulate the most important known results on ξ^{(d)}(n) of (1.2), we need some more definition. Denote by γ_{d}(n) the probability that in the first n − 1 steps the path does not return to the origin. Then

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

It was proved in Chung and Hunt [2] that, for d ≥ 3

γ_{d}(n) → γ_{d} > 0, (1.11)

and γ_{d} < γ_{d}(n) < γ_{d} + O(n^{1−d/2}) (1.12)

as n → ∞. So γ_{d} is the probability that the d-dimensional simple symmetric random walk never returns to its starting point.

Let ξ^{(d)}(0, ∞) be the total local time at 0 of the infinite path in Z_{d}. Then (see [7]) ξ^{(d)}(0, ∞) has geometric distribution:

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

Erdős and Taylor [7] proved the following strong law for the maximal local time:

Theorem F ([7])For d ≥ 3

lim_{n→∞} \frac{ξ^{(d)}(n)}{log n} = λ_{d} a.s., (1.14)

where

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

Remark. For the exact value of γ_{3} see e.g. Spitzer [10], p. 103 which implies that λ_{3} < 1 and hence λ_{d} < 1 for all d ≥ 3.

Let B(r) stand for the (discrete) ball centered at the origin in the d-dimensional space and having radius r, i.e.

B(r) := {x ∈ Z_{d} : ||x|| ≤ r}. (1.16)

Let furthermore x = (x_{1}, x_{2}, …, x_{d}),

S_{d−1} := {x ∈ Z_{d} : a_{1}x_{1} + a_{2}x_{2} + ... + a_{d}x_{d} = 0}

and

S_{d−2} := {x ∈ Z_{d} : a_{1}x_{1} + a_{2}x_{2} + ... + a_{d}x_{d} = 0, b_{1}x_{1} + b_{2}x_{2} + ... + b_{d}x_{d} = 0}

with integer coefficients a_{1}, a_{2}, ...a_{d}, b_{1}, b_{2}, ...b_{d}.

For subspaces we will prove the following two results.

Theorem 1.4. Suppose that a_{1}, a_{2}, ...a_{d} are integers, not all of them zero, then

lim_{n→∞} \frac{ξ_{S_{d−1}}^{(d)}(n)}{log n} = \frac{λ_{d}}{2} a.s.

The above theorem is telling us that the maximal local time in the d − 1 dimensional subspace has the same order of magnitude as in the whole d-dimensional space. On the other hand, the next theorem shows that in the d−2 dimensional subspace the maximal local time gets drastically smaller.

Theorem 1.5. Suppose that a_{1}, a_{2}, ...a_{d} are integers, not all of them zero and b_{1}, b_{2}, ...b_{d} are also integers not all of them zero. Assume also that the vectors (a_{1}, a_{2}, …, a_{d}) and (b_{1}, b_{2}, …, b_{d}) are not parallel. Then

lim_{n→∞} \frac{ξ_{S_{d−2}}^{(d)}(n)}{log log n} = λ_{d} a.s.

For balls centered at the origin we will prove the following result:

Theorem 1.6. For any sequence r_{n} ↑ ∞, such that lim sup_{n→∞}(log r_{n})/(log n) ≤ 1/2, we have

lim_{n→∞} \frac{ξ_{B(r_{n})}^{(d)}(n)}{log r_{n}} = 2λ_{d} a.s. (1.17)

The organization of the paper is as follows. In Section 2 we will present some well-known facts and prove some preliminary results. Sections 3 and 4 contain the proofs of the two dimensional and higher dimensional results, respectively. In Section 5 some implications of the above results and some open questions will be discussed. Throughout the paper c, c_{1}, …, C, C_{1}, … will denote positive constants, the value of which is unimportant and may vary from line to line.

2. Preliminary facts and results

First we present the d-dimensional law of the iterated logarithm and rate of escape for simple walk.

Fact 1. (Dvoretzky and Erdős [6] or [9], pp. 193, 195) For a simple symmetric random walk in Z_{d}

(2.1)  lim sup_{n→∞}(2n log log n)^{−1/2}d^{1/2}||S_{n}|| = 1  a.s.

Moreover, in case d ≥ 3, for any 0 < ε < 1/2 and large enough n we have

||S_{n}|| > n^{1/2−ε} a.s. (2.2)

Consider now the case d = 2. Introduce

p(x) : = P(min{n : S_{n} = 0} > min{n : S_{n} = x})
(2.3)  = P({S_{n}} reaches x before returning to 0).

We will need the following two lemmas from Révész [9]:

Fact 2. ([9], p. 219) For a simple symmetric random walk in Z_{2} there exists a positive constant C such that for any x ∈ Z_{2} with ||x|| ≥ 2

p(x) ≥ \frac{C}{log ||x||}. (2.4)

Let us define ρ_{0} := 0, ρ_{n} := min{k : k > ρ_{n−1}, S_{k} = 0}, n = 1, 2, … (2.5)

Fact 3. ([9], pp. 219-220.) For a simple symmetric random walk in Z_{2} let Y_{i}(x) := ξ^{(2)}(x, ρ_{i}) − ξ^{(2)}(x, ρ_{i−1}), i = 1, 2, … (2.6) Then for fixed x ∈ Z_{2}, {Y_{i}(x)}_{i=1}^{∞} are i.i.d. random variables with the following distribution: P(Y_{1}(x) = 0) = 1 − p(x) (2.7)

P(Y_{1}(x) = k) = (1 − p(x))^{k−1}p^{2}(x), k = 1, 2, … (2.8)

Now we will prove our first Lemma 2.1. For a simple symmetric random walk in Z_{2} we have for arbitrary x ∈ Z_{2}, and any u > 0

P (∑_{k=1}^{n} Y_{k}(x) > u n) ≤ e^{np(x)(1−u/2)}. (2.9)

Remark. Fact 3 and Lemma 2.1 are true for more general random walk, but we need them only for simple symmetric case. Proof: From (2.8) we easily get with q(x) = 1 − p(x) that for any z > 0, for which q(x)e^{z} < 1,

E (e^{zY_{1}(x)}) = q(x) + \frac{p^{2}(x)e^{z}}{1 − q(x)e^{z}} . (2.10)

Putting z = log(2/(1 + q(x))), we have

q(x)e^{z} = \frac{2q(x)}{1 + q(x)} < 1 (2.11)

so (2.10) holds. Thus

E (e^{zY_{1}(x)}) = q(x) + \frac{p^{2}(x)e^{z}}{1 − q(x)e^{z}} = 1 + p(x). (2.12)

By exponential Markov inequality, and (2.12) we have

P (∑_{k=1}^{n} Y_{k}(x) > u n) ≤ \frac{(Ee^{zY_{1}(x)})^{n}}{e^{zun}} = (1 + p(x))^{n} (1 − \frac{p(x)}{2})^{un}
(2.13)  ≤ exp (np(x)(1 − u/2)) ,

where the inequality 1 + v ≤ e^{v} was used. □

For our next lemma we need further notations and facts. Our main source for these is Spitzer’s book [10]. Here we consider a two-dimensional symmetric aperiodic recurrent walk on Z_{2}, more general than a simple symmetric random walk. Recall that a random walk in Z_{d} is aperiodic if the steps are not supported on a proper subgroup of Z_{d}. All what we are quoting however work in case of a one-dimensional walk under the same constraints as well. We adopt the notations and definitions listed below from [10]. Denote the n-step probability transition function by

P_{n}(x, y) = P_{n}(y, x) = P_{n}(0, x − y) = P(S_{n} = x − y|S_{0} = 0), n = 0, 1, …, x, y ∈ Z_{2}.

For a ≥ 0 integer we define

T_{a} := min{j > 0 : S_{a+j} = 0} (2.14)

and will denote T_{0} =: T. Let (see [10], pp. 107, 160-161)

(2.15) Q_{n}(x, y) := P_{x}(S_{n} = y, T > n), n = 0, 1, …, x, y ∈ Z_{2} − {0},

and

g(x, y) := ∑_{n=0}^{∞} Q_{n}(x, y), x, y ∈ Z_{2} − {0} (2.16)

where P_{x}(·) := P(·|S_{0} = x). Using P(·) := P_{0}(·) we also recall from Spitzer [10] that

(2.17) P_{x}(T > n) = ∑_{t≠0} g(x, t) ∑_{y≠0} Q_{n}(t, y)P (y, 0), n = 0, 1, …, x ∈ Z_{2} − {0}

and introducing

(2.18) v_{n}(t) = \frac{1}{P(T > n + 1)} ∑_{y≠0} Q_{n}(t, y)P (y, 0), n = 0, 1, …, t ∈ Z_{2} − \{0\},

we get for x ≠ 0

(2.19) P_{x}(T > n) = P(T > n + 1) ∑_{t≠0} g(x, t)v_{n}(t), n = 0, 1, … with

v_{n}(t) ≥ 0, ∑_{t≠0} v_{n}(t) = 1. (2.20)

We introduce further the notations (see [10], pp. 114, 139, 328)

G_{n}(x, y) = ∑_{k=0}^{n} P_{k}(x, y), n = 0, 1, …, x, y ∈ Z_{2}, (2.21)

the truncated Green function

g(n) = G_{n}(0, 0) = ∑_{k=0}^{n} P_{k}(0, 0), n = 0, 1, … (2.22)

and the potential kernel

a(x) = ∑_{n=0}^{∞}(P_{n}(0, 0) − P_{n}(0, x)), x ∈ Z_{2}. (2.23)

Then it is known, that 0 ≤ g(x, y) = a(x) + a(y) − a(x − y). (2.24)

We recall from Spitzer [10], p. 139 Fact 4. For any symmetric recurrent aperiodic random walk in two dimension (2.25) ∑_{y∈Z_{2}} P_{n+1}(x, y)a(y) = a(x) + G_{n}(x, 0), n = 0, 1, …, x ∈ Z_{2}. Now we are ready to prove our Lemma 2.2. For any symmetric, recurrent aperiodic walk in two dimension we have

P(T_{a} ≥ k) ≤ 2\frac{g(a)}{g(k − 1)}, a = 0, 1, …, k = 1, 2, … (2.26)

Proof: We start with the following simple observation: for k ≥ 1, a ≥ 0 (2.27) P(T_{a} ≥ k) = ∑_{x∈Z_{2}} P(T_{a} ≥ k|S_{a} = x)P(S_{a} = x) = ∑_{x∈Z_{2}} P_{a}(0, x)P_{x}(T ≥ k).

Now (2.24) and the symmetry of the walk implies that a(x + y) ≤ a(x) + a(y). (2.28)

Moreover, denoting x + y = z we easily get from (2.28) that a(z) ≤ a(x) + a(z − x) = a(x) + a(x − z), (2.29) thus a(z) − a(x − z) ≤ a(x), (2.30) which in turn, combined with (2.24) implies that g(x, y) ≤ 2 a(x). (2.31) Combining (2.19), (2.20) and (2.31) we conclude that for x ≠ 0 P_{x}(T > n) ≤ 2a(x)P(T > n + 1), n = 0, 1, … (2.32) Now using (2.27), (2.32), Fact 4 and the simple observation that a(0) = 0, we get that

P(T_{a} ≥ k) ≤ 2P(T ≥ k + 1) ∑_{x∈Z_{2}−{0}} P_{a}(0, x)a(x) + P_{a}(0, 0)P(T ≥ k)
≤ 2P(T ≥ k) ( ∑_{x∈Z_{2}} P_{a}(0, x)a(x) + P_{a}(0, 0))
(2.33)  ≤ 2P(T ≥ k)(G_{a−1}(0, 0) + P_{a}(0, 0)) ≤ 2P(T ≥ k)g(a).

To estimate P(T > k) we use an argument essentially from Erdős and Taylor [7]. Partitioning according to the last return to zero we get

∑_{j=0}^{k} P(T > k − j)P_{j}(0, 0) = 1 (2.34)

implying that

P(T > k) ∑_{j=0}^{k} P_{j}(0, 0) ≤ 1, (2.35)

hence P(T > k) ≤ 1/g(k). (2.36) Now (2.33) and (2.36) imply our lemma. □

Fact 5. If the walk is recurrent and aperiodic with finite second moment, then we have as n → ∞ g(n) ∼ c_{2} log n for d = 2, (2.37)

g(n) ∼ c_{1}\sqrt{n} for d = 1. (2.38)

The case d = 2 is well-known for strongly aperiodic walk (see [10], p. 75) and [5] how to weaken this condition for the aperiodic case). The case d = 1 is well-known (see e.g. [10], p. 381).

Let {S_{n}} be a symmetric recurrent aperiodic walk in two dimension. Consider the following problem. Let T_{a} be defined by (2.14). At a + T_{a} the walk is at 0. Now after another a steps we wait again until the walk returns to 0. Keep repeating this procedure, we would like to estimate the number of such returns within n steps. This problem was considered in [3] in one dimension. Here we repeat essentially the same argument and spell out it in the d = 2 case with the appropriate modifications, using Lemma 2.2. To formulate this problem precisely, let

ζ_{1}(a) := a, α_{k}(a) := T_{ζ_{k}(a)}, ζ_{k+1}(a) := ∑_{i=1}^{k} α_{i}(a) + (k + 1)a, k = 1, 2, … (2.39)

Then α_{k}(a), k = 1, 2, … are i.i.d. random variables having the same distribution as T_{a}.

Lemma 2.3. For a symmetric recurrent aperiodic random walk in Z_{2} we have for a > 1, u > 1, k ≥ 1

P (∑_{i=1}^{k} α_{i}(a) ≥ u) ≤ C k \frac{log a}{log u}. (2.40)

Proof: By Lemma 2.2 and Fact 5

(2.41) P(T_{a} ≥ k) ≤ 2\frac{g(a)}{g(k − 1)} ≤ C \frac{log a}{log(k − 1)} ≤ C \frac{log a}{log k}.

Let

uα_{k}(a) = \{ \begin{matrix}α_{k}(a) & if α_{k}(a) ≤ u \\ 0 & if α_{k}(a) > u \end{matrix} (2.42)

First observe, that

(2.43) E(^{u}α_{i}(a)) ≤ ∑_{j=0}^{u} P(T_{a} ≥ j) ≤ 2 + C ∑_{j=2}^{u} \frac{log a}{log j} ≤ Cu\frac{log a}{log u}.

Define the event

A = ⋂_{j=1}^{k}{α_{j}(a) < u}. (2.44)

P (∑_{i=1}^{k} α_{i}(a) ≥ u) ≤ P (∑_{i=1}^{k} α_{i}(a) ≥ u, A) + P(Ā) ≤ P (∑_{i=1}^{k} ^{u}α_{i}(a) ≥ u)
(2.45)  + kP(α_{i}(a) ≥ u) ≤ \frac{kE(^{u}α_{i}(a))}{u} + kC \frac{log a}{log u} ≤ Ck \frac{log a}{log u}.

□ Let a_{t} > 1 be an integer valued function of t and let ν_{t} be the largest integer N for which

∑_{i=1}^{N} α_{i}(a_{t}) + (N + 1)a_{t} ≤ t. (2.46)

Lemma 2.4. Under the conditions of Lemma 2.3 for f(t) > 0, (f(t) + 2)a_{t} < t − 1 we have

P(ν_{t} ≤ f(t)) ≤ Cf(t) \frac{log a_{t}}{log(t − (f(t) + 2)a_{t})}. (2.47)

Proof: By Lemma 2.3

P(ν_{t} ≤ f(t)) ≤ P(ν_{t} ≤ [f(t)] + 1) ≤ P ( ∑_{i=1}^{[f(t)]+1} α_{i}(a_{t}) > t − ([f(t)] + 2)a_{t}))
(2.48)  ≤ C(f(t) + 1)\frac{log a_{t}}{log(t − (f(t) + 2)a_{t})},

implying our statement. □

As mentioned above, the quantities defined in this section have analogues in one dimension. Also, there are corresponding one-dimensional analogues of results quoted for two-dimensional case. We recall the one-dimensional versions of Lemmas 2.3 and 2.4.

Fact 6. ([3]) Consider a symmetric aperiodic random walk {S_{n}} on Z_{1} with finite variance and define α_{i}(a) and ν_{t} exactly as before for {S_{n}}. Then for a > 1, u > 1, k ≥ 1

P (∑_{i=1}^{k} α_{i}(a) ≥ u) ≤ C k\sqrt{\frac{a}{u}}. (2.49)

Furthermore, if f(t) > 0, a_{t} > 0, (f(t) + 2)a_{t} < t we have

P(ν_{t} ≤ f(t)) ≤ Cf(t)\begin{matrix}√ & \overline{a_{t}} \\ √ & \overline{t − (f(t) + 2)a_{t}} \end{matrix} . (2.50)

We will need the following upper tail estimates essentially from Erdős and Taylor [7].

Fact 7. ([7] or [5]) For the simple symmetric random walk on the plane we have for any α > 0 and 0 < δ < 1, n ≥ 1

P(ξ^{(2)}(0, n) ≥ α(log n)^{2}) < n^{−(1−δ)πα}. (2.51)

Fact 8. ([7], (3.6)) For the simple symmetric random walk on the plane we have for any α > 0, δ > 0, n ≥ 1

P(ξ^{(2)}(0, n) ≥ α(log n)^{2}) > n^{−(1+δ)πα}. (2.52)

Fact 9. ([3]) Let {S_{n}} be a one-dimensional symmetric aperiodic random walk on Z_{1} with

σ^{2} = E(X_{1}^{2}) < ∞ and suppose that x_{n} → ∞, x_{n}/n^{1/2} → 0 as n → ∞. Let ξ(0, n) be its local time at zero. Then for any ε > 0 and large enough n

C_{1} exp (−(1 + ε)\frac{x_{n}^{2}σ^{2}}{2} ) ≤ P(ξ(0, n) ≥ x_{n} n^{1/2}) ≤ C_{2} exp (−(1 − ε)\frac{x_{n}^{2}σ^{2}}{2} ) . (2.53)

Fact 10. ([4], (2.1) and [8], Lemma 2.5.) For a symmetric aperiodic random walk with finite variance in Z_{2} we have for any x > 0

P (ξ^{(2)}(0, n) ≥ x log n) ≤ exp(−cx) (2.54)

with some constant c > 0.

3. Proofs of the two dimensional results.

Proof of Theorem 1.1. Consider the line L = L(a_{1}, a_{2}) with a_{1}x_{1} + a_{2}x_{2} = 0, where a_{1} and a_{2} are integers, not both of them zero. Without loss of generality we may assume that a_{1} and a_{2} are relatively prime.

For the two-dimensional random walk define a one-dimensional walk with steps

Y_{i} = a_{j} if X_{i} = e_{j}, i = 1, 2, ... j = 1, 2.

Y_{i} = −a_{j} if X_{i} = −e_{j}, i = 1, 2, ... j = 1, 2.

Then Z_{n} = ∑_{i=1}^{n} Y_{i} is an aperiodic one-dimensional symmetric random walk with Z_{n} = 0 if and only if S_{n} ∈ L(a_{1}, a_{2}). Thus denoting by V^{L}(n) = #{i : 1 ≤ i ≤ n, S_{i} ∈ L(a_{1}, a_{2})}, the number of visits of S_{n} on L(a_{1}, a_{2}), we have

V^{L}(n) = ξ^{Z}(0, n), (3.1) where ξ^{Z}(·, n) is the local time of {Z_{n}}.

To get the upper bound in our theorem, denote by D(n) the set of lattice points on L which are visited up to n by {S_{i}}, and denote by |D(n)| the number of points in D(n). Select a subsequence n_{j} = [e^{j}], j = 1, 2, ... and let for any x ∈ Z_{2}

C_{x}^{j} = {ξ^{(2)}(x, n_{j+1}) > λ(log n_{j})^{2}}.

Then using (3.1), Facts 7 and 9 we conclude that for any λ > 0, δ > 0, ε > 0 and j large enough

P(ξ_{L}^{(2)}(n_{j+1}) > λ(log n_{j})^{2})
≤ P ( ⋃_{x∈D(n_{j+1})} C_{x}^{j}, |D(n_{j+1})| ≤ \sqrt{n_{j+1} log n_{j+1}}) + P (|D(n_{j+1})| > \sqrt{n_{j+1} log n_{j+1}})

≤ P ( ⋃_{x∈D(n_{j+1})} C_{x}^{j}, |D(n_{j+1})| ≤ \sqrt{n_{j+1} log n_{j+1}}) + P (ξ^{Z}(0, n_{j+1}) > \sqrt{n_{j+1} log n_{j+1}})

≤ \sqrt{n_{j+1} log n_{j+1}} P(ξ^{(2)}(0, n_{j+1}) > λ(log n_{j})^{2}) + C_{2} exp (−(j + 1)\frac{(1 − ε)σ^{2}}{2} )
≤ \sqrt{n_{j+1} log n_{j+1}} exp (−λ(1 − δ)π \frac{j^{2}}{j + 1}) + C_{2} exp (−j \frac{(1 − ε)σ^{2}}{2} )

≤ exp (−(1 − δ)^{2}π j λ + j(1/2 + ε)) + C_{2} exp (−j \frac{(1 − ε)σ^{2}}{2} ) , (3.2)

where we used in the second inequality above that |D(n)| ≤ V^{L}(n). σ^{2} is the variance of Y_{i} and hence depends only on a_{1} and a_{2}. It is easy to see that we can choose ε > 0, δ > 0 for which the last line of (3.2) is summable in j whenever λ > 1/(2π), which in turn, using Borel-Cantelli lemma and the usual monotonicity argument implies

(3.3)  lim sup_{n→∞} \frac{ξ_{L}^{(2)}(n)}{(log n)^{2}} ≤ \frac{1}{2π} ,

so we have the upper half of the theorem.

To get the lower bound, we will essentially follow Erdős and Taylor’s argument with some modification. We consider the walk {S_{i}}, wait [n^{α}] steps and observe ξ^{(2)}(0, [n^{α}]). The number 0 < α < 1 will be choosen later. At time [n^{α}] the walk is somewhere on the plane, and we wait until its first return to L = L(a_{1}, a_{2}). When it returns to L, we observe the local time of the hitting point of L for a time interval [n^{α}], and then wait again for the walk to return to L. We keep repeating this procedure for a total time of n steps. This construction ensures that the local times of these hitting points over a time interval [n^{α}] are i.i.d. random variables having the same distribution as ξ^{(2)}(0, [n^{α}]). Combining this observation with our Fact 6, would produce our lower bound in the theorem. In what follows we work out the above outlined ideas with the added complexity of working with subsequences as before. Let n_{j} = j^{β}, j = 1, 2, … with integer β to be choosen later. Now fix j ≥ 1 and define for k = 1, 2, …

η_{0}^{j} := 0,  η_{k}^{j} := min{i > η_{k−1}^{j} + [n_{j}^{α}] : S_{i} ∈ L},  Y_{k}^{j} := S_{η_{k}^{j}}. (3.4)

Furthermore, let ν_{j} be the largest integer N for which

η_{N}^{j} + [n_{j}^{α}] ≤ n_{j}. (3.5)

Put f(n_{j}) = [n_{j}^{(1−α)(1−η)/2}] for any 0 < η < 1. Since S_{i} ∈ L if and only if Z_{i} = 0, we can apply Fact 6 to get

P (ν_{j} < f(n_{j})) ≤ Cn_{j}^{(α−1)η/2}. (3.6)

Introduce further the events

A_{k}^{j} = {ξ^{(2)}(Y_{k}^{j}, η_{k}^{j} + [n_{j}^{α}]) − ξ^{(2)}(Y_{k}^{j}, η_{k}^{j}) < K(log n_{j+1})^{2}}. (3.7)

For fixed j the events A_{k}^{j} are independent in k and having the same probability as A_{1}^{j}. Using the above notations and (3.6)

P (ξ_{L}^{(2)}(n_{j}) < K(log n_{j+1})^{2}) ≤ P ( ⋂_{k=1}^{ν_{j}} A_{k}) ≤ Cn_{j}^{(α−1)η/2} + (P(A_{1}^{j}))^{f(n_{j})} . (3.8)

Now by Fact 8 we have

P(A_{1}^{j}) = P(ξ^{(2)}(0, [n_{j}^{α}]) < K(log n_{j+1})^{2})
(3.9)  ≤ 1 − exp \{−\frac{Kπ}{α} (1 + δ)(β log j) (\frac{log(j + 1)}{log j})^{2}\} .

Consequently, we have for j big enough

P (ξ_{L}^{(2)}(n_{j}) < K(log n_{j+1})^{2})
≤ Cn_{j}^{(α−1)η/2} + (1 − exp \{−\frac{Kπ}{α} (1 + δ)^{2}(β log j)\})^{(n_{j})^{\frac{(1−α)(1−η)}{2}}}

≤ Cj^{β(α−1)η/2} + (1 − \frac{1}{j^{\frac{Kπ}{α} β(1+δ)^{2}}} )^{j^{\frac{β(1−α)(1−η)}{2}}}
(3.10)  ≤ Cj^{β(α−1)η/2} + C exp\{−j^{\frac{β(1−α)(1−η)}{2} − \frac{Kπ}{α} β(1+δ)^{2}}\}.

For given 0 < α < 1 and η > 0 select an integer β such that

β(α − 1)η/2 < −1

so that the first term in (3.10) is summable in j. The second term will be summable in j whenever

\frac{(1 − α)(1 − η)}{2} > \frac{Kπ}{α} (1 + δ)^{2}. (3.11)

On choosing α = 1/2, δ > 0 and η > 0 small, we conclude that (3.10) is summable in j if

K < \frac{1}{8π} . (3.12)

Using again Borel-Cantelli lemma and the usual monotonicity argument, we get

(3.13)  lim sup_{n→∞} \frac{ξ_{L}^{(2)}(n)}{(log n)^{2}} ≥ \frac{1}{8π} ,

proving our theorem. □

Proof of Theorem 1.2. First observe that the condition α ≤ 1/2 is not a real restriction as by the LIL (Fact 1) with probability 1 the walk in the time interval [0, n] remains in B(r_{n}) for r_{n} = n^{α}, α > 1/2, n large, thus ξ_{B(r_{n})}^{(2)}(n) = ξ^{(2)}(n) eventually with probability 1.

In case α ≤ 1/2, using the LIL again, during the first [r_{n}^{2−ε}] steps the walk remains in B(r_{n}) with probability 1 for any ε > 0 and large n. Hence by Theorem C for any ε > 0 and large enough n,

ξ_{B(r_{n})}^{(2)}(n) ≥ ξ^{(2)}(r_{n}^{2−ε}) ≥ \frac{1}{π} (log r_{n}^{2−ε})^{2} (1 − ε)
(3.14)  = \frac{1}{π} (log n^{α(2−ε)})^{2} (1 − ε) = \frac{α^{2}(2 − ε)^{2}}{π} (log n)^{2}(1 − ε)  a.s.

Let ε → 0 to get

(3.15)  lim inf_{n→∞} \frac{ξ_{B(r_{n})}^{(2)}(n)}{(log n)^{2}} ≥ \frac{4α^{2}}{π}  a.s.

The upper bound is proved in Dembo et al. [5].

Thus we have our theorem. □ Remark. Observe that in case α = 1/2 the lim inf and lim sup coincide.

Proof of Theorem 1.3. Let r_{n} = exp{(log n)^{β}}. To get the lower half of the theorem, by the same argument as in Theorem 1.2, in the first [r_{n}^{2−ε}] steps the walk remains in B(r_{n}) with probability 1, thus by Theorem C for large n we have

ξ_{B(r_{n})}^{(2)}(n) ≥ ξ^{(2)}([r_{n}^{2−ε}]) ≥ \frac{1}{π} (log r_{n}^{2−ε})^{2} (1 − ε)
(3.16)  = \frac{1}{π} (log n)^{2β}(2 − ε)^{2}(1 − ε)  a.s.

Sending now ε → 0 we get

(3.17)  lim inf_{n→∞} \frac{ξ_{B(r_{n})}^{(2)}(n)}{(log n)^{2β}} ≥ \frac{4}{π}  a.s.

To get the other half of the theorem, consider first a disc A_{n} := B(exp{n^{γ}}) where 1/2 ≤ γ < 1. Recall the definition of ρ_{n} in (2.5). First we show that for arbitrary small δ > 0

max_{x∈A_{n}} ξ^{(2)}(x, ρ_{n}) ≤ n^{2γ+δ} a.s. (3.18)

Using the definition of Y_{n}(x) in Fact 3 and Lemma 2.1 we have

P(max_{x∈A_{n}} ξ^{(2)}(x, ρ_{n}) > u n) ≤ P(max_{x∈A_{n}} ∑_{k=1}^{n} Y_{k}(x) > u n)
≤ C_{1} exp{2n^{γ}} max_{x∈A_{n}} P(∑_{k=1}^{n} Y_{k}(x) > u n)
≤ C_{1} exp{2n^{γ}} max_{x∈A_{n}} exp{np(x)(1 − u/2)}
(3.19)  ≤ C_{1} exp{2n^{γ}} exp{C_{2}n^{1−γ}(1 − u/2)},

where in the last inequality we used that for all x ∈ A_{n} p(x) ≥ C_{2}n^{−γ} by Fact 2. Selecting now u = n^{θ} we get from (3.19) that for n big enough

(3.20) P(max_{x∈A_{n}} ξ^{(2)}(x, ρ_{n}) > n^{1+θ}) ≤ C_{1} exp{2n^{γ}} exp{−C_{3}n^{1+θ−γ}}.

The probabilities in (3.20) can be summed up for n if 1+θ−γ > γ. Thus for any 1/2 ≤ γ < 1 and for an arbitrary small δ > 0 we might select θ > 0 such that

1 + θ = 2γ + δ (3.21)

to get by Borel-Cantelli lemma that (3.18) holds.

Applying now (3.18) with n = ξ^{(2)}(0, k) we get that

max_{x∈A_{ξ^{(2)}(0,k)}} ξ^{(2)}(x, k) ≤ max_{x∈A_{ξ^{(2)}(0,k)+1}} ξ^{(2)}(x, ρ_{ξ^{(2)}(0,k)+1})
(3.22)  ≤ (ξ^{(2)}(0, k) + 1)^{2γ+δ} ≤ (log k)^{2γ+δ′}  a.s.

for any δ′ > δ by Theorem A. On the other hand, (3.22) and Theorem A imply that for any 0 < γ′ < γ and k large enough

(3.23) max_{x∈B(exp{(log k)^{γ′}})} ξ^{(2)}(x, k) ≤ max_{x∈A_{ξ^{(2)}(0,k)}} ξ^{(2)}(x, k) ≤ (log k)^{2γ+δ′}  a.s.

which is equivalent to our statement. □

Proof of Corollary 1.1. Clearly the upper bound for ξ_{B(r_{n})}^{(2)}(n) or ξ_{L}^{(2)}(n) holds for ξ_{B(r_{n})}^{(2)}∩L as well. On the other hand, to get the lower bounds, observe that with probability one, in the first [r_{n}^{2−ε}] steps the walk remains in B(r_{n}) for large n. Consequently

ξ_{L}^{(2)}(r_{n}^{2−ε}) = ξ_{L∩B(r_{n})}^{(2)}(r_{n}^{2−ε}) ≤ ξ_{L∩B(r_{n})}^{(2)}(n). (3.24)

But (3.24) and Theorem 1.1 imply our statements. □

4. Proofs of the higher dimensional results.

Proof of Theorem 1.4. The proof of this theorem is very similar to the proof of Theorem 1.1. Consider the subspace

S_{d−1} = {x ∈ Z_{d} : a_{1}x_{1} + a_{2}x_{2} + ... + a_{d}x_{d} = 0}

with integer coefficients a_{1}, a_{2}, ...a_{d}, not all of them zero. Without loss of generality we may assume that the largest common divisor of (a_{1}, …, a_{d}) is equal to 1.

Define a one-dimensional random walk with the following steps:

Y_{i} = a_{ℓ} if X_{i} = e_{ℓ},  ℓ = 1, 2, ...d,  i = 1, 2, ...
Y_{i} = −a_{ℓ} if X_{i} = −e_{ℓ},  ℓ = 1, 2, ...d,  i = 1, 2, ... (4.1)

Note that these values are not necessarily distinct. In that case we sum up the probabilities 1/(2d) according to their multiplicity.

Z_{n} = ∑_{i=1}^{n} Y_{i}, n = 1, 2, … is an aperiodic one-dimensional symmetric random walk with Z_{n} = 0 if and only if S_{n} ∈ S_{d−1}. Thus denoting by V^{S_{d−1}}(n) = #{i : 1 ≤ i ≤ n, S_{i} ∈ S_{d−1}}, the number of visits of {S_{i}} up to time n in S_{d−1}, we have

V^{S_{d−1}}(n) = ξ^{Z}(0, n), (4.2)

where ξ^{Z}(0, n) is the local time at zero up to time n of the random walk {Z_{i}}.

To get the upper bound in our theorem, denote by D(n) the set of lattice points on S_{d−1} which are visited by {S_{i}} up to time n and denote |D(n)| the number of points in D(n). Select a subsequence n_{j} = [e^{j}], j = 1, 2, … and define the events for any x ∈ Z_{d}

C_{x}^{j} = {ξ^{(d)}(x, n_{j+1}) > λ(log n_{j})}.

Then using the exact distribution (1.13), and Fact 9 we conclude, that

P(ξ_{S_{d−1}}^{(d)}(n_{j+1}) > λ log n_{j})
≤ P ( ⋃_{x∈D(n_{j+1})} C_{x}^{j}, |D(n_{j+1})| ≤ \sqrt{n_{j+1} log n_{j+1}}) + P (|D(n_{j+1})| > \sqrt{n_{j+1} log n_{j+1}})

≤ P ( ⋃_{x∈D(n_{j+1})} C_{x}^{j}, |D(n_{j+1})| ≤ \sqrt{n_{j+1} log n_{j+1}}) + P (ξ^{Z}(0, n_{j+1}) > \sqrt{n_{j+1} log n_{j+1}})

≤ \sqrt{n_{j+1} log n_{j+1}} P(ξ^{(d)}(0, n_{j+1}) > λ log n_{j}) + C_{2} exp (−(j + 1)\frac{(1 − ε)σ^{2}}{2} )
≤ \sqrt{n_{j+1} log n_{j+1}} P(ξ^{(d)}(0, ∞) > λ log n_{j}) + C_{2} exp (−(j + 1)\frac{(1 − ε)σ^{2}}{2} )

≤ \sqrt{n_{j+1} log n_{j+1}} exp (−\frac{λ}{λ_{d}} j) + C_{2} exp (−(j + 1)\frac{(1 − ε)σ^{2}}{2} )

≤ C\sqrt{j} exp (j (\frac{1}{2} − \frac{λ}{λ_{d}} )) + C_{2} exp (−(j + 1)\frac{(1 − ε)σ^{2}}{2} ) (4.3)

for j big enough, where we used in the second inequality above that |D(n)| ≤ V^{S_{d−1}}(n). The σ above depends only on a_{1}, a_{2}, ...a_{d}. It is easy to see that the last line of (4.3) is summable in j whenever λ > λ_{d}/2, which in turn, using Borel-Cantelli lemma and the usual monotonicity argument implies

(4.4)  lim sup_{n→∞} \frac{ξ_{S_{d−1}}^{(2)}(n)}{log n} ≤ \frac{λ_{d}}{2}  a.s.,

so we have the upper half of the theorem.

To get the lower bound, we will again follow Erdős and Taylor’s argument with the appropriate modification. We consider the walk {S_{n}}, wait [(log n)^{2}] steps. After that many steps we wait until the walk arrives back to S_{d−1}. Then wait again [(log n)^{2}] steps, and repeat this procedure over and over again. The probability that an arrival point to S_{d−1} will be visited by the walk again in the next [log n] steps is by (1.12)

1 − γ_{d} + O (\frac{1}{(log n)^{1/2}} )

and the probability that it will be visited at least [λ log n] times (with some λ < 1) within [(log n)^{2}] steps is greater than

(1 − γ_{d} + O (\frac{1}{(log n)^{1/2}} ))^{[λ log n]} . (4.5)

These ideas will be combined with our Fact 6, and applied for subsequences, just like in the proof of Theorem 1.1.

Let n_{j} = j^{β}, j = 1, 2, … with some integer β. Define

(4.6) η_{0}^{j} := 0,  η_{k}^{j} := min{i > η_{k−1}^{j} + [(log n_{j})^{2}] : S_{i} ∈ S_{d−1}},  Y_{k}^{j} := S_{η_{k}^{j}}.

Furthermore, let ν_{j} be the largest integer N for which

η_{N}^{j} + [(log n_{j})^{2}] ≤ n_{j}. (4.7)

Selecting for any 0 < η < 1, f(n_{j}) = [(\frac{n_{j}}{(log n_{j})^{2}} )^{(1−η)/2}], it is easy to see that from Fact 6 we get

P (ν_{j} < f(n_{j})) ≤ C (\frac{(log n_{j})^{2}}{n_{j}} )^{η/2} . (4.8)

Introduce further the events

(4.9) A_{k}^{j} = {ξ^{(d)}(Y_{k}^{j}, η_{k}^{j} + [(log n_{j})^{2}]) − ξ^{(d)}(Y_{k}^{j}, η_{k}^{j}) < λ log n_{j+1}}.

For fixed j the events A_{k}^{j} are independent in k and having the same probability as A_{1}^{j}. Using (4.8) we get that

P (ξ_{S_{d−1}}^{(d)}(n_{j}) < λ log n_{j+1}) ≤ P ( ⋂_{k=1}^{ν_{j}} A_{k}^{j})

(4.10)  ≤ C (\frac{(log n_{j})^{2}}{n_{j}} )^{η/2} + (P(A_{1}^{j}))^{f(n_{j})} .

Now by (4.5) we have

P(A_{1}^{j}) = P(ξ^{(d)}(0, [(log n_{j})^{2}]) < λ(log n_{j+1}))
(4.11)  < 1 − (1 − γ_{d} + O (\frac{1}{(log n_{j})^{1/2}} ))^{λ log n_{j+1}} = 1 − n_{j+1}^{− \frac{λ}{λ_{d}} (1+O(_{\frac{1}{(log n_{j})^{1/2}}} ))}.

Consequently,

P (ξ^{(d)}(n_{j}) < λ(log n_{j+1}))

≤ C (\frac{β^{2}(log j)^{2}}{j^{β}} )^{η/2} + (1 − n_{j+1}^{− \frac{λ}{λ_{d}} (1+O(_{\frac{1}{(log n_{j})^{1/2}}} ))})^{[^{(\frac{n_{j}}{(log n_{j})^{2}} )}\frac{1−η}{2} ]}

≤ j^{− \frac{βη}{3}} + (1 − (j + 1)^{−β \frac{λ}{λ_{d}} (1+O( \frac{1}{(log j)^{1/2}} ))})^{j^{\frac{β(1−2η)}{2}}}
(4.12)  ≤ j^{− \frac{βη}{3}} + exp (−\frac{1}{2}j^{β(\frac{1}{2} −η− \frac{λ}{λ_{d}} +O( \frac{1}{(log j)^{1/2}} ))})

for 0 < η < 1/2 and j big enough. It is easy to see that in (4.12) selecting η > 0 as small as necessary the second term is summable in j if λ < λ_{d}/2. On the other hand, one can select a β big enough (depending on η) that the first term is summable in j. Borel-Cantelli lemma and the usual monotonicity argument results in

(4.13)  lim inf_{n→∞} \frac{ξ_{S_{d−1}}^{(2)}(n)}{log n} ≥ \frac{λ_{d}}{2}  a.s.

which combined with (4.4) implies our theorem. □

Proof of Theorem 1.5. Recall that

S_{d−2} = {x ∈ Z_{d} : a_{1}x_{1} + a_{2}x_{2} + ... + a_{d}x_{d} = 0, b_{1}x_{1} + b_{2}x_{2} + ... + b_{d}x_{d} = 0}

with integers a_{i}, b_{j}. Without loss of generality, we may assume that the largest common divisor of both (a_{1}, …, a_{d}) and (b_{1}, …, b_{d}) is equal to 1 and (a_{1}, …, a_{d}) ≠ (b_{1}, …, b_{d}).

Define a two-dimensional random walk associated with our d-dimensional random walk with steps

Ỹ_{i} = (a_{r}, b_{r}) if X_{i} = e_{r}, r = 1, 2, …, d,
Ỹ_{i} = −(a_{r}, b_{r}) if X_{i} = −e_{r}, r = 1, 2, …, d.

Note that, as in the previous theorem, these values are not necessarily distinct. In that case we sum up the probabilities 1/(2d) according to their multiplicity.

Then

Z̃_{n} = Ỹ_{1} + … + Ỹ_{n}, n = 1, 2, …

is a two-dimensional symmetric recurrent (possibly periodic) random walk in Z_{2} with finite variance with the property S_{n} ∈ S_{d−2} if and only if Z̃_{n} = 0. Let

V^{S_{d−2}}(n) = #{i : 1 ≤ i ≤ n, S_{i} ∈ S_{d−2}}

and

ξ_{Z}(0, n) = #{i : 1 ≤ i ≤ n, Z̃_{i} = 0},

the local time of {Z̃} at 0 up to time n.

Then we have V^{S_{d−2}}(n) = ξ_{Z}(0, n).

Now we define an aperiodic random walk with the same property. If {Z̃_{n}} is aperiodic, then let Ẑ_{n} = Z̃_{n}, n = 0, 1, … In the case when {Z̃_{n}} happens to be periodic, then following Spitzer [10], pp. 65-66 construct an aperiodic walk in Z_{2} as follows. The steps (a_{r}, b_{r}), r = 1, …, d are supported on a proper subgroup G ⊂ Z_{2}. Since under our assumptions a_{r} ≠ b_{r} at least for one r, the subgroup is two-dimensional, i.e. there exists a basis of G consisting of two vectors, say u, v. Let (α_{r}, β_{r}) be the coordinates of (a_{r}, b_{r}) related to this basis, i.e. (a_{r}, b_{r}) = α_{r}u + β_{r}v. Now define a new two-dimensional random walk with steps

Ŷ_{i} = (α_{r}, β_{r}) if Ỹ_{i} = (a_{r}, b_{r}), r = 1, 2, …, d,
Ŷ_{i} = −(α_{r}, β_{r}) if Ỹ_{i} = −(a_{r}, b_{r}), r = 1, 2, …, d.

Then (cf. [10], p. 65)

Ẑ_{n} = Ŷ_{1} + … + Ŷ_{n}, n = 1, 2, …

is a symmetric recurrent aperiodic random walk in Z_{2}. Obviously Z̃_{n} = 0 if and only if Ẑ_{n} = 0. Hence we have also V^{S_{d−2}}(n) = ξ_{Z}(0, n) with obvious notation for the local time of {Ẑ}.

Now we prove the upper bound in Theorem 1.5, i.e.

(4.14)  lim sup_{n→∞} \frac{ξ_{S_{d−2}}^{(d)}(n)}{log log n} ≤ λ_{d}  a.s.

In the proof we follow the same lines as in the proof of Theorem 1.4. Choose λ > λ_{d} and ε > 0 such that δ = λ/λ_{d} − 1 − ε > 0. Then using (1.13), Fact 5 and Fact 10 we can see as in (4.3) that for n big enough,

P (ξ_{S_{d−2}}^{(d)}(n) > u) ≤ (log n)^{1+ε}P (ξ^{(d)}(0, n) ≥ u) + P(V^{(d−2)}(n) > (log n)^{1+ε})
≤ (log n)^{1+ε}P(ξ^{(d)}(0, ∞) > u) + P(ξ_{Z}(0, n) > (log n)^{1+ε})
≤ (log n)^{1+ε} exp (−\frac{u}{λ_{d}} ) + exp(−(log n)^{ε/2}).

Hence choosing n_{j} = [exp (j^{2/δ})],

P(ξ_{S_{d−2}}^{(d)}(n_{j+1}) ≥ λ log log n_{j}) ≤ C(log n_{j})^{−δ} = \frac{C}{j^{2}} .

Borel-Cantelli lemma and the usual monotonicity argument yields (4.14), since ε can be arbitrary small.

Now we prove the lower bound

(4.15)  lim inf_{n→∞} \frac{ξ_{S_{d−2}}^{(d)}}{log log n} ≥ λ_{d}  a.s.

Here again we follow the proof of Theorem 1.4. Let λ < λ_{d} and n_{j} = [exp(j^{2/(1−β)})] with some λ/λ_{d} < β < 1 and define

(4.16) η_{0}^{j} := 0,  η_{k}^{j} := min{i > η_{k−1}^{j} + [(log n_{j})^{2}] : S_{i} ∈ S_{d−2}},  Y_{k}^{j} := S_{η_{k}^{j}}.

Furthermore, let ν_{j} be the largest integer N for which

η_{N}^{j} + [(log n_{j})^{2}] ≤ n_{j}. (4.17)

Since {Ẑ} is a two-dimensional random walk for which Lemma 2.4 holds, choosing a = [(log n_{j})^{2}], f(n_{j}) = (log n_{j})^{β} there, we get

P(ν_{j} ≤ (log n_{j})^{β}) ≤ \frac{c log log n_{j}}{(log n_{j})^{1−β}} .

Similarly to (4.5), the probability that a point will be visited at least λ log log n_{j+1} times within [(log n_{j})^{2}] steps is greater than

(1 − γ_{d} + O (\frac{1}{(log n_{j})^{1/2}} ))^{[λ log log n_{j+1}]} = (log n_{j+1})^{−λ/λ_{d}}(1 + o(1)).

Define the events

A_{k}^{j} = {ξ^{(d)}(S_{η_{k}^{j}}, η_{k}^{j} + [(log n_{j})^{2}]) − ξ^{(d)}(S_{η_{k}^{j}}, η_{k}^{j}) < λ log log n_{j+1}},

then clearly A_{k}^{j} are independent in k for fixed j, and have the same probability, hence we have for j big enough

P(A_{k}^{j}) ≤ 1 − \frac{1 + o(1)}{(log n_{j+1})^{λ/λ_{d}}} .

Moreover,

P(ξ_{S_{d−2}}^{(d)}(n_{j}) < λ log log n_{j+1}) ≤ (1 − \frac{1 + o(1)}{(log n_{j+1})^{λ/λ_{d}}} )^{(log n_{j})^{β}} + \frac{c log log n_{j}}{(log n_{j})^{1−β}}

≤ exp (−(1/2)(log n_{j})^{β−λ/λ_{d}}) + \frac{c log log n_{j}}{(log n_{j})^{1−β}} .

This is summable in j, hence Borel–Cantelli lemma and monotonicity imply (4.15). This together with (4.14) completes the proof of Theorem 1.5. □

Proof of Theorem 1.6. First we prove the lower bound, i.e.

(4.18)  2λ_{d} ≤ lim inf_{n→∞} \frac{ξ_{B(r_{n})}^{(d)}(n)}{log r_{n}}  a.s.

For any δ > 0 and large enough n we have r_{n}^{2−δ} ≤ n and by the law of the iterated logarithm (2.1) we conclude that for any δ > 0, {S_{i}, 1 ≤ i ≤ r_{n}^{2−δ} ≤ n} are all in B(r_{n}) for large n with probability one, hence by Theorem F we have for any η and large enough n,

ξ_{B(r_{n})}^{(d)}(n) ≥ ξ^{(d)}(r_{n}^{2−δ}) ≥ (1 − η)λ_{d} log r_{n}^{2−δ} = (1 − η)(2 − δ)λ_{d} log r_{n} a.s.

Since η and δ are arbitrary, (4.18) follows.

To show the upper bound

(4.19)  lim sup_{n→∞} \frac{ξ_{B(r_{n})}^{(d)}(n)}{log r_{n}} ≤ 2λ_{d}  a.s.,

note that by (2.2) for any ε > 0 and large n the random walk does not hit points in the ball B(r_{n}) after r_{n}^{2+ε} steps with probability one. Hence by Theorem F for large n

ξ_{B(r_{n})}^{(d)}(n) ≤ ξ^{(d)}(r_{n}^{2+ε}) ≤ (2 + 2ε)λ_{d} log r_{n} a.s.

Since ε is arbitrary, (4.19) follows.

This completes the proof of Theorem 1.6. □

5. Further consequences and questions.

5.1 A special one dimensional walk.

Consider a simple symmetric walk in Z_{2}

S_{n}^{(2)} = ∑_{k=1}^{n} X_{k} = (S_{n,1}, S_{n,2}) = (∑_{k=1}^{n} X_{k,1}, ∑_{k=1}^{n} X_{k,2})

Clearly the components X_{k,1} and X_{k,2} are dependent. However it is easy to check that the pair

Y_{k,1} = X_{k,1} + X_{k,2}, Y_{k,2} = X_{k,1} − X_{k,2}

are independent, with common distribution

P(Y_{k,1} = ±1) = P(Y_{k,2} = ±1) = \frac{1}{2}.

Consequently,

V_{n} = ∑_{k=1}^{n} Y_{k,1} = S_{n,1} + S_{n,2} and Z_{n} = ∑_{k=1}^{n} Y_{k,2} = S_{n,1} − S_{n,2}, n = 1, 2 …

are independent simple symmetric random walks.

Consider now the consecutive return times of {Z_{n}} to zero, that is to say let

ρ_{0} := 0, ρ_{k} := min{i > ρ_{k−1} : Z_{i} = 0}, k = 1, 2, …

Now clearly our two-dimensional walk S_{n}^{(2)} is on the line x_{1} −x_{2} = 0 if an only if Z_{n} = 0, that is to say at the steps ρ_{i}, i = 1, 2, … Introducing the i.i.d. sequence U_{i} = V_{ρ_{i}} −V_{ρ_{i−1}} i = 1, 2... we get a one-dimensional random walk

R_{n} = V_{ρ_{n}} = ∑_{i=1}^{n} U_{i}, n = 1, 2, …

For this walk we have from Spitzer [10], p. 89 that

P(U_{1} = 0) = 1 − \frac{2}{π} ,

P(U_{1} = 2k) = \frac{2}{π} \frac{1}{4k^{2} − 1}, k = ±1, ±2, …

R_{n} is in the domain of attraction of the Cauchy distribution, so we will refer to it as Cauchy walk. Some properties of the Cauchy walk was investigated in Taylor [11]. Here we want to point out that our results have some implications for the local time of the Cauchy walk. As

R_{n} = 2k ⇔ S_{ρ_{n}}^{(2)} = (k, k),

we conclude that for the local time of R_{n}

η(2ℓ, n) := #{i : 1 ≤ i ≤ n, R_{i} = 2ℓ} = ξ^{(2)}((ℓ, ℓ), ρ_{n}). (5.1)

Thus from (5.1) we get that

η(n) = max_{y} η(y, n) = ξ_{L}^{(2)}(ρ_{n})

where L = L(1, −1) is the line x_{1} − x_{2} = 0.

Taking into account the well-known fact that log ρ_{n} ∼ 2 log n (see e.g. [9], p. 115) a simple application of our Theorem 1.1 implies that for the maximal local time of the Cauchy walk we have

\frac{1}{2π} ≤ lim inf_{n→∞} \frac{η(n)}{(log n)^{2}} ≤ lim sup_{n→∞} \frac{η(n)}{(log n)^{2}} ≤ \frac{2}{π} a.s.

5.2 Open questions.

1./ Our methods are not powerful enough to get exact constants in Theorems 1.1, 1.2. We don’t have any conjecture whether in these theorems the lim inf and lim sup can be replaced by limit and if so what would be the actual value of those limits. In Theorem 1.3 even the exact order escapes us.

2./ In Theorems 1.1, 1.4 and 1.5 we have lines and subspaces going through the origin. These results remain valid for lines and subspaces having a fixed distance from the origin. However it would be interesting to investigate the maximal local time on lines and subspaces having a distance from the origin d(n) → ∞.

3./ In our theorems we have balls centered at the origin. One might be interested in the maximal local time in balls having a center with distance d(n) → ∞ from the origin.

4./ We discussed subspaces and balls in the theorems but other sets would be just as interesting to be investigated. One possibility would be to investigate angular domains, cones and wedges. E.g. in Theorem 1.4 if we take the wedge in between two planes, then we have to have a transition from \frac{λ_{d}}{2} to λ_{d} as the angle of the wedge increases from 0 → 2π. Similarly we might ask that if in Theorem 1.5 we replace the line with a cone (centered at the origin) what kind of transition happen as the cone gets wider, that is to say how does the order change from log log n to log n as the angle of the cone changes form 0 → π (from the line to Z_{3}.) Similar questions can be asked in two dimension as well but those would be more interesting if the exact constant was known in Theorem 1.1.

5./ One might ponder that how important is the actual shape of the subset on which the maximum is taken. E.g. it would be interesting to have results on the maximal local time on sets which are not specified in shape just their size are given and of course one has to ensure that they are located close enough to the origin that visits should occur.

6./ All our theorems are about simple symmetric walk. We might ask how important is this restriction. Theorem C is valid for a much wider class of random walks. So we might ask whether our theorems remain valid for aperiodic random walks under certain moment conditions. In Theorem C all the moments has to exist, maybe somewhat less precise results can be ensured even if only the second moment exists. Is it possible to say anything without second moment?

References

[1] Auer, P.: The circle homogenously covered by random walk on Z_{2}. Statist. and Probab. Lett. 9 (1990), 403–407.

[2] Chung, K.L. and Hunt, C.A.: (1949) On the zeros of ∑_{1}^{n} ±1. Annals of Math. 50, 385–400.

[3] Csáki, E. and Földes, A.: How big are the increments of the local time of a recurrent random walk? Z. Wahrsch. verw. Gebiete 65 (1983), 307–322.

[4] 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.

[5] Dembo, A., Peres, Y., Rosen, J. and Zeitouni, O.: Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk. Acta Mathematica 186 (2001), 1–30.

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

[7] 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.

[8] Marcus, M. and Rosen, J.: Laws of the iterated logarithm for the local times of recurrent random walks on Z_{2} and of Lévy processes and random walks in the domain of attraction of Cauchy random variables. Ann. Inst. H. Poincaré Prob. Stat. 30 (1994), 467–499.

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

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

[11] Taylor, H.M.: The fundamental matrix for a certain random walk. J. Appl. Probab. 36 (1999), 320–333.