Percolation I: Critical Probabilities

This is the first in a series of posts about percolation theory, which I’m studying this summer. The main text I’m using is Bollobas’s book on the subject, and I plan to follow it pretty closely. There should be around six posts, culminating in the proof of the Harris-Kesten theorem, a major result about percolation on {{\mathbb Z}^2}. This material corresponds to the first three chapters of Bollobas, with some omissions and rearrangement.

1. The Big Picture

The idea is to consider some graph (prototypically {{\mathbb Z}^d} but theoretically any graph), and choose a random subgraph of this graph by selecting each edge to be part of the subgraph with probability {p}. Alternatively, do the same thing with vertices instead of edges, and take the subgraph to be the one induced by the chosen vertices.

Some terminology:

  • The edges are bonds
  • The vertices are sites
  • The chosen edges/vertices are open
  • The chosen graph is the open subgraph
  • The connected components of the open subgraph are open clusters

According to this language, the two models described above are bond percolation and site percolation.

The physical motivation for this model is a liquid percolating through a solid lattice, where the open bonds/sites represent the bonds/sites that the liquid can pass through. The main question suggested by this interpretation is whether the liquid will be able to pass through the lattice completely, which corresponds to the existence of an infinite open cluster.

The Harris-Kesten theorem mentioned above answers this question for bond percolation on {{\mathbb Z}^2}. It shows that for {p>\frac{1}{2}}, there is an infinite open cluster with probability 1, and for {p<\frac{1}{2}} there is an infinite open cluster with probability 0.

This post takes the first step toward proving this result by defining two critical probabilities that are closely related to this question, and then computing them for some simple graphs. Before we can even take that step though, we must construct a probability space {(\Sigma, \mathop{\mathbb P})} in which to work. For a graph {G=(V,E)}, we take:

  • {\Omega=\{0,1\}^{|E|}} to be the set of all arrangements of open edges, where 0 represents a closed edge and 1 represents an open edge; 
  • {\Sigma} to be the {\sigma}-algebra on {\Omega} generated by the cylinders

    \displaystyle C(F, \sigma)=\{\omega \in \Omega\mid \omega_f = \sigma_f\text{ for } f\in F\},\quad F\subset E\text{ and }\sigma =\{0,1\}^{|F|};


  • {\mathop{\mathbb P}} to be the probability measure on {\Sigma} induced by

    \displaystyle \mathop{\mathbb P}(C(F, \sigma))=\left(\prod_{\substack{f\in F\\ \sigma_f=1}} p\right)\left(\prod_{\substack{f\in F\\ \sigma_f=0}} 1-p\right).

In everything that follows, all probabilities are defined according to this measure.

2. Critical Probabilities

For a site {x}, let {C_x} be the open cluster containing {x}, and let {\theta_x(p)} be the probability that {C_x} is infinite.

Proposition 1. There is a critical probability {p_H} such that {\theta_x(p)=0} if {p<p_H} and {\theta_x(p)>0} if {p<p_H}, for all {x}.

(The notation {p_H} is in honor of Hammersley, who first proposed this model.)

Proof: Take any two sites {x, y} such that {|x-y|=d} (this is the distance induced by {G}). Then {\theta_x(p)\geq p^d \theta_y(p)}, since if there is an infinite open cluster containing {y} and a path from {y} to {x}, there will be an infinite open cluster containing {x} as well. Thus, if {\theta_x(p)=0} for one site, then {\theta_x(p)=0} for all sites, and if {\theta_x(p)>0} for one site, then {\theta_x(p)>0} for all sites. If we show that {\theta_x(p)} is an increasing function of {p}, the existence of {p_H} follows.

To see the increasing behavior (which is intuitively clear), consider assigning each edge {e} an independent random variable {X_e\sim \text{Uni}[0,1]}, and then taking it to be open if {X_e<p}. If {p_1<p_2}, the subgraph obtained with probability {p_1} will always be contained in the subgraph obtained with probability {p_2}, so {\theta_x(p)} must be increasing. \Box

We now connect this {p_H} to our original question about the existence of an infinite open cluster.

Corollary 2. Let {E} be the event that there is an infinite open cluster. Then {\mathop{\mathbb P}(E)=1} if {p>p_H} and {\mathop{\mathbb P}(E)=0} if {p<p_H}.

Proof: The event {E} is a tail event, so by the Kolmogorov 0-1 law, it can only take the values 0 and 1. If {p<p_H}, then {\mathop{\mathbb P}(E)\leq \sum_{\text{sites }x} \theta_x(p)=0,} so {\mathop{\mathbb P}(E)=0}. If {p>p_H}, then {\mathop{\mathbb P}(E)\geq \theta_x(p)>0} for at least one site, so {\mathop{\mathbb P}(E)=1}. \Box

