Percolation: Slipping through the CracksPosted August 2008.The existence of a critical probability makes percolation a mathematically interesting and rich subject. ...
David Austin
IntroductionMy backyard has an area where the soil is mainly clay and another where it's mainly sand. The day after a hard rain, the sandy region is usually dry while the clay region is still damp. The process by which water moves through a medium, like sand or clay, is called percolation and is currently the focus of significant mathematical activity, some of which we'll describe in this article. Geoffrey Grimmett begins his book Percolation with the question: "Suppose we immerse a large porous stone in a bucket of water. What is the probability that the centre of the stone is wetted?" To begin creating a mathematical model, we will imagine a two-dimensional lattice of channels running through the rock (a more realistic three-dimensional model can wait).
This is known as the square lattice, and we will denote it by Z^{2}. We choose a parameter p between 0 and 1 and declare that each edge is open with probability p. Think of an open edge as a channel that is large enough to conduct water through it. Here are examples for two different values of p.
If we imagine that the size of the channels is much smaller than the size of the rock, it is reasonable to assume that the lattice is infinite in extent. To rephrase Grimmett's question, we may ask, "What is the probability that there is a path of open edges from the origin that travels infinitely far?
We can easily make two statements. When p = 0, every edge is closed so there will be no infinite open path containing the origin. However, when p = 1, every edge will be open so there must be an infinite open path. What happens for intermediate values of p? For small p, there will be few open channels so any open paths will most likely be short. However, as p increases, there are more open channels, and eventually it is likely that there is an infinite open path starting at the origin. If there is a positive probability of having such an infinite path, we say that percolation occurs. We will see that there is a critical probability, that we denote p_{c}, representing a threshold; percolation occurs above p_{c} but not below. A result due to Harris and Kesten, which we'll outline later, states that the critical probability for the square lattice is p_{c} = 1/2. The existence of a critical probability makes percolation a mathematically interesting and rich subject. On either side of the critical probability, the system behaves in fundamentally different ways (as water drains easily through sandy soil but not through clay). As such, it serves as a model for more complex systems that experience a phase transition when some parameter, such as temperature, passes through a critical value. Percolation provides a model that is simple enough to be mathematically accessible while still displaying many of the features of more complex systems. A simple exampleLet's begin with a simple example that illustrates some general principles. We will study percolation on the infinite binary tree, a portion of which is shown below.
If p is the probability that each edge is open, we want to find θ(p), the probability that there is an infinite open path containing the root of the tree v_{0}. We begin by letting P_{n} be the probability that there is an open path from v_{0} to a vertex n levels below. Notice that we have P_{0} = 1. Shown in red below is a path from v_{0} to a vertex three levels below.
This path moves through another vertex v_{1}. The probability that an open path from v_{0} to a vertex n levels below passes through v_{1} is pP_{n}_{-1}, the probability p that the edge from v_{0} to v_{1} is open times the probability P_{n}_{-1} that a path from v_{1} to a vertex n - 1 levels below it is open. Therefore, the probability that there is no open path from v_{0} to a vertex n levels below passing through v_{1} is 1 - pP_{n}_{-1}. Since any path from v_{0} to a vertex n levels below must pass through one of the children of v_{0}, we find that the probability that there is not an open path from v_{0} to a vertex n levels below is
and therefore
If we define the function f_{p}(x) = 1 - (1 - px)^{2}, we have P_{n} = f_{p}(P_{n}_{-1}). The graph of f_{p} is shown below in two different cases, depending on the derivative f_{p}'(0) = 2p.
In the first case, 2p > 1 , we see that there is a fixed point
and if 2p < 1, the only fixed point is x_{0} = 0. From the graph, we see that if 2p > 1 and x > x_{0}, then x_{0} < f_{p}(x) < x. Since P_{0} = 1, we have
It then follows that
if p > 1/2. The graph of θ(p) is therefore shown below:
Here we see that the critical probability, p_{c} = 1/2; above p_{c}, θ(p) > 0 and we have percolation. Below the critical probability, θ(p) = 0 and there is no percolation. This example is unusual in that it is difficult to compute the critical probability and θ(p) exactly for most combinatorial graphs. As we'll see toward the end of this article, however, it is thought that the specific form that θ(p) takes here shares features with that from other graphs. Percolation on the square latticePercolation theory was introduced to mathematicians by Broadbent and Hammersley in 1957. For two decades, work in this new field concentrated mainly on finding critical probabilities. For instance, Broadbent and Hammersley showed that the critical probability for the square lattice Z^{2}, shown below, is between 1/3 and 2/3.
On the basis of Monte Carlo simulations, Hammersley later suggested that this probability should be 1/2. Indeed, through work of Harris and later Kesten, it was eventually proven that p_{c} = 1/2. We will outline the proof of this theorem later. For now, let's develop a feel for how configurations behave for various values of p. Here is one configuration of open edges that results when p = 0.4.
Given a configuration of open edges and a vertex v in the lattice, the cluster C_{v} will denote the collection of vertices connected to v by open edges. Below we show a configuration when p = 0.3 and C_{0}, the cluster containing the origin, in blue.
Remember that θ(p) is the probability that there is an infinite path containing the origin, which is the same event as the cluster C_{0} being infinite. Here's what happens as we increase p.
Based on these examples, two things can be observed. First, if we look at a fixed value of p, we see that the size of the clusters is relatively small for small values of p. A theorem of Menshikov allows us to state this quantitatively. If E is some event, we will use P_{p}(E) to denote the probability that E holds when the edges are open with probability p. By S_{x,n}, we will denote the event that there is an open path from a vertex x to another vertex whose distance from x, measured in the lattice, is n. (We measure distances in the lattice as the number of edges in the shortest possible path between the two vertices.) Though proven in considerably more generality, Menshikov's theorem roughly says that
This means that the probability of having an open path decreases exponentially as the distance traveled by the path increases. The Harris-Kesten TheoremFor our second observation, imagine increasing p as we consider the size of the cluster C_{0}. It is relatively small for small values of p, but around p = 0.45, its size begins to grow significantly. This leads us to suspect that the critical probability p_{c}, the probability that marks the transition from θ(p) = 0 to θ(p) > 0 occurs around 1/2. In fact, one of the first significant results in percolation theory is the Harris-Kesten Theorem
In what follows, we will outline a proof of this theorem, which divides naturally into two parts. The first half, originally proven by Harris in 1960, states that θ(1/2) = 0. In particular, this implies that p_{c} ≥ 1/2. The second half, proven later by Kesten in 1982, says that p_{c} ≤ 1/2. The result that p_{c} = 1/2 naturally follows. We'll begin outlining an argument for Harris' theorem by considering the dual of the square lattice. This graph is formed from the square lattice by placing one vertex in the center of each square and joining vertices with an edge when their corresponding squares in the square lattice share an edge.
Notice that if we are given an edge in the lattice, there is exactly one edge crossing it in the dual. Also, the dual lattice is a copy of the square lattice translated so that the vertices are in the centers of the squares. For this reason, we say the square lattice is self-dual. Suppose we are given a configuration of open edges in the square lattice. We will consider an edge in the dual lattice to be open exactly when the edge it crosses in the square lattice is closed. Shown below in red is a configuration for the square lattice and, in blue, the corresponding configuration in the dual lattice.
In this way, requiring that the edges in the square lattice are open with probability p is the same as requiring that edges in the dual lattice are open with probability 1 - p. Now consider C_{0}, the cluster in the square lattice containing the origin. If p < p_{c}, then this cluster is almost surely finite. As the figure below shows, this means that there is almost surely an open cycle in the dual lattice containing the origin in its interior (shown in green).
To summarize, we see that θ(p) = 0 for those values of p for which there is almost surely an open cycle in the dual lattice containing the origin in its interior. We will therefore assume that p = 1/2 and show that there is almost surely an open cycle in the dual lattice containing the origin in its interior. From this it follows that θ(1/2) = 0 and hence p_{c} ≥ 1/2. To do this, we will find the probability that there is an open cycle in the dual lattice contained in an annulus and composed of four separate open paths as shown below.
Breaking the problem down even further, we will look at one of the four sides of this rectangular annulus, a rectangle whose dimensions are 3n by n, and find the probability that there is an open path running horizontally across this rectangle. We begin, however, by studying a square. Here is a fundamental observation: Suppose we consider R, a rectangular portion of the square lattice with k by l vertices. We may also consider R', a k - 1 by l + 1 rectangular portion of the dual lattice:
Recall that P_{p}(H(R)) denotes the probability that there is a horizontal open path across R when edges are open with probability p. In the same way, P_{1-p}(V(R')) is the probability that there is an open vertical path across R'. Since there is either a horizontal open path across R or an open vertical path across R', we must have
If we consider the case that R is an n + 1 by n rectangle, then R' is an n by n + 1 rectangle. We then have P_{1/2}(H(R)) = P_{1/2}(V(R')) = 1/2. If instead we take R to be an n by n square S, a horizontal path has a shorter distance to travel so we have
Notice that this is independent of n, the size of the square. Now that we understand the probability of having an open path across a square, we would like to use this understanding to study more general rectangles. Remember that we would eventually like to understand rectangles of dimension 3n by n. The following technique is due to Russo, Seymour and Welsh. Consider the figure to the left, in which we have two squares of sides n and 2n. Consider the event F_{1} described by a configuration of open paths, like the blue and red ones shown below. We know that the probability of an open vertical path in the smaller square is greater than 1/2. In the same way, the probability of having a horizontal path, like the red one, open is greater than 1/2 as well. The fact that we want the red path to enter the smaller square introduces another factor of 1/2:
Now let F_{2} be the event that there is an open path across a 3n by 2n rectangle. We break this into smaller pieces by considering the rectangle to consist of two squares of dimension 2n by 2n overlapping in an n by 2n rectangle. Applying our previous result, we have
Continuing in this way, we may continue to understand wider rectangles by breaking them into smaller rectangles that overlap in a square. For instance, the figure to the right illustrates an argument showing that the probability there is an open path across a 2n by n rectangle is greater than 2^{-15}.
With some additional work, we see that the probability that there is an open horizontal path across a 3n by n rectangle is greater than 2^{-25}. Remember that we are interested in finding an open cycle around the annulus shown below. Decomposing the annulus into four rectangles whose dimensions are 3n by n, we see that the probability of having an open cycle in the annulus is greater than (2^{-25})^{4} = 2^{-100}. That's a pretty small number, but it's enough to do the trick. Again, the important point is that this number does not depend on the size of the annulus.
We now imagine ringing the origin with a set of concentric annuli as shown.
We now know that the probability there is no open cycle in an annulus is smaller than 1 - 2^{-100}. Therefore, if we look at k concentric annuli, the probability that there is an open cycle encircling the origin is smaller than (1 - 2^{-100})^{k}. Since 1 - 2^{-100} < 1, we see, by allowing k to become arbitrarily large, that the probability that there is no open cycle encircling the origin is smaller than any positive number and hence zero. Therefore, there is almost surely an open cycle encircling the origin, which means that C_{0} is almost surely finite and hence θ(1/2) = 0 and p_{c} ≥ 1/2. This completes the proof of Harris' Theorem. To complete the proof of the Harris-Kesten theorem, we also need to prove Kesten's theorem, which says that p_{c} ≤ 1/2. We will do this by assuming that p_{c} > 1/2 and arriving at a contradiction. The argument sketched here is not Kesten's original proof. If we assume that p_{c} > 1/2, then p = 1/2 is below the critical probability. Recalling Menshikov's theorem, which we stated earlier, we then have
where S_{x,n} is the event that an open path runs from x to a vertex whose distance from x is n. Consider an n by n square S. Since there are n vertices on the left side of the square and any horizontal path has length at least n - 1, we have By choosing n to be very large, we can make the term n e^{-an} as small as we like. For instance, we may choose n to be so large that n e^{-an} < 1/4. The inequality above then says that P_{1/2}(H(S)) < 1/4. However, this contradicts the fact that P_{1/2}(H(S)) ≥ 1/2. Therefore, our assumption that 1/2 < p_{c} must be incorrect, which completes the proof of Kesten's theorem. Some other resultsThe early days of mathematical work in percolation focused on finding critical probabilities for various combinatorial graphs. After a considerable amount of effort, relatively little is known. Here is a summary. The scenario we have presented, where edges are declared to be open or closed, is usually known as bond percolation. Alternatively, we may also consider site percolation, in which the vertices of the graph are declared to be open with probability p. We then study paths in which every vertex visited is open. Shown below, for instance, are the vertices in the triangular lattice T and a configuration of open vertices with p = 0.3.
Aside from these results and those for regular graphs, which are similar to the binary tree we looked at earlier, very little is known about the exact values of critical probabilities for other graphs. Conformal InvarianceAs mentioned before, early work in percolation theory concentrated on finding critical probabilities. Recently, however, theoretical physics has raised interesting questions in some different directions. It should be clear that the critical probability depends on geometric properties of the graph. However, there is evidence that certain percolation probabilities remain unchanged under "conformal maps." A conformal map of the plane is a function from one region in the plane to another that may distort distances but must preserve angles. Examples are provided by complex analytic functions such as f(z) = e^{z}. Motivated by theoretical physics and numerical experiments, Aizenman and Langlands, Pouliot and Saint-Aubin conjectured that certain "crossing probabilities" were unchanged after the application of a conformal map, as we'll now explain. To begin, we will consider a region D in the plane with four marked points P_{1}, P_{2}, P_{3}, and P_{4}. These points divide the boundary of D into four arcs A_{1}, A_{2}, A_{3}, and A_{4}. We will call this data a 4-marked region and denote it by D_{4}. If L is some lattice in the plane, we may consider the portion inside D and a configuration in which either sites or bonds are open with probability p. By P(D_{4},L, p), we mean the probability that there is an open crossing from arc A_{1} to A_{3} contained inside D. The example P(H(R)) that we considered earlier is a special case of this construction. Finally, imagine that the lattice L is scaled by a parameter δ to obtain δL. Here are some examples:
Consider what happens as δ → 0. Since the distance between the two arcs in δL grows arbitarily large and, if p < p_{c}, Menshikov's theorem says that the size of the clusters decays exponentially, we must have P(D_{4}, δL, p) → 0 if p < p_{c}. Conversely, if p > p_{c}, we are guaranteed to have an infinite cluster, and it follows that P(D_{4}, δL, p) → 1. The interesting question is what happens if p = p_{c}.
This is a remarkable conjecture for it says that the limiting probability does not depend on the lattice and is unchanged when the region is changed by a conformal map. In fact, Cardy, motivated by ideas from conformal field theory, proposed an exact formula for the limiting probability. To understand Cardy's formula, we note that conformal maps provides a great deal of versatility. For instance, any two regions D_{3} with three marked points are related to one another by a conformal map, a fact that follows from the Riemann mapping theorem. If we consider a 4-marked region D_{4} and momentarily forget about the fourth point P_{4}, there is then a conformal map carrying the region D and the three marked points P_{1}, P_{2}, and P_{3} into the equilateral triangle D' with vertices P'_{1} = (1, 0), P'_{2} = (1/2, /2), and P'_{3} = (0, 0). Now the fourth point P_{4} corresponds to a point P'_{4} = (x, 0) as shown below. Assuming that conformal invariance holds, Cardy's remarkable formula, interpreted in this way, says that P(D_{4}) = x. As yet, conformal invariance and Cardy's formula have only been rigorously proven for the case of site percolation on the triangular lattice T, a result due to Smirnov in 2001. However, there is considerable evidence to suggest that they hold in wide generality. Power laws and universalityTheoretical physics also predicts that a number of properties depend, not on the geometric properties of the graph, but only on its dimension. For instance, we know that the critical probability for site percolation on the triangular lattice is 1/2. This says that θ(p) = 0 for p < 1/2. If, however, we ask how θ(p) behaves for values of p above 1/2, physics indicates that the following should hold:
We call such an expression a power law. Besides demonstrating the relatively simple behavior of θ(p) in the case of site percolation on the triangular lattice, the conjecture further says that the exponent 5/36 should describe θ(p) for percolation on any planar lattice near its critical probability p_{c}. That is, θ(p) ≈ (p - p_{c})^{5/36} for any planar lattice. This is an indication of universality, the hypothesis, based on physical reasoning, that there are critical exponents, such as 5/36, that depend only on the dimension and not on the details of the particular lattice. In fact, it has been mathematically verified, by Lawler, Schramm, and Werner, that, for site percolation on the triangular lattice, θ(p) has this form. At present, however, we are not able to say that this result holds more generally. Other, similar results hold as well. If we consider χ(p), the average number of vertices in C_{0} when p < p_{c}, physics tells us that it should be true that
Also, suppose that p = p_{c} and consider P(n ≤ |C_{0}| < ∞), the probability that the cluster containing the origin contains a finite number of vertices greater than or equal to n. Physics again predicts that
Both of these power laws have been proven for site percolation on the triangular lattice by the work of Kesten, Lawler, Schramm, Smirnov, and Werner. At this time, it appears that theoretical physics, more specifically, conformal field theory and quantum gravity, have a great deal to say about percolation. One of the challenges before mathematicians is to create a mathematically rigorous theory to support these physical insights by, in particular, verifying conformal invariance for percolation on two-dimensional lattices and the universality of power laws. Mathematics has traditionally been tightly connected to physics. It is interesting to see that the link between these two disciplines is still so vital. The mathematical importance of this field is demonstrated by the fact that Wendelin Werner was awarded mathematics' highest honor, the Fields Prize, in part for his work in percolation.
References
David Austin Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services. |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |