simple random walk Endre Csaki 1   Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, P.O.B. 127, H-1364, Hungary. E-mail address: csaki@renyi.hu Antonia Foldes 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 3  

Heavy points of a d-dimensional

Pal Revesz

November 27, 2006

Institut fur Statistik und Wahrscheinlichkeitstheorie, Technische Universitat Wien, Wiedner Hauptstrasse 8-10/107 A-1040 Vienna, Austria. E-mail address: reveszp@renyi.hu
Abstract
For a simple symmetric random walk in dimension d ≥ 3   , a uniform strong law of large numbers is proved for the number of sites with given local time up to time n   .
AMS 2000 Subject Classification: Primary 60G50; Secondary 60F15, 60J55.
Keywords: local time, simple random walk in d   -dimension, strong theorems.

1. Introduction and main results

Consider a simple symmetric random walk { S n } n = 1 ∞   starting at the origin 0   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 = e i ) = P ( X 1 = − e i ) = 1 2 d , 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
ξ ( x , n ) : = # { k : 0 < k ≤ n , S k = x } , n = 1 , 2 , … , (1.1)
where x   is any lattice point of Z d .   The maximal local time of the walk is defined as
ξ ( n ) : = max x ∈ Z d ξ ( x , n ) . (1.2)
Define also
η ( n ) : = max 0 ≤ k ≤ n ξ ( S k , ∞ ) . (1.3)
Denote by γ ( n ) = γ ( n ; d )   the probability that in the first n − 1   steps the d   -dimensional path does not return to the origin. Then
1 = γ ( 1 ) ≥ γ ( 2 ) ≥ . . . ≥ γ ( n ) ≥ . . . > 0 . (1.4)
It was proved in [2] that Theorem A (Dvoretzky and Erdos [2] ) For d ≥ 3  
lim n → ∞ γ ( n ) = γ = γ ( ∞ ; d ) > 0 , (1.5)
and
γ < γ ( n ) < γ + O ( n 1 − d / 2 ) , (1.6)
or equivalently
P ( ξ ( 0 , n ) = 0 , ξ ( 0 , ∞ ) > 0 ) = O ( n 1 − d / 2 ) (1.7)
as n → ∞   .
So γ   is the probability that the d   -dimensional simple symmetric random walk never returns to its starting point.
Let ξ ( x , ∞ )   be the total local time at x   of the infinite path in Z d   . Then (see Erdos and Taylor [3] ) ξ ( 0 , ∞ )   has geometric distribution:
P ( ξ ( 0 , ∞ ) = k ) = γ ( 1 − γ ) k , k = 0 , 1 , 2 , . . . (1.8)
Erdos and Taylor [3] proved the following strong law for the maximal local time:
Theorem B (Erdos and Taylor [3] ) For d ≥ 3  
lim n → ∞ ξ ( n ) log n = λ a . s . , (1.9)
where
λ = λ d = − 1 log ( 1 − γ ) . (1.10)
Following the proof of Erdos and Taylor, without any new idea, one can prove that
lim n → ∞ η ( n ) log n = λ a . s . (1.11)
We can present a stronger lower estimate of ξ ( n )   .
Theorem C (Revesz [10] ) Let d ≥ 4   and
ψ ( n ) = ψ ( n , B ) = λ log n − λ B log log n . (1.12)
Then with probability 1 for any ɛ > 0   there is a random variable n 0   such that ξ ( n ) ≥ ψ ( n , 3 + ɛ )   if n ≥ n 0   .
Erdos and Taylor [3] also investigated the properties of Q ( k , n ) : = # { x : x ∈ Z d , ξ ( x , n ) = k } ,   i.e. the cardinality of the set of points visited exactly k   times in the time interval [ 1 , n ]   .
They proved Theorem D (Erdos and Taylor [3] ) For d ≥ 3   and for any k = 1 , 2 , …  
lim n → ∞ Q ( k , n ) n = γ 2 ( 1 − γ ) k − 1 a . s . (1.13)
Let
U ( k , n ) : = # { j : 0 < j ≤ n , ξ ( S j , ∞ ) = k , S j ≠ S ℓ ( ℓ = 1 , 2 , … , j − 1 ) }
= # { x ∈ Z d : 0 < ξ ( x , n ) ≤ ξ ( x , ∞ ) = k } . (1.14)
Repeating the proof of Theorem D one can get
lim n → ∞ U ( k , n ) n = γ 2 ( 1 − γ ) k − 1 a . s . (1.15)
for any k = 1 , 2 , …   .
Define furthermore
R ( k , n ) : = ∑ j = k ∞ Q ( j , n ) , (1.16)
V ( k , n ) : = ∑ j = k ∞ U ( j , n ) . (1.17)
It follows that for fixed k ≥ 1  
lim n → ∞ R ( k , n ) n = γ ( 1 − γ ) k − 1 a . s . (1.18)
lim n → ∞ V ( k , n ) n = γ ( 1 − γ ) k − 1 a . s . (1.19)
The properties of these quantities were further investigated (for fixed k   ) by Pitt [8] who proved ( 1.13 ), ( 1.15 ) and ( 1.18 ), ( 1.19 ) for general random walk and by Hamana [5] , [6] who proved central limit theorems (in general case for d ≥ 3   ).
In this paper we study the question whether k   can be replaced by a sequence t ( n ) = t n ↗ ∞   of positive integers in ( 1.13 ), ( 1.15 ), ( 1.18 ) and ( 1.19 ).
Theorem Let d ≥ 3   , and define
μ = μ ( t ) : = γ ( 1 − γ ) t − 1 , (1.20)
t n : = [ ψ ( n , B ) ] , B > 2 , (1.21)
where ψ ( n , B )   is defined by ( 1.12 ). Then we have
lim n → ∞ sup t ≤ t n | U ( t , n ) n γ μ ( t ) − 1 | = 0 a . s . (1.22)
lim n → ∞ sup t ≤ t n | Q ( t , n ) n γ μ ( t ) − 1 | = 0 a . s . (1.23)
lim n → ∞ sup t ≤ t n | V ( t , n ) n μ ( t ) − 1 | = 0 a . s . (1.24)
lim n → ∞ sup t ≤ t n | R ( t , n ) n μ ( t ) − 1 | = 0 a . s . (1.25)
Here in sup t ≤ t n   , t   runs through positive integers.
( 1.25 ) of Theorem clearly implies (compare to Theorem C) Corollary Let d ≥ 3   . Then with probability 1 for any ɛ > 0   there is a random variable n 0   such that ξ ( n ) ≥ λ log n − ( 2 + ɛ ) log log n   if n ≥ n 0   .
First we present some more notations. For x ∈ Z d   let T x   be the first hitting time of 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   .
Let T = T 0   . In general, for a subset A   of Z d   , let T A   denote the first time the random walk visits A   , i.e. T A = min { i ≥ 1 : S i ∈ A } = min x ∈ A T x   . Let P x ( ⋅ )   denote the probability of the event in the bracket under the condition that the random walk starts from x ∈ Z d   . We denote P ( ⋅ ) = P 0 ( ⋅ )   .
Introduce further
q x : = P ( T < T x ) , (1.26)
s x : = P ( T x < T ) . (1.27)
In words, q x   is the probability that the random walk, starting from 0   , returns to 0   , before reaching 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 = ∞   ).

