Perhaps the first result on the range of random walks is that of Dvoretzky and
Erd¨ os [13]. They proved a strong law of large numbers for the range of a random
walk for a number of cases, including simple random walk in dimensions 2 and
1, a.s.
This strong law was extended by Jain and Pruitt [20] to more general random
walks, in particular, for any recurrent random walk in 2 dimensions. (The paper
[20] improves upon the results in [19].) In each of these papers, the key is obtaining
a good estimate on Var Rn. Turning to central limit theorems, the paper [20]
showed that in one dimension for finite variance walks, Rn/ERn converges in law
to the size of the range of one-dimensional Brownian motion if EX1 = 0 and
Rn ERn
(Var Rn)1/2
converges in law to a standard normal if EX1 = 0. Jain and Orey [18] showed the
same convergence for strongly transient random walks; in the case of finite variance
with mean 0, this means that the dimension is 5 or larger. Jain and Pruitt [21]
later established the analogous results for dimensions 3 and 4. In 3 dimensions, the
variance of Rn is O(n log n), while in 4 dimensions the variance is O(n). In both
cases, the expectation of the range is O(n). For random walks without moment
conditions and for a weak invariance principle, see [23]. The central limit theorem
for the range in two dimensions was not accomplished until LeGall [24]. In this
paper LeGall proved the remarkable result that
Rn ERn
n/(log n)2

where the convergence is in law, X1 has the identity as its covariance matrix, and γ1
is the renormalized self-intersection local time of a planar Brownian motion. (We
will discuss intersection local times in a bit.) The result of LeGall can be extended
to the case where X1 has an arbitrary nondegenerate covariance matrix in a routine
The central limit theorem for random walks in the domain of attraction of a
stable law was analyzed in [27]. It is noteworthy that in this case the results depend
on the relationship between the dimension and the index of the stable law.
The law of the iterated logarithm for the range of random walks in 4 or more
was established by Jain and Pruitt [22], where they showed that
lim sup
Rn ERn
(2n log log n)1/2
= 1, a.s.
Previous Page Next Page