1Percolation
III Percolation and Random Walks on Graphs
1.1 The critical probability
There are two models of percolation — bond percolation and site percolation. In
this course, we will focus on bond percolation, but we will look at site percolation
in the example sheets.
The very basic set up of percolation theory involves picking a graph
G
=
(
V, E
), where
V
is the set of vertices and
E
is the set of edges. We also pick a
percolation probability
p ∈
[0
,
1]. For each edge
e ∈ E
, we keep it with probability
p
and throw it with probability 1
− p
. In the first case, we say the edge is open,
and in the latter, we say it is closed.
More precisely, we define the probability space to be Ω =
{
0
,
1
}
E
, where 0
denotes a closed edge and 1 denotes an open one (in the case of site percolation,
we have Ω =
{
0
,
1
}
V
). We endow Ω with the
σ
-algebra generated by cylinder
sets
{ω ∈ Ω : ω(e) = x
e
for all e ∈ A},
where
A
is a finite set and
x
e
∈ {
0
,
1
}
for all
e
. In other words, this is the
product
σ
-algebra. As probability measure, we take the product measure
P
p
, i.e.
every edge is 1 with probability
p
and 0 with probability 1
− p
. We will write
η
p
∈ {0, 1}
E
for the state of the system.
Now what can we say about the graph resulting from this process? One
question we may ask is whether we can connect two points in the graphs via the
edges that remain. To further the discussion, we introduce some notation.
Notation. We write x ↔ y if there is an open path of edges from x to y.
Notation. We write C(x) = {y ∈ V : y ↔ x}, the cluster of x.
Notation. We write x ↔ ∞ if |C(x)| = ∞.
From now on, we shall take
G
=
L
d
= (
Z
d
, E
(
Z
d
)), the
d
-dimensional integer
lattice. Then by translation invariance,
|C
(
x
)
|
has the same distribution as
|C
(0)
|
for all x. We now introduce a key piece of notation:
Definition (θ(p)). We define θ(p) = P
p
(|C(0)| = ∞).
Most of the questions we ask surround this
θ
(
p
). We first make the most
elementary observations:
Example. θ(0) = 0 and θ(1) = 1.
A natural question to ask is then if we can find
p ∈
(0
,
1) such that
θ
(
p
)
>
0.
But even before answering that question, we can ask a more elementary one —
is θ an increasing function of p?
Intuitively, it must be. And we can prove it. The proof strategy is known as
coupling. We have already seen coupling in IB Markov Chains, where we used it
to prove the convergence to the invariant distribution under suitable conditions.
Here we are going to couple all percolation processes for different values of P .
Lemma. θ is an increasing function of p.
Proof.
We let (
U
(
e
))
e∈E(Z
d
)
be iid
U
[0
,
1] random variables. For each
p ∈
[0
,
1],
we define
η
p
(e) =
(
1 U(e) ≤ p
0 otherwise
Then
P
(
η
p
(
e
) = 1) =
P
(
U
(
e
)
< p
) =
p
. Since the
U
(
e
) are independent, so are
η
p
. Thus η
p
has the law of bond percolation with probability p.
Moreover, if p ≤ q, then η
p
(e) ≤ η
q
(e). So the result follows.
Note that this is not only useful as a theoretical tool. If we want to simulate
percolation with different probabilities
p
, we can simply generate a set of
U
[0
,
1]
variables, and use it to produce a percolation for all p.
If we wish, we can provide an abstract definition of what coupling is, but the
detailed definition is not of much practical use:
Definition
(Coupling)
.
Let
µ
and
ν
be two probability measures on (potentially)
different probability spaces. A coupling is a pair of random variables (
X, Y
)
defined on the same probability space such that the marginal distribution of
X
is µ and the marginal distribution of Y is ν.
With the lemma, we can make the definition
Definition (Critical probability). We define p
c
(d) = sup{p ∈ [0, 1] : θ(p) = 0}.
Recall we initially asked whether
θ
(
p
) can be non-zero for
p ∈
(0
,
1). We
can now rephrase and strengthen this question by asking for the value of p
c
(d).
There are a lot more questions we can ask about p
c
and θ(p).
For example, we know that
θ
(
p
) is a
C
∞
function on (
p
c
,
1]. However, we
do not know if
θ
is continuous at
p
c
in
d
= 3. We will see soon that
p
c
=
1
2
in
d = 2, but the exact value of p
c
is not known in higher dimensions.
Let’s start actually proving things about p
c
. We previously noted that
Proposition. p
c
(1) = 1.
The first actually interesting theorem is the following:
Theorem. For all d ≥ 2, we have p
c
(d) ∈ (0, 1).
We shall break this up into two natural parts:
Lemma. For d ≥ 2, p
c
(d) > 0.
Proof.
Write Σ
n
for the number of open self-avoiding paths of length
n
starting
at 0. We then note that
P
p
(|C(0)| = ∞) = P
p
(∀n ≥ 1 : Σ
n
≥ 1) = lim
n→∞
P
p
(Σ
n
≥ 1) ≤ lim
n→∞
E
p
[Σ
n
].
We can now compute
E
p
[Σ
n
]. The point is that expectation is linear, which
makes this much easier to compute. We let
σ
n
be the number of self-avoiding
paths of length n from 0. Then we simply have
E
p
[Σ
n
] = σ
n
p
n
.
We can bound
σ
n
by 2
d ·
(2
d −
1)
n−1
, since we have 2
d
choices of the first step,
and at most 2d − 1 choices in each subsequent step. So we have
E
p
[Σ
n
] ≤ 2d(2d − 1)
n−1
p
n
=
2d
2d − 1
(p(2d − 1))
n
.
So if p(2d − 1) < 1, then θ(p) = 0. So we know that
p
c
(d) ≥
1
2d − 1
.
Before we move on to the other half of the theorem, we talk a bit more about
self-avoiding paths.
Definition
(
σ
n
)
.
We write
σ
n
for the number of self-avoiding paths of length
n
starting from 0.
In the proof, we used the rather crude bound
σ
n
≤ 2d · (2d − 1)
n−1
.
More generally, we can make the following bound:
Lemma. We have σ
n+m
≤ σ
n
σ
m
.
Proof.
A self-avoiding path of length
n
+
m
can be written as a concatenation of
self-avoiding paths of length
n
starting from 0 and another one of length
m
.
Taking the logarithm, we know that
log σ
n
is a subadditive sequence. It turns
out this property alone is already quite useful. It is an exercise in analysis to
prove the following lemma:
Lemma
(Fekete’s lemma)
.
If (
a
n
) is a subadditive sequence of real numbers,
then
lim
n→∞
a
n
n
= inf
n
a
k
k
: k ≥ 1
o
∈ [−∞, ∞).
In particular, the limit exists.
This allows us to define
Definition (λ and κ). We define
λ = lim
n→∞
log σ
n
n
, κ = e
λ
.
κ is known as the connective constant.
Then by definition, we have
σ
n
= e
nλ(1+o(1))
= κ
n+o(n)
.
as n → ∞.
Thus, asymptotically, the growth rate of
σ
n
is determined by
κ
. It is natural
to then seek for the value of
κ
, but unfortunately we don’t know the value of
κ
for the Euclidean lattice. A bit more on the positive side, the value for the
hexagonal lattice has been found recently:
Theorem (Duminil-Copin, Smirnov, 2010). The hexagonal lattice has
κ
hex
=
q
2 +
√
2.
We might want to be a bit more precise about how
σ
n
grows. For
d ≥
5, we
have the following theorem:
Theorem
(Hara and Slade, 1991)
.
For
d ≥
5, there exists a constant
A
such
that
σ
n
= Aκ
n
(1 + O(n
−ε
))
for any ε <
1
2
.
We don’t really know what happens when
d <
5, but we have the following
conjecture:
Conjecture.
σ
n
≈
n
11/32
κ
n
d = 2
n
γ
κ
n
d = 3
(log n)
1/4
κ
n
d = 4
One can also instead try to bound
σ
n
from above. We have the following
classic theorem:
Theorem (Hammersley and Welsh, 1962). For all d ≥ 2, we have
σ
n
≤ Cκ
n
exp(c
0
√
n)
for some constants C and c
0
.
In fact, a better bound was recently found:
Theorem (Hutchcroft, 2017). For d ≥ 2, we have
σ
n
≤ Cκ
n
exp(o(
√
n)).
This will be proved in the example sheet.
What would be a good way to understand self-avoiding walks? Fixing an
n
,
there are only finitely many self-avoiding walks of length
n
. So we can sample
such a self-avoiding walk uniformly at random. In general, we would expect
the total displacement of the walk to be
∼
√
n
. Thus, what we can try to do
is to take
n → ∞
while simultaneously shrinking space by a factor of
1
√
n
. We
would then hope that the result converges toward some Brownian motion-like
trajectory. If we can characterize the precise behaviour of this scaling limit,
then we might be able to say something concrete about
κ
and the asymptotic
behaviour of σ
n
.
But we don’t really know what the scaling limit is. In the case
d
= 2, it is
conjectured to be
SLE
(
8
3
). Curiously, it was proven by Gwynne and Miller in
2016 that if we instead looked at self-avoiding walks on a random surface, then
the scaling limit is SLE(
8
3
).
That’s enough of a digression. Let’s finish our proof and show that
p
c
(
d
)
<
1.
A first observation is that it suffices to show this for
d
= 2. Indeed, since
Z
d
embeds into
Z
d+1
for all
d
, if we can find an infinite cluster in
Z
d
, then the same
is true for
Z
d+1
. Thus, it is natural to restrict to the case of
d
= 2, where duality
will be prove to be an extremely useful tool.
Definition
(Planar graph)
.
A graph
G
is called planar if it can be embedded
on the plane in such a way that no two edges cross.
Definition
(Dual graph)
.
Let
G
be a planar graph (which we call the primal
graph). We define the dual graph by placing a vertex in each face of
G
, and
connecting 2 vertices if their faces share a boundary edge.
Example. The dual of Z
2
is isomorphic to Z
2
The dual lattice will help us prove a lot of properties for percolation in Z
2
.
Lemma. p
c
(d) < 1 for all d ≥ 2.
Proof.
It suffices to show this for
d
= 2. Suppose we perform percolation on
Z
2
.
Then this induces a percolation on the dual lattice by declaring an edge of the
dual is open if it crosses an open edge of Z
2
, and closed otherwise.
Suppose
|C
(0)
| < ∞
in the primal lattice. Then there is a closed circuit in
the dual lattice, given by the “boundary” of
C
(0). Let
D
n
be the number of
closed dual circuits of length
n
that surround 0. Then the union bound plus
Markov’s inequality tells us
P
p
(|C(0)| < ∞) = P
p
(∃n ≥ D
n
≥ 1) ≤
∞
X
n=4
E
p
[D
n
],
using the union bound and Markov’s inequality.
It is a simple exercise to show that
Exercise.
Show that the number of dual circuits of length
n
that contain 0 is
at most n · 4
n
.
From this, it follows that
P
p
(|C(0)| < ∞) ≤
∞
X
n=4
n · 4
n
(1 − p)
n
.
Thus, if
p
is sufficiently near 1, then
P
p
(
|C
(0)
| < ∞
) is bounded away from 1.
By definition, if
p < p
c
(
d
), then 0 is almost surely not contained in an infinite
cluster. If
p > p
c
(
d
), then there is a positive probability that 0 is contained
in an infinite cluster. However, it is of course not necessarily the case that
0 is connected to
∞
with probability 1. In fact, there is at least probability
(1
− p
)
2d
that 0 is not connected to
∞
, since 0 cannot be connected to
∞
if all
its neighbouring edges are closed. However, it is still possible that there is some
infinite cluster somewhere. It’s just that it does not contain 0.
Proposition. Let A
∞
be the event that there is an infinite cluster.
(i) If θ(p) = 0, then P
p
(A
∞
) = 0.
(ii) If θ(p) > 0, then P
p
(A
∞
) = 1.
Proof.
(i) We have
P
p
(A
∞
) = P
p
(∃x : |C(x)| = ∞) ≤
X
x∈Z
d
P
p
(|C(x)| = ∞) =
X
θ(p) = 0.
(ii)
We need to apply the Kolmogorov 0-1 law . Recall that if
X
1
, X
2
, . . .
are
independent random variables, and
F
n
=
σ
(
X
k
:
k ≥ n
),
F
∞
=
T
n≥0
F
n
,
Then F
∞
is trivial, i.e. for all A ∈ F
∞
, P(A) ∈ {0, 1}.
So we order the edges of Z
d
as e
1
, e
2
, . . . and denote their states
w(e
1
), w(e
2
), . . . .
These are iid random variables. We certainly have
P
p
(
A
∞
)
≥ θ
(
p
)
>
0.
So if we can show that
A
∞
∈ F
∞
, then we are done. But this is clear,
since changing the states of a finite number of edges does not affect the
occurrence of A
∞
.
The next follow up questions is how many infinite clusters do we expect to
get?
Theorem
(Burton and Keane)
.
If
p > p
c
, then there exists a unique infinite
cluster with probability 1.
This proof is considerably harder than the ones we have previously done. We
might think we can use the Kolmogorov 0-1 law, but we can’t, since changing
a finite number of edges can break up or join together infinite clusters, so the
event that there are
k
infinite clusters for
k >
0 is not in
F
∞
. However, we can
exploit the fact that N is translation invariant.
Exercise.
Let
A
be an event that is translation invariant. Then
P
p
(
A
) = 0 or 1
almost surely.
Proof.
Let
N
be the number of infinite clusters. Then by the lemma, we know
N
is constant almost surely. So there is some
k ∈ N ∪{∞}
such that
P
p
(
N
=
k
) = 1.
First of all, we know that
k 6
= 0, since
θ
(
p
)
>
0. We shall first exclude 2
≤ k < ∞
,
and then exclude k = ∞.
Assume that
k < ∞
. We will show that
P
p
(
n
= 1)
>
0, and hence it must
be the case that P
p
(n = 1) = 1.
To bound this probability, we let
B
(
n
) = [
−n, n
]
d
∩ Z
d
(which we will
sometimes write as B
n
), and let ∂B(n) be its boundary. We know that
P
p
(all infinite clusters intersect ∂B(n)) → 1
as
n → ∞
. This is since with probability 1, there are only finitely many clusters
by assumption, and for each of these configurations, all infinite clusters intersect
∂B(n) for sufficiently large n.
In particular, we can take n large enough such that
P
p
(all infinite clusters intersect ∂B(n)) ≥
1
2
.
We can then bound
P
p
(N = 1) ≥ P
p
(all infinite clusters intersect ∂B(n)
and all edges in B(n) are open).
Finally, note that the two events in there are independent, since they involve
different edges. But the probability that all edges in
B
(
n
) are open is just
p
E(B(n))
. So
P
p
(N = 1) ≥
1
2
p
E(B(n))
> 0.
So we are done.
We now have to show that
k 6
=
∞
. This involves the notion of a trifurcation.
The idea is that we will show that if k = ∞, then the probability that a vertex
is a trifurcation is positive. This implies the expected number of trifurcations
is
∼ n
d
. We will then show deterministically that the number of trifurcations
inside
B
(
n
) must be
≤ |∂B
(
n
)
|
, and so there are
O
(
n
d−1
) trifurcations, which is
a contradiction.
We say a vertex x is a trifurcation if the following three conditions hold:
(i) x is in an infinite open cluster C
∞
;
(ii) There exist exactly three open edges adjacent to x;
(iii) C
∞
\ {x} contains exactly three infinite clusters and no finite ones.
This is clearly a translation invariant notion. So
P
p
(0 is a trifurcation) = P
p
(x is a trifurcation)
for all x ∈ Z
d
.
Claim. P
p
(0 is a trifurcation) > 0.
We need to use something slightly different from
B
(
n
). We define
S
(
n
) =
{x ∈ Z
d
: kxk
1
≤ n}.
The crucial property of this is that for any
x
1
, x
2
, x
3
∈ ∂S
(
n
), there exist three
disjoint self-avoiding paths joining
x
i
to 0 (exercise!). For each triple
x
1
, x
2
, x
3
,
we arbitrarily pick a set of three such paths, and define the event
J(x
1
, x
2
, x
3
) = {all edges on these 3 paths are open
and everything else inside S(n) is closed}.
Next, for every possible infinite cluster in
Z
d
\ S
(
n
) that intersects
∂S
(
n
) at at
least one point, we pick a designated point of intersection arbitrarily.
Then we can bound
P
p
(0 is a trifurcation) ≥ P
p
(∃C
1
∞
, C
2
∞
, C
3
∞
⊆ Z
d
\ S(n)
infinite clusters which intersect ∂S(n) at x
1
, x
2
, x
3
, and J(x
1
, x
2
, x
3
)).
Rewrite the right-hand probability as
P
p
(J(x
1
, x
2
, x
3
) | ∃C
1
∞
, C
2
∞
, C
3
∞
⊆ Z intersecting ∂S(n))
× P
p
(∃C
1
∞
, C
2
∞
, C
3
∞
⊆ Z
d
\ ∂S(n))
We can bound the first term by
min(p, 1 − p)
E(S(n))
.
To bound the second probability, we have already assumed that
P
p
(
N
=
∞
) = 1.
So
P
p
(
∃C
1
∞
, C
2
∞
, C
3
∞
⊆ Z
d
\ S
(
n
)
intersecting ∂S
(
n
))
→
1 as
n → ∞
. We can
then take
n
large enough such that the probability is
≥
1
2
. So we have shown
that c ≡ P
p
(0 is a trifurcation) > 0.
Using the linearity of expectation, it follows that
E
p
[number of trifurcations inside B(n))] ≥ c|B(n)| ∼ n
d
.
On the other hand, we can bound the number of trifurcations in
B
(
n
) by
|∂B
(
n
)
|
.
To see this, suppose
x
1
is a trifurcation in
B
(
n
). By definition, there exists
3 open paths to
∂B
(
n
). Fix three such paths. Let
x
2
be another trifurcation.
It also has 3 open paths to the
∂B
(
n
), and its paths to the boundary could
intersect those of
x
1
. However, they cannot create a cycle, by definition of a
trifurcation. For simplicity, we add the rule that when we produce the paths for
x
2
, once we intersect the path of x
1
, we continue following the path of x
1
.
Exploring all trifurcations this way, we obtain a forest inside B(n), and the
boundary points will be the leaves of the forest. Now the trifurcations have
degree 3 in this forest. The rest is just combinatorics.
Exercise.
For any tree, the number of degree 3 vertices is always less than the
number of leaves.