Probability on Trees and Networks

This book explores the fascinating field of probability on trees and weighted graphs. Although some related topics have been treated by other recent books, none has explored so thoroughly the relations between the geometry of graphs, the probabilistic objects defined on them, such as Markov chains and their electrical network interpretations, edge percolations, Galton-Watson branching processes, random spanning trees, and the analytical notions of Hausdorff dimension and capacity. As noted in Math reviews by Laurent Miclo,
these links are presented in a conversational and enjoyable fashion in the first chapter, where the unifying concept of the branching number of a rooted tree is defined This quantity is bounded above by the lower exponential growth rate of T and is directly related to (i) the transience properties of weighted random walks (ii) the critical percolation probability, (iii) the Hausdorff dimension of the boundary ∂T and (iv) the existence of a finite energy probability measure on ∂T. Chapter 2 presents the correspondence between electric networks and reversible Markov chains, based on the identifications of the conductance of an edge. It enables one to see voltages as Green functions and currents as expected edge crossings and leads to a criterion for transience based on positive effective conductance to infinity. Notions from discrete potential theory are introduced, leading to Thomson’s Principle, characterizing current flows as minimizing flows for the energy, to Rayleigh’s Monotonicity Principle, comparing effective conductances from edge conductance inequalities, and to the characterization of transience by the existence of a unit flow to infinity of finite energy. In particular Pólya’s Theorem on the recurrence/transience dichotomy for the random walk on lattices is recovered. To deduce the transience of the hyperbolic spaces of dimension at least 2, the general relations between rough embedding, rough isometry and transience are presented. Chapter 2 ends with the electrical interpretations of (i) the hitting and commuting times to get cover time bounds and (ii) the canonical Gaussian field on the vertices, via a minimization property of its gradient.
Chapter 3 introduces the special cases of trees and Cayley graphs, but begins with the general max-flow min-cut theorem, identifying the maximum strength of an admissible flow with the minimal capacity value of an edge cutset. The universal covering tree of a graph is presented and related to the notion of periodicity of a tree. (Sub, super)periodicity enables one to identify the branching number of a tree with its growth rate. The basics of Cayley graphs are introduced, with the notions of free groups, representation of groups, and free and Cartesian products, as well as the useful lamplighter group. Using a geodesic subtree, the critical value for the transience of a Cayley graph is identified with its exponential growth rate.
Chapter 4 begins the investigation of the wonderful weighted “uniform” spanning trees, whose distribution is proportional to the product of the conductances of the edges of the tree. To sample these spanning trees, the powerful algorithm of Wilson is presented, based on the loop erasures of the associated Markov chains. Next the authors discuss the electrical interpretations via Kirchhoff’s Effective Resistance Formula and the Transfer Current Theorem, giving a determinantal form for the probability that some edges belong to the spanning tree. The case of the square lattice Z2 serves as an illustration. The notes give the Markov Chain Tree Theorem representation of the invariant probability and allude to the amazing relations with stochastic Loewner evolutions.
Chapter 5 begins by recalling the classical theory of Galton-Watson branching processes, with the Kesten-Stigum and Seneta-Heyde theorems. Next the first and second weighted moments methods, as well as an electrical interpretation, are used to deduce bounds on the critical probability for Bernoulli percolation to infinity on graphs. On trees, it is identified with the inverse branching number. Some extensions to quasi-independent percolation, as well as the transience of percolation clusters, are considered. The decomposition of supercritical Galton-Watson trees into surviving/non-surviving parts is obtained via conditioning and percolation. The existence of d-ary subtrees and left-to-right crossing in fractal percolation is investigated in a similar spirit. Chapter 5 ends with Harris’ inequality, i.e., the positive correlation of increasing observables for independent percolation, and the existence of flows in weighted Galton-Watson trees.
Chapter 6 is a combinatorics-oriented presentation of isoperimetric constants, comparing the sizes, measured in various ways, of the boundary of a subset with respect to its interior. Their relations with the notions of dual flows, submodularity and amenability are investigated. Cheeger’s inequalities establish an important link with the spectral radius, which is used to deduce estimates on the speed of random walks, on the cogrowth (i.e., the growth of the covering space obtained via non-backtracking paths) and on mixing rates in the finite setting. Regular planar graphs, their dual graphs and hyperbolic tessellation edge graphs illustrate special behaviors of isoperimetry and lead to nice pictures. The discrete analogue of the original Euclidean isoperimetry is recalled through the Loomis and Whitney inequality on projections and justifies a pleasant introduction to entropy and to the Shannon, Han and Shearer inequalities. Chapter 6 ends with the more specific (anchored) isoperimetric profiles and their applications to decay of transition probabilities, to transience of Cayley graphs and to percolation, including a presentation of evolving sets, covering maps and random subdivision of edges. As usual, the notes are rich and allude in particular to Buser’s inequality and to Ramanujan graphs.
Chapter 7 begins the investigation of percolation on transitive graphs, namely those looking the same from any of their vertices. Some important facts from the general theory of percolation are presented: insertion/deletion tolerance, tail events and ergodicity, inequalities between bond and site percolations, contour arguments, dual percolation, numbers of infinite clusters, invasion and bootstrap percolation. One of the main questions is the validity of pc<pu<1, where the critical probability pc (resp. pu) commands the phase transition to the existence (resp. the uniqueness) of an infinite cluster in the Bernoulli percolation. Some bounds on pu are provided and significant conjectures are recalled, in the context of quasi-transitive non-amenable graphs. The notes go further into the relations with groups, introducing, e.g., the Kazhdan property (T).
Chapter 8 introduces a mass-transport principle for unimodular graphs, which is a technique interchanging the order of summation of functions of two vertex variables invariant under the diagonal action of the group of automorphisms. It is a powerful tool in the developed investigation of the critical percolation on non-amenable quasi-transitive unimodular graphs, of the double phase transition of the Bernoulli percolation on planar quasi-transitive graphs and of the properties of ends in infinite clusters.
Chapter 9 comes back to current flows from one vertex to another, now in the context of infinite networks, in which there exist two definitions: free and wired currents, depending on the chosen approximation by finite sets. One highlight of the chapter is that it shows that in a transient network, the subnetwork formed by the edges crossed by a random walk is a.s. recurrent.
In Chapter 10, the fascinating model of uniform spanning trees is extended to infinite transient graphs through uniform spanning forests, either free or wired.
Chapter 11 investigates other distributions on spanning forests, corresponding to the free or wired extensions of minimal spanning trees on finite graphs (minimizing the sum of independent and uniformly distributed weights on the edges). Similarities and discrepancies with uniform spanning forests are put forward, as well as the links with Bernoulli percolation.
Chapter 12 provides the proofs of the limit theorems for Galton-Watson processes via size-biased transformations.
Chapter 13 begins the investigation of the speed of escape of transient random walks in metric spaces. After proving the fundamental Varopoulos-Carne inequality, the authors give an application to lower bounds on mixing times of finite Markov chains. Distortions of embeddings of finite metric spaces into Hilbert spaces are also presented.
Chapter 14 introduces the Avez entropy h on Cayley graphs and shows that for simple random walks, h>0 is equivalent to the existence of a positive escape speed, to the nontriviality of the tail σ-field and to the existence of bounded non-constant harmonic functions (failure of the Liouville property). This chapter also addresses the identification of the Poisson boundary via the method of Kaimanovich and recalls the proofs of the Birkhoff and Kingman ergodic theorems.
Chapter 15 is concerned with Hausdorff dimension and the analysis of random fractals. The relationship of Hausdorff dimension with capacities in Euclidean spaces is covered in Chapter 16, with an application to Brownian intersections. Another interest of Hausdorff dimension is given in Chapter 17, with the investigation of the harmonic measure associated to random walks on trees, especially those randomly chosen according to a Galton-Watson measure.
The book has numerous exercises (with hints and solutions at the end of the book. It has been used in courses in many universities, including Cornell, Berkeley, Stanford and Tel-Aviv.