Percolation II: The Integer Lattice

This post presents a couple of results regarding percolation on {{\mathbb Z}^d} (and especially {{\mathbb Z}^2}), which are valuable mainly because they tell us that percolation on these graphs is non-trivial i.e. none of the critical probabilities is 0 or 1. But on a concrete level, they actually do more: they give explicit bounds on the critical probabilities.

Proposition 1. For bond percolation on {{\mathbb Z}^2}, we have {p_T\geq \frac{1}{3}}

This proof hinges on counting {\mu_n({\mathbb Z}^2)}, the number of self-avoiding walks of length {n} (in the language of graph theory, paths) on {{\mathbb Z}^2}. We will make use of the obvious bound

\displaystyle \mu_n({\mathbb Z}^2)\leq 4\cdot 3^{n-1}.

Proof: The middle inequality was discussed in the previous post, so it suffices to do the first and last ones. Let’s start with the first.

Choose some {p<\frac{1}{3}} and consider the bond percolation on {{\mathbb Z}^2} where every bond is open with probability {p}. Let {C_0} be the cluster containing the origin and note that any site in {C_0} must be connected to the origin by an open path starting at the origin. (It’s a little hard to see, but this is where the self-avoiding condition comes in: if the walk from the origin to the site intersected itself, we could “excise” the loop and then get another path that’s more likely to be open, because it is shorter.) The size of {C_0} is bounded by the number {X} of such paths and the probaibility of a path of length {n} being open is {p^n}, so

\displaystyle \mathop{\mathbb E}(|C_0|)\leq \mathop{\mathbb E}(X)=\sum_{n=0}^{\infty} p^n\mu_n\leq 1+\sum_{n=1}^{\infty} p^n\cdot 4\cdot 3^{n-1}<\infty,

because {p<\frac{1}{3}}. Since the expected size of {C_0} is finite for any {p<\frac{1}{3}}, we conclude that {p_T\geq \frac{1}{3}}. \Box

Proposition 2. For bond percolation on {{\mathbb Z}^2}, we have {p_H\leq \frac{2}{3}}

This proof hinges on studying the dual graph of {{\mathbb Z}^2} (more on this in a second) and using a technical lemma that I won’t prove.

For a graph {\Lambda}, the dual {\Lambda^*} is a graph whose vertices correspond to faces of {\Lambda} with edges connecting adjacent faces in {\Lambda}. For example,

\displaystyle \left({\mathbb Z}^2\right)^*={\mathbb Z}^2+(0.5,0.5).

In the context of percolation, we call the sites and bonds of {\Lambda^*} dual sites and dual bonds, with a dual bond taken to be closed when the original bond is open, or vice versa. (We’re associating bonds to dual bonds here by {e\mapsto e^*} where {e^*} is the edge of {\Lambda^*} connecting the faces of {\Lambda} that meet at {e}).

In {{\mathbb Z}^2}, if {H} is a finite subgraph of {{\mathbb Z}^2} with vertex set {C}, then {{\mathbb Z}^2\setminus C} must have some infinite component {C_{\infty}}. We define {\partial^{\infty} C} to be the bonds of {\left({\mathbb Z}^2\right)^*} that are dual to bonds of {{\mathbb Z}^2} joining {C} and {C_{\infty}}.

Put another way, you take some finite subgraph, and look at all the edges connecting it to the infinite component of it’s complement. This set of edges maps to some set of edges in the dual, and that set is {\partial^{\infty} C}. The lemma says that {\partial^{\infty} C} looks like the boundary of {H}.

Lemma 3. {\partial^{\infty} C} is a cycle containing {C}.

Proof: As before, take some {p>\frac{2}{3}}, and consider bond percolation on {{\mathbb Z}^2} where each bond is open with probability {p}. Take dual bonds {e^*} to be open if {e} is closed and vice versa, and call a cycle in the dual consisting of open bonds an open dual cycle.

Let {L_k} be the segment connecting the origin to {(k,0)} and {S} some dual cycle of length {2\ell} surrounding {L_k}. {S} must cut the {x}-axis between {k+0.5} and {0.5(2\ell-3)}, so there are fewer than {\ell} choices for the dual bond that cuts the {x}-axis. The rest of {S} is a path of length {2\ell-1}, and since the dual of {{\mathbb Z}^2} is isomorphic to {{\mathbb Z}^2}, there are {\mu_{2\ell-1}} possibilities for this portion of {S}. In total, we have fewer than {\ell \mu_{2\ell-1}} possibilities for {S}.

