Random Walks and Brownian Motion

Random Walks and Brownian Motion (0366-4758-01)

Spring 2011, Tel Aviv University

Location: Dan David 204, Mondays 16-19

Syllabus: The course will explore the properties of random walks and Brownian motion. In the first part of the course we will focus on simple random walks on the integers Z and the lattice Z^d. We will explore recurrence/transience of the walks, sample path properties, the average amount of visits to a point (Green's function), the range of values taken by the walk, the probability that the walk will visit a given set, the chance that two independent walks will intersect and related questions. We will highlight the relation between simple random walks and harmonic functions and make use of martingales to exploit it.
In the second part of the course we will focus on Brownian motion. We will explain its definition and relation to random walks, and explore its properties such as non-differentiability of the paths, symmetry, Hausdorff dimension of its range, special points, random variables associated to it, conformal invariance in 2D and its relation to differential equations.
Additional topics if time permits include: random walks on finite and general graphs, heavy-tailed random walks, Itō calculus.

Prerequisites: be a graduate student who has done introduction to probability and has additional relevant background such as the courses probability for mathematicians, real analysis or similar courses.

Announcements

There will be no classes on March 14'th and May 30'th since I will be away. Makeup classes have been scheduled for Friday, April 29'th and Friday, May 13'th (there will be no class on these weeks due to Passover and Memorial day). The hours of the makeup classes will be announced as the date approaches.

The first makeup class will be on Friday, April 29'th, from 10:00 to 13:00 at the Shenkar Physics building room 105.

The second makeup class will be on Friday, May 13'th, from 10:00 to 13:00 at the Shenkar Physics building room 105.

Requirements

Several mandatory homework assignments will be given during the course. Additionally, every student will need to scribe at least one lecture in Latex format using the following template. We may also have some student presentations of additional topics in the end of the course.

Exercise 1. The exercise needs to be handed in by May 2'nd in class.

Exercise 2. The exercise needs to be handed in by May 23'rd in class.

Exercise 3. The exercise needs to be handed in by July 12'th by email or to the instructor's mail box on the first floor of Schreiber building.

Lectures so far

Lecture 1 (21.2): Introduction, gambler's ruin for 1D SRW, recurrence of 1D SRW, stopping times and the strong Markov property, first passage time distribution for skip-free RW, reflection principle - ballot theorem and distribution of maximum, introduction to Wald identities. This talk is based on the excellent lecture notes of Steven Lalley. The ballot theorem treatment follows Feller, vol. 1, chapter 3.

Lecture 2 (28.2): Wald identities, derivation of the moment generating function of the first passage time for 1D SRW, arcsine laws for the last zero and fraction of time above axis, time reversal and applications to ladder times and additional arcsine laws, uniform distribution for fraction of time above axis for SRW bridge. The treatment of Wald identities and the application to the first passage time mgf are based on the notes of Lalley. The rest of the class follows the treatment in Feller vol. 1, chapter 3.
Scribe notes by David Lagziel.

Lecture 3 (7.3): LCLT for 1D SRW, Law of the iterated logarithm for 1D SRW, General RW: permutable events and the Hewitt-Savage 0-1 law, application to the possible limiting behavior of 1D RW's. The treatment of the LCLT and law of the iterated logarithm follows a combination of the proofs in Durrett, Feller and Peres' BM book. The Hewitt-Savage law and application follow Durrett.
Scribe notes by Aya Vituri.

Lecture 4 (21.3): Possible values, recurrence and transience for general RW's. Point-recurrence vs. neighbourhood-recurrence. Polya's thm: SRW on Z^d is recurrent iff d=1,2. Statement of the Chung-Fuchs thm.: sufficient criteria for neighbourhood-recurrence or transience of a general RW in R^d. Strong law of large numbers and the Birkhoff ergodic theorem. The Kesten-Spitzer-Whitman theorem on the range of a RW. Application: mean zero RW in 1D are recurrent. Fourier-analytic criterion for recurrence of RW. Discussion of recurrence for 1D stable RW. Most of the class follows the treatment in Durrett. The ergodic theorem, KSW theorem and its application follows the notes of Lalley.
Scribe notes by Liran Rotem.

Lecture 5 (28.3): Proof of 2D Chung-Fuchs recurrence criterion for Z^2 RW's. Intuition behind d≥3 transience criterion. Crash course on Martingale theory: definitions, optional sampling, maximal inequality and convergence theorems. Harmonic functions on graphs: definition, relation to SRW on the graph, definitions of Poisson boundary and Liouville property. Examples on Z^d and a regular tree. Proof that on connected, recurrent graphs non-negative harmonic functions are constant. CF theorem treatment follows Durrett. Martingale treatment follows appendix in Lawler-Limic book and Durrett. Harmonic function discussion based on Durrett (chap. 6.7), Kallenberg, Kaimanovich-Vershik paper and unpublished notes of Robin Pemantle.
Scribe notes by Yishai Kohn.

Lecture 6 (4.4): Relation between harmonic functions, space-time harmonic functions, the invariant sigma-field, the tail sigma-field and successful couplings and shift-couplings. Equivalences between various properties of these. The coupling inequality for the mixing of Markov chains. Maximal couplings. Examples: SRW on Z^d, irreducible recurrent chains, long range 1D RW's (Ornstein's coupling), SRW on regular trees. Discussion on Poisson boundary of groups: Kaimanovich-Vershik theorem, example of lamplighter groups and some open questions. Discussion borrows material from the books of Durrett (chapter 6.7), Lindvall and Thorisson, and the paper of Kaimanovich and Vershik.
Scribe notes by Eyal Weinberger.

