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
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
. It was first introduced by
John Hammersley
John Michael Hammersley, (21 March 1920 – 2 May 2004) was a British mathematician best known for his foundational work in the theory of self-avoiding walks and percolation theory.
Early life and education
Hammersley was born in Helensburgh i ...
and
Dominic Welsh in 1965 as a model of fluid flow in a porous media. 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
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
) 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
In geometry, a geodesic () is a curve representing in some sense the shortest path ( arc) between two points in a surface, or more generally in a Riemannian manifold. The term also has meaning in any differentiable manifold with a connection. ...
, 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.
Let
be a
graph. We place a non-negative random variable
, called the passage time of the edge
, at each nearest-neighbor edge of the graph
. The collection
is usually assumed to be independent, identically distributed but there are variants of the model.
The random variable
is interpreted as the time or the cost needed to traverse edge
.
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.
:
Given two vertices
of
one then sets
:
where the infimum is over all finite paths that start at
and end at
.
The function
induces a random pseudo-metric on
.
The most famous model of first passage percolation is on the lattice
. 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.
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.
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 and 2-width strips can be described using a Markov chain and solved using a
Harris chain
In the mathematical study of stochastic processes, a Harris chain is a Markov chain where the chain returns to a particular part of the state space an unbounded number of times. Harris chains are regenerative processes and are named after Theodo ...
.
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
Ergodic theory (Greek: ' "work", ' "way") is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, statistical properties means properties which are expres ...
.
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
A Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction of multiple items. Bidders submit bids that report their valuations for the items, without knowing the bids of the other bidders. The auction system assigns the items in a ...
(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
{{Reflist
Network theory
Combinatorics
Percolation theory