2Random walks
III Percolation and Random Walks on Graphs
2.2 Infinite graphs
Finally, let’s think a bit about how we can develop the same theory for infinite
graphs.
Let
G
be an infinite connected weighted graph with conductances (
c
(
e
))
e
.
Let 0 be a distinguished vertex. Let (
G
k
= (
V
k
, E
k
))
k
be an exhaustion of
G
by
finite graphs, i.e.
– V
k
⊆ V
k+1
for all k;
– 0 ∈ V
k
for all k;
–
S
k
V
k
= V ;
– E
k
is the set of edges of E with both end points in V
k
.
Let
G
∗
n
be the graph obtained by gluing all the vertices of
V \V
n
into a single
point z
n
and setting
c(x, z
n
) =
X
z∈V \V
n
c(x, z)
for all
x ∈ V
n
. Now observe that
R
eff
(0
, z
n
;
G
∗
n
) is a non-decreasing function of
n (Rayleigh). So the limit as n → ∞ exists. We set
R
eff
(0, ∞) = lim
n→∞
R
eff
(0, z
n
; G
n
∗).
This is independent of the choice of exhaustion by Rayleigh.
Now we have
P
0
(τ
+
0
= ∞) = lim
n→∞
P
0
(τ
z
n
< τ
+
0
) =
1
c(0)R
eff
(0, z
n
; G
∗
n
)
=
1
c(0)R
eff
(0, ∞)
.
Definition
(Flow)
.
Let
G
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
G
be an infinite connected graph with conductances (
c
(
e
))
e
.
Then
(i) Random walk on G is recurrent iff R
eff
(0, ∞) = ∞.
(ii)
The random walk is transient iff there exists a unit flow
i
from 0 to
∞
of
finite energy
E(i) =
X
e
(i(e))
2
r(e).
Proof. The first part is immediate since
P
0
(τ
+
0
= ∞) =
1
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
i
n
be the unit current flow from 0 to
z
n
in
G
∗
n
. Let
v
n
(
x
) be the associated
potential. Then by Thompson,
R
eff
(0, z
n
; G
∗
n
) = E(i
n
).
Let
θ
n
be the restriction of
θ
to
G
∗
n
. Then this is a unit flow on
G
∗
n
from 0 to
z
n
. By Thompson, we have
E(i
n
) ≤ E(θ
n
) ≤ E(θ) < ∞.
So
R
eff
(0, ∞) = lim
n→∞
E(i
n
).
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 (
i
n
)(
x, y
).
By the first part, we know
R
eff
(0
, ∞
) =
lim E
(
i
n
)
< ∞
. So there exists
M >
0 such that
E
(
i
n
)
≤ M
for all
n
. Starting from 0, let
Y
n
(
x
) be the number
of visits to
x
up to time
τ
z
n
. Let
Y
(
x
) be the total number of visits to
x
. Then
Y
n
(x) % Y (x) as n → ∞ almost surely.
By monotone convergence, we get that
E
0
[Y
n
(x)] % E
0
[Y (x)] < ∞,
since the walk is transient. On the other hand, we know
E
0
[Y
n
(x)] = G
τ
z
n
(0, x).
It is then easy to check that
G
τ
z
n
(0,x)
c(x)
is a harmonic function outside of 0 and
z
n
with value 0 at z
n
. So it has to be equal to the voltage v
n
(x). So
v
n
(x) =
G
τ
z
n
(0, x)
c(x)
.
Therefore there exists a function v such that
lim
n→∞
c(x)v
n
(x) = c(x)v(x).
We define
i(x, y) = c(x, y)(v(x) − v(y)) = lim
n→∞
c(x, y)(v
n
(x) − v
n
(y)) = lim
n→∞
i
n
(x, y).
Then by dominated convergence, we know
E
(
i
)
≤ M
, and also
i
is a flow from 0
to ∞.
Note that this connection with electrical networks only works for reversible
Markov chains.
Corollary. Let G
0
⊆ G be connected graphs.
(i) If a random walk on G is recurrent, then so is random walk on G
0
.
(ii) If random walk on G
0
is transient, so is random walk on G.
Theorem
(Polya’s theorem)
.
Random walk on
Z
2
is recurrent and transient on
Z
d
for d ≥ 3.
Proof sketch. For d = 2, if we glue all vertices at distance n from 0, then
R
eff
(0, ∞) ≥
n−1
X
i=1
1
8i − 4
≥ c · log n
using the parallel and series laws. So R
eff
(0, ∞) = ∞. So we are recurrent.
For
d
= 3, we can construct a flow as follows — let
S
be the sphere of radius
1
4
centered at the origin. Given any edge
e
, take the unit square centered at
the midpoint
m
e
of
e
and has normal
e
. We define
|θ
(
e
)
|
to be the area of the
radial projection on the sphere, with positive sign iff hm
e
, ei > 0.
One checks that
θ
satisfies Kirchoff’s node law outside of 0. Then we find
that
E(θ) ≤ C
X
n
n
2
·
1
n
2
2
< ∞,
since there are
∼ n
2
edges at distance
n
, and the flow has magnitude
∼
1
n
2
.
Another proof sketch.
We consider a binary tree
T
ρ
with edges joining generation
to n + 1 having resistance ρ
n
for ρ to be determined. Then
R
eff
(T
ρ
) =
∞
X
n=1
ρ
2
n
,
and this is finite when ρ < 2.
Now we want to embed this in
Z
3
in such a way that neighbours in
T
ρ
of generation
n
and
n
+ 1 are separated by a path of length of order
ρ
n
. In
generation
n
of
T
ρ
, there are 2
n
vertices. On the other hand, the number of
vertices at distance
n
in
Z
3
will be of order (
ρ
n
)
2
. So we need (
ρ
n
)
2
≥
2
n
. So
we need ρ >
√
2. We can then check that
R
eff
(0, ∞; Z
3
) ≤ c · R
eff
(T
ρ
) < ∞.
Note that this method is rather robust. We only need to be able to embed
our
T
ρ
into
Z
3
. Using a similar method, Grimmett, Kesten and Zhang (1993)
showed that simple random walk on a supercritical bond percolation is transient
for d ≥ 3.