First passage percolation

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 ${\displaystyle G}$ be a graph. We place a non-negative random variable ${\displaystyle t(e)}$, called the passage time of the edge ${\displaystyle e}$, at each nearest-neighbor edge of the graph ${\displaystyle G}$. The collection ${\displaystyle t(e)}$ is usually assumed to be independent, identically distributed but there are variants of the model. The random variable ${\displaystyle t(e)}$ is interpreted as the time or the cost needed to traverse edge ${\displaystyle 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]

${\displaystyle T(\gamma )=\sum _{i\in \gamma }t(e_{i}).}$

Given two vertices ${\displaystyle x,y}$ of ${\displaystyle G}$ one then sets

${\displaystyle T(x,y)=\inf _{\gamma }T(\gamma ),}$

where the infimum is over all finite paths that start at ${\displaystyle x}$ and end at ${\displaystyle y}$. The function ${\displaystyle T}$ induces a random pseudo-metric on ${\displaystyle G}$.

The most famous model of first passage percolation is on the lattice ${\displaystyle \mathbb {Z} ^{d}}$. One of its most notorious questions is "What does a ball of large radius look like?". 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. 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.