III Percolation and Random Walks on Graphs (Full)

Part III — Percolation and Random Walks on

Graphs

Based on lectures by P. Sousi

Notes taken by Dexter Chua

Michaelmas 2017

These notes are not endorsed by the lecturers, and I have modified them (often

significantly) after lectures. They are nowhere near accurate representations of what

was actually lectured, and in particular, all errors are almost surely mine.

A phase transition means that a system undergoes a radical change when a continuous

parameter passes through a critical value. We encounter such a transition every day

when we boil water. The simplest mathematical model for phase transition is percolation.

Percolation has a reputation as a source of beautiful mathematical problems that are

simple to state but seem to require new techniques for a solution, and a number of

such problems remain very much alive. Amongst connections of topical importance

are the relationships to so-called Schramm–Loewner evolutions (SLE), and to other

mo dels from statistical physics. The basic theory of percolation will be described in

this course with some emphasis on areas for future development.

Our other major topic includes random walks on graphs and their intimate connection

to electrical networks; the resulting discrete potential theory has strong connections

with classical potential theory. We will develop tools to determine transience and

recurrence of random walks on infinite graphs. Other topics include the study of

spanning trees of connected graphs. We will present two remarkable algorithms to

generate a uniform spanning tree (UST) in a finite graph

via random walks, one

due to Aldous-Broder and another due to Wilson. These algorithms can be used to

prove an important property of uniform spanning trees discovered by Kirchhoff in the

19th century: the probability that an edge is contained in the UST of

, equals the

effective resistance between the endpoints of that edge.

Pre-requisites

There are no essential pre-requisites beyond probability and analysis at undergraduate

levels, but a familiarity with the measure-theoretic basis of probability will be helpful.

Contents

0 Introduction

1 Percolation

1.1 The critical probability

1.2 Correlation inequalities

1.3 Two dimensions

1.4 Conformal invariance and SLE in d = 2

2 Random walks

2.1 Random walks in finite graphs

2.2 Infinite graphs

3 Uniform spanning trees

3.1 Finite uniform spanning trees

3.2 Infinite uniform spanning trees and forests

0 Introduction

This course is naturally divided into two parts — percolation, and random

walks on graphs. Percolation is one of the simplest models that experience phase

transition — an abrupt change in quantitative feature due to a continuous change

of a parameter. More sophisticated examples of percolation the boiling of water

and the loss of long-range correlation in magnets when temperature increases.

But we are not physicists. So let’s talk about percolation. For reasons that

become clear later, consider an n × (n + 1) lattice connected by edges:

We now fix some

p ∈

1], and for each edge in the graph, we either keep it

or remove it with probability

. There are many questions we may ask. For

example, we may ask for the probability that there is a left-to-right crossing of

open edges.

For example, we have f

(0) = 0 and f

(1) = 1.

An interesting choice of

to consider is

. We can argue that

(

)

must be

, by symmetry. More precisely, consider the dual lattice:

Note that this lattice is isomorphic to the original lattice we were thinking about,

by applying a rotation. Now each edge in the dual lattice crosses exactly one edge

in the original lattice, and we can set the edge to be open iff the corresponding

edge in the original lattice is open. This gives rise to a percolation on the dual

lattice with p =

as well.

Now notice that that there is a left-right crossing of open edges in the original

lattice iff there is no top-bottom crossing in the dual graph. But since the dual

and original lattices are isomorphic, it follows that the probability that there is

a left-right crossing in the original lattice is equal to the probability that there

is no left-right crossing in the original lattice. So both of these must be

The ability to talk about the dual graph is a very important property that

is only true in 2 dimensions. In general, there are many things known for 2

dimensions via the dual, which do not generalize to higher dimensions.

The other topic we are going to discuss is random walks in graphs. In IB

Markov chains, and maybe IA Probability, we considered random walks on the

integer lattice

. Here we shall consider random walks on any graph. We

shall mostly think about finite graphs, but we will also talk about how certain

results can be extended to infinite graphs. It turns out a rather useful way of

thinking about this is to think of the graph as representing an electrical network.

Then many concepts familiar from high school physics translate to interesting

properties about the graph, and importing well-known (and elementary) results

from electrical networks helps us understand graphs better.

1 Percolation

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

(

V, E

), where

is the set of vertices and

is the set of edges. We also pick a

percolation probability

p ∈

1]. For each edge

e ∈ E

, we keep it with probability

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 Ω =

{

}

, where 0

denotes a closed edge and 1 denotes an open one (in the case of site percolation,

we have Ω =

{

}

). We endow Ω with the

-algebra generated by cylinder

sets

{ω ∈ Ω : ω(e) = x

for all e ∈ A},

where

is a finite set and

∈ {

}

for all

. In other words, this is the

product

-algebra. As probability measure, we take the product measure

, i.e.

every edge is 1 with probability

and 0 with probability 1

− p

. We will write

∈ {0, 1}

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

= (

, E

(

)), the

-dimensional integer

lattice. Then by translation invariance,

(

)

has the same distribution as

(0)

for all x. We now introduce a key piece of notation:

Definition (θ(p)). We define θ(p) = P

(|C(0)| = ∞).

Most of the questions we ask surround this

(

). 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 ∈

1) such that

(

)

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 (

(

))

e∈E(Z

)

be iid

1] random variables. For each

p ∈

1],

we define

(e) =

(

1 U(e) ≤ p

0 otherwise

Then

(

) = 1) =

(

)

< p

) =

. Since the

(

) are independent, so are

. Thus η

has the law of bond percolation with probability p.

Moreover, if p ≤ q, then η

(e) ≤ η

(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

, we can simply generate a set of

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

is µ and the marginal distribution of Y is ν.

With the lemma, we can make the definition

Definition (Critical probability). We define p

(d) = sup{p ∈ [0, 1] : θ(p) = 0}.

Recall we initially asked whether

(

) can be non-zero for

p ∈

1). We

can now rephrase and strengthen this question by asking for the value of p

(d).

There are a lot more questions we can ask about p

and θ(p).

For example, we know that

(

) is a

∞

function on (

1]. However, we

do not know if

is continuous at

= 3. We will see soon that

d = 2, but the exact value of p

is not known in higher dimensions.

Let’s start actually proving things about p

. We previously noted that

Proposition. p

(1) = 1.

The first actually interesting theorem is the following:

Theorem. For all d ≥ 2, we have p

(d) ∈ (0, 1).

We shall break this up into two natural parts:

Lemma. For d ≥ 2, p

(d) > 0.

Proof.

Write Σ

for the number of open self-avoiding paths of length

starting

at 0. We then note that

(|C(0)| = ∞) = P

(∀n ≥ 1 : Σ

≥ 1) = lim

n→∞

(Σ

≥ 1) ≤ lim

n→∞

[Σ

We can now compute

[Σ

]. The point is that expectation is linear, which

makes this much easier to compute. We let

be the number of self-avoiding

paths of length n from 0. Then we simply have

[Σ

] = σ

We can bound

by 2

d ·

d −

n−1

, since we have 2

choices of the first step,

and at most 2d − 1 choices in each subsequent step. So we have

[Σ

] ≤ 2d(2d − 1)

n−1

2d − 1

(p(2d − 1))

So if p(2d − 1) < 1, then θ(p) = 0. So we know that

(d) ≥

2d − 1

Before we move on to the other half of the theorem, we talk a bit more about

self-avoiding paths.

Definition

(

)

We write

for the number of self-avoiding paths of length

starting from 0.

In the proof, we used the rather crude bound

≤ 2d · (2d − 1)

n−1

More generally, we can make the following bound:

Lemma. We have σ

n+m

≤ σ

Proof.

A self-avoiding path of length

can be written as a concatenation of

self-avoiding paths of length

starting from 0 and another one of length

Taking the logarithm, we know that

log σ

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 (

) is a subadditive sequence of real numbers,

then

lim

n→∞

= inf

: k ≥ 1

∈ [−∞, ∞).

In particular, the limit exists.

This allows us to define

Definition (λ and κ). We define

λ = lim

n→∞

log σ

, κ = e

κ is known as the connective constant.

Then by definition, we have

= e

nλ(1+o(1))

= κ

n+o(n)

as n → ∞.

Thus, asymptotically, the growth rate of

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

2 +

√

We might want to be a bit more precise about how

grows. For

d ≥

5, we

have the following theorem:

Theorem

(Hara and Slade, 1991)

For

d ≥

5, there exists a constant

such

that

= Aκ

(1 + O(n

−ε

))

for any ε <

We don’t really know what happens when

d <

5, but we have the following

conjecture:

Conjecture.

≈











11/32

d = 2

d = 3

(log n)

1/4

d = 4

One can also instead try to bound

from above. We have the following

classic theorem:

Theorem (Hammersley and Welsh, 1962). For all d ≥ 2, we have

≤ Cκ

exp(c

√

for some constants C and c

In fact, a better bound was recently found:

Theorem (Hutchcroft, 2017). For d ≥ 2, we have

≤ Cκ

exp(o(

√

n)).

This will be proved in the example sheet.

What would be a good way to understand self-avoiding walks? Fixing an

there are only finitely many self-avoiding walks of length

. 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

∼

√

. Thus, what we can try to do

is to take

n → ∞

while simultaneously shrinking space by a factor of

√

. 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 σ

But we don’t really know what the scaling limit is. In the case

= 2, it is

conjectured to be

SLE

(

). 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(

That’s enough of a digression. Let’s finish our proof and show that

(

)

A first observation is that it suffices to show this for

= 2. Indeed, since

embeds into

d+1

for all

, if we can find an infinite cluster in

, then the same

is true for

d+1

. Thus, it is natural to restrict to the case of

= 2, where duality

will be prove to be an extremely useful tool.

Definition

(Planar graph)

A graph

is called planar if it can be embedded

on the plane in such a way that no two edges cross.

Definition

(Dual graph)

Let

be a planar graph (which we call the primal

graph). We define the dual graph by placing a vertex in each face of

, and

connecting 2 vertices if their faces share a boundary edge.

Example. The dual of Z

is isomorphic to Z

The dual lattice will help us prove a lot of properties for percolation in Z

Lemma. p

(d) < 1 for all d ≥ 2.

Proof.

It suffices to show this for

= 2. Suppose we perform percolation on

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

, and closed otherwise.

Suppose

(0)

| < ∞

in the primal lattice. Then there is a closed circuit in

the dual lattice, given by the “boundary” of

(0). Let

be the number of

closed dual circuits of length

that surround 0. Then the union bound plus

Markov’s inequality tells us

(|C(0)| < ∞) = P

(∃n ≥ D

≥ 1) ≤

∞

n=4

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

that contain 0 is

at most n · 4

From this, it follows that

(|C(0)| < ∞) ≤

∞

n=4

n · 4

(1 − p)

Thus, if

is sufficiently near 1, then

(

(0)

| < ∞

) is bounded away from 1.

By definition, if

p < p

(

), then 0 is almost surely not contained in an infinite

cluster. If

p > p

(

), 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

− p

)

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

∞

) = 0.

(ii) If θ(p) > 0, then P

∞

) = 1.

