Frequently visited sets for random walks

Endre Csáki^{∗} Antónia Földes^{†} Pál Révész^{∗} Jay Rosen^{‡} Zhan Shi

Abstract

We study the occupation measure of various sets for a symmetric transient random walk in Z^{d} with finite variances. Let μ_{n}^{X}(A) denote the occupation time of the set A up to time n. It is shown that sup_{x∈Z^{d}} μ_{n}^{X}(x + A)/ log n tends to a finite limit as n → ∞. The limit is expressed in terms of the largest eigenvalue of a matrix involving the Green’s function of X restricted to the set A. Some examples are discussed and the connection to similar results for Brownian motion is given.

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

Keywords: random walk, occupation measure, strong theorems

1 Introduction

Let X_{n}, n = 0, 1, … be a symmetric transient random walk in Z^{d} (d ≥ 3). We will always assume that X_{n}, n = 0, 1, … is not supported on any subgroup strictly smaller than Z^{d}. We denote by μ_{n}^{X} its occupation measure:

μ_{n}^{X}(A) = ∑_{j=0}^{n} 1_{A}(X_{j})

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

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

‡Research supported, in part, by grants from the NSF and from PSC-CUNY.

for all sets A ⊆ Z^{d}. Let q_{n}(x) = P(X_{n} = x). As usual, we let

G(x) = ∑_{k=0}^{∞} q_{k}(x)  (1.1)

denote the Green’s function for {X_{n}}. For any finite A ⊆ Z^{d} let Λ_{A} denote the largest eigenvalue of the |A| × |A| matrix

G_{A}(x, y) = G(x − y), x, y ∈ A.  (1.2)

Theorem 1.1 If X has finite second moments then

lim_{n→∞} sup_{x∈Z^{d}} \frac{μ_{n}^{X}(x + A)}{log n} = −1/ log(1 − 1/Λ_{A}) a.s.  (1.3)

and

lim_{n→∞} sup_{0≤m≤n} \frac{μ_{n}^{X}(X_{m} + A)}{log n} = −1/ log(1 − 1/Λ_{A}) a.s.  (1.4)

For our first example, when A = {0}, Λ_{A} = G(0) = 1/γ_{d}, where γ_{d} is the probability of no-return to the origin, and in the case of the simple random walk we recover Theorem 13 of [3].

Here are some other examples. Set t_{y} = P(T_{y} < ∞), where T_{y} := inf{s > 0 : X_{s} = y}. Let S(0, 1) = {e_{1}, …, e_{d}, −e_{1}, …, −e_{d}}, B(0, 1) = {0} ∪ S(0, 1), be the (Euclidean) sphere and ball in Z^{d} of radius 1 centered at the origin.

Theorem 1.2 If X has finite second moments, then for any 0 ≠ y ∈ Z^{d}

lim_{n→∞} sup_{x∈Z^{d}} \frac{μ_{n}^{X}(x + \{0, y\})}{log n} = −1/ log(1 − γ_{d}/(1 + t_{y})) a.s.  (1.5)

For the simple random walk

lim_{n→∞} sup_{x∈Z^{d}} \frac{μ_{n}^{X}(x + S(0, 1))}{log n} = −1/ log (1 − γ_{d}/2d(1 − γ_{d})) a.s.  (1.6)

and

lim_{n→∞} sup_{x∈Z^{d}} \frac{μ_{n}^{X}(x + B(0, 1))}{log n} = −1/ log (\frac{p + \sqrt{p^{2} + 2/d}}{2}) a.s.  (1.7)

where p = 1 − 1/2d(1 − γ_{d}).

Corollary 1.3 If X has finite second moments, then for any fixed K > 0

lim_{n→∞} \frac{max_{x,y∈Z^{d}:|x−y|≤K}(μ_{n}^{X}(\{x, y\})}{log n} < −2/ log(1 − γ_{d}) a.s.

Since the constant for one-point set in Theorem 1.1 is −1/ log(1−γ_{d}), this corollary expresses the fact that any two points with individual occupation measures up to time n, both close to the maximum, should be at a distance larger than any constant K > 0. In particular, a neighbor of a maximally visited point is not maximally visited.

Let W_{t} denote Brownian motion in IR^{d}, d ≥ 3. We denote by ν_{T}^{W} its occupation measure:

ν_{T}^{W} (A) = ∫_{0}^{T} 1_{A}(W_{t}) dt

for all Borel sets A ⊆ IR^{d}. Let K ⊆ IR^{d} be a fixed compact neighborhood of the origin which is the closure of its interior and set K(x, r) = x + rK.

As usual, we let

u^{0}(x) = \frac{c_{d}}{|x|^{d−2}}  (1.8)

denote the 0-potential density for \{W_{t}\}, where c_{d} = 2^{−1}π^{−d/2}Γ(\frac{d}{2} − 1). Let Λ_{K}^{0} denote the norm of

R_{K}f(x) = ∫_{K} u^{0}(x − y)f(y) dy

considered as an operator from L^{2} (K, dx) to itself. If B(x, r) denotes the Euclidean ball in R^{d} of radius r centered at x, it is known, [1], that Λ_{B(0,1)}^{0} = 2r_{d}^{−2} where r_{d} is the smallest positive root of the Bessel function J_{d/2−2}.

We mention that it can be shown, at least for K convex, that for any S ∈ (0, ∞) and any T ∈ (0, ∞],

lim_{ϵ→0} sup_{|x|≤S} \frac{ν_{T} (K(x, ϵ))}{ϵ^{2}| log ϵ|} = 2Λ_{K}^{0} a.s.  (1.9)

and

lim_{ϵ→0} sup_{0≤t≤T} \frac{ν_{T} (K(W_{t}, ϵ))}{ϵ^{2}| log ϵ|} = 2Λ_{K}^{0} a.s.  (1.10)

(These results are mentioned for motivation. They are not used in the rest of the paper).

For any x ∈ R^{d} and ϵ > 0, let e_{ϵ}(x) = x+[0, ϵ]^{d}, the cube of edgelength ϵ with ‘lower’ corner at x. Set

L_{ϵ}(K) = {x ∈ ϵZ^{d} | e_{ϵ}(x) ⊆ K}, and C_{ϵ}(K) = ⋃_{x∈L_{ϵ}(K)} e_{ϵ}(x)  (1.11)

and assume that

lim_{ϵ→0} λ^{d}(C_{ϵ}(K)) = λ^{d}(K)  (1.12)

where λ^{d} denotes Lebesgue measure.

Note that ϵ^{−1}L_{ϵ}(K) ⊆ Z^{d}.

Theorem 1.4 Assume that X_{1} has d−1 moments and covariance matrix equal to the identity. Then

lim_{ϵ→0} ϵ^{2}Λ_{ϵ^{−1}L_{ϵ}(K)} = Λ_{K}^{0}  (1.13)

and consequently

− lim_{ϵ→0} ϵ^{2}/ log(1 − 1/Λ_{ϵ^{−1}L_{ϵ}(K)}) = Λ_{K}^{0}.  (1.14)

Section 2 states and proves the crucial Localization Lemma 2.2. Theorem 1.1 is proven in section 3, Theorem 1.2 and Corollary 1.3 are proven in section 4, and Theorem 1.4 is proven in section 5.

2 Localization for random walk occupation measures

We start by providing a convenient representation of the law of the total occupation measure μ_{∞}^{X} (A). This representation is the counterpart of the Ciesielski-Taylor representation for the total occupation measure of spatial Brownian motion in [1, Theorem 1].

Let (f, g)_{A} = ∑_{x∈A} f(x)g(x), and let δ_{0}(x) be the function on A defined by δ_{0}(x) = δ(0, x), x ∈ A.

Lemma 2.1 Let {X_{n}} be a symmetric transient random walk in Z^{d}, and let A be a finite set in Z^{d} which contains the origin. Then,

P (μ_{∞}^{X}(A) > u) = ∑_{j} h_{j} (\frac{λ_{j} − 1}{λ_{j}})^{u} u = 0, 1, …,  (2.1)

where λ_{1} > λ_{2} ≥ ⋯ ≥ λ_{|A|} ≥ 1/2 are the eigenvalues of the symmetric matrix G_{A} with the corresponding orthonormal eigenvectors ϕ_{j}(y), h_{j} := (1, ϕ_{j})_{A}ϕ_{j}(0).

Proof of Lemma 2.1: Let J = μ_{∞}^{X}(A) and set Ḡ(x−y) = ∑_{k=1}^{∞} q_{k}(x−y) = G(x−y)−q_{0}(x−y).

Note that for any m,

IE (J^{m}) = IE ({∑_{i=0}^{∞} 1_{A}(X_{i})}^{m}) = ∑_{i_{1},...,i_{m}=0}^{∞} IE (∏_{j=1}^{m} 1_{A}(X_{i_{j}}))
= ∑_{k=1}^{m} ∑_{c_{1}+···+c_{k}=m^{c_{1},...,c_{k}∈[1,m]}} \binom{m}{c_{1}, …, c_{k}} ∑_{A^{k}} ∑_{0≤n_{1}<···<n_{k}<∞} ∏_{j=1}^{k} q_{n_{j}−n_{j−1}}(x_{j} − x_{j−1}). (2.2)

Here, k is the number of distinct indices n_{1} < ⋯ < n_{k} among the indices i_{1}, …, i_{m} and c_{l} is the number of times that n_{l} appears, i.e. c_{l} = #\{j; 1 ≤ j ≤ m, i_{j} = n_{l}\}. The factor \binom{m}{c_{1},...,c_{k}} is the number of ways to assign the value n_{l} to c_{l} of the indices i_{1}, …, i_{m}, for each 1 ≤ l ≤ k.

Also, we have that

∑_{A^{k}} ∑_{0≤n_{1}<···<n_{k}<∞} ∏_{j=1}^{k} q_{n_{j}−n_{j−1}}(x_{j} − x_{j−1}) = ∑_{A^{k}} G(x_{1}) ∏_{j=2}^{k} Ḡ(x_{j} − x_{j−1})  (2.3)
= (1, Ḡ_{A}^{k−1}G_{A}δ_{0})_{A}.

Hence (we justify the computations shortly)

IE (e^{ζJ} ) = 1 + ∑_{m=1}^{∞} \frac{ζ^{m}}{m!} ∑_{k=1}^{m} ∑_{c_{1}+···+c_{k}=m^{c_{1},...,c_{k}∈[1,m]}} \binom{m}{c_{1}, …, c_{k}}(1, Ḡ_{A}^{k−1}G_{A}δ_{0})_{A}  (2.4)

= 1 + ∑_{k=1}^{∞} ∑_{m=k}^{∞} ∑_{c_{1}+···+c_{k}=m^{c_{1},...,c_{k}∈[1,m]}} ∏_{j=1}^{k} \frac{ζ^{c_{j}}}{c_{j}!} (1, Ḡ_{A}^{k−1}G_{A}δ_{0})_{A}

= 1 + ∑_{k=1}^{∞}(e^{ζ} − 1)^{k}(1, Ḡ_{A}^{k−1}G_{A}δ_{0})_{A}

G_{A} is a symmetric matrix. Let ψ(p) denote the characteristic function of X_{1}. Then ψ(p) is real and |ψ(p)| ≤ 1. Thus 0 ≤ 1 − ψ(p) ≤ 2, or equivalently \frac{1}{1−ψ(p)} ≥ \frac{1}{2}. Hence, using the Fourier transform representation G(x − y) = ∫ e^{i((x−y)·p)}(1 − ψ(p))^{−1} dp we can see that ∑_{x,y∈A} G_{A}(x, y)a_{x}a_{y} ≥ \frac{1}{2} ∑_{x∈A} a_{x}^{2} for any \{a_{x} ∈ R^{1}; x ∈ A\}. By the standard theory for symmetric matrices, G_{A} has all eigenvalues ≥ 1/2, and the corresponding eigenvectors of G_{A}, denoted {ϕ_{j}} form an orthonormal basis of L^{2} (A) (see [7, Theorems VI.15, VI.16]). Moreover, since the entries of G_{A} are strictly positive, by the Perron-Frobenius Theorem, see [8, Theorem XIII.43], the eigenspace corresponding to Λ_{A} = λ_{1} is one dimensional, and we may and shall choose ϕ_{1} such that ϕ_{1}(y) > 0 for all y ∈ A.

Thus we can write (2.4) as

IE (e^{ζJ} ) = 1 + ∑_{k=1}^{∞}(e^{ζ} − 1)^{k}(1, Ḡ_{A}^{k−1}G_{A}δ_{0})_{A}  (2.5)
= 1 + ∑_{j=1}^{|A|}(1, ϕ_{j})_{A}(ϕ_{j}, δ_{0})_{A} ∑_{k=1}^{∞}(e^{ζ} − 1)^{k}(λ_{j} − 1)^{k−1}λ_{j}
= 1 + ∑_{j=1}^{|A|} h_{j}(e^{ζ} − 1)λ_{j} ∑_{k=1}^{∞}(e^{ζ} − 1)^{k−1}(λ_{j} − 1)^{k−1}

where h_{j} = (1, ϕ_{j})_{A}(ϕ_{j}, δ_{0})_{A}. It is now easy to see that we can justify the derivation of (2.4) and (2.5) if

|(e^{ζ} − 1)(λ_{j} − 1)| < 1, ∀j.  (2.6)

In that case we can write (2.5) as

IE (e^{ζJ} ) = 1 + ∑_{j} h_{j} \frac{(e^{ζ} − 1)λ_{j}}{1 − (e^{ζ} − 1)(λ_{j} − 1)}.  (2.7)

Since ∑_{j=1}^{|A|} h_{j} = ∑_{j=1}^{|A|}(1, ϕ_{j})_{A}(ϕ_{j}, δ_{0})_{A} = (1, δ_{0})_{A} = 1 we have that

IE (e^{ζJ} ) = ∑_{j} h_{j} \frac{e^{ζ}}{1 − (e^{ζ} − 1)(λ_{j} − 1)}.  (2.8)

Let f_{j} = 1 − 1/λ_{j} = (λ_{j} − 1)/λ_{j}. A straightforward calculation shows that

\frac{e^{ζ}(1 − f_{j})}{1 − e^{γ}f_{j}} = \frac{e^{ζ}}{1 − (e^{ζ} − 1)(λ_{j} − 1)}  (2.9)

so that

IE (e^{ζJ} ) = ∑_{j} h_{j} \frac{e^{ζ}(1 − f_{j})}{1 − e^{ζ}f_{j}}.  (2.10)

Note that since all λ_{j} ≥ 1/2 we have |f_{j}| ≤ 1. We can always choose ζ so that addition to (2.6) we also have

|e^{ζ}| < 1.  (2.11)

Then we can write

\frac{e^{ζ}(1 − f_{j})}{1 − e^{ζ}f_{j}} = e^{ζ}(1 − f_{j}) ∑_{k=0}^{∞} e^{kζ}f_{j}^{k}.  (2.12)

Hence

∑_{k=1}^{∞} e^{kζ}P (J = k) = IE (e^{ζJ} ) = ∑_{j} h_{j}(1 − f_{j}) ∑_{k=1}^{∞} e^{kζ}f_{j}^{k−1}.  (2.13)

We can choose ζ_{0} < 0 so that (2.6) and (2.11) hold. Furthermore, both sides of (2.13) are analytic functions of ζ in some neighborhood of ζ_{0} + iR^{1} and agree for ζ_{0} + iy when y is small. This is enough to allow us to conclude that

P (J = k) = ∑_{j} h_{j}(1 − f_{j})f_{j}^{k−1}, k = 1, 2, ….  (2.14)

Hence

P (J > u) = ∑_{j} h_{j}f_{j}^{u} u = 0, 1, …  (2.15)

This completes the proof of (2.1). □

With the aid of (2.1) we next provide a localization result for the occupation measure of {X_{n}}.

Lemma 2.2 (The Localization Lemma) Let {X_{n}} be a symmetric transient random walk in Z^{d} with finite second moments, and let A be a finite set in Z^{d}. Set θ^{∗} = log(Λ_{A}/(Λ_{A} − 1)). Then for some c_{1} < ∞, n ≥ u^{6}, and all u > 0 sufficiently large

c_{1}^{−1}e^{−θ^{∗}u} ≤ P (μ_{n}^{X} (A) ≥ u) ≤ P (μ_{∞}^{X} (A) ≥ u) ≤ c_{1}e^{−θ^{∗}u}.  (2.16)

Proof of Lemma 2.2: Let J_{n} := μ_{n}^{X}(A). Assume first that A contains the origin. The dominant terms in (2.15) correspond to the f_{j}’s with largest absolute value. But since P (J > u) ≥ 0 and monotone decreasing it is clear that these dominant terms must in addition be those which correspond to positive f_{j}’s. Thus the f_{j}’s with largest absolute value are positive, i.e. correspond to λ_{j}’s which are greater than 1. Recall that ϕ_{1} is a strictly positive function on A, hence in (2.15) we have h_{1} > 0. Since (x − 1)/x = 1 − 1/x is strictly monotone increasing on (1, ∞) we conclude that the dominant term in (2.15) is precisely the single term corresponding to the largest eigenvalue λ_{1} = Λ_{A}. Hence

P (J > u) ∼ h_{1}f_{1}^{u} = h_{1} (\frac{Λ_{A} − 1}{Λ_{A}})^{u} = h_{1}e^{−u log(Λ_{A}/(Λ_{A}−1))}  (2.17)

implying that

lim_{u→∞} P(J_{∞} > u)e^{θ^{∗}u} = h_{1} ∈ (0, ∞)  (2.18)

out of which the upper bound of (2.16) immediately follows.

Turning to prove the corresponding lower bound, let τ_{z} := inf{s : |X_{s}| > z}, and note that

P(τ_{z} > n) ≤ c_{1} exp(−c_{2}nz^{−2}).  (2.19)

Here is a simple proof:

P (τ_{z} > n) = P (|X_{k}| ≤ z; 1 ≤ k ≤ n)
≤ P (|X_{lz^{2}}| ≤ z; 1 ≤ l ≤ nz^{−2})
≤ P (|X_{lz^{2}} − X_{(l−1)z^{2}}| ≤ 2z; 1 ≤ l ≤ nz^{−2})
≤ ∏_{l=1}^{[nz^{−2}]} P (|X_{lz^{2}} − X_{(l−1)z^{2}}| ≤ 2z)
= (P (|X_{z^{2}}| ≤ 2z))^{[nz^{−2}]} ≤ e^{−c_{2}[nz^{−2}]}.  (2.20)

Hence

P(J_{n} > u) ≥ P(J_{τ_{z}} > u) − P(τ_{z} > n) ≥ P(J_{τ_{z}} > u) − c^{−1} exp(−cnz^{−2}) .  (2.21)

As usual we use the notation P^{a} to denote probabilities of the random walk a + X_{n}, n = 0, 1, . . .. We now observe that

sup_{a∈A} P^{a}(μ_{∞}^{X}(A) > u) ≤ cP(μ_{∞}^{X}(A) > u)  (2.22)

for some c < ∞ and all u. To see this, note that for each a ∈ A we can find some n_{a} with h_{a} = P(X_{n_{a}} = a) > 0. Then using the Markov property,

P(μ_{∞}^{X}(A) > u) ≥ P({μ_{∞}^{X}(A) > u} ∘ θ_{n_{a}}, X_{n_{a}} = a) = h_{a}P^{a}(μ_{∞}^{X}(A) > u).  (2.23)

Then (2.22) follows with c = sup_{a∈A} h_{a}^{−1} < ∞.

Let J and J′ denote two independent copies of J_{∞} and T_{A} := inf{s > 0 : X_{s} ∈ A}. Noting (2.22), and using the strong Markov property, it is not hard to verify that

P(J_{∞} > u) ≤ P(J_{τ_{z}} > u) + cP(J + J′ > u) sup_{|v|>z} P^{v}(T_{A} < ∞)  (2.24)

(c.f. [2, (3.6) and (3.7)] where this is obtained for the Brownian motion). It follows from Theorem 10.1 of [5] that

G(x) ≤ \frac{c}{|x|}, |x| ≠ 0.  (2.25)

Using this together with the fact that G(X_{n∧T_{A}}) is a martingale shows that

G(v) = IE^{v}(G(X_{T_{A}}), T_{A} < ∞) ≥ inf_{a∈A} G(a)P^{v}(T_{A} < ∞).  (2.26)

Therefore

sup_{|v|>z} P^{v}(T_{A} < ∞) ≤ cz^{−1}.  (2.27)

By (2.18) it follows that for some constant C independent of u, which may change from line to line,

P(J + J′ > u) = P(J > u) + ∑_{y=0}^{u} P(J′ > u − y)P(J = y)

≤ C[ exp(−uθ^{∗}) + ∑_{y=0}^{u} exp(−(u − y)θ^{∗})P(J = y)]
≤ C exp(−uθ^{∗}) + C ∑_{y=0}^{u} exp(−uθ^{∗})
= C(1 + u) exp(−uθ^{∗}) .  (2.28)

Hence, taking z = u^{2} one gets from (2.21) and (2.24) that for some c′ > 0, all n ≥ u^{6} and u sufficiently large

P(J_{n} > u) ≥ c′e^{−θ^{∗}u}  (2.29)

as needed to complete the proof of the lemma when A contains the origin. In general we have

P(μ_{∞}^{X}(A) > u) = P({μ_{∞}^{X}(A) > u} ∘ θ_{T_{A}}, T_{A} < ∞) = ∑_{a∈A} P^{a}(μ_{∞}^{X}(A) > u)P(T_{A} = T_{a} < ∞)

(2.30)

and since it is easy to see from its proof that (2.18) holds with P replaced by P^{a} for any a ∈ A, for some c_{1} = c_{1}(a) it follows that (2.18) also holds. This completes the proof of the lemma. □

Remark. If A is replaced by z + A for some fixed z ∈ Z^{d}, note from (1.2) that as matrices, G_{z+A} = G_{A}. Hence Λ_{z+A} = Λ_{A}.

3 Proof of Theorem 1.1

Given Lemma 2.2, Theorem 1.1 follows by the methods of [3, Section 7]. We spell out the details.

We first prove the lower bound for (1.4). To this end fix a < θ^{∗}^{−1} = 1/ log(Λ_{A}/(Λ_{A} − 1)).

Let k(n) = (log n)^{8} and N_{n} = [n/k(n)], and t_{i,n} = ik(n) for i = 0, …, N_{n} − 1. Writing X_{s}^{t} = X_{s+t} − X_{t} it follows that

sup_{m∈[0,n]} μ_{n}^{X}(X_{m} + A) ≥ max_{0≤i≤N_{n}−1} Z_{i}^{(n)} ,

where Z_{i}^{(n)} = μ_{k(n)}^{X^{t_{i,n}}} (A) are i.i.d. and by Lemma 2.2, for some c > 0 and all n large enough,

P( max_{0≤i≤N_{n}−1} Z_{i}^{(n)} ≤ a log n) ≤ (1 − cn^{−aθ^{∗}})^{N_{n}} ≤ e^{−cn^{−aθ^{∗}}N_{n}} .

Since aθ^{∗} < 1 this is summable, so that applying Borel-Cantelli, then taking a ↑ θ^{∗}^{−1}, we see that a.s.

lim inf_{n→∞} sup_{m∈[0,n]} \frac{μ_{n}^{X}(X_{m} + A)}{log n} ≥ θ^{∗}^{−1}.  (3.1)

This gives the lower bound for (1.4).

For the upper bound, fix a > θ^{∗}^{−1}. Note that for any m ∈ [0, n]

μ_{n}^{X}(X_{m} + A) = ∑_{j=0}^{n} 1_{X_{m}+A}(X_{j}) = ∑_{j=0}^{n} 1_{A}(X_{j} − X_{m})  (3.2)
= ∑_{j=0}^{m−1} 1_{A}(X_{j} − X_{m}) + ∑_{j=m}^{n} 1_{A}(X_{j} − X_{m})
=^{law} ∑_{j=1}^{m} 1_{A}(X′_{j}) + ∑_{j=0}^{n−m} 1_{A}(X′′_{j})

where {X′_{j} , j = 0, 1, …}, {X′′_{j} , j = 0, 1, …} are two independent copies of {X_{j} , j = 0, 1, …} and we have used the symmetry of X_{1}. Using this and (2.28),

P( sup_{m∈[0,n]} μ_{n}^{X}(X_{m} + A) ≥ a log n) ≤ ∑_{m=0}^{n} P(μ_{n}^{X}(X_{m} + A) ≥ a log n)  (3.3)
≤ 2nP(J + J′ ≥ a log n) ≤ c(log n) n^{−(aθ^{∗}−1)}.

Thus letting n_{k} = n^{k} for k sufficiently large that k(aθ^{∗} − 1) > 2, we see from applying Borel-Cantelli, then taking a ↓ θ^{∗}^{−1}, that a.s.

lim sup_{n→∞} sup_{m∈[0,n^{k}]} \frac{μ_{n^{k}}^{X}(X_{m} + A)}{log n^{k}} ≤ θ^{∗}^{−1}.

The upper bound for (1.4) then follows by interpolation.

The lower bound for (1.3) follows immediately from (3.1). As for the upper bound in (1.3), we note that μ_{n}^{X}(x + A) = 0 unless X_{m} ∈ x + A for some m ∈ [0, n]. Thus the only relevant x’s in (1.3) are of the form X_{m} − a for some m ∈ [0, n] and a ∈ A. Thus

sup_{x∈Z^{d}} μ_{n}^{X}(x + A) = sup_{m∈[0,n], a∈A} μ_{n}^{X}(X_{m} − a + A).  (3.4)

Recalling Remark and the fact that A is a finite set, the upper bound for (1.3) now follows as in the proof of the upper bound for (1.4).

4 Examples

Proof of (1.5): When A = {0, y} we have

G_{A} = ( \begin{matrix}G(0) & G(y) \\ G(y) & G(0) \end{matrix} ) .

The eigenvalues are G(0) + G(y), G(0) − G(y) so that Λ_{A} = G(0) + G(y) = G(0)(1 + t_{y}) = (1 + t_{y})/γ_{d}, where t_{y} = P(T_{y} < ∞), γ_{d} is the probability of no-return to the origin, and we have used the fact that G(y) = t_{y}G(0). Then 1 − 1/Λ_{A} = 1 − γ_{d}/(1 + t_{y}).

We note that in the notation of Lemma 2.1, h_{1} = 1, h_{2} = 0 so that by (2.1)

P (μ_{∞}^{X}({0, y}) > u) = (1 − γ_{d}/(1 + t_{y}))^{u} u = 1, 2, …  (4.1)

Proof of (1.6): We now consider the simple random walk, and for ease of notation consider first d = 3. Let A = {e_{1}, e_{2}, e_{3}, −e_{1}, −e_{2}, −e_{3}} = S(0, 1), the (Euclidean) sphere in Z^{3} of radius 1 centered at the origin. We have

G_{S(0,1)} = ( \begin{matrix}G(0) & G(e_{1} − e_{2}) & G(e_{1} − e_{3}) & G(2e_{1}) & G(e_{1} + e_{2}) & G(e_{1} + e_{3}) \\ G(e_{2} − e_{1}) & G(0) & G(e_{2} − e_{3}) & G(e_{2} + e_{1}) & G(2e_{2}) & G(e_{2} + e_{3}) \\ G(e_{3} − e_{1}) & G(e_{3} − e_{2}) & G(0) & G(e_{3} + e_{1}) & G(e_{3} + e_{2}) & G(2e_{3}) \\ G(2e_{1}) & G(e_{1} + e_{2}) & G(e_{1} + e_{3}) & G(0) & G(e_{1} − e_{2}) & G(e_{1} − e_{3}) \\ G(e_{2} + e_{1}) & G(2e_{2}) & G(e_{2} + e_{3}) & G(e_{2} − e_{1}) & G(0) & G(e_{2} − e_{3}) \\ G(e_{3} + e_{1}) & G(e_{3} + e_{2}) & G(2e_{3}) & G(e_{3} − e_{1}) & G(e_{3} − e_{2}) & G(0) \end{matrix} ) .

Using G(x) = t_{x}G(0), where t_{x} = P(T_{x} < ∞), and symmetry which allows us to set a =: t_{e_{i}±e_{j}} for i ≠ j and b =: t_{2e_{i}} we can write

G_{S(0,1)} = G(0) ( \begin{matrix}1 & a & a & b & a & a \\ a & 1 & a & a & b & a \\ a & a & 1 & a & a & b \\ b & a & a & 1 & a & a \\ a & b & a & a & 1 & a \\ a & a & b & a & a & 1 \end{matrix} ) .

It follows from the Perron-Frobenius Theorem that the largest eigenvalue is Λ_{S(0,1)} = G(0)(1 + 4a + b) with eigenvector (1, 1, 1, 1, 1, 1). Also, it is easy to see by symmetry that γ_{3} = P(T_{e_{i}} = ∞). Then again by symmetry P(T_{e_{1}} = ∞) = \frac{4}{6}P(T_{e_{1}−e_{2}} = ∞) + \frac{1}{6}P(T_{2e_{1}} = ∞), i.e. 6γ_{3} = 4P(T_{e_{1}−e_{2}} = ∞) + P(T_{2e_{1}} = ∞). Hence Λ_{S(0,1)} = G(0)(1 + 4a + b) = G(0)6(1 − γ_{3}) = 6(1 − γ_{3})/γ_{3}. For the case of general d ≥ 3, G_{S(0,1)} is now a 2d × 2d matrix, which is G(0) times a matrix in which each row has a single entry entry of 1, a single entry of b =: t_{2e_{i}} and 2d − 2 entries of a =: t_{e_{i}±e_{j}}, where as before t_{x} = P(T_{x} < ∞). It is easy to see by symmetry that γ_{d} = P(T_{e_{i}} = ∞). Also, as before, it is easy to see by symmetry P(T_{e_{1}} = ∞) = \frac{(2d−2)}{2d}P(T_{e_{1}−e_{2}} = ∞) + \frac{1}{2d}P(T_{2e_{1}} = ∞), i.e. 2dγ_{d} = (2d − 2)P(T_{e_{1}−e_{2}} = ∞) + P(T_{2e_{1}} = ∞). Hence Λ_{S(0,1)} = G(0)(1 + (2d − 2)a + b) = G(0)2d(1 − γ_{d}) = 2d(1 − γ_{d})/γ_{d} for all d ≥ 3.

We note that in the notation of Lemma 2.1, h_{1} = 1, h_{j} = 0, ∀j ≠ 1 so that by (2.1)

P (μ_{∞}^{X}(S(0, 1)) > u) = (1 − γ_{d}/2d(1 − γ_{d}))^{u} u = 1, 2, …  (4.2)

Actually, (2.1) assumes that 0 ∈ A which doesn’t hold here, but using (2.30) and symmetry we have that P (μ_{∞}^{X}(S(0, 1)) > u) = P^{e_{1}} (μ_{∞}^{X}(S(0, 1)) > u) and (4.2) follows.

Proof of (1.7): We again consider the simple random walk. Let now A = {0} ∪ S(0, 1) = B(0, 1), the (Euclidean) ball in Z^{3} of radius 1 centered at the origin. With s = P(T_{e_{i}} < ∞) and s̄ = (s, ⋯, s) ∈ R^{2d} we have

G_{B(0,1)} = G(0) ( \begin{matrix}1 & s̄ \\ s̄^{t} & M \end{matrix} )

with M the 2d × 2d matrix in the previous example. M is a self-adjoint matrix, and as mentioned the principal eigenvector is ¯1 = (1, ⋯, 1) ∈ R^{2d}. If u_{i}, i = 1, …, 2d − 1 denote the other orthonormal eigenvectors of G(0)M with eigenvalue λ_{i} < Λ_{S(0,1)}, then since they are orthogonal to ¯1 it is clear that (0, u_{i}), i = 1, …, 2d−1 will give us 2d−1 orthonormal eigenvectors of G_{B(0,1)} with eigenvalues λ_{i} < Λ_{S(0,1)}. The remaining (two) orthonormal eigenvectors must be of the form (v, w¯1) and the corresponding eigenvalues will be G(0) times those of the 2 × 2 matrix

L = ( \begin{matrix}1 & 2ds \\ s & Λ \end{matrix} )

where we abbreviate Λ = Λ_{S(0,1)}/G(0) = 2d(1 − γ_{d}). The eigenvalues of L are

\frac{(1 + Λ) ± \sqrt{(1 + Λ)^{2} − 4(Λ − 2ds^{2})}}{2}  (4.3)

so that

1/Λ_{B(0,1)} = \frac{2}{G(0)} \frac{(1 + Λ) − \sqrt{(1 + Λ)^{2} − 4(Λ − 2ds^{2})}}{4(Λ − 2ds^{2})}.  (4.4)

Since s = 1 − γ_{d} we have Λ − 2ds^{2} = 2dγ_{d}(1 − γ_{d}) = γ_{d}Λ we have

1/Λ_{B(0,1)} = \frac{(1 + Λ) − \sqrt{(1 + Λ)^{2} − 4γ_{d}Λ}}{2Λ}  (4.5)

so that

1 − 1/Λ_{B(0,1)} = \frac{(Λ − 1) + \sqrt{(1 + Λ)^{2} − 4γ_{d}Λ}}{2Λ}  (4.6)
= \frac{(1 − 1/Λ) + \sqrt{(1 + 1/Λ)^{2} − 4γ_{d}/Λ}}{2}.

Setting p = 1 − 1/Λ we can write this as

1 − 1/Λ_{B(0,1)} = \frac{p + \sqrt{(2 − p)^{2} − 4γ_{d}/Λ}}{2}  (4.7)
= \frac{p + \sqrt{p^{2} + 4 − 4p − 4γ_{d}/Λ}}{2}
= \frac{p + \sqrt{p^{2} + 2/d}}{2}.

We note that in the notation of Lemma 2.1, h_{j} = 0 for the 2d − 1 orthonormal eigenvectors of the form (0, u_{i}), i = 1, …, 2d − 1 above. For the principle eigenvalue we have (4.7) and for the other ‘surviving’ eigenvalue the corresponding expression is ^{\frac{p−\sqrt{p^{2}+2/d}}{2}}. Hence by (2.1)

P (μ_{∞}^{X}(B(0, 1)) > u) = h_{1} (\frac{p + \sqrt{p^{2} + 2/d}}{2})^{u} + h_{2} (\frac{p − \sqrt{p^{2} + 2/d}}{2})^{u} , u = 1, 2, …, (4.8)

where h_{1}, h_{2} can be calculated in a straightforward manner. We observe that since p < \sqrt{p^{2} + 2/d}, the expression in (4.8) is not a mixture of geometric random variables.

Now we prove Corollary 1.3. For any y ∈ Z^{d} we have t_{y}^{2} < 1 − γ_{d}, since t_{y}^{2} is the probability that the random walk hits y and then returns to 0 in finite time which is obviously less than the probability 1−γ_{d} that the random walk returns to zero in finite time. This implies (1+t_{y}−γ_{d})^{2} < (1 + t_{y})^{2}(1 − γ) which in turn, implies

−1/ log(1 − γ_{d}/(1 + t_{y})) < −2/ log(1 − γ_{d}),

and taking sup_{|y|≤K} we obtain the Corollary 1.3.

5 The Brownian connection

Since R_{K} is a convolution operator on a bounded subset of IR^{d} with locally L^{1} (IR^{d}, dx) kernel, it follows easily as in [4, Corollary 12.3] that R_{K} is a (symmetric) compact operator on L^{2}(K, dx). Moreover, the Fourier transform relation ∫ e^{i(x·p)}u^{0}(x) dx = c|p|^{−2} > 0 implies that R_{K} is strictly positive definite. By the standard theory for symmetric compact operators, R_{K} has discrete spectrum (except near 0) with all eigenvalues positive, and of finite multiplicity (see [7, Theorems VI.15, VI.16]). Moreover, if we use (f, g)_{2,K} to denote the inner product in L^{2}(K, dx), we have that (f, R_{K}g)_{2,K} > 0 for any non-negative, non-zero, f, g, so by the generalized Perron-Frobenius Theorem, see [8, Theorem XIII.43], the eigenspace corresponding to the largest eigenvalue, Λ_{K}^{0}, is one dimensional.

Let R_{K,ϵ} be the operator on L^{2}(K, dx) with kernel

u_{K,ϵ}^{0}(x, y) = ∑_{z≠z′∈L_{ϵ}(K)} u^{0}(z − z′)1_{e_{ϵ}(z)}(x)1_{e_{ϵ}(z′)}(y).  (5.1)

Since the sum is over disjoint sets, it can be checked easily that for any 1 < p < d/(d − 2), u_{K,ϵ}^{0}(x, y) is bounded in L^{p}(K × K, dx dy) uniformly in ϵ > 0:

∫_{K×K} |u_{K,ϵ}^{0}(x, y)|^{p} dx dy = ∑_{z≠z′∈L_{ϵ}(K)} ∫_{e_{ϵ}(z)×e_{ϵ}(z′)} |u^{0}(z − z′)|^{p} dx dy  (5.2)
= cϵ^{2d} ∑_{z≠z′∈L_{ϵ}(K)} \frac{1}{|z − z′|^{p(d−2)}}
= cϵ^{2d−p(d−2)} ∑_{i≠j∈Z^{d}, |i|,|j|≤k/ϵ} \frac{1}{|i − j|^{p(d−2)}} ≤ C.

Also u_{K,ϵ}^{0}(x, y) → u^{0}(x − y) as ϵ → 0 for all x ≠ y. Hence, using (1.12)

lim_{ϵ→0}(f, R_{K,ϵ}f)_{2,K} = (f, R_{K}f)_{2,K}, ∀f ∈ C(K).  (5.3)

By [9],

G(x) = (1 + δ(x))u^{0}(x), ∀x ≠ 0  (5.4)

with δ(x) bounded and lim_{|x|→∞} δ(x) = 0 so that

ϵ^{2−d}G(ϵ^{−1}x) = (1 + δ(ϵ^{−1}x))u^{0}(x), ∀x ∈ L_{ϵ}(K), x ≠ 0.  (5.5)

Let G_{K,ϵ} be the operator on L^{2}(K, dx) with kernel

v_{K,ϵ}^{0}(x, y) = ∑_{z≠z′∈L_{ϵ}(K)} ϵ^{2−d}G(ϵ^{−1}(z − z′))1_{e_{ϵ}(z)}(x)1_{e_{ϵ}(z′)}(y).  (5.6)

Using (5.5), the same argument leading to (5.3) shows that

lim_{ϵ→0}(f, G_{K,ϵ}f)_{2,K} = (f, R_{K}f)_{2,K}, ∀f ∈ C(K).  (5.7)

Furthermore, since G(0) < ∞, if we let G̃_{K,ϵ} be the operator on L^{2}(K, dx) with kernel

w_{K,ϵ}^{0}(x, y) = ∑_{z,z′∈L_{ϵ}(K)} ϵ^{2−d}G(ϵ^{−1}(z − z′))1_{e_{ϵ}(z)}(x)1_{e_{ϵ}(z′)}(y)  (5.8)

it follows from (5.7) that

lim_{ϵ→0}(f, G̃_{K,ϵ}f)_{2,K} = (f, R_{K}f)_{2,K}, ∀f ∈ C(K).  (5.9)

It now follows from [6, Theorem VIII.3.6, ] that, if Λ(G̃_{K,ϵ}) denotes the largest eigenvalue of the operator G̃_{K,ϵ}

lim_{ϵ→0} Λ(G̃_{K,ϵ}) = Λ(R_{K}) = Λ_{K}^{0}.  (5.10)

If f is any eigenvector for G̃_{K,ϵ} with eigenvalue ζ > 0, it is clear that f is in the image of G̃_{K,ϵ} so that we can write

f(x) = ∑_{z∈L_{ϵ}(K)} 1_{e_{ϵ}(z)}(x)f(z)  (5.11)

and the eigenvalue equation G̃_{K,ϵ}f = ζf becomes

1_{e_{ϵ}(z)}(x) ∑_{z′∈L_{ϵ}(K)} ∫_{K} w_{K,ϵ}^{0}(x, y)1_{e_{ϵ}(z′)}(y)f(z′) dy = ζf(z), ∀z ∈ L_{ϵ}(K).  (5.12)

Noting that the dy integration picks up a factor ϵ^{d}, this implies that

∑_{z′∈L_{ϵ}(K)} ϵ^{2}G(ϵ^{−1}(z − z′))f(z′) = ζf(z), ∀z ∈ L_{ϵ}(K).  (5.13)

Hence Λ_{ϵ^{−1}L_{ϵ}(K)} = ϵ^{−2}Λ(G̃_{K,ϵ}). Together with (5.10) this completes the proof of Theorem 1.4.

References

1. Z. Ciesielski and S. J. Taylor, First passage times and sojourn times for Brownian motion in space and the exact Hausdorff measure of the sample path, Trans. Amer. Math. Soc. 103 (1962), 434–452.

2. A. Dembo, J. Rosen, Y. Peres and O. Zeitouni, Thick points for spatial Brownian motion: multifractal analysis of occupation measure, Ann. Probab., 28 (2000), 1-35.

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

4. P. Halmos and V. Sunder, Bounded Integral Operators on L^{2} Spaces, Springer-Verlag, New York, 1978.

5. G. Lawler, Notes on random walks, in preparation.

www.math.cornell.edu/~lawler/m778s04.html

6. T. Kato, Perturbation Theory of Linear Operators, second edition, Springer-Verlag, New York, 1976.

7. M. Reed and B. Simon, Methods of Modern Mathematical Physics I: Functional Analysis, Academic Press, New York, 1972.

8. M. Reed and B. Simon, Methods of Modern Mathematical Physics IV: Analysis of Operators, Academic Press, New York, 1978.

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

Endre Csáki  Antónia Földes
Alfréd Rényi Institute of Mathematics  Department of Mathematics
Hungarian Academy of Sciences  College of Staten Island, CUNY
P.O. Box 127  2800 Victory Blvd., Staten Island
H-1364 Budapest  New York 10314
Hungary  USA

csaki@renyi.hu                                        afoldes@gc.cuny.edu

Pál Révész  Jay Rosen
Institut für Statistik und Wahrscheinlichkeitstheorie  Department of Mathematics
Technische Universität Wien  College of Staten Island, CUNY
Wiedner Hauptstrasse 8-10/107  2800 Victory Blvd., Staten Island
A-1040 Vienna  New York 10314
Austria  USA

revesz@ci.tuwien.ac.at                                jrosen3@earthlink.net

Zhan Shi Laboratoire de Probabilités UMR 7599 Université Paris VI 4 place Jussieu F-75252 Paris Cedex 05 France

zhan@proba.jussieu.fr