Let {Y_k} be the number of open dual cycles surrounding {L_k}. An open dual cycle of length {2\ell} occurs with probability {(1-p)^{2\ell}}, so

\displaystyle \mathop{\mathbb E}(Y_k)\leq \sum_{\ell=k+2}^{\infty} \ell\mu_{2\ell-1}(1-p)^{2\ell}\leq \sum_{\ell =k+2}^{\infty} \ell\cdot 4\cdot 3^{2\ell-2}(1-p)^{2\ell}<\infty,

because {p>\frac{2}{3}\implies 3(1-p)<1}.

This means that {\mathop{\mathbb E}(Y_k)\rightarrow 0} as {k\rightarrow \infty}, and in particular, {\mathop{\mathbb E}(Y_k)<1} eventually. If {A_k} is the event that {Y_k=0}, this means that {\mathop{\mathbb P}(A_k)>0} (if {P(A_k)} were never zero, then integrating over a set of measure 1 would have to give something that is at least 1). Now let {B_k} be the event that all the bonds in {L_k} are open, which occurs with probability {p^k}, which is independent of {A_k}.

If {A_k} and {B_k} both occur, then {C_0} cannot be contained in a cycle of the dual graph (since {Y_k=0}), so it must be infinite by our lemma. Thus

\displaystyle \theta_0(p)=\mathop{\mathbb P}(|C_0|=\infty)\geq \mathop{\mathbb P}(A_k\cap B_k)= \mathop{\mathbb P}(A_k)\mathop{\mathbb P}(B_k)\geq \mathop{\mathbb P}(A_k)p^k>0,

so there is an infinite open cluster with probability 1. This means that {p_H\geq p}, and since {p} is any probability {>\frac{2}{3}}, we have {p_H\leq \frac{2}{3}}. \Box

Remark 1. \leavevmode

  1. Recalling that {p_T\leq p_H}, we can chain these together into

    \displaystyle \frac{1}{3}\leq p_T\leq p_H\leq \frac{2}{3},

    showing that the critical probabilities for bond percolation on {{\mathbb Z}^2} are non-trivial.


  2. The bound of {\mu_n\leq 4\cdot 3^{n-1}} is crude, and these inequalities can be sharpened by using tighter inequalities. For example, noting that {\mu_{m+n}\leq \mu_m\mu_n} (you can just concatenate paths), we see by Fekete’s lemma that {\mu_n^{1/n}\rightarrow \lambda}. This {\lambda} is called the connective constant, and our result becomes

    \displaystyle \frac{1}{\lambda}\leq p_T\leq p_H\leq 1-\frac{1}{\lambda},

    so we just need to estimate this constant, which I won’t get into but can certainly be done.


  3. Since {{\mathbb Z}^d} contains {{\mathbb Z}^2} within it for {d\geq 2}, we can recall the result at the end of the previous post to obtain

    \displaystyle \frac{1}{2d-1}\leq p_T({\mathbb Z}^d)\leq p_H({\mathbb Z}^d)\leq \frac{2}{3},

    giving non-triviality of critical probabilities for {{\mathbb Z}^d}.


These results are only for bond percolation. We can use them to say things about site percolation as well though, by showing that percolation is “more likely” in the site model than the bond model.

Theorem 4. For any graph {\Lambda}, we have {p_H^{\mathrm{s}}\geq p_H^{\mathrm{b}}} and {p_T^{\mathrm{s}}\geq p_T^{\mathrm{b}}}.

Proof: The key claim is that for any site {x}, integer {n}, and probability {p},

\displaystyle \mathop{\mathbb P}^{\text{s}}(|C_x|\geq n)\leq p \mathop{\mathbb P}^{\text{b}}(|C_x|\geq n).

(Here, {\mathop{\mathbb P}^{\text{b}}} and {\mathop{\mathbb P}^{\text{s}}} are the probability measures induced by bond and site percolation where bonds and sites are open with probability {p}, respectively. Throughout this proof, we use such superscripts to indicate the type of percolation being considered.)

From this claim, we let {n\rightarrow \infty} to obtain {\theta_x^{\text{s}}\leq p\theta_x^{\text{b}}}. Then, if {\theta_x^{\text{b}}=0}, we have {\theta_x^{\text{s}}=0} as well, so {p_H^{\text{s}}\geq p_H^{\text{b}}}.