Proof.

(i) We have

∞

) = P

(∃x : |C(x)| = ∞) ≤

x∈Z

(|C(x)| = ∞) =

θ(p) = 0.

(ii)

We need to apply the Kolmogorov 0-1 law . Recall that if

, X

, . . .

are

independent random variables, and

(

k ≥ n

∞

n≥0

Then F

∞

is trivial, i.e. for all A ∈ F

∞

, P(A) ∈ {0, 1}.

So we order the edges of Z

as e

, e

, . . . and denote their states

w(e

), w(e

), . . . .

These are iid random variables. We certainly have

(

∞

)

≥ θ

(

)

So if we can show that

∞

∈ 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)

p > p

, 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

infinite clusters for

k >

0 is not in

∞

. However, we can

exploit the fact that N is translation invariant.

Exercise.

Let

be an event that is translation invariant. Then

(

) = 0 or 1

almost surely.

Proof.

Let

be the number of infinite clusters. Then by the lemma, we know

is constant almost surely. So there is some

k ∈ N ∪{∞}

such that

(

) = 1.

First of all, we know that

k 6

= 0, since

(

)

0. We shall first exclude 2

≤ k < ∞

and then exclude k = ∞.

Assume that

k < ∞

. We will show that

(

= 1)

0, and hence it must

be the case that P

(n = 1) = 1.

To bound this probability, we let

(

) = [

−n, n

]

∩ Z

(which we will

sometimes write as B

), and let ∂B(n) be its boundary. We know that

(all infinite clusters intersect ∂B(n)) → 1

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

(all infinite clusters intersect ∂B(n)) ≥

We can then bound

(N = 1) ≥ 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

(

) are open is just

E(B(n))

. So

(N = 1) ≥

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

∼ n

. We will then show deterministically that the number of trifurcations

inside

(

) must be

≤ |∂B

(

)

, and so there are

(

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

(0 is a trifurcation) = P

(x is a trifurcation)

for all x ∈ Z

Claim. P

(0 is a trifurcation) > 0.

We need to use something slightly different from

(

). We define

(

) =

{x ∈ Z

: kxk

≤ n}.

The crucial property of this is that for any

, x

∈ ∂S

(

), there exist three

disjoint self-avoiding paths joining

to 0 (exercise!). For each triple

, x

we arbitrarily pick a set of three such paths, and define the event

J(x

, x

) = {all edges on these 3 paths are open

and everything else inside S(n) is closed}.

Next, for every possible infinite cluster in

\ S

(

) that intersects

∂S

(

) at at

least one point, we pick a designated point of intersection arbitrarily.

Then we can bound

(0 is a trifurcation) ≥ P

(∃C

∞

, C

∞

, C

∞

⊆ Z

\ S(n)

infinite clusters which intersect ∂S(n) at x

, x

, and J(x

, x

)).

Rewrite the right-hand probability as

(J(x

, x

) | ∃C

∞

, C

∞

, C

∞

⊆ Z intersecting ∂S(n))

× P

(∃C

∞

, C

∞

, C

∞

⊆ Z

\ ∂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

(

∞

) = 1.

(

∃C

∞

, C

∞

, C

∞

⊆ Z

\ S

(

)

intersecting ∂S

(

))

→

1 as

n → ∞

. We can

then take

large enough such that the probability is

≥

. So we have shown

that c ≡ P

(0 is a trifurcation) > 0.

Using the linearity of expectation, it follows that

[number of trifurcations inside B(n))] ≥ c|B(n)| ∼ n

On the other hand, we can bound the number of trifurcations in

(

) by

|∂B

(

)

To see this, suppose

is a trifurcation in

(

). By definition, there exists

3 open paths to

∂B

(

). Fix three such paths. Let

be another trifurcation.

It also has 3 open paths to the

∂B

(

), and its paths to the boundary could

intersect those of

. However, they cannot create a cycle, by definition of a

trifurcation. For simplicity, we add the rule that when we produce the paths for

, once we intersect the path of x

, we continue following the path of x

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.

1.2 Correlation inequalities

In this section, we are going to prove some useful inequalities and equalities,

and use them to prove some interesting results about

(

) and the decay of

(0 ↔ ∂B

To motivate our first inequality, suppose we have 4 points

x, y, u, v

, and we

want to ask for the conditional probability

(x ↔ y | u ↔ v).

Intuitively, we expect this to be greater than

(

x ↔ y

), since

u ↔ v

tells us

there are some open edges around, which is potentially helpful. The key property

underlying this intuition is that having more edges is beneficial to both of the

events. To quantify this, we need the notion of an increasing random variable.

Again, let

= (

V, E

) be a graph and Ω =

{

}

. We shall assume that

is countable.

Notation (≤). Given ω, ω

∈ Ω, we write ω ≤ ω

if ω(e) ≤ ω

(e) for all e ∈ E.

This defines a partial order on Ω.

Definition

(Increasing random variable)

A random variable

is increasing if

X(ω) ≤ X(ω

) whenever ω ≤ ω

, and is decreasing if −X is increasing.

Definition

(Increasing event)

An event

is increasing (resp. decreasing) if

the indicator 1(A) is increasing (resp. decreasing)

Example. {|C(0)| = ∞} is an increasing event.

An immediate consequence of the definition is that

Theorem. If N is an increasing random variable and p

≤ p

, then

[N] ≤ E

[N],

and if an event A is increasing, then

(A) ≤ P

(A).

Proof. Immediate from coupling.

What we want to prove is the following result, which will be extremely useful.

Theorem

(Fortuin–Kasteleyn–Ginibre (FKG) inequality)

Let

and

increasing random variables with E

], E

] < ∞. Then

[XY ] ≥ E

[X]E

[Y ].

In particular, if A and B are increasing events, then

(A ∩ B) ≥ P

(A)P

(B).

Equivalently,

(A | B) ≥ P

(A).

Proof.

The plan is to first prove this in the case where

and

depend on a

finite number of edges, and we do this by induction. Afterwards, the desired

result can be obtained by an application of the martingale convergence theorem.

In fact, the “real work” happens when we prove it for

and

depending on

a single edge. Everything else follows from messing around with conditional

probabilities.

and

depend only on a single edge

, then for any

, ω

∈ {

}

, we

claim that

(X(ω

) − X(ω

))(Y (ω

) − Y (ω

)) ≥ 0.

Indeed,

and

are both increasing. So if

> ω

, then both terms are

positive; if

ω < ω

, then both terms are negative, and there is nothing to do if

they are equal.

In particular, we have

,ω

∈{0,1}

(X(ω

) −X(ω

))(Y (ω

) −Y (ω

))P

(ω(e

) = ω

(ω(e

) = ω

) ≥ 0.

Expanding this, we find that the LHS is 2(

[

]

− E

[

]

[

]), and so we

are done.

Now suppose the claim holds for

and

that depend on

n < k

edges. We

shall prove the result when they depend on k edges e

, . . . , e

. We have

[XY ] = E

[XY | ω(e

), . . . , ω(e

k−1

)]].

Now after conditioning on

(

)

, . . . , ω

(

k−1

), the random variables

and

become increasing random variables of ω(e

). Applying the first step, we get

[XY | ω(e

), . . . , ω(e

k−1

)]

≥ E

[X | ω(e

), . . . , ω(e

k−1

)]E

[Y | ω(e

), . . . , ω(e

k−1

)]. (∗)

But

[

X | ω

(

)

, . . . , ω

(

k−1

)] is a random variable depending on the edges

, . . . , e

k−1

, and moreover it is increasing. So the induction hypothesis tells us



[X | ω(e

), . . . , ω(e

k−1

)]E

[Y | ω(e

), . . . , ω(e

k−1

)]



≥ E



[X | ω(e

), . . . , ω(e

k−1

)]





[Y | ω(e

), . . . , ω(e

k−1

)]



Combining this with (the expectation of) (∗) then gives the desired result.

Finally, suppose

and

depend on the states of a countable set of edges

, e

, . . .. Let’s define

= E

[X | ω(e

), . . . , ω(e

)]

= E

[Y | ω(e

), . . . , ω(e

)]

Then

and

are martingales, and depend only on the states of only finitely

many edges. So we know that

] ≥ E

] = E

[X]E

[Y ].

By the

-martingale convergence theorem,

→ X

→ Y

and almost

surely. So taking the limit n → ∞, we get

[XY ] ≥ E

[X]E

[Y ].

What we want to consider next is the notion of disjoint occurrence. For

example, we want to able to ask the probability that there exists two disjoint

paths connecting a pair of points.

To formulate this disjointness, suppose we have an event

, and let

ω ∈ A

To ask whether this occurrence of

depends only on some set

S ⊆ E

of edges,

we can look at the set

[ω]

= {ω

∈ Ω : ω

(e) = ω(e) for all e ∈ S}.

If [

]

⊆ A

, then we can rightfully say this occurrence of

depends only on

the edges in

. Note that this depends explicitly and importantly on

, i.e. the

“reason”

happened. For example, if

{x ↔ y}

, and

ω ∈ A

, then we can

take

to be the set of all edges in a chosen path from

in the configuration

of ω. This choice will be different for different values of ω.

Using this, we can define what it means for two events to occur disjointly.

Definition

(Disjoint occurrence)

Let

be a set and Ω =

{

}

. If

and

are events, then the event that A and B occurs disjointly is

A ◦ B = {ω ∈ Ω : ∃S ⊆ F s.t. [ω]

⊆ A and [ω]

F \S

⊆ B}.

Theorem

(BK inequality)

Let

be a finite set and Ω =

{

}

. Let

and

B be increasing events. Then

(A ◦ B) ≤ P

(A)P

(B).

This says if

and

are both events that “needs” edges to occur, then requir-

ing that they occur disjointly is more difficult than them occurring individually.

The proof is completely magical. There exist saner proofs of the inequality,

but they are rather longer.

Proof (Bollob´as and Leader).

We prove by induction on the size

of the set

For n = 0, it is trivial.

Suppose it holds for

n −

1. We want to show it holds for

. For

D ⊆ {

}

and i = 0, 1, set

= {(ω

, . . . , ω

n−1

) : (ω

, . . . , ω

n−1

, i) ∈ D}.

Let A, B ⊆ {0, 1}

, and C = A ◦ B. We check that

= A

◦ B

, C

= (A

◦ B

) ∪ (A

◦ B

Since

and

are increasing,

⊆ A

and

⊆ B

, and

and

are also

increasing events. So

⊆ (A

◦ B

) ∩ (A

◦ B

)

⊆ A

◦ B

By the induction hypothesis, we have

) = P

