Percolation models

Percolation theory was introduced by Broadbent and Hammersley [7] as a mathematical model (or a collection of mathematical models) of random media. Consider the square grid; let each site be ``occupied'' with probability $p$ or ``vacant'' with probability $(1-p)$, independently of all the other sites on the lattice. A ``percolation cluster'' on this grid is a collection of nearest-neighbour occupied sites -- a site animal! The number of occupied sites within a cluster is called its ``mass'' (see figure 15). Instead of occupying the sites on the lattice, we can also consider occupying the bonds or a combination of both -- giving rise to site-percolation, bond-percolation and site-bond-percolation. Percolation clusters can (and have) been used to model a wide array of phenomena; from oil deposits to forest fires (see [38,17] and references therein)

Figure 15: Percolation clusters: five clusters of mass $1$, one of mass $2$, two of mass $3$ and two of mass $4$.

As the occupation probability, $p$, is increased from zero, the average or typical clusters become larger (both in terms of the number of sites and geometric size). If we define $P(p)$, ``the percolation probability'', to be the probability that the origin is part of an infinite cluster, then we find that below a certain value $p=p_c$, called the critical probability, $P(p)$ is always zero. As $p$ is increased above $p_c$, the percolation probability becomes non-zero (see figure 16). This change in behaviour is an example of a phase transition.

Figure 16: The expected behaviour of the percolation probability, $P(p)$.

As an example consider an orchard, in which all of the trees are arranged on the vertices of a large square grid. Suppose that a tree will become infected with a nasty disease with probability $p$ if one of its neighbours is infected. Say a few of the trees in the orchard become infected and the disease spreads through the orchard. After a few days the disease has stopped spreading and there are a number of clusters of diseased trees. Obviously, in this scenario we wish to minimise the size of these clusters; if we know how $p$ varies with the distance between trees (presumably it decreases as we place trees further apart), how far apart do we have to plant the trees to stop the epidemic from destroying a large portion of the orchard? We could just place the trees a long way apart (a small value of $p$), but then there would not be many trees in the orchard and we would go broke. For the orchard to be viable we need lots of trees, and so we need to choose a large value of $p$, but not so large that the orchard is endangered. If $p$ is chosen below the critical probability, then we know that the average cluster size will be quite small, and the disease cannot spread far. On the other hand, if $p$ is above the critical probability, then there is a non-zero probability that the disease could spread to a significant part of the orchard. Hence we must choose $p$ as close to $p_c$ as we dare, while still ensuring that $p$ is less than $p_c$.

The percolation probability, $P(p)$, can be written in terms of site animals enumerated according to their area and another parameter, the site-perimeter. The site-perimeter of a site animal is the number of nearest-neighbour sites that are not part of the animal (see figure 17).

Figure 17: A site animal and its site-perimeter. This animal contains $15$ sites, and has a site-perimeter of $21$.

Let us write the generating function of all finite site animals, $A$, enumerated according to both area and site-perimeter as

$$G(p,q) = \sum_{A} p^{\vert A\vert} q^{\mbox{\scriptsize site.p}(A)}$$ (6)

where $\vert A\vert$ and site.p$(A)$ denote, respectively, the area and site-perimeter of an animal $A$. The probability that the origin is part of a given cluster $A$ is equal to $\vert A\vert p^{\vert A\vert} (1-p) ^{\mbox{\scriptsize site.p}(A)}$, since $\vert A\vert$ sites must be occupied, site.p$(A)$ sites must be vacant, and there are exactly $\vert A\vert$ ways of placing the animal over the origin. Consequently the probability that the origin is part of a finite cluster is (expanding in $q=1-p$ about $q=0$)

$$\sum_{A} \vert A\vert (1-q)^{\vert A\vert} q ^{\mbox{\scriptsize ... ...= \left. (1-q) \left( \frac{\partial G}{\partial p} \right)\right\vert _{p=1-q}$$ (7)

and the percolation probability is the probability that the origin is not part of a finite cluster (nor vacant):

$$P(p) = 1 - q - \left. (1-q) \left( \frac{\partial G}{\partial p} \right)\right\vert _{p=1-q}.$$ (8)

So a knowledge of $G(p,q)$ would give us an expression for $P(p)$. Unfortunately computing the site-perimeter of polyominoes is a very difficult problem; to date, only polygons that are fully convex (rectangles, Ferrers diagrams, stacks, staircase polygons, directed convex polygons and convex polygons) have been solved by site-perimeter. In chapter 6 we find the site-perimeter generating function of the simplest family of non-convex polygons -- bargraph polygons.