Random walks on disordered media and their scaling limits

(1)

Random walks on disordered media and their scaling limits

Takashi Kumagai ^⇤ Department of Mathematics Kyoto University, Kyoto 606-8502, Japan

Email: kumagai@math.kyoto-u.ac.jp (June 27, 2010)

(Version for St. Flour Lectures)

Abstract

The main theme of these lectures is to analyze heat conduction on disordered media such as fractals and percolation clusters using both probabilistic and analytic methods, and to study the scaling limits of Markov chains on the media.

The problem of random walk on a percolation cluster ‘the ant in the labyrinth’ has received much attention both in the physics and the mathematics literature. In 1986, H. Kesten showed an anomalous behavior of a random walk on a percolation cluster at critical probability for trees and forZ². (To be precise, the critical percolation cluster is finite, so the random walk is considered on an incipient infinite cluster (IIC), namely a critical percolation cluster conditioned to be infinite.) Partly motivated by this work, analysis and di↵usion processes on fractals have been developed since the late eighties. As a result, various new methods have been produced to estimate heat kernels on disordered media, and these turn out to be useful to establish quenched estimates on random media. Recently, it has been proved that random walks on IICs are sub-di↵usive onZ^d whendis high enough, on trees, and on the spread-out oriented percolation ford >6.

Throughout the lectures, I will survey the above mentioned developments in a compact way.

In the first part of the lectures, I will summarize some classical and non-classical estimates for heat kernels, and discuss stability of the estimates under perturbations of operators and spaces.

Here Nash inequalities and equivalent inequalities will play a central role. In the latter part of the lectures, I will give various examples of disordered media and obtain heat kernel estimates for Markov chains on them. In some models, I will also discuss scaling limits of the Markov chains.

Examples of disordered media include fractals, percolation clusters, random conductance models and random graphs.

⇤Research partially supported by the Grant-in-Aid for Scientific Research (B) 22340017.

(2)

0 Plan of the lectures and remark

A rough plan of lectures at St. Flour is as follows.

Lecture 1–3: In the first lecture, I will discuss general potential theory for symmetric Markov chains on weighted graphs (Section 1). Then I will show various equivalent conditions for the heat kernel upper bounds (the Nash inequality (Section 2)). In the third lecture, I will use e↵ective resistance to estimate Green functions, exit times from balls etc.. On-diagonal heat kernel bounds are also obtained using the e↵ective resistance (Section 3).

Lecture 4–6¹₂: I will discuss random walk on an incipient infinite cluster (IIC) for a critical percolation. I will give some sufficient condition for the sharp on-diagonal heat kernel bounds for random walk on random graphs (Section 4). I then prove the Alexander-Orbach conjecture for IICs when two-point functions behave nicely, especially for IICs of high dimensional critical bond percolations on Z^d (Section 5). I also discuss heat kernel bounds and scaling limits on related random models (Section 6).

Lecture 6¹₂–8: The last 2 (and half) lectures will be devoted to the quenched invariance principle for the random conductance model onZ^d(Section 7). Put i.i.d. conductanceµe on each bond inZ^d and consider the Markov chain associated with the (random) weighted graph. I consider two cases, namely 0 µ_e c P-a.e. and c µ_e <1 P-a.e.. Although the behavior of heat kernels are quite di↵erent, for both cases the scaling limit is Brownian motion in general. I will discuss some technical details about correctors of the Markov chains, which play a key role to prove the invariance principle.

This is the version for St. Flour Lectures. There are several ingredients (which I was planning to include) missing in this version. Especially, I could not explain enough about techniques on heat kernel estimates; for example o↵-diagonal heat kernel estimates, isoperimetric profiles, relations to Harnack inequalities etc. are either missing or mentioned only briefly. (Because of that, I could not give proof to most of the heat kernel estimates in Section 7.) This was because I was much busier than I had expected while preparing for the lectures. However, even if I could have included them, most likely there was not enough time to discuss them during the 8 lectures. Anyway, my plan is to revise these notes and include the missing ingredients in the version for publication from Springer.

I referred many papers and books during the preparation of the lecture notes. Especially, I owe a lot to the lecture notes by Barlow [10] and by Coulhon [40] for Section 1–2. Section 3–4 (and part of Section 6) are mainly from [18, 87]. Section 5 is mainly from the beautiful paper by Kozma and Nachmias [86] (with some simplification in [101]). In Section 7, I follow the arguments of the papers by Barlow, Biskup, Deuschel, Mathieu and their co-authors [16, 30, 31, 32, 90, 91].

(4)

1 Weighted graphs and the associated Markov chains

In this section, we discuss general potential theory for symmetric (reversible) Markov chains on weighted graphs. Note that there are many nice books and lecture notes that treat potential theory and/or Markov chains on graphs, for example [6, 10, 51, 59, 88, 107, 109]. While writing this section, we are largely influenced by the lecture notes by Barlow [10].

1.1 Weighted graphs

Let X be a finite or countably infinite set, and E is a subset of {{x, y}:x, y2X, x6=y}. A graph is a pair (X, E). For x, y2 X, we write x ⇠y if{x, y} 2E. A sequence x₀, x₂,· · · , x_n is called a path with lengthnifx_i 2X fori= 0,1,2,· · · , nandx_j ⇠x_j+1 forj= 0,1,2,· · ·, n 1. Forx6=y, define d(x, y) to be the length of the shortest path from x to y. If there is no such path, we set d(x, y) =1 and we setd(x, x) = 0. d(·,·) is a metric on X and it is called a graph distance. (X, E) is connected if d(x, y) <1 for all x, y 2X, and it is locally finite if ]{y :{x, y} 2E}< 1 for all x 2 X. Throughout the lectures, we will consider connected locally finite graphs (except when we consider the trace of them in Subsection 1.3).

Assume that the graph (X, E) is endowed with a weight (conductance)µ_xy, which is a symmetric nonnegative function on X⇥X such that µ_xy > 0 if and only if x ⇠ y. We call the pair (X, µ) a weighted graph.

Letµ_x =µ(x) =P

y2Xµ_xy and define a measureµonX by settingµ(A) =P