◦ B

) ≤ P

)

) ≤ P

◦ B

) ≤ P

)

) + P

) ≤ P

((A

◦ B

) ∩ (A

◦ B

)) + P

((A ◦ B

) ∪ (A

◦ B

))

= P

◦ B

) + P

◦ B

)

≤ P

) + P

Now note that for any D, we have

(D) = pP

) + (1 − p)P

By some black magic, we multipy the first inequality by (1

− p

)

, the second by

and the third by p(1 − p). This gives

) + (1 −p)P

) ≤ (pP

) + (1 −p)P

))(pP

) + (1 −p)P

)).

Expand and we are done.

It turns out the increasing hypothesis is not necessary:

Theorem

(Reimer)

For all events

A, B

depending on a finite set, we have

(A ◦ B) ≤ P

(A)P

(B).

But the proof is much harder, and in all the case where we want to apply

this, the variables are increasing.

As an application of the BK inequality, we first prove a preliminary result

about the decay of

↔ ∂B

(

)). To prove our result, we will need a stronger

condition than p < p

. Recall that we defined

θ(p) = P

(|C(0)| = ∞).

We also define

χ(p) = E

[|C(0)|].

If χ(p) is finite, then of course θ(p) = 0. However, the converse need not hold.

Theorem.

(

)

< ∞

, then there exists a positive constant

such that for all

n ≥ 1,

(0 ↔ ∂B(n)) ≤ e

−cn

Later, we will show that in fact this holds under the assumption that

p < p

However, that requires a bit more technology, which we will develop after this

proof.

The idea of the proof is that if we want a path from, say, 0 to

), then

the path must hit a point on

∂B

(

). So there is a path from 0 to a point on

∂B

(

), and a path from that point to

∂B

). Moreover, these two paths are

disjoint, which allows us to apply the BK inequality.

Proof. Let

x∈∂B(n)

1(0 ↔ x).

Now consider

∞

n=0

E[X

] =

x∈∂B(n)

(0 ↔ x) =

x∈Z

(0 ↔ x) = χ(p).

Since

(

) is finite, we in particular have

[

]

→

0 as

n → ∞

. Take

large

enough such that E

] < δ < 1.

Now we have

(0 ↔ ∂B(m + k)) = P

(∃x ∈ ∂B(m) : 0 ↔ x and x ↔ ∂B(m + k) disjointly)

≤

x∈∂B(m)

(0 ↔ x)P

(x ↔ ∂B(m + k)) (BK)

≤

x∈∂B(m)

(0 ↔ x)P

(0 ↔ ∂B(k)) (trans. inv.)

≤ P

(0 ↔ B(k))E

So for any

n > m

, write

, where

r ∈

, m −

1]. Then iterating the

above result, we have

(0 ↔ ∂B(n)) ≤ P

(0 ↔ B(mq)) ≤ δ

≤ δ

−1+

≤ e

−cn

To replace the condition with the weaker condition

p < p

, we need to

understand how

(

) changes with

. We know

(

) is an increasing function in

. It would be great if it were differentiable, and even better if we could have an

explicit formula for

dθ

To do so, suppose we again do coupling, and increase

by a really tiny bit.

Then perhaps we would expect that exactly one of the edges switches from being

closed to open. Thus, we want to know if the state of this edge is pivotal to the

event |C(0)| = ∞, and this should determine the rate of change of θ.

Definition

(Pivotal edge)

Let

be an event and

a percolation configuration.

The edge e is pivotal for (A, ω) if

1(ω ∈ A) 6= 1(ω

∈ A),

where ω

is defined by

(f) =

(

ω(f) f 6= e

1 − ω(f) f = e

The event that

is pivotal for

is defined to be the set of all

such that

pivotal for (A, ω).

Note that whether or not e is pivotal for (A, ω) is independent of ω(e).

Theorem

(Russo’s formula)

Let

be an increasing event that depends on the

states of a finite number of edges. Then

(A) = E

[N(A)],

where N (A) is the number of pivotal edges for A.

Proof.

Assume that

depends the states of

edges

, . . . , e

. The idea is to

let each

be open with probability

, whree the

}

may be distinct. We then

vary the p

one by one and see what happens.

Writing ¯p = (p

, . . . , p

), we define

f(p

, . . . , p

) = P

¯p

(A),

Now

is the sum of the probability of all configurations of

, . . . , e − m}

for

which

happens, and is hence a finite sum of polynomials. So in particular, it

is differentaible.

We now couple all percolation process. Let (

(

) :

e ∈ L

) be iid

random variables. For a vector ¯p = (p(e) : e ∈ L

), we write

¯p

(e) = 1(X(e) ≤ p(e)).

Then we have P

¯p

(A) = P(η

¯p

∈ A).

Fix an edge

and let

¯p

= (

(

)) be such that

(

) =

(

) for all

e 6

, and

(f) = p(f ) + δ for some δ > 0. Then

¯p

(A) − P

¯p

(A) = P(η

¯p

∈ A) − P(η

¯p

∈ A)

= P(η

¯p

∈ A, η

¯p

∈ A) + P(η

¯p

∈ A, η

¯p

∈ A) − P(η

¯p

∈ A).

But we know

is increasing, so

(

¯p

∈ A, η

¯p

∈ A

) =

(

¯p

∈ A

). So the first

and last terms cancel, and we have

¯p

(A) − P

¯p

(A) = P(η

¯p

∈ A, η

¯p

6∈ A).

But we observe that we simply have

P(η

¯p

∈ A, η

¯p

6∈ A) = δ · P

¯p

(f is pivotal for A).

Indeed, we by definition of pivotal edges, we have

P(η

¯p

∈ A, η

¯p

6∈ A) = P

¯p

(f is pivotal for A, p(f) < X(f) ≤ p(f) + δ).

Since the event

{f is pivotal for A}

is independent of the state of the edge

we obtain

¯p

(f is pivotal, p(f) < X(f) ≤ p(f) + δ) = P

¯p

(f is pivotal) · δ.

Therefore we have

∂

∂p(f)

¯p

(A) = lim

δ→0

¯p

(A) − P

¯p

(A)

= P

¯p

(f is pivotal for A).

The desired result then follows from the chain rule:

(A) =

i=1

∂

∂p(e

)

¯p

(A)



¯p=(p,...,p)

i=1

is pivotal for A)

= E

[N(A)].

depends on an infinite number of edges, then the best we can say is that

lim inf

δ↓0

p+δ

(A) − P

(A)

≥ E

[N(A))].

To see this, again set B(n) = [−n, n]

∩ Z

. Define ¯p

¯p

(e) =

(

p e 6∈ B(n)

p + δ e ∈ B(n)

Then since a is increasing, we know

p+δ

(A) − P

(A)

≥

¯p

(A) − P

(A)

We can then apply the previous claim, take successive differences, and take

n → ∞.

Corollary.

Let

be an increasing event that depends on

edges. Let

p ≤ q ∈

[0, 1]. Then P

(A) ≤ P

(A)





Proof.

We know that

{f is pivotal for A}

is independent of the state of

, and

(ω(f) = 1, f is pivotal for A) = pP

(f is pivotal for A).

But since

is increasing, if

(

) = 1 and

is pivotal for

, then

occurs.

Conversely, if f is pivotal and A occurs, then ω(f) = 1.

Thus, by Russo’s formula, we have

(A) = E

[N(A)]

(e is pivotal for A)

(ω(e) = 1, e is pivotal for A)

(e is pivotal | A)P

(A)

= P

(A)

[N(A) | A].

So we have

(A)

[N(A) | A].

Integrating, we find that

log

(A)

[N(A) | A] du.

Bounding E

[N(A) | A] ≤ m, we obtain the desired bound.

With Russo’s formula, we can now prove the desired theorem.

Theorem. Let d ≥ 2 and B

= [−n, n]

∩ Z

(i)

p < p

, then there exists a positive constant

for all

n ≥

↔

∂B

) ≤ e

−cn

(ii) If p > p

, then

θ(p) = P

(0 ↔ ∞) ≥

p − p

p(1 − p

)

This was first proved by Aizenman and Barsky who looked at the more

general framework of long-range percolation. Menshikov gave an alternative

proof by analyzing the geometry of pivotal edges. The proof we will see is by

Duminil-Copin and Tassion. Recall that we defined

χ(p) = E

[|C(0)|].

We saw that if

(

)

< ∞

, then

↔ ∂B

)

≤ e

−cn

. We now see that

(

)

< ∞

iff p < p

The strategy of the proof is to define a new percolation probability

˜p

, whose

definition makes it easier to prove the theorem. Once we have established the

two claims, we see that (i) forces ˜p

≤ p

, and (ii) forces ˜p

≥ p

. So they must

be equal.

Proof (Duminil-Copin and Tassion). If S ⊆ V is finite, we write

∂S = {(x, y) ∈ E : x ∈ S, y 6∈ S}.

We write

↔ y

if there exists an open path of edges from

all of whose

end points lie in S.

Now suppose that 0 ∈ S. We define

(S) = p

(x,y)∈∂S

↔ x).

Define

˜p

= sup{p ∈ [0, 1] : exists a finite set S with 0 ∈ S and ϕ

(S) < 1}.

Claim. It suffices to prove (i) and (ii) with p

replaced by ˜p

Indeed, from (i), if

p < ˜p

, then

↔ ∂B

)

≤ e

−cn

. So taking the limit

n → ∞

, we see

(

) = 0. So

˜p

≤ p

. From (ii), if

p > ˜p

, then

(

)

0. So

≤ ˜p

. So p

= ˜p

We now prove (i) and (ii):

(i)

Let

p < ˜p

. Then there exists a finite set

containing 0 with

(

)

Since

is finite, we can pick

large enough so that

S ⊆ B

L−1

. We will

prove that P

(0 ↔ ∂B

) ≤ (ϕ

(S))

k−1

for k ≥ 1.

Define C = {x ∈ S : 0

↔ x}. Since S ⊆ B

L−1

, we know S ∩ ∂B

= ∅.

Now if we have an open path from 0 to

∂B

, we let

be the last element

on the path that lies in

. We can then replace the path up to

by a path

that lies entirely in

, by assumption. This is then a path that lies in

, then takes an edge on

∂S

, and then lies entirely outside of

. Thus,

(0 ↔ ∂B

) ≤

A⊆S

0∈A

(x,y)∈∂A

↔ x, (x, y) open, C = A, y

↔ ∂B

Now observe that the events

↔ x}

{

(

x, y

)

is open}

and

↔

∂B

} are independent. So we obtain

(0 ↔ ∂B

) ≤

A⊆S,0∈A

(x,y)∈∂S

p P

↔ x, C = A) P

↔ ∂B

Since we know that y ∈ B

, we can bound

↔ ∂B

) ≤ P

