6 2. HISTORY

and that the corresponding lim inf is −1 a.s.

For 2 and 3 dimensions, the law of the iterated logarithm was proved by Bass

and Kumagai [5]. In 3 dimensions

(2.3) lim sup

n→∞

Rn − ERn

(n log n log log n)1/2

=

(p2/π)

√

det Γ, a.s.,

where Γ is the covariance matrix of X1 and p = P(Sk = 0 for all k). The cor-

responding lim inf is the negative of this constant. These (and other laws of the

iterated logarithm) are consequences of an invariance principle. In [5] it was proved

that if the random walk is three dimensional, then there exists a one-dimensional

Brownian motion such that

(2.4)

Rn − ERn

(

√

2p2/2π

√

det Γ)

− Bn

log n

= O(

√

n(log

n)15/32).

The law of the iterated logarithm for the range in 2 dimensions was a bit

surprising:

(2.5) lim sup

n→∞

Rn − ERn

n log log log n/(log n)2

= c1, a.s.

provided the random walk had bounded range and where c1 is an unidentified

constant. Among the results in the current paper is that we identify the constant,

we remove the restriction of bounded range, and we determine the corresponding

lim inf.

An almost sure invariance principle for Rn − ERn in 4 or more dimensions was

proved by Hamana [15]. There the result is that there exists a one-dimensional

Brownian motion Bt such that for each λ 0

(2.6)

Rn − ERn

(Var Rn)1/2

− Bn =

O(n2/5+λ).

The almost sure invariance principle for random walks in 2 dimensions is more

complicated. Bass and Rosen [6] showed that if the random walk has mean 0, has

the identity as the covariance matrix, and has 2 + δ moments for some δ 0, then

for each k

(2.7) (log

n)k

Rn

n

+

k

j=1

(−1)j

log n

2π

+ cX

−j

γj,n → 0, a.s.

where Wt is a 2-dimensional Brownian motion, cX is a constant depending on the

random walk, and γj,n is the renormalized self-intersection local time of order j at

time 1 of the Brownian motion

Wt(n)

= Wnt/

√

n. The intuition behind this formula

is the following: at time n, if the process hits a point it has already hit before, then

n − Rn increases by 1, and so does the number of self-intersections of the random

walk. If the point that is hit again has only been hit once before, then the double

self-intersections of the random walk increases by 1, but if this point has been hit a

number of times, then the double self-intersections will go up more than 1, and this

has to be compensated by subtracting off the number of triple self-intersections,

and so on.

Large deviations for the range have been considered by Donsker and Varadhan

[12], by Hamana [16], and by Hamana and Kesten [17]. These are related to