2. Preliminary facts and results

First we present some lemmas needed to prove Theorem. Introduce the following notations:
X i ( t ) = X i =
= { 1 i f S j ≠ S i ( j = 1 , 2 , … , i − 1 ) , ξ ( S i , ∞ ) ≥ t , 0 o t h e r w i s e ,
Y i ( t , n ) = Y i =
= { 1 i f S j ≠ S i ( j = 1 , 2 , … , i − 1 ) , ξ ( S i , n ) ≥ t , 0 o t h e r w i s e ,
ρ i = ρ i ( t ) = I { X i = 1 } ( min { j : ξ ( S i , j ) ≥ t } − i ) ,
μ i = μ i ( t ) = γ ( i ) ( 1 − γ ) t − 1 ,
t = 1 , 2 , …   , i = 1 , 2 , …   , where I { ⋅ }   denotes the usual indicator function.
Recall the definitions of γ ( i ) ,   γ   and μ = μ ( t )   in ( 1.4 ) ( 1.5 ) and ( 1.20 ). Furthermore let
σ n 2 = σ n 2 ( t ) : = E ( ∑ i = 1 n X i − n μ ) 2 . (2.1)
Clearly we have R ( t , n ) = ∑ i = 1 n Y i ,   V ( t , n ) = ∑ i = 1 n X i .  
Lemma 2.1. (Dvoretzky and Erdos [2] ) P ( S i ≠ S j , j = 1 , 2 , … , i − 1 ) = P ( ξ ( 0 , i − 1 ) = 0 ) = γ ( i ) .  
The following lemma is a trivial consequence of Theorem A.
Lemma 2.2. P ( n < ρ i ( t ) < ∞ ) ≤ O ( 1 ) t d / 2 n d / 2 − 1 ,   μ ≤ μ i ≤ ( 1 + O ( 1 ) i d / 2 − 1 ) μ ,   E X i = μ i .  
The next lemma can be obtained by elementary calculations.
Lemma 2.3. n μ ≤ E ∑ i = 1 n X i = ∑ i = 1 n μ i ≤ n μ + μ a n O ( 1 ) ,   where a n = ∑ i = 1 n 1 i d / 2 − 1 = { O ( 1 ) i f d > 4 , O ( 1 ) log n i f d = 4 , O ( 1 ) n 1 / 2 i f d = 3 .  
Lemma 2.4. Let n > 3 3   . Then
σ n 2 ≤ n μ + μ a n O ( 1 ) − n 2 μ 2 + 2 ( I + I I + I I I ) , (2.2)
where
I = ∑ 1 ≤ i < j ≤ n P ( X i = 1 , X j = 1 , ρ i ≥ n α ) ,
I I = ∑ 1 ≤ i < j ≤ min ( i + 3 n α , n ) P ( X i = 1 , X j = 1 , ρ i < n α ) ,
I I I = ∑ 1 ≤ i < i + 3 n α < j ≤ n P ( X i = 1 , X j = 1 , ρ i < n α ) ,
α = 2 / d .
Proof. Clearly we have
σ n 2 = E ( ∑ i = 1 n X i ) 2 + n 2 μ 2 − 2 n μ E ∑ i = 1 n X i =
= E ∑ i = 1 n X i + 2 ∑ 1 ≤ i < j ≤ n E X i X j + n 2 μ 2 − 2 n μ ∑ i = 1 n μ i ≤
≤ n μ + μ a n O ( 1 ) + 2 ∑ 1 ≤ i < j ≤ n E X i X j − n 2 μ 2 .
Further ∑ 1 ≤ i < j ≤ n E X i X j = ∑ 1 ≤ i < j ≤ n P { X i = 1 , X j = 1 } = I + I I + I I I .   Hence Lemma 2.4 is proved.
Now let A ( x )   denote the two-point set { 0 , x }   and let Ξ ( A ( x ) , ∞ ) = ξ ( 0 , ∞ ) + ξ ( x , ∞ )   denote its total occupation time.
Lemma 2.5. For x ∈ Z d , x ≠ 0   , define γ x : = P ( T x = ∞ )   and recall the definitions of q x   and s x   in ( 1.26 ) and ( 1.27 ). Then
γ e i = γ − e i = γ , i = 1 , 2 , … , d , (2.3)
γ x ≥ γ , (2.4)
q x = 1 − γ 1 − ( 1 − γ x ) 2 , (2.5)
s x = ( 1 − γ x ) ( 1 − q x ) , (2.6)
q x + s x = 1 − γ 2 − γ x , (2.7)
P ( Ξ ( A ( x ) , ∞ ) = j ) = ( 1 − q x − s x ) ( q x + s x ) j , j = 0 , 1 , … . (2.8)
Proof. We show ( 2.3 ) first. For symmetric reason, γ ± e i = γ ± e j   , i , j = 1 , … , d   . Hence 1 − γ = ∑ i = 1 d P ( S 1 = e i ) ( 1 − γ e i ) + ∑ i = 1 d P ( S 1 = − e i ) ( 1 − γ − e i ) = 2 ∑ i = 1 d 1 2 d ( 1 − γ e 1 ) = 1 − γ e 1 ,   proving ( 2.3 ).
To show ( 2.4 ), observe that starting from the origin, before hitting x   with ∥ x ∥ > 1   , the random walk should hit first the sphere S ( x , 1 ) : = { y : ∥ y − x ∥ = 1 }   . Hence
1 − γ x = P ( T S ( x , 1 ) < ∞ ) ( 1 − γ ) ≤ 1 − γ . (2.9)
Now let Z ( A )   denote the number of visits in the set A   up to the first return to zero, i.e.
Z ( A ) = ∑ n = 1 T I { S n ∈ A } . (2.10)
Observe that
P ( Z ( A ( x ) ) = j + 1 , T < ∞ ) = { q x i f j = 0 , s x 2 q x j − 1 i f j = 1 , 2 , . . . (2.11)
Summing up in ( 2.11 ) we get
∑ j = 0 ∞ P ( Z ( A ( x ) ) = j + 1 , T < ∞ ) = q x + s x 2 1 − q x = P ( T < ∞ ) = 1 − γ . (2.12)
On the other hand, one can easily see that
1 − γ = P ( T < ∞ ) = P ( T < T x ) + P ( T > T x , T < ∞ )
= P ( T < T x ) + P ( T > T x ) P x ( T < ∞ )
= P ( T < T x ) + P ( T > T x ) P ( T x < ∞ ) = q x + s x ( 1 − γ x ) ,
i.e.
1 − γ = q x + s x ( 1 − γ x ) (2.13)
Now ( 2.12 ) and ( 2.13 ) easily imply ( 2.5 ) and ( 2.6 ), hence also ( 2.7 ).
Equation ( 2.8 ) was proved in [1] for general random walk. For completeness a short proof is presented here. The probability that the random walk, starting from 0   , returns to 0   without hitting x   , is q x   , while s x   is the probability that the random walk starting from 0   hits x   without returning to 0   . Similarly, for symmetric reason, q x   is also the probability of the random walk starting from x   returns to x   without hitting 0   , and s x   is also the probability of the random walk starting from x   hits 0   in finite time, without returning to x   . Hence, the probability that the random walk starting from any point of A ( x )   , returns to A ( x )   in finite time, is q x + s x   . This gives ( 2.8 ).
Similarly to Theorem A, we prove
Lemma 2.6.
1 − γ x ( n ) : = P ( T x < n ) = 1 − γ x + O ( 1 ) n d / 2 − 1 , (2.14)
q x ( n ) : = P ( T < min ( n , T x ) ) = q x + O ( 1 ) n d / 2 − 1 , (2.15)
s x ( n ) : = P ( T x < min ( n , T ) ) = s x + O ( 1 ) n d / 2 − 1 , (2.16)
and O ( 1 )   is uniform in x   .
Proof. For the proof of ( 2.14 ) see Jain and Pruitt [7] .
To prove ( 2.15 ) and ( 2.16 ), observe that
q x − q x ( n ) = P ( T < T x , n ≤ T < ∞ ) ≤ P ( n ≤ T < ∞ ) = γ ( n ) − γ ,
s x − s x ( n ) = P ( T x < T , n ≤ T x < ∞ ) ≤ P ( n ≤ T x < ∞ ) = γ x ( n ) − γ x .
Lemma 2.7. Let i < j   . Then for t ≥ 1   integer we have
P ( X i = 1 , X j = 1 ) ≤ C μ 2 ( 1 + t d / ( d − 2 ) ( j − i ) d / 2 ( 2 2 − γ ) 2 t ) , (2.17)
where C   is a constant, independent of i , j , t   and μ = μ ( t ) = γ ( 1 − γ ) t − 1   .
Proof. Using ( 2.8 ) of Lemma 2.5, we get P ( X i = 1 , X j = 1 )   ≤ ∑ x ∈ Z d P ( S j − S i = x , ξ ( S i , ∞ ) − ξ ( S i , i ) + ξ ( S j , ∞ ) − ξ ( S j , i ) ≥ 2 t − 1 )   = ∑ x ∈ Z d P ( S j − i = x ) P ( Ξ ( A ( x ) , ∞ ) ≥ 2 t − 1 )   = ∑ x ∈ Z d P ( S j − i = x ) ( q x + s x ) 2 t − 1 = ∑ x ∈ Z d , ∥ x ∥ ≤ R + ∑ x ∈ Z d , ∥ x ∥ > R ,   where R   will be chosen later. For estimating the first sum, we use γ x ≥ γ   (cf. ( 2.4 ) of Lemma 2.5), hence by ( 2.7 ) q x + s x = 1 − γ 2 − γ x ≤ 2 ( 1 − γ ) 2 − γ .   On the other hand P ( S j − i = x ) ≤ C 1 ( j − i ) d / 2 , x ∈ Z d   with some constant C 1   , not depending on x   (cf. Spitzer [11] , page 72).
Since the cardinality of the set { ∥ x ∥ ≤ R }   is a constant multiple of R d   , we have
∑ x ∈ Z d , ∥ x ∥ ≤ R ≤ C 2 R d ( j − i ) d / 2 ( 2 ( 1 − γ ) 2 − γ ) 2 t (2.18)
with some constant C 2   .
For estimating the second sum, we use 1 − γ x ≤ C 3 R − d + 2   for ∥ x ∥ > R   (cf. Revesz [9] , page 241), hence q x + s x ≤ 1 − γ + C 4 R − d + 2 = ( 1 − γ ) ( 1 + C 4 ( 1 − γ ) R d − 2 ) .   Now choose R = t 1 / ( d − 2 )   . Then ( q x + s x ) 2 t − 1 ≤ C 5 ( 1 − γ ) 2 t .   Here the constant C 5   is independent of both x   and t   . Since ∑ x ∈ Z d P ( S j − S i = x ) = 1 ,   we have ∑ x ∈ Z d , ∥ x ∥ > R ≤ C 5 ( 1 − γ ) 2 t = C 6 μ 2 .   this together with ( 2.18 ) (putting R = t 1 / ( d − 2 )   there) proves Lemma 2.7.
In the subsequent lemmas t n   is defined by ( 1.21 ).
Lemma 2.8. For t ≤ t n   , any ɛ > 0   and large enough n   we have
I ≤ O ( 1 ) n 2 / d + ɛ ( n + ( 2 2 − γ ) 2 t n ) μ 2 ( t ) . (2.19)
Proof. Now we need to estimate the probability P ( X i = 1 , X j = 1 , ρ i ≥ n α ) .   Define the events B k   by B k = { ξ ( S i , ∞ ) − ξ ( S i , i ) + ξ ( S j , ∞ ) − ξ ( S j , i ) = k }   and consider the k   time intervals between the consecutive visits of { S i , S j }   . Then at least one of these intervals is larger than
ρ i ( t ) k ≥ n α k (2.20)
(provided that { X i = 1 , X j = 1 , ρ i ≥ n α }   ). Denote this event by D k   . Similarly to the proof of Lemma 2.7 we have P ( X i = 1 , X j = 1 , ρ i ≥ n α ) ≤ ∑ x ∈ Z d P ( S j − S i = x , ∪ k ≥ 2 t − 1 B k D k )   ≤ ∑ x ∈ Z d P ( S j − i = x ) ∑ k ≥ 2 t − 1 P ( B k D k | S j − S i = x ) .   The event B k D k   , under the condition S j − S i = x   , means that placing a new origin at the point S i   , and starting the time at i   , there are exactly k   visits in the set A ( x )   , and at least one time interval between consecutive visits is larger than n α / k   . Hence applying ( 2.8 ) of Lemma 2.5 and ( 2.15 ), ( 2.16 ) of Lemma 2.6, we get P ( B k D k | S j − S i = x ) ≤ k ( 1 − q x − s x ) ( q x + s x ) k − 1 ( q x + s x − q x ( n α k ) − s x ( n α k ) )   ≤ O ( 1 ) k ( k n α ) d / 2 − 1 ( 1 − q x − s x ) ( q x + s x ) k − 1 ≤ O ( 1 ) k d / 2 n 2 / d − 1 ( q x + s x ) k − 1 ,   where O ( 1 )   is uniform in k   and x   , hence
∑ k ≥ 2 t − 1 P ( B k D k | S j − S i = x ) ≤ O ( 1 ) n 2 / d − 1 ∑ k ≥ 2 t − 1 k d / 2 ( q x + s x ) k − 1
≤ O ( 1 ) n 2 / d − 1 t d / 2 ( q x + s x ) 2 t − 2 .
Proceeding now as in the proof of Lemma 2.7, we can estimate P ( X i = 1 , X j = 1 , ρ i ≥ n α ) ≤ O ( 1 ) t d / 2 n 2 / d − 1 μ 2 ( t ) ( 1 + t d / ( d − 2 ) ( j − i ) d / 2 ( 2 2 − γ ) 2 t )   and summing up for 1 ≤ i < j ≤ n   , we get I ≤ O ( 1 ) n 2 / d t n d / 2 ( n + t n d / ( d − 2 ) ( 2 2 − γ ) 2 t n ) μ 2 ( t ) ,   since t ≤ t n   . But t n < λ log n   , therefore any power of t n   can be estimated by n ɛ   , hence ( 2.19 ) follows.
Lemma 2.9. For t ≤ t n   , any ɛ > 0   and large enough n   we have
I I ≤ O ( 1 ) n 2 / d + ɛ ( n + n 1 − 2 / d ( 2 2 − γ ) 2 t n ) μ 2 ( t ) . (2.21)
Proof. Using the estimate in Lemma 2.7 and summing up for i , j   with 1 ≤ i < j ≤ min ( i + 3 n α , n )   , using again that t n < λ log n   , a simple calculation shows ( 2.21 ).
Lemma 2.10. For t ≤ t n   , any ɛ > 0   and large enough n   we have
I I I ≤ μ 2 ( t ) n 2 2 + O ( 1 ) n 3 / 2 μ 2 ( t ) . (2.22)
Proof. Let
A = { S i i s a n e w p o i n t i . e . S i ≠ S j j = 1 , 2 , … , i − 1 } ,
B = { ξ ( S i , i + n α ) − ξ ( S i , i ) ≥ t − 1 } ,
D = { S j i s a n e w p o i n t } ,
E = { ξ ( S j , ∞ ) − ξ ( S j , j ) ≥ t − 1 } ,
D ⊂ G = { ξ ( S j , j ) − ξ ( S j , i + 2 ( j − i ) 3 ) = 0 } ,
B ⊂ H = { ξ ( S i , ∞ ) − ξ ( S i , i ) ≥ t − 1 } .
Recall the definition of γ ( n )   in Section 1 and let j > i + 3 n α   . Then
P { X i = 1 , X j = 1 , ρ i < n α } ≤ P { A B D E } ≤
≤ P ( A B G E ) = P ( A ) P ( B ) P ( G ) P ( E ) ≤
≤ P ( A ) P ( H ) P ( G ) P ( E ) =
= γ ( i + 1 ) ( 1 − γ ) t − 1 γ ( ( j − i ) / 3 ) ( 1 − γ ) t − 1 .
Clearly we have
I I I ≤ ∑ γ ( i + 1 ) ( 1 − γ ) t − 1 γ ( ( j − i ) / 3 ) ( 1 − γ ) t − 1 ≤
≤ γ 2 ( 1 − γ ) 2 t − 2 ∑ ( 1 + O ( 1 ) ( j − i ) d / 2 − 1 ) ( 1 + O ( 1 ) i d / 2 − 1 ) ≤
≤ γ 2 ( 1 − γ ) 2 t − 2 [ ( n 2 ) + O ( 1 ) ( K + L + M ) ]
where the summations above and below go for { i , j : 1 ≤ i < i + 3 n α < j ≤ n }   and
K = ∑ 1 i d / 2 − 1 ≤ n a n ,
L = ∑ 1 ( j − i ) d / 2 − 1 ≤ n a n ,
M = ∑ 1 i d / 2 − 1 1 ( j − i ) d / 2 − 1 ≤ n a n .
Using a n = O ( 1 ) n 1 / 2   (see Lemma 2.3) we have ( 2.22 ).
Lemma 2.11. For t ≤ t n   , any ɛ > 0   and large enough n   we have
σ n 2 = O ( 1 ) [ n μ ( t ) + μ 2 ( t ) n 1.8 ] . (2.23)
Proof is based on Lemmas 2.4, 2.8, 2.9 and 2.10. The numerical values of λ   can be obtained by a result of Grif f in [4] :
1 − γ 3 = 0.341 ,
1 − γ 4 = 0.193 ,
1 − γ 5 = 0.131 ,
1 − γ 6 = 0.104 .
Consequently
λ 3 = 0.929 ,
λ 4 = 0.608 ,
λ 5 = 0.492 ,
λ 6 = 0.442 .
By using t n < λ log n   , one can verify (numerically) ( 2 2 − γ ) 2 t n < n 2 λ log ( 2 / ( 2 − γ ) ) < n 0.75   for d = 3   and hence also for all d ≥ 3   . By choosing an appropriate ɛ   and putting the estimations ( 2.19 ), ( 2.21 ), ( 2.22 ) into ( 2.2 ), we can see, that the term n 2 μ 2   cancels out and all the other terms are smaller than the right hand side of ( 2.23 ), proving Lemma 2.11.
Lemma 2.11 implies
Lemma 2.12. For any 0 < C < B   , t ≤ t n   and large enough n   we have σ n ( log n ) C / 2 ≤ O ( 1 ) ( ( n μ ( t ) ) 1 / 2 ( log n ) C / 2 + μ ( t ) n 0.9 ( log n ) C / 2 ) = o ( 1 ) n μ ( t ) .  

3. Proof of the Theorem

First we prove ( 1.24 ).
By Markov’s inequality for any C > 0   we have P ( | V ( t , n ) − n μ ( t ) | ≥ σ n ( log n ) C / 2 ) ≤ ( log n ) − C .   By Lemma 2.12, if C < B   , P ( | V ( t , n ) − n μ ( t ) | ≥ o ( 1 ) n μ ( t ) ) ≤ ( log n ) − C .   Consequently, since t n < λ log n   ,
P ( sup t ≤ t n + 1 | V ( t , n ) − n μ ( t ) | n μ ( t ) ≥ o ( 1 ) ) ≤ O ( 1 ) ( log n ) − C + 1 . (3.1)
Choose C > 2 , n ( k ) = exp ( k / log k )   . ( 3.1 ) and Borel-Cantelli lemma imply
lim k → ∞ sup t ≤ t ( n ( k ) ) + 1 | V ( t , n ( k ) ) n ( k ) μ ( t ) − 1 | = 0 a . s . (3.2)
Let n ( k ) ≤ n < n ( k + 1 )   . Then for t ≤ t n   we have V ( t , n ( k ) ) ≤ V ( t , n ) ≤ V ( t , n ( k + 1 ) )   and lim k → ∞ n ( k + 1 ) n ( k ) = 1 .   Hence for any ɛ > 0   and large enough n   , V ( t , n ) n μ ( t ) ≤ V ( t , n ( k + 1 ) ) n ( k + 1 ) μ ( t ) n ( k + 1 ) n ≤ ( 1 + ɛ ) a . s . ,   since t ≤ t n ≤ t ( n ( k + 1 ) )   . Similarly, V ( t , n ) n μ ( t ) ≥ V ( t , n ( k ) ) n ( k ) μ ( t ) n ( k ) n ≥ ( 1 − ɛ ) a . s .   Hence we have ( 1.24 ).
Now we turn to the proof of ( 1.25 ).
Let M ( t , n ) = V ( t , n ) − R ( t , n ) = ∑ i = 1 n ( X i − Y i ) .   Observe that X i ≥ Y i   and hence M ( t , n )   is non-negative and non-decreasing in n   . Moreover, by Lemma 2.2 E ( X i − Y i ) = P ( X i − Y i = 1 ) ≤ P ( X i = 1 , n − i ≤ ρ i ( t ) < ∞ ) ≤ O ( 1 ) μ ( t ) t d / 2 ( n − i ) d / 2 − 1 .   Consequently 0 ≤ E M ( t , n ) n μ ( t ) ≤ O ( 1 ) ( log n ) d / 2 n 1 / 2 .   By Markov’s inequality P ( sup t ≤ t n M ( t , n ) n μ ( t ) > ɛ ) ≤ O ( 1 ) ( log n ) d / 2 + 1 n 1 / 2 .   On choosing n k = k 2 + δ   , δ > 0   , Borel-Cantelli lemma implies lim k → ∞ sup t ≤ t n k M ( t , n k ) n k μ ( t ) = 0 a . s .   Using the monotonicity of M ( t , n )   in n   , interpolating between n k   and n k + 1   we get lim n → ∞ sup t ≤ t n M ( t , n ) n μ ( t ) = 0 a . s .   This combined with ( 1.24 ) gives ( 1.25 ).
( 1.23 ) and ( 1.22 ) are immediate from ( 1.25 ) and ( 1.24 ), since Q ( t , n ) = R ( t , n ) − R ( t + 1 , n )   and U ( t , n ) = V ( t , n ) − V ( t + 1 , n )   .
This completes the proof of the Theorem. References

  1. Csaki, E., Foldes, A., Revesz, P., Rosen, J., Shi, Z., 2005. Frequently visited sets for random walks. Stochastic Process. Appl., to appear.
  2. Dvoretzky, A., Erdos, P., 1951. Some problems on random walk in space. Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley, pp. 353–367.
  3. Erdos, P., Taylor, S.J., 1960. Some problems concerning the structure of random walk paths. Acta Math. Acad. Sci. Hungar. 11, 137–162.
  4. Griffin, P., 1990. Accelerating beyond the third dimension: returning to the origin in simple random walk. Math. Scientist 15, 24–35.
  5. Hamana, Y., 1992. On the central limit theorem for the multiple point range of random walk. J. Fac. Sci. Univ. Tokyo 39, 339–363.
  6. Hamana, Y., 1995. On the multiple point range of three dimensional random walk. Kobe J. 12, 95–122.
  7. Jain, N.C., Pruitt, W.E., 1971. The range of transient random walk. J. Analyse Math. 24, 369–393.
  8. Pitt, J.H., 1974. Multiple points of transient random walk. Proc. Amer. Math. Soc. 43, 195–199.
  9. Revesz, P., 1990. Random Walk in Random and Non-Random Environments. World Scientific, Singapore.
  10. Revesz, P., 2004. The maximum of the local time of a transient random walk. Studia Sci. Math. Hungar. 41, 379–390.
  11. Spitzer, F., 1976. Principles of Random Walk, 2nd. ed. Van Nostrand, Princeton.

1   Corresponding author. Research supported by the Hungarian National Foundation for Scientif ic Research, Grant No. T 037886 and T 043037.

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

3   Research supported by the Hungarian National Foundation for Scientif ic Research, Grant No. T 037886 and T 043037.