(Probability Theory and Statistical Mechanics)

Percolation is a fascinating stochastic process which can model many physical effects, as well as being interesting in its own right. Like many such random models, it displays a variety of "threshold effects": as a controlling parameter changes continuously, different qualitative effects occur.

I exhibit the simplest model of percolation. This model is closely related to the Ising model of statistical mechanics, which describes how spins align themselves to create magnetism. But percolation can also be used in many other scenarios: to describe global connectivity properties despite link failure in a communications network, to describe social interaction, or whatever else strikes your fancy. In fact, the coffee-related name "percolation" is apparently the result of the initial effect which it was used to model: how gas in a coal mine permeates the filter of a gas mask. In all these physical effects, a one parameter changes value gradually, leading to a sudden "collapse" of the system into a different phase. This is a phase transition, and we can see the mathematics of one such phase transition in some detail.

I deal mostly with percolation on infinite graphs. The study of percolation on finite graphs has a distinct flavour, tends to be more related to Computer Science and applications, and, while sharing many properties, is even harder to analyze.

Definition

Let G=(V,E) be a graph. Percolation on G (the name "bond percolation" is often used instead, to indicate that edges are erased but vertices kept) is a set of random variables Xe belonging to each edge e∈E, each Xe taking on the values {0,1}. When Xe=1, we say that edge e is "open"; when Xe=0, e is said to be "closed".

We shall take all Xe's to be IID (which see).

In other words, fix some probability 0≤p≤1. For every edge in E, flip a coin which comes up heads with probability p; delete ("close") the edge if the coin came up tails. The resulting graph is (a sample of) percolation on G, with edge probability p.

Now suppose G is infinite and a transitive graph (which see). Consider the event C={there exists an infinite connected open cluster} (i.e. an infinite set of vertices A⊆V, such that there is a path of open edges between any two elements of A). Note that C is a tail event of the variables Xe, so by Kolmogorov's 0-1 Law we have either that P(C)=0 or P(C)=1. Which of the two cases depends on the choice of the graph G and of the parameter p.

Critical percolation is the study of the phase transition between C occurring and not occurring.

To give a taste of the theory, here are some other events we may consider:

  • For some v∈V, Cv={there exists an infinite connected open cluster containing v}. When G is transitive, P(Cv)=P(Cu) for any 2 vertices u,v, and it turns out that P(Cv)>0 iff P(C)=1.
  • Define θ(p) to be P(C) when we perform percolation with edge probability p. What is the behaviour of θ(p)? Is it continuous?
  • Assuming P(C)=1 -- how many infinite open clusters are there?
  • Assuming P(C)=0 -- what is the expected size of an open cluster?
Many of these numbers are unknown. Even more frustratingly, many of the answers are "known" (from Physics), but we are unable to prove them!

Per`co*la"tion (?), n. [L. percolatio.]

The act or process of percolating, or filtering; filtration; straining. Specifically Pharm., the process of exhausting the virtues of a powdered drug by letting a liquid filter slowly through it.

 

© Webster 1913.

Log in or registerto write something here or to contact authors.