Percolation IV: Harris’s Theorem

We’re ready to start proving the Harris-Kesten theorem, so from now on, everything we say is about bond percolation in {{\mathbb Z}^2}. The global structure of the argument is in three steps:

  1. Show that {\theta(1/2)=0} (this implies {p_H\geq 1/2})
  2. Show that for {p>1/2}, there is an infinite open cluster with probability 1 (this implies {p_H\leq 1/2})
  3. Show that {\chi(p)<\infty} for {p<1/2} (this implies that {p_T\geq 1/2})
  4. Conclude that {p_T=p_H=1/2}

This post will accomplish the first step.

1. Crossing Probabilities

We start with some more definitions: a rectangle {R} in {{\mathbb Z}^2} is a set of sites of the form {[a,b]\times [c,d]}. We say this rectangle has size {k\times \ell}, where {k=b-a+1, \ell=d-c+1}. It contains {k\ell} sites and {2k\ell-k-\ell} bonds.

This rectangle has two duals: a horizontal dual

\displaystyle R^h=[a+0.5, b-0.5]\times [c-0.5, d+0.5]

and a vertical dual

\displaystyle R^v=[a-0.5, b+0.5]\times [c+0.5, d-0.5].

We have that {R^h} is a {k-1\times \ell+1} rectangle and {R^v} is a {k+1\times \ell-1} rectangle. Additionally,

\displaystyle \left(R^h\right)^v=\left(R^v\right)^h=R.

Finally, we define an open horizontal crossing of a rectangle {R} to be an open path in {R} connecting a site {(a,x)} to a site {(b,y)}, and similarly for an open vertical crossing. We write {H(R)} and {V(R)} for the events that such crossings exist.

The following lemma is, according to Bollobas, the “reason” why {p_H=1/2}. It is intuitively clear, but working through all the details is a bit of slog, so let’s just take it at face value.

Lemma 1. Let {R} be a rectangle in {{\mathbb Z}^2} or its dual. Then exactly one of {H(R)} and {V(R^h)} holds.

Why exactly is this lemma the “reason” cited above? The following corollary sheds some light on that.

Corollary 2. If {R} and {R'} are {k\times \ell-1} and {k-1\times \ell} rectangles in {{\mathbb Z}^2}, then

\displaystyle \mathop{\mathbb P}_p(H(R))+\mathop{\mathbb P}_{1-p}(V(R'))=1.

Proof: The bonds of the dual are open when the bonds of the original graph are closed and vice versa. So by Lemma 1, each configuration of bonds will satisfy exactly one of {H(R)} and {V(R^h)}, so

\displaystyle \mathop{\mathbb P}(H(R))+\mathop{\mathbb P}(V(R^h))=1.

But {R^h} is indistinguishable from {R'}, so the result follows. \Box

Now if we take {k=\ell} in this corollary, we get that for an {n+1\times n} rectangle {R},

\displaystyle \mathop{\mathbb P}_{1/2}(H(R))+\mathop{\mathbb P}_{1/2}(V(R'))=1.

But because the rectangle {R'} has dimension {n\times n+1}, the event {V(R')} has the same probability as {H(R')}, so they are both equal to {1/2}.

So the intuition is somehow that when {p>1/2}, it’s more likely you have a horizontal crossing than not, so you get an infinite open cluster. When {p<1/2}, it’s less likely than not, so you don’t. The critical behavior is at exactly {p=1/2}.

More importantly, we get that if {S} is an {n\times n} square,

\displaystyle \mathop{\mathbb P}_{1/2}(V(S))=\mathop{\mathbb P}_{1/2}(H(S))\geq \frac{1}{2},

where we have the inequality because this event must be more likely than the crossing for an {n\times n+1} rectangle. This is a bound on the crossing probabilities of a square. We now have to extend this result to rectangles.

2. Squares to Rectangles

This next lemma relates crossings of squares to crossings of rectangles. We use the notation {[n]=[0,n]}.

Lemma 3. Consider {R=[m]\times [2n]}, an {m\times 2n} rectangle with {m\geq n}. Let {X(R)} be the event that there are open paths {P_1, P_2} such that {P_1} crosses the {n\times n} square {S=[n]\times [n]} from top to bottom and {P_2} lies within {R} and joins some site on {P_1} to the right hand side of {R}. Then

\displaystyle \mathop{\mathbb P}_p(X(R))\geq \frac{\mathop{\mathbb P}_p(H(R))\mathop{\mathbb P}_p(V(S))}{2}.

Proof: Suppose {V(S)} occurs, so an open path {P_0} crosses {S} from top to bottom. Such a path cuts {S} into two pieces, one on the left and on the right. Let {LV(S)} be the left-most open vertical crossing (when one exists). For any {P_1}, the event {\{LV(S)=P_1\}} does not depend on bonds to the right of {P_1}.

The key claim is that

\displaystyle \mathop{\mathbb P}_p(X(R)\mid LV(S)=P_1)\geq \frac{\mathop{\mathbb P}(H(R))}{2}.

Since {V(S)} is a disjoint union of events of the form {\{LV(S)=P_1\}}, this implies that

\displaystyle \mathop{\mathbb P}_p(X(R)\mid V(S))\geq\frac{\mathop{\mathbb P}_p(H(R))}{2},

which rearranges to

\displaystyle \mathop{\mathbb P}_p(X(R)\cap V(S))\geq \frac{\mathop{\mathbb P}_p(H(R))\mathop{\mathbb P}_p(V(S))}{2}.

But {X(R)} occurring means that {V(S)} does as well, so {\mathop{\mathbb P}_p(X(R)\cap V(S))=\mathop{\mathbb P}_p(X(R))}, and the lemma is proven.

For the claim, let {P} be the path (that may or may not be open) formed by the union of {P_1} and it’s reflection {P_1'} in the horizontal axis of {R}, with a bond joining {P_1} to {P_1'}. This path is a vertical crossing of the rectangle {[n]\times [2n]}.

Now, there is an open path {P_3} crossing {R} horizontally with probability {\mathop{\mathbb P}_p(H(R))}. This path must meet {P}, and the probability it does so at a site of {P_1} is at least {\mathop{\mathbb P}_p(H(R))/2}. Thus the event that there is an open path {P_2} in {R} to the right of {P} joining a site of {P_1} to the right end of {R} has probability at least {\mathop{\mathbb P}_p(H(R))/2}. This event depends only bonds to the right of {P}, and all such bonds in {S} are to the right of {P_1}. These bonds are independent of {LV(S)=P_1}, so

\displaystyle \mathop{\mathbb P}_p(Y(P_1)\mid LV(S)=P_1)=\mathop{\mathbb P}_p(Y(P_1))\geq \mathop{\mathbb P}_p(H(R))/2.

If {Y(P_1)} and {LV(S)=P_1} both occur, then {X(R)} does as well. So

\displaystyle \mathop{\mathbb P}_p(X(R)\mid LV(S)=P_1)\geq \mathop{\mathbb P}_p(H(R))/2,

proving the claim and thus the lemma. \Box

Remark 1. If we instead take an {m_!\times 2n} rectangle {R} and an {m_2\times 2n} rectangle {R'}, this proof will show that

\displaystyle h(m_1+m_2-n, 2n)\geq \frac{h(m_1, 2n)h(m_2,2n)}{2^5},

and we will use this formulation later on.

(This argument is much simpler than it seems – drawing the picture goes a long way.)

3. Thinning the Rectangles Out

With this lemma, we can now bound the crossing probabilities for non-square rectangles. In particular, we look at a {3n\times 2n} rectangle. For convenience, let {h_p(m,n)=\mathop{\mathbb P}_p(H(R))}, and since it’s the case we really care about, {h(m,n)=h_{1/2}(m,n)}.

Corollary 4. We have {h(3n, 2n)\geq 2^{-7}}.

Proof: Take two square {2n\times 2n} rectangles {R, R'} that overlap in an {n\times 2n} strip. This {n\times 2n} strip contains two {n\times n} squares; call {S} the smaller of these. (Again, draw the picture!) Let {X'(R')} be the event {X(R)} described above, but reflected horizontally. Then we apply Lemma 4 to {R} (which is coincidentally a square) to get

\displaystyle \mathop{\mathbb P}_p(X'(R'))=\mathop{\mathbb P}_p(X(R))\geq \frac{\mathop{\mathbb P}_p(H(R))\mathop{\mathbb P}_p(V(S))}{2}.

Now, we call back to Harris’s lemma from the previous post: the events {X(R), X'(R'), H(S)} are all increasingly and positive correlated. If they all hold, so does {H(R\cup R')}, and so we have

\displaystyle h(3n,2n)=\mathop{\mathbb P}_{1/2}(H(R\cup R'))\geq \mathop{\mathbb P}_{1/2}(X'(R'))\mathop{\mathbb P}_{1/2}(X(R))\mathop{\mathbb P}_{1/2}(H(S)).

This is then

\displaystyle \geq \frac{\mathop{\mathbb P}_{1/2}(H(R))^2\mathop{\mathbb P}_{1/2}(V(S))^2\mathop{\mathbb P}_{1/2}(H(S))}{4}.

But by our observation at the end of Section 1, this is at least

\displaystyle \frac{(0.5^2)^3}{4}=2^{-7},

as desired. \Box

A {3n\times 2n} rectangle isn’t quite thing enough for our purposes, but the rest of the thinning can be done using the remark after Lemma 3. We have

\displaystyle h(5n,2n)\geq \frac{h(3m,2n)^2}{2^5}\geq 2^{-19},

and so

\displaystyle h(6n,2n)\geq \frac{h(5n,2n)h(2n,2n)}{2^5}\geq 2^{-25},

and this is the bound that our proof of {\theta(1/2)=0} will hinge on.

4. Harris’s Theorem

Theorem 5. For bond percolation on {{\mathbb Z}^2}, {\theta(1/2)=0}.

Proof: Let

\displaystyle r(C_0)=\sup\{d(x,0)\mid x\in C_0\}.

The actual result we’ll show is that

\displaystyle \mathop{\mathbb P}_{1/2}(r(C_0)\geq n)\leq n^{-c}

for a constant {c}, and the stated result follows from this.

When {p=1/2}, bonds in the dual lattice are open with probability {1/2}, so by the computation above, the probability a {6n\times 2n} rectangle has a crossing the long way is at least {2^{-25}}. Consider 4 such rectangles oriented to form an annulus around the origin, with the “hole” in the annulus being a {2n\times 2n} square centerd at the origin.

By Harris’s lemma, the probability each of these rectangles is crossed the long way by an open path in the dual is at least {\epsilon=2^{-100}}. The union of these paths is an open dual cycle around the annulus.

Let {A_k} be the square annulus centered on {(0.5, 0.5)} with inner radius {4^k} and outer radius {3\cdot 4^k}. Let {E_k} be the event that {A_k} contains an open dual cycle surrounding the inside of {A_k}, and thus the origin.

By our argument above, {\mathop{\mathbb P}(E_k)\geq \epsilon} for each {k}. All of the {E_k} are independent, and if {E_k} holds, then there is no path from inside {A_k} to outside {A_k}, so {r(C_0)\leq 1+3\cdot 4^k\leq 4^{k+1}.}


\displaystyle \mathop{\mathbb P}\left(r(C_0)\geq 4^{\ell+1}\right)\leq \mathop{\mathbb P}_{1/2}\left(\bigcap_{k=1}^{\ell} E_k^c\right)=\prod_{k=1}^{\ell} \mathop{\mathbb P}_{1/2}(E_k^c)\leq (1-\epsilon)^{\ell},

which is the desired bound. \Box


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