So to understand when there is an infinite open cluster, it suffices to understand {p_H}.

When {p<p_H}, any {C_x} is almost surely finite, but it’s expected size might not be. Set {\chi_x(p)=\mathop{\mathbb E}(|C_x|)}. By the same arguments as before, {\chi_x(p)} increases with {p}, and it is either finite for all sites or for no sites. Thus we define

\displaystyle p_T=\sup\{p\mid \chi_x(p)<\infty\},

with the notation in honor of Temperley this time.

We have been deliberately ambiguous until now about whether we are working with bond percolation or site percolation in this section, and in fact we mean both. That is, there are actually four critical probabilities: {p_T^{\text{b}}, p_T^{\text{s}}, p_H^{\text{b}}, p_H^{\text{s}}}. And since each of these depends on the choice of graph, we actually need to write {p_T^{\text{s}}(G)}. This notation is a bit cumbersome though, so we refrain from using it except where absolutely necessary.

One obvious relationship between {p_T} and {p_H} is that {p_T\leq p_H}. Some more difficult relations are known, but we’ll look at those in a later post. For now, let’s do an example.

3. Computing the Critical Probabilities

Determining {p_T} and {p_H} in general is quite hard (after all, the Harris-Kesten theorem basically boils down to doing this for {{\mathbb Z}^2}, and is already highly non-trivial), but there are some simple graphs for which it can be done. We do an example with bond percolation.

Suppose {G=T_k} is the tree in which every vertex has degree {k+1}, except for the root which has degree {k}. Call the root {v_0} and let {T_{k,n}} be the subgraph obtained by truncating this graph {n} levels down from the root. We write {\pi_n} for the probability that, in bond percolation with probability {p}, there is an open path of length {n} from {v_0} to a leaf of {T_{k,n}}.

For there to be an open path of length {n} from {v_0} to a leaf of {T_{k,n}}, there must be an open edge between {v_0} and some other vertex, and then an open path from that vertex to a leaf. This gives

\displaystyle \pi_n=1-(1-p\pi_{n-1})^k.

Consider the function {f(x)=1-(1-px)^k}. The {\pi_n} result from iterating this function starting with {\pi_0=1}, so we need to study it’s fixed points. We have {f(0)=0} and {f(1)<1}. If {f'(0)>1}, then {f(\epsilon)>\epsilon} for some small {\epsilon>0}, but {f(1)<1}, so there is some fixed point {x_0}. Otherwise, the unique fixed point is at {x=0}. Concretely, {f'(0)=pk}, so this condition reduces to {p>\frac{1}{k}}.

In the case where {p>\frac{1}{k}}, we see that {\pi_{n-1}\geq x_0\implies \pi_n\geq x_0}, and since {\pi_0=1\geq x_0}, we always have {\pi_n\geq x_0}. But this {\pi_n} is a lower bound on {\theta_{v_0}(p)}, since if there is an infinite open cluster containing {v_0} there must be a path to the bottom, so {\theta_{v_0}(p)>0}, and so {p_H\leq \frac{1}{k}}.

On the other hand, if {p\leq \frac{1}{k}}, the {\pi_n} converge to the unique fixed point at 0, meaning that {\theta_{v_0}(p)=0}. It follows that {p_H=\frac{1}{k}} for {T_k}.

We can also do {p_T}: a site at depth {\ell} is part of {C_{v_0}} with probability {p^{\ell}}, so

\displaystyle \chi_{v_0}(p)=\sum_{y\in T_k} \mathop{\mathbb P}(y\in C_{v_0})=\sum_{\ell=0}^{\infty} k^{\ell}p^{\ell},

which is finite if and only if {pk<1}. Thus {p_T=\frac{1}{k}} as well.

A few remarks about this calculation: the fact that {p_T=p_H} here is not unusual. This is true for a very general class of graphs.

Also, it turns out that this tree {T_k} has, in some sense, the lowest critical probability possible. To see this, take {G} to be a graph with maximum degree {\Delta}. If {y\in C_x}, then there is an open path from {y} to {x}, so we can bound {\chi_x(p)} by the number of paths in {G} that start at {x}. Using our information about the maximum degree, this gives

\displaystyle \chi_x(p)\leq 1+\sum_{\ell=1}^{\infty} \Delta(\Delta-1)^{\ell-1} p^{\ell},

which converges exactly when {p<\frac{1}{\Delta-1}}. This means that {p_T\geq \frac{1}{\Delta-1}}, and since {p_H\geq p_T}, this bound holds for {p_H} as well. In {T_k}, {\Delta=k+1}, and this bound is attained.

So the tree {T_k} is special in more ways than one. It turns out that the more “tree-like” a graph is, the more easily {p_T} and {p_H} can be computed. Unfortunately, {{\mathbb Z}^2} is nothing like a tree, so a different approach is required to tackle it.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s