Random Walks at Notre Dame
I'm super happy to be able to give a short course on random walks at the Thematic program on Boundaries and Dynamics 2015 at Notre Dame.
These are the notes I've prepared for the course.The basic bibliography is Woess's book "Random walks on infinite graphs and groups" as well as the book by Russel Lyons and Yuval Peres which is available for free online.
I'll try to add more resources as things evolve.
Lecture 1
We started with a 1 hour lecture whose objective was to introduce the general concepts of random walks informally and give a few examples.
The first example was PageRank, which is based on the so-called "Random surfer model". It was an important innovations to search engines in the late 90's and the basic concept is to model the internet as a finite graph and rank pages according to how much time a random walk would spend on them.
Then we got to the actual point of these lectures which is to study the simple random walks (i.e. at each step pick a random neighbor of the current vertex and go there) on infinite (connected, undirected, locally finite) graphs.
At an informal level of rigor we introduced recurrence and transience and the statement of Pólya's theorem from the 1920s.
We then gave examples in two families of graphs. Trees and Cayley graphs.
Richard Feynman used to say that the method to being a genius is to have list of favorite questions and then each time you hear of new technique try to apply it to the questions on your list. One day it will work and you will look like a genius.
In this course I hope the students will have the following list of questions and examples in there head and try to apply each result we learn to them.
The questions are: On which infinite graphs is the simple random walk recurrent? Can a transient graph be made recurrent by subdividing its edges? Can a transient graph be made recurrent by adding edges? Can two Cayley graphs for the same group exhibit different behavious (i.e. can one be recurrent and the other transient?)?
The tree examples are: Regular tree of degree 3, Radially symmetric trees (especially coming from sequences of ones and twos), Self similar trees, the canopy trees.
The Cayley graph examples are: Z^d, the free group on 2 generators, the wallpaper group *632, the lampligher group on Z, the nilpotent group or heisenberg group NIL, and the modular group.
In the second lecture I plan to briefly review the main questions and examples (including the few we didn't have time for this lecture). After which we can start proving our first theorem: the so-called "Flow theorem" from the mid 1980s which is a geometric criterion for recurrence or transience of an infinite graph.
Lecture 2
This was an hour and a half long lecture (poor students).
We started out reviewing the questions and examples (this meant introducing the Canopy tree, the Modular group, and the Heisenberg group).
Next we gave a (very formal) definition of a graph (an undirected, locally finite, conected graph).
We also defined a simple random walk starting at a vertex in a graph. At least well enough to calculate any probability involving any finite number of coordinates of the random walk.
We defined Transience and Recurrence of a simple random walk. And we reviewed the results one gets from measure-theoretic probability about these notions: They make sense, It's either one or the other, they depend only on the graph (not on the starting point), and finally Recurrence is equivalent to the series of return probabilities being non-summable.
We talked about Pólya's proof of Pólya's theorem which boils down to estimating the number of closed paths of length 2n starting at the origin for each n. And we talked about why this proof doesn't help answer our questions (or analyze our examples) too much.
Finally we briefly introduced the result we will prove in the next lecture. The flow theorem. A more geometric characterization of recurrent/transient graphs.
Lecture 3
Another hour and a half long lecture.
This time we started by stating the flow theorem and the basic definitions for doing calculus on graphs (function, field, gradient, divergence, laplacian, energy of a field, summation by parts formula).
The flow theorem allows one to see easily that a transient graph cannot be made recurrent by adding edges. Also some examples are very easy to treat (though I left this for the audience to think about)
Then we proved the "finite flow theorem" a result about finite graphs. We ran out of time but managed to give an idea of how to prove the flow theorem from this result (full details in the notes of course).
In the next and last lecture we will try to answer as many of the main questions as possible and classify a bunch of the examples. If time permits we might get into some more recent results on trees (from the 90s).
Lecture 4 (last one)
The last lecture was an hour long. We reviewed the questions and examples, the definitions for doing calculus on graphs, and the statements of the flow theorems (finite and infinite).
We recalled that the flow theorem shows that one cannot make a transient graph recurrent by adding edges.
We then discussed the Canopy tree example and ended up showing it was transient via the flow theorem.
Using a variant of the same trick used for the Canopy tree (but using a sequence of disjoint sets of edges, instead of just a sequence of edges) we showed that Z^2 is transient. The same technique generalized is the result called the Nash-Williams criterion. We left it as an exercise to find appropriate subsets of edges for showing that *632 is recurrent.
The lamplighter group was shown to be transient because its Cayley graph contains a binary tree (with some edges subdivided only once).
To conclude we discussed radially symmetric trees. Sketching the proof that such a tree is recurrent if and only if the sequence 1/a_1...a_n is summable. In particular we obtained a subdivision of the infinite binary tree which is recurrent (the radially symmetric tree given by 2 1 2 1 1 1 2 1 1 1 1 1 1 1 etc).
Thanks!
It was my pleasure to participate in this school. I really enjoyed preparing and teaching my course. But most of all it was great to attend the other excellent courses and to interact with students from different backgrounds.
