You are here

50 Years of First-Passage Percolation

Buy Now:

Antonio Auffinger, Michael Damron, and Jack Hanson
American Mathematical Society
Publication Date: 
Number of Pages: 
University Lecture Series 68
[Reviewed by
David Aldous
, on

This is a monograph recounting (as the title says) of 50 years of research on a particular topic within the field of theoretical mathematical probability. It is written in traditional theorem-proof style, though with helpful discussions, and some deeper results are only sketched. Readers will need a solid understanding of measure-theoretic probability at the level of a first-year-graduate course such as Durrett's Probability: Theory and Examples.

In the basic first-passage percolation (FPP) model on the \(d\)-dimensional Euclidean lattice \(\mathbb{Z}^d\), there are independent identically distributed non-negative random variables on edges, interpreted as the time to traverse the edge. So there is some shortest-time path (geodesic) between any two vertices. Many mathematical questions can be asked within this model. A fundamental and quite easy start is the shape theorem, that the region reached from the origin before time \(t\) grows linearly with \(t\) and the rescaled limit is a deterministic convex set. But further results are deeper. In dimension 2 the time \(T_n\) to percolate from the origin to \((n,0)\) is widely believed to have standard deviation of order \(n^{1/3}\), and this scaling exponent \(1/3\) is expected to be related to another exponent measuring the maximum deviation of the shortest-time path from a straight line, but results of this kind are deep or unproven. Other questions involves existence or non-existence of infinite geodesics. One can view FPP as a "growth of clusters" process, and a brief chapter describes relations to other such growth processes. The list of open problems shows that the general FPP research topic remains active.

The monograph succeeds admirably in providing an authoritative overview of this topic, with complete proofs of the main results, and the 190 cited papers provide some sense of the size of this topic. It will deservedly become the definitive introduction and reference for many years. It could be used as the basis for an advanced graduate course, though there are no exercises.

At only 161 pages it is necessarily rather tightly focussed on this one specific model of interest within mathematical theory. So it is worth noting that there is a parallel, more applied field. There is a vast modern literature on quantitative aspects of general networks, and within that literature there are many models interpretable as spread of information (epidemics, rumors, fashion, innovations, etc) through local interactions, on social networks or similar, and these aspects of contemporary life provide huge amounts of available real-world data. The FPP model is mathematically basic within such models, in the sense that it represents the extreme case of how fast information can spread locally (see e.g. the reviewer's survey paper "Interacting Particle Systems as Stochastic Social Dynamics" Bernoulli 19 (2013) 1122-1149). While there has been extensive study of FPP on a few specific network models, it lacks any substantial "general network theory" and this represents a challenge for mathematicians interested in the interface between theory and applications.

David Aldous ( is retired from U.C. Berkeley after 39 years, but retains interests in theoretical and applied probability and in the popular exposition of probability in the real world.

See the table of contents in the publisher's webpage.