Random Walks and Brownian Motion (0366-4758-01)
Spring 2011, Tel Aviv University
Location: Dan David 204, Mondays 16-19
Instructor: Ron Peled
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 Zd. 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.
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.
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
Lalley. The rest of the
class follows the treatment in Feller vol. 1, chapter 3.
Scribe notes by David Lagziel.
(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.
(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
Scribe notes by Liran Rotem.
(28.3): Proof of 2D Chung-Fuchs recurrence criterion for Z^2 RW's. Intuition
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
Scribe notes by Yishai Kohn.
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.
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
Scribe notes by Yoav Ram.
8 (29.4): Asymptotics for Green's functions - For d≥3, G(x)~cd|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
Scribe notes by Uri Grupel.
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.
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.
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.
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.
(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 Zd 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 Zd 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).