First passage percolation

First passage percolation is a mathematical method used to describe the paths reachable in a random medium within a given amount of time.

Introduction

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.

Mathematics

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]

Applications

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.

References

1. Hammersley, J. M.; Welsh, D. J. A. (1965). "First-Passage Percolation, Subadditive Processes, Stochastic Networks, and Generalized Renewal Theory". Bernoulli 1713 Bayes 1763 Laplace 1813. pp. 61–110. doi:10.1007/978-3-642-99884-3_7. ISBN 978-3-540-03260-1.
2. Auffinger, A.; Damron, M.; Hanson, J. (2016). "50 years of first passage percolation". arXiv:1511.03262 [math.PR].
3. Kesten, H. (1987). "Percolation theory and first-passage percolation". The Annals of Probability. 15 (4): 1231–1271. doi:10.1214/aop/1176991975.
4. Cox, J.; Durrett, Rick (1981). "Some limit theorems for percolation with necessary and sufficient conditions". The Annals of Probability. 9 (4): 583–603. doi:10.1214/aop/1176994364.
5. Auffinger, A.; Damron, M. (2013). "Differentiability at the edge of the limit shape and related results in first passage percoaltion". Probability Theory and Related Fields. 156: 193–227. arXiv:1105.4172. doi:10.1007/s00440-012-0425-4.
6. Van Der Hofstad, R.; Hooghiemstra, G.; Van Mieghem, P. "First passage percolation on the random graph" (PDF). ewi.tudelft.nl. Delft University of Technology. Retrieved 2014-11-17.
7. Flaxman, A.; Gamarnik, D.; Sorkin, G. "First-passage percolation on a width-2 strip, and the path cost in a VCG auction" (PDF). math.cmu.edu. CMU. Retrieved 2014-11-15.