Lecture 7 (11.4): Introduction to potential theory: Harmonic functions on Z^d and the dirichlet problem - criterion for a unique solution, Poisson equation and Green's function in a domain, analogy to continuous case. Local central limit theorem for SRW on Z^d - statement and idea of proof. Green's function - introduction, some asymptotics and application showing that the expected range of an n-step 2D SRW is order n/logn. Treatment follows books of Lawler-Limic and Lawler.
Scribe notes by Yoav Ram.

Lecture 8 (29.4): Asymptotics for Green's functions - For d≥3, G(x)~c_d|x|^2-d. Application to exit probabilities of annuli (quantitative transience). Relation to Green's function in domain and application to number of visits to 0 before exiting ball. Asymptotics of 1D and 2D potential kernel and application to exit probabilities of annuli (quantitative recurrence). Martin capacity for Markov chains: Martin capacities of sets and application to hitting probabilities. Intersection of random walks: Probability that S[0,n] intersects S[2n,3n] for a SRW. Overview of intersection exponents in dimensions d<=4. Green's function section based on Lawler-Limic, Martin capacity treatment follows Benjamini-Pemantle-Peres and intersection of random walks section follows Lawler-Limic.
Scribe notes by Uri Grupel.

Lecture 9 (2.5): Introduction and motivation for Brownian Motion. Definition of BM. Background on Gaussian RVs. Lévy's construction of BM. Upper and lower bounds for the modulus of continuity of BM. Treatment follows Mörters and Peres book.
Scribe notes by Jonathan Hermon.

Lecture 10 (13.5): Discussion of modulus of continuity and Hölder continuity of BM. Proof that BM is a.s. nowhere differentiable. Scaling invariance and time inversion invariance of the distribution of BM. Definition of the Ornstein-Uhlenbeck process. Applications to the growth rate at 0 and infinity of BM. Proof that BM has no interval of monotonicity. Definition of d-dimensional BM. Markov property of BM. Blumenthal's zero-one law (that germ sigma-field is trivial for a BM). Application to showing that tail sigma-field is trivial for BM. Treatment follows Mörters and Peres book.
Scribe notes by Assa Naveh.

