Probability on Trees and Networks
|Publisher:||Cambridge University Press|
This book is concerned with certain aspects of discrete probability on infinite graphs that are currently in vigorous development. Of course, finite graphs are analyzed as well, but usually with the aim of understanding infinite graphs and networks. These areas of discrete probability are full of interesting, beautiful, and surprising results, many of which connect to other areas of mathematics and theoretical computer science. Numerous fascinating questions are still open.
Our major topics include random walks and their intimate connection to electrical networks; uniform spanning trees, their limiting forests, and their marvelous relationships with random walks and electrical networks; branching processes; percolation and the powerful, elegant mass-transport technique; isoperimetric inequalities and how they relate to both random walks and percolation; minimal spanning trees and forests and their connections to percolation; Hausdorff dimension, capacity, and how to understand them via trees; and random walks on Galton-Watson trees. Connections among our topics are pervasive and rich, making for surprising and enjoyable proofs.
There are three main classes of graphs on which discrete probability is most interesting, namely, trees, Cayley graphs of groups (or, more generally, transitive, or even quasi-transitive, graphs), and planar graphs. More classical discrete probability has tended to focus on the special and important case of the Euclidean lattices, Zd, which are prototypical Cayley graphs. This book develops the general theory of various probabilistic processes on graphs and then specializes to the three broad classes listed, always seeing what we can say in the case of Zd.
This book has been released as Open Access by its author.