First passage percolation is a mathematical method used to describe the paths reachable in a random medium within a given amount of time.
It was first introduced by John Hammersley and Dominic Welsh in 1965 as a model of fluid flow in a porous media.
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.
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.
This question was raised in the original paper of Hammersley and Welsh in 1969 and gave rise to the Cox-Durrett limit shape theorem in 1981.
[4] Although the Cox-Durrett theorem provides existence of the limit shape, not many properties of this set are known.
For instance, it is expected that under mild assumptions this set should be strictly convex.
As of 2016, the best result is the existence of the Auffinger-Damron differentiability point in the Cox-Liggett flat edge case.
[5] There are also some specific examples of first passage percolation that can be modeled using Markov chains.
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.