Lecture 11 (16.5): Application of Markov property to properties of local maxima of BM. Stopping times for BM and discussion of choice of filtration. Sigma-field of a stopping time. The strong Markov property of BM. The reflection principle for BM and application to the distribution of the maximum of a BM. Application to showing area of planar BM is a.s. zero (Lévy's theorem), to showing that planar BM does not visit (pre-fixed) points a.s. and to showing that the zero set of a 1D BM is a.s. a perfect set (closed with no isolated points). Treatment follows Mörters and Peres book.
Scribe notes by Jun Chen.

Lecture 12 (23.5): Definition of continuous martingales and sub-martingales in continuous time. Example: 1D BM is a continuous martingale. Statement of optional stopping theorem in continuous time. Wald's first and second lemmas for BM. Application to calculating for 1D BM in an interval its exit probabilities and expected exit time. The Skorohod embedding problem. Example of Skorohod embedding for a random variable taking two values. The Azéma-Yor embedding theorem. Discussion of convergence in distribution for random continuous functions. The Donsker invariance principle: motivation (as a universality theorem for RWs) and proof (with some details omitted at end). Treatment follows Mörters and Peres book.
Scribe notes by Naomi Feldheim.

Lecture 13 (6.6): An application of the Donsker invariance principle to the distribution of maxima of random walks. Introduction to stochastic integration for L_2 processes: Discrete motivation, definition, continuity, isometry and martingale properties. Ito's formula in one and several dimensions. Informal description of conformal invariance of 2D Brownian motion. Treatment follows Mörters and Peres book.
Scribe notes by Jacob Kagan.

Recommended reference notes and books

1) Steven Lalley has written excellent lecture notes covering some of the basics of 1D random walks.

2) The acclaimed two-volume book of William Feller: An introduction to probability theory and its applications, has some chapters with an excellent exposition to one-dimensional random walks. Some information is given also on the higher dimensional setting.

3) The recent book "Brownian Motion" by Mörters and Peres will be the basis for much of our treatment of Brownian motion. An older version is available on Peter Mörters homepage.

4) The book "Intersection of random walks" by Gregory F. Lawler provides detailed information on some aspects of Z^d simple random walks including Green's functions, potential theory and estimates for the amount of intersections of independent walks.

5) The book "Probability: Theory and Examples" by Rick Durrett has several sections on random walks and Brownian motion. It is also an excellent reference for general probability theory and measure theory for those who need additional background. The new fourth edition is available on Rick's website (but not for long!).

6) Frank Spitzer's "Principles of random walk" contains a huge amount of material on general Z^d random walks.

7) The book "Random walk: a modern introduction" by Lawler and Limic is a modern introduction to the theory with a focus on very precise Green's function and capacity estimates for somewhat general random walks. An older version of the book and some very basic probability notes are available on Greg Lawler's website.

8) The book "Foundations of Modern Probability" by Olav Kallenberg contains a wealth of material on probability theory in general including random walks, Markov chains, martingales and Brownian motion. The second edition contains a discussion of the ergodic properties of Markov processes including some relations with harmonic functions.

9) The book "Probability with Martingales" by David Williams contains a thorough discussion of martingales in discrete time.

10) The book "Coupling, Stationarity and Regeneration" by Hermann Thorisson contains a modern development of the theory of coupling, shift-coupling and its applications including relations to various sigma-fields and notions of harmonic functions. The book "Lectures on the coupling method" by Torgny Lindvall is an earlier treatment of the subject.

11) The book in preparation "Probability and geometry on groups" by Gábor Pete has a lot of information about random walks and other probabilistic structures on groups.

12) We will go over the papers "Martin capacity for Markov chains" by Benjamini, Pemantle and Peres (1995) and "On the support of harmonic measure for the random walk" by Benjamini (1996). We will also refer to some results from the paper "Random Walks on Discrete Groups: Boundary and Entropy" by Kaimanovich and Vershik (1983).