For {p_T}, we argue similarly:

\displaystyle \chi_x^{\text{s}}=\sum_{n=1}^{\infty} \mathop{\mathbb P}^{\text{s}}(|C_x|\geq n)\leq \sum_{n=1}^{\infty} \mathop{\mathbb P}^{\text{b}}(|C_x|\geq n)\leq p\chi_x^{\text{b}},

and so {\chi_x^{\text{b}}<\infty\implies \chi_x^{\text{s}}<\infty}, meaning that {p_T^{\text{s}}\geq p_T^{\text{b}}.}

It remains to show the claim. We begin by writing {\mathop{\mathbb P}^{\text{s}}(|C_x|\geq n)} as

\displaystyle \mathop{\mathbb P}^{\text{s}}(|C_x|\geq n\mid x\text{ is open})\mathop{\mathbb P}^{\text{s}}(x\text{ is open})+\mathop{\mathbb P}^{\text{s}}(|C_x|\geq n\mid x\text{ is closed})\mathop{\mathbb P}^{\text{s}}(x\text{ is closed}).

If {x} is closed, {C_x} is empty, so the second term is zero. Thus we see that

\displaystyle \mathop{\mathbb P}^{\text{s}}(|C_x|\geq n)=p\mathop{\mathbb P}^{\text{s}}(|C_x|\geq n\mid x\text{ is open}),

and so our claim is equivalent to

\displaystyle p\mathop{\mathbb P}^{\text{s}}(|C_x|\geq n\mid x\text{ is open})\geq \mathop{\mathbb P}^{\text{b}}(|C_x|\geq n).

Next, we note that since the event {|C_x^{\text{s}}|\geq n} depends only on vertices that are within {n} of {x}, it suffices to consider the subgraph {\Lambda_n} of points within {n} of {x}. The idea now is to construct a sequence of subsets of {V(\Lambda_n)} (the vertex set of {\Lambda_n)} denoted {\mathcal{T}=(R_t, D_t, U_t)_{t=1}^{\ell}} such that {R_{\ell}= C_x^{\text{s}}}. The constant {\ell} is random, and the letters {R, D, U} stand for reached, dead, and untested respectively.

The construction is as follows:

  1. Let {R_1=\{x\}, U_1=V(\Lambda)\setminus \{x\}, D_1=\emptyset}
  2. Pick a bond {e_t=y_tz_t} where {y_t\in R_t} and {z_t\in U_t}. Remove {z_t} from {U_t}. If {y_t} is open, add it to {R_t} and leave {D_t} alone; otherwise add it to {D_t} and leave {R_t} alone. This gives the new triplet.
  3. Repeat 2 until no such bond {e_t} exists, and set {t=\ell}, completing the process. (This must happen eventually because {\Lambda_n} is finite.)

In the end, {R_{\ell}} is a connected set of open sites with no neighbors in {U_{\ell}} that is disjoint from the sites of {D_{\ell}} which are all closed, so it is exactly {C_x^{\text{s}}}. Note that the conditional probability of {z_t} being open is always {p}.

Now, consider an analogous sequence for {C_x^{\text{b}}}, {\mathcal{T}'}. The difference here is that after picking {e_t}, we check whether {e_t} is open (conditioned on the sequence up to that open). This probability is always {p} as well, so {\mathcal{T}} and {\mathcal{T}'} have the same distribution.

In particular, {|C_x^{\text{s}}|=|R_{\ell}|} and {|R'_{\ell'}|} have the same distribution. Since {R'_{\ell'}} is contained in {C_{x}^{\text{b}}} (it is the vertex set of the subgraph spanned by the bond we found to be open), the claim follows, concluding the proof. \Box

So this shows that {p_H^{\text{s}}, p_T^{\text{s}}} are not zero. To show that they are also not 1, we need another inequality, namely:

Theorem 5. For percolation on an infinite connected graph with maximum degree {\Delta},

\displaystyle p_H^{\mathrm{s}}\leq 1-(1-p_H^{\mathrm{b}})^{\Delta-1}.

The proof is similar, but more involved, so I’ll skip it here. The upshot of all this is that {p_T^{\text{s}}, p_T^{\text{b}}, p_H^{\text{b}}, p_H^{\text{s}}} are all non-trivial for {{\mathbb Z}^2}. In the next few posts, we’ll take the next step and actually determine {p_T^{\text{b}}} and {p_H^{\text{s}}}.


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s