x2Aµ_x forA⇢X.

Also, we define B(x, r) ={y 2X:d(x, y)< r}for each x2X and r 1.

Definition 1.1 We say that (X, µ) has controlled weights (or (X, µ) satisfies p0-condition) if there exists p₀ >0 such that

µ_xy µx

p₀ 8x⇠y.

If (X, µ) has controlled weights, then clearly]{y2X :x⇠y} p₀¹.

Once the weighted graph (X, µ) is given, we can define the corresponding quadratic form, Markov chain and the discrete Laplace operator.

Quadratic form We define a quadratic form on (X, µ) as follows.

H²(X, µ) =H² = {f :X !R:E(f, f) = 1 2

X

x,y2X x⇠y

(f(x) f(y))²µ_xy <1},

E(f, g) = 1 2

X

x,y2X x⇠y

(f(x) f(y))(g(x) g(y))µ_xy 8f, g2H².

Physically,E(f, f) is the energy of the electrical network for an (electric) potentialf.

Since the graph is connected, one can easily see that E(f, f) = 0 if and only if f is a constant function. We fix a base point 02X and define

kfk²_H² =E(f, f) +f(0)² 8f 2H².

(5)

Note that

E(f, f) = 1 2

X

x⇠y

(f(x) f(y))²µ_xy X

x

X

y

(f(x)²+f(y)²)µxy = 2kfk²2 8f 2L², (1.1) wherekfk2 is the L²-norm of f. So L² ⇢H². We give basic facts in the next lemma.

Lemma 1.2 (i) Convergence in H² implies the pointwise convergence.

(ii) H² is a Hilbert space.

Proof. (i) Suppose fn!f inH² and let gn =fn f. ThenE(gn, gn) +gn(0)² ! 0 so gn(0)!0.

For any x 2 X, there is a sequence {x_i}^li=0 ⇢ X such that x₀ = 0, x_l = x and x_i ⇠ x_i+1 for i= 0,1,· · ·, l 1. Then

|g_n(x) g_n(0)|² l

l 1

X

i=0

|g_n(x_i) g_n(x_i+1)|² 2l(min^l ¹

i=0 µ_x_i_x_i+1) ¹E(g_n, g_n)!0 (1.2) asn! 1so we have g_n(x)!0.

(ii) Assume that {fn}n⇢H² is a Cauchy sequence in H². Thenfn(0) is a Cauchy sequence inRso converges. Thus, similarly to (1.2) f_n converges pointwise tof, say. Now using Fatou’s lemma, we have kf_n fk²_H² lim infmkf_n f_mk²_H², so thatkf_n fk²_H² !0.

Markov chain Let Y ={Yn}be a Markov chain on X whose transition probabilities are given by P(Yn+1 =y|Yn=x) = µ_xy

µ_x =:P(x, y) 8x, y2X.

We writeP^xwhen the initial distribution ofY is concentrated onx(i.e. Y₀=x,P-a.s.). (P(x, y))x,y2X

is the transition matrix for Y. Y is called a simple random walk when µ_xy = 1 whenever x⇠y. Y is µ-symmetric since for each x, y2X,

µxP(x, y) =µxy =µyx=µyP(y, x).

We define the heat kernelofY by

p_n(x, y) =P^x(Yn=y)/µy 8x, y2X.

Using the Markov property, we can easily show the Chapman-Kolmogorov equation:

p_n+m(x, y) =X

z

p_n(x, z)p_m(z, y)µ_z, 8x, y2X. (1.3) Using this and the factp₁(x, y) =µ_xy/(µxµ_y) =p₁(y, x), one can verify the following inductively

p_n(x, y) =p_n(y, x), 8x, y2X.

(6)

For n 1, let

Pnf(x) =X

y

pn(x, y)f(y)µy =X

y

P^x(Yn=y)f(y) =E^x[f(Yn)], 8f :X!R.

We sometimes consider a continuous time Markov chain {Yt}t 0 w.r.t. µ which is defined as follows: each particle stays at a point, say x for (independent) exponential time with parameter 1, and then jumps to another point, sayywith probability P(x, y). The heat kernel for the continuous time Markov chain can be expressed as follows.

p_t(x, y) =P^x(Yt=y)/µy =X¹

n=0

e ^ttⁿ

n!p_n(x, y), 8x, y2X.

Discrete Laplace operator Forf :X!R, the discrete Laplace operator is defined by Lf(x) =X

y

P(x, y)f(y) f(x) = 1 µ_x

X

y

(f(y) f(x))µ_xy =E^x[f(Y₁)] f(x) = (P₁ I)f(x). (1.4) Note that according to the Ohm’s law ‘I =V /R’, P

y(f(y) f(x))µ_xy is the total flux flowing into x, given the potentialf.

Definition 1.3 Let A⇢X. A function f :X!R is harmonic on A if Lf(x) = 0, 8x2A.

h is sub-harmonic (resp. super-harmonic) on A if Lf(x) 0 (resp. Lf(x)0) for x2A.

Lf(x) = 0 means that the total flux flowing into x is 0 for the given a potential f. This is the behavior of the currents in a network called Kircho↵’s (first) law.

ForA⇢X, we define the (exterior) boundary ofA by

@A={x2A^c :9z2A such thatz⇠x}.

