First passage percolation is a mathematical method used to describe the paths reachable in a random medium within a given amount of time.
First passage percolation is one of the most classical areas of probability theory. It was first introduced by John Hammersley and Dominic Welsh in 1965 as a model of fluid flow in a porous media.[1] It is part of percolation theory, and classical Bernoulli percolation can be viewed as a subset of first passage percolation.
Most of the beauty of the model lies in its simple definition (as a random metric space) and the property that several of its fascinating conjectures do not require much effort to be stated. Most times, the goal of first passage percolation is to understand a random distance on a graph, where weights are assigned to edges. Most questions are tied to either find the path with the least weight between two points, known as a geodesic, or to understand how the random geometry behaves in large scales.
As is the case in percolation theory in general, many of the problems related to first passage percolation involve finding optimal routes or optimal times. The model is defined as follows.[2] Let
G
t(e)
e
G
t(e)
t(e)
e
Since each edge in first passage percolation has its own individual weight (or time) we can write the total time of a path as the summation of weights of each edge in the path.[3]
T(\gamma)=\sumit(ei).
Given two vertices
x,y
G
T(x,y)=inf\gammaT(\gamma),
x
y
T
G
The most famous model of first passage percolation is on the lattice
Zd
There are also some specific examples of first passage percolation that can be modeled using Markov chains. For example: a complete graph can be described using Markov chains and recursive trees [6] and 2-width strips can be described using a Markov chain and solved using a Harris chain.[7]
First passage percolation is well-known for giving rise to other tools of mathematics, including the Subadditive Ergodic Theorem, a fundamental result in ergodic theory.
Outside mathematics, the Eden growth model is used to model bacteria growth and deposition of material. Another example is comparing a minimized cost from the Vickrey–Clarke–Groves auction (VCG-auction) to a minimized path from first passage percolation to gauge how pessimistic the VCG-auction is at its lower limit. Both problems are solved similarly and one can find distributions to use in auction theory.