On the behavior of random walk around heavy points

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: Consider a symmetric aperiodic random walk in Z^{d}, d ≥ 3. There are points (called heavy points) where the number of visits by the random walk is close to its maximum. We investigate the local times around these heavy points and show that they converge to a deterministic limit as the number of steps tends to infinity.

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

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

Running title: Random walk around heavy points

1. Introduction and main results

Consider a random walk {S_{n}}_{n=1}^{∞} starting at the origin on the d-dimensional 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} = x) = p(x), x ∈ Z^{d}.  (1.1)

The random walk is called simple symmetric if p(e_{i}) = 1/(2d), i = 1, …, 2d, where e_{1}, …, e_{d} is a system of orthogonal unit vectors in Z^{d} and e_{i} = −e_{i−d}, i = d + 1, …, 2d.

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

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

Denote by Q the covariance matrix of X_{1}, and let |Q| be its determinant and let Q^{−1} its inverse. Let

∥x∥^{2} := xQ^{−1}x.  (1.2)

For simple symmetric random walk ∥x∥^{2} = |x|^{2} := x_{1}^{2} + ⋯ + x_{d}^{2}, where x = (x_{1}, …, x_{d}). Recall the following definitions and basic properties from Spitzer [9]. A random walk is aperiodic if for

R^{+} = {x ∈ Z^{d} : P(S_{n} = x) > 0 for some n ≥ 0}

we have

{x : x = y − z, for some y ∈ R^{+}, z ∈ R^{+}} = Z^{d}.

A random walk is strongly aperiodic if for each x ∈ Z^{d}

{y : y = x + z, where p(z) > 0} = Z^{d}.

We assume throughout the paper that the random walk is aperiodic (but not necessarily strongly aperiodic) and symmetric, i.e. p(x) = p(−x), x ∈ Z^{d}.

For d ≥ 3 the random walk is transient, i.e.

γ := P(S_{i} ≠ 0, i = 1, 2, …) > 0.  (1.3)

Define

γ_{x} := P(S_{i} ≠ x, i = 1, 2, …), x ∈ Z^{d}.  (1.4)

We shall impose the following moment conditions:

∑_{x∈Z^{d}} |x|^{2}p(x) < ∞,  d = 3,  (1.5)
∑_{x∈Z^{d}} |x|^{2} log(|x| + 1)p(x) < ∞,  d = 4,  (1.6)
∑_{x∈Z^{d}} |x|^{d−2}p(x) < ∞,  d ≥ 5,  (1.7)

where |x| is the Euclidean distance.

The Green function is defined by

G(x) := ∑_{n=0}^{∞} P(S_{n} = x), x ∈ Z^{d}.  (1.8)

We have the identities

γ = \frac{1}{G(0)}, 1 − γ_{x} = \frac{G(x)}{G(0)}, x ≠ 0.

We need the following asymptotic property for the Green function in the case of aperiodic random walk with mean 0, satisfying the moment conditions (1.5), (1.6), (1.7) for d ≥ 3.

G(x) ∼ c_{d}|Q|^{−1/2}∥x∥^{2−d}, |x| → ∞  (1.9)

with some constant c_{d}. See Spitzer [9], p. 308 for d = 3, p. 339, Problem 5 for d > 3, or Uchiyama [10] for strongly aperiodic case and use Spitzer’s trick ([9], p. 310) to reduce the aperiodic case to strongly aperiodic case. For simple random walk see Révész [8].

In this paper we are interested in studying local times of the random walk defined by the number of visits as follows.

ξ(x, n) := ∑_{k=1}^{n} I{S_{k} = x}, n = 1, 2, …, x ∈ Z^{d},  (1.10)

where I{A} denotes the indicator of A.

Since the random walk is transient for d ≥ 3, typically there is only a finite number of visits to a fixed site, even for infinite time. More precisely we have the distribution

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

Cf. Erdős and Taylor [4] for simple random walk. The general case is similar.

There are however (random) points where the random walk accumulates a higher number of visits. Consider the maximal local time

ξ(n) := max_{x∈Z^{d}} ξ(x, n), n = 1, 2, …  (1.12)

and also

η(n) := max_{0≤j≤n} ξ(S_{j}, ∞), n = 1, 2, …  (1.13)

Erdős and Taylor [4] proved for simple random walk and d ≥ 3

lim_{n→∞} \frac{ξ(n)}{log n} = λ := −\frac{1}{log(1 − γ)}  a.s.  (1.14)

Following the proof of Erdős and Taylor, without any new idea, one can prove that (1.14) holds for general aperiodic random walk and also

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

For general treatment of similar strong theorems for local and occupation times see [3]. (1.14) means that there are sites where the local time up to time n is around λ log n.

These will be called heavy points. We are interested in the problem what happens around these heavy points. We may ask whether it is possible that in a close neighborhood of a heavy point there is another heavy point? Or an empty point (not visited at all up to time n)? We shall see that the answers for both questions happen to be negative.

In [2] we investigated the joint asymptotic behavior of local times of two neighboring sites for simple random walk and found that the vector

(\frac{ξ(x, n)}{log n}, \frac{ξ(x + e_{1}, n)}{log n})

is essentially in the domain

{y ≥ 0, z ≥ 0 : −(y + z) log(y + z) + y log y + z log z − (y + z) log α ≤ 1},

where

α := \frac{1 − γ}{2 − γ} .

One can see that the only point in this domain with y = λ is z = λ(1 − γ), which tells us that if a point is heavy, i.e. its local time is around λ log n, then the local time of any of its neighbors should be around λ(1 − γ) log n, i.e. cannot fluctuate too much, at least asymptotically. We say that the local time around a heavy point is asymptotically deterministic. Our concern is to investigate this phenomenon further and determine the asymptotic value of local times of sites x with ∥x∥ ≤ r_{n}, where r_{n} may tend to infinity at a certain rate.

Define

m_{x} = \{ \begin{matrix}1  if x = 0, \\ \frac{(1−γ_{x})^{2}}{1−γ} if x ≠ 0. \end{matrix}  (1.16)

m_{x} is, in fact, the expectation of the local time at x between two consecutive returns to zero (see Remark 2.1).

We shall consider the "balls" (which are, in fact, ellipsoids in Euclidean space)

B(r) = {x : ∥x∥ ≤ r} ,  (1.17)

where ∥x∥ is defined by (1.2).

Theorem 1.1. 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}  (1.18)
lim_{n→∞} β_{n} = 0,  lim_{n→∞} δ_{n}r_{n}^{2d−4} = 0.  (1.19)

Define the random set of points

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

Then we have for symmetric aperiodic random walk

lim_{n→∞} sup_{z∈A_{n}} sup_{x∈B(r_{n})} |\frac{ξ(z + x, n)}{m_{x}λ log n} − 1| = 0 a.s.  (1.21)

Theorem 1.2. 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}  (1.22)
lim_{n→∞} β_{n} = 0,  lim_{n→∞} δ_{n}r_{n}^{2d−4} = 0.  (1.23)

Define the random set of indices

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

Then we have for symmetric aperiodic random walk

lim_{n→∞} sup_{j∈B_{n}} sup_{x∈B(r_{n})} |\frac{ξ(S_{j} + x, ∞)}{m_{x}λ log n} − 1| = 0 a.s.  (1.25)

Remark 1.1 For a given ω, A_{n} or B_{n} can be empty. In this case sup_{z∈A_{n}} or sup_{j∈B_{n}} is automatically considered to be 0.

Corollary 1.1 Let A ⊂ Z^{d} be a fixed set.

(i) If d ≥ 5 and z_{n} ∈ A_{n}, then

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

(ii) If d ≥ 3 and j_{n} ∈ B_{n}, then

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

From our Theorems it is obvious that the critical case is around r_{n} ∼ (log n)^{1/(2d−4)}. It follows that for smaller r_{n} the ball S_{j} + B(r_{n}) is completely covered for j ∈ B_{n} with probability 1. We have the following Corollary.

Corollary 1.2 For j ∈ B_{n} let R(n, j) denote the largest number such that S_{j} +B(R(n, j)) is completely covered by the random walk S_{0}, S_{1}, S_{2}, …, i.e. ξ(S_{j} + x, ∞) > 0, x ∈ B(R(n, j)). Then for any ε > 0 we have R(n, j) ≥ (log n)^{(1−ε)/(2d−4)} almost surely.

We conjecture that for j ∈ B_{n} we have R(n, j) ≤ (log n)^{(1+ε)/(2d−4)}. Our next result is one step in this direction, showing that in Theorems 1.2 the power 1/(2d−4) of log n cannot be improved in general.

Theorem 1.3. For simple symmetric random walk let {x_{n}} be a sequence such that |x_{n}| ∼ c(log n)^{1/(2d−4)} for some c > 0. Then with probability one there exist infinitely many n such that

ξ(S_{n}, ∞) ≥ λ (log n + (\frac{d − 4}{d − 2} − ε) log log n) , ξ(S_{n} + x_{n}, ∞) = 0.

