First-Passage Percolation

First-passage percolation is a time-dependent generalization of discrete Bernoulli percolation in which each graph edge e of Z^d is assigned a nonnegative random variable t=t(e) called a time coordinate, the collection of which are identically and independently distributed . Within this model, the main objects of study are the asymptotic properties as t->infty of the set

 B^~(t)={v in Z^d:T(0,v)<=t}


 T(u,v)=inf{T(r):r is a path from u to v}

is the so-called travel time from u to v and where


is the so-called passage time of a path r on Z^d which runs successively through the edges e_1,...,e_n. B^~(t) is interpreted as the collection of vertices which can be reached from the origin by time t.

Site versions of the first-passage model in which the t's are assigned to sites rather than bonds have also been considered though haven't been written about extensively (Kesten 1987).

See also

AB Percolation, Bernoulli Percolation Model, Bond Percolation, Boolean Model, Boolean-Poisson Model, Bootstrap Percolation, Cayley Tree, Cluster, Cluster Perimeter, Continuum Percolation Theory, Dependent Percolation, Discrete Percolation Theory, Disk Model, Germ-Grain Model, Inhomogeneous Percolation Model, Lattice Animal, Long-Range Percolation Model, Mixed Percolation Model, Oriented Percolation Model, Percolation, Percolation Theory, Percolation Threshold, Polyomino, Random-Cluster Model, Random-Connection Model, Random Walk, s-Cluster, s-Run, Site Percolation

This entry contributed by Christopher Stover

Explore with Wolfram|Alpha


Grimmett, G. Percolation, 2nd ed. Berlin: Springer-Verlag, 1999.Kesten, H. "The 1986 Wald Memorial Lectures: Percolation Theory and First-Passage Percolation." Ann. Prob. 15, 1231-1271, 1987.

Cite this as:

Stover, Christopher. "First-Passage Percolation." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications