Percolation theory

A three-dimensional site percolation graph

In statistical physics and mathematics, percolation theory describes the behavior of connected clusters in a random graph. The applications of percolation theory to materials science and other domains are discussed in the article percolation.

Introduction

A representative question (and the source of the name) is as follows. Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled mathematically as a three-dimensional network of n × n × n vertices, usually called "sites", in which the edge or "bonds" between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path (meaning a path, each of whose links is an "open" bond) exists from the top to the bottom? The behavior for large n is of primary interest. This problem, called now bond percolation, was introduced in the mathematics literature by Broadbent & Hammersley (1957),^[1] and has been studied intensively by mathematicians and physicists since then.

In a slightly different mathematical model for obtaining a random graph, a site is "occupied" with probability p or "empty" (in which case its edges are removed) with probability 1-p; the corresponding problem is called site percolation. The question is the same: for a given p, what is the probability that a path exists between top and bottom?

Of course the same questions can be asked for any lattice dimension. As is quite typical, it is actually easier to examine infinite networks than just large ones. In this case the corresponding question is: does an infinite open cluster exist? That is, is there a path of connected points of infinite length "through" the network? By Kolmogorov's zero-one law, for any given p, the probability that an infinite cluster exists is either zero or one. Since this probability is an increasing function of p (proof via coupling argument), there must be a critical p (denoted by p_c) below which the probability is always 0 and above which the probability is always 1. In practice, this criticality is very easy to observe. Even for n as small as 100, the probability of an open path from the top to the bottom increases sharply from very close to zero to very close to one in a short span of values of p.

Detail of a bond percolation on the square lattice in two dimensions with percolation probability p = 0.51

In some cases p_c may be calculated explicitly. For example, for the square lattice Z² in two dimensions, p_c = 1/2 for bond percolation, a fact which was an open question for more than 20 years and was finally resolved by Harry Kesten in the early 1980s,^[2] see Kesten (1982). A limit case for lattices in many dimensions is given by the Bethe lattice, whose threshold is at p_c = 1/(z − 1) for a coordination number z. For most infinite lattice graphs, p_c cannot be calculated exactly.

Universality

The universality principle states that the numerical value of p_c is determined by the local structure of the graph, whereas the kind of behavior of clusters that is observed below, at, and above p_c is independent of the local structure, and therefore, in some sense these behaviors are more natural to consider than p_c itself . This universality also means that for a given dimension, the fractal dimension of the clusters at p_c is independent of the lattice type and percolation type (e.g., bond or site).

Phases

Subcritical and supercritical

The main fact in the subcritical phase is "exponential decay". That is, when p < p_c, the probability that a specific point (for example, the origin) is contained in an open cluster (meaning a maximal connected set of "open" edges of the graph) of size r decays to zero exponentially in r. This was proved for percolation in three and more dimensions by Menshikov (1986) and independently by Aizenman & Barsky (1987). In two dimensions, it formed part of Kesten's proof that p_c = 1/2.^[3]

The dual graph of the square lattice Z² is also the square lattice. It follows that, in two dimensions, the supercritical phase is dual to a subcritical percolation process. This provides essentially full information about the supercritical model with d = 2. The main result for the supercritical phase in three and more dimensions is that, for sufficiently large N, there is an infinite open cluster in the two-dimensional slab Z² × [0, N]^d−2. This was proved by Grimmett & Marstrand (1990).^[4]

In two dimensions with p < 1/2, there is with probability one a unique infinite closed cluster (a closed cluster is a maximal connected set of "closed" edges of the graph) . Thus the subcritical phase may be described as finite open islands in an infinite closed ocean. When p > 1/2 just the opposite occurs, with finite closed islands in an infinite open ocean. The picture is more complicated when d ≥ 3 since p_c < 1/2, and there is coexistence of infinite open and closed clusters for p between p_c and 1 − p_c.

Critical

The model has a singularity at the critical point p = p_c believed to be of power-law type. Scaling theory predicts the existence of critical exponents, depending on the number d of dimensions, that determine the class of the singularity. When d = 2 these predictions are backed up by arguments from conformal field theory and Schramm–Loewner evolution, and include predicted numerical values for the exponents. Most of these predictions are conjectural except when the number d of dimensions satisfies either d = 2 or d ≥ 19. They include:

There are no infinite clusters (open or closed)
The probability that there is an open path from some fixed point (say the origin) to a distance of r decreases polynomially, i.e. is on the order of r^α for some α
- α does not depend on the particular lattice chosen, or on other local parameters. It depends only on the dimension d (this is an instance of the universality principle).
- α_d decreases from d = 2 until d = 6 and then stays fixed.
- α₂ = −5/48
- α₆ = −1.
The shape of a large cluster in two dimensions is conformally invariant.

See Grimmett (1999).^[5] In dimension ≥ 19, these facts are largely proved using a technique known as the lace expansion. It is believed that a version of the lace expansion should be valid for 7 or more dimensions, perhaps with implications also for the threshold case of 6 dimensions. The connection of percolation to the lace expansion is found in Hara & Slade (1990).^[6]

In dimension 2, the first fact ("no percolation in the critical phase") is proved for many lattices, using duality. Substantial progress has been made on two-dimensional percolation through the conjecture of Oded Schramm that the scaling limit of a large cluster may be described in terms of a Schramm–Loewner evolution. This conjecture was proved by Smirnov (2001)^[7] in the special case of site percolation on the triangular lattice.

Different models

The first model studied was Bernoulli percolation. In this model all bonds are independent. This model is called bond percolation by physicists.
A generalization next was introduced as the Fortuin–Kasteleyn random cluster model, which has many connections with the Ising model and other Potts models.
Bernoulli (bond) percolation on complete graphs is an example of a random graph. The critical probability is p = 1/N, where N is the number of vertices (sites) of the graph.
Directed percolation, which has connections with the contact process.
First passage percolation.
Invasion percolation.
Percolation with dependency links was introduced by Parshani et al.^[8]
Opinion Model^[9]

References

↑ Broadbent, S. R.; Hammersley, J. M. (2008). "Percolation processes". Mathematical Proceedings of the Cambridge Philosophical Society 53 (03): 629. doi:10.1017/S0305004100032680. ISSN 0305-0041.
↑ Bollobás, Béla; Riordan, Oliver (2006). "Sharp thresholds and percolation in the plane". Random Structures and Algorithms 29 (4): 524–548. doi:10.1002/rsa.20134. ISSN 1042-9832.
↑ Kesten, Harry (1982). doi:10.1007/978-1-4899-2730-9. Missing or empty |title= (help)
↑ Grimmett, G. R.; Marstrand, J. M. (1990). "The Supercritical Phase of Percolation is Well Behaved". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 430 (1879): 439–457. doi:10.1098/rspa.1990.0100. ISSN 1364-5021.
↑ Grimmett, Geoffrey (1999). 321. doi:10.1007/978-3-662-03981-6. ISSN 0072-7830. Missing or empty |title= (help)
↑ Hara, Takashi; Slade, Gordon (1990). "Mean-field critical behaviour for percolation in high dimensions". Communications in Mathematical Physics 128 (2): 333–391. doi:10.1007/BF02108785. ISSN 0010-3616.
↑ Smirnov, Stanislav (2001). "Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limits". Comptes Rendus de l'Académie des Sciences - Series I - Mathematics 333 (3): 239–244. doi:10.1016/S0764-4442(01)01991-7. ISSN 0764-4442.
↑ Parshani, R.; Buldyrev, S. V.; Havlin, S. (2010). "Critical effect of dependency groups on the function of networks". Proceedings of the National Academy of Sciences 108 (3): 1007–1010. doi:10.1073/pnas.1008404108. ISSN 0027-8424.
↑ Shao, Jia; Havlin, Shlomo; Stanley, H. Eugene (2009). "Dynamic Opinion Model and Invasion Percolation". Physical Review Letters 103 (1). doi:10.1103/PhysRevLett.103.018701. ISSN 0031-9007.

Aizenman, Michael; Barsky, David (1987), "Sharpness of the phase transition in percolation models", Communications in Mathematical Physics 108 (3): 489–526, Bibcode:1987CMaPh.108..489A, doi:10.1007/BF01212322
Bollobás, Béla; Riordan, Oliver (2006), Percolation, Cambridge University Press, ISBN 0521872324
Broadbent, Simon; Hammersley, John (1957), "Percolation processes I. Crystals and mazes", Proceedings of the Cambridge Philosophical Society 53: 629–641, Bibcode:1957PCPS...53..629B, doi:10.1017/S0305004100032680
Bunde A. and Havlin S. (1996), Fractals and Disordered Systems, Springer
Cohen R. and Havlin S. (2010), Complex Networks: Structure, Robustness and Function, Cambridge University Press
Grimmett, Geoffrey (1999), Percolation, Springer
Grimmett, Geoffrey; Marstrand, John (1990), "The supercritical phase of percolation is well behaved", Proceedings of the Royal Society A 430 (1879): 439–457, Bibcode:1990RSPSA.430..439G, doi:10.1098/rspa.1990.0100
Hara, Takashi; Slade, Gordon (1990), "Mean-field critical behaviour for percolation in high dimensions", Communications in Mathematical Physics 128 (2): 333–391, Bibcode:1990CMaPh.128..333H, doi:10.1007/BF02108785
Kesten, Harry (1982), Percolation theory for mathematicians, Birkhauser
Menshikov, Mikhail (1986), "Coincidence of critical points in percolation problems", Soviet Mathematics Doklady 33: 856–859
Smirnov, Stanislav (2001), "Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limits", Comptes Rendus de l'Academie des Sciences 333 (3): 239–244, Bibcode:2001CRASM.333..239S, doi:10.1016/S0764-4442(01)01991-7
Stauffer, Dietrich; Aharony, Anthony (1994), Introduction to Percolation Theory (2nd ed.), CRC Press, ISBN 978-0-7484-0253-3

External links

PercoVIS: a Mac OS X program to visualize percolation on networks in real time
Interactive Percolation
Kesten, Harry (May 2006), "What Is ... Percolation?" (PDF), Notices of the American Mathematical Society (Providence, RI: American Mathematical Society) 53 (5): 572–573, ISSN 1088-9477
Austin, David (July 2008), Percolation: Slipping through the Cracks, American Mathematical Society
Online course on Percolation Theory
Introduction to Percolation Theory: short course by Shlomo Havlin

Stochastic processes

Discrete time	Bernoulli process Branching process Chinese restaurant process Galton–Watson process Independent and identically distributed random variables Markov chain Moran process Random walk Loop-erased Self-avoiding

Continuous time	Bessel process Birth–death process Brownian motion Bridge Excursion Fractional Geometric Meander Cauchy process Contact process Continuous-time random walk Cox process Diffusion process Empirical process Feller process Fleming–Viot process Gamma process Hunt process Interacting particle systems Itô diffusion Itô process Jump diffusion Jump process Lévy process Local time Markov additive process McKean–Vlasov process Ornstein–Uhlenbeck process Poisson process Compound Non-homogeneous Point process Schramm–Loewner evolution Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process Wiener process Wiener sausage

Both	Branching process Gaussian process Hidden Markov model (HMM) Markov process Martingale Differences Local Sub- Super- Random dynamical system Regenerative process Renewal process White noise

Fields and other	Dirichlet process Gaussian random field Gibbs measure Hopfield model Ising model Potts model Boolean network Markov random field Percolation Pitman–Yor process Point process Cox Poisson Random field Random graph

Time series models	Autoregressive conditional heteroskedasticity (ARCH) model Autoregressive integrated moving average (ARIMA) model Autoregressive (AR) model Autoregressive–moving-average (ARMA) model Generalized autoregressive conditional heteroskedasticity (GARCH) model Moving-average (MA) model

Financial models	Black–Derman–Toy Black–Karasinski Black–Scholes Chen Constant elasticity of variance (CEV) Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie

Actuarial models	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson

Queueing models	Bulk Fluid Generalized queueing network M/G/1 M/M/1 M/M/c

Properties	Càdlàg paths Continuous Continuous paths Ergodic Exchangeable Feller-continuous Gauss–Markov Markov Mixing Piecewise deterministic Predictable Progressively measurable Self-similar Stationary Time-reversible

Limit theorems	Central limit theorem Donsker's theorem Doob's martingale convergence theorems Ergodic theorem Fisher–Tippett–Gnedenko theorem Large deviation principle Law of large numbers (weak/strong) Law of the iterated logarithm Maximal ergodic theorem Sanov's theorem

Inequalities	Burkholder–Davis–Gundy Doob's martingale Kunita–Watanabe

Tools	Cameron–Martin formula Convergence of random variables Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Kolmogorov continuity theorem Kolmogorov extension theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract

Disciplines	Actuarial mathematics Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Statistics Stochastic analysis Time series analysis Machine learning

List of topics Category

This article is issued from Wikipedia - version of the Tuesday, May 03, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.