Probability on Trees and Networks

In 1990 Russ Lyons published a paper in the Annals of Probability titled “Random Walks and Percolation on Trees.” Probabilists and physicists have for many years studied processes on regular trees because they are simpler than the corresponding processes on the \(d\)-dimensional lattice. The big new idea in Lyons paper was to consider a general tree. That may seem an impossible task, but motivated by an idea of Furstenberg, Lyons was able to define a branching number that describes how fast the tree grows and in turn can be used to calculate the critical value of percolation on the tree and the amount of bias toward the root that a random walk needs to become recurrent.

Five years later Lyons, joined by Robin Pemantle and Yuval Peres, studied the special case of Galton-Watson trees. Making clever use of ergodic theory, they were able to prove many detailed results about the asymptotic behavior of random walks on these trees, including the somewhat surprising fact that the limits as \(t\) tends to infinity concentrate on a very small fraction of the possible limits. To be specific, if the degree distribution is random then the Hausdorff dimension of the limit set is smaller than that of the boundary. Though this was the first of seven papers the trio wrote between 1995–1999, it is the last chapter (number 17) in the book.

The trio’s second paper in 1996 gave a conceptual proof of the Kesten-Stigum theorem, a necessary and sufficient condition for a branching process normalized by its mean to converge to a nontrivial limit. I must confess that I have never read the proof, but the paper has been cited 126 times, making it the most cited paper for each of the three authors.

I don’t know when the first version of this book appeared on the web, but it has been there for many years and has grown to be an amazing reference. The book begins with eight pages of beautiful color pictures followed by 17 pages that highlight some of the major results. The book does its best to be self-contained. Chapter 2 describes the connection between random walks and electrical networks. Chapter 5 introduces branching processes. Chapter 6 introduces isoperimetric inequalities. Much later in the book Hausdorff dimension and capacity are discussed, in Chapters 15 and 16.

The organization of the book is somewhat puzzling: Uniform Spanning trees are studied in Chapter 4 but uniform spanning forests have to wait until Chapter 10. Branching processes part 1 is Chapter 5, but part 2 with the “conceptual proof” is Chapter 12. A colorful tree diagram gives the dependencies between the chapters. Perhaps the problem with the organization (if there is one) is that it is hard to embed the tree structure of the book in one dimension.

There is much to be learned from studying this book. Many of the ideas and tools are useful in a wide variety of different contexts. As explained in the preface, Lyons is responsible for most of the 600 pages of text, except for Chapters 13 and 14, which were written by Peres. Lyons has invested many hours in this book. For those with time on their hands, there are something like 1000 exercises. I didn’t count very carefully but there are 139 in Chapter 2 alone.

Geoff Grimmett’s quote on the cover calls the book “Masterly, beautiful, encyclopedic and yet browsable.” I totally agree. Even though it is freely available on the web, you should buy a copy of the book. Just be careful not to drop it on your foot. 

Richard Durrett taught at UCLA and Cornell before he came to Duke in 2010. He is a member of the National Academy of Science, who for the last thirty years has used probability to study problems that arise from ecology, genetics, and cancer modeling.