A mini course on percolation theory

Jerey E. Steif
Abstract. These are lecture notes based on a mini course on percolation which
was given at the Jyv askyl a summer school in mathematics in Jyv askyl a, Fin-
land, August 2009. The point of the course was to try to touch on a number
of dierent topics in percolation in order to give people some feel for the eld.
These notes follow fairly closely the lectures given in the summer school. How-
ever, some topics covered in these notes were not covered in the lectures (such
as continuity of the percolation function above the critical value) while other
topics covered in detail in the lectures are not proved in these notes (such as
conformal invariance).
Contents
1. Introduction 2
2. The model, nontriviality of the critical value and some other basic facts 2
2.1. Percolation on Z
2
: The model 2
2.2. The existence of a nontrivial critical value 5
2.3. Percolation on Z
d
9
2.4. Elementary properties of the percolation function 9
3. Uniqueness of the innite cluster 10
4. Continuity of the percolation function 13
5. The critical value for trees: the second moment method 15
6. Some various tools 16
6.1. Harris inequality 17
6.2. Margulis-Russo Formula 18
7. The critical value for Z
2
equals 1/2 19
7.1. Proof of p
c
(2) = 1/2 assuming RSW 19
7.2. RSW 24
7.3. Other approaches. 26
8. Subexponential decay of the cluster size distribution 28
9. Conformal invariance and critical exponents 30
9.1. Critical exponents 30
2 Jerey E. Steif
9.2. Elementary critical exponents 31
9.3. Conformal invariance 33
10. Noise sensitivity and dynamical percolation 34
References 36
Acknowledgment 38
1. Introduction
Percolation is one of the simplest models in probability theory which exhibits what
is known as critical phenomena. This usually means that there is a natural pa-
rameter in the model at which the behavior of the system drastically changes.
Percolation theory is an especially attractive subject being an area in which the
major problems are easily stated but whose solutions, when they exist, often re-
quire ingenious methods. The standard reference for the eld is [12]. For the study
of percolation on general graphs, see [23]. For a study of critical percolation on the
hexagonal lattice for which there have been extremely important developments,
see [36].
In the standard model of percolation theory, one considers the the d-dimensional
integer lattice which is the graph consisting of the set Z
d
as vertex set together
with an edge between any two points having Euclidean distance 1. Then one xes
a parameter p and declares each edge of this graph to be open with probability p
and investigates the structural properties of the obtained random subgraph con-
sisting of Z
d
together with the set of open edges. The type of questions that one
is interested in are of the following sort.
Are there innite components? Does this depend on p? Is there a critical
value for p at which innite components appear? Can one compute this critical
value? How many innite components are there? Is the probability that the origin
belongs to an innite component a continuous function of p?
The study of percolation started in 1957 motivated by some physical con-
siderations and very much progress has occurred through the years in our under-
standing. In the last decade in particular, there has been tremendous progress
in our understanding of the 2-dimensional case (more accurately, for the hexago-
nal lattice) due to Smirnovs proof of conformal invariance and Schramms SLE
processes which describe critical systems.
2. The model, nontriviality of the critical value and some other
basic facts
2.1. Percolation on Z
2
: The model
We now dene the model. We start with the graph Z
2
which, as a special case of
that described in the introduction, has vertices being the set Z
2
and edges between
pairs of points at Euclidean distance 1. We will construct a random subgraph of Z
2
A mini course on percolation theory 3
Figure 1. A percolation realization (from [12])
as follows. Fix p [0, 1] which will be the crucial parameter in the model. Letting
each edge be independenly open with probability p and closed with probability
1 p, our random subgraph will be dened by having the same vertex set as Z
2
but will only have the edges which were declared open. We think of the open edges
as retained or present. We will think of an edge which is open as being in state 1
and an edge which is closed as being in state 0. See Figure 1 for a realization.
Our rst basic question is the following: What is the probability that the
origin (0, 0) (denoted by 0 from now on) can reach innitely many vertices in our
random subgraph? By Exercise 2.1 below, this is the same as asking for an innite
self-avoiding path from 0 using only open edges. Often this function (of p), denoted
here by (p), is called the percolation function. See Figure 2.
One should denitely not get hung up on any measure-theoretic details in
the model (essentially since there are no measure theoretic issues to speak of) but
nonetheless I say the above more rigorously. Let E denote the edge set of Z
2
. Let
=

eE
0, 1, F be the -algebra generated by the cylinder sets (the events
4 Jerey E. Steif
Figure 2. The percolation function (from [12])
which only depend on a nite number of edges) and let P
p
=

eE

p
where