Consequently, n ∈ B_{n} and R(n, n) ≤ c(log n)^{1/(2d−4)} infinitely often with probability one.

2. Preliminary facts and results

First we present some more notations. For x ∈ Z^{d} let T_{x} be the first hitting time of the point x, i.e. T_{x} = min{i ≥ 1 : S_{i} = x} with the convention that T_{x} = ∞ if there is no i with S_{i} = x. Denote T_{0} = T.

Introduce further

q_{x} := P(T < T_{x}),  (2.1)
s_{x} := P(T_{x} < T).  (2.2)

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

Now we give the joint distribution of ξ(0, ∞) and ξ(x, ∞) in the following form.

Lemma 2.1. For x ≠ 0, v < log(1/(1 − γ)), k = 0, 1, 2, …

E(e^{vξ(x,∞)}; ξ(0, ∞) = k) = (q_{x} + \frac{s_{x}^{2}e^{v}}{1 − q_{x}e^{v}} )^{k} (1 − q_{x} − s_{x}) (1 + \frac{s_{x}e^{v}}{1 − q_{x}e^{v}} )  (2.3)
= γ(1 − γ)^{k} (φ(v))^{k} ψ(v),  (2.4)

where

φ(v) := \frac{1 − \frac{(1−γ)^{2}−(1−γ_{x})^{2}}{γ(1−γ)} (e^{v} − 1)}{1 − \frac{1−γ−(1−γ_{x})^{2}}{γ} (e^{v} − 1)},  (2.5)

ψ(v) := \frac{1 − \frac{γ_{x}−γ}{γ} (e^{v} − 1)}{1 − \frac{1−γ−(1−γ_{x})^{2}}{γ} (e^{v} − 1)},  (2.6)

Proof. Observe that

