Random Walk: A Modern Introduction

1 Random Walk: A Modern IntroductionGregory F. Lawler and Vlada LimicContentsPrefacepage61 Basic Continuous-time Random Other Other Filtrations and strong Markov A word about constants212 Local Central Limit Characteristic Functions and Characteristic functions of Random variables Characteristic functions of Random variables LCLT characteristic function Exponential Some corollaries of the LCLT combinatorial Stirling s formula and LCLT for Poisson and continuous-time walks563 Approximation by Brownian Construction of Brownian Skorokhod Higher An alternative formulation724 Green s Recurrence and Green s generating Green s function.

2 Transient Asymptotics under weaker Potential Two Asymptotics under weaker One Fundamental Green s function for a set965 One-dimensional Gambler s ruin General One-dimensional killed Hitting a half-line1156 Potential Dirichlet Difference estimates and Harnack Further Capacity, transient Capacity in two Neumann Beurling Eigenvalue of a set1577 Dyadic Some Quantile The dyadic Proof of Theorem Higher Coupling the exit distributions1778 Addtional topics on Simple Random Poisson Half Strips and quadrants Eigenvalues for Approximating continuous harmonic Estimates for the ball1939 Loop Definitions and Simple Random walk on a Generating functions and loop Loop Loop Boundary Wilson s algorithm and spanning Complete Sierpinski Spanning trees of subsets Gaussian free field23010 Intersection Probabilities for Random Long range Short range One-sided exponent24311 Loop-erased

3 Random Loop-erased Random LERW Rate of Short-range intersections25712 Some Riemann Optional Sampling Maximal Continuous Joint normal Markov Chains restricted to Maximal coupling of Markov Some Tauberian Second moment Subadditivity281 References285 Index of Symbols286 Index288 PrefaceRandom walk the stochastic process formed by successive summation of independent, identicallydistributed Random variables is one of the most basic and well-studied topics in probabilitytheory. For Random walks on the integer latticeZd, the main reference is the classic book bySpitzer [16]. This text considers only a subset of such walks, namely those corresponding toincrement distributions with zero mean and finite this case, one can summarize themain result very quickly: the central limit theorem impliesthat under appropriate rescaling thelimiting distribution is normal, and the functional central limit theorem implies that the distributionof the corresponding path-valued process (after standard rescaling of time and space) approachesthat of Brownian who work with perturbations of Random walks, orwith particle systems and othermodels that use Random walks as a basic ingredient, often need more precise information on randomwalk behavior than that provided by the central limit theorems.

4 In particular, it is important tounderstand the size of the error resulting from the approximation of Random walk by Brownianmotion. For this reason, there is need for more detailed analysis. This book is an introductionto the Random walk theory with an emphasis on the error estimates. Although mean zero, finitevariance assumption is both necessary and sufficient for normal convergence, one typically needsto make stronger assumptions on the increments of the walk inorder to get good bounds on theerror project embarked with an idea of writing a book on the simple, nearest neighbor randomwalk. Symmetric, finite range Random walks gradually becamethe central model of the class of walks, while being rich enough to require analysis by general techniques, can bestudied without much additional difficulty.

5 In addition, forsome of the results, in particular, thelocal central limit theorem and the Green s function estimates, we have extended the discussion toinclude other mean zero, finite variance walks, while indicating the way in which moment conditionsinfluence the form of the first chapter is introductory and sets up the notation. Inparticular, there are three mainclasses of irreducible walks in the integer latticeZd Pd(symmetric, finite range),P d(aperiodic,mean zero, finite second moment), andP d(aperiodic with no other assumptions). Symmetricrandom walks on other integer lattices such as the triangular lattice can also be considered bytaking a linear transformation of the lattice local central limit theorem (LCLT) is the topic for Chapter 2.

6 Its proof, like the proof of theusual central limit theorem, is done by using Fourier analysis to express the probability of interest6 Preface7in terms of an integral, and then estimating the integral. The error estimates depend stronglyon the number of finite moments of the corresponding increment distribution. Some importantcorollaries are proved in Section ; in particular, the fact that aperiodic Random walks startingat different points can be coupled so that with probability 1 O(n 1/2) they agree for all timesgreater thannis true for any aperiodic walk, without any finite moment assumptions. The chapterends by a more classical, combinatorial derivation of LCLT for simple Random walk using Stirling sformula, while again keeping track of error motion is introduced in Chapter 3.

7 Although we would expect a typical reader toalready be familiar with Brownian motion, we give the construction via the dyadic splitting estimates for the modulus of continuity are given as well. We then describe the Skorokhodmethod of coupling a Random walk and a Brownian motion on the same probability space, andgive error estimates. The dyadic construction of Brownian motion is also important for the dyadiccoupling algorithm of Chapter Green s function and its analog in the recurrent setting, the potential kernel, are studiedin Chapter 4. One of the main tools in the potential theory of Random walk is the analysis ofmartingales derived from these functions. Sharp asymptotics at infinity for the Green s functionare needed to take full advantage of the martingale technique.

8 We use the sharp LCLT estimates ofChapter 2 to obtain the Green s function estimates. We also discuss the number of finite momentsneeded for various error 5 may seem somewhat out of place. It concerns a well-known estimate for one-dimensionalwalks called the gambler s ruin estimate. Our motivation for providing a complete self-containedargument is twofold. Firstly, in order to apply this result to all one-dimensional projections of ahigher dimensional walk simultaneously, it is important toshiw that this estimate holds for non-lattice walks uniformly in few parameters of the distribution (variance, probability of making anorder 1 positive step). In addition, the argument introduces the reader to a fairly general techniquefor obtaining the overshoot estimates.

9 The final two sections of this chapter concern variations ofone-dimensional walk that arise naturally in the argumentsfor estimating probabilities of hitting(or avoiding) some special sets, for example, the Chapter 6, the classical potential theory of the Random walk is covered in the spirit of [16]and [10] (and a number of other sources). The difference equations of our discrete space setting(that in turn become matrix equations on finite sets) are analogous to the standard linear partialdifferential equations of (continuous) potential theory. The closed form of the solutions is important,but we emphasize here the estimates on hitting probabilities that one can obtain using them. Themartingales derived from the Green s function are very important in this analysis, and again specialcare is given to error terms.

10 For notational ease, the discussion is restricted here to symmetric fact, most of the results of this chapter hold for nonsymmetric walks, but in this case one mustdistinguish between the original walk and the reversed walk, between an operator andits adjoint. An implicit exercise for a dedicated student would be to redo this entire chapter fornonsymmetric walks, changing the statements of the propositions as necessary. It would be morework to relax the finite range assumption, and the moment conditions would become a crucialcomponent of the analysis in this general setting. Perhaps this will be a topic of some future 7 discusses a tight coupling of a Random walk (that has a finite exponential moment)and a Brownian motion, called the dyadic coupling or KMT or Hungarian coupling, originated inK omlos, Major, and Tusn ady [7, 8].