p
(1) = p,
p
(0) = 1 p. The latter is of course a product measure. is the
set of possible outcomes of our random graph and P
p
describes its distribution.
This paragraph can be basically ignored and is just for sticklers but we do use the
notation P
p
to describe probabilities when the parameter used is p.
Let C(x) denote the component containing x in our random graph; this is just
the set of vertices connected to x via a path of open edges. Of course C(x) depends
on the realization which we denote by but we do not write this explicitly. We
abbreviate C(0) by C. Note that P
p
([C[ = ) = (p).
Exercise 2.1: For any subgraph of Z
2
(i.e., for every ), show that [C[ = if and
only if there is a self-avoiding path from 0 to consisting of open edges (i.e.,
containing innitely many edges).
Exercise 2.2: Show that (p) is nondecreasing in p. Do NOT try to compute any-
thing!
A mini course on percolation theory 5
Exercise 2.3: Show that (p) cannot be 1 for any p < 1.
2.2. The existence of a nontrivial critical value
The main result in this section is that for p small (but positive) (p) = 0 and
for p large (but less than 1) (p) > 0. In view of this (and exercise 2.2), there
is a critical value p
c
(0, 1) at which the function (p) changes from being 0 to
being positive. This illustrates a so-called phase transition which is a change in the
global behavior of a system as we move past some critical value. We will see later
(see Exercises 2.7 and 2.8) the elementary fact that when (p) = 0, a.s. there is no
innite component anywhere while when (p) > 0, there is an innite component
somewhere a.s.
Let us nally get to proving our rst result. We mention that the method of
proof of the rst result is called the rst moment method, which just means you
bound the probability that some nonnegative integer-valued random variable is
positive by its expected value (which is usually much easier to calculate). In the
proof below, we will implicitly apply this rst moment method to the number of
self-avoiding paths of length n starting at 0 and for which all the edges of the path
are open.
Theorem 2.1. If p < 1/3, (p) = 0.
Proof. : Let F
n
be the event that there is a self-avoiding path of length n starting at
0 using only open edges. For any given self-avoiding path of length n starting at 0
in Z
2
(not worrying if the edges are open or not), the probability that all the edges
of this given path are open is p
n
. The number of such paths is at most 4(3
n1
)
since there are 4 choices for the rst step but at most 3 choices for any later step.
This implies that P
p
(F
n
) 4(3
n1
)p
n
which 0 as n since p < 1/3. As
[C[ = F
n
n, we have that P
p
[C[ = = 0; i.e., (p) = 0.
Theorem 2.2. For p suciently close to 1, we have that (p) > 0.
Proof. : The method of proof to be used is often called a contour or Peierls
argument, the latter named after the person who proved a phase transition for
another model in statistical mechanics called the Ising model.
The rst key thing to do is to introduce the so-called dual graph (Z
2
)

which
is simply Z
2
+ (
1
2
,
1
2
). This is nothing but our ordinary lattice translated by the
vector (
1
2
,
1
2
). See Figure 3 for a picture of Z
2
and its dual (Z
2
)

. One then sees

that there is an obvious 1-1 correspondence between the edges of Z
2
and those of
(Z
2
)

. (Two corresponding edges cross each other at their centers.)

Given a realization of open and closed edges of Z
2
, we obtain a similar real-
ization for the edges of (Z
2
)

by simply calling an edge in the dual graph open if

6 Jerey E. Steif
Figure 3. Z
2
and its dual (Z
2
)

(from [12])
and only if the corresponding edge in Z
2
is open. Observe that if the collection of
open edges of Z
2
is chosen according to P
p
(as it is), then the distribution of the
set of open edges for (Z
2
)

will trivially also be given by P

p
.
A key step is a result due to Whitney which is pure graph theory. No proof
will be given here but by drawing some pictures, you will convince yourself it is
very believable. Looking at Figures 4 and 5 is also helpful.
Lemma 2.3. [C[ < if and only if a simple cycle in (Z
2
)

surrounding 0
consisting of all closed edges.
Let G
n
be the event that there is a simple cycle in (Z
2
)

surrounding 0 having
length n, all of whose edges are closed. Now, by Lemma 2.3, we have
P
p
([C[ < ) = P
p
(

n=4
G
n
)

n=4
P
p
(G
n
)

n=4
n4(3
n1
)(1 p)
n
A mini course on percolation theory 7
Figure 4. Whitney (from [12])
since one can show that the number of cycles around the origin of length n (not
worrying about the status of the edges) is at most n4(3
n1
) (why?, see Exercise
2.4) and the probability that a given cycle has all its edges closed is (1 p)
n
. If
p >
2
3
, then the sum is < and hence it can be made arbitrarily small if p is
chosen close to 1. In particular, the sum can be made less than 1 which would
imply that P
p
([C[ = ) > 0 for p close to 1.
8 Jerey E. Steif
Figure 5. Whitney (picture by Vincent Beara)
Remark:
We actually showed that (p) 1 as p 1.
Exercise 2.4: Show that the number of cycles around the origin of length n is at
most n4(3
n1
).
Exercise 2.5: Show that (p) > 0 for p >
2
3
.
Hint: Choose N so that

nN
n4(3
n1
)(1 p)
n
< 1. Let E
1
be the event that all
edges are open in [N, N] [N, N] and E
2
be the event that there are no simple
cycles in the dual surrounding [N, N]
2
consisting of all closed edges. Look now
at E
1
E
2
.
It is now natural to dene the critical value p
c
by
p
c
:= supp : (p) = 0 = infp : (p) > 0.
With the help of Exercise 2.5, we have now proved that p
c
[1/3, 2/3]. (The
model would not have been interesting if p
c
were 0 or 1.) In 1960, Harris [16]
proved that (1/2) = 0 and the conjecture made at that point was that p
c
= 1/2
and there was indications that this should be true. However, it took 20 more years
before there was a proof and this was done by Kesten [18].
Theorem 2.4. [18] The critical value for Z
2
is 1/2.
A mini course on percolation theory 9
In Chapter 7, we will give the proof of this very fundamental result.
2.3. Percolation on Z
d
The model trivially generalizes to Z
d
which is the graph whose vertices are the
integer points in R
d
with edges between vertices at distance 1. As before, we let
each edge be open with probability p and closed with probability 1p. Everything
else is dened identically. We let
d
(p) be the probability that there is a self-
avoiding open path from the origin to for this graph when the parameter p is
used. The subscript d will often be dropped. The denition of the critical value in
d dimensions is clear.
p
c
(d) := supp :
d
(p) = 0 = infp :
d
(p) > 0.
In d = 1, it is trivial to check that the critical value is 1 and therefore things
are not interesting in this case. We saw previously that p
c
(2) (0, 1) and it turns
out that for d > 2, p
c
(d) is also strictly inside the interval (0, 1).
Exercise 2.6: Show that
d+1
(p)
d
(p) for all p and d and conclude that p
c
(d +
1) p
c
(d). Also nd some lower bound on p
c
(d). How does your lower bound
behave as d ?
Exercise 2.7. Using Kolmogorovs 0-1 law (which says that all tail events have
probability 0 or 1), show that P
p
(some C(x) is innite) is either 0 or 1. (If you
are unfamiliar with Kolmogorovs 0-1 law, one should say that there are many
(relatively easy) theorems in probability theory which guarantee, under certain
circumstances, that a given type of event must have a probability which is either
0 or 1 (but they dont tell which of 0 and 1 it is which is always the hard thing).)
Exercise 2.8. Show that (p) > 0 if and only if P
p
(some C(x) is innite)=1.
Nobody expects to ever know what p
c
(d) is for d 3 but a much more interesting
question to ask is what happens at the critical value itself; i.e. is
d
(p
c
(d)) equal
to 0 or is it positive. The results mentioned in the previous section imply that it
is 0 for d = 2. Interestingly, this is also known to be the case for d 19 (a highly
nontrivial result by Hara and Slade ([15]) but for other d, it is viewed as one of
the major open questions in the eld.
Open question: For Z
d
, for intermediate dimensions, such as d = 3, is there per-
colation at the critical value; i.e., is
d
(p
c
(d)) > 0?
Everyone expects that the answer is no. We will see in the next subsection why
one expects this to be 0.
2.4. Elementary properties of the percolation function
Theorem 2.5.
d
(p) is a right continuous function of p on [0, 1]. (This might be a
good exercise to attempt before looking at the proof.)
10 Jerey E. Steif
Proof. : Let g
n
(p) := P
p
(there is a self-avoiding path of open edges of length n
starting from the origin). g
n
(p) is a polynomial in p and g
n
(p) (p) as n .
Now a decreasing limit of continuous functions is always upper semi-continuous
and a nondecreasing upper semi-continuous function is right continuous.
Exercise 2.9. Why does g
n
(p) (p) as n as claimed in the above proof?
Does this convergence hold uniformly in p?
Exercise 2.10. In the previous proof, if you dont know what words like upper semi-
continuous mean (and even if you do), redo the second part of the above proof
with your hands, not using anything.
A much more dicult and deeper result is the following due to van den Berg and
Keane ([4]).
Theorem 2.6.
d
(p) is continuous on (p
c
(d), 1].
The proof of this result will be outlined in Section 4. Observe that, given the
above results, we can conclude that there is a jump discontinuity at p
c
(d) if and
only if
d
(p
c
(d)) > 0. Since nice functions should be continuous, we should believe
that
d
(p
c
(d)) = 0.
3. Uniqueness of the innite cluster
In terms of understanding the global picture of percolation, one of the most natural
questions to ask, assuming that there is an innite cluster, is how many innite
clusters are there?
My understanding is that before this problem was solved, it was not com-
pletely clear to people what the answer should be. Note that, for any k 0, 1, 2, . . . , ,
it is trivial to nd a realization for which there are k innite clusters. (Why?).
The following theorem was proved by Aizenman, Kesten and Newman ([1]). A
much simpler proof of this theorem was found by Burton and Keane ([8]) later on
and this later proof is the proof we will follow.
Theorem 3.1. If (p) > 0, then P
p
( a unique innite cluster ) = 1.
Before starting the proof, we tell (or remind) the reader of another 0-1 Law which
is dierent from Kolmogorovs theorem and whose proof we will not give. I will not
state it in its full generality but only in the context of percolation. (For people who
are familiar with ergodic theory, this is nothing but the statement that a product
measure is ergodic.)
Lemma 3.2. If an event is translation invariant, then its probability is either 0 or
1. (This result very importantly assumes that we are using a product measure, i.e,
doing things independently.)
A mini course on percolation theory 11
Translation invariance means that you can tell whether the event occurs or not
by looking at the percolation realization but not being told where the origin is.
For example, the events there exists an innite cluster and there exists at least
3 innite clusters are translation invariant while the event [C(0)[ = is not.
Proof of Theorem 3.1. Fix p with (p) > 0. We rst show that the number of
innite clusters is nonrandom, i.e. it is constant a.s. (where the constant may
depend on p). To see this, for any k 0, 1, 2, . . . , , let E
k
be the event that the
number of innite cluster is exactly k. Lemma 3.2 implies that P
p
(E
k
) = 0 or 1 for
each k. Since the E
k
s are disjoint and their union is our whole probability space,
there is some k with P
p
(E
k
) = 1, showing that the number of innite clusters is
a.s. k.
The statement of the theorem is that the k for which P
p
(E
k
) = 1 is 1 assuming
(p) > 0; of course if (p) = 0, then k is 0. It turns out to be much easier to rule
out all nite k larger than 1 than it is to rule out k = . The easier part, due
to Newman and Schulman ([25]), is stated in the following lemma. Before reading
the proof, the reader is urged to imagine for herself why it would be absurd that,
for example, there could be 2 innite clusters a.s.
Lemma 3.3. For any k 2, 3, . . ., it cannot be the case that P
p
(E
k
) = 1.
Proof. : The proof is the same for all k and so we assume that P
p
(E
5
) = 1. Let
F
M
= there are 5 innite clusters and each intersects [M, M]
d
. Observe that
F
1
F
2
. . . . . . and
i
F
i
= E
5
. Therefore P
p
(F
i
)
i
1. Choose N so that
P
p
(F
N
) > 0.
Now, let

F
N
be the event that all innite clusters touch the boundary of
[N, N]
d
. Observe that (1) this event is measurable with respect to the edges
outside of [N, N]
d
and that (2) F
N


F
N
. Note however that these two events
are not the same. We therefore have that P
p
(

F
N
) > 0. If we let G be the event
that all the edges in [N, N]
d
are open, then G and

F
N
are independent and hence
P
p
(G

F
N
) > 0. However, it is easy to see that G

F
N
E
1
which implies that
P
p
(E
1
) > 0 contradicting P
p
(E
5
) = 1.
It is much harder to rule out innitely many innite clusters, which we do
now. This proof is due to Burton and Keane. Let Q be the # of innite clusters.
Assume P
p
(Q = ) = 1 and we will get a contradiction. We call z an encounter
point (e.p.) if
1. z belongs to an innite cluster C and
2. Cz has no nite components and exactly 3 innite components.
See Figure 6 for how an encounter points looks.
Lemma 3.4. If P
p
(Q = ) = 1, then P
p
(0 is an e.p. ) > 0.
12 Jerey E. Steif
Figure 6. An encounter point (from [12])
Proof. : Let F
M
= at least 3 innite clusters intersect [M, M]
d
.
Since F
1
F
2
. . . and
i
F
i
= 3 innite clusters, we have, under the
assumption that P
p
(Q = ) = 1, that P
p
(F
i
)
i
1 and so we can choose N so
that P
p
(F
N
) > 0.
Now, let

F
N
be the event that outside of [N, N]
d
, there are at least 3 innite
clusters all of which touch the boundary of [N, N]
d
. Observe that (1) this event
is measurable with respect to the edges outside of [N, N]
d
and that (2) F
N


F
N
and so P
p
(

F
N
) > 0. Now, if we have a conguration with at least 3 innite clusters
all of which touch the boundary of [N, N]
d
, it is easy to see that one can nd
a conguration within [N, N]
d
which, together with the outside conguration,
makes 0 an e.p. By independence, this occurs with positive probability and we have
P
p
(0 is an e.p. ) > 0. [Of course the conguration we need inside depends on the
outside; convince yourself that this argument can be made completely precise.]
Let = P
p
(0 is an encounter point) which we have seen is positive under
the assumption that P
p
(Q = ) = 1. The next key lemma is the following.
A mini course on percolation theory 13
Lemma 3.5. For any conguration and for any N, the number of encounter points
in [N, N]
d
is at most the number of outer boundary points of [N, N]
d
.
Remark: This is a completely deterministic statement which has nothing to do
with probability.
Before proving it, lets see how we nish the proof of Theorem 3.1. Choose N so
large that (2N +1)
d
is strictly larger than the number of outer boundary points
of [N, N]
d
. Now consider the number of e.p.s in [N, N]
d
. On the one hand, by
Lemma 3.5 and the way we chose N, this random variable is always strictly less
than (2N + 1)
d
. On the other hand, this random variable has an expected value
of (2N + 1)
d
, giving a contradiction.
We are left with the following.
Proof of Lemma 3.5.
Observation 1: For any nite set S of encounter points contained in the same
innite cluster, there is at least one point s in S which is outer in the sense that all
the other points in S are contained in the same innite cluster after s is removed.
To see this, just draw a picture and convince yourself; it is easy.
Observation 2: For any nite set S of encounter points contained in the same
innite cluster, if we remove all the elements of S, we break our innite cluster
into at least [S[ + 2 innite clusters. This is easily done by induction on [S[. It is
clear if [S[ = 1. If [S[ = k + 1, choose, by observation 1, an outer point s. By the
induction hypothesis, if we remove the points in Ss, we have broken the cluster
into at least k+2 clusters. By drawing a picture, one sees, since s is outer, removal
of s will create at least one more innite cluster yielding k + 3, as desired.
Now x N and order the innite clusters touching [N, N]
d
, C
1
, C
2
, . . . , C
k
,
assuming there are k of them. Let j
1
be the number of encounter points inside
[N, N]
d
which are in C
1
. Dene j
2
, . . . , j
k
in the same way. Clearly the number
of encounter points is

k
i=1
j
i
. Looking at the rst cluster, removal of the j
1
encounter points which are in [N, N]
d
C
1
leaves (by observation 2 above) at
least j
1
+2 j
1
innite clusters. Each of these innite clusters clearly intersects the
outer boundary of [N, N]
d
, denoted by [N, N]
d
. Hence [C
1
[N, N]
d
[ j
1
.
Similarly, [C
i
[N, N]
d
[ j
i
. This yields
[[N, N]
d
[
k

i=1
[C
i
[N, N]
d
[
k

i=1
j
i
.

4. Continuity of the percolation function

The result concerning uniqueness of the innite cluster that we proved will be
crucial in this section (although used in only one point).
14 Jerey E. Steif
Proof of Theorem 2.6. Let p > p
c
. We have already established right continuity and
so we need to show that lim
p
() = ( p). The idea is to couple all percolation
realizations, as p varies, on the same probability space. This is not so hard. Let
X(e) : e E
d
be a collection of independent random variables indexed by the
edges of Z
d
and having uniform distribution on [0, 1]. We say e E
d
is p-open if
X(e) < p. Let P denote the probability measure on which all of these independent
uniform random variables are dened.
Remarks:
(i) P(e is popen ) = p and these events are independent for dierent es. Hence,
for any p, the set of es which are p-open is just a percolation realization with
parameter p. In other words, studying percolation at parameter p is the same as
studying the structure of the p-open edges.
(ii) However, as p varies, everything is dened on the same probability space which
will be crucial for our proof. For example, if p
1
< p
2
, then
e : e is p
1
open e : e is p
2
open.
Now, let C
p
be the p-open cluster of the origin (this just means the cluster of
the origin when we consider edges which are p-open). In view of Remark (ii) above,
obviously C
p
1
C
p
2
if p
1
< p
2
and by Remark (i), for each p, (p) = P([C
p
[ = ).
Next, note that
lim
p
() = lim
p
P([C

[ = ) = P([C

[ = for some < p).

The last equality follows from using countable additivity in our big prob-
ability space (one can take going to p along a sequence). (Note that we have
expressed the limit that we are interested in as the probability of a certain event
in our big probability space.) Since [C

[ = for some < p [C

p
[ = , we
need to show that
P([C
p
[ = [C

[ = for some < p) = 0.

If it is easier to think about, this is the same as saying
P([C
p
[ = [C

[ < for all < p) = 0.

Let be such that p
c
< < p. Then a.s. there is an innite -open cluster
I

(not necessarily containing the origin).

Now, if [C
p
[ = , then, by Theorem 3.1 applied to the p-open edges, we have
that I

C
p
a.s. If 0 I

, we are of course done with = . Otherwise, there is

a p-open path from the origin to I

. Let = maxX(e) : e which is < p.

Now, choosing such that , < < p, we have that there is a open path from
0 to I

and therefore [C

[ = , as we wanted to show.
A mini course on percolation theory 15
5. The critical value for trees: the second moment method
Trees, graphs with no cycles, are much easier to analyze than Euclidean lattices
and other graphs. Lyons, in the early 90s, determined the critical value for any
tree and also determined whether one percolates or not at the critical value (both
scenarios are possible). See [21] and [22]. Although this was done for general trees,
we will stick here to a certain subset of all trees, namely the spherically symmetric
trees, which is still a large enough class to be very interesting.
A spherically symmetric tree is a tree which has a root which has a
0
children,
each of which has a
1
children, etc. So, all vertices in generation k have a
k
children.
Theorem 5.1. Let A
n
be the number of vertices in the nth generation (which is of
course just

n1
i=0
a
i
). Then
p
c
(T) = 1/[liminf
n
A
1/n
n
].
Exercise 5.1 (this exercise explains the very important and often used second
moment method). Recall that the rst moment method amounts to using the
(trivial) fact that for a nonnegative integer valued random variable X, P(X >
0) E[X].
(a). Show that the converse of the rst moment method is false by showing that
for nonnegative integer valued random variables X, E[X] can be arbitrarily large
with P(X > 0) arbitrarily small. (This shows that you will never be able to show
that P(X > 0) is of reasonable size based on knowledge of only the rst moment.)
(b). Show that for any nonnegative random variable X
P(X > 0)
E[X]
2
E[X
2
]
.
(This says that if the mean is large, then you can conclude that P(X > 0) might
be reasonably large provided you have a reasonably good upper bound on the
second moment E[X
2
].) Using the above inequality is called the second moment
method and it is a very powerful tool in probability.
We will see that the rst moment method will be used to obtain a lower bound on
p
c
and the second moment method will be used to obtain an upper bound on p
c
.
Proof of Theorem 5.1.
Assume p < 1/[liminf
n
A
1/n
n
]. This easily yields (an exercise left to the reader)
that A
n
p
n
approaches 0 along some subsequence n
k
. Now, the probability that
there is an open path to level n is at most the expected number of vertices on the
nth level connected to the root which is A
n
p
n
. Hence the probability of having an
open path to level n
k
goes to 0 and hence the root percolates with probability 0.
Therefore p
c
(T) 1/[liminf
n
A
1/n
n
].
To show the reverse inequality, we need to show that if p > 1/[liminf
n
A
1/n
n
],
then the root percolates with positive probability. Let X
n
denote the number
16 Jerey E. Steif
of vertices at the nth level connected to the root. By linearity, we know that
E(X
n
) = A
n
p
n
. If we can show that for some constant C, we have that for all n,
E(X
2
n
) CE(X
n
)
2
, (5.1)
we would then have by the second moment method exercise that P(X
n
> 0) 1/C
for all n. The events X
n
> 0 are decreasing and so countable additivity yields
P(X
n
> 0 n) 1/C. But the latter event is the same as the event that the root
is percolating and one is done.
We now bound the second moment in order to establish (5.1). Letting U
v,w
be the event that both v and w are connected to the root, we have that
E(X
2
n
) =

v,wT
n
P(U
v,w
)
where T
n
is the nth level of the tree. Now P(U
v,w
) = p
2n
p
k
v,w
where k
v,w
is the
level at which v and w split. For a given v and k, the number of w with k
v,w
being
k is at most A
n
/A
k
. Hence (after a little computation) one gets that the second
moment above is
A
n
n

k=0
p
2n
p
k
A
n
/A
k
= E(X
n
)
2
n

k=0
1/(p
k
A
k
).
If

k=0
1/(p
k
A
k
) < , then we would have (5.1). We have not yet used that p >
1/[liminf
n
A
1/n
n
] which we now use. If this holds, then liminf
n
(p
n
A
n
)
1/n
1 +
for some > 0. This gives that 1/(p
k
A
k
) decays exponentially to 0 and we have
the desired convergence of the series.
Remark: The above theorem determines the critical value but doesnt say what
happens at the critical value. However, the proof gives more than this and some-
times tells us what happens even at the critical value. The proof gives that

k=0
1/(p
k
A
k
) < implies percolation at p and in certain cases we might have
convergence of this series at p
c
giving an interesting case where one percolates at
the critical value. For example if A
n
2
n
n

(which means that the ratio of the

left and right sides are bounded away from 0 and uniformly in n and which is
possible to achieve) then Theorem 5.1 yields p
c
= 1/2 but furthermore, if > 1,
then

n
k=0
1/(p
k
c
A
k
)

1/n

< and so we percolate at the critical value. For

1, the above sum diverges and so we dont know what happens at p
c
. However,
in fact, Lyons showed that

n
k=0
1/(p
k
A
k
) < is also a necessary condition to
percolate at p. In particular, in the case above with 1, we do not percolate at
the critical value. This yields a phase transition in at a ner scale.
6. Some various tools
In this section, I will state two basic tools in percolation. Although they come up
all the time, we have managed to avoid their use until now. However, now we will
A mini course on percolation theory 17
need them both for the next section, Section 7, where we give the proof that the
critical value for Z
2
is 1/2.
6.1. Harris inequality
Harris inequality (see [16]) tells us that certain random variables are positively
correlated. To state this, we need to rst introduce the important property of a
function being increasing. Let := 0, 1
J
. There is a partial order on given by
_

if
i

i
for all i J.
Denition 6.1. A function f : 0, 1
J
R is increasing if _

implies that
f() f(

). An event is increasing if its indicator function is increasing.

If J is the set of edges in a graph and x and y are vertices, then the event
that there is an open path from x to y is an increasing event.
Theorem 6.2. Let X := X
i

iJ
be independent random variables taking values 0
and 1. Let f and g be increasing functions as above. Then
E(f(X)g(X)) E(f(X))E(g(X)).
To understand this, note that an immediate application to percolation is the fol-
lowing. Let x, y, z and w be 4 vertices in Z
d
, A be the event that there is an open
path from x to y and B be the event that there is an open path from z to w. Then
P(A B) P(A)P(B).
Proof. We do the proof only in the case that J is nite; to go to innite J is done
by approximation. We prove this by induction on [J[. Assume [J[ = 1. Let
1
and

2
take values 0 or 1. Then since f and g are increasing, we have
(f(
1
) f(
2
))(g(
1
) g(
2
)) 0.
Now letting
1
and
2
be independent with distribution X
1
, one can take expec-
tation in the above inequality yielding
E[f(
1
)g(
1
)] +E[f(
2
)g(
2
)] E[f(
2
)g(
1
)] E[f(
1
)g(
2
)] 0.
This says 2E(f(X
1
)g(X
1
)) 2E(f(X
1
))E(g(X
1
)).
Now assuming it is true for [J[ = k 1 and f and g are functions of k
variables, we have, by the law of total expectation
E(f(X
1
, . . . , X
k
)g(X
1
, . . . , X
k
)) = E[E(f(X
1
, . . . , X
k
)g(X
1
, . . . , X
k
)) [ X
1
, . . . , X
k1
].
(6.1)
The k = 1 case implies that for each X
1
, . . . , X
k1
,
E(f(X
1
, . . . , X
k
)g(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
)
E(f(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
)E(g(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
).
Hence (6.1) is
E[E(f(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
)E(g(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
)]. (6.2)
18 Jerey E. Steif
Now E(f(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
) and E(g(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
)
are each increasing functions of X
1
, . . . , X
k1
as is easily checked and hence the
induction assumption gives that (6.2) is
E[E(f(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
)]E[E(g(X
1
, . . . , X
k
) [ X
1
, . . . , X
k1
)] =
E(f(X
1
, . . . , X
k
))E(g(X
1
, . . . , X
k
))
and we are done.
Remark: The above theorem is not true for all sets of random variables. Where
precisely in the above proof did we use the fact that the random variables are
independent?
6.2. Margulis-Russo Formula
This formula has been discovered by a number of people and it describes the
derivative with respect to p of the probability under P
p
of an increasing event A in
terms of the very important concept of inuence or pivotality. Let P
p
be product
measure on 0, 1
J
and let A be a subset of 0, 1
J
which is increasing.
Exercise 6.1. Show that if A is an increasing event, then P
p
(A) is nondecreasing
in p.
Denition 6.3. Given i J, and 0, 1
J
, let
(i)
denote the sequence which
is equal to o of i and is 1 on i and
(i)
denote the sequence which is equal to
o of i and is 0 on i. Given a (not necessarily increasing) event A of 0, 1
J
, let
Piv
i
(A) be the event, called that i is pivotal for A, that exactly one of
(i)
and

(i)
is in A. Let I
p
i
(A) = P
p
(Piv
i
(A)), which we call the inuence at level p of i
on A.
Remarks: The last denition is perhaps a mouth full but contains fundamentally
important concepts in probability theory. In words, Piv
i
(A) is the event that chang-
ing the sequence at location i changes whether A occurs. It is an event which is
measurable with respect to o of i. I
p
i
(A) is then the probability under P
p
that
Piv
i
(A) occurs. These concepts are fundamental in a number of dierent areas,
including theoretical computer science.
Exercise 6.2. Let J be a nite set and let A be the event in 0, 1
J
that there are
an even number of 1s. Determine Piv
i
(A) and I
p
i
(A) for each i and p.
Exercise 6.3. Assume that [J[ is odd and let A be the event in 0, 1
J
that there
are more 1s than 0s. Describe, for each i, Piv
i
(A) and I
1/2
i
(A).
The following is the fundamental Margulis-Russo Formula. It was proved indepen-
dently in [24] and [27].
Theorem 6.4. Let A be an increasing event in 0, 1
J
with J a nite set. Then
d(P
p
(A))/dp =

iJ
I
p
i
(A).
A mini course on percolation theory 19
Exercise 6.4. Let A be the event in 0, 1
J
corresponding to at least one of the
rst two bits being 1. Verify the Margulis-Russo Formula in this case.
Outline of Proof. Let Y
i

iJ
be i.i.d. uniform variables on [0, 1] and let
p
be
dened by
p
i
= 1 if and only if Y
i
p. Then P
p
(A) = P(
p
A) and moreover

p
1
A
p
2
A if p
1
p
2
. It follows that
P
p+
(A) P
p
(A) = P(
p+
A
p
A).
The dierence of these two events contains (with a little bit of thought)

iJ
(
p
Piv
i
(A) Y
i
(p, p +)) (6.3)
and is contained in the union of the latter union (with the open intervals replaced
by closed intervals) together with
Y
i
[p, p +] for two dierent is.
This latter event has probability at most C
2
for some constant C (depending
on [J[). Also, the union in (6.3) is disjoint up to an error of at most C
2
. Hence
P
p+
(A)P
p
(A) =

iJ
P(
p
Piv
i
(A)Y
i
(p, p+))+O(
2
) =

iJ
I
p
i
(A)+O(
2
).
(Note that we are using here the fact that the event that i is pivotal is measurable
with respect to the other variables.) Divide by and let 0 and we are done.
Exercise 6.5. (The square root trick.) Let A
1
, A
2
, . . . , A
n
be increasing events with
equal probabilities such that P(A
1
A
2
. . . A
n
) p. Show that
P(A
i
) 1 (1 p)
1/n
.
Hint: Use Harris inequality.
7. The critical value for Z
2
equals 1/2
There are a number of proofs of this result. Here we will stick more or less to the
original, following [27]. It however will be a little simpler since we will use only
the RSW theory (see below) for p = 1/2. The reason for my doing this older proof
is that it illustrates a number of important and interesting things.
7.1. Proof of p
c
(2) = 1/2 assuming RSW
First, L-R will stand for left-right and T-B for top-bottom. Let J
n,m
be the event
that there is a L-R crossing of [0, n] [0, m]. Let J

n,m
be the event that there is
a L-R crossing of [0, n] (0, m) (i.e., of [0, n] [1, m1]).
Our rst lemma explains a very special property for p = 1/2 which already
hints that this might be the critical value.
Lemma 7.1. P
1/2
(J
n+1,n
) = 1/2.
20 Jerey E. Steif
Proof. This is a symmetry argument using the dual lattice. Let B be the event that
there is a B-T crossing of [1/2, n+1/2] [1/2, n+1/2] using closed edges in the
dual lattice. By a version of Whitneys theorem, Lemma 2.3, we have that J
n+1,n
occurs if and only if the event B fails. Hence for any p, P
p
(J
n+1,n
) + P
p
(B) = 1.
If p = 1/2, we have by symmetry that these two events have the same probability
and hence each must have probability 1/2.
The next theorem is crucial for this proof and is also crucial in Section 9. It will
be essentially proved in Subsection 7.2. It is called the Russo Seymour Welsh or
RSW Theorem and was proved independently in [31] and [26].
Theorem 7.2. For all k, there exists c
k
so that for all n, we have that
P
1/2
(J
kn,n
) c
k
. (7.1)
Remarks: There is in fact a stronger version of this which holds for all p which says
that if P
p
(J
n,n
) , then P
p
(J
kn,n
) f(, k) where f does not depend on n or on
p. This stronger version together with (essentially) Lemma 7.1 immediately yields
Theorem 7.2 above. The proof of this stronger version can be found in [12] but
we will not need this stronger version here. The special case dealing only with the
case p = 1/2 above has a simpler proof due to Smirnov, especially in the context of
the so-called triangular lattice. (In [6], an alternative simpler proof of the stronger
version of RSW can be found.)
We will now apply Theorem 7.2 to prove that (1/2) = 0. This is the rst important
step towards showing p
c
= 1/2 and was done in 1960 by Harris (although by a
dierent method since the RSW Theorem was not available in 1960). As already
stated, it took 20 more years before Kesten proved p
c
= 1/2. Before proving
(1/2) = 0, we rst need a lemma which is important in itself.
Lemma 7.3. Let O() be the event that there exists an open circuit containing 0 in
Ann() := [3, 3]
2
[, ]
2
.
Then there exists c > 0 so that for all ,
P
1/2
(O()) c.
Proof. Ann() is the (nondisjoint) union of four 6 2 rectangles. By Theorem
7.2, we know that there is a constant c

so that for each , the probability of crossing

(in the longer direction) a 6 2 rectangle is at least c

. By Harris inequality, the

probability of crossing each of the 4 rectangles whose union is Ann() is at least
c := c
4
. However, if we have a crossing of each of these 4 rectangles, we clearly
have the circuit we are after.
Lemma 7.4. (1/2) = 0.
A mini course on percolation theory 21
Proof. Let C
k
be the event that there is a circuit in Ann(4
k
) + 1/2 in the dual
lattice around the origin consisting of closed edges. A picture shows that the C
k
s
are independent and Lemma 7.3 implies that P
1/2
(C
k
) c for all k for some
c > 0. It follows that P
1/2
(C
k
i.o. ) = 1 where as usual, C
k
i.o. means that there
are innitely many k so that C
k
occurs. However, the latter event implies by
Lemma 2.3 that the origin does not percolate. Hence (1/2) = 0.
The next lemma is very interesting in itself in that it gives a nite criterion
which implies percolation.
Proposition 7.5. (Finite size criterion) For any p, if there exists an n such that
P
p
(J

2n,n
) .98,
then P
p
([C(0)[ = ) > 0.
To prove this proposition, one rst establishes
Lemma 7.6. For any .02, if P
p
(J

2n,n
) 1 , then P
p
(J

4n,2n
) 1 /2.
Proof. Let B
n
be the event that there exists an L-R crossing of [n, 3n] (0, n). Let
C
n
be the event that there exists an L-R crossing of [2n, 4n] (0, n). Let D
n
be
the event that there exists a T-B crossing of [n, 2n] [0, n]. Let E
n
be the event
that there exists a T-B crossing of [2n, 3n] [0, n].
We have P
p
(D
n
) = P
p
(E
n
) P
p
(B
n
) = P
p
(C
n
) = P
p
(J

2n,n
) 1 .
Therefore P
p
(J

2n,n
B
n
C
n
D
n
E
n
) 1 5. By drawing a picture, one sees
that the above intersection of 5 events is contained in J

4n,n
. Letting

J

4n,n
denote
the event that exists a L-R crossing of [0, 4n] (n, 2n), we have that J

4n,n
and

4n,n
are independent, each having probability at least 1 5 and so
P
p
(J

4n,n


J

4n,n
) = 1 (1 P
p
(J

4n,n
))
2
1 25
2
.
This is at least 1 /2 if .02. Since J

4n,n


J

4n,n
J

4n,2n
, we are done.
Proof of Proposition 7.5.
Choose n
0
such that P
p
(J

2n
0
,n
0
) .98. Lemma 7.6 and induction implies that for
all k 0
P
p
(J

2
k+1
n
0
,2
k
n
0
) 1
.02
2
k
and hence

k0
P
p
((J

2
k+1
n
0
,2
k
n
0
)
c
) < .
We will dene events H
k

k0
where H
k
will be a crossing like J

2
k+1
n
0
,2
k
n
0
except
in a dierent location and perhaps with a dierent orientation. Let H
0
= J

2n
0
,n
0
.
22 Jerey E. Steif
Then let H
1
be a T-B crossing of (0, 2n
0
) [0, 4n
0
], H
2
be a L-R crossing of
[0, 8n
0
] (0, 4n
0
), H
3
be a T-B crossing of (0, 8n
0
) [0, 16n
0
], etc. Since the
probability of H
k
is the same as for J

2
k+1
n
0
,2
k
n
0
, the Borel-Cantelli lemma implies
that a.s. all but nitely many of the H
k
s occur. However, it is clear geometrically
that if all but nitely many of the H
k
s occur, then there is percolation.
Our main theorem in this section is
Theorem 7.7. p
c
= 1/2.
Before doing the proof, we make a digression and explain how the concept of
a sharp threshold yields the main result as explained in [28]. In order not to lose
track of the argument, this digression will be short and more details concerning
this approach will be discussed in subsection 7.3.
The underlying idea is that increasing events A which depend on lots of
random variables have sharp thresholds meaning that the function P
p
(A), as p
increases from 0 to 1, goes very sharply from being very small to being very large.
Exercise 7.1. Let A be the event in 0, 1
J
corresponding to the rst bit being a
1. Note that P
p
(A) = p and hence does not go quickly from 0 to 1 but then again
A does not depend on a lot of random variables. Look at what happens if n = [J[
is large and A is the event that at least half the random variables are 1.
Denition 7.8. A sequence of increasing events A
n
has a sharp threshold if for all
> 0, there exists N such that for all n N, there is an interval [a, a +] [0, 1]
(depending on n) such that
P
p
(A
n
) < for p a
and
P
p
(A
n
) > 1 for p a +.
We claim that if the sequence of events J

2n,n
has a sharp threshold, then p
c
1/2.
The reason for this is that if p
c
were 1/2+ with > 0, then, since the probability
of J

2n,n
at p = 1/2 is not too small due to Theorem 7.2, a sharp threshold would
tell us that, for large n, P
p
(J

2n,n
) would get very large way before p reaches 1/2+.
However, Proposition 7.5 would then contradict the denition of the critical value.
Slightly more formally, we have the following.
Proof of Theorem 7.7 assuming J

2n,n
has a sharp threshold.
First, Lemma 7.4 implies that p
c
1/2. Assume p
c
= 1/2 +
0
with
0
> 0. Then
Theorem 7.2 tells us there is c > 0 such that
P
1/2
(J

2n,n
) c
for all n. Let = min
0
/2, .02, c. Choose N as given in the denition of a
sharp threshold and let [a, a + ] be the corresponding interval for n = N. Since
P
1/2
(J

2N,N
) c , a must be 1/2. Hence 1/2 +
0
/2 a +
0
/2 a + and
A mini course on percolation theory 23
hence P
1/2+
0
/2
(J

2N,N
) 1 .98. By Proposition 7.5, we get P
1/2+
0
/2
([C(0)[ =
) > 0, a contradiction.
We now follow Kestens proof as modied by Russo ([27]). We even do a
slight modication of that so that the stronger version of RSW is avoided; this
was explained to me by A. Balint.
Proof of Theorem 7.7.
Note that Lemma 7.4 implies that p
c
1/2. Assume now that p
c
= 1/2 +
0
with

0
> 0. Let V
n
be the number of pivotal edges for the event J
4n,n
. The key step is
the following proposition.
Proposition 7.9. If p
c
= 1/2 +
0
with
0
> 0, then
lim
n
inf
p[1/2,1/2+
0
/2]
E
p
[V
n
] = .
Assuming this proposition, the Margulis-Russo formula would then give
lim
n
inf
p[1/2,1/2+
0
/2]
(d/dp)P
p
(J
4n,n
) = .
Since
0
> 0 by assumption, this of course contradicts the fact that these proba-
bilities are bounded above by 1.
Proof of Proposition 7.9.
Since J

4n,n/2
is an increasing event, Theorem 7.2 implies that
inf
p[1/2,1/2+
0
/2],n
P
p
(J

4n,n/2
) :=
1
> 0.
Next, letting U
n
be the event that there is a B-T dual crossing of [2n +
1/2, 4n 1/2] [1/2, n + 1/2] consisting of closed edges, we claim that
inf
p[1/2,1/2+
0
/2],n
P
p
(U
n
) :=
2
> 0.
The reason for this is that P
p
(U
n
) is minimized for all n at p = 1/2 +
0
/2,
Proposition 7.5 implies that P
1/2+
0
/2
(J

2n,n
) .98 for all n since 1/2+
0
/2 < p
c
,
and the fact that the event J

2n,n
translated to the right distance 2n and U
n
are
complementary events.
Now, if U
n
occurs, let be the right-most such crossing. (You need to think
about this and convince yourself it is reasonable that, when such a path exists,
there exists a right-most path; I would not worry about a precise proof of this
which can be topologically quite messy). Since is the right-most crossing, given
the path , we know nothing about what happens to the left of . (Although you
do not need to know this, it is worth pointing out that this is some complicated
analogue of what is known as a stopping time and the corresponding strong Markov
property.) Therefore, conditioned on , there is probability at least
1
that there
is a path of open edges from the left of [0, 4n] [0, n/2] all the way to 1 step to
the left of . Note that if this happens, then there is an edge one step away from
the end of this path which is pivotal for J
4n,n
! Let be the lowest such path if
24 Jerey E. Steif
one exists. Conditioned on both and , we know nothing about the area to the
top-left of these curves. Let q be the point where and meet. For each n,
consider the annuli Ann(4
k
) + 1/2 + q (this is our previous annulus but centered
around q) but only for those ks where 4
k
n/2. Lemma 7.3 together with the
fact that the events O() are increasing implies that there is a xed probability

3
, independent of n and p [1/2, 1/2 +
0
/2] and k (with 4
k
n/2), such that
with probability at least
3
, there is an open path from to 1 step to the left
of running within Ann(4
k
) + 1/2 + q in this top-left area. (For dierent ks,
these events are independent but this is not needed). Note that each k where this
occurs gives us a dierent pivotal edge for the event J
4n,n
. Since the number of
ks satisfying 4
k
n/2 goes to innity with n, the proposition is established.
7.2. RSW
In this section, we prove Theorem 7.2. However, it is more convenient to do this
for site percolation on the triangular lattice or equivalently the hexagonal lattice
instead. (In site percolation, the sites of the graph are independently declared to
be white or black with probability p and one asks for the existence of an innite
path of white vertices; edges are not removed.)
(The reader will trust us that the result is equally true on Z
2
and is welcome
to carry out the details.) This simpler proof of RSW for p = 1/2 on the triangular
lattice was discovered by Stas Smirnov and can be found in [13] or in [36].
We rst quickly dene what the triangular lattice and hexagonal lattice are.
The set of vertices consists of those points x +e
i/3
y where x and y are integers.
Vertices having distance 1 have an edge between them. See Figure 7 which depicts
the triangular lattice. The triangular lattice is equivalent to the hexagonal lattice
where the vertices of the triangular lattice correspond to the hexagons. Figure
7 shows how one moves between these representations. It is somehow easier to
visual the hexagonal lattice compared to the triangular lattice. We mention that
the duality in Lemma 2.3 is much simpler in this context. For example, there is a
sequence of white hexagons from the origin out to innity if and only if there is
no path encircling the origin consisting of black hexagons. So, in working with the
hexagonal lattice, one does not need to introduce the dual graph as we did for Z
2
.
Outline of proof of Theorem 7.2 for p = 1/2 for the hexagonal lattice instead. (We
follow exactly the argument in [36].)
The key step is to prove the following lemma. (The modication for the denition
of J
n,m
for the triangular lattice should be pretty clear.)
Lemma 7.10.
P
1/2
(J
2n,m
) (1/4)(P
1/2
(J
n,m
))
2
.
A mini course on percolation theory 25
Figure 7. From sites to cells (picture by O. Schramm and pro-
vided by W. Werner)
Proof. Write P for P
1/2
. If a L-R crossing of [0, n] [0, m] exists, let be the
highest one. has a type of Markov property which says the following. If g
is a L-R path (not necessarily open) of [0, n] [0, m] touching the left and right
26 Jerey E. Steif
sides only once, then the event = g is independent of the percolation process
below g.
If g is such a L-R path (not necessarily open) of [0, n] [0, m], let g

be the
reection of g about x = n (which is then a L-R crossing of [n, 2n] [0, m]. Assume
g does not touch the x-axis (a similar argument can handle that case as well). Let
be the part of the boundary of [0, 2n] [0, m] which is on the left side and below
g (this consists of 2 pieces, the x-axis between 0 and n and the positive y-axis
below the left point of g). Let

be the reection of about x = n. Symmetry

and duality gives that the probability that there is an open path from right below
g to

is 1/2. Call this event A(g).

Observe that if g is a path as above which is open and A(g) occurs, then we
have a path from the left side of [0, 2n] [0, m] to either the right side of this box
or to the bottom boundary on the right side; call this latter event F. We obtain
P(F) = P(
g
(F = g)) P(
g
(A(g) = g)).
A(g) and = g are independent and we get that the above is therefore
1/2

g
P( = g) = P(J
n,m
)/2.
If F

is dened to be the reection about x = n of the event F, then by

Theorem 6.2, P(F F

) (1/4)(P(J
n,m
))
2
. Finally, one observes that F F

J
2n,m
.
Continuing with the proof, we rst note that the analogue of Lemma 7.1
for the triangular lattice is that the probability of a crossing of white (or black)
hexagons of the 2n 2n rhombus in Figure 8 is exactly 1/2 for all n. With some
elementary geometry, one sees that a crossing of such a rhombus yields a crossing
of a n

3n rectangle and hence P(J

n,

3n
) 1/2 for all n. From here, Lemma
7.10 gives the result by induction.
7.3. Other approaches.
We briey mention in this section other approaches to computing the critical value
of 1/2.
Exercise 7.2. (Outline of alternative proof due to Yu Zhang for proving (1/2) = 0
using uniqueness of the innite cluster; this does not use RSW).
Step 1: Assuming that (1/2) > 0, show that the probability that there is
an open path from the right side of [n, n] [n, n] to innity touching this box
only once (call this event E) approaches 1 as n . (Hint: Use the square-root
trick of the previous section, Exercise 6.5.)
Step 2: Let F be the event analogous to E but using the left side instead, G
the analogous event using closed edges in the dual graph and the top of the box
and H the analogous event to G using the bottom of the box. Using step 1, show
that for large n P(E F G H) > 0.
Step 3: Show how this contradicts uniqueness of the innite cluster.
A mini course on percolation theory 27
Figure 8. White top-to-bottom crossing vs. black horizontal
crossing (picture provided by W. Werner)
In the next section, the following very nontrivial result is mentioned but not proved.
Theorem 7.11. In any dimension, if p < p
c
(d), then there exists c = c(p) > 0 so
that the probability that there is an open path from the origin to distance n away
is at most e
cn
.
Exercise 7.3. Use Theorem 7.11 and Lemma 7.1 to show that p
c
(Z
2
) 1/2.
Alternatively, there are at present fairly sophisticated and general results which
imply sharp thresholds, which we have seen is the key to proving that the critical
value is 1/2. An early version of such a result comes from [28], where the following
beautiful result was proved.
Theorem 7.12. Let A
n
be a sequence of increasing events. If (recall Denition 6.3)
lim
n
sup
p,i
I
p
i
(A
n
) = 0,
then the sequence A
n
has a sharp threshold.
28 Jerey E. Steif
Exercise 7.4. Show that lim
n
sup
p,i
I
p
i
(J

2n,n
) = 0.
Hint: Use the fact that (1/2) = 0. (This exercise together with Theorem 7.12
allows us, as we saw after Denition 7.8, to conclude that p
c
(Z
2
) 1/2.)
Theorem 7.12 is however nontrivial to prove. In [6], the threshold property for
crossings is obtained by a dierent method. The authors realized that it could be
deduced from a sharp threshold result in [10] via a symmetrization argument. A
key element in the proof of the result in [10] is based on [17], where it is shown
that for p = 1/2 if an event on n variables has probability bounded away from 0
and 1, then there is a variable of inuence at least log(n)/n for this event. (The
proof of this latter very interesting result uses Fourier analysis and the concept
of hypercontractivity). As pointed out in [10], the argument in [17] also yields
that if all the inuences are small, then the sum of all the inuences is very large
(provided again that the variance of the event is not too close to 0). A sharpened
version of this latter fact was also obtained in [35] after [17]. Using this, one can
avoid the symmetrization argument mentioned above. One of the big advantages
of the approach in [6] is that it can be applied to other models. In particular, with
the help of the sharp threshold result of [10], it is proved in [7] that the critical
probability for a model known as Voronoi percolation in the plane is 1/2. It seems
that at this time neither Theorem 7.12 nor other approaches can achieve this. This
approach has also been instrumental for handling certain dependent models.
8. Subexponential decay of the cluster size distribution
Lots of things decay exponentially in percolation when you are away from criticality
but not everything. I will rst explain three objects related to the percolation
cluster which do decay exponentially and nally one which does not, which is the
point of this section. If you prefer, you could skip down to Theorem 8.1 if you only
want to see the main point of this section.
For our rst exponential decay result, it was proved independently by Men-
shikov and by Aizenman and Barsky that in any dimension, if p < p
c
, the prob-
ability of a path from the origin to distance n away decays exponentially. This
was a highly nontrivial result which had been one of the major open questions
in percolation theory in the 1980s. It easily implies that the expected size of the
cluster of the origin is nite for p < p
c
.
Exercise 8.1. Prove this last statement.
It had been proved by Aizenman and Newman before this that if the expected size
of the cluster of the origin is nite at parameter p, then the cluster size has an
exponential tail in the sense that
P
p
([C[ n) e
cn
for all n for some c > 0 where c will depend on p. This does not follow from the
Menshikov and Aizenman-Barsky result since that result says that the radius of
the cluster of the origin decays exponentially while [C[ is sort of like the radius
A mini course on percolation theory 29
raised to the dth power and random variables who have exponential tails dont
necessary have the property that their powers also have exponential tails.
The above was all for the subcritical case. In the supercritical case, the radius,
conditioned on being nite, also decays exponentially, a result of Chayes, Chayes
and Newman. This says that for p > p
c
,
P
p
(A
n
) e
cn
for all n for some c = c(p) > 0 where A
n
is the event that there is an open path
from the origin to distance n away and [C[ < . Interestingly, it turns out on
the other hand that the cluster size, conditioned on being nite, does not have an
exponential tail in the supercritical regime.
Theorem 8.1. For any p > p
c
, there exists c = c(p) < so that for all n
P
p
(n [C[ < ) e
cn
(d1)/d
.
Note that this rules out the possible exponential decay of the tail of the cluster
size. (Why?) As can be seen by the proof, the reason for this decay rate is that
it is a surface area eect. Here is the 2 line proof of this theorem. By a law of
large numbers type thing (and more precisely an ergodic theorem), the number of
points belonging to the innite cluster in a box with side length n
1/d
should be
about (p)n. However, with probability a xed constant to the n
(d1)/d
, the inner
boundary has all edges there while the outer boundary has no edges there which
gives what we want.
Lemma 8.2. Assume that (p) > 0. Fix m and let X
m
be the number of points
in B
m
:= [m, m]
d
which belong to the innite cluster and F
m
be the event that
X
m
[B
m
[(p)/2. Then
P(F
m
) (p)/2.
Proof. Clearly E(X
m
) = [B
m
[(p). We also have
E(X
m
) = E[X
m
[F
m
]P(F
m
) +E[X
m
[F
c
m
]P(F
c
m
) [B
m
[P(F
m
) +[B
m
[(p)/2.
Now solve for P(F
m
).
Proof of Theorem 8.1.
Using the denition of B
m
as in the previous lemma, we let F be the event that
there are at least [B
n
1/d[(p)/2 points in [0, 2n
1/d
]
d
which reach the inner boundary.
Let G be the event that all edges between points in the inner boundary are on and
let H be the event that all edges between points in the inner boundary and points
in the outer boundary are closed. Clearly these three events are independent. The
probability of F has, by Lemma 8.2, a constant positive probability not depending
on n, and G and H each have probabilty at least e
cn
(d1)/d
for some constant
30 Jerey E. Steif
c < . The intersection of these three events implies that [B
n
1/d[(p)/2 [C[ <
yielding that
P
p
([B
n
1/d[(p)/2 [C[ < ) e
cn
(d1)/d
.
This easily yields the result.
9. Conformal invariance and critical exponents
This section will touch on some very important recent developments in 2 dimen-
sional percolation theory that has occurred in the last 10 years. I would not call
this section even an overview since I will only touch on a few things. There is a
lot to be said here and this section will be somewhat less precise than the earlier
sections. See [36] for a thorough exposition of these topics.
9.1. Critical exponents
We begin by discussing the concept of critical exponents. We have mentioned in
Section 8 that below the critical value, the probability that the origin is connected
to distance n away decays exponentially in n, this being true for any dimension.
It had been conjectured for some time that in 2 dimensions, at the critical value
itself, the above probability decays like a power law with a certain power, called
a critical exponent. While this is believed for Z
2
, it has only been proved for the
hexagonal lattice. Recall that one does site percolation rather than bond (edge)
percolation on this lattice; in addition, the critical value for this lattice is also 1/2
as Kesten also showed.
Let A
n
be the event that there is a white path from the origin to distance n
away.
Theorem 9.1. (Lawler, Schramm and Werner, [20]) For the hexagonal lattice, we
have
P
1/2
(A
n
) = n
5/48+o(1)
where the o(1) is a function of n going to 0 as n .
Remarks: Critical values (such as 1/2 for the Z
2
and the hexagonal lattice) are
not considered universal since if you change the lattice in some way the critical
value will typically change. However, a critical exponent such as 5/48 is believed
to be universal as it is believed that if you take any 2-dimensional lattice and look
at the critical value, then the above event will again decay as the
5
48
th power of
the distance.
Exercise 9.1. For Z
2
, show that there exists c > 0 so that for all n
P
1/2
(A
n
) n
c
.
Hint: Apply Lemma 7.3 to the dual graph.
Exercise 9.2. For Z
2
, show that for all n
P
1/2
(A
n
) (1/4)n
1
.
A mini course on percolation theory 31
Hint: Use Lemma 7.1.
There are actually an innite number of other known critical exponents. Let A
k
n
be the event that there are k disjoint monochromatic paths starting from within
distance (say) 2k of the origin all of which reach distance n from the origin and
such that at least one of these monochromatic paths is white and at least one is
black. This is referred to as the k-arm event. Let A
k,H
R
be the analogous event but
where we restrict to the upper half plane and where the restriction of having at
least one white path and one black path may be dropped. This is referred to as
the half-plane k-arm event.
Theorem 9.2. (Smirnov and Werner, [33]) For the hexagonal lattice, we have
(i) For k 2, P
1/2
(A
k
n
) = n
(k
2
1)/12+o(1)
(ii) For k 1, P
1/2
(A
k,H
n
) = n
k(k+1)/6+o(1)
where again the o(1) is a function
of n going to 0 as n .
The proofs of the above results crucially depended on conformal invariance,
a concept discussed in Section 9.3 and which was proved by Stas Smirnov.
9.2. Elementary critical exponents
Computing the exponents in Theorems 9.1 and 9.2 is highly nontrivial and relies
on the important concept of conformal invariance to be discussed in the next
subsection as well as an extremely important development called the Schramm-
Lowner evolution. We will not do any of these two proofs; a few special cases of
them are covered in [36]. (These cases are not the ones which can be done via the
elementary methods of the present subsection.)
It turns out however that some exponents can be computed by elementary
means. This section deals with a couple of them via some long exercises. Exercises
9.3 and 9.4 below are taken (with permission) (almost) completely verbatim from
[36]. In order to do these exercises, we need another important inequality, which
we managed so far without; this inequality, while arising quite often, is used only
in this subsection as far as these notes are concerned. It is called the BK inequality
named after van den Berg and Kesten; see [5]. The rst ingredient is a somewhat
subtle operation on events.
Denition 9.3. Given two events A and B depending on only nitely many edges,
we dene AB as the event that there are two disjoint sets of edges S and T such
that the status of edges in S guarantee that A occurs (no matter what the status
of edges outside of S are) and the status of edges in T guarantee that B occurs
(no matter what the status of edges outside of T are).
Example: To understand this concept, consider a nite graph G where percolation
is being performed, let x, y, z and w be four (not necessarily distinct) vertices, let
A be the event that there is an open path from x to y, let B be the event that
there is an open path from z to w and think about what AB is in this case. How
should the probability P
p
(A B) compare with that of P
p
(A)P
p
(B)?
32 Jerey E. Steif
Theorem 9.4. (van den Berg and Kesten, [5]) (BK inequality).
If A and B are increasing events, then P
p
(A B) P
p
(A)P
p
(B).
While this might seem obvious in some sense, the proof is certainly non-
trivial. When it was proved, it was conjectured to hold for all events A and B.
However, it took 12 more years (with false proofs by many people given on the
way) before David Reimer proved the above inequality for general events A and
B.
Exercise 9.3. Two-arm exponent in the half-plane. Let p = 1/2. Let
n
be the
set of hexagons which are of distance at most n from the origin. We consider
H
n
= z
n
: (z) 0 where (z) is dened to be the imaginary part of the
center of z. The boundary of H
n
can be decomposed into two parts: a horizontal
segment parallel to and close to the real axis and the angular semi-circle h
n
.
We say that a point x on the real line is n-good if there exist one open path
originating from x and one closed path originating from x + 1, that both stay in
x +H
n
and join these points to x +h
n
(these paths are called arms). Note that
the probability w
n
that a point x is n-good does not depend on x.
1) We consider percolation in H
2n
.
a) Prove that with a probability that is bounded from below independently of
n, there exists an open cluster O and a closed cluster C, that both intersect the
segment [n/2, n/2] and h
2n
, such that C is to the right of O.
b) Prove that in the above case, the right-most point of the intersection of O with
the real line is n-good.
c) Deduce that for some absolute constant c, w
n
c/n.
2) We consider percolation in H
n
.
a) Show that the probability that there exists at least k disjoint open paths joining
h
n
to [n/2, n/2] in H
n
is bounded by
k
for some constant that does not depend
on n (hint: use the BK inequality). Show then that the number K of open clusters
that join h
n
to [n/2, n/2] satises P(K k)
k
.
b) Show that each 2n-good point in [n/2, n/2] is the right-most point of the
intersection of one of these K clusters with the real line.
c) Deduce from this that for some absolute constant c

, (n + 1)w
2n
E(K) c

.
3) Conclude that for some positive absolute constants c
1
and c
2
, c
1
/n w
n
c
2
/n.
Exercise 9.4. Three-arm exponent in the half-plane. Let p = 1/2. We say that a
point x is n-Good (mind the capital G) if it is the unique lowest point in x +H
n
of an open cluster C such that C , x + H
n
. Note that the probability v
n
that a
point is n-Good does not depend on x.
1) Show that this event corresponds to the existence of three arms, having colors
black, white and black, originating from the neighborhood of x in x +H
n
.
2) Show that the expected number of clusters inside H
n
that join h
n/2
to h
n
is
bounded. Compare this number of clusters with the number of 2n-Good points in
H
n/2
and deduce from this that for some constant c
1
, v
n
c
1
/n
2
.
A mini course on percolation theory 33
3) Show that with probability bounded from below independently of n, there
exists in H
n/2
an n-Good point (note that an argument is needed to show that
with positive probability, there exists a cluster with a unique lowest point). Deduce
that for some positive absolute constant c
2
, v
n
c
2
/n
2
.
9.3. Conformal invariance
One of the key steps in proving the above theorems is to prove conformal invariance
of percolation which is itself very important. Before even getting to this, we warm
up with posing the following question, which could be thought of in either the
context of Z
2
or the hexagonal lattice.
Question: Letting a
n
be the probability at criticality of having a crossing of [0, 2n]
[0, n], does lim
n
a
n
exist?
Remark: We have seen in Section 7 that a
n
1/2 and that liminf a
n
> 0.
The central limit theorem in probability is a sort of scaling limit. It says
that if you add up many i.i.d. random variables and normalize them properly, you
get a nice limiting object (which is the normal distribution). We would like to do
something vaguely similar with percolation, where the lattice spacing goes to 0 and
we ask if some limiting object emerges. In this regard, note that a
n
is exactly the
probability that there is a crossing of [0, 2][0, 1] on the lattice scaled down by 1/n.
In studying whether percolation performed on smaller and smaller lattices might
have some limiting behavior, looking at a crossing of [0, 2] [0, 1] is one particular
(of many) global or macro-events that one may look at. If p is subcritical, then
a
n
goes exponentially to 0, which implies that subcritical percolation on the 1/n
scaled down lattice has no interesting limiting behavior.
The conformal invariance conjecture contains 3 ingredients; (i) limits, such as
the sequence a
n
above exist (ii) their values depend only on the structure of the
domain and hence are conformally invariant and (iii) exact values, due to Cardy,
of the values of these limits. We now make this precise.
Let be a bounded simply connected domain of the plane and let A, B, C
and D be 4 points on the boundary of in clockwise order. Scale a 2-dimensional
lattice, such as Z
2
or the hexagonal lattice T, by 1/n and perform critical per-
colation on this scaled lattice. Let P(, A, B, C, D, n) denote that the probability
that in the 1/n scaled hexagonal lattice, there is an open path in going from the
boundary of between A and B to the boundary of between C and D. (For
Z
2
, an open path should be interpreted as a path of open edges while for T, it
should be interpreted as a path of white hexagons.) The rst half of the following
conjecture is attributed to Michael Aizenman and the second half of the conjecture
to John Cardy.
Conjecture 9.5. (i) For all and A, B, C and D as above,
P(, A, B, C, D, ) := lim
n
P(, A, B, C, D, n)
exists and is conformally invariant in the sense that if f is a conformal mapping,
then P(, A, B, C, D, ) = P(f(), f(A), f(B), f(C), f(D), ).
34 Jerey E. Steif
(ii) There is an explicit formula (which we do not state here) for P(, A, B, C, D, ),
called Cardys formula, when is a rectangle and A, B, C and D are the 4 corner
points. (Since every , A, B, C and D can be mapped to a unique such rectangle
(with A, B, C and D going to the 4 corner points), this would specify the above
limit in general assuming conformal invariance.)
Cardys formula was quite complicated involving hypergeometric functions
but Lennart Carleson realized that assuming conformal invariance, there is a nicer
set of representing domains with four specied points where the formula simples
tremendously. Namely, if is an equilateral triangle (with side lengths 1), A, B and
C the three corner points and D (on the line between C and A) having distance x
from C, then the above probability would just be x. Using Carlesons reformulation
of Cardys formula, Smirnov proved the above conjecture for the hexagonal lattice.
Theorem 9.6. [32] For the hexagonal lattice, both (i) and (ii) of the above conjecture
are true.
This conjecture is also believed to hold on Z
2
but is not (yet) proved in that
case. An important related object is the interface between whites and blacks in
the upper half plane when one places white hexagons on the positive xaxis and
black hexagons on the negative xaxis; see Figure 9. In [29], Schramm described
what this interface should be as the lattice spacing goes to 0, assuming conformal
invariance. This paper is where the now famous SLE (for stochastic Lowner evo-
lution and later called the Schramm-Lowner evolution) was introduced. Smirnov
[32] proved the convergence for one interface and Camia and Newman [9] proved
a full scaling limit, which is a description of the behavior of all the interfaces
together. The critical exponents described in Theorems 9.1 and 9.2 are proved
by exploiting the SLE description of the interface. Theorem 9.1 and one case of
Theorem 9.2 are described in [36].
In the summer school, we went through the proof of Theorem 9.6 in detail
following precisely the argument in [2]. The argument can also be found on-line in
[13] or in [36] as well as in a number of other places. The argument diered from
[2] more or less only in presentation and so after some thought, I decided not to
detail this argument here.
10. Noise sensitivity and dynamical percolation
This last section gives an extremely quick overview of some other interesting de-
velopments in percolation most of which are surveyed in [34].
Noise sensitivity: In [3], the concept of noise sensitivity is introduced. Here we only
explain what this is in the context of percolation. Perform percolation with p = 1/2
and consider the event E
n
that there is a L-R open crossing of an (n+1) n box.
Recall from Lemma 7.1 that P(E
n
) = 1/2 for each n. Now, x > 0 and ip the
status of each edge (from open to closed or from closed to open) independently
with probability . Let E

n
be the event that there is a L-R open crossing of the
A mini course on percolation theory 35
Figure 9. The percolation interface (picture by Oded Schramm
and provided by Vincent Beara)
same (n+1) n box after the ipping procedure. Of course P(E

n
) = 1/2 for each
n. In [3], it was shown that for all > 0,
lim
n
P(E

n
E
n
) = 1/4.
This means that for any xed , E
n
and E

n
become, interestingly, asymptotically
independent as n tends to . One then says that crossing probabilities are very
sensitive to noise. Later on, quantitative versions of this, where depends on n
and goes to 0 with n were obtained. For the hexagonal lattice (where the critical
exponents are known), it was shown in [30] that one still has asymptotic indepen-
dence if
n
= (1/n)

provided that < 1/8. It was later shown in [11] that this
asymptotic independence also holds for < 3/4 and that this is sharp in that the
correlation of E

n
and E
n
goes to 1 if > 3/4.
Dynamical percolation: Dynamical percolation, which was introduced in [14], is a
model in which a time dynamics is introduced. In this model, given a xed graph
G and a p, the edges of G switch back and forth according to independent 2-state
continuous time Markov chains where closed switches to open at rate p and open
switches to closed at rate 1 p. Clearly, P
p
is the unique stationary distribution
for this Markov process. The general question studied in dynamical percolation is
whether, when we start with distribution P
p
, there exist atypical times at which
the percolation structure looks markedly dierent than that at a xed time. In
36 Jerey E. Steif
almost all cases, the term markedly dierent refers to the existence or nonexis-
tence of an innite connected component. A number of results for this model were
obtained in [14] of which we mention the following.
(i) For p less than the critical value, there are no times at which percolation occurs
while for p larger than the critical value, percolation occurs at all times.
(ii) There exist graphs which do not percolate at criticality but for which there
exist exceptional times (necessarily of Lebesgue measure 0) at which percolation
occurs.
(iii) For large d, there are no exceptional times of percolation for dynamical per-
colation run at criticality on Z
d
. (Recall that we have seen, without proof, that
ordinary percolation on Z
d
for large d does not percolate.) The key property ex-
ploited for this result is that the percolation function has a nite derivative at
the critical value.
It was left open what occurs at Z
2
where it is known that the percolation
function has an innite derivative at the critical value. Using the known critical
exponents for the hexagonal lattice, it was proved in [30] that there are in fact
exceptional times of percolation for this lattice when run at criticality and that the
Hausdor dimension of such times is in [1/6, 31/36] with the upper bound being
conjectured. In [11], it was then shown that the upper bound of 31/36 is correct
and that even Z
2
has exceptional times of percolation at criticality and also that
this set has positive Hausdor dimension.
While the relationship between noise sensitivity and dynamical percolation might
not be clear at rst sight, it turns out that there is a strong relation between them
because the 2nd moment calculations necessary to carry out a second moment
argument for the dynamical percolation model involve terms which are closely
related to the correlations considered in the denition of noise sensitivity. See [34]
for many more details.
References
[1] Aizenman, M., Kesten, H. and Newman, C. M. Uniqueness of the innite cluster and
continuity of connectivity functions for short- and long-range percolation. Comm.
Math. Phys. 111, (1987), 505532.
[2] Beara, V. Cardys formula on the triangular lattice, the easy way. Universality and
Renormalization, Vol. 50 of the Fields Institute Communications, (2007), 3945.
[3] Benjamini, I., Kalai, G. and Schramm, O. Noise sensitivity of Boolean functions and
applications to percolation. Inst. Hautes

Etudes Sci. Publ. Math. 90, (1999), 543.
[4] van den Berg, J. and Keane, M. On the continuity of the percolation probability
function. Conference in modern analysis and probability (New Haven, Conn., 1982),
Contemp. Math. 26, Amer. Math. Soc., Providence, RI, 1984, 6165.
[5] van den Berg, J. and Kesten, H. Inequalities with applications to percolation and
reliability. J. Appl. Probab. 22, (1985), 556569.
A mini course on percolation theory 37
[6] Bollob as B. and Riordan O.M. A short proof of the HarrisKesten Theorem, Bull.
London Math. Soc., 38, (2006), 470484.
[7] Bollob as B. and Riordan O.M. The critical probability for random Voronoi percolation
in the plane is 1/2, Probab. Theory Related Fields, 136, (2006), 417468.
[8] Burton, R. and Keane, M. Density and uniqueness in percolation. Comm. Math. Phys.
121, (1989), 501505.
[9] Camia, F. and Newman, C. M. Two-dimensional critical percolation: the full scaling
limit, Comm. Math. Phys., 268, (2006), 138.
[10] Friedgut, E. and Kalai, G. Every monotone graph property has a sharp threshold,
Proc. Amer. Math. Soc., 124, (1996), 29933002.
[11] Garban, C., Pete, G. and Schramm, O. The Fourier Spectrum of Critical Percolation,
Acta Math., to appear, arXiv:0803.3750[math:PR].
[12] Grimmett, G. Percolation Second edition, Springer-Verlag, (1999), New York.
[13] Grimmett, G. Probability on Graphs, Cambridge University Press, (2010), Cam-
bridge.
[14] H aggstrom, O., Peres, Y. and Steif, J. E. Dynamical percolation. Ann. Inst. Henri
Poincare, Probab. et Stat. 33, (1997), 497528.
[15] Hara, T. and Slade, G. (1994) Mean eld behavior and the lace expansion, in Prob-
ability Theory and Phase Transitions, (ed. G. Grimmett), Proceedings of the NATO
ASI meeting in Cambridge 1993, Kluwer.
[16] Harris, T. E. A lower bound on the critical probability in a certain percolation
process. Proc. Cambridge Phil. Soc. 56, (1960), 1320.
[17] Kahn, J., Kalai, G. and Linial, N. The inuence of variables on boolean functions.
29th Annual Symposium on Foundations of Computer Science, (1988), 6880.
[18] Kesten, H. The critical probability of bond percolation on the square lattice equals
1
2
. Comm. Math. Phys. 74, (1980), 4159.
[19] Langlands, R., Pouliot, P. and Saint-Aubin, Y. Conformal invariance in two-
dimensional percolation. Bull. Amer. Math. Soc. (N.S.) 30, (1994), 161.
[20] Lawler, G., Schramm, O. and Werner, W. One-arm exponent for critical 2D perco-
lation. Electron. J. Probab. 7, (2002), no. 2, 13 pp. (electronic).
[21] Lyons, R. Random walks and percolation on trees. Ann. Probab. 18, (1990), 931958.
[22] Lyons, R. Random walks, capacity, and percolation on trees. Ann. Probab. 20, (1992),
20432088.
[23] Lyons, R. with Peres, Y. Probability on Trees and Networks. Cambridge University
Press. In preparation. Current version available at http://mypage.iu.edu/rdlyons/.
[24] Margulis, G. A. Probabilistic characteristics of graphs with large connectivity, Prob-
lemy Peredaci Informacii, 10, (1974), 101108.
[25] Newman, C. M. and Schulman, L. S. Number and density of percolating clusters. J.
Phys. A, 14, (1981), 17351743.
[26] Russo, L. A note on percolation. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete,
43, (1978), 3948.
[27] Russo, L. On the critical percolation probabilities. Z. Wahrsch. Verw. Gebiete 56,
(1981), 229237.
38 Jerey E. Steif
[28] Russo, L. An approximate zero-one law. Z. Wahrsch. Verw. Gebiete 61, (1982), 129
139.
[29] Schramm, O. Scaling limits of loop-erased random walks and uniform spanning trees.
Israel J. Math. 118, (2000), 221288.
[30] Schramm, O. and Steif, J. E. Quantitative noise sensitivity and exceptional times
for percolation. Ann. Math., 171, (2010), 619672.
[31] Seymour, P. D. and Welsh, D. J. A. Percolation probabilities on the square lattice.
Advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cam-
bridge, 1977). Ann. Discrete Math., 3, (1978), 227245.
[32] Smirnov, S. Critical percolation in the plane: conformal invariance, Cardys formula,
scaling limits. C. R. Acad. Sci. Paris Ser. I Math. 333, (2001), 239244.
[33] Smirnov, S. and Werner, W. Critical exponents for two-dimensional percolation.
Math. Res. Lett. 8, (2001), 729744.
[34] Steif, J. A survey on dynamical percolation. Fractal geometry and stochastics, IV,
Birkhauser, (2009), 145174.
[35] Talagrand, M. On Russos approximate zero-one law. Ann. Probab. 22, (1994), 1576
1587.
[36] Werner, W. Lectures on two-dimensional critical percolation. IAS Park City Grad-
uate Summer School, 2007, arXiv:0710.0856[math:PR].
Acknowledgment
I would like to thank Andras Balint for explaining to me how one adapts the
original proofs of Theorem 7.7 so that one needs only the RSW result for p =
1/2. I thank Vincent Beara for providing me with some pictures. The pictures
which state in their captions that they have come from reference [12] have been
reproduced courtesy of Georey Grimmett from [12] which I hereby thank. I also
thank the students from the summer school for some of their corrections for these
notes. Various helpful comments were also given to me by Andras Balint, Ragnar
Freij and Marcus Warfheimer. I also received useful comments from an anonymous
referee. Lastly, I would like to thank Ville Suomala for organizing the mathematics
part of the Jyvaskyla summer school which was a very enjoyable experience for
me.
Jerey E. Steif
Mathematical Sciences
Chalmers University of Technology
and
Mathematical Sciences
G oteborg University
SE-41296 Gothenburg, Sweden
e-mail: steif@chalmers.se