P (∑_{n=1}^{T} I\{S_{n} = x\} = j, T < ∞) = \{ \begin{matrix}q_{x} & if j = 0, \\ s_{x}^{2}q_{x}^{j−1} & if j = 1, 2, ... \end{matrix}  (2.7)

and

P (∑_{n=1}^{T} I\{S_{n} = x\} = j, T = ∞) = \{ \begin{matrix}1 − q_{x} − s_{x} & if j = 0, \\ s_{x}(1 − q_{x} − s_{x})q_{x}^{j−1} & if j = 1, 2, ... \end{matrix}  (2.8)

Obviously

ξ(x, ∞) = Z_{1} + … + Z_{ξ(0,∞)} + Ẑ,

where Z_{1}, …, Z_{ξ(0,∞)} are the local times of x between consecutive returns to 0 and Ẑ is the local time of x after the last return to zero. Hence (2.3) follows from (2.7) and (2.8). (2.4) can be obtained by using

q_{x} = 1 − \frac{γ}{1 − (1 − γ_{x})^{2}} ,  (2.9)
s_{x} = (1 − γ_{x})(1 − q_{x}).  (2.10)

(Cf. [1] or [8] for simple random walk, the general case being similar).

Remark 2.1 It is easy to see that our condition v < log(1/(1 − γ)) implies q_{x}e^{v} < 1, needed to obtain (2.3). Furthermore

φ(v) = E (e^{v ∑_{n=1}^{T} I{S_{n}=x}} | T < ∞) ,
ψ(v) = E (e^{v ∑_{n=1}^{T} I{S_{n}=x}} | T = ∞)

and

m_{x} = E (∑_{n=1}^{T} I{S_{n} = x} | T < ∞) .

Further properties of q_{x} and s_{x} for simple symmetric random walk are given in the next Lemma.

Lemma 2.2. For simple symmetric random walk and x ∈ Z^{d}

γ_{x} ≥ γ,  (2.11)
\frac{1 − γ}{2 − γ} ≤ q_{x} ≤ 1 − γ,  (2.12)
1 − q_{x} − s_{x} ≥ \frac{γ}{2 − γ} ,  (2.13)
q_{x}(n) := P(T < min(n, T_{x})) = q_{x} + \frac{O(1)}{n^{d/2−1}} .  (2.14)

Proof. For (2.11) see [1], Lemma 2.4 and for (2.14) see [1], Lemma 2.5. (2.12) and (2.13) can be easily obtained from (2.9), (2.10) and (2.11).

The next result gives an estimation of φ and ψ, where the error term is uniform in x.

Lemma 2.3. For log(1 − γ(1 − γ)) < v < log(1 + γ(1 − γ)) we have

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

where O is uniform in x,

ψ(v) ≤ \frac{1 + |e^{v} − 1|}{1 − |e^{v} − 1|/γ} .  (2.16)

Proof. Write

φ(v) = \frac{1 − u}{1 − y}

with

u = \frac{(1 − γ)^{2} − (1 − γ_{x})^{2}}{γ(1 − γ)} (e^{v} − 1), y = \frac{1 − γ − (1 − γ_{x})^{2}}{γ} (e^{v} − 1).

Then it is easy to see that

y − u = m_{x}(e^{v} − 1),

and

|u| ≤ \frac{|e^{v} − 1|}{γ(1 − γ)}, |y| ≤ \frac{|e^{v} − 1|}{γ(1 − γ)}.

By Taylor series

log \frac{1 − u}{1 − y} = log(1 − u) − log(1 − y) = y − u + \frac{y^{2} − u^{2}}{2} + \frac{y^{3} − u^{3}}{3} + …

= (y − u) (1 + \frac{y + u}{2} + \frac{y^{2} + uy + u^{2}}{3} + …) .

Since e^{v} − 1 = v + O(v^{2}), we have

|log \frac{1 − u}{1 − y} − m_{x}(e^{v} − 1)| ≤ m_{x}|e^{v} − 1| (\frac{|e^{v} − 1|}{γ(1 − γ)} + (\frac{|e^{v} − 1|}{γ(1 − γ)})^{2} + …) = m_{x}O(v^{2}),

where O is independent of x. Hence (2.15) follows. (2.16) is obvious.

3. Proof of Theorem 1.2

Observe that k_{n} ∼ λ log n. Let n_{ℓ} = [e^{ℓ}], ξ(z) = ξ(z, ∞) and define the events

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

P ( ⋃_{j=0}^{n_{ℓ+1}} A_{j}) ≤ ∑_{j=0}^{n_{ℓ+1}} P(A_{j}) ≤ ∑_{j=0}^{n_{ℓ+1}} ∑_{x∈B(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 have 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_{n_{ℓ}} − 1. Using exponential Markov inequality, Lemma 2.1, 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}}γ^{2}(1 − γ)^{k_{1}+k_{2}}ψ^{2}(v)e^{−v(1+ε)m_{x}k_{n_{ℓ}}}
= γ^{2}ψ^{2}(v)e^{−v(1+ε)m_{x}k_{n_{ℓ}}} ∑(φ(v)(1 − γ))^{k_{1}+k_{2}}
= γ^{2}ψ^{2}(v)e^{−v(1+ε)m_{x}k_{n_{ℓ}}}(φ(v)(1 − γ))^{k_{n_{ℓ}}}
× (\frac{k_{n_{ℓ}}}{φ(v)(1 − γ)(1 − φ(v)(1 − γ))} + \frac{1}{(1 − φ(v)(1 − γ))^{2}} ) .

By (2.15) we obtain for all j

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

Choose v_{0} > 0 small enough such that

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

Using x ∈ B(r_{n_{ℓ+1}}) and (1.9) we get

m_{x}k_{n_{ℓ}} = \frac{(1 − γ_{x})^{2}}{1 − γ} (λ log n_{ℓ}(1 − δ_{n_{ℓ}})) ≥ \frac{C_{1}(1 − δ_{n_{ℓ}}) log n_{ℓ}}{∥x∥^{2d−4}} ≥ \frac{C_{1}(1 − δ_{n_{ℓ}}) log n_{ℓ}}{r_{n_{ℓ+1}}^{2d−4}} ,

where here and in the sequel C_{1}, C_{2}, … will 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}))}(1 − γ)^{k_{n_{ℓ}}}
≤ C_{2}k_{n_{ℓ}} exp (−(1 − δ_{n_{ℓ}}) log n_{ℓ} (\frac{C_{3}}{r_{n_{ℓ+1}}^{2d−4}} + 1)) .

Hence

∑_{j=0}^{n_{ℓ+1}} ∑_{x∈B(r_{n_{ℓ+1}})} P(A_{j}^{(x)}) ≤ C_{4}n_{ℓ+1}r_{n_{ℓ+1}}^{d}k_{n_{ℓ}} exp (−(1 − δ_{n_{ℓ}}) log n_{ℓ} (\frac{C_{3}}{r_{n_{ℓ+1}}^{2d−4}} + 1))

≤ C_{4} \frac{n_{ℓ+1}}{n_{ℓ}} k_{n_{ℓ}}r_{n_{ℓ+1}}^{d} exp (−\frac{C_{3} log n_{ℓ}}{r_{n_{ℓ+1}}^{2d−4}} + δ_{n_{ℓ}} log n_{ℓ})

