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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.