First-Passage Percolation

First-passage percolation is a time-dependent generalization of discrete Bernoulli percolation in which each graph edge  of  is assigned a nonnegative random variable  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  of the set

(1)

where

(2)

is the so-called travel time from  to  and where

(3)

is the so-called passage time of a path  on  which runs successively through the edges .  is interpreted as the collection of vertices which can be reached from the origin by time .

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

REFERENCES

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.