Random Walk: A Modern Introduction - University of Chicago

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, 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.

2 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 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.

3 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. In particular, it is important tounderstand the size of the error resulting from the approximation of Random walk by Brownianmotion.

4 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. 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.

5 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. 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.

6 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. 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.

7 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. 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).

8 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. 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.

9 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]. The idea of the couplingis very natural (once explained), but8 Prefacehard work is needed to prove the strong error estimate. The sharp LCLT estimates from Chapter2 are one of the key points for this bounded rectangles with sides parallel to the coordinatedirections, the rate of convergence ofsimple Random walk to Brownian motion is very fast. Moreover, in this case, exact expressions areavailable in terms of finite Fourier sums. Several of these calculations are done in Chapter 9 is different from the rest of this book. It covers an area that includes both classicalcombinatorial ideas and topics of current research. As has been gradually discovered by a numberof researchers in various disciplines (combinatorics, probability, statistical physics) several objectsinherent to a graph or network are closely related: the number of spanning trees, the determinantof the Laplacian, various measures on loops on the trees, Gaussian free field, and loop-erased give an Introduction to this theory, using an approach that is focused on the (unrooted) randomwalk loop measure, and that uses Wilson s algorithm [18] forgenerating spanning original outline of this book put much more emphasis on the path-intersection probabilitiesand the loop-erased walks.

10 The final version offers only a general Introduction to some of the mainideas, in the last two chapters. On the one hand, these topicswere already discussed in moredetail in [10], and on the other, discussing the more recent developments in the area would requirefamiliarity with Schramm-Loewner evolution, and explaining this would take us too far from themain of the content of this text (the first eight chapters in particular) are well-known classicalresults. It would be very difficult, if not impossible, to givea detailed and complete list of refer-ences. In many cases, the results were obtained in several places at different occasions, as auxiliary(technical) lemmas needed for understanding some other model of interest, and were therefore notparticularly noticed by the community. Attempting to give even a reasonably fair account of thedevelopment of this subject would have inhibited the conclusion of this project.