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 a subset of percolation theory, specifically Bernoulli percolation, and was first introduced by John Hammersley and Dominic Welsh in 1965.^[1] There are two different methods of calculating any kind of percolation: bond percolation and site percolation. This article will deal mostly with bond percolation, as this is where most of the work on first passage percolation has been done, but there are other articles which talk about site percolation.

Bernoulli percolation is a percolation model in which, starting at a specified initial node, each attached link is either followed or not followed by a specified probability $p$ (where $p$ is the probability of the following the link and $q = 1-p$ is the probability of not following this link). First passage percolation differs from Bernoulli percolation by assigning a different $p$ value, or different Weight, to each link, as opposed to having the same $p$ value used for every link in the system. The goal of first passage percolation is look at all the paths that can be reached, each described by the sum of individual weights in the path.^[2] Many times the goal is to find the path with the least weight, or Geodesic.

Mathematics

As is the case percolation theory in general, many of the problems related to first passage percolation involve finding optimal routes or optimal times. Since each link in first passage percolation has its own individual weight (or time) we can write the total time, $T$, through multiple links as the summation of weights of each link in the path.

$T(r)= \sum_{i} t(e_i),$

Where $T$ is the total time of the path $r$, $e_i$ is the weight of each specific link (or edge, hence the e), and $t(e_i)$ is the amount of time is takes to move through the a specific link^[3]

There are 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 ^[4] and 2-width strips can be described using a Markov chain and solved using a Harris chain.^[5]

Applications

There has not been much study done on first passage percolation, but some does exist. One 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.^[6] Both problems are solved similarly and one can find distributions to use in auction theory.

Lots of the work done with first passage percolation is looking at very large systems, or a system with a large number of links, to obtain information about the Asymptotic behavior of the given system. The systems are usually symmetric in some way to make mathematical calculations easier, but this is not required.

References

1. Hammersley, J.M.; Welsh, J.D. (1965). "First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory". Spring-Verlag. Bernoulli-Bayes-Laplace Anniversary Volume: 61–110.
2. Kesten, H. "A minicourse on first-passage percolation" (PDF). eurandom.nl. European Institute for Statistics, Probability, Stochastic Operations Research and their Applications. Retrieved 2014-11-17.
3. Kesten, H. (1987). "Percolation theory and first-passage percolation". The Annals of Probability 15 (4): 1231–1271. doi:10.1214/aop/1176991975.
4. Van Der Hofstad, R.; Hooghiemstra, G.; Van Miegham, P. "First passage percolation on the random graph" (PDF). ewi.tudelft.nl. Delft University of Technology. Retrieved 2014-11-17.
5. 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.
6. 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.