= C_{4} \frac{n_{ℓ+1}}{n_{ℓ}} k_{n_{ℓ}}r_{n_{ℓ+1}}^{d} exp (−\frac{log n_{ℓ}}{r_{n_{ℓ}}^{2d−4}} (C_{3} (\frac{r_{n_{ℓ}}}{r_{n_{ℓ+1}}} )^{2d−4} − δ_{n_{ℓ}}r_{n_{ℓ}}^{2d−4}))

≤ C_{4} \frac{n_{ℓ+1}}{n_{ℓ}} k_{n_{ℓ}}r_{n_{ℓ+1}}^{d} exp (−C_{5} \frac{log n_{ℓ}}{r_{n_{ℓ}}^{2d−4}} ) ≤ C_{6}(log n_{ℓ})^{3− \frac{C_{7}}{βn_{ℓ}}} ,

where in the last two lines we used the conditions of the Theorem for r_{n} and δ_{n}. Consequently

P( ⋃_{j=0}^{n_{ℓ+1}} A_{j}) ≤ ∑_{j=0}^{n_{ℓ+1}} ∑_{x∈B(r_{n_{ℓ+1}})} P(A_{j}^{(x)}) ≤ C_{6}ℓ^{3− \frac{C_{7}}{βn_{ℓ}}} ≤ \frac{C_{6}}{ℓ^{2}}

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

Let now n_{ℓ} ≤ n < n_{ℓ+1} and x ∈ B(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}.  (3.1)

The lower bound is similar, with slight modifications. We call S_{j} new if S_{i} ≠ S_{j}, i = 1, 2, …, j − 1. Define the events

D_{j} = \{ξ(S_{j}) ≥ k_{n_{ℓ}}, sup_{x∈B(r_{n_{ℓ+1}})} (1 − \frac{ξ(S_{j} + x)}{m_{x}k_{n_{ℓ+1}}}) ≥ ε\} ,

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

Observe that

⋃_{{j:0≤j≤n_{ℓ+1}}} D_{j} = ⋃_{{j:0≤j≤n_{ℓ+1}, S_{j} new}} D_{j}.

Considering again the forward random walk, we have

ξ(S_{j}) = ξ”(0) + 1, ξ(S_{j} + x) ≥ ξ”(x).

Hence by Markov’s inequality

P(D_{j}^{(x)}) ≤ ∑_{k=k_{n_{ℓ}}−1}^{∞} P(ξ”(0) = k, ξ”(x) ≤ (1 − ε)m_{x}k_{n_{ℓ+1}})

≤ ∑_{k=k_{n_{ℓ}}−1}^{∞}(φ(−v)(1 − γ))^{k}ψ(−v) exp(v(1 − ε)m_{x}k_{n_{ℓ+1}})

≤ \frac{ψ(−v)}{(1 − γ)φ(−v)(1 − (1 − γ)φ(−v))}((1 − γ)φ(−v))^{k_{n_{ℓ}}}e^{v(1−ε)m_{x}k_{n_{ℓ+1}}}.

Proceeding as above we finally conclude after somewhat simpler calculations than the previous one, that for large enough n, ξ(S_{j}) ≥ k_{n} implies ξ(S_{j} + x) ≥ (1 − ε)m_{x}k_{n}.

This, combined with (3.1) completes the proof of Theorem 1.2.

4. Proof of Theorem 1.1

Lemma 4.1. Let d ≥ 5, \frac{2}{d−2} < α < 1, j ≤ n − n^{α}, |x| ≤ log n. 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. The proof is essentially the same as that of Theorem 1 (iii) in Erdős and Taylor [5].

Let

n_{k+1} = n_{k} + [\frac{1}{2}n_{k}^{α}] .

A_{k} = ⋃_{j≤n_{k}}  ⋃_{ℓ≥n_{k}+[ \frac{1}{2} n_{k−1}^{α}]} ⋃_{x∈B(log n_{k+1})}\{S_{ℓ} − S_{j} = x\}.

For aperiodic random walk we have (cf. Jain and Pruitt [6])

P(S_{n} = x) ≤ C_{8}n^{−d/2}  (4.1)

for all x ∈ Z^{d} and n ≥ 1 with some constant C_{8}.

Using the fact that B(log n_{k+1}) contains less than C_{9}(log n_{k+1})^{d} points,

P(A_{k}) ≤ C_{9}(log n_{k+1})^{d} ∑_{j=0}^{n_{k}} ∑_{ℓ=n_{k}+[ \frac{1}{2} n_{k−1}^{α}]}^{∞} \frac{C_{8}}{(ℓ − j)^{d/2}}