Proposition 1.4 (Maximum principle) Let A be a connected subset of X and h :A[@A! R be sub-harmonic on A. If the maximum ofhoverA[@Ais attained inA, thenhis constant on A[@A.

Proof. Let x₀ 2A be the point where h attains the maximum and let H ={z2 A[@A:h(z) = h(x0)}. Ify2H\A, then sinceh(y) h(x) for all x2A[@A, we have

0µ_yLh(y) =X

y

(h(x) h(y))µxy 0.

Thus,h(x) =h(y) (i.e. x2H) for allx⇠y. SinceA is connected, this implies H=A[@A.

We can prove the minimum principle for a super-harmonic functionh by applying the maximum principle to h.

Forf, g2L², denote their L²-inner product as (f, g), namely (f, g) =P

xf(x)g(x)µx.

(7)

Lemma 1.5 (i) L:H² !L² andkLfk²22kfk²_H2. (ii) For f 2H² andg2L², we have ( Lf, g) =E(f, g).

(iii) L is a self-adjoint operator onL²(X, µ) and the following holds:

( Lf, g) = (f, Lg) =E(f, g), 8f, g2L². (1.5) Proof. (i) Using Schwarz’s inequality, we have

kLfk²2 = X

x

1 µ_x(X

y

(f(y) f(x))µxy)²

 X

x

1 µx(X

y

(f(y) f(x))²µxy)(X

y

µxy) = 2E(f, f)2kfk²_H². (ii) Using (i), both sides of the equality are well-defined. Further, using Schwarz’s inequality,

X

x,y

|µ_xy(f(y) f(x))g(x)| (X

x,y

µ_xy(f(y) f(x))²)^1/2(X

x,y

µ_xyg(y)²)^1/2 =E(f, f)^1/2kgk2 <1. So we can use Fubini’s theorem, and we have

( Lf, g) = X

x

(X

y

µxy(f(y) f(x)))g(x) = 1 2

X

x

X

y

µxy(f(y) f(x))(g(y) g(x)) =E(f, g).

(iii) We can prove (f, Lg) =E(f, g) similarly and obtain (1.5).

(1.5) is the discrete Gauss-Green formula.

Lemma 1.6 Set p^x_n(·) =p_n(x,·). Then, the following hold for all x, y2X.

pn+m(x, y) = (p^x_n, p^y_m), P1p^x_n(y) =pn+1(x, y), (1.6) Lp^x_n(y) =p_n+1(x, y) p_n(x, y), E(p^x_n, p^y_m) =p_n+m(x, y) p_n+m+1(x, y), (1.7) p_2n(x, y)p

p_2n(x, x)p2n(y, y). (1.8)

Proof. The two equations in (1.6) are due to the Chapman-Kolmogorov equation (1.3). The first equation in (1.7) is then clear sinceL=P1 I. The last equation can be obtained by these equations and (1.5). Using (1.6) and the Schwarz inequality, we have

p2n(x, y)² = (p^x_n, p^y_n)² (p^x_n, p^x_n)(p^y_n, p^y_n) =p2n(x, x)p2n(y, y), which gives (1.8).

It can be easily shown that (E,L²) is a regular Dirichlet form on L²(X, µ) (c.f. [55]). Then the corresponding Hunt process is the continuous time Markov chain {Y_t}t 0 w.r.t. µ and the corresponding self-adjoint operator onL² isL in (1.4).

(8)

Remark 1.7 Note that {Yt}t 0 has the transition probability P(x, y) = µxy/µx and it waits at x for an exponential time with mean 1 for each x 2 X. Since the ‘speed’ of {Y_t}t 0 is independent of the location, it is sometimes called constant speed random walk (CSRW for short). We can also consider a continuous time Markov chain with the same transition probability P(x, y) and wait at x for an exponential time with mean µ_x¹ for each x2X. This Markov chain is called variable speed random walk (VSRW for short). We will discuss VSRW in Section 7. The corresponding discrete Laplace operator is

LVf(x) =X

y

(f(y) f(x))µxy. (1.9)

For each f, g that have finite support, we have

E(f, g) = (LVf, g)⌫ = (LCf, g)µ,

where ⌫ is a measure on X such that ⌫(A) =|A| for all A⇢ X. So VSRW is the Markov process associated with the Dirichlet form (E,F) on L²(X,⌫) and CSRW is the Markov process associated with the Dirichlet form (E,F) on L²(X, µ). VSRW is a time changed process of CSRW and vice versa.

We now introduce the notion of rough isometry.

Definition 1.8 Let (X₁, µ₁),(X₂, µ₂) be weighted graphs that have controlled weights.

(i) A map T :X₁ !X₂ is called a rough isometry if the following holds.

There exist constants c₁, c₂, c₃ >0 such that

c₁¹d₁(x, y) c₂ d₂(T(x), T(y))c₁d₁(x, y) +c₂ 8x, y2X₁, (1.10) d₂(T(X₁), y⁰)c₂ 8y⁰ 2X₂, (1.11) c₃¹µ₁(x)µ₂(T(x))cµ₁(x) 8x2X₁, (1.12) where d_i(·,·) is the the graph distance of (Xi, µ_i), for i= 1,2.

(ii) (X₁, µ₁),(X₂, µ₂) are said to be rough isometric if there is a rough isometry between them.

It is easy to see that rough isometry is an equivalence relation. One can easily prove that Z² and the triangular lattice, the hexagon lattice are all roughly isometric. It can be proved that Z¹ andZ² are not roughly isometric.

The notion of rough isometry was first introduced by M. Kanai ([73, 74]). As this work was mainly concerned with Riemannian manifolds, definition of rough isometry included only (1.10), (1.11).

The definition equivalent to Definition 1.8 is given in [42] (see also [65]). Note that rough isometry corresponds to quasi-isometry in the field of geometric group theory.

While discussing various properties of Markov chains/Laplace operators, it is important to think about their ‘stability’. In the following, we introduce two types of stability.

Definition 1.9 (i) We say a property is stable under bounded perturbation if whenever (X, µ) satisfies the property and (X, µ⁰) satisfies c ¹µ_xy µ⁰_xy  cµ_xy for all x, y 2 X, then (X, µ⁰) satisfies

(9)

the property.

(ii) We say a property is stable under rough isometry if whenever (X, µ) satisfies the property and (X⁰, µ⁰) is rough isometric to (X, µ), then (X⁰, µ⁰) satisfies the property.

If a propertyP is stable under rough isometry, then it is clearly stable under bounded perturbation.

It is known that the following properties of weighted graphs are stable under rough isometry.

(i) Transience and recurrence

(ii) The Nash inequality, i.e. p_n(x, y)c₁n ^↵ for all n 1, x2X (for some↵ >0) (iii) Parabolic Harnack inequality

We will see (i) later in this section and (ii) in Section 2. One of the important open problem is to show if the elliptic Harnack inequality is stable under these perturbations or not.

Definition 1.10 (X, µ) has the Liouville property if there is no bounded non-constant harmonic functions. (X, µ) has the strong Liouville property if there is no positive non-constant harmonic functions.

It is known that both Liouville and strong Liouville properties are not stable under bounded perturbation (see [89]).

1.2 Harmonic functions and e↵ective resistances For A⇢X, define

A= inf{n 0 :Y_n2A}, ⁺_A= inf{n >0 :Y_n2A}, ⌧_A= inf{n 0 :Y_n2/A}. ForA⇢X and f :A!R, consider the followingDirichlet problem.

( Lv(x) = 0 8x2A^c,

v|A=f. (1.13)

Proposition 1.11 Assume thatf :A!R is bounded and set '(x) =E^x[f(Y _A) : A<1].

(i) ' is a solution of (1.13).

(ii) If P^x( A<1) = 1 for allx2X, then 'is the unique solution of (1.13).

Proof. (i) '|A=f is clear. Forx2A^c, using the Markov property ofY, we have '(x) =X

y

P(x, y)'(y),

(10)

soL'(x) = 0.

(ii) Let '⁰ be another solution and let H_n='(Y_n) '⁰(Y_n). Then H_n is a bounded martingale up to A, so using the optional stopping theorem, we have

'(x) '⁰(x) =E^xH₀ =E^xH _A =E^x['(Y _A) '⁰(Y _A)] = 0 since _A<1a.s. and '(x) ='⁰(x) forx2A.

Remark 1.12 (i) In particular, we see that 'is the unique solution of (1.13) whenA^c is finite. In this case, here is another proof of the uniqueness of the solution of (1.13): let u(x) ='(x) '⁰(x), then u|A = 0 and Lu(x) = 0 for x 2 A^c. So, noting u 2 L² and using Lemma 1.5, E(u, u) = ( Lu, u) = 0 which implies thatu is constant on X (so it is 0 since u|A= 0).

(ii) If hA(x) := P^x( A = 1) >0 for some x 2X, then the function '+ hA is also a solution of (1.13) for all 2R, so the uniqueness of the Dirichlet problem fails.

ForA, B⇢X such thatA\B=;, define

R_e↵(A, B) ¹= inf{E(f, f) :f 2H², f|A= 1, f|B = 0}. (1.14) (We defineR_e↵(A, B) =1when the right hand side is 0.) We callR_e↵(A, B) thee↵ective resistance betweenAandB. It is easy to see thatR_e↵(A, B) =R_e↵(B, A). IfA⇢A⁰,B ⇢B⁰withA⁰\B⁰ =;, thenR_e↵(A⁰, B⁰)R_e↵(A, B).

Take a bond e={x, y}, x⇠ y in a weighted graph (X, µ). We say cutting the bond ewhen we take the conductance µ_xy to be 0, and we say shorting the bond ewhen we identify x=y and take the conductanceµxy to be 1. Clearly, shorting decreases the e↵ective resistance (shorting law), and cutting increases the e↵ective resistance (cutting law).

The following proposition shows that among feasible potentials whose voltage is 1 onAand 0 on B, it is a harmonic function on (A[B)^c that minimizes the energy.

Proposition 1.13 (i) The right hand side of (1.14) is attained by a unique minimizer'.

(ii) ' in (1) is a solution of the following Dirichlet problem ( L'(x) = 0 8x2X\(A[B),

'|A= 1, '|B = 0. (1.15)

Proof. (i) We fix a based point x₀ 2 B and recall that H² is a Hilbert space with kfkH² = E(f, f) +f(x₀)² (Lemma 1.2 (ii)). Since V :={f 2H²:f|A= 1, f|B= 0}is a closed convex subset of H², a general theorem shows that V has a unique minimizer fork · kH² (which is equal to E(·,·) on V).

(ii) Letg be a function onX whose support is finite and is contained inX\(A[B). Then, for any 2R,'+ g2 V, so E('+ g,' + g) E(','). ThusE(', g) = 0. Applying Lemma 1.5(ii), we have (L', g) = 0. For eachx2X\(A[B), by choosingg(z) = x(z), we obtainL'(x)µx= 0.

(11)

As we mentioned in Remark 1.12 (ii), we do not have uniqueness of the Dirichlet problem in general. So in the following of this section, we will assume that A^c is finite in order to guarantee uniqueness of the Dirichlet problem.

The next theorem gives a probabilistic interpretation of the e↵ective resistance.

Theorem 1.14 If A^c is finite, then for each x02A^c,

R_e↵(x0, A) ¹=µ_x₀P^x⁰( A< _x⁺₀). (1.16) Proof. Let v(x) =P^x( _A < _x₀). Then, by Proposition 1.11, v is the unique solution of Dirichlet problem withv(x0) = 0, v|A= 1. By Proposition 1.13 and Lemma 1.5 (noting that 1 v2L²),

R_e↵(x0, A) ¹=E(v, v) =E( v,1 v) = (Lv,1 v) =Lv(x0)µx0 =E^x⁰[v(Y1)]µx0. By definition ofv, one can seeE^x⁰[v(Y₁)] =P^x⁰( _A< _x⁺₀) so the result follows.

Similarly, if A^c is finite one can prove

R_e↵(B, A) ¹= X

x2B

µ_xP^x( A< ⁺_B).

Note that by Ohm’s law, the right hand side of (1.16) is the current flowing fromx0 toA^c. The following lemma is useful and will be used later in Proposition 3.18.

Lemma 1.15 Let A, B⇢X and assume that both A^c, B^c are finite. Then the following holds.

R_e↵(x, A[B)

R_e↵(x, A) ¹ R_e↵(x, B) ¹ P^x( A< _B) R_e↵(x, A[B)

R_e↵(x, A) , 8x /2A[B.

Proof. Using the strong Markov property, we have

P^x( A< B) = P^x( A< B, A[B < _x⁺) +P^x( A< B, A[B> ⁺_x)

= P^x( A< _B, _A_[_B < _x⁺) +P^x( A[B> ⁺_x)P^x( A< _B).

So

P^x( _A< _B) = P^x( _A< _B, _A[B < ⁺_x)

P^x( A[B< _x⁺)  P^x( _A< ⁺_x) P^x( A[B < _x⁺). Using (1.16), the upper bound is obtained. For the lower bound,

P^x( A< B, A[B< ⁺_x) P^x( A< _x⁺< B) P^x( A< ⁺_x) P^x( B< _x⁺), so using (1.16) again, the proof is complete.

As we see in the proof, we only need to assume thatA^c is finite for the upper bound.

(12)

Now let (X, µ) be an infinite weighted graph. Let{An}¹n=1be a family of finite sets such thatAn⇢ A_n+1 forn2Nand [n 1A_n=X. Letx₀2A₁. By the short law,R_e↵(x₀, A^c_n)R_e↵(x₀, A^c_n+1), so the following limit exists.

R_e↵(x0) := lim

n!1R_e↵(x0, A^c_n). (1.17)

Further, the limit R_e↵(x₀) is independent of the choice of the sequence {A_n} mentioned above.

(Indeed, if {B_n} is another such family, then for each n there exists N_n such that A_n ⇢ B_N_n, so limn!1R_e↵(x0, A^c_n)  limn!1R_e↵(x0, B_n^c). By changing the role of An and Bn, we have the opposite inequality.)

Theorem 1.16 Let (X, µ) be an infinite weighted graph. For each x2X, the following holds P^x( _x⁺=1) = (µxRe↵(x)) ¹.

Proof. By Theorem 1.14, we have

P^x( A^c_n< _x⁺) = (µxR_e↵(x, A^c_n) ¹) ¹. Taking n! 1 and using (1.17), we have the desired equality.

Definition 1.17 We say a Markov chain is recurrent at x 2 X if P^x( _x⁺ = 1) = 0. We say a Markov chain is transient at x2X if P^x( _x⁺=1)>0.

The following is well-known for irreducible Markov chains (so in particular it holds for Markov chains corresponding to weighted graphs). See, for example [97].

Proposition 1.18 (1) {Y_n}n is recurrent at x 2 X if and only if m := P₁

n=0P^x(Y_n = x) = 1. Further, m ¹=P^x( _x⁺=1).

(2) If {Y_n}n is recurrent (resp. transient) at some x2X, then it is recurrent (resp. transient) for all x2X.

(3) {Y_n}n is recurrent if and only if P^x({Y hitsy infinitely often}) = 1 for all x, y 2X. {Y_n}n is transient if and only if P^x({Y hits y finitely often}) = 1 for allx, y2X.

From Theorem 1.16 and Proposition 1.18, we have the following.

{Y_n} is transient (resp. recurrent) , R_e↵(x)<1 (resp. R_e↵(x) =1),9x2X (1.18) , R_e↵(x)<1 (resp. R_e↵(x) =1),8x2X.

Example 1.19 Consider Z² with weight 1 on each nearest neighbor bond. Let@B_n={(x, y)2Z²: either |x|or |y| isn}. By shorting @Bn for alln2N, one can obtain

R_e↵(0) X¹

n=0

1

4(2n+ 1) =1. So the simple random walk on Z² is recurrent.

(13)

Let us recall the following fact.

Theorem 1.20 (P´olya 1921) Simple random walk on Z^d is recurrent if d = 1,2 and transient if d 3.

The combinatorial proof of this theorem is well-known. For example, ford= 1, by counting the total number of paths of length 2nthat moves both right and left ntimes,

P⁰(Y2n= 0) = 2 ²ⁿ 2n n

!

= (2n)!

2²ⁿn!n! ⇠(⇡n) ^1/2, where Stirling’s formula is used in the end. Thus

m=X¹

n=0

P⁰(Y_n= 0)⇠ X1 n=1

(⇡n) ^1/2+ 1 =1, so{Y_n} is recurrent.

This argument is not robust. For example, if one changes the weight onZ^d so that c₁ µ_xy  c₂ for x ⇠ y, one cannot apply the argument at all. The advantage of the characterization of transience/recurrence using the e↵ective resistance is that one can make a robust argument. Indeed, by (1.18) we can see that transience/recurrence is stable under bounded perturbation. This is because, if c₁µ⁰_xy  µ_xy  c₂µ⁰_xy for all x, y 2 X, then c₁R_e↵(x)  R⁰_e↵(x)  c₂R_e↵(x). We can further prove that transience/recurrence is stable under rough isometry.

Finally in this subsection, we will give more equivalence condition for the transience and discuss some decomposition of H². Let H₀² be the closure of C₀(X) in H², where C₀(X) is the space of compactly supported function on X. For a finite set B⇢X, define the capacity of B by

Cap (B) = inf{E(f, f) :f 2H₀², f|B = 1}. We first give a lemma.

Lemma 1.21 If a sequence of non-negative functionsvn 2H², n2N satisfies limn!1vn(x) = 1 for all x2X and lim_n!1E(v_n, v_n) = 0, then

nlim!1ku (u^v_n)kH² = 0, 8u2H², u 0.

Proof. Let u_n = u^v_n and define U_n = {x 2 X : u(x) > v_n(x)}. By the assumption, for each N 2 N, there exists N0 = N0(N) such that Un ⇢ B(0, N)^c for all n N0. For A ⇢ X, denote EA(u) = ¹₂P

x,y2A(u(x) u(y))²µ_xy. Since EU_n^c(u u_n) = 0, we have E(u u_n, u u_n)  2·1

2 X

x2Un

X

y:y⇠x

⇣u(x) u_n(x) (u(y) u_n(y))⌘2

µ_xy

 2EB(0,N 1)^c(u u_n)2⇣

EB(0,N 1)^c(u) +EB(0,N 1)^c(u_n)⌘

(1.19)

(14)

for all n N0. Asun= (u+vn |u vn|)/2, we have EB(0,N 1)^c(un)  c₁⇣

EB(0,N 1)^c(u) +EB(0,N 1)^c(vn) +EB(0,N 1)^c(|u v_n|)⌘

 c₂⇣

EB(0,N 1)^c(u) +EB(0,N 1)^c(v_n)⌘ . Thus, together with (1.19), we have

E(u un, u un)c3

⇣EB(0,N 1)^c(u) +EB(0,N 1)^c(vn)⌘

c3

⇣EB(0,N 1)^c(u) +E(vn, vn)⌘ . Sinceu2H²,EB(0,N 1)^c(u)!0 asN ! 1and by the assumption,E(v_n, v_n)!0 asn! 1. So we obtain E(u u_n, u u_n)!0 as n! 1. By the assumption, it is clear that u u_n !0 pointwise, so we obtainku unkH² !0.

We say that a quadratic form (E,F) is Markovian if u 2 F and v = (0_u)^1, then v 2 F and E(v, v)  E(u, u). It is easy to see that quadratic forms determined by weighted graphs are Markovian.

Proposition 1.22 The following are equivalent.

(i) The Markov chain corresponding to (X, µ) is transient.

(ii) 12/ H₀²

(iii) Cap({x})>0 for some x2X.

(iii)⁰ Cap({x})>0 for allx2X.

(iv) H₀² 6=H²

(v) There exists a non-negative super-harmonic function which is not a constant function.

(vi) For each x2X, there exists c₁(x)>0 such that

|f(x)|² c1(x)E(f, f) 8f 2C0(X). (1.20) Proof. For fixed x2X, define'(z) =P^z( x <1). We first show the following: '2H₀² and

E(',') = ( L',1_{_x_}) =R_e↵(x) ¹= Cap ({x}). (1.21) Indeed, let {A_n}¹n=1 be a family of finite sets such that A_n ⇢ A_n+1 for n 2 N, x 2 A₁, and [n 1An = X. Then R_e↵(x, A^c_n) ¹ # R_e↵(x) ¹. Let 'n(z) = P^z( x < ⌧An). Using Lemma 1.5 (ii), and noting '_n2C₀(X), we have, for mn,

E('m, 'n) = ('m, L'n) = (1_{_x_}, L'n) =E('n, 'n) =R_e↵(x, A^c_n) ¹. (1.22) This implies

E('_m '_n, '_m '_n) =R_e↵(x, A^c_m) ¹ R_e↵(x, A^c_n) ¹.

Hence {'_m} is aE-Cauchy sequence. Noting that '_n !' pointwise, we see that'_n !'in H² as well and ' 2 H₀². Taking n =m and n ! 1 in (1.22), we obtain (1.21) except the last equality.

To prove the last equality of (1.21), take any f 2 H₀² with f(x) = 1. Then g := f '2 H₀² and

(15)

g(x) = 0. Let gn 2 C0(X) with gn ! g in H₀². Then, by Lemma 1.5 (ii), E(', gn) = ( L', gn).

Noting that 'is harmonic except at x, we see thatL'2C₀(X). so, letting n! 1, we have E(', g) = ( L', g) = L'(x)g(x)µx= 0.

Thus,

E(f, f) =E('+g,' +g) =E(',') +E(g, g) E(','),

which means that ' is the unique minimizer in the definition of Cap ({x}). So the last equality of (1.21) is obtained.

Given (1.21), we now prove the equivalence.

(i) =)(iii)⁰: This is a direct consequence of (1.18) and (1.21).

(iii) () (ii) () (iii)⁰: This is easy. Indeed, Cap ({x}) = 0 if and only if there is f 2 H₀² with f(x) = 1 andE(f, f) = 0, that isf is identically 1.

(iii)⁰ =)(vi): Letf 2C0(X)⇢H₀² withf(x)6= 0, and defineg=f /f(x). Then Cap ({x}) E(g, g) =E(f, f)/f(x)².

So, lettingc₁(x) = 1/Cap ({x})>0, we obtain (vi).

(vi) =) (i): As before, let 'n(z) = P^z( x < ⌧An). Then by (1.20), E('n, 'n) c1(x) ¹. So, using the fact '_n!' inH² and (1.21), R_e↵(x) ¹ =E(',') = lim_nE('_n, '_n) c₁(x) ¹. This means the transience by (1.18).

(ii) ()(iv): (ii) =) (iv) is clear since 1 2H², so we will prove the opposite direction. Suppose 1 2H₀². Then there exists {f_n}n ⇢C₀(X) such that k1 f_nkH² < n ². Since E is Markovian, we have k1 f_n|H² k1 (fn_0)^1kH², so without loss of generality we may assume f_n 0. Let vn = nfn 0. Then limnvn(x) = 1 for all x 2X and E(vn, vn) = n²E(fn, fn) n ² ! 0 so by Lemma 1.21, ku (u^v_n)kH² !0 for all u2 H² with u 0. Since u^v_n 2C₀(X), this implies u 2 H₀². For general u 2H², we can decompose it into u₊ u where u₊, u 0 are in H². So applying the above, we have u₊, u 2H₀² and concludeu2H₀².

(i) =) (v): If the corresponding Markov chain is transient, then (z) = P^z( _x⁺ < 1) is the non- constant super-harmonic function.

(i) (= (v): Suppose the corresponding Markov chain {Y_n}n is recurrent. For a super-harmonic function 0, M_n = (Yn) 0 is a supermartingale, so it converges P^x-a.s. Let M₁ be the limiting random variable. Since the set {n2N:Yn=y} is unbounded P^x-a.s. for ally2X (due to the recurrence), we haveP^x( (y) =M₁) = 1 for all y2X, so is constant.

Remark 1.23 (v) =) (i) implies that if the Markov chain corresponding to (X, µ) is recurrent, then it has the strong Liouville property.

ForA, B which are subspaces of H², we writeA B ={f +g :f 2A, g 2B} ifE(f, g) = 0 for all f 2Aand g2B.

As we see above, the Markov chain corresponding to (X, µ) is recurrent if and only ifH² =H₀². When the Markov chain is transient, we have the following decomposition ofH², which is called the Royden decomposition (see [107, Theorem 3.69]).

(16)

Proposition 1.24 Suppose that the Markov chain corresponding to(X, µ) is transient. Then H² =H H₀²,

where H:={h2H² :h is a harmonic functions on X.}. Further the decomposition is unique.

Proof. For eachf 2H², leta_f = inf_h2H2

0 E(f h, f h). Then, similarly to the proof of Proposition 1.13, we can show that there is a unique minimizer v_f 2 H₀² such that a_f = E(f v_f, f v_f), E(f v_f, g) = 0 for allg2H₀², and in particularf v_f is harmonic onX. For the uniqueness of the decomposition, suppose f =u+v =u⁰+v⁰ where u, u⁰ 2 H and v, v⁰ 2H₀². Then, w:= u u⁰ = v⁰ v2 H \H₀², soE(w, w) = 0, which implies w is constant. Sincew2H₀² and the Markov chain is transient, by Proposition 1.22 we havew⌘0.

1.3 Trace of weighted graphs

Finally in this section, we briefly mention the trace of weighted graphs, which will be used in Section 3 and Section 7. Note that there is a general theory on traces for Dirichlet forms (see [55]). Also note that a trace to infinite subset ofX may not satisfy locally finiteness, but one can consider quadratic forms on them similarly.

Proposition 1.25 (Trace of the weighted graph) Let V ⇢ X be a non-void set such that P( _V <

1) = 1and let f be a function on V. Then there exists a uniqueu2H² which attains the following infimum:

inf{E(v, v) :v2H², v|V =f}. (1.23) Moreover, the map f 7!u=:H_Vf is a linear map and there exist weights {µˆ_xy}x,y2V such that the corresponding quadratic form EˆV(·,·) satisfies the following:

EˆV(f, f) =E(HVf, H_Vf) 8f :V !R.

Proof. The first part can be proved similarly to Proposition 1.11 and Proposition 1.13. It is clear that H_V(cf) = cH_Vf, so we will show H_V(f₁ +f₂) = H_V(f₁) +H_V(f₂). Let ' = H_V(f₁ +f₂), '_i = H_V(fi) for i = 1,2, and for f :V ! R, define Ef : X ! R by (Ef)|V =f and Ef(x) = 0 when x 2 V^c. As in the proof of Proposition 1.13 (ii), we see that E(HVf, g) = 0 whenever Supp g⇢V^c. So

E('1+'2, '1+'2) =E('1+'2, Ef1+Ef2) =E('1+'2, ') =E(E(f1+f2), ') =E(',').

Using the uniqueness of (1.23), we obtain '₁ +'₂ = '. This establishes the linearity of H_V. Set Ê(f, f) = E(H_Vf, H_Vf). Clearly, Ê is a non-negative definite symmetric bilinear form and Eˆ(f, f) = 0 if any only iff is a constant function. So, there exists {a_xy}x,y2V with a_xy =a_yx such that Ê(f, f) = ¹₂P

x,y2V axy(f(x) f(y))².

(17)

Next, we show that ˆE is Markovian. Indeed, writing ¯u = (0_u)^1 for a function u, since H_Vu|V = ¯u, we have

Eˆ(¯u,u) =¯ E(H_Vu, H¯ _Vu)¯  E(H_Vu, H_Vu) E(H_Vu, H_Vu) = ˆE(u, u), 8u:V !R,

where the fact that E is Markovian is used in the second inequality. Now take p, q 2V with p6=q arbitrary, and consider a functionhsuch thath(p) = 1, h(q) = ↵ <0 andh(z) = 0 forz2V\{p, q}. Then, there exist c₁, c₂ such that

Eˆ(h, h) = a_pq(h(p) h(q))²+c₁h(p)²+c₂h(q)²=a_pq(1 +↵)²+c₁+c₂↵² Eˆ(¯h,¯h) =a_pq(¯h(p) ¯h(q))²+c₁¯h(p)²+c₂h(q)¯ ² =a_pq+c₁.

So (a_pq+c₂)↵²+ 2a_pq↵ 0. Since this holds for all ↵ >0, we havea_pq 0. Putting ˆµ_pq =a_pq for each p, q2V withp6=q, we have ÊV = Ê, that is Ê is associated with the weighted graph (V,µ).ˆ

We call the induced weights{µˆ_xy}x,y2V as thetrace of {µ_xy}x,y2X toV. From this proposition, we see that forx, y2V,R_e↵(x, y) =R^V_e↵(x, y) whereR^V_e↵(·,·) is the e↵ective resistance for (V,µ).ˆ

2 Heat kernel upper bounds (The Nash inequality)

In this section, we will consider various equivalent inequalities to the Nash-type heat kernel upper bound, i.e. p_t(x, y)  c₁t ^✓/2 for some ✓ > 0. We would prefer to discuss them under a general framework including weighted graphs. However, some arguments here are rather sketchy to apply for the general framework. (The whole arguments are fine for weighted graphs, so readers may only consider them.) This section is strongly motivated by Coulhon’s paper [40].

LetX be a locally compact separable metric space and µ be a Radon measure on X such that µ(B) > 0 for any non-void ball. (E,F) is called a Dirichlet form on L²(X, µ) if it is a symmetric Markovian closed bilinear form on L². It is well-known that given a Dirichlet form, there is a corresponding symmetric strongly continuous Markovian semigroup {Pt}t 0 on L²(X, µ) (see [55, Section 1.3, 1.4]). Here Markovian means ifu2L² satisfies 0u1µ-a.s., then 0P_tu1µ-a.s.

for all t 0. We denote the corresponding non-negative definiteL²-generator by L.

We denote the inner product of L² by (·,·) and for p 1 denote kfkp for the L^p-norm of f 2L²(X, µ). For each ↵ >0, define

E↵(·,·) =E(·,·) +↵(·,·).

(E1,F) is then a Hilbert space.

2.1 The Nash inequality We first give a preliminary lemma.

Lemma 2.1 (i) kP_tfk1  kfk1 for all f 2L¹\L².

(ii) For f 2L², defineu(t) = (P_tf, P_tf). Then u⁰(t) = 2E(P_tf, P_tf).

(iii) For f 2 F and t 0, exp( E(f, f)t/kfk²2) kP_tfk2/kfk2.

(18)

Proof. (i) We first show that if 0f 2L², then 0Ptf. Indeed, if we letfn=f·1_f ¹_([0,n]), then f_n!f inL². Since 0f_nn, the Markovian property of{P_t} implies that 0P_tf_nn. Taking n ! 1, we obtain 0  P_tf. So we have P_t|f| |P_tf|, since |f|  f  |f|. Using this and the Markovian property, we have for allf 2L²\L¹ and all Borel setA⇢X,

(|P_tf|,1_A)(P_t|f|,1_A) = (|f|, P_t1_A) kfk1. Hence we have P_tf 2L¹ andkP_tfk1  kfk1.

(ii) SinceP_tf 2Dom(L), we have u(t+h) u(t)

h = 1

h(P_t+hf+P_tf, P_t+hf P_tf) = (P_t+hf+P_tf,(P_h I)Ptf

h )

h#0

! 2(P_tf,LP_tf) = 2E(P_tf, P_tf).

Hence u⁰(t) = 2E(Ptf, P_tf).

(iii) We will prove the inequality for f 2 Dom(L); then one can obtain the result for f 2 F by approximation. Let L = R₁

0 dE be the spectral decomposition of L. Then P_t = e^Lt = R₁

0 e ^tdE and kfk²2=R₁

0 (dE f, f). Since 7!e ² ^t is convex, by Jensen’s inequality, exp⇣

2Z ₁

0

t(dE f, f) kfk²2

⌘ Z ₁

0

e ² ^t(dE f, f) kfk²2

= (P2tf, f) kfk²2

= kP_tfk²2

kfk²2

. Taking the square root in each term, we obtain the desired inequality.

Remark 2.2 An alternative proof of (iii) is to use the logarithmic convexity ofkP_tfk²2. Indeed, kP_(t+s)/2fk²2 = (Pt+sf, f) = (Ptf, Psf) kPtfk2kPsfk2, 8s, t >0

so kP_tfk²2 is logarithmic convex. Thus, t7! d

dtlogkPtfk²2= ^dt^d(kPtfk²2) kP_tfk²2

= 2E(Ptf, Ptf) kP_tfk²2

(2.1) is non-decreasing. (The last equality is due to Lemma 2.1(ii).) The right hand side of (2.1) is

2E(f,f)

kfk²2 when t= 0, so integrating (2.1) over [0, t], we have logkP_tfk²2

kfk²₂ =Z _t

0

d

dslogkP_sfk²2ds 2tE(f, f) kfk²₂ . The following is easy to see. (Note that we only need the first assertion.)

Lemma 2.3 Let (E,F)be a symmetric closed bilinear form on L²(X, µ), and let{P_t}t 0, Lbe the corresponding semigroup and the self-adjoint operator respectively. Then, for each >0, (E ,F) is also a symmetric closed bilinear form and the corresponding semigroup and the self-adjoint operator are {e ^tP_t}t 0, I L, respectively. Further, if (E,F) is the regular Dirichlet form on L²(X, µ) and the corresponding Hunt process is {Y_t}t 0, then (E ,F) is also the regular Dirichlet form and the corresponding hunt process is {Y_t^⇣}t 0 where ⇣ is the independent exponential random variable with parameter . (⇣ is the killing time; i.e. the process goes to the cemetery point at ⇣.)

(19)

The next theorem was proved by Carlen-Kusuoka-Stroock ([38]), where the original idea of the proof of (i))(ii) was due to Nash [96].

Theorem 2.4 (The Nash inequality, [38]) The following are equivalent for any 0.

(i) There exist c₁, ✓ > 0 such that for all f 2 F \L¹,

kfk^2+4/✓2 c₁(E(f, f) + kfk²2)kfk^4/✓1 . (2.2) (ii) For all t > 0, P_t(L¹) ⇢L¹ and it is a bounded operator. Moreover, there exist c₂, ✓ > 0 such that

kP_tk1!1c₂e^tt ^✓/2, 8t >0. (2.3) Here kP_tk1!1 is an operator norm of P_t:L¹!L¹.

When = 0, we cite (2.2) as (N_✓) and (2.3) as (U C_✓).

Proof. First, note that using Lemma 2.1, it is enough to prove the theorem when = 0.

(i) ) (ii) : Let f 2 L² \L¹ with kfk1 = 1 and u(t) := (Ptf, P_tf)2. Then, by Lemma 2.1 (ii), u⁰(t) = 2E(Ptf, Ptf). Now by (i) and Lemma 2.1 (i),

2u(t)^1+2/✓ c1( u⁰(t))kPtfk^4/✓₁  c1u⁰(t),

so u⁰(t)  c₂u(t)^1+2/✓. Set v(t) = u(t) ^2/✓, then we obtain v⁰(t) 2c2/✓. Since limt#0v(t) = u(0) ^2/✓ =kfk2^4/✓ >0, it follows that v(t) 2c2t/✓. This means u(t) c₃t ^✓/2, whencekP_tfk2  c₃t ^✓/4kfk1 for all f 2 L² \ L¹, which implies kP_tk1!2  c₃t ^✓/4. Since P_t = P_t/2 P_t/2 and kP_t/2k1!2 =kP_t/2k2!1, we obtain (ii).

(ii))(i) : Letf 2L²\L¹ withkfk1 = 1. Using (ii) and Lemma 2.1 (iii), we have exp( 2E(f, f)t

kfk²2

) c₄t ^✓/2 kfk²2

.

Rewriting, we have E(f, f)/kfk²2 (2t) ¹log(t^✓/2kfk²2) (2t) ¹A, where A = logc4 and we may take A > 0. Set (x) = sup_t>0{_2t^x log(xt^✓/2) Ax/(2t)}. By elementary computations, we have (x) c₅x^1+2/✓. So

E(f, f) (kfk²2) c5kfk^2(1+2/✓)₂ =c5kfk^2+4/✓. Since this holds for allf 2L²\L¹ with kfk1= 1, we obtain (i).

Remark 2.5 (1) When one is only concerned about t 1 (for example on graphs), we have the following equivalence under the assumption of kP_tk1!1 C for allt 0 (C is independent oft).

(i) (N_✓) with = 0 holds for E(f, f) kfk²1. (ii) (U C✓) with = 0 holds for t 1.

Random walks on disordered media and their scaling limits