CHAPTER 2 History 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 larger: (2.1) Rn ERn 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 (2.2) Rn ERn n/(log n)2 −4π2γ1, 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 fashion. 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 n→∞ Rn ERn (2n log log n)1/2 = 1, a.s. 5
Previous Page Next Page