Reading Seminar - Probability on trees

Aims of the course

In this course I would like to give a first impression on the subject of stochastic processes in random environments by looking at stochastic processes on random trees. In particular, I would like to explore to what extent processes in inhomogeneous environments can behave differently from processes in homogeneous environments. Random trees can be an accessible model for such inhomogeneous environments.

Particular subjects I would like to cover:

  • Random walk on trees (recurrence and transience, speed, etc.)
  • Percolation on trees
  • Limit theorems for Galton-Watson trees
  • Hausdorff dimension
  • Capacity and flows on trees
  • Harmonic measure on Galton-Watson trees
  • Ising model on trees

Prerequisites and format

To take this course you should have a good background in measure-theoretic probability. For former University of Bath Undergraduates this means successful participation in the course Ma40058 Martingale Theory.

In the first two lectures I will give an introduction to the subject. Then the participants will take over and the course will take the format of a reading seminar. Participants will cover special topics in the form of oral presentations. Every participant will have to present at least one topic, in the case of a small number of participants up to two.

Assessment

If you are attending this course for credit, your presentation will be attended by a second examiner and followed by a brief interview/question session. No further exam is necessary.

Talk subjects

We have time for eight contributed talks.
Here are the proposed subjects, titles in red are still available:
  • Random walks and electric networks
     Material from (1) (Section 2.1 to 2.3).
    Highlight: Transience of a random walk is equivalent to positive effective conductance of the network.
  • Energy and flows on trees.
     Material from (1) (Section 2.4 to 2.8).
    Highlight: Polya's theorem and transience/recurrence for homesick random walk.
  • Percolation on trees.
     Material from (1) (Section 4.1 to 4.4).
    Highlight: Percolation occurs iff the random walk is transient.
  • Limit theorems for Galton-Watson trees.
     Material from (1) (Section 10.1 to 10.4).
    Highlight: A conceptual proof of the Kesten-Stigum theorem using size-biased trees.
  • Speed of simple random walk on trees
     Material from (2) (Section 1 to 3).
    Highlight: Formula for the speed of SRW on a Galton-Watson tree.
  • Local dimension of the harmonic measure
    Material from (2) (Section 4 to 8).
    Highlight: Formula for the local dimension of the harmonic measure.
  • Biased random walks with outward bias
     Material from (3) (Section 1 to 4).
    Highlight: A beautiful big-drift-small-speed result.
  • Biased random walks with inward bias
     Material from (1) (Section 12.1) and (3) (Section 5).
    Highlight: Comparing Hausdorff dimensions of the harmonic measures of various homesick walks.
Please see me if you have any questions.

Material

  • (1) Probability on trees and networks
     by Russell Lyons with Yuval Peres.
    Book manuscript available from Russell Lyons homepage.
  • (2) Ergodic Theory on Galton-Watson trees: Speed of random walk and dimension of harmonic measure.
     By Russell Lyons, Robin Pemantle and Yuval Peres.
    Ergodic Theory Dynam. Systems 15 (1995), no. 3, 593--619 or preprint version from authors' homepages.
  • (3) Biased random walks on Galton-Watson trees.
     By Russell Lyons, Robin Pemantle and Yuval Peres.
    Probab. Theory Related Fields 106 (1996), no. 2, 249--264 or preprint version from authors' homepages.

Further resources

Download the introductory survey talk here.
Download the the submartingale argument from Matt's talk here.
Download the slides for Adam's talk here.
Download the slides for Marcel's talk here.

Times

The seminar will take place on Fridays 11:15 in Room 1W3.24.

This web page was last updated on Monday, November 27th, 2006.