(0 ↔ ∂B

(k−1)L

So we have

(0 ↔ ∂B

) ≤ p P

(0 ↔ ∂B

(k−1)L

)

A⊆S,0∈A

(x,y)∈∂S

↔ x, C = A)

= P

(0 ↔ ∂B

(k−1)L

) p

(x,y)∈∂S

↔ x)

= P

(0 ↔ ∂B

(k−1)L

)ϕ

(S).

Iterating, we obtain the deseired result.

(ii) We want to use Russo’s formula. We claim that it suffices to prove that

(0 ↔ ∂B

) ≥

p(1 − p)

inf

S⊆B

,0∈S

(S)(1 − P

(0 ↔ ∂B

)).

Indeed, if

p > ˜p

, we integrate from

˜p

, use in this range

(

)

≥

and then take the limit as n → ∞.

The event

{

↔ ∂B

}

is increasing and only dependson a finite number of

edges. So we can apply Russo’s formula

(0 ↔ ∂B

) =

e∈B

(e is pivotal for {0 ↔ ∂B

})

Since being pivotal and being open/closed are independent, we can write

this as

e∈B

1 − p

(e is pivotal for {0 ↔ ∂B

}, e is closed)

e∈B

1 − p

(e is pivotal for {0 ↔ ∂B

}, 0 6↔ ∂B

)

Define S = {x ∈ B

: x 6↔ ∂B

}. Then {0 6↔ ∂B

} implies 0 ∈ S. So

(0 ↔ ∂B

) =

1 − p

e∈B

A⊆B

,0∈A

(e is pivotal, S = A)

Given that

, an edge

= (

x, y

) is pivotal iff

e ∈ ∂A

and 0

↔ x

. So

we know

(0 ↔ ∂B

) =

1 − p

A⊆B

,0∈A

(x,y)∈∂A

↔ x, S = A).

Observe that

{

↔ x}

and

are independent, since to determine if

, we only look at the edges on the boundary of

. So the above is

equal to

1 − p

A⊆B

,0∈A

(x,y)∈∂A

↔ x)P

(S = A)

p(1 − p)

A⊆B

,0∈A

(A)P

(S = A)

≥

p(1 − p)

inf

S⊆B

,0∈S

(S)P

(0 6↔ ∂B

as desired.

We might ask if

↔ ∂B

)

≤ e

−cn

is the best convergence rate when

p < p

, but we cannot do better, since P

(0 ↔ ∂B

) ≥ p

Also, if p < p

, then we can easily bound

(|C(0)| ≥ n) ≤ P

(0 ↔ ∂B

1/d

) ≤ exp(−cn

1/d

However, this is not a good bound. In fact,

1/d

can be replaced by

, but we

will not prove it here. This tells us the largest cluster in

will have size of

order log n with high probability.

1.3 Two dimensions

We now focus on 2 dimensions. As discussed previously, we can exploit duality to

prove a lot of things specific to two dimensions. In particular, we will show that,

, certain probabilities such as

↔ ∂B

(

)) exhibit a power law

decay. This is in contrast to the exponential decay for subcritical percolation

(and being bounded away from zero for supercritical percolation).

First we establish that p

is actually

Theorem. In Z

, we have θ





= 0 and p

It is conjectured that for all

d ≥

2, we have

(

)) = 0. It is known to be

true only in d = 2 and d ≥ 11.

This was proved first by Harris, Kesten, Russo, Seymour, Welsh in several

iterations.

Proof. First we prove that θ





= 0. This will imply that p

≥

Suppose not, and θ





> 0. Recall that B(n) = [−n, n]

, and we define

C(n) = [−(n −1), (n − 1)]





in the dual lattice. The appearance of the

−

1 is just a minor technical inconve-

nience. For the same n, our B(n) and C(n) look like

B(n)C(n)B(n)

We claim that for large

, there is a positive probability that there are open

paths from the left and right edges of

(

) to

∞

, and also there are closed

paths from the top and bottom edges of

(

) to

∞

. But we know that with

probability 1, there is a unique infinite cluster in both the primal lattice and

the dual lattice. To connect up the two infinite open paths starting from the

left and right edges of

(

), there must be an open left-right crossing of

(

To connect up the two infinite closed paths starting from the top and bottom

(

), there must be a closed top-bottom crossing. But these cannot both

happen, since this would require an open primal edge crossing a closed dual edge,

which is impossible.

To make this an actual proof, we need to show that these events do happen

with positive probability. We shall always take

, and will not keep repeating

it.

First note that since there is, in particular, an infinite cluster with probability

1, we have

P(∂B(n) ↔ ∞) → 1.

So we can pick n large enough such that

P(∂B(n) ↔ ∞), P(∂C(n) ↔ ∞) ≥ 1 −

Let

be the events that the left/right/top/bottom side of

(

) is

connected to

∞

via an open path of edges. Similarly, let

be the event that

the left of C(n) is connected to ∞ via a closed path, and same for D

, D

Of course, by symmetry, for

i, j ∈ {`, r, t, b}

, we have

(

) =

(

). Using

FKG, we can bound

P(∂S

6↔ ∞) = P(A

∩ A

) ≥ (P(A

))

= (1 − P(A

))

Thus, by assumption on n, we have

(1 − P(A

))

≤

hence

P(A

) ≥

Of course, the same is true for other A

and D

Then if G = A

∩ A

∩ D

, which is the desired event, then we have

P(G

) ≤ P(A

) + P(A

) + P(D

) ≤

So it follows that

P(G) ≥

which, as argued, leads to a contradiction.

So we have

≥

. It remains to prove that

≤

. Suppose for contradiction

that

. Then

is in the subcritical regime, and we expect exponential

decay. Thus, (again with

fixed) there exists a

c >

0 such that for all

n ≥ 1,

P(0 ↔ ∂B(n)) ≤ e

−cn

Consider

= [0

, n

+ 1]

, n

], and define

to be the event that there exists

a left-right crossing of C

by open edges.

Again consider the dual box D

= [0, n] × [−1, n] +





Define

to be the event that there is a top-bottom crossing of

by closed

edges of the dual.

As before, it cannot be the case that

and

both occur. In fact,

and

partition the whole space, since if

does not hold, then every path from

left to right of C

is blocked by a closed path of the dual. Thus, we know

P(A

) + P(B

) = 1.

But also by symmetry, we have P(A

) = P(B

). So

P(A

) =

On the other hand, for any point on the left edge, the probability of it reaching

the right edge decays exponentially with n. Thus,

P(A

) ≤ n(n + 1)P(0 ↔ ∂B

) ≤ (n + 1)e

−cn

which is a contradiction. So we are done.

So we now know that p

. We now want to prove that

(0 ↔ ∂B(n)) ≤ An

−α

for some

A, α

. To prove this, we again consider the dual lattice. Observe that if

we have a closed dual circuit around the origin, then this prevents the existence

of an open path from the origin to a point far far away. What we are going to

do is to construct “zones” in the dual lattice like this:

The idea is to choose these zones in a way such that the probability that each

zone contains a closed circuit around the origin is

≥ ζ

for some fixed

. Thus, if

(

) contains

many of these zones, then the probability that 0 is connected

∂B

(

) is bounded above by (1

−ζ

)

. We would then be done if we can show

that m ∼ log n.

The main strategy to bounding these probabilities is to use FKG. For example,

if we want to bound the probability that there is a closed circuit in a region

then we cut it up into the pieces

If we can bound the probability of there being a left-to-right crossing of a

horizontal piece, and hence by symmetry the probability of there being a top-to-

bottom crossing of a vertical piece, then FKG gives us a bound on the probability

of there being a closed circuit.

For convenience of notation, we prove these bounds for open paths in the

primal lattice. We make the following definitions:

B(k`, `) = [−`, (2k − 1)`] × [−`, `]

B(`) = B(`, `) = [−`, `]

A(`) = B(3`) \ B(`)

LR(k`, `) = {there exists left-right crossing of B(k`, `) of open edges}

LR(`) = LR(`, `)

O(`) = {there exists open circuit in A(`) that contains 0 in its interior}.

We first note that we have already proven the following:

Proposition. P

(LR(`)) ≥

for all `.

Proof.

We have already seen that the probability of there being a left-right

crossing of [0

, n

+ 1]

, n

] is at least

. But if there is a left-right crossing of

[0, n + 1] × [0, n], then there is also a left-right crossing of [0, n] × [0, n]!

For a general

, Russo–Symour–Welsh (RSW) lets us bound

(

)) by

(LR(`)):

Theorem (Russo–Symour–Welsh (RSW) theorem). If P

(LR(`)) = α, then

(O(`)) ≥





1 −

√

1 − α





A large part of the proof is done by the cut-and-paste argument we sketched

above. However, to successfully do cut-and-paste, it turns out we need bounds

on the probability of a left-right crossing on something that is not a square. The

key, non-trivial estimate is the following:

Lemma. If P

(LR(`)) = α, then



`, `



≥ (1 −

√

1 − α)

To prove this, we need a result from the first example sheet:

Lemma

(

th root trick)

, . . . , A

are increasing events all having the same

probability, then

) ≥ 1 −

1 − P

[

i=1

1/n

Proof sketch.

Observe that the proof of FKG works for decreasing events as well,

and then apply FKG to A

We can now prove our initial lemma.

Proof sketch.

Let

be the set of left-right crossings of

(

) = [

−`, `

]

. Define a

partial order on

≤ π

is contained in the closed bounded region of

B(`) below π

Note that given any configuration, if the set of open left-right crossings is

non-empty, then there exists a lowest one. Indeed, since

must be finite, it

suffices to show that meets exist in this partial order, which is clear.

For a left-right crossing

, let (0

, y

) be the last vertex on the vertical axis

where

intersects, and let

be the path of the path that connects (0

, y

) to

the right.

(0, y

)

Let

−

= {π ∈ A : y

≤ 0}

= {π ∈ A : y

≥ 0}

Letting

(

)

= [0

]

[

−`, `

], our goal is to find a left-right crossing of the

form

More precisely, we want the following paths:

(i) Some π ∈ A

−

(ii) Some top-bottom crossing of B(`

) that crosses π

(iii)

Some left-right crossing of

(

) that starts at the positive (i.e. non-

negative) y axis.

To understand the probabilities of these events happening, we consider the

“mirror” events and then apply the square root trick.

Let π

be the reflection of π

on {(`, k) : k ∈ Z}. For any π ∈ A, we define

= {all edges of π are open}

= {exists open crossing from top of B(`)

to π

∪ π

}

−

= {exists open crossing from top of B(`)

to π

}

= {exists open crossing from top of B(`)

to π

}

= {exists open path in A

}

−

= {exists open path in A

−

}

= {π is the lowest open LR crossing of B(`)}

N = {exists open LR crossing of B(`)

}

= {exists open LR crossing in B(`)

starting from positive vertical axis}

−

= {exists open LR crossing in B(`)

starting from negative vertical axis}

In this notation, our previous observation was that

[

π∈A

−

∩ M

−

)

| {z }

∩N

⊆ LR



`, `



So we know that



`, `



≥ P

(G ∩ N

) ≥ P

(G)P

using FKG.

Now by the “square root trick”, we know

) ≥ 1 −

