2Random walks
III Percolation and Random Walks on Graphs
2.1 Random walks in finite graphs
We shall consider weighted random walks on finite graphs. Let
G
= (
V, E
) be a
finite connected graph. We assign a conductances/weights to the edges (
c
(
e
))
e∈E
.
Here c is a function of the edges, so we require c(xy) = c(yx).
In the weighted random walk on
G
, the probability of going from
x
to
y
(assuming x ∼ y) is
P(x, y) =
c(x, y)
c(x)
, c(x) =
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) =
(
1
deg x
y ∼ x
0 otherwise
.
The weighted random walk is reversible with respect to
π
(
x
) =
c(x)
c
G
, where
c
G
=
P
x
c(x), because
π(x)P (x, y) =
c(x)
c
G
·
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}
if
P
(
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) =
1
c(e)
.
Naturally, we would like to talk about currents flowing through the circuit.
Definition
(Flow)
.
A flow
θ
on
G
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
a
and
z
, called the source and the sink respectively. We think of current
as entering the network through
a
and exiting through
z
. 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) =
X
y∼x
θ(x, y).
By the antisymmetry property, we have
X
x
div θ(x) =
X
x
X
y∼x
θ(x, y) =
X
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
a
to
z
is
kθk
=
div θ
(
a
).We say this is a unit flow
if kθk = 1.
Since
P
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
y
. We know that if we sum
I
(
x, y
) over all
y
, 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
x∼y
c(x, y)
c(x)
W (y) =
X
x∼y
P(x, y)W (y).
Definition
(Harmonic function)
.
Let
P
be a transition matrix on Ω. We call
h
harmonic for P at the vertex x if
h(x) =
X
y
P(x, y)h(y).
We now take this as a definition of what a voltage is.
Definition
(Voltage)
.
A voltage
W
is a function on Ω that is harmonic on
Ω \ {a, z}.
The first theorem to prove is that given any two values
W
(
a
) and
W
(
z
), we
can find a unique voltage with the prescribed values at a and z.
More generally, if
B ⊆
Ω, and
X
is a Markov chain with matrix
P
, then we
write
τ
B
= min{t ≥ 0 : X
t
∈ B},
Proposition.
Let
P
be an irreducible matrix on Ω and
B ⊆
Ω,
f
:
B → R
a
function. Then
h(x) = E
x
[f(X
τ
B
)]
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
x
[f(X
τ
B
)]
=
X
y
P(x, y)E
x
[f(X
τ
B
) | X
1
= y]
=
X
y
P(x, y)E
y
[f(X
τ
B
)]
=
X
Y
P(x, y)h(y)
So h is harmonic.
To show uniqueness, suppose
h
0
be another harmonic extension. Take
g
=
h − h
0
. Then g = 0 on B. Set
A =
x : g(x) = max
y∈Ω\B
g(y)
,
and let
x ∈ A \B
. Now since
g
(
x
) is the weighted average of its neighbours, and
g
(
y
)
≤ g
(
x
) for all neighbours
y
of
x
, it must be the case that
g
(
x
) =
g
(
y
) for
all neighbours of y.
Since we assumed
G
is connected, we can construct a path from
x
to the
boundary, where
g
vanishes. So
g
(
x
) = 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
1
, e
2
, . . . , e
n
, we have
n
X
i=1
r(e
i
)I(e
i
) = 0.
Proposition.
Let
θ
be a flow from
a
to
z
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
f
=
θ − I
. Then
f
is a flow which satisfies Kirchhoff’s node law
at all vertices and the cycle law for any cycle. We want to show that
f
= 0.
Suppose not. The we can find some e
1
such that f(e
i
) > 0. But
X
y∼x
f(x, y) = 0
for all
x
, so there must exist an edge
e
2
that
e
1
leads to such that
f
(
e
2
)
>
0.
Continuing this way, we will get a cycle of ordered edges where
f >
0, which
violates the cycle law.
Let
W
0
be a voltage with
W
0
(
a
) = 1 and
W
0
(
z
) = 0, and let
I
0
be the current
associated to W
0
. Then any other voltage W can be written as
W (x) = (W (a) − W (z))W
0
(x) + W (z).
So, noting that W
0
(a) = 1, we have
W (a) = W (x) = (W (a) − W (z))(W
0
(a) − W
0
(x)).
Thus, if I is the current associated to W , then
kIk =
X
x∼a
I(a, x) =
X
x∼a
W (a) − W (x)
r(a, x)
= (W (a) − W (z))kI
0
k.
So we know that
W (a) − W (z)
kIk
=
1
kI
0
k
,
and in particular does not depend on W .
Definition
(Effective resistance)
.
The effective resistance
R
eff
(
a, z
) of an electric
network is defined to be the ratio
R
eff
(a, z) =
W (a) − W (z)
kIk
for any voltage
W
with associated current
I
. The effective conductance is
C
eff
(a, z) = R
eff
(a, z)
−1
.
Proposition. Take a weighted random walk on G. Then
P
a
(τ
z
< τ
+
a
) =
1
c(a)R
eff
(a, z)
,
where τ
+
a
= min{t ≥ 1 : X
t
= a}.
Proof. Let
f(x) = P
x
(τ
z
< τ
a
).
Then
f
(
a
) = 0 and
f
(
z
) = 1. Moreover,
f
is harmonic on Ω
\ {a, z}
. Let
W
be
a voltage. By uniqueness, we know
f(x) =
W (a) − W (x)
W (a) − W (z)
.
So we know
P
a
(τ
z
< τ
+
a
) =
X
x∼a
P(a, x)f(x)
=
X
x∼a
c(a, x)
c(a)
W (a) − W (x)
W (a) − W (z)
=
1
c(a)(W (a) − W (z))
X
x∼a
I(a, x)
=
kIk
c(a)(W (a) − W (z))
=
1
c(a)R
eff
(a, z)
.
Definition
(Green kernel)
.
Let
τ
be a stopping time. We define the Green
kernel to be
G
τ
(a, x) = E
a
"
∞
X
t=0
1(X
t
= 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
G
τ
z
(a, a) = c(a)R
eff
(a, z).
Proof.
By the Markov property, the number of visits to
a
starting from
a
until
τ
z
is the geometric distribution Geo(P
a
(τ
z
< τ
+
a
)). So
G
τ
z
(a, a) =
1
P
a
(τ
z
< τ
+
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
1
c
2
=
c
1
+ c
2
Thus, if
e
1
and
e
2
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
1
, e
2
, and we check that Kirchhoff’s and Ohm’s
law are satisfied with
I(e) = I(e
1
) + I(e
2
).
Similarly, resistances in series add. Let
v
be a node of degree 2 and let
v
1
and
v
2
be its 2 neighbours. Then we can replace these 2 edges by a single edge of
resistance
r
1
+
r
2
. Again, to justify this, we check Kirchoff’s and Ohm’s law with
I(v
1
v
2
) = I(v
1
v) + I(vv
2
).
r
1
r
2
v
1
v v
2
=
r
1
+ r
2
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
T
be a finite connected tree, and
a, z
two vertices. Then
R
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
2
R. For any flow, we define
Definition
(Energy)
.
Let
θ
be a flow on
G
with conductances (
c
(
e
)). Then the
energy is
E(θ) =
X
e
(θ(e))
2
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
G
be a finite connected graph with
conductances (c(e)). Then for any a, z, we have
R
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
i
be the unit current flow associated to potential
ϕ
. Let
j
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) =
X
e
(i(e) + k(e))
2
r(e) = E(i) + E(k) + 2
X
e
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
X
e
i(e)k(e)r(e) =
1
2
X
x
X
y∼x
(ϕ(x) − ϕ(y))k(x, y)
=
1
2
X
x
X
y∼x
ϕ(x)k(x, y) +
1
2
X
x
X
y∼x
ϕ(x)k(x, y).
Now note that
P
y∼x
k
(
x, y
) = 0 for any
x
since
k
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
G
be a finite connected
graph and (
r
(
e
))
e
and (
r
0
(
e
))
e
two sets of resistances on the edges such that
r(e) ≤ r
0
(e) for all e. Then
R
eff
(a, z; r) ≤ R
eff
(a, z; r
0
).
for all a, z ∈ G.
Proof. By definition of energy, for any current i, we have
E(i; r) ≤ E(i; r
0
).
Then take the infimum and conclude by Thompson.
Corollary.
Suppose we add an edge to
G
which is not adjacent to
a
. This
increases the escape probability
P
a
(τ
z
< τ
+
a
).
Proof. We have
P
a
(τ
z
< τ
+
z
) =
1
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
a
from
z if every path from a to z uses an edge of Π.
Theorem
(Nash–Williams inequality)
.
Let (Π
k
) be disjoint edge-cutsets sepa-
rating a from z. Then
R
eff
(a, z) ≥
X
k
X
e∈Π
k
c(e)
!
−1
.
The idea is that if we combine all paths in each Π
k
to a single path with
conductance
P
e∈Π
k
c
(
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
a
to
z
,
we have
X
e
(θ(e))
2
r(e) ≥
X
k
X
e∈Π
k
c(e)
!
−1
.
Certainly, we have
X
e
(θ(e))
2
r(e) ≥
X
k
X
e∈Π
k
(θ(e))
2
r(e).
We now use Cauchy–Schwarz to say
X
e∈Π
k
(θ(e))
2
r(e)
!
X
e∈Π
k
c(e)
!
≥
X
e∈Π
k
|θ(e)|
p
r(e)c(e)
!
2
=
X
e∈Π
k
|θ(e)|
!
2
.
The result follows if we show that the final sum is ≥ 1.
Let
F
be the component of
G \
Π
k
containing
a
. Let
F
0
be the set of all
edges that start in F and land outside F . Then we have
1 =
X
x∈F
div θ(x) ≤
X
e∈F
0
|θ(e)| ≤
X
e∈Π
k
|θ(e)|.
Corollary. Consider B
n
= [1, n]
2
∩ Z
2
. Then
R
eff
(a, z) ≥
1
2
log(n − 1).
There is also an upper bound of the form
R
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
Π
k
= {(v, u) ∈ B
n
: kvk
∞
= k −1, kuk
∞
= k}.
Then
|Π
k
| = 2(k − 1),
and so
R
eff
(a, z) ≥
−1
X
k=1
1
|Π
k
|
≥
1
2
log(n − 1).
We shall need the following result:
Proposition.
Let
X
be an irreducible Markov chain on a finite state space. Let
τ
be a stopping time such that
P
a
(
X
τ
=
a
) = 1 and
E
a
[
τ
]
< ∞
for some
a
in
the state space. Then
G
τ
(a, x) = π(x)E
a
[τ].
A special case of this result was proven in IB Markov Chain, where
τ
was
taken to be the first return time to
a
. 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
X
be a reversible Markov chain on a
finite state space. Then for all a, b, we have
E
a
[τ
b
] + E
b
[τ
a
] = c(G)R
eff
(a, b),
where
c(G) = 2
X
e
c(e).
Proof.
Let
τ
a,b
be the first time we hit
a
after we hit
b
. Then
P
a
(
X
τ
a,b
=
a
) = 1.
By the proposition, we have
G
τ
a,b
(a, a) = π(a)E
a
[τ
a,b
].
Since starting from
a
, the number of times we come back to
A
by
τ
a,b
is the
same as up to time τ
b
, we get
G
τ
a,b
(a, a) = G
τ
b
(a, a) = c(a)R
eff
(a, b).
Combining the two, we get
π(a)E
a
[τ
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.