≤ ∑_{j=0}^{n_{k}} \frac{C_{10}(log n_{k+1})^{d}}{(n_{k} + [\frac{1}{2}n_{k−1}^{α}] − j)^{d/2−1}} ≤ \frac{C_{10}(log n_{k+1})^{d}}{n_{k−1}^{α(d/2−2)}} ≤ \frac{C_{10}(log n_{k−1})^{d}}{n_{k−1}^{α(d−4)/2}} .  (4.2)

We will show now that ∑_{k} P(A_{k}) converges.

∑_{n=1}^{∞} \frac{(log n)^{d}}{n^{α(d−2)/2}} ≥ ∑_{k} ∑_{n=n_{k}+1}^{n_{k+1}} \frac{(log n)^{d}}{n^{α(d−2)/2}} ≥ C_{11} ∑_{k} \frac{n_{k+1} − n_{k}}{n_{k+1}^{α(d−2)/2}} (log n_{k+1})^{d}

≥ C_{11} ∑_{k} \frac{\frac{1}{2}n_{k}^{α}}{n_{k+1}^{α(d−2)/2}} (log n_{k+1})^{d} = C_{12} ∑_{k} \frac{(log n_{k+1})^{d}}{n_{k+1}^{α(d−4)/2}} (\frac{n_{k}}{n_{k+1}} )^{α} . (4.3)

Observe that

(\frac{n_{k}}{n_{k+1}} )^{α} = (\frac{n_{k}}{n_{k} + [\frac{1}{2}n_{k}^{α}]})^{α} → 1, k → ∞.

Since

∑_{n=1}^{∞} \frac{(log n)^{d}}{n^{α(d−2)/2}}

converges, (4.2) and (4.3) imply the convergence of ∑_{k} P(A_{k}). By Borel-Cantelli lemma, if k is big enough, the tube of radius log n_{k+1} around the path {S_{j}, j = 1, 2, …, n_{k}} is disjoint from the path \{S_{ℓ}, ℓ = n_{k} + [\frac{1}{2}n_{k−1}^{α}], …\}.

To finish the proof, let

n_{k−1} < n − n^{α} ≤ n_{k}.

Then

n_{k−1} + 2 [\frac{n_{k−1}^{α}}{2} ] < n_{k−1} + n^{α} < n,

hence

n_{k} + [\frac{n_{k−1}^{α}}{2} ] < n.

Thus with probability 1 for large n the tube of radius log n around the path {S_{j}, j = 1, 2, …, n − [n^{α}]} is disjoint from the path {S_{ℓ}, ℓ = n, …}, i.e. Lemma 4.1 follows.

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

5. Proof of Theorem 1.3

First we prove

Lemma 5.1. Let A_{i}, B_{i} be events such that ∑_{i} P(A_{i}) = ∞,

P(A_{i}A_{k}) ≤ c_{1}P(A_{i})P(A_{k}),

and

P(A_{i}B_{i}) ≥ c_{2}P(A_{i})

with some constants c_{1}, c_{2} > 0. Then

P(A_{i}B_{i} i.o.) > 0.

Proof.

∑_{i} P(A_{i}B_{i}) ≥ c_{2} ∑_{i} P(A_{i}) = ∞.

On the other hand,

P(A_{i}B_{i}A_{k}B_{k}) ≤ P(A_{i}A_{k}) ≤ \frac{c_{1}}{c_{2}^{2}} P(A_{i}B_{i})P(A_{k}B_{k}),

the Lemma follows by Borel-Cantelli lemma in Spitzer [9], pp. 317.

To prove the Theorem, define the stopping times V_{j} as in Révész [7]. Let

ρ_{0}(t) = t,
ρ_{1}(t) = min{τ : τ > t, S(τ) = S(t)},
ρ_{2}(t) = min{τ : τ > ρ_{1}(t), S(τ) = S(ρ_{1}(t)) = S(t)},
…,

where here and the sequel we denote S(k) = S_{k}.