1 − P

∪ N

−

Of course, we have P

∪ N

−

) = P

(LR(`)) = α. So we know that

) ≥ 1 −

√

1 − α.

We now have to understand

. To bound its probability, we try to bound it by

the union of some disjoint events. We have

(G) = P





[

π∈A

−

∩ M

−

)





≥ P





[

π∈A

−

∩ L

)





π∈A

−

| L

Claim.

−

| L

) ≥ 1 −

√

1 − α.

Note that if

intersects the vertical axis in one point, then

(

−

| L

) =

(

−

| V

), since

−

tells us what happens below

, and this does not affect

the occurrence of M

−

Since M

−

and V

are increasing events, by FKG, we have

−

| V

) ≥ P

−

) ≥ 1 −

1 − P

−

∪ M

) = 1 −

1 − P

Since P

) ≥ P

(LR(`)) = α, the claim follows.

In the case where

is more complicated, we will need an extra argument,

which we will not provide.

Finally, we have

(G) ≥

π∈A

−

)(1 −

√

1 − α) = (1 −

√

1 − α)P

−

But again by the square root trick,

−

) ≥ 1 −

1 − P

∪ L

−

) = 1 −

√

1 − α,

and we are done.

We now do the easy bit to finish off the theorem:

Lemma.

(LR(2`, `)) ≥ P

(LR(`))



`, `



(LR(3`, `)) ≥ P

(LR(`)) (P

(LR (2`, `)))