U(L, t) = \{ \begin{matrix}t + L & if ρ_{1}(t) − t > L, \\ ρ_{1}(t) + L & if ρ_{1}(t) − t ≤ L, ρ_{2}(t) − ρ_{1}(t) > L, \\ ρ_{2}(t) + L & if ρ_{1}(t) − t ≤ L, ρ_{2}(t) − ρ_{1}(t) ≤ L, ρ_{3}(t) − ρ_{2}(t) > L, \\ …, \end{matrix}

L_{k} = (log(k + 2))^{α}, (α > \frac{2}{d − 2}, k = 0, 1, 2, …)
V_{0} = 0, V_{j+1} = U(L_{j}, V_{j}), (j = 0, 1, 2, …)

V_{j+1} is the first time-point after V_{j} when the random walk has not visited S(V_{j}) during a time-interval of length L_{j}.

Let {x_{n}} be a sequence of points in Z^{d} as in Theorem 1.3 and define the events

A_{j} = {ξ(S(V_{j}), V_{j+1})−ξ(S(V_{j}), V_{j}) = ψ_{j}, ξ(S(V_{j})+x_{V_{j}}, V_{j+1})−ξ(S(V_{j})+x_{V_{j}}, V_{j}) = 0}, (5.1)
B_{j} = {ξ(S(V_{j}) + x_{V_{j}}, V_{j}) = ξ(S(V_{j}) + x_{V_{j}}, ∞) − ξ(S(V_{j}) + x_{V_{j}}, V_{j+1}) = 0},  (5.2)

where ψ_{j} = [λ(log j + log log j)].

Lemma 5.2. The events A_{j}, j = 1, 2, … are independent and

P(A_{j}) ≥ \frac{C_{13}}{j log j}  (5.3)

Proof. Since {V_{j}}_{j=1}^{∞} is a sequence of stopping times and A_{j} depends only on the random walk between V_{j} and V_{j+1}, independence follows. To show (5.3), let U_{j} := U(L_{j}, 0). Consider the random walk starting from V_{j} as a new origin. Then the original random walk in the interval (V_{j}, V_{j+1}) has the same distribution as the new random walk in (0, U_{j}). Hence

P(A_{j} | V_{j} = m) = P(ξ(0, U_{j}) = ψ_{j}, ξ(x_{m}, U_{j}) = 0).

The event {ξ(0, U_{j}) = ψ_{j}, ξ(x_{m}, U_{j}) = 0} means that there are exactly ψ_{j} excursions around 0, each of which has length less than L_{j}, none of them are visiting x_{m} and in the last section (U_{j} − L_{j}, U_{j}) the random walk starting from 0, does not visit 0 and x_{m}. Hence applying (2.14) of Lemma 2.2,

P(ξ(0, U) = ψ_{j}, ξ(x_{m}, U) = 0)
= (q_{x_{m}} + O((log j)^{−α(d/2−1)}))^{ψ_{j}} P(ξ(0, L_{j}) = 0, ξ(x_{m}, L_{j}) = 0).

Obviously

P(ξ(0, L_{j}) = 0, ξ(x_{m}, L_{j}) = 0) ≥ P(ξ(0, ∞) = 0, ξ(x_{m}, ∞) = 0) = 1 − q_{x_{m}} − s_{x_{m}}.

>From the inequalities (2.12) and (2.13) of Lemma 2.2 we can get by easy calculation that

P(ξ(0, U_{j}) = ψ_{j}, ξ(x_{m}, U_{j}) = 0) ≥ C_{14}(q_{x_{m}})^{ψ_{j}} ≥ C_{15}(1 − γ)^{ψ_{j}} (1 − \frac{(1 − γ_{x_{m}})^{2}}{1 − γ} )^{ψ_{j}} .

Since L_{j} ≥ 1, we obviously have V_{j} ≥ j, i.e. we can take m ≥ j. Since

(1 − γ)^{ψ_{j}} ≥ \frac{1}{j log j}

and (cf. (1.9))

(1 − γ_{x_{m}})^{2} ∼ C_{16}(log m)^{−1},

we have

P(A_{j} | V_{j} = m) = P(ξ(0, U_{j}) = ψ_{j}, ξ(x_{m}, U_{j}) = 0) ≥ \frac{C_{13}}{j log j} ,

with C_{13} > 0 independent of m, the lemma follows.

Lemma 5.3. Let the events A_{j}, B_{j} be defined by (5.1) and (5.2). Then

P(A_{j}B_{j}) ≥ γ^{2}P(A_{j}).  (5.4)

Proof.

P(A_{j}B_{j}) = EP(A_{j}B_{j} | S(V_{j}), S(V_{j+1}))
= E (P(A_{j} | S(V_{j}), S(V_{j+1}))P(B_{j} | S(V_{j}), S(V_{j+1}))) .

We show that

P(B_{j} | S(V_{j}), S(V_{j+1})) ≥ γ^{2}, j = 1, 2, …  (5.5)

Consider the reversed random walk before S(V_{j}), as in the the proof of Theorem 1.2, i.e. S′_{i} = S(V_{j} − i) − S(V_{j}), and its local time ξ′(x, n) and also the forward random walk starting from S(V_{j+1}), i.e. S_{i}” = S(V_{j+1} + i) − S(V_{j+1}), i = 1, 2, … and its local time ξ”(x, n). These two random walks are independent and the event B_{j} means that the first random walk S′ does not visit x_{V_{j}} (up to time V_{j}) and the second random walk S” does not visit S(V_{j}) + x_{V_{j}} − S(V_{j+1}) (for infinite time). Hence

P(B_{j} | S(V_{j}), S(V_{j+1}))
= P(ξ′(x_{V_{j}}, V_{j}) = 0, ξ”(S(V_{j}) − S(V_{j+1}) + x_{V_{j}}, ∞) = 0 | S(V_{j}), S(V_{j+1}))
≥ P(ξ′(x_{V_{j}}, ∞) = 0)P(ξ”(S(V_{j}) − S(V_{j+1}) + x_{V_{j}}, ∞) = 0 | S(V_{j}), S(V_{j+1})).

>From (2.11) of Lemma 2.2 it follows that

P(ξ′(x_{V_{j}}, ∞) = 0) ≥ γ

and similarly

P(ξ”(S(V_{j}) − S(V_{j+1}) + x_{V_{j}}, ∞) = 0 | S(V_{j}), S(V_{j+1})) ≥ γ,

hence (5.5) follows, which, in turn, implies (5.4). This proves Lemma 5.3.

Lemma 5.2 and Lemma 5.3 together imply by Lemma 5.1 that

P(A_{j}B_{j} i.o.) > 0.

Since (cf. Révész [7])

V_{j} = n_{j} ≤ O(1)j(log j)^{α} a.s.,

assuming that A_{j}B_{j} occurs, we have

ξ(S_{n_{j}}, ∞) = ξ(S(V_{j+1}), ∞) ≥ ξ(S(V_{j}), V_{j+1}) − ξ(S(V_{j}), V_{j}) ≥ ψ_{j} ≥
≥ λ log n_{j} − λα log log n_{j} + (1 − ε)λ log log n_{j} ≥
≥ λ log n_{j} + λ (\frac{d − 4}{d − 2} − ε) log log n_{j}

and also ξ(S_{n_{j}} + x_{n_{j}}, ∞) = 0. Thus we have P(D_{n} i.o.) > 0, where

D_{n} = \{ξ(S_{n}, ∞) ≥ λ (log n + (\frac{d − 4}{d − 2} − ε) log log n) , ξ(S_{n} + x_{n}, ∞) = 0\} .

Let

D̃_{n} = \{ξ(S_{n}, ∞) ≥ λ (log n + (\frac{d − 4}{d − 2} − ε) log log n) ,
ξ(S_{n} + x_{n}, ∞) − ξ(S_{n} + x_{n}, log n) = 0}.

Then we have also P(D̃_{n} i.o.) > 0 and since D̃_{n} is a tail event for the random walk, by 0-1 law we have P(D̃_{n} i.o.) = 1.

To show that also P(D_{n} i.o.) = 1, we prove the following

Lemma 5.4. For any 0 < δ < 1/2 with probability 1 there exists n_{0} such that for n ≥ n_{0} we have

ξ(S_{n} + x, n^{δ}) = 0 for all |x| ≤ log n.

Proof. By (4.1) we get

P ( ⋃_{|x|≤log n} ⋃_{j≤n^{δ}}{S_{j} = S_{n} + x}) ≤ ∑_{|x|≤log n} ∑_{j≤n^{δ}} P(S_{j} = S_{n} + x)

≤ ∑_{|x|≤log n} ∑_{j≤n^{δ}} \frac{C_{8}}{(n − j)^{d/2}} ≤ \frac{C_{17}(log n)^{d}}{n^{d/2−δ}} ,

and since this is summable, the lemma follows by Borel-Cantelli lemma. This implies P(D_{n} i.o.) = 1, proving Theorem 1.3.

References

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

[2] Csáki, E., Földes, A. and Révész, P.: Joint asymptotic behavior of local and occupation times of random walk in higher dimension. Preprint.

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

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

[5] Erdős, P. and Taylor, S.J.: Some intersection properties of random walk paths. Acta Math. Acad. Sci. Hung. 11 (1960), 231–248.

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

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

[8] Révész, P.: Random Walk in Random and Non-random Environment, Second ed., World Scientific Publishing Co., Singapore, 2005.

[9] Spitzer, F.: Principles of Random Walk, Van Nostrand, Princeton, 1964.

[10] Uchiyama, K.: Green’s functions for random walks on Z^{N}. Proc. London Math. Soc. 77 (1998), 215–240.