(O(`)) ≥ P

(LR(3`, `))

Proof. To prove the first inequality, consider the box [0, 4`] × [−`, `].

3``

We let

= {exists left-right crossing of [0, 3`] × [−`, `]}

= {exists left-right crossing of [`, 4`] × [−`, `]}

T B

= {exists top-bottom crossing of [`, 3`] × [−`, `]}.

Then by FKG, we find that

(LR(2`, `)) ≥ P

(LR

∩ LR

∩ T B

) ≥ P

(LR

(T B

The others are similar.

Theorem. There exists positive constants α

, α

, A

such that

(0 ↔ ∂B(n)) ≤ A

−α

(|C(0)| ≥ n) ≤ A

−α

E(|C(0)|

) ≤ ∞

Moreover, for p > p

, we have

θ(p) ≤ A



p −



It is an exercise on the example sheet to prove that

↔ B

(

))

≥

√

using the BK inequality. So the true decay of

↔ ∂B

(

)) is indeed a power

law.

Proof.

(i) We first prove the first inequality. Define dual boxes

B(k)

= B(k) +





The dual annuli A(`)

are defined by

A(`)

= B(3`)

\ B(`)

We let

(

)

be the event that there is a closed dual circuit in

(

)

containing





. Then RSW tells us there is some ζ ∈ (0, 1) such that

(O(`)

) ≥ ζ,

independent of `. Then observe that

(0 ↔ ∂B(3

+ 1)) ≤ P

(O(3

)

does not occur for all r < k).

Since the annuli (

)

) are disjoint, the events above are independent.

(0 ↔ ∂B(3

+ 1)) ≤ (1 − ζ)

and this proves the first inequality.

(ii)

The second inequality follows from the first inequality plus the fact that

|C(0)| ≥ n implies 0 ↔ ∂B(g(n)), for some function g(n) ∼

√

(iii)

To show that

[

(0)

]

< ∞

for some

, we observe that this expecta-

tion is just

(|C(0)|

≥ n).

(iv) To prove the last part, note that

θ(p) = P

(|C(0)| = ∞) ≤ P

(0 ↔ ∂B

)

for all

. By the corollary of Russo’s formula, and since

{

↔ ∂B

}

only

depends on the edges in B

, which are ≤ 18n

, we get that

(0 ↔ ∂B

) ≥





18n

(0 ↔ ∂B

θ(p) ≤ (2p)

18n

(0 ↔ ∂B

) ≤ A

(2p)

18n

−α

Now take n = b(log 2p)

−1/2

c. Then as p &

, we have

n ∼

(2p − 1)

Substituting this in, we get

θ(p) ≤ C



p −



By similar methods, we can prove that

Theorem.

When

= 2 and

p > p

, there exists a positive constant

such that

(0 ↔ ∂B(n), |C(0)| < ∞) ≤ e

−cn

It is natural to ask if we have a similar result in higher dimensions. In higher

dimensions, all the techniques in Z

don’t work.

Higher dimensions

In d ≥ 3, define the slab

= Z

× {0, 1, . . . , k}

d−2

Then S

⊆ S

k+1

⊆ Z

In general, for a graph

, we let

(

) be the critical probability of bond

percolation in G. Then we have

) ≥ p

k+1

) ≥ p

So the sequence (p

)) must converge to a limit. Call this limit

slab

= lim

k→∞

We know that p

slab

≥ p

A lot of the results we can prove for

can be proven for

slab

instead of

So the natural question is how

slab

is related to

, and in particular, if they

are equal. This has been an open question for a long time, until Grimmett and

Marstrand proved it.

Theorem

(Grimmett–Marstrand)

Let

be an infinite-connected subset of

with p

(F ) < 1. Then for all η > 0, there exists k ∈ N such that

(2kF + B

) ≤ p

+ η.

In particular, for all d ≥ 3, p

slab

= p

We shall not prove the theorem, but we shall indicate how the “in particular”

part works.

We take F = Z

× {0}

d−2

. Then

2kF + B

= Z

× ([−k, k]

d−2

∩ Z

d−2

a translate of S

. So p

) = p

(2kF + B

) → p

as k → ∞.

A consequence of Grimmett-Marstrand is that

Theorem. If d ≥ 3 and p > p

, then there exists c > 0 such that

(0 ↔ ∂B(n), |C(0)| < ∞) ≤ e

−cn

1.4 Conformal invariance and SLE in d = 2

Instead of working on

, we will now work on the triangular lattice

. We

consider site percolation. So every vertex is open (black) with probability

and

closed (white) with probability 1 − p, independently for different vertices.

Like for Z

, we can show that p = p

(T) =

Let

be an open simply connected domain in

with

∂D

a Jordan curve.

Let

a, b, c ∈ ∂D

be 3 points labeled in anti-clockwise order. Consider the triangle

with vertices

= 0,

= 1 and

iπ/3

. By the Riemann mapping theorem,

there exists a conformal map ϕ : D → T that maps a 7→ A, b 7→ B, c 7→ C.

Moreover, this can be extended to ∂D such that ϕ :

D →

T is a homeomor-

phism. If

is in the arc

, then it will be mapped to

(

) on the edge

BC of T .

Focus on the case

. We can again put a triangular lattice inside

with mesh size

. We let

ac ↔ bx

to mean the event that there is an open path

in D joining the arc ac to bx.

Then by RSW (for T), we get that

(ac ↔ bx) ≥ c > 0,

independent of

. We might ask what happens when

δ →

0. In particular, does

it converge, and what does it converge to?

Cardy, a physicist studying conformal field theories, conjectured that

lim

δ→0

(ac ↔ bx) = |BX|.

He didn’t really write it this way, but expressed it in terms of hypergeometric

functions. It was Carlesson who expressed it in this form.

In 2001, Smirnov proved this conjecture.

Theorem

(Smirnov, 2001)

Suppose (Ω

, a, b, c, d

) and (Ω

, a

, b

, c

, d

) are con-

formally equivalent. Then

P(ac ↔ bd in Ω) = P(a

↔ b

in Ω

This says percolation at criticality on the triangular lattice is conformally

invariant.

We may also take the dual of the triangular lattice, which is the hexagonal

lattice. Colour a hexagon black if the center is black, and similarly for whites.

Suppose we impose the boundary condition on the upper half plane that the

hexagons are black when x > 0, y = 0, and white when x < 0, y = 0.

Starting at (

x, y

) = (0

0), we explore the interface between the black and

white by always keeping a black to our right and white on our right. We can

again take the limit

δ →

0. What is this exploration path going to look like in

the limit δ → 0? It turns out this is an SLE(6) curve.

To prove this, we use the fact that the exploration curve satisfies the locality

property, namely that if we want to know where we will be in the next step, we

only need to know where we currently are.

2 Random walks

2.1 Random walks in finite graphs

We shall consider weighted random walks on finite graphs. Let

= (

V, E

) be a

finite connected graph. We assign a conductances/weights to the edges (

(

))

e∈E

Here c is a function of the edges, so we require c(xy) = c(yx).

In the weighted random walk on

, the probability of going from

(assuming x ∼ y) is

P(x, y) =

c(x, y)

c(x)

, c(x) =

z∼x

c(x, z).

If we put c(e) = 1 for all e, then this is just a simple random walk, with

P(x, y) =

(

deg x

y ∼ x

0 otherwise

The weighted random walk is reversible with respect to

(

) =

c(x)

, where

c(x), because

π(x)P (x, y) =

c(x)

c(x, y)

c(x)

= π(y)P(y, x).

Conversely, every reversible Markov chain can be represented as a random walk

on a weighted graph — place an edge

{x, y}

(

x, y

)

0. By reversibility,

P(x, y) > 0 iff P(y, x) = 0. Define weights

c(x, y) = π(x)P(x, y)

for all x ∼ y.

One way to understand random walks on weighted graphs is to think of them

as currents in electrical networks. We set the resistance on the edges by

r(e) =

c(e)

Naturally, we would like to talk about currents flowing through the circuit.

Definition

(Flow)

A flow

is a function defined on oriented edges which

is anti-symmetric, i.e. θ(x, y) = −θ(y, x).

Not every flow can be thought of as a current. We fix two distinguished

vertices

and

, called the source and the sink respectively. We think of current

as entering the network through

and exiting through

. Through any other

vertex, the amount of current going in should equal the amount of current going

out.

Definition (Divergence). The divergence of a flow θ is

div θ(x) =

y∼x

θ(x, y).

By the antisymmetry property, we have

div θ(x) =

y∼x

θ(x, y) =

x∼y

θ(x, y) = 0.

Definition (Flow from a to z). A flow θ from a to z is a flow such that

(i) div θ(x) = 0 for all x 6∈ {a, z}. (Kirchhoff’s node law)

(ii) div θ(a) ≥ 0.

The strength of the flow from

kθk

div θ

(

).We say this is a unit flow

if kθk = 1.

Since

div θ(x) = 0, a flow from a to z satisfies div θ(z) = −div θ(a).

Now if we believe in Ohm’s law, then the voltage difference across each edge

is I(x, y)r(x, y). So we have

W (x) = W (y) + r(x, y)I(x, y)

for all

. We know that if we sum

(

x, y

) over all

, then the result vanishes. So

we rewrite this as

c(x, y)W (x) = c(x, y)W (y) + I(x, y).

Summing over all y, we find that the voltage satisfies

W (x) =

x∼y

c(x, y)

c(x)

W (y) =

x∼y

P(x, y)W (y).

Definition

(Harmonic function)

Let

be a transition matrix on Ω. We call

harmonic for P at the vertex x if

h(x) =

P(x, y)h(y).

We now take this as a definition of what a voltage is.

Definition

(Voltage)

A voltage

is a function on Ω that is harmonic on

Ω \ {a, z}.

The first theorem to prove is that given any two values

(

) and

(

), we

can find a unique voltage with the prescribed values at a and z.

More generally, if

B ⊆

Ω, and

is a Markov chain with matrix

, then we

write

= min{t ≥ 0 : X

∈ B},

Proposition.

Let

be an irreducible matrix on Ω and

B ⊆

Ω,

B → R

function. Then

h(x) = E

[f(X

)]

is the unique extension of f which is harmonic on Ω \ B.

Proof. It is obvious that h(x) = f(x) for x ∈ B. Let x 6∈ B. Then

h(x) = E

[f(X

)]

P(x, y)E

[f(X

) | X

= y]

P(x, y)E

[f(X

)]

P(x, y)h(y)

So h is harmonic.

To show uniqueness, suppose

be another harmonic extension. Take

h − h

. Then g = 0 on B. Set

A =



x : g(x) = max

y∈Ω\B

g(y)



and let

x ∈ A \B

. Now since

(

) is the weighted average of its neighbours, and

(

)

≤ g

(

) for all neighbours

, it must be the case that

(

) =

(

) for

all neighbours of y.

Since we assumed

is connected, we can construct a path from

to the

boundary, where

vanishes. So

(

) = 0. In other words,

max g

= 0. Similarly,

min g = 0. So g = 0.

Given a voltage, Ohm’s law defines a natural flow, called the current flow.

Definition (Current flow). The current flow associated to the voltage W is

I(x, y) =

W (x) − W (y)

r(x, y)

= c(x, y)(W (x) − W (y)).

The current flow has an extra property, namely that it satisfies the cycle law.

For any cycle e

, e

, . . . , e

, we have

i=1

r(e

)I(e

) = 0.

Proposition.

Let

be a flow from

satisfying the cycle law for any cycle.

Let I the current flow associated to a voltage W . If kθk = kIk, then θ = I.

Proof.

Take

θ − I

. Then

is a flow which satisfies Kirchhoff’s node law

at all vertices and the cycle law for any cycle. We want to show that

= 0.

Suppose not. The we can find some e

such that f(e

) > 0. But

y∼x

f(x, y) = 0

for all

, so there must exist an edge

that

leads to such that

(

)

Continuing this way, we will get a cycle of ordered edges where

f >

0, which

violates the cycle law.

Let

be a voltage with

(

) = 1 and

(

) = 0, and let

be the current

associated to W

. Then any other voltage W can be written as

W (x) = (W (a) − W (z))W

(x) + W (z).

So, noting that W

(a) = 1, we have

W (a) = W (x) = (W (a) − W (z))(W

(a) − W

(x)).

Thus, if I is the current associated to W , then

kIk =

x∼a

I(a, x) =

x∼a

W (a) − W (x)

r(a, x)

= (W (a) − W (z))kI

So we know that

W (a) − W (z)

kIk

and in particular does not depend on W .

Definition

(Effective resistance)

The effective resistance

eff

(

a, z

) of an electric

network is defined to be the ratio

eff

(a, z) =

W (a) − W (z)

kIk

for any voltage

with associated current

. The effective conductance is

eff

(a, z) = R

eff

(a, z)

−1

Proposition. Take a weighted random walk on G. Then

(τ

< τ

) =

c(a)R

eff

(a, z)

where τ

= min{t ≥ 1 : X

= a}.

Proof. Let

f(x) = P

(τ

< τ

Then

(

) = 0 and

(

) = 1. Moreover,

is harmonic on Ω

\ {a, z}

. Let

a voltage. By uniqueness, we know

f(x) =

W (a) − W (x)

W (a) − W (z)

So we know

(τ

< τ

) =

x∼a

P(a, x)f (x)

x∼a

c(a, x)

c(a)

W (a) − W (x)

W (a) − W (z)

c(a)(W (a) − W (z))

x∼a

I(a, x)

kIk

c(a)(W (a) − W (z))

c(a)R

eff

(a, z)

Definition

(Green kernel)

Let

be a stopping time. We define the Green

kernel to be

(a, x) = E

∞

t=0

1(X

= x, t < τ )

This is the expected number of times we hit x before τ occurs.

Corollary. For any reversible chain and all a, z, we have

(a, a) = c(a)R

eff

(a, z).

Proof.

By the Markov property, the number of visits to

starting from

until

is the geometric distribution Geo(P

(τ

< τ

)). So

(a, a) =

(τ

< τ

)

= c(a)R

eff

(a, z).

Practically, to compute the effective resistance, it is useful to know some

high school physics. For example, we know that conductances in parallel add:

+ c

Thus, if

and

are two edges with the same endvertices, then we we can

replace them by a single edge of conductance the sum of the conductances. We

can prove that this actually works by observing that the voltages and currents

remain unchanged outside of

, e

, and we check that Kirchhoff’s and Ohm’s

law are satisfied with

I(e) = I(e

) + I(e

Similarly, resistances in series add. Let

be a node of degree 2 and let

and

be its 2 neighbours. Then we can replace these 2 edges by a single edge of

resistance

. Again, to justify this, we check Kirchoff’s and Ohm’s law with

I(v

) = I(v

v) + I(vv

v v

+ r

We can also glue 2 vertices of the same potential, keeping all other edges.

Current and potential are unchanged since current doesn’t flow if there is the

same potential.

Exercise.

Let

be a finite connected tree, and

a, z

two vertices. Then

eff

(

a, z

)

is the graph distance between a and z.

It turns out it is not convenient to work with our definition of effective

resistance. Instead, we can use the well known result from high school physics

P = IV = I

R. For any flow, we define

Definition

(Energy)

Let

be a flow on

with conductances (

(

)). Then the

energy is

E(θ) =

(θ(e))

r(e).

Here we sum over unoriented edges.

Note that given any flow, we can always increase the energy by pumping

more and more current along a cycle. Thus, we might expect the lowest energy

configuration to be given by the flows satisfying the cycle law, and if we focus

on unit flows, the following should not be surprising:

Theorem

(Thomson’s principle)

Let

be a finite connected graph with

conductances (c(e)). Then for any a, z, we have

eff

(a, z) = inf{E(θ) : θ is a unit flow from a to z}.

Moreover, the unit current flow from a to z is the unique minimizer.

Proof.

Let

be the unit current flow associated to potential

. Let

be another

unit flow a → z. We need to show that E(j) ≥ E(i) with equality iff j = i.

Let k = j −i. Then k is a flow of 0 strength. We have

E(j) = E(i + k) =

(i(e) + k(e))

r(e) = E(i) + E(k) + 2

i(e)k(e)r(e).

It suffices to show that the last sum is zero. By definition, we have

i(x, y) =

ϕ(x) − ϕ(y)

r(x, y)

So we know

i(e)k(e)r(e) =

y∼x

(ϕ(x) − ϕ(y))k(x, y)

y∼x

ϕ(x)k(x, y) +

y∼x

ϕ(x)k(x, y).

Now note that

y∼x

(

x, y

) = 0 for any

since

has zero strength. So this

vanishes.

Thus, we get

E(j) = E(i) + E(k),

and so E(j) ≥ E(i) with equality iff E(k) = 0, i.e. k(e) = 0 for all e.

Using this characterization, it is then immediate that

Theorem

(Rayleigh’s monotonicity principle)

Let

be a finite connected

graph and (

(

))

and (

(

))

two sets of resistances on the edges such that

r(e) ≤ r

(e) for all e. Then

eff

(a, z; r) ≤ R

eff

(a, z; r

for all a, z ∈ G.

Proof. By definition of energy, for any current i, we have

E(i; r) ≤ E(i; r

Then take the infimum and conclude by Thompson.

Corollary.

Suppose we add an edge to

which is not adjacent to

. This

increases the escape probability

(τ

< τ

Proof. We have

(τ

< τ

) =

c(a)R

eff

(a, z)

We can think of the new edge as an edge having infinite resistance in the old

graph. By decreasing it to a finite number, we decrease R

eff

Definition

(Edge cutset)

A set of edges Π is an edge-cutset separating

from

z if every path from a to z uses an edge of Π.

Theorem

(Nash–Williams inequality)

Let (Π

) be disjoint edge-cutsets sepa-

rating a from z. Then

eff

(a, z) ≥

e∈Π

c(e)

−1

The idea is that if we combine all paths in each Π

to a single path with

conductance

e∈Π

(

), then every path has to use all of these edges, so we

can bound the effective resistance.

Proof.

By Thompson, it suffices to prove that for any unit flow

from

we have

(θ(e))

r(e) ≥

e∈Π

c(e)

−1

Certainly, we have

(θ(e))

r(e) ≥

e∈Π

(θ(e))

r(e).

We now use Cauchy–Schwarz to say

e∈Π

(θ(e))

r(e)

e∈Π

c(e)

≥

e∈Π

|θ(e)|

r(e)c(e)

e∈Π

|θ(e)|

The result follows if we show that the final sum is ≥ 1.

Let

be the component of

G \

containing

. Let

be the set of all

edges that start in F and land outside F . Then we have

1 =

x∈F

div θ(x) ≤

e∈F

|θ(e)| ≤

e∈Π

|θ(e)|.

Corollary. Consider B

= [1, n]

∩ Z

. Then

eff

(a, z) ≥

log(n − 1).

There is also an upper bound of the form

eff

(

a, z

)

≤ c log n

. So this is

indeed the correct order. The proof involves constructing an explicit flow with

this energy.

Proof. Take

= {(v, u) ∈ B

: kvk

∞

= k − 1, kuk

∞

= k}.

Then

|Π

| = 2(k − 1),

and so

eff

(a, z) ≥

−1

k=1

|Π

≥

log(n − 1).

We shall need the following result:

Proposition.

Let

be an irreducible Markov chain on a finite state space. Let

be a stopping time such that

(

) = 1 and

[

]

< ∞

for some

the state space. Then

(a, x) = π(x)E

[τ].

A special case of this result was proven in IB Markov Chain, where

was

taken to be the first return time to

. The proof of this is very similar, and we

shall not repeat it.

Using this, we can prove the commute-time identity.

Theorem

(Commute time identity)

Let

be a reversible Markov chain on a

finite state space. Then for all a, b, we have

[τ

] + E

[τ

] = c(G)R

eff

(a, b),

where

c(G) = 2

c(e).

Proof.

Let

a,b

be the first time we hit

after we hit

. Then

(

a,b

) = 1.

By the proposition, we have

a,b

(a, a) = π(a)E

[τ

a,b

Since starting from

, the number of times we come back to

a,b

is the

same as up to time τ

, we get

a,b

(a, a) = G

(a, a) = c(a)R

eff

(a, b).

Combining the two, we get

π(a)E

[τ

a,b

] = c(a)R

eff

(a, b).

Thus, the result follows.

In particular, from the commute-time identity, we see that the effective

resistance satisfies the triangle inequality, and hence defines a metric on any

graph.

2.2 Infinite graphs

Finally, let’s think a bit about how we can develop the same theory for infinite

graphs.

Let

be an infinite connected weighted graph with conductances (

(

))

Let 0 be a distinguished vertex. Let (

= (

, E

))

be an exhaustion of

finite graphs, i.e.

– V

⊆ V

k+1

for all k;

– 0 ∈ V

for all k;

–

= V ;

– E

is the set of edges of E with both end points in V

Let

∗

be the graph obtained by gluing all the vertices of

V \V

into a single

point z

and setting

c(x, z

) =

z∈V \V

c(x, z)

for all

x ∈ V

. Now observe that

eff

, z

;

∗

) is a non-decreasing function of

n (Rayleigh). So the limit as n → ∞ exists. We set

eff

(0, ∞) = lim

n→∞

eff

(0, z

; G

∗).

This is independent of the choice of exhaustion by Rayleigh.

Now we have

(τ

= ∞) = lim

n→∞

(τ

< τ

) =

c(0)R

eff

(0, z

; G

∗

)

c(0)R

eff

(0, ∞)

Definition

(Flow)

Let

be an infinite graph. A flow

from 0 to

∞

is an

anti-symmetric function on the edges such that div θ(x) = 0 for all x 6= 0.

Theorem.

Let

be an infinite connected graph with conductances (

(

))

Then

(i) Random walk on G is recurrent iff R

eff

(0, ∞) = ∞.

(ii)

The random walk is transient iff there exists a unit flow

from 0 to

∞

finite energy

E(i) =

(i(e))

r(e).

Proof. The first part is immediate since

(τ

= ∞) =

c(0)R

eff

(0, ∞)

To prove the second part, let

be a unit flow from 0 to

∞

of finite energy. We

want to show that the effective resistance is finite, and it suffices to extend

Thompson’s principle to infinite graphs.

Let

be the unit current flow from 0 to

∗

. Let

(

) be the associated

potential. Then by Thompson,

eff

(0, z

; G

∗

) = E(i

Let

be the restriction of

∗

. Then this is a unit flow on

∗

from 0 to

. By Thompson, we have

E(i

) ≤ E(θ

) ≤ E(θ) < ∞.

eff

(0, ∞) = lim

n→∞

E(i

So by the first part, the flow is transient.

Conversely, if the random walk is transient, we want to construct a unit flow

from 0 to

∞

of finite energy. The idea is to define it to be the limit of (

)(

x, y

By the first part, we know

eff

, ∞

) =

lim E

(

)

< ∞

. So there exists

M >

0 such that

(

)

≤ M

for all

. Starting from 0, let

(

) be the number

of visits to

up to time

. Let

(

) be the total number of visits to

. Then

(x) % Y (x) as n → ∞ almost surely.

By monotone convergence, we get that

(x)] % E

[Y (x)] < ∞,

since the walk is transient. On the other hand, we know

(x)] = G

(0, x).

It is then easy to check that

(0,x)

c(x)

is a harmonic function outside of 0 and

with value 0 at z

. So it has to be equal to the voltage v

(x). So

(x) =

(0, x)

c(x)

Therefore there exists a function v such that

lim

n→∞

c(x)v

(x) = c(x)v(x).

We define

i(x, y) = c(x, y)(v(x) −v(y)) = lim

n→∞

c(x, y)(v

(x) − v

(y)) = lim

n→∞

(x, y).

Then by dominated convergence, we know

(

)

≤ M

, and also

is a flow from 0

to ∞.

Note that this connection with electrical networks only works for reversible

Markov chains.

Corollary. Let G

⊆ G be connected graphs.

(i) If a random walk on G is recurrent, then so is random walk on G

(ii) If random walk on G

is transient, so is random walk on G.

Theorem

(Polya’s theorem)

Random walk on

is recurrent and transient on

for d ≥ 3.

Proof sketch. For d = 2, if we glue all vertices at distance n from 0, then

eff

(0, ∞) ≥

n−1

i=1

8i − 4

≥ c · log n

using the parallel and series laws. So R

eff

(0, ∞) = ∞. So we are recurrent.

For

= 3, we can construct a flow as follows — let

be the sphere of radius

centered at the origin. Given any edge

, take the unit square centered at

the midpoint

and has normal

. We define

|θ

(

)

to be the area of the

radial projection on the sphere, with positive sign iff hm

, ei > 0.

One checks that

satisfies Kirchoff’s node law outside of 0. Then we find

that

E(θ) ≤ C





< ∞,

since there are

∼ n

edges at distance

, and the flow has magnitude

∼

Another proof sketch.

We consider a binary tree

with edges joining generation

to n + 1 having resistance ρ

for ρ to be determined. Then

eff

) =

∞

n=1





and this is finite when ρ < 2.

Now we want to embed this in

in such a way that neighbours in

of generation

and

+ 1 are separated by a path of length of order

. In

generation

, there are 2

vertices. On the other hand, the number of

vertices at distance

will be of order (

)

. So we need (

)

≥

. So

we need ρ >

√

2. We can then check that

eff

(0, ∞; Z

) ≤ c · R

eff

) < ∞.

Note that this method is rather robust. We only need to be able to embed

our

into

. Using a similar method, Grimmett, Kesten and Zhang (1993)

showed that simple random walk on a supercritical bond percolation is transient

for d ≥ 3.

3 Uniform spanning trees

3.1 Finite uniform spanning trees

The relation between uniform spanning trees and electrical networks was discov-

ered by Kirchoff in 1850’s. Of course, he was not interested in uniform spanning

tress, but in electrical networks themselves. One of the theorems we will prove is

Theorem

(Foster’s theorem)

Let

= (

V, E

) be a finite weighted graph on

vertices. Then

e∈E

eff

(e) = n − 1.

We can prove this using the commute-time formula, but there is a one-line

proof using this connection between electrical networks and uniform spanning

trees.

Definition

(Spanning tree)

Let

= (

V, E

) be a finite connected graph. A

spanning tree

is a connected subgraph of

which is a tree (i.e. there are

no cycles) and contains all the vertices in G.

Let

be the set of all spanning trees of

. Pick

T ∈ T

uniformly at random.

We call it the uniform spanning tree. We shall prove the following theorem:

Theorem. Let e 6= f ∈ E. Then

P(e ∈ T | f ∈ T ) ≤ P(e ∈ T ).

It is tempting to ask a very similar question — if we instead considered all

spanning forests, do we get the same result? Intuitively, we should, but it turns

out this is an open question. So let’s think about trees instead.

In order to prove this, we need the following result:

Theorem (Kirchoff). Let T be a uniform spanning tree, e an edge. Then

P(e ∈ T ) = R

eff

(e)

Of course, this immediately implies Foster’s theorem, since every tree has

n − 1 edges.

Notation.

Fix two vertices

s, t

. For all every edge

= (

a, b

), define

(

s, a, b, t

) to be the set of spanning tress of

whose unique path from

passes along the edge (a, b) in the direction from a to b. Write

N(s, a, b, t) = |N(s, a, b, t)|,

and N the total number of spanning trees.

Theorem. Define, for every edge e = (a, b),

i(a, b) =

N(s, a, b, t) − N(s, b, a, t)

Then

is a unit flow from

satisfying Kirchoff’s node law and the cycle law.

Note that from the expression for i, we know that

i(a, b) = P(T ∈ N(s, a, b, t)) − P(T ∈ N(s, b, a, t)).

Proof.

We first show that

is a flow from

. It is clear that

is anti-

symmetric. To check Kirchoff’s node law, pick

a 6∈ {s, t}

. We need to show

that

x∼a

i(a, x) = 0.

To show this, we count how much each spanning tree contributes to the sum. In

each spanning tree, the unique path from

may or may not contain

. If

it does not contain

, it contributes 0. If it contains

, then there is one edge

entering

and one edge leaving

, and it also contributes 0. So every spanning

tree contributes exactly zero to the sum.

So we have to prove that

satisfies the cycle law. Let

= (

, v

, . . . , v

n+1

) be a cycle. We need to show that

i=1

i(v

, v

i+1

) = 0.

To prove this, it is easier to work with “bushes” instead of trees. An

s/t

bush is

a forest that consists of exactly 2 trees,

and

, such that

s ∈ T

and

t ∈ T

Let

= (

a, b

) be an edge. Define

(

s, a, b, t

) to be the set of

s/t

bushes such

that a ∈ T

and b ∈ T

We claim that

(

s, a, b, t

)

(

s, a, b, t

). Indeed, given a bush in

(

s, a, b, t

we can add the edge

= (

a, b

) to get a spanning tree whose unique path from

to t passes through e, and vice versa.

Instead of considering the contribution of each tree to the sum, we count the

contribution of each bush to the set. Then this is easy. Let

= |{(v

, v

j+1

) : B ∈ B(s, v

, v

j+1

, t)}

−

= |{(v

, v

j+1

) : B ∈ B(s, v

j+1

, v

, t)}

Then the contribution of B is

− F

−

By staring it at long enough, since we have a cycle, we realize that we must have

= F

−

. So we are done.

Finally, we need to show that i is a unit flow. In other words,

x∼s

i(s, x) = 1.

But this is clear, since each spanning tree contributes

(

s, x

), and there are

N spanning trees.

We can now prove the theorem we wanted to prove.

Theorem. Let e 6= f ∈ E. Then

P(e ∈ T | f ∈ T ) ≤ P(e ∈ T ).

Proof.

Define the new graph

G.f

to be the graph obtained by gluing both

endpoints of

to a single vertex (keeping multiple edges if necessary). This

gives a correspondence between spanning trees of

containing

and spanning

trees of G.f. But

P(e ∈ T | f ∈ T ) =

number of spanning trees of G.f containing e

number of spanning trees of G.f

But this is just

(

e ∈ UST of G.f

), and this is just

eff

(

;

G.f

). So it suffices

to show that

eff

(e; G.f ) ≤ R

eff

(e; G).

But this is clear by Rayleigh’s monotone principle, since contracting

is the

same as setting the resistance of the edge to 0.

In practice, how can we generate a uniform spanning tree? One way to do so

is Wilson’s method.

Definition

(Loop erasure)

Let

, . . . x

be a finite path in the graph

. We define the loop erasure as follows: for any pair

i < j

such that

remove x

i+1

, x

i+2

, . . . , x

, and keep repeating until no such pairs exist.

To implement Wilson’s algorithm, distinguish a root vertex of

, called

and take an ordering of

. Set

{r}

. Define

inductively as follows: take

the first vertex in the ordering is not in

. We start a simple random walk from

this vertex, and run until it hits

, and erase the loops. Then set

i+1

to be

the union of T

with this (loop-erased) path. Repeat until all vertices are used.

Theorem (Wilson). The resulting tree is a uniform spanning tree.

Note that in particular, the choice of ordering is irrelevant to the resulting

distribution.

To prove this theorem, it is convenient to have a good model of how the

simple random walk on

is generated. Under any vertex

, place an infinite

number of cards that contain iid instructions, i.e. each card tells us to which

neighbour we jump. Different vertices have independent stacks. Whenever we

are at a vertex

, look at the top card underneath it and go to the neighbour it

instructs. Then throw away the top card and continue.

Given stacks of cards under the vertices of the graph, by revealing the top

card of each vertex, we get a directed graph, where directed edges are of the

form (x, y), where y is the instruction on the top card under x.

If there is no directed cycle, then we stop, and we have obtained a spanning

tree. If there is a directed cycle, then we remove the top cards from all vertices

on the cycle. We call this procedure cycle popping. Then we look at the top

cards again and remove cycles and cards used.

We first prove a deterministic lemma about cycle popping.

Lemma.

The order in which cycles are popped is irrelevant, in the sense that

either the popping will never stop, or the same set of cycles will be popped, thus

leaving the same spanning tree lying underneath.

Proof.

Given an edge (

x, S

), where

is the

th instruction under

, colour

(

x, S

) with colour

. A colour is now coloured, but not necessarily with the

same colour.

Suppose

is a cycle that can be popped in the order

, C

, . . . , C

, with

. Let

be any cycle in the original directed graph. We claim that

either

does not intersect

, . . . , C

, or

for some

, and

does not

intersect

, . . . C

k−1

. Indeed, if they intersect, let

x ∈ C

∩ C

, where

is the

smallest index where they intersect. Then the edge coming out of

will have

colour 1. Then

is also in the intersection of

and

, and so the same is

true for the edge coming out of

. Continuing this, we see that we must have

. So popping

, C

, . . . , C

k−1

, C

k+1

, . . . , C

gives the same result as

popping C

, . . . , C

Thus, by induction, if

is a cycle that is popped, then after performing a

finite number of pops,

is still a cycle that can be popped. So either there is

an infinite number of cycles that can be popped, so popping can never stop, or

every cycle that can be popped will be popped, thus in this case giving the same

spanning tree.

Using this, we can prove that Wilson’s method gives the correct distribution.

In Wilson’s algorithm, we pop cycles by erasing loops in the order of cycle

creation. This procedure will stop will probability 1. With this procedure, we

will reveal a finite set of coloured cycles

lying over a spanning tree. Let

be the set of all (

O, T

), where

is the set of coloured cycles lying on top of

which arise from running the random walks.

Now if we can get to (

O, T

), then we could also get to (

O, T

) for any other

spanning spanning tree

, since there is no restriction on what could be under

the stacks. So we can write

X = X

× X

where

is a certain set of finite sets of coloured cycles, and

is the set of all

spanning trees.

Define a function Ψ on the set of cycles by

Ψ(C) =

e∈C

p(e), p(e) =

c(e)

c(e

−

)

where

= (

−

, e

), and

(

−

) is the sum of the conductances of all edges with

vertex e

−

More generally, if O is a set of cycles, then we write

Ψ(O) =

C∈O

Ψ(C).

Then

P(get (O, T ) using Wilson’s algorithm) =

e∈

C∈O

C∪T )

p(e) = Ψ(O) ·Ψ(T ).

Since this probability factorizes, it follows that the distribution of

is indepen-

dent of

, and the probability of getting

is proportional to Ψ(

). So

has

the distribution of a uniform spanning tree.

Corollary

(Cayley’s formula)

The number of labeled unrooted trees on

vertices is equal to n

n−2

Proof. Exercise.

How can we generalize Wilson’s algorithm to infinite graphs? If the graph is

recurrent, then we can still use the same algorithm, and with probability one,

the algorithm terminates. If we have a transient graph, then we can still perform

the same algorithm, but it is not clear what the resulting object will be.

The Aldous–Broder algorithm is another way of generating a uniform spanning

tree. Run a random walk that visits all vertices at least once. For every vertex

other than the root, take the edge the walk crossed the first time it visited the

vertex, and keep the edge in the spanning tree. It is an exercise to prove that

this does give a uniform spanning tree. Again, this algorithm works only on a

recurrent graph. A generalization to transient graphs was found by Hutchcroft.

3.2 Infinite uniform spanning trees and forests

Since recurrent graphs are boring, let G be an infinite transient graph. Then a

“naive” way to define a uniform spanning tree is by exhaustions.

Let

be an exhaustion of

by finite graphs. Define

(where

stands

for “wired”) to be the graph

, where all of the vertices of

G \ G

are glued to

a single vertex

. The “free”

is just

considered as a subgraph. It turns

out the wired one is much easier to study.

Let

be the uniform spanning tree measure on

. Let

be a finite set

of edges B = {e

, . . . , e

}. Then for T a UST of G

, we have

(B ⊆ T ) =

k=1

µ(e

∈ T | e

∈ T for all j < k)

k=1

eff

; G

/{e

: j < k}),

where

/{e

j < k}

is the graph obtained from

by contracting the edges

: j < k}.

We want to show that

as a sequence of measures converges. So we want

to understand how

eff

(

;

/{e

j < k}

) changes when we replace

with

+ 1. By Rayleigh’s monotonicity principle, since

can be obtained from

n+1

by contracting more edges, we know the effective resistance increases when

we replace n with n + 1. So we know that

(B ⊆ T ) ≤ µ

n+1

(B ⊆ T ).

So (µ

(B ⊆ T )) is an increasing sequence. So we can define

µ(B ⊆ F) = lim

n→∞

(B ⊆ T ),

and

is our uniform forest. We can then extend the definition of

to cylinder

events

{F : B

⊆ F, B

∩ F = ∅}

with B

, B

finite sets of edges, using inclusion-exclusion:

µ(B

⊆ F, B

∩ F = ∅) =

S⊆B

µ(B

∪ S ⊆ F)(−1)

|S|

Then by commuting limits, we find that in fact

µ(B

⊆ F, B

∩ F = ∅) = lim

n→∞

⊆ T, B

∩ T = ∅).

If A is a finite union or intersection of cylinder sets of this form, then we have

µ(A) = lim

n→∞

(A).

So this gives a consistent family of measures.

By Kolmogorov’s theorem, we get a unique probability measure

supported

on the forests of

is called the wired uniform spanning forest. One can

also consider the free uniform spanning forest, where we do the same thing but

without gluing, however, this is more complicated and we will not study it.

We can adapt Wilson’s algorithm to generate uniform spanning forests. This

is called Wilson’s method rooted at infinity (BKPS, 2001).

Let

be a transient graph, and start with

∅

. Pick an ordering of the

vertices of

, x

, . . .}

. Inductively, from

, we start a simple random

walk until the first time it hits

n−1

if it does. If it doesn’t, then run indefinitely.

Call this (possibly infinite) path

. Since

is transient,

will visit every

vertex finitely many times with probability 1. So it makes sense to define the

loop erasure of P

. Call it LE(P

). We set

= F

n−1

∪ LE(P

and take

F =

[

As before, the order of V that we take does not affect the final distribution.

Proposition.

Let

be a transient graph. The wired uniform spanning forest

is the same as the spanning forest generated using Wilson’s method rooted at

infinity.

Proof.

Let

, . . . , e

be a finite set of edges. Let

(

) be the uniform spanning

tree on

. Let

be the limiting law of

(

). Look at

and generate

(

)

using Wilson’s method rooted at

. Start the random walks from

, u

, . . . , u

in this order, where (

) are all the end points of the

, . . . , e

(

could be less

than 2M if the edges share end points).

Start the first walk from

and wait until it hits

; Then start from the

next vertex and wait until it hits the previous path. We use the same infinite

path to generate all the walks, i.e. for all

, let (

(

))

k≥0

be a simple random

walk on

started from

. When considering

, we stop these walks when

they exit

, .e. if they hit

. In this way, we couple all walks together and all

the spanning trees.

Let

be the first time the

th walk hits the tree the previous

i −

1 walks

have generated in G

. Now

P(e

, . . . , e

∈ T (n)) = P





, . . . , e

∈

[

j=1

LE(X

)) : k ≤ τ





Let

be the stopping times corresponding to Wilson’s method rooted at infinity.

By induction on

, we have

→ τ

n → ∞

, and by transience, we have

LE(X

) : k ≤ τ

) → LE(X

) : k ≤ τ

). So we are done.

Theorem

(Pemantle, 1991)

The uniform spanning forest on

is a single tree

almost surely if and only if d ≤ 4.

Note that the above proposition tells us

Proposition

(Pemantle)

The uniform spanning forest is a single tree iff starting

from every vertex, a simple random walk intersects an independent loop erased

random walk infinitely many times with probability 1. Moreover, the probability

that

and

are in the same tree of the uniform spanning forest is equal to the

probability that simple random walk started from

intersects an independent

loop-erased random walk started from y.

To further simplify the theorem, we use the following theorem of Lyons, Peres

and Schramm:

Theorem

(Lyons, Peres, Schramm)

Two independent simple random walks

intersect infinitely often with probability 1 if one walks intersects the loop erasure

of the other one infinitely often with probability 1.

Using these, we can now prove the theorem we wanted. Note that proving

things about intersection, rather than collisions, tends to be higher, because any

attempts to, say, define the first intersection time would inherently introduce an

asymmetry.

We prove half of Pemantle’s theorem.

Theorem.

The uniform spanning forest is not a tree for

d ≥

5 with probability

Proof of Pemantle’s theorem.

Let

X, Y

be two independent simple random walks

in Z

. Write

I =

∞

t=0

∞

s=0

1(X

= Y

Then we have

x,y

[I] =

x−y

t+s

= 0) ≈

t=kx−yk

x−y

= 0).

It is an elementary exercise to show that

= 0) ≤

d/2

= 0) ≤

t=kx−yk

d/2−1

For d ≥ 5, for all ε > 0, we take x, y such that

x,y

[I] < ε.

Then

P(USF is connected) ≤ P

x,y

(I > 0) ≤ E

x,y

[I] < ε.

Since this is true for every ε, it follows that P(USF is connected) = 0.