Volume and time doubling of graphs and random walks, the strongly recurrent case

András Telcs IMC Graduate School of Business, Budapest

January 26, 2001

Abstract This paper proves upper and lower off-diagonal, sub-Gaussian transition probability estimates for strongly recurrent random walks under sufficient and necessary conditions. Besides the known conditions, volume doubling and elliptic Harnack inequality, a new property: time doubling is introduced.

1 Introduction

1.1 The beginnings

The diffusion processes in ℝ^{d}, on Riemannian manifolds and random walks on groups and graphs have common fundamental questions to answer. In light of the advances of the theory of diffusion on fractals it seems to be worth reconsidering the basic questions of classical studies (Einstein [19], Wiener [59], Aronson [1], Moser [36],[37], Cheeger, Yau [11], Gromov [25], Varopoulos [54], Davies [17]);

What geometric, analytic or spectral properties determine the diffusion speed in terms of the heat kernel or transition probability estimates and their relation to the elliptic and parabolic Harnack inequalities?

The generalized transition probability (heat kernel) estimates in the discrete time and space setting have the form of

P_{n}(x, y) ≤ \frac{Cμ(y)}{V (x, f(n))} exp −ck(n, d(x, y))  (UE_{F})

P̃_{n}(x, y) ≥ \frac{cμ(y)}{V (x, f(n))} exp −Ck(n, d(x, y))  (LE_{F})

where P̃_{n} = P_{n} + P_{n+1} and the functions f(n), k(n, d(x, y)) take over the role of \sqrt{n}, d^{2}(x, y)/n, re-

spectively, in the classical Gaussian estimates; n^{\frac{1}{β}} , (\frac{d^{β}(x,y)}{n})^{\frac{1}{β−1}} in the estimates typically appear with respect of a fractal type space. In a recent paper [26] complete characterization of polynomially growing

transient graphs was given. The estimates (UE_{F}), (LE_{F}) ( with f(n) = n^{\frac{1}{β}} , k(n, d(x, y)) = (\frac{d^{β}(x,y)}{n})^{\frac{1}{β−1}} ) hold if and only if

V (x, R) ≃ R^{α} and G(x, y) ≃ d(x, y)^{β−α},

for α > β > 1, where G is the Green function of the walk. The β > 2 case has acquired the sub-Gaussian nickname reflecting the sub-diffusive character of the diffusion process (c.f. [2], [3], [31] and [7]).

The present paper supplements the result of [26] handling the strongly recurrent case and goes much beyond its scope. It generalizes fundamental results ( among others [1], [36],[54]) and recent works ( e.g. [7],[16],[22], [29]) giving necessary and sufficient conditions for (UE_{F}), (LE_{F}) showing connection between the sub-Gaussian estimates and elliptic and parabolic Harnack inequalities. In doing that a new framework was developed for parabolic Harnack inequalities and sub-Gaussian estimates covering the widest possible set of functions approximating the mean exit time. The key element of this approach is the new notion of time doubling. It provides a promising new approach for further studies of diffusion on measure metric spaces.

The further exposition needs some definitions.

1.2 The foundations

In this subsection we provide the necessary definitions and concepts to be able to formulate the topics and the main result of the paper.

Consider an infinite connected graph Γ with a weight function μ_{x,y} on the edges x ∼ y. This weight induces a measure μ(x)

μ(x) = ∑_{y∼x} μ_{x,y} and μ(A) = ∑_{y∈A} μ(y)

on the vertex set A ⊂ Γ and defines a reversible Markov chain, i.e. a random walk on the weighted graph (Γ, μ ) with transition probabilities

P (x, y) = \frac{μ_{x,y}}{μ(x)}.

The graph is equipped with the usual (shortest path length) graph distance d(x, y) and metric balls defined for x ∈ Γ, R > 0 as B(x, R) = {y ∈ Γ : d(x, y) < R} and its μ−measure is denoted by V (x, R) = μ(B(x, R)). The random walk is said to be strongly recurrent (SR) if the number of returns to the starting point of the walk, before it leaves the ball, centered at the staring point, is at least polynomial in the radius of the ball.

Definition 1.1 The graph has property of volume doubling (VD) if there is a constant D_{V} > 0 such that for all x ∈ Γ and R > 0

V (x, 2R) ≤ D_{V} V (x, R).  (P D_{1}V or V D)

The volume function V acts on Γ × ℕ^{0} and has some remarkable properties ([14, Lemma 2.2]). There is a C_{V} > 0, A_{V} > 0 such that x, y ∈ Γ, R ≥ S ≥ 1

\frac{V (x, R)}{V (y, S)} ≤ C_{V} (\frac{R}{S})^{α} ,  (PD_{2}V)

where α = log_{2} D_{V} and there is an A_{V} > 1 such that

2V (x, R) ≤ V (x, A_{V} R).  (P D_{3}V)

From the triangular inequality one can easily deduce the super-additivity of the volume. For x ∈ Γ, R, S > 0

V (x, R) + min_{y:d(x,y)≤R} V (y, S) ≤ V (x, R + S),  (P D_{4}V)

as well, in fact, for V, V (x, R) + V (y, S) ≤ V (x, R + S) is also true for any x, y : d(x, y) ≤ R.

Definition 1.2 If for the function F : Γ × ℕ → ℝ (P D_{1}F)...(P D_{4}F) are valid, the short notation (P D_{F}) will be used.

Using this notation the above statements say that (P D_{1}V) (i.e., volume doubling ) implies (P D_{V}). Let us consider the exit time T_{B(x,R)} = min{k : X_{k} ∉ B(x, R)} from the ball B(x, R) and its mean

value E_{z}(x, R) = 𝔼(T_{B(x,R)}|X_{0} = z) and let us use the short notation E(x, R) = E_{x}(x, R).

Definition 1.3 Analogously to the volume doubling, we say that (Γ, μ) has the property of time doubling if there is a D_{E} > 0 such that for all x ∈ Γ and R ≥ 0

E(x, 2R) ≤ D_{E}E(x, R).  (P D_{1}E or T D)

We will prove that the mean exit time has property (P D_{E}) and E(x, R) ≥ cR^{2} provided that certain conditions hold.

Although we have remarkable similarity between the properties of the volume and the exit time, this set of functions appeared to be too wide to get sub-Gaussian estimates (UE_{F}), (LE_{F}) and the parabolic Harnack inequality. We assume that the mean exit time is uniform in space in the sense that for all x, y ∈ Γ

E(x, R) ≃ E(y, R).  (E)

Let us define the function F (R), R ≥ 0 as

F (R) = inf_{x∈Γ} E(x, R).

From (E) it follows that F satisfies with a fixed C > 1 for all x ∈ Γ and R ≥ 0

F (R) ≤ E(x, R) ≤ C_{0}F (R).  (E_{F})

This function inherits (see Theorem 4.4) certain properties of E(x, R) namely

F (2R) ≤ D_{F} F (R),  (ED_{1}F)

\frac{F (R)}{F (S)} ≤ C_{F} (\frac{R}{S})^{ϕ} ,  (ED_{2}F)

where ϕ = log_{2} D_{F} ≥ log_{2} D_{E} and there are B_{F} > A_{F} > 1 such that

B_{F} F (R) ≤ F (A_{F} R),  (ED_{3}F)
F (R) + F (S) ≤ F (R + S).  (ED_{4}F)

The mean exit time has a natural lower bound in many cases and also in the present study which is also inherited by F

F (R) ≥ cR^{2}.  (ED_{5}F)

Definition 1.4 If (ED_{1}F)..(ED_{5}F) are true the short notation (ED_{F}) will be used.

The function F with property (ED_{F}) will take over the role of R^{2} (or R^{β}), the mean exit time in the parabolic Harnack inequality and its inverse in the sub-Gaussian estimates. Let us observe that E(x, R) ≃ R^{β} is also a uniformity restriction of the mean exit time.

Definition 1.5 The weighted graph satisfies the (F −parabolic or simply) parabolic Harnack inequality (PH_{F}) if the following condition holds. For a given profile C = {c_{1}, c_{2}, c_{3}, c_{4}, η}, 0 < c_{1} < c_{2} < c_{3} < c_{4}, 0 < η < 1, set of constants, there is a C_{H}(C) > 0 constant such that for any solution u of the equation

u_{n+1}(x) = P u_{n}(x) on U = [k, k + F (c_{4}R)] × B(x, R)

for k, R ∈ ℕ the following is true. On the smaller cylinders defined by

U^{−} = [k + F (c_{1}R), k + F (c_{2}R)] × B(x, ηR) and U^{+} = [k + F (c_{3}R), k + F (c_{4}R)] × B(x, ηR)

and taking (n_{−}, x_{−}) ∈ U^{−}, (n_{+}, x_{+}) ∈ U^{+}, d(x_{−}, x_{+}) ≤ n_{+} − n_{−} the inequality

u(n_{−}, x_{−}) ≤ C_{H} ũ(n_{+}, x_{+})

holds, where the short notation ũ_{n} = u_{n} + u_{n+1} was used. Let us remark that C_{H} depends on the involved constants (including c_{i}, η, D_{V} , A_{V} , A_{F} , B_{F} , C_{F} , D_{F} ).

It is known that if the (classical) parabolic Harnack inequality holds for a given profile, then it is true for arbitrary profile. We shall see in Subsection 7.1 that the same holds in our general case in the presence of (P D_{F}) or (ED_{F}).

The elliptic Harnack inequality is a direct consequence of the F-parabolic one as in the classical case.

Definition 1.6 The graph satisfies the elliptic Harnack inequality if there is a C > 0 such that for all x ∈ Γ, R > 0 and u harmonic function on B(x, 2R), which means, that

P u = u on B(x, 2R),

the following inequality holds

max_{B(x,R)} u ≤ C min_{B(x,R)} u  (H)

Definition 1.7 We define \underline{k} as 1 ≤ \underline{k} = k(x, n, R) ≤ R ≤ n as the maximal integer for which

\frac{n}{\underline{k}} ≤ q min_{y∈B(x,R)} E(y, ⌊\frac{R}{\underline{k}}⌋)  (iter)

or \underline{k} = 0 by definition if there is no appropriate \underline{k}. Similarly the kernel function k = k(n, d(x, y)) ≥ 1 in (UE_{F}), (LE_{F}) is defined as the maximal integer for which

\frac{n}{k} ≤ qF (⌊\frac{d(x, y)}{k}⌋)  (:k)

or k = 0 by definition if there is no appropriate k. The constant q is fixed, 0 < q < min \{\frac{p_{0}}{C_{F} D_{F}} , \frac{1}{16}\} .

1.3 The result in brief

Without going into further details, the main result of the paper can be sketched as follows.

Theorem 1.1 For a strongly recurrent weighted graph (Γ, μ) with \frac{μ_{x,y}}{μ(x)} ≥ p_{0} > 0 the following statements are equivalent

1. (Γ, μ) satisfies (V D), (T D) (H) and (E);

2. ∃F : (Γ, μ) satisfies (ED_{F}) and (UE_{F}), (LE_{F});

3. ∃F : (Γ, μ) satisfies (ED_{F}) and (P H_{F}).

To our best knowledge similar results are known only for E(x, R) ≃ F (R) = cR^{2} on manifolds and for local Dirichlet spaces provided that the topology induced by intrinsic metric (associated with the Dirichlet form) is equivalent with the original one (c.f. [29], [44]). This homogeneity is ensured in our settings by the elliptic Harnack inequality and the uniform behavior of the mean exit time. These conditions seem to fit well to the sub-Gaussian estimates and F −parabolic Harnack inequality.

It is impossible to fit an overview of the enormous literature of diffusion theory into the framework of the present paper. The reader is requested for further historical background and recent developments to turn to the works listed below by topics and method.

• R^{n} and Riemannian manifolds [13],[23], [24], [28],[48]

• Markov chains and graphs [14], [12], [13], [60]

• Random walks on groups and graphs [55], [60], [42]

• fractals [2],[3],[6], [27], [35], [38], [40], [56], • isoperimetry, geometry, spectra [9],[15],[33], [34], [39],[41]

• Dirichlet spaces (or measure metric spaces) [3], [6], [20],[29], [43], [44], [45], [57]

• further generalizations [10], [58]

At this point the author has to apologize. The list is far from being complete, rather it reflects the author’s limited capacity and not judgement about the missing works.

Acknowledgments

The author is indebted to A. Grigor’yan and T. Coulhon for their friendly support and useful discussions.

2 Further definitions and the results

This section contains all the necessary definitions, the full statement of the results and some comments.

Condition 1 Throughout the whole paper

P_{x,y} ≥ p_{0} > 0  (p_{0})

is a standing assumption.

The analysis of the random walk needs some basic elements of potential theory([18],[53]).

Definition 2.1 For any two disjoint sets A, B ⊂ Γ the resistance ρ(A, B) is defined as

ρ(A, B)^{−1} = inf {((I − P) f, f)_{μ} : f|_{A} = 1, f|_{B} = 0}

and we introduce the following short notations

ρ = ρ(x, R) = ρ({x}, Γ\B(x, 2R)) and ρ(x, R, 2R) = ρ(B(x, R), Γ\B(x, 2R)),

which will be used where it is not ambiguous.

Definition 2.2 We say that the random walk or the graph is strongly recurrent if there are c_{ρ} > 0, M ≥ 2 such that for all x ∈ Γ, R ≥ 1

ρ(x, MR) ≥ (1 + c_{ρ})ρ(x, R).  (SR)

Remark 2.1 It is evident that from this condition it follows that there are c, δ_{ρ} > 0 for which for all L, R ∈ ℕ, x∈ Γ

ρ(x, LR) ≥ cL^{δ_{ρ}}ρ(x, R),  (2.1)
ρ(x, R) > cR^{δ_{ρ}},

(δ_{ρ} = log_{2}(1 + c_{ρ})) i.e. ρ(x, R) tends to infinity and hence the random walk is recurrent since it is well known that this holds if ρ(x, R) → ∞ (c.f.[18]). This definition is similar but not equivalent with the classical one, namely, that G_{n} = ∑_{k=0}^{n} p_{k}(x, x), the expected number of returns is polynomial in n. It is well known that for the simple symmetric random walk on ℤ^{d} G_{n} ≃ \sqrt{n} if d = 1 while G_{n} ≃ log n if d = 2. The two conditions coincide provided that further conditions hold (c.f. [52]). For ℤ^{d} it is easy to find that ρ(x, R) = \frac{1}{2}R if d = 1 and ρ(x, R) ≃ log R which immediately shows that the two dimensional integer lattice is weakly recurrent according to the definition. Also one can find several examples for strongly recurrent fractal type graphs. The most common example is the Sierpinski gasket, where logρ(x, R)/ log R ≃ (log 5 − log 3) / log 2.[5].

Definition 2.3 We say that the graph has the resistance doubling property if there is a constant D_{ρ} > 0 such that for all x ∈ Γ and R > 0

ρ(x, 2R) ≤ D_{ρ}ρ(x, R).  (ρD)

One can observe that this condition and strong recurrence don’t imply the polynomial growth of ρ(x, R).

In the whole sequel the short notation a_{ξ} ≃ b_{ξ} will be used if there is a C > 1 such that for all possible ξ; \frac{1}{C} a_{ξ} ≤ b_{ξ} ≤ Ca_{ξ}.

Definition 2.4 We say that the resistance is uniform in Γ relative to the volume if

ρ(x, R)V (x, R) ≃ ρ(y, R)V (y, R).  (ρ)

Definition 2.5 We say that the graph has the resistance doubling property on annuli if there are constants D_{ρ_{A}} > 0, M ≥ 2 such that for all x ∈ Γ and R > 0

ρ(x, 2R, 2MR) ≤ D_{ρ_{A}}ρ(x, R, MR).  (ρ_{A}D)

Definition 2.6 We say that the annulus resistance is uniform in Γ relative to the volume if with a fixed M ≥ 2

ρ(x, R, MR)V (x, MR) ≃ ρ(y, R, MR)V (y, MR).  (ρ_{A})

Definition 2.7 The random walk defined by (Γ, μ) will be denoted by (X_{n}). It is a reversible Markov chain on the state space Γ, reversible with respect to the measure μ and has one step transition probability

ℙ(X_{n+1} = y|X_{n} = x) = P (x, y) = \frac{μ_{x,y}}{μ(x)}

and the n-step transition probability is

P_{n}(x, y) = ℙ(X_{n} = y|X_{0} = x).

Definition 2.8 For A ⊂ Γ, P^{A} = P^{A}(y, z) = P (y, z)|_{A×A} is a substochastic matrix (or the operator corresponding to the Dirichlet boundary condition), the restriction of P to the set A. Its iterates are denoted by P_{k}^{A} and it defines also a random walk killed, when it leaves the set.

For the sake of completeness we give a formal definition of the exit time.

Definition 2.9 The exit time (and its expected value) from a set A is defined as

T_{A} = min{k : X_{k} ∈ Γ\A}, E_{x}(A) = 𝔼(T_{A}|X_{0} = x) and denote E(x, R) = E_{x}(B(x, R))

Definition 2.10 The extreme mean exit time is defined as

\overline{E}(A) = max_{x∈A} E(x, A) and \overline{E}(x, R) = max_{y∈B(x,R)} 𝔼(T_{B(x,R)}|X_{0} = y).

Definition 2.11 The inverse function of E(x, R) in the second variable will be denoted by e(x, t), i.e. e(x, E(x, R)) = R

Definition 2.12 We introduce

G^{A}(y, z) = ∑_{k=0}^{∞} P_{k}^{A}(y, z)

the local Green function, the Green function of the killed walk. The notation P^{R} = P^{x,R} = P^{B(x,R)}(y, z) will be used for A = B(x, R) and for the corresponding Green function by G^{R} = G^{x,R}.

Definition 2.13 Let ∂A denote the boundary of A : ∂A = {z ∈ Γ\A : ∃y ∈ A and y ∼ z}, and particularly S(x, R) = ∂B(x, R).

Remark 2.2 It is well-known (c.f. [49]) that

G^{x,R}(x, x) = μ(x)ρ(x, R),

which is a special case of

G^{A}(x, x) = μ(x)ρ(x, ∂A).

Definition 2.14 We introduce the maximal recurrent resistance (or inverse capacity) of a set A ⊂ Γ with respect to the internal Dirichlet problem

\overline{ρ}(A) = max_{y∈A} ρ(y, ∂A).

Definition 2.15 The Laplace operator of finite sets particularly for balls can be defined as (I − P)|_{A×A} or simply I − P^{A}. The smallest eigenvalue is denoted in general by λ(A) and for A = B(x, R) by λ = λ(x, R) = λ(B(x, R)). For variational definition and properties see [14].

Definition 2.16 We say that the graph satisfies the eigenvalue doubling property if there is a D_{λ} > 0 such that for all balls B(x, R)

λ^{−1}(x, 2R) ≤ D_{λ}λ^{−1}(x, R).  (λ^{−1}D)

Definition 2.17 We say that the eigenvalue is uniform in Γ if

λ(x, R) ≃ λ(y, R).  (λ)

The results of the paper are the following:

Theorem 2.1 For any weighted graph (Γ, μ) with (p_{0}) if (V D)(SR), (H)

and \{ \begin{matrix}(T D) & or \\ (ρD) & or \\ (ρ_{A}D) & or \\ (λ^{−1}D) \end{matrix} \} hold, then there are c, C > 0 such that for all x, y ∈ Γ, n > 0

1.

P_{n}(x, x) ≤ \frac{Cμ(x)}{V (x, e(x, n))};  (LDUE)

2.

P_{n}(x, y) ≤ Cμ(y) (\frac{1}{V (x, e(x, n))V (y, e(y, n))})^{\frac{1}{2}} ;  (LPUE)

3.

P_{2n}(x, x) ≥ \frac{cμ(x)}{V (x, e(x, n))};  (LDLE)

4.

ℙ(T_{x,R} < n) ≤ exp −\underline{k}(x, n, R),  (LΨ)

where \underline{k} is the maximal integer 1 ≤ k ≤ R ≤ n satisfying (iter).

Theorem 2.2 For strongly recurrent weighted graphs with (p_{0}) the following statements are equivalent

1. (Γ, μ) satisfies (V D), (H), \{ \begin{matrix}(T D) & or \\ (ρD) & or \\ (ρ_{A}D) & or \\ (λ^{−1}D) \end{matrix} \}and\{ \begin{matrix}(E) & or \\ (ρ) & or \\ (ρ_{A}) & or \\ (λ) \end{matrix} \};

2. there is an F such that (ED_{F}) and (UE_{F}), (LE_{F}) hold;

3. there is an F such that (ED_{F}) and (P H_{F}) hold.

Theorem 2.3 For all weighted graph (Γ, μ) with (p_{0}) the statements below imply the subsequent one.

1. there is an F such that (Γ, μ) satisfies (ED_{F}), (UE_{F}) and (LE_{F});

2. there is an F such that (Γ, μ) satisfies (ED_{F}) and (P H_{F});

3. (Γ, μ) satisfies (V D),(ρ_{A}), (ρ_{A}D) and (H).

The above results are new in several respects. We are not aware of any predecessor or counterpart of the time doubling and upper and lower estimate and parabolic Harnack inequality based on F. The results generalizes several works: ( [36],[54],[29],[22],[16], [7] just to list some of them).

The proof itself contains several new elements. In order to handle the sub-Gaussian kernel, several properties are studied in Section 3 and 4. This analysis is based on general potential-theoretic arguments and inequalities given in the Subsection 3.1-3.4. The large deviation result (Section 5.) of the exit time is a slight generalization of the similar estimate of [4] or [26]. In order to get the sub-Gaussian estimate from the diagonal estimate a new method is developed (in Section 7.1) since none of the known methods (c.f. [22], [17],[23], [30]) was directly applicable. Several steps of this new method were adapted from or at least inspired by the above works, particularly by [23] and [26]. The proof of the diagonal estimates (Section 6.) is a generalization of known methods [27],[50] and Theorem 2.3 (Section 7.,8.) generalize [22], [16].

We introduce for these set of initial conditions a short notation

(Ini) = (p_{0}) + (V D) + (SR) + (T D) + (H).

3 Scaling properties

In this section we prove the following results, which are the key to the sub-Gaussian estimates.

Theorem 3.1 If (Ini) holds, then there is an M > 1 such that for all x ∈ Γ, R ≥ 1

E(x, R) ≃ \overline{E}(x, R) ≃ λ^{−1}(x, R) ≃ ρ(x, R)V (x, R) ≃ ρ(x, R, MR)V (x, MR).  (3.1)

Theorem 3.2 If (Ini) holds, then there is a C > 1 such that for all x ∈ Γ and R > 0

\overline{E}(x, R) ≤ CE(x, R).  (\overline{E})

Corollary 3.3 If (p_{0}), (V D), (SR) and (H) holds, then

(T D) ⟺ (λ^{−1}D) ⟺ (ρD) ⟺ (ρ_{A}D).

First we shall recall some very general and useful inequalities, then assuming the elliptic Harnack inequality we can obtain inequalities in the opposite direction and get asymptotic equalities.

3.1 General inequalities

We start with some elementary observations, which will be used in the rest of the proofs and are interesting on their own.

Proposition 3.4 If (p_{0}) and (V D) hold, then

λ(x, R) ≤ CR^{−2}.

Proof. For the proof see [14] or [26, Lemma 5.3].

Lemma 3.5 For all recurrent random walks it is obvious, that

E_{x}(T_{A}) ≤ ρ(x, ∂A)μ(A).  (3.2)

Proof. By definition

E_{x}(A) = ∑_{y∈A} G^{A}(x, y) = ∑_{y∈A} \frac{μ(y)}{μ(x)}G^{A}(y, x) = ∑_{y∈A} \frac{μ(y)}{μ(x)}P (T_{x} < T_{A})G^{A}(x, x) = \frac{1}{μ(x)}G^{A}(x, x)μ(A).

Lemma 3.6 For all random walks and for all ∅ ≠ A ⊂ Γ

λ^{−1}(A) ≤ \overline{E}(A)  (λ\overline{E})

and for recurrent random walks

\overline{E}(A) ≤ \overline{ρ}(A)μ(A)  (3.3)

Proof. Assume that f ≥ 0 is the eigen function corresponding to λ = λ(A), the smallest eigenvalue of the Laplace operator Δ_{A} = I − P^{A} on A and let f be normalized so that max_{y∈A}f(y) = f(x) = 1. It is clear that

E_{x}(T_{A}) = ∑_{y∈A} G^{A}(x, y),

while Δ_{A}^{−1} = G^{A} consequently

\frac{1}{λ} = \frac{1}{λ}f(x) = G^{A}f(x) ≤ ∑_{y∈A} G^{A}(x, y) = E_{x}(T_{A}),

which gives the first statement. The second follows from the Lemma 3.5.

Proposition 3.7 For all random walks on weighted graphs and for ∅ ≠ A ⊂ B ⊂ Γ finite sets

λ(B) ≤ \frac{ρ(A, ∂B)μ(B\A)}{𝔼_{∂A}(T_{A,B})^{2}}

where T_{A,B} denotes the time of the walk reflected on A and killed when it leaves B. The initial step of the walk from x ∈ A to y ∈ Γ\A is distributed by μ_{x,y}/ ∑_{z∈A,w∈Γ\A} μ_{z,w}. This is denoted in short by 𝔼_{∂A}.

We omit the proof of this proposition since it is direct generalization of the proof of the following statement.

Proposition 3.8 (c.f. [51],[52])For all random walks on weighted graphs and R ≥ 2, M ≥ 2

λ(x, MR) ≤ \frac{ρ(x, R, MR)V (x, MR)}{E(\underline{w}, \frac{M−1}{2}R)^{2}},

where \underline{w}∈ S(x, \frac{M+1}{2}R) minimizes E(w, \frac{M−1}{2}R).

3.2 Consequences of the elliptic Harnack inequality

Before we study the mean exit time we will recall some properties of the volume.

Proposition 3.9 If (p_{0}) holds, then for all x, y ∈ Γ and R > 0 and for some C = C(p_{0}),

V (x, R) ≤ C^{R}μ(x),  (3.4)

p_{0}^{d(x,y)}μ(y) ≤ μ(x).  (3.5)

Remark 3.1 The inequality (3.4) implies that, for any fixed R; V (x, R) ≃ μ(x).

The volume doubling has a well known consequence, the so-called covering principle, which is the following

Proposition 3.10 If (p_{0}) and (V D) hold, then there is a fixed integer M such that for all x ∈ Γ, R > 0, B(x, R) can be covered at most with M balls of radius R/2.

Proposition 3.11 Assume, that Γ satisfies (p_{0}), (V D) and (H), then for all fixed K ≥ 2L, L ≥ 1 there is a C = C(K, L) > 1 such that for all x ∈ Γ

max_{y∈A} G^{x,(K+3)R}(y, x) ≤ C min_{y∈A} G^{x,(K+3)R}(y, x),  (HG)

where A = B(x, KR)\B(x, LR).

Proof. The idea of the proof is due to T. Delmotte and A. Grigor’yan (private communication). Let us assume first that R ≥ 20 and K = 2, L = 1. (The general case follows in the same way, it will be clear that this is the most restrictive case.) Denote g(a, b) = \frac{1}{μ(b)}G^{x,(K+3)R}(a, b). For two arbitrary points y, z ∈ A = B(x, 2R)\B(x, R) consider the shortest path connecting them;

y = ξ_{0} ∼ ξ_{1} ∼ ... ∼ ξ_{k} = z

where k = d(y, z). If the path runs outside of B(x, \frac{R}{4}), then the direct application of the covering principle gives the desired estimate.

CASE 1. Suppose first that each point ξ_{i} lies outside the ball B(x, \frac{R}{4}). By the iterated use of the covering principle the ball B(x, 4R) can be covered by N balls of radius s = \frac{R}{20} ≥ 1. Select out of them only those, which contain at least one of the points ξ_{i} and denote their centers by o_{j}, j = 1, 2, ..., N. We select a subset of these balls and define recursively a new listing of them. The new centers will be denoted by w_{k}. Define the union of the balls covering a ∈ Γ as U(a) = ∪{B(o_{j}, s) : j : a ∈ B(o_{j}, s)}. Let us define a_{1} = y, b_{1} = ξ_{i_{1}} if i_{1} = max(j : ξ_{j} ∈ U(a_{1})}. Denote a_{2} = ξ_{i_{1}+1} the first vertex on the path from y to z, which is not covered by U(a_{1}) . Then the recursive definition is

i_{k} = max{j : ξ_{j} ∈ U(a_{k})}

and b_{k} = ξ_{i_{k}}, a_{k+1} = ξ_{i_{k}+1}. Our procedure ends at b_{K} = z in K ≤ N steps. From the definition it is clear, that for each b_{k} there is at least one B(o_{j}, s), such that a_{k}, b_{k} ∈ B(o_{j}, s). Denote one of this ball B(w_{k}, s). It is evident from the definition, that a_{k}, b_{k}, a_{k+1} ∈ B(w_{k}, 2s) as well as the whole path is covered by the balls B(w_{k}, s) k = 1..K. We recall now that d(ξ_{j}, x) > \frac{R}{4}, consequently d(x, w_{k}) > 4s since

d(x, w_{k}) ≥ d(ξ_{j}, x) − s > \frac{R}{4} − \frac{R}{20} ≥ \frac{4R}{20} = 4s.

This means that we can compare g(x, a_{i}) ≤ Cg(x, a_{i+1}) using the Harnack inequality on B(w_{i}, 4s) and in the last ball g(x, a_{K}) ≤ Cg(x, z) which finally results that

g(x, y) ≤ C^{N}g(x, z).

CASE 2. Suppose that one of the points ξ_{i} lies in the ball B(x, \frac{R}{4}). Denote by ξ one of ξ_{i}-s which is the nearest point to x. Then we obtain

4R ≥ d(y, z) ≥ d(y, ξ) ≥ d(x, y) − d(x, ξ) ≥ R(1 − \frac{1}{4}) > \frac{3R}{4}.

Therefore, both points x, z lie in the annulus B(y, 4R) \ B(y, 3R/4). Let us connect now the points x and z by the shortest path and let η be the nearest point to y on that path. By the triangle inequality, we have

d(y, ξ) ≥ d(x, y) − d(x, ξ) and d(z, ξ) ≥ d(x, z) − d(x, ξ),

whence

d(y, z) = d(y, ξ) + d(z, ξ) ≥ d(x, y) + d(x, z) − 2d(x, ξ).

Therefore,

d(y, η) ≥ d(y, z) − d(z, η) ≥ d(y, z) − d(z, x) ≥ d(x, y) − 2d(x, ξ) > R − \frac{2R}{4} = \frac{R}{2}.

Hence, the path from x to z stays outside the ball B(y, \frac{R}{2}). Applying the argument of the first case, we obtain

g(y, x) ≤ Cg(y, z).  (3.6)

In the same way, by interchanging the points y, z, we obtain

g(z, y) ≤ Cg(z, x).  (3.7)

Since the kernel g is symmetric, (3.6) and (3.7) imply

g(y, x) ≤ C^{2}g(z, x),

which was to be proved. For small R use (p_{0}).

Proposition 3.12 If (p_{0}), (V D), (SR) and (H) hold, then there are c > 0, M ≥ 2 such that for all x ∈ Γ, R > 0

ρ(x, R, MR) ≥ cρ(x, MR).

Proof. Denote A = B(x, MR) and let us define the super-level sets of G^{A} as H_{y} = {z ∈ B(x, 2R) : G^{A}(x, z) > G^{A}(x, y)} and Γ_{y} the potential level of y using the linear interpolation on the edges (c.f. [50]). For y ∈ S(x, R)

ρ(x, MR) = ρ(x, Γ_{y}) + ρ(Γ_{y}, S_{x,MR}) ≤^{(HG)} ρ(x, R) + \frac{C}{μ(x)} min_{y∈S(x,R)} G^{A}(y, x),

which provides

ρ(x, MR) ≤ ρ(x, R) + Cρ(R, MR) ≤ \frac{1}{1 + c_{ρ}} ρ(x, MR) + Cρ(x, R, MR).

Finally it follows, that

ρ(x, MR) ≤ \frac{1 + c_{ρ}}{c_{ρ}} Cρ(x, R, MR).

Remark 3.2 The converse of this proposition is straightforward. If

ρ(x, R, MR) ≥ cρ(x, MR),

then the random walk is strongly recurrent. This follows from the shorting of S(x, R), which gives

ρ(x, MR) ≥ ρ(x, R) + ρ(x, R, MR).

Using the condition one gets

ρ(x, MR) ≥ ρ(x, R) + cρ(x, MR)

and (SR) follows. This results the following corollary.

Corollary 3.13 If (p_{0}), (V D), (SR) and (H) hold, then for R > 0

ρ(x, R, MR) ≃ ρ(x, MR).

Corollary 3.14 If (p_{0}), (V D), (SR) and (H) hold, then there is a C > 1 such that for all x ∈ Γ, R > 0

G^{x,MR}(x, x) ≤ C min_{y∈B(x,R)} G^{x,MR}(y, x).  (CG)

Proof. Denote A = B(x, MR) and let us use Proposition 3.12.

\frac{1}{μ(x)}G^{x,MR}(x, x) = ρ(x, MR) ≤^{(SR)} Cρ(x, R, MR) ≤ C max_{y∈B(x,MR)\B(x,R)} \frac{1}{μ(x)}G^{x,MR}(y, x),

where the last inequality follows from the maximum principle. The potential level of the vertex y maximizing G^{x,MR}(., x) runs inside of B(x, R) and clearly y ∈ S(x, R), hence

C max_{y∈B(x,MR)\B(x,R)} \frac{1}{μ(x)}G^{x,MR}(y, x) = C max_{y∈S(x,R)} \frac{1}{μ(x)}G^{x,MR}(y, x) ≤^{(HG)}

C min_{y∈S(x,R)} \frac{1}{μ(x)}G^{x,MR}(y, x) = C min_{y∈B(x,R)} \frac{1}{μ(x)}G^{x,MR}(y, x).

Proposition 3.15 (c.f. [53])For all random walks and for all A ⊂ B ⊂ Γ

λ(B)ρ(A, B)μ(A) < 1,  (3.8)

particularly for B = B(x, MR), A = B(x, R), x ∈ Γ, R, M > 1

λ(x, MR)ρ(x, R, MR)V (x, R) ≤ 1,  (3.9)

assuming (V D)

λ(x, MR)ρ(x, R, MR)V (MR) ≤ C  (3.10)

and for B = B(x, R), A = {x} if (p_{0}), (V D), (SR) and (H) hold, then

λ(x, R)ρ(y, R)V (x, R) ≤ C.  (3.11)

Proof. The first statement follows from the variational definition of the eigenvalue using the capacity potential between A and Γ\B. The other statements are direct consequences of the previous one.

The next proposition is an easy adaptation of [49]

Proposition 3.16 For recurrent walks if (p_{0}), (V D) and (CG) hold, then

ρ(x, MR)V (x, MR) ≃ E(x, MR),  (3.12)

in details there is a constant c > 0 such that

cV (x, MR)ρ(x, MR) ≤ E(x, MR) ≤ V (x, MR)ρ(x, MR)  (3.13)

holds and additionally (ρ) is equivalent with (E).

Proof. The upper estimate is trivial from Lemma 3.5. The lower estimate is almost as simple as the upper one.

E(x, MR) = ∑_{y∈B(x,MR)} G^{MR}(x, y) ≥ ∑_{y∈B(x,R)} \frac{μ(y)}{μ(x)}G^{MR}(y, x).

At this point one can use (CG) to get

∑_{y∈B(x,R)} \frac{μ(y)}{μ(x)}G^{MR}(y, x) ≥ \frac{1}{C} ∑_{y∈B(x,R)} \frac{μ(y)}{μ(x)}G^{MR}(x, x) = \frac{1}{C} ρ(x, MR)V (x, MR),

from which the statement follows.

Corollary 3.17 (p_{0}), (SR), (V D) and (H) imply

ρ(x, MR)V (x, MR) ≃ ρ(x, R, MR)V (x, MR) ≃ E(x, MR)  (3.14)

and (ρD) or (T D) results the multiplicative Einstein relation

ρ(x, R)V (x, R) ≃ ρ(x, R, 2R)V (x, 2R) ≃ E(x, R).  (ER)

Proof. The statement follows from Corollary 3.13 and Proposition 3.16 where the condition is (CG) given by Corollary 3.14.

3.3 Weak spatial symmetry

The following seemingly innocent statement plays a central role in the whole paper since it makes possible to change the reference point in question.

Theorem 3.18 If (Ini) holds, then there is a C ≥ 1 such that for all R > 0, x, y ∈ Γ, d(x, y) < R

ρ(y, 2R) ≤ Cρ(x, 2R).

Proof. The proof uses Proposition 3.12 and (ρD) provided by Corollary 3.17.

ρ(y, 2R) ≤^{Proposition 3.12} Cρ(y, 2R, 2MR) ≤ Cρ(x, R, (2M + 1)R) ≤^{(ρD)} Cρ(x, 2R).

Proof of Theorem 3.2. The proof is simple, it is based on the inequalities we have already shown. Assume that the maximum \overline{E}(x, R) attained at y.

\overline{E}(x, R) ≤ E(y, 2R) ≤^{(3.9)} V (y, 2R)ρ(y, 2R) ≤^{T heorem 3.18} CV (y, 2R)ρ(x, 2R)

≤^{(P D_{2}V)} CV (x, 2R)ρ(x, 2R) ≤^{(ER)} CE(x, 2R) ≤^{(T D)} CE(x, R).

Corollary 3.19 If (p_{0}),(V D) and (E) hold, then

E(x, R) ≥ cR^{2},

i.e. β ≥ 2.

Proof. The statement follows easily from Theorem 3.2, Lemma 3.6 and Proposition 3.4.

3.4 The scaling

In this subsection we summarize the results of the whole section. The main message of the results is that the elliptic Harnack inequality (and the other conditions) ensures not only the Einstein relation (ER) but several further asymptotic equalities.

Proof of Theorem 3.1. We have seen E(x, MR) ≃ ρ(x, MR)V (x, MR) in Corollary 3.16, while

ρ(x, R) ≃ ρ(x, R, MR) follows from Proposition 3.12 and Corollary 3.13. E(x, R) ≃ \overline{E}(x, R) is a direct consequence of Theorem 3.2. Finally the upper estimate λ^{−1}(x, R) ≤ \overline{E}(x, R) was given in Lemma 3.6 while the lower estimate follows from (3.11) of Proposition 3.15 and Theorem 3.2.

Cλ^{−1}(x, R) ≥ ρ(x, R)V (x, R) ≥ E(x, R) ≥ c\overline{E}(x, R).

Proof of Corollary 3.3. Thanks to Theorem 3.1 (T D) implies ⟹ (3.1) and hence the doubling property of the functions in question is evident. (T D) follows from (ρ_{A}D) or from (ρD) thanks to Corollary 3.17.

The opposite direction for (λ^{−1}D) is a bit tricky, as it needs again the change of the reference vertex and the assumption that R is large enough (R ≥ 2M).

E(x, 2R) ≤ ρ(x, 2R)V (x, 2R) ≤ λ^{−1}(x, 2R).

For the lower estimate of E(x, R) let us use (λ^{−1}D) repeatedly to get

λ^{−1}(x, 2R) ≤ Cλ^{−1}(x, \frac{R}{2M}) ≤ C\overline{E}(x, \frac{R}{2M}) ≤ Cρ(\overline{y}, \frac{R}{M})V (\overline{y}, \frac{R}{M})

where \overline{y} ∈ B(x, \frac{R}{2M}) the vertex maximizing the exit time. Now we use Theorem 3.18 to switch to x.

Cρ(\overline{y}, \frac{R}{M})V (\overline{y}, \frac{R}{M}) ≤ Cρ(\overline{y}, \frac{R}{M})V (x, \frac{R}{M}) ≤ Cρ(x, \frac{R}{M})V (x, \frac{R}{M}) ≤ Cρ(x, \frac{R}{M} , R)V (x, R) ≤ CE(x, R)

and the combination of the inequalities results (T D).

For R < 2M the time doubling property can be forced with further increase of the leading constant since E(x, R) ≥ 1 and E(x, R) ≤ Cp_{0}^{−2M} for all x ∈ Γ.

At this point the equivalence of the conditions in 1. of Theorem 2.1 has been proved.

4 Time doubling

4.1 Properties of E(x, R)

In this subsection we will investigate the consequences of time doubling.

Theorem 4.1 If (Ini) holds for the weighted graph (Γ, μ), then it satisfies (P D_{E})

Proof. We borrow some ideas from [14, Lemma 2.2]. Let us consider the l.h.s. of (P D_{2}E)

\frac{E(x, R)}{E(y, S)} = \frac{E(x, R)}{E(y, R)} \frac{E(y, R)}{E(y, S)},

from where \frac{E(y,R)}{E(y,S)} can be estimated easily by C (\frac{R}{S})^{β} and

\frac{E(x, R)}{E(y, R)} ≤ C \frac{E(x, 2R)}{E(y, 2R)} ≤ \frac{ρ(x, 2R)V (x, 2R)}{ρ(y, 2R)V (y, 2R)} ≤ C

using (V D) and Theorem 3.18, which shows (P D_{2}E).

The next relation, (P D_{3}E) follows from (P D_{2}E). Consider y : S(x, 3R − 1) and apply (P D_{2}E) to get

E(y, R) > εE(x, 3R),

where ε = (C3^{β})^{−1} . This can be rewritten as

E(\underline{y}, R) =: min_{y∈S(x,3R−1)} E(y, R) ≥ εE(x, 3R),

but it is clear that

E(x, 4R) > E(x, 3R) + E(y, R) ≥ (1 + ε)E(x, R)

and iterating this procedure enough many times we get the result. The inequality (P D_{4}E) is immediate from the strong Markovity and triangular inequality. Finally Corollary 3.19 provides (P D_{5}E).

Corollary 4.2 If (Ini) holds for the graph (Γ, μ), then the following inequalities are valid. There are D_{e}, C > 0, ν, > 0 such that for all x ∈ Γ and n > 0

e(x, 2n) ≤ D_{e}e(x, n),  (P D_{1}e)

\frac{e(x, n)}{e(y, m)} ≥ C_{e} (\frac{n}{m})^{ν} ,  (P D_{2}e)

for y ∈ B(x, e(x, n)), n ≥ m > 0 and there is an A_{e} > 1, such that, for all n > 0, x ∈ Γ

e(x, A_{e}n) ≥ 2e(x, n).  (P D_{3}e)

Proof. The statements are direct consequences of (P D_{E}).

4.2 Properties of F (R)

Here we draw the conclusion of the present section assuming (E).

Proposition 4.3 For arbitrary weighted graphs

1. (E) implies (\overline{E}) and

\overline{E}(x, R) ≃ F (R),

2. furthermore if (Ini) holds, then

(E) ⟺ (ρ) ⟺ (ρ_{A}) ⟺ (λ).

Proof. The proof is evident from Theorem 3.1 and (E).

Theorem 4.4 If (Ini) and (E) holds for the weighted graph (Γ, μ), then there is a function F such that (ED_{F}) holds furthermore there are ε > 0 and c_{0} > 0 such that

F (LR) > c_{0}L^{1+ε}F (R)  (F +)

for all L ≥ 0, R ≥ 0.

Proof. The first relation, (ED_{1}F), is direct consequence of the time doubling. The relation (ED_{2}F) follows from (ED_{1}F) easily. The inequality (ED_{4}F) is immediate from the strong markovity and triangular inequality without the use of the condition (Ini), in fact is also follows from (ED_{3}F).

The proof of B_{F} > A_{F} (in (ED_{3}F) ) starts with a special choice of the reference point. We fix an ε > 0 small constant, which will be chosen later, assume R ≥ 1 and assign an x = x_{ε,R} ∈ Γ to them satisfying

F (3R) + ε ≥ E(x, 3R).

Let us denote by τ(B) the first hitting time of a set B. Denote ξ = X_{T_{x,2R}} ∈ S(x, 2R) and split the trajectory according to T_{x,2R} as follows. E(x, 3R) can be estimated from below by

E(x, 2R) + 𝔼_{x} (𝔼_{ξ} [T_{x,3R} ∧ τ(S(x, R − 1))]) + 𝔼(I [T_{x,3R} > τ(S(x, R − 1)] (T_{x,3R} − τ(S(x, R − 1)))

≥ F (2R) + 𝔼_{x} (𝔼 (ξ, R)) + 𝔼_{x} [𝔼_{ξ} (I [T_{x,3R} > τ(S(x, R − 1)] (T_{x,3R} − τ(S(x, R − 1))))] .

The third term contains the sub case when the walk reach S(x, 2R) then returns to S(x, R − 1), let us denote this return site by ζ = X_{τ(ξ,S(x,R−1))}. Using this we get

𝔼_{x} [𝔼_{ξ} (I [T_{x,3R} > τ(S(x, R − 1)] (T_{x,3R} − τ(S(x, R − 1))))]
= 𝔼_{x} (ℙ_{ξ} (T_{x,3R} > τ(S(x, R − 1)))E_{ζ}(T_{ζ,2R}))

≥ 𝔼_{x} (P_{ζ}(T_{x,3R} > τ(S(x, R − 1))F (2R)) ≥ min_{w∈S_{x,2R}} ℙ_{w}(T_{x,3R} > τ(S(x, R − 1)))F (2R).

The probability in the above expression can be estimated using the elliptic Harnack inequality (as in Proposition 3.11) to get, that

min_{w∈S_{x,2R}} ℙ_{w}(T_{x,3R} > τ(S(x, R − 1))) ≥ c\frac{ρ(2R, 3R)}{ρ(R, 3R)} ≥ c =: c_{F} .

If c_{F} > \frac{2ε}{F (R)}, i.e. ε ≤ \frac{F (1)c_{F}}{2} the statement follows with A_{F} = 3, B_{F} = 3 + \frac{c_{F}}{2}

The relation (F +) follows from B_{F} > A_{F} immediately. Finally (ED_{5}F) follows from Corollary 3.19 and (E).

At this point the equivalence of the conditions in 1. of Theorem 2.2 has been proved. Corollary 3.3 provide the equivalence of the doubling of the corresponding functions. Furthermore assuming, that any of them is uniform in Γ and has doubling property it follows that all the others are uniform as well thanks to Theorem 3.1 and Proposition 4.3.

4.3 Properties of the sub-Gaussian kernel

As it was pointed out in [53] the convexity of certain functions plays a central role in the proof of the offdiagonal upper estimate. Though we can not prove exact convexity, this subsection will provide sufficient set of properties of the sub-Gaussian kernel to proceed.

Theorem 4.5 If (Ini) and (E) hold, then there is a c > 0 such that

ck(n, d(x, y)) ≤ k(n, d(x, z)) + k(n, d(z, y)) + 1.

The next statements collect simple, but useful properties of the kernel function k(n, R).

Lemma 4.6 In general

1. k(n, R) is non-increasing in n and non-decreasing in R,

2. for any L ∈ ℕ

Lk(n, R) ≤ k(Ln, LR)

3. and if (ED_{1}) holds, then for all R, S ∈ ℕ

F (R + S) < D_{F} (F (R) + F (S)) .

Proof. The first two statements direct consequences of the definition of k. Let us assume R ≥ S, then

F (R + S) ≤ F (2R) ≤^{(ED_{1}F)} D_{F} F (R) ≤ D_{F} (F (R) + F (S))

results the third statement.

Lemma 4.7 Assume (p_{0}) and n ≥ R > 0. If R ≥ m > k(n, R), then

\frac{n}{m} > qF (⌊\frac{R}{m}⌋).  (4.15)

Proof. The statement is a direct consequence of the definition of k(n, R).

Lemma 4.8 If (ED_{F}) holds, then for k = k(n, R)

k + 1 ≥ c (\frac{F (R)}{n})^{\frac{1}{ϕ−1}} , k + 1 ≥ c′ (\frac{R}{f(n)})^{\frac{ϕ}{ϕ−1}} and k ≤ C (\frac{R^{ϕ}}{n} )^{\frac{1}{ϕ−1}}  (4.16)

Proof. The statements are easy consequences of (ED_{F}).

Proposition 4.9 Assume (p_{0}), (ED_{4}F). If n ≥ R ≥ 2, then

1 ≤ s ≤ \frac{1}{2}k(4n, R) ⟹ \frac{n}{s} ≤ qF (⌊\frac{R}{s}⌋) .

Proof. Consider 0 ≤ l < s, m ≥ 2 and k = ms + l ≤ R. But s ≤ k/2 which gives from k ≤ R that s ≤ R/2 holds as well. Let us start with the following elementary inequalities.

\frac{n}{s} ≤ \frac{mn}{k − l} ≤ \frac{m}{2} \frac{4n}{k}.  (4.17)

On the other hand one gets

⌊\frac{R}{s}⌋ ≥ \frac{R − s}{s} > \frac{R/2}{s} = m\frac{R/2}{k − l} > \frac{m}{2} \frac{R}{k} ≥ \frac{m}{2} ⌊\frac{R}{k}⌋ .

For integers m, L > 0, F (mL) ≥ mF (L) can be seen from repeated application of (ED_{4}F). If k = k(4n, R), then

qF (⌊\frac{R}{s}⌋) ≥ mqF (⌊\frac{R/2}{k}⌋) ≥ \frac{m}{2} \frac{4n}{k} ≥^{(4.17)} \frac{n}{s}.

Proposition 4.10 If (p_{0}) and (ED_{F}) hold, then there is a C_{q} > 0 such that for all n, m, R, S ≥ 1

\frac{1}{2}k (C_{q} (n + m) , R + S) ≤ k(n, R) + k(m, S) + 1

Proof. Denote a = k(n, R), b = k(m, S)

F (⌊\frac{R + S}{a + b + 1}⌋) ≤ F (⌊\frac{R}{a + b + 1}⌋ + ⌊\frac{S}{a + b + 1}⌋ + 2)

≤ D_{F} (F (⌊\frac{R}{a + b + 1}⌋) + F (⌊\frac{S}{a + b + 1}⌋) + F (2))

< \frac{1}{q}D_{F} (\frac{n}{a + b + 1} + \frac{m}{a + b + 1} + F (2)) .

Let us recall that

F (2) ≤ D_{F} F (1) = \frac{D_{F} C_{F}}{1 − P (x, x)} ≤ D_{F} C_{F} max_{y≠x,y∼x} \frac{1}{p_{xy}} < \frac{D_{F} C_{F}}{p_{0}} =: C′.

Using a ≤ n, b ≤ m it follows that

F (⌊\frac{R + S}{a + b + 1}⌋) < \frac{1}{q} ⌈\frac{C′ (n + m)}{a + b + 1}⌉ .

This means, using Proposition 4.9, that a + b + 1 > \frac{1}{2}k(4C′(n + m), R + S).

Proposition 4.11 If (p_{0}) and (ED_{F}) hold, then there is a C_{k} > 1 such that

\frac{1}{2}k(C_{k}n, d(x, y)) ≤ k(n, d(x, z)) + k(n, d(z, y)) + 1.

Proof. The statement is immediate from Proposition 4.10 and the triangular inequality.

We finish the study of the sub-Gaussian kernel with some observations, which are using directly (F +), consequence of (ED_{3}F).

Proposition 4.12 If (F +) holds, then there are ε > 0, C > 1, such that for all n, R ∈ ℕ

k(n, R) ≤ C (\frac{F (R)}{n})^{\frac{1}{ε}} .  (4.18)

Proof. Using the definition of k = k(n, R) and (F +) one has

\frac{n}{k} ≤ qF (⌊\frac{R}{k}⌋) ≤ qCk^{−1−ε}F (k ⌊\frac{R}{k}⌋) ≤ qCk^{−1−ε}F (R) ,

which results

k^{ε} ≤ qC \frac{F (R)}{n}.

Proposition 4.13 If (F +) hold, then for all fixed A ≥ 1 there is a c > 0 such that for all n, R ≥ 1

k(An, R) ≥ ck(n, R),

and

k(n, R) + 1 ≥ ck(\frac{1}{A}n, R).

Proof. The statement follows from (F +).

Proof of Theorem 4.5. The statement follows from Proposition 4.11 and Proposition 4.13.

5 Tail of the exit time

This section contains one of the key elements of the proof, the short time sub-Gaussian estimate. The idea goes back to [4], a new proof was given in [26]. Here we prefer the original arguments in order to give a more transparent proof, showing the role of the sub-Gaussian kernel.

Theorem 5.1 Assume that the graph (Γ, μ) possesses the property (\overline{E}). Then, for all x ∈ Γ , n ≥ R ≥ 1, we have

ℙ_{x}(T_{x,R} ≤ n) ≤ exp (−c_{1}\underline{k}) ,  (LΨ)

for any positive integer \underline{k} = \underline{k}(x, n, R) ≤ R satisfying the inequality (iter). Here c_{1} > 0 is sufficiently small constant depending only on the constant C from (\overline{E})

We start with the next lemma

Lemma 5.2 ([4]) Let T, τ_{1}, τ_{2}, ..., τ_{m} be non-negative random variables such that T ≥ ∑_{k=1}^{m} τ_{i}. Assume also that, for some a ∈ (0, 1) and b > 0, and for all k = 1, 2, ..., m and t ≥ 0,

ℙ (τ_{k} ≤ t|σ(τ_{1}, ...τ_{k−1})) ≤ a + bt.  (5.1)

Then, for all t ≥ 0,

ℙ(T ≤ t) ≤ exp (2 (\frac{btm}{a})^{1/2} − m log \frac{1}{a}) .  (5.2)

The following lemma will help to ensure (5.1) in our context (c.f. [4, Lema 4.3]).

Lemma 5.3 For all A ⊂ Γ, x ∈ A, and t ≥ 0, we have

ℙ_{x}(T_{A} < t) ≤ 1 − \frac{E_{x}(A)}{2\overline{E}(A)} + \frac{t}{\overline{E}(A)}.  (5.3)

Proof. Denote n = ⌊t⌋ and observe that

T_{A} ≤ 2t + 1_{{T_{A}>t}}T_{A} ∘ θ_{n}

where θ_{n} is the time shift operator. Since {T_{A} > t} = {T_{A} > n}, we obtain, by the strong Markov property,

𝔼_{x}(T_{A}) ≤ 2t + 𝔼_{x} (1_{\{T_{A}>t\}}𝔼_{X_{n}} (T_{A})) ≤ 2t + ℙ_{x} (T_{A} > t) 2\overline{E}(A).

Applying the definition E_{x}(A) = 𝔼_{x}(T_{A}), we obtain (5.3).

Proof of Theorem 5.1. Let us denote r = ⌊\frac{R}{m}⌋ and define a series of exit times recursively

τ_{1} = T_{x,r} ,
τ_{k+1} = T_{y_{k},r} , where y_{k} = X_{τ_{k}}, for k = 1, ..., m.

Since d(X_{τ_{k+1}}, X_{τ_{k}}) < r and mr ≤ R, we see that d(X_{n}, x) < R for all n ≤ ∑_{k=1}^{m} τ_{k}. Therefore, we obtain

T_{x,R} ≥ ∑_{k=1}^{m} τ_{k} .  (5.4)

Lemma 5.3 can be applied to A = B(X_{τ_{k}}, r), we have

ℙ (τ_{k} ≤ t|σ(τ_{1}, ...τ_{k−1})) ≤ a + bn,  (5.5)

where

a = sup_{y} (1 − \frac{E(y, r)}{2\overline{E}(y, r)}) ∈ [\frac{1}{2}, 1 − ε] and b = \frac{1}{2 inf_{y} \overline{E}(y, r)} ≤ \frac{1}{2 inf_{y} E(y, r)}.  (5.6)

Having (5.4) and (5.5), we apply Lemma 5.2 which yields

ℙ_{x}(T_{x,R} ≤ n) ≤ exp (2 (\frac{bnm}{a})^{1/2} − m log \frac{1}{a}) .

Rewriting the inequality (iter) in the form

n ≤ c_{2}m min_{y∈B(x,R)} E(y, r)

and combining it with (5.6), we obtain bn ≤ \frac{1}{2}c_{2}m. If c_{2} > 0 is sufficiently small (say c_{2} = \frac{1}{16} log^{2} \frac{1}{1−ε}) then, together with 1/2 ≤ a ≤ 1 − ε, this implies

2 (\frac{bnm}{a})^{1/2} − m log \frac{1}{a} ≤ −c_{1}m,

(where c_{1} = \frac{1}{2} log \frac{1}{1−ε}), which finishes the proof of (LΨ).

This proves 4. in Theorem 2.1. The next Corollary is immediate consequence of Theorem 5.1, since we have seen in Proposition 4.3 that (E) implies (\overline{E}).

Corollary 5.4 Assume that the graph (Γ, μ) possesses the property (E). Then, for all x ∈ Γ , n ≥ R ≥ 1, we have

ℙ_{x}(T_{x,R} ≤ n) ≤ exp (−c_{Ψ}k) ,  (Ψ)

for any positive integer k = k(n, R) ≤ R satisfying the inequality (: k). Here c_{Ψ} > 0 is sufficiently small constant depending only on the constants from (\overline{E}) and (E).

6 The diagonal estimates

In this section we prove local diagonal estimates of Theorem 2.1 based on the parabolic volume and time doubling.

Theorem 6.1 If (Ini) holds, then there are c_{i}, C_{j} > 0 such that

P_{n}(x, x) ≤ C_{1} \frac{μ(x)}{V (x, e(x, n))};  (LDUE)

P_{n}(x, y) ≤ C_{2} \frac{μ(y)}{(V (x, e(x, n))V (y, e(y, n)))^{1/2}} ;  (LPUE)

and if n ≤ c_{3}E(x, R), A = B(x, R), then

P_{2n}(x, x) ≥ P_{n}^{A}(x, x) ≥ C_{4} \frac{μ(x)}{V (x, e(x, n))}.  (LDLE)

Let us define the λ− resolvent and recall the local Green function as follows (again denote A = B(x, R))

G_{λ}(x, x) = ∑_{k=0}^{∞} e^{−λk}P_{k}(x, x)

and

G^{A}(x, x) = ∑_{k=0}^{∞} P_{k}^{A}(x, y).

Lemma 6.2 If λ^{−1} = n, then

P_{2n}(x, x) ≤ cλG_{λ}(x, x).

Proof. The proof is elementary. (c.f. [27] or [51])

Lemma 6.3 If (\overline{E}) holds, then

G_{λ}(x, x) ≤ CG^{R}(x, x).

Proof. The proof can be taken from [27] or [51].

Proof of Theorem 6.1. Let us recall that (\overline{E}) follows from the conditions by Theorem 3.2. Combining the previous lemmas with λ^{−1} = n = \frac{1}{2}E(x, R) one has

P_{2n}(x, x) ≤^{Lemma 6.2} CλG_{λ}(x, x) ≤^{Lemma 6.3} CE(x, R)^{−1}G^{R}(x, x).

Now let us recall from Remark 2.2 , that G^{R}(x, x) = μ(x)ρ(x, R). Here and only here we use (SR) and (H) to be able to use (3.11) from Proposition 3.15 to proceed

μ(x)ρ(x, R) ≤ \frac{Cμ(x)}{λ(x, R)V (x, R)} ≤^{(λ\overline{E})} \frac{Cμ(x)\overline{E}(x, R)}{V (x, R)},

P_{2n} (x, x) ≤ \frac{Cμ(x)\overline{E}}{E(x, R)V (x, R)} ≤^{(\overline{E})} \frac{Cμ(x)}{V (x, R)} ≤ \frac{Cμ(x)}{V (x, e(x, n))}.

From this it is evident that P_{2n+1}(x, x) ≤ Cμ(x) V (x, e(x, 2n + 1))^{−1} and with Cauchy-Schwartz and the standard argument (c.f. [14]) one has (LP UE).

The (DLE) follows from the next simple observation Proposition 6.4 For any random walk on (Γ, μ) and for any A ⊂ Γ, w ∈ A if

\overline{E}(A) ≤ c_{0}E_{w}(A),

then for n = \frac{1}{2}E_{w}(A)

P_{2n}^{A}(w, w) ≥ \frac{cμ(w)}{μ(A)}.

Proof. Let us start from the condition using Lemma 5.3. It follows that if n = \frac{1}{2}E_{w}(A), then

ℙ_{w}(T_{R} > n) > \frac{E_{w}(A) − n}{\overline{E}(A)} = \frac{1}{2c_{0}} = c > 0

c^{2} ≤ ℙ_{w}(T_{R} > n)^{2} ≤ (e_{w}^{∗}P_{n}^{A}1)^{2} ≤ (∑_{y∈A} P_{n}^{A}(w, y)\sqrt{\frac{μ(y)}{μ(y)}})^{2} ≤ (∑_{y∈A} μ(y)) (∑_{y∈A} \frac{P_{n}^{A}(w, y)^{2}}{μ(y)} )

= μ(A) (∑_{y∈A} P_{n}^{A}(w, y)\frac{P_{n}^{A}(y, w)}{μ(w)}) ≤ \frac{1}{μ(w)}μ(A)P_{2n}^{A}(w, w),

which was to be shown.

In the possession of the above proposition the lower diagonal estimate is a simple consequence of (\overline{E}).

Proposition 6.5 If (\overline{E}) holds on (Γ, μ), then

P_{2n}(x, x) ≥ c_{1} \frac{μ(x)}{V (x, e(x, 2n))}  (6.1)

or alternatively if we assume (Ini), then

P_{2n}(x, x) ≥ c_{2} \frac{μ(x)}{V (x, e(x, n))}.  (6.2)

Proof of Proposition 6.5. We can apply P^{A} ≤ P and Proposition 6.4 for A = B(x, R), to get (6.1). The relation (6.2) follows by w = x and having (\overline{E}) thanks to Theorem 3.2 furthermore from volume doubling and the consequences of the time doubling to e(x, n).

7 Off-diagonal estimates

In this section we will assume that time doubling condition holds in conjunction with (E). The next corollary is immediate from Theorem 6.1.

Corollary 7.1 If (Ini) and (E) hold, then

P_{n}(x, x) ≤ C \frac{μ(x)}{V (x, f(n))};  (DUE)

P_{n}(x, y) ≤ C \frac{μ(y)}{(V (x, f(n))V (y, f(n)))^{1/2}} ;  (PUE)

and if n ≤ cE(x, R), A = B(x, R), then

P_{2n}(x, x) ≥ P_{n}^{A}(x, x) ≥ C \frac{μ(x)}{V (x, f(n))}.  (DLE)

7.1 Upper estimate

Theorem 7.2 (Ini) + (E) ⟹ (UE_{F})

For the proof we use the idea of (c.f. [23]) on a general inequality.

Lemma 7.3 If we assume (Ini) and (E), then there is a C > 0 such that

P_{n}(x, y) ≤ C (E_{D}(x, n)E_{D}(y, n))^{1/2} exp −\frac{c}{D} k(n, d(x, y)),

where D > 1 and

E_{D}(w, n) = ∑_{z∈Γ} \frac{p(w, z)^{2}}{μ(z)} exp \frac{1}{D} k(n, d(w, z)).

Proof. Let us recall Theorem 4.5 and use Jensen and Schwartz inequalities.( For the technical details see the Appendix.)

The next step towards the proof of (UE_{F}) is to get an upper bound for E_{D}(w, n).

Lemma 7.4 There is a C > 0 such that for all w ∈ Γ, n ∈ ℕ the conditions (Ini) and (E) imply

E_{D}(w, n) ≤ \frac{C}{V (w, f(n))}.

Proof. Let us split the sum of E_{D}. If d(w, z) < f(n), then use trivial estimate, if d(w, z) ≥ f(n) use (DUE), (P UE) and (Ψ). ( For the technical details see the Appendix.)

Proof of Theorem 7.2. Now we collect our findings. It is evident that (E) implies (\overline{E}) and by Theorem 5.1 (\overline{E}) implies (Ψ). On the other hand (P UE) is given by Theorem 6.1 consequently we can apply Lemma 7.4 in Lemma 7.3. The final step is standard to replace V (y, f(n))^{−1/2} with V (x, f(n))^{− \frac{1}{2}} C_{ε}e^{2εD_{E}k(n,d(x,y))} and choosing ε small enough. The factor 2εD_{E}k (n, d(x, y)) can be absorbed in the exponent of the exit time estimate as in [14].

7.2 Lower estimate

In this subsection we derive (LE_{F}). The key of the proof is the near diagonal lower estimate (NLE) which is given in Proposition 7.9 and 7.11.

Theorem 7.5 The following implications hold

(p_{0}) + (V D) + (ED_{F}) + (NLE) ⟹ (LE_{F})

and

(Ini) + (E) ⟹ (LE_{F}).

In the development of the lower estimate we do not need uniformity of the mean exit time till the very last step.

Definition 7.1 For a function u_{n}(x) on ℕ × V we define the time derivative as

∂_{n}u = u_{n+2} − u_{n}.

Definition 7.2 For any set U and a function u on U, denote

osc_{U} u := max_{U} u − min_{U} u.

The next two propositions are taken from [26] without any change and hence we omit their proof.

Proposition 7.6 [26, Proposition 11.2])Assume that the elliptic Harnack inequality (H) holds on (Γ, μ). Let u ∈ c_{0}(B(x, R)) satisfy in B(x, R) the equation Δ_{B(x,R)}u = f. Then for any ε > 0, there exists σ = σ(ε, H) < 1 such that for any positive r < R,

osc_{B(x,σr)}u ≤ 2 (\overline{E}(x, r) + ε\overline{E}(x, R)) max |f| .  (7.1)

Proposition 7.7 ([26, Proposition 12.1 and 12.2])For all A ⊂ Γ, x, y ∈ Γ, n ∈ ℕ

|∂_{n}p^{A}(x, y)| ≤ Cn^{−1} (p_{n}^{A}(x, x)p_{n}^{A}(y, y))^{1/2} .  (7.2)

Corollary 7.8 If (V D) and (LDUE) hold, then there are C > 1, c > 0 such that for all x, y ∈ Γ, n ∈ ℕ, d(x, y) ≤ ce(x, n)

|∂_{n}P^{B(x,R)}(x, y)| ≤ C \frac{μ(y)}{nV (x, e(x, n))}.  (7.3)

Proof. The proof is evident from the assumptions, (7.2) and (V D).

From these propositions the next local particular lower estimate follows again as in [26, Proposition 13.1].

Proposition 7.9 Assume (p_{0}), then from (LDUE), (LDLE), (\overline{E}) and (H) it follows that there are δ, c, C > 0 such that for all x, y ∈ Γ, n ∈ ℕ, R ≥ Ce(x, n)

P_{n}^{B(x,R)}(x, y) + P_{n+1}^{B(x,R)}(x, y) ≥ c\frac{μ(y)}{V (x, e(x, n))}  (LPLE)

provided that d(x, y) ≤ δe(x, n).

Proof. The proof closely follows the proof given in [26, Proposition 13.1]. ( For the technical details see the Appendix.)

Proposition 7.9 immediately imply the near diagonal lower estimate.

Proposition 7.10 Assume (Ini), then there are δ, c > 0 for which all x, y ∈ Γ, n ∈ ℕ

P̃_{n}(x, y) = P_{n}(x, y) + P_{n+1}(x, y) ≥ c\frac{μ(y)}{V (x, e(x, n))},  (LNLE)

provided that d(x, y) ≤ δe(x, n).

The next proposition embeds the above statement in our chain of proofs.

Proposition 7.11 For weighted graphs

(Ini) ⟹ (LNLE)

and if (Ini) + (E) hold, then for d(x, y) ≤ δf(n)

P_{n}^{B(x,R)}(x, y) + P_{n+1}^{B(x,R)}(x, y) ≥ c\frac{μ(y)}{V (x, f(n))},  (PLE)

furthermore

P̃_{n}(x, y) = P_{n}(x, y) + P_{n+1}(x, y) ≥ c\frac{μ(y)}{V (x, f(n))}.  (NLE)

Proof. The first statement is immediate from Theorem 6.1 and Proposition 7.10 and the rest follows imposing the extra restriction to (LP LE) and (LNLE).

Proof of Theorem 7.5. First let us point out that the second implication is the direct consequence of the first one and Proposition 7.11. Using (PLE) and Aronson’s [1] standard chaining argument the lower estimate (LE_{F}) can be easily seen. It is exhaustively elaborated for the regular volume growth case in [26, Proposition 13.2]. (See [16, Theorem 3.8 lower bound] under the volume doubling condition and the Appendix for the technical details.)

8 The parabolic Harnack inequality

In this section we show the 2. ⟹ 3. implication of Theorem 2.2.

Theorem 8.1 Assume (p_{0}), then

(UE_{F}) + (LE_{F}) + (ED_{F}) ⟹ (P H_{F}).

The proof consists of a few intermediate steps.

Proposition 8.2 Assume (p_{0}) and q < 1/16 then

(ED_{F}) + (LE_{F}) ⟹ (V D).

Proof. The (LE_{F}) directly provides the following inequality

1 ≥ \frac{1}{2} ∑_{y∈B(x,b)} P̃_{a}(x, y) ≥ ∑_{y∈B(x,b)} \frac{cμ(y)}{V (x, f(a))} exp (−Ck (a, b)) = \frac{cV (x, b)}{V (x, f(a))} exp −Ck(a, b).  (8.1)

Let us fix a = F (R), b = 2R. Using this assumptions (8.1) has the form of

1 ≥ \frac{cV (x, 2R)}{V (x, R)} exp −Ck(F (R), 2R).

Applying Proposition 4.12 it follows that k < C and hence the statement.

In order to show (P H_{F}) we need the upper and lower estimate of the solution of the parabolic equation. This should be based on the whole knowledge of (ED_{F}) and the sub-Gaussian estimates. (LE_{F}) provides estimates of P but not of P_{n}^{B(x,R)}. Denote again A = B(x, R). Following the idea of [16, Lemma 3.9 and Theorem 3.10] let us use P_{n}^{A}(., y) = P_{n}^{B(x,R)}(., y) as the solution on U as in (HP_{F}) with boundary conditions

P_{0}^{A}(w, y) = δ(w, y)
P_{k}^{A}(w, y) = 0 if w ∈ Γ \ B(x, R),

where w ∈ B(x, εR), y ∈ B(x, εKR) and ε > 0, K > 1, εK < 1. It is clear that P^{A} ≤ P so the lower estimate should be given.

Lemma 8.3 From (ED_{F}), (UE_{F}) and (LE_{F}) it follows that for a fixed 2 ≤ K ≤ \frac{1}{4q} − 1 there is an ε, 1/K > ε > 0 such that for all x ∈ Γ, R > 1

P̃_{n}^{A}(w, y) = P_{n}^{A}(w, y) + P_{n+1}^{A}(w, y) ≥ \frac{cμ(y)}{V (w, KεR)},  (PLE)

if F (εR) ≤ n ≤ F (KεR), w ∈ B(x, εR), y ∈ B(x, KεR), d(w, y) ≤ n.

Proof. For the proof see [16, Lemma 3.9 and Theorem 3.10] and for the technical details the Appendix.

Proof of Theorem 8.1. The proof generalization of the proof developed in [16, Theorem 3.10]. It uses regularity properties of F and k provided by Theorem 4.4 and Lemma 4.8 and Proposition 4.12. ( For the technical details see the Appendix.)

8.1 Behavior of the F-parabolic Harnack inequality

It is standard that if the R^{2}−parabolic Harnack inequality is true for a given profile C = {c_{1}, c_{2}, c_{3}, c_{4}, η}, then it is true for all profiles. This follows easily from the covering principle. The covering principle holds on any connected graphs (with (p_{0}) ) having the volume doubling property. The only task is to show that the test ball can be equipped with a proper metric and measure for which the volume doubling is still true. This is straightforward for R^{β} and follows easily for F (R) satisfying (ED_{F}) as well. Denote f(n) the inverse of F (R). The construction works on U = [s_{0}, s_{0} + F (R)] × B(x, R). It is clear that the box-metric on the direct product

ρ((s, y) , (t, z)) = \frac{1}{2} (d(y, z) + |f(s − s_{0}) − f(t − s_{0})|)

is suitable for our purposes. The metric balls are U′ = [s_{0} +s, s_{0} +s+F (r)]×B(y, r) of radius r centered at (y, s). The measure is induced by μ, μ((y, s)) = μ(y),

μ(U′) = V (y, r)F (r)

and it has volume doubling property on the metric balls thanks to the doubling property of the original volume and (ED_{1}F). Consequently, this setup ensures that the covering principle works on U and consequently the standard argument can be applied to show that (P H_{F}) holds for all profiles, provided that it holds for a given one.

9 Consequences of the parabolic Harnack inequality

To close the loop of the implications in Theorem 2.2. we will show the following theorem.

Theorem 9.1 Assume (p_{0}), then

(ED_{F}) + (P H_{F}) ⟹ (V D) + (H) + (ρ_{A}).

This will follow from the next proposition.

Proposition 9.2 Assume (p_{0}), then

(ED_{F}) + (P H_{F}) ⟹ (DUE), (P LE), (NLE).

Proof of Proposition 9.2. The proof is base on [16, Proposition 3.1]. It uses the regularity properties of F. ( For the technical details see the Appendix.)

Proposition 9.3 Assume (p_{0}), then

(ED_{F}) + (P H_{F}) ⟹ (V D).

Proof. The volume doubling is an easy consequence of (DUE) and (DLE) for n = E(x, R), m = E(x, 2R)

c\frac{μ(x)}{V (x, f(n))} ≤ P̃_{n}(x, x) ≤^{(P H_{F})} 2C_{H} P̃_{m}(x, x) ≤ C \frac{μ(x)}{V (x, f(m))}.  (9.1)

The first step towards the estimates of ρ is to present the upper estimate for λ^{−1}.

Proposition 9.4 If (p_{0}), (DUE), (V D) and (ED_{F}) hold, then

λ(x, R) ≥ cF^{−1}(R).

Proof. The proof uses the idea of [14, Theorem 5.4]. Assume that C_{1} > 1, n = F (C_{1}R), y, z ∈ B(x, R). At the end of the proof of Theorem 6.1 we have seen that (DUE) implies upper estimate of P_{n}(y, z) which is in our case

P_{n}(y, z) ≤ C \frac{μ(z)}{(V (y, f(n))V (z, f(n)))^{1/2}} .

For w = y or z d(x, w) ≤ R < C_{1}R = f(n) and thanks to (V D)

\frac{V (x, C_{1}R)}{V (w, C_{1}R)} ≤ C_{V} ,

which results

P_{n}(y, z) ≤ C \frac{μ(z)}{V (x, f(n))}.

If ϕ is the left eigenvector (measure) belonging to the smallest eigenvalue λ of I − P^{B(x,R)} normalized to (ϕ1) = 1, then

(1 − λ)^{n} = ϕP_{n}^{B(x,R)}1 = ∑_{y,z∈B(x,R)} ϕ(z)P_{n}(z, y) ≤ ∑_{y,z∈B(x,R)} \frac{Cμ(z)}{min_{y∈B(x,R)} V (y, f(n))}

≤ C_{V} \frac{V (x, R)}{V (x, f(n))} = C_{V} \frac{V (x, R)}{V (x, C_{1}R)} ≤ 2^{−k−1}2^{log_{2} C_{v}} < \frac{1}{2},

if C_{1} = ⌈A_{V}^{k+1}⌉ where k = ⌈log_{2} C_{V} ⌉ ∨ 1 . Using the inequality and 1 − ξ ≥ \frac{1}{2} log \frac{1}{ξ} for ξ ∈ [\frac{1}{2}, 1] where ξ = 1 − λ(x, R) one has

λ(x, R) ≥ \frac{log 2}{2n} ≥ cF (AR)^{−1} >^{(ED_{1}F)} cF (R)^{−1}.

Corollary 9.5 If (p_{0}), (ED_{F}), and (P H_{F}) hold, then

ρ(x, R, 2R) ≤ C \frac{F (R)}{V (x, R)}.

Proof. Proposition 3.15 gives

ρ(x, R, 2R) ≤ \frac{1}{λ(x, 2R)V (x, R)},

which conclude to the statement together with Proposition 9.4.

The lower estimate of ρ is quite simple in the possession of (P LE).

Proposition 9.6 If (P LE) holds, then

E(x, 2R) ≥ cF (R).

Proof. We assumed that for all x ∈ Γ, R > 1, A = B(x, 2R)

P̃_{n}^{A}(x, y) = P_{n}^{A}(x, y) + P_{n+1}^{A}(x, y) ≥ \frac{cμ(y)}{V (x, R)},

if F := F (R) ≤ n ≤ L(L − 1)F (R) =: F′, y ∈ B(x, R). It follows that

E(x, 2R) = ∑_{k=0}^{∞} ∑_{y∈B(x,2R)} P_{k}^{A}(x, y) ≥ ∑_{k=0}^{∞} ∑_{y∈B(x,R)} \frac{1}{2}P̃_{k}^{A}(x, y) ≥ ∑_{k=F}^{F′} ∑_{y∈B(x,R)} \frac{1}{2}P̃_{k}^{A}(x, y)

≥ c\frac{V (x, R)}{V (x, R)}(L − 1)^{2}F (R) ≥ cF (R).

Corollary 9.7 If (p_{0}), (ED_{F}) and (P H_{F}) hold, then

ρ(x, R, 2R) ≥ c\frac{F (R)}{V (x, R)}.

Proof. Let us recall from Proposition 3.8 that

λ(x, 2R) ≤ \frac{ρ(x, R, 2R)V (x, 2R)}{E(\underline{w}, \frac{1}{4}R)^{2}},

which means that using Proposition 9.6 follows the statement

ρ(x, R, 2R) ≥ c\frac{λ(x, 2R)F^{2}(2R)}{V (x, 2R)} ≥ c\frac{F (x, 2R)}{V (x, 2R)}.

Proof of Theorem 9.1. On one hand the result follows from Proposition 9.3, Corollary 9.5, 9.7. On the other hand the elliptic Harnack inequality evidently follows from the parabolic one. This finishes the proof of 3. ⟹ 1. in Theorem 2.2 and hence the whole proof is complete.

Proof of Theorem 2.3. One has to recognize that in the course of the proof 2. ⟹ 3. ⟹ 1. of Theorem 2.2 recurrence or strong recurrence was not used, consequently this theorem is proved as well.

10 Appendix

Proof of Lemma 7.3. From Theorem 4.5 we know that

\frac{c}{D} k(n, d(x, y)) ≤ \frac{1}{D} (k (n, d(x, z)) + k (n, d(z, y)) + 1) .

This means that

exp \frac{1}{D} (−ck (n, d(x, y)) + k (n, d(x, z)) + k (n, d(z, y))) ≥ c′,

hence

P_{2n}(x, y) = ∑_{z∈Γ} P_{n}(x, z)P_{n}(z, y) = ∑_{z∈Γ} P_{n}(x, z)\frac{μ(y)}{μ(z)}P_{n}(y, z)

≤ μ(y) ∑_{z∈Γ} \frac{P_{n}(x, z)}{μ(z)^{1/2}} \frac{P_{n}(y, z)}{μ(z)^{1/2}}Ce^{− \frac{1}{D} (−ck(n,d(x,y))+k(n,d(x,z))+k(n,d(z,y)))}

≤ Cμ(y) exp (−\frac{c}{D} k (n, d(x, y))) (∑_{z∈Γ} \frac{p(x, z)^{2}}{μ(z)} exp \frac{1}{D} k (n, d(x, z)))^{1/2}

× (∑_{z∈Γ} \frac{p(y, z)^{2}}{μ(z)} exp \frac{1}{D} k (n, d(z, y)))^{1/2} .

Proof of Lemma 7.4. Let us assume first that d(w, z) < 2f(n) in the summa of E_{D}. In this case it follows from Proposition 4.12 that

k(n, d(w, z)) ≤ C \frac{F (d(w, z))}{n} < \frac{F (2f(n))}{n} ≤ C,

hence

\frac{P_{n}(w, z)^{2}}{μ(z)} exp \frac{1}{D} k (n, d(z, y)) ≤ C \frac{P_{n}(w, z)^{2}}{μ(z)} ≤ C ∑_{d(w,z)<2f(n)} \frac{P_{n}(w, z)P_{n}(z, w)}{μ(w)}

≤ C ∑_{z∈Γ} \frac{P_{n}(w, z)P_{n}(z, w)}{μ(w)} ≤^{(DUE)+(V D)} \frac{C}{V (w, f(n))}.  (10.2)

Let us consider the summa of ”far away” vertices.

∑_{d(w,z)≥2f(n)} \frac{P_{n}(w, z)^{2}}{μ(z)} exp \frac{1}{D} k (n, d(z, y)) ≤ ∑_{d(w,z)≥2f(n)} P_{n}(w, z) exp \frac{1}{D} k (n, d(z, y)) max_{z} \frac{P_{n}(w, z)}{μ(z)}.

The max can be handled as usual using (P UE)

max_{z} \frac{P_{n}(w, z)}{μ(z)} ≤ \frac{C}{V (w, f(n))} (\frac{V (w, f(n))}{V (z, f(n))})^{1/2} ≤ \frac{C}{V (w, f(n))} (\frac{V (w, d(w, z))}{V (z, f(n))})^{1/2}

≤^{(V D)} \frac{C}{V (w, f(n))} (\frac{d(w, z)}{f(n)})^{α/2} ≤ \frac{C}{V (w, f(n))}C_{ε} exp \frac{εα}{2} \frac{d(w, z)}{f(n)}.

Here we recall from Lemma 4.8 that

\frac{R}{f(n)} ≤ (\frac{R}{f(n)})^{\frac{ϕ}{ϕ−1}} ≤ C (k(n, R) + 1) ,

where k = k(n, R) ≥ 1 follows from the condition R = d(w, z) ≥ 2f(n), consequently

max_{z} \frac{P_{n}(w, z)}{μ(z)} ≤ \frac{C}{V (w, f(n))}C_{ε} exp \frac{εα}{2} (k (n, d(w, z)) + 1) .

Applying this in the sum

∑_{d(w,z)≥2f(n)} \frac{P_{n}(w, z)^{2}}{μ(z)} exp \frac{1}{D} k (n, d(z, w)) ≤ \frac{C}{V (w, f(n))} ∑_{r=2f(n)}^{∞} ∑_{z∈S(w,r)} P_{n}(w, z) exp (\frac{εα}{2} + \frac{1}{D} ) k (n, r)

= \frac{C}{V (w, f(n))} ∑_{r=2f(n)}^{∞} P_{n}(w, S(w, r)) exp (\frac{εα}{2} + \frac{1}{D} ) k (n, r) .

Here P_{n}(w, S(w, r)) can be estimated using (Ψ) to get further upper bound by

≤ \frac{C}{V (w, f(n))} ∑_{r=2f(n)}^{∞} exp [(\frac{εα}{2} + \frac{1}{D} ) k (n, r) − c_{Ψ}k (n, r)]

and if ε is chosen ε = \frac{c_{Ψ}}{3α} and \frac{1}{D} = \frac{c_{Ψ}}{3} , then finally we obtain

\frac{C}{V (w, f(n))} ∑_{r=2f(n)}^{∞} exp [(\frac{εα}{2} + \frac{1}{D} ) k − c_{Ψ}k]  (10.3)
≤ \frac{C}{V (w, f(n))} ∑_{r=2f(n)}^{∞} exp −\frac{c_{Ψ}}{3} k (n, r) ≤ \frac{C}{V (w, f(n))} ∑_{r=2f(n)}^{∞} exp −\frac{c_{Ψ}}{3} c\frac{r}{f(n)},  (10.4)

where the last inequality is again from Lemma 4.8 and the last sum is evidently bounded by a constant depending only on c_{Ψ} and ϕ. The estimates in (10.2) and (10.4) provide the statement.

Proof of Proposition 7.9. Let us fix x ∈ Γ , n ∈ ℕ and set

R = e (x, \frac{n}{ε}) ,  (10.5)

for small enough positive ε. So far we assume only that ε satisfies the restriction in (DLE) but later one more upper bound on ε will be imposed. Denote A := B(x, R) and introduce the function

ũ(y) := p_{n}^{A}(x, y) + p_{n+1}^{A}(x, y).

By the hypothesis (DLE), we have u(x) ≥ cV (x, e(n))^{−1}. Let us show that

|ũ(x) − ũ(y)| ≤ \frac{c}{2} \frac{1}{V (x, f(n))},  (10.6)

provided that d(x, y) ≤ δf(n), which would imply u(y) ≥ \frac{c}{2}V (x, f(n))^{−1}, hence proving (P LE). The function u(y) is in class c_{0}(A) and solves the equation Δu(y) = f(y), where

f(y) := p_{n+2}^{A}(x, y) − p_{n}^{A}(x, y).

The on-diagonal upper bound (DUE) implies, by Corollary 7.8,

max |f| ≤ \frac{C}{nV (x, f(n))}.  (10.7)

By (H) and Proposition 7.6, we have, for any 0 < r < R and for some σ = σ(ε^{2}) ∈ (0, 1),

osc_{B(x,σr)}ũ ≤ 2 (\overline{E}(x, r) + ε^{2}\overline{E}(x, R)) max |f| .

From the assumption (\overline{E}) we can estimate \overline{E} with E . Estimating max |f| by (10.7), we obtain

osc_{B(x,σr)}u ≤ C \frac{E(x, r) + ε^{2}E(x, R)}{V (x, f(n))}.

Choosing r to satisfy r = εR and substituting from (10.5) n = εE(x, R), we obtain

osc_{B(x,σr)}ũ ≤ C \frac{ε^{2}E(R)}{nV (x, f(n))} = \frac{εC}{V (x, f(n))}.

From this it follows that

osc_{B(x,σr)}ũ ≤ \frac{c}{2} \frac{1}{V (x, f(n))},  (10.8)

provided that ε is enough small, which implies

|ũ(x) − ũ(y)| ≤ \frac{c}{2} \frac{1}{V (x, f(n))},

if d(x, y) ≤ δf(n).

Proof of Theorem 7.5. The classical proof generalizes automatically to the recent situation hence we give here just the key step of the proof. Assume that R = d(x, y), δe(n) < d ≤ εn and consider a sequence of vertices o_{i} ∈ Γ for i = 1, 2.. = k = k(cn, R), o_{0} = x, o_{k} = y where is c(ε, δ) > 0 a small constant. Define

d(o_{i,}o_{i+1}) ≤ ⌊\frac{R}{k}⌋ =: r and m = ⌊\frac{n}{k}⌋ − 1.

The key trick is that

3r ≤ δf(m)  (10.9)

provides the condition of (P LE), but this holds with the right choice of the constants. The inequality (10.9) holds if

qF (⌊\frac{R}{k + 1}⌋) < q (\frac{δ}{3})^{ϕ} \frac{n}{k + 1}

with k = k(q (\frac{δ}{3})^{ϕ} n, R) by definition. It follows now that

r < f ((c\frac{δ}{3})^{ϕ} m) ≤ \frac{δ}{3}f(m).

Using this we apply (P LE) for z_{i} ∈ B(o_{i}, r) =: B_{i}, with d(z_{i}, z_{i+1}) ≤ 3r ≤ δe(n) in the form

P̃_{m}(z_{i}, z_{i+1}) ≥ c_{l} \frac{μ(z_{i+1})}{V (z_{i}, f(n))}.

This can be applied to get

P̃_{n}(x, y) ≥ ∑_{(z_{1},..z_{k−1})∈B_{1}×..B_{k−1}} \frac{c_{l}μ(z_{1})}{V (x, r)} \frac{c_{l}μ(z_{2})}{V (o_{1}, r)}...\frac{c_{l}μ(y)}{V (o_{k−1}, r)} ≥ c′ \frac{μ(y) exp (−k log 1/c_{l})}{V (x, f(n))}.

using Lemma 13.6 in [26]. Finally we get (LE_{F}) from Proposition 4.13 removing c = q (c\frac{δ}{3})^{ϕ} from k(cn, d(x, y)) with a further increase of the leading constant in the exponent and decreasing in front. For the trivial d(x, y) ≤ δf(n) and d(x, y) > εn cases see the arguments in [26].

Proof of Lemma 8.3. Let us recall that from the (LE_{F}) we have

P̃_{n}(w, y) = P_{n}(w, y) + P_{n+1}(w, y) ≥ \frac{cμ(y)}{V (w, KεR)} exp −Ck(n, d(w, y)) ≥ c\frac{μ(y)}{V (w, KεR)},  (10.10)

where the last inequality follows from k < C, which is provided that by (F +) and Proposition 4.12. Let us define r̃ by

\frac{μ(w)}{μ(y)}r̃_{n}(w) := P̃_{n}(y, w) − P̃_{n}^{A}(y, w).

It can be decomposed according to the exit time and place

\frac{μ(w)}{μ(y)}r̃_{n}(w) ≤ ∑_{z∈S(x,R)} ∑_{m=0}^{n−1} P_{y}(T_{R} = m, X_{m} = z)P̃_{n−m}(z, w) =: ∑_{z∈S(x,R)} ∑_{m=0}^{n−1} \frac{μ(w)}{μ(z)}P̃_{n−m}(w, z)π_{m}^{A}(y, z),

where it is clear that

∑_{m=0}^{n−1} ∑_{z} π_{m}^{A}(y, z) ≤ 1.

From the upper estimate, monotonicity in the second variable of k and from d(w, z) ≥ (1 − ε)R with 0 ≤ m < n

\frac{1}{μ(z)}P̃_{n−m}(w, z) ≤ \frac{C}{V (w, f(n − m))} exp (−ck(n − m, (1 − ε)R))

= \frac{1}{V (w, KεR)} (\frac{CV (w, KεR)}{V (w, f(n − m))} exp (−ck((n − m) , (1 − ε)R))) .

We will show that with the right choice of ε the term in the brackets can be bounded by c/2. Let us start with

\frac{CV (w, KεR)}{V (w, f(n − m))} exp (−ck((n − m) , (1 − ε)R)) ≤ C (\frac{KεR}{f(n − m)})^{α} e^{−ck} ≤ C exp (α\frac{2εR}{f(n − m)} − ck) .

Now we use Lemma 4.8

k(n − m, KεR) + 1 ≥ c (\frac{KεR}{f(n − m)})^{\frac{ϕ}{ϕ−1}} ≥ c\frac{KεR}{f(n − m)}

and get

C exp [α\frac{KεR}{f(n − m)} − ck] ≤ C exp (\frac{KεαC}{1 − ε} (\frac{(1 − ε)R}{f (n − m)})^{\frac{ϕ}{ϕ−1}} − ck)

≤ C exp (−c (1 − \frac{KεαC}{1 − ε} ) (\frac{(1 − ε)R}{f(n)})^{\frac{ϕ}{ϕ−1}} ) .

The original restrictions to n and R can be used to receive

C exp [α\frac{KεR}{f(n − m)} − ck] ≤ C exp −cε^{−1}.

This can be made arbitrarily small with the right choice of ε. This results

\frac{μ(y)}{μ(z)}P̃_{2n−m}(w, z) ≤ \frac{c}{2},

which ends the proof using (10.10).

Proof of Theorem 8.1. To complete the proof of (P H_{F}) we need the estimates of the solution u = u_{n}(w) ≥ 0. This can be given with the aid of another solution v_{n}, 0 ≤ v_{n} ≤ u_{n}, v_{n} = u_{n} on the smaller ball B = B(x, 2εR). Denote again A = B(x, R). The solution v can be estimated using the fundamental solutions P_{n−m}^{A}(x, z).

v_{n}(y) = ∑_{(m,z)∈V} P_{n−m}^{A}(x, z)π_{m}^{B}(y, z),  (10.11)

where V = [1, n] × S(x, 2εR) ∪ {0} × B(x, 2εR) and 0 ≤ π_{m}^{B}(y, z) ≤ 1. This, means again that it is enough to show (P H_{F}) for h(n, w) = P_{n−m}^{A}(w, z), which is a solution on [m, m + F (2εR)] × B(x, 2εR) for all but fixed m ≤ F (c_{2}R). The constants in (HP_{F}) can be chosen as follows. η = ε, c_{1} = ε^{2}/2, c_{2} = ε^{2}, c_{3} = 2ε^{2}, c_{4} = 4ε^{2} and it is enough to show that

h(n_{⊝}, w_{⊝}) ≤ Ch(n_{⊕}, w_{⊕}).

Lemma 8.3 provides the lower estimate ( choosing K = 2 )

P̃_{n_{⊕}−m}^{A}(w_{⊕}, z) ≥ \frac{cμ(z)}{V (w_{⊕}, 2εR)} for \{ \begin{matrix}w_{⊕} ∈ B(x, εR) \\ z ∈ B(x, 2εR) \\ F (c_{3}R) ≤ (n_{⊕} − m) ≤ F (c_{4}R) \\ d(w_{⊕}, z) ≤ n_{⊕} − m. \end{matrix} .

Let us observe that if d(w_{⊕}, z) > n_{⊕} − m and d(w_{⊕}, w_{⊝}) ≤ n_{⊕} − n_{⊝}, then d(w_{⊝}, z) ≥ d(w_{⊕}, z) − d(w_{⊕}, w_{⊝}) > n_{⊕} − m − (n_{⊝} − n_{⊕}) = n_{⊝} − m and consequently f(n_{⊝}, w_{⊝}) = P_{n_{⊝}−m}^{A}(w_{⊝}, z) = 0.

For the upper estimate we start with P_{n−m}^{A}(w, z) ≤ P_{n−m}(w, z) and apply the (P UE). If m = 0, F (c_{1}R) ≤ n_{⊝} ≤ F (c_{2}R), then

P_{n_{⊝}}^{A}(w_{⊝}, z) ≤ P_{n_{⊝}}(w_{⊝}, z) ≤ \frac{Cμ(z)}{V (w_{⊝}, f(n_{⊝}))}

≤ \frac{Cμ(z)}{V (w_{⊝}, c_{1}R)} ≤ \frac{Cμ(z)}{V (w_{⊝}, 2εR)}.

If 0 < m ≤ n_{⊝} and w_{⊝} ∈ B(x, εR), z ∈ S(x, 2εR) ( hence d(w_{⊝}, z) ≥ εR ), then the upper estimate provides for F (c_{1}R) ≤ n_{⊝} − m ≤ F (c_{2}R)

P_{n_{⊝}−m}^{A}(w_{⊝}, z) ≤ P_{n_{⊝}−m}(w_{⊝}, z) ≤ \frac{Cμ(z) exp (−ck ((n_{⊝} − m) , d(w_{⊝}, z)))}{V (w_{⊝}, f(n_{⊝} − m))}.

which can be handled exactly as at the end of Lemma 8.3 to get

P_{n_{⊝}}^{A}(w_{⊝}, z) ≤ \frac{Cμ(z)}{V (w_{⊝}, 2εR)}.

The proof ends with the comparison of V (w_{.}, 2εR) with V (x, 2εR) provided by the finite number of iterated use of (P D_{2}V) based on the covering principle.

Proof of Proposition 9.2. Let us show an upper estimate of the transition probability first. Let us fix y ∈ Γ and let u_{n}(x) = P_{n}(x, y) the solution on [0, F (2R)]×B(x, 2R). Denote η = \frac{1}{2}, n = F (c_{2}R), choose

c_{1} < c_{2} < 1 arbitrarily, and define L = ⌈C_{F} ⌉ , where C_{F} is the constant in (ED_{2}F), c_{3} = (\frac{L}{C_{F}} )^{\frac{1}{ϕ}} c_{2}, and

c_{4} = (\frac{L}{c_{0}})^{1/ε} c_{2}, where ε, c_{0} are the constants in (F +). This assumptions ensure that

F (c_{3}R) ≤ Ln ≤ F (c_{4}R)

and let us observe that c′_{3} < c′_{4} since c_{0} < 1 < C_{F} and ϕ ≥ 2 thanks to (F +).

c′_{3} = (\frac{L}{C_{F}} )^{\frac{1}{ϕ}} < (\frac{L}{c_{0}} )^{1/ε} = c′_{4}.

Assume that d(x, y) ≤ R, d(z, y) ≤ R, and apply (P H_{F}), then

P_{n}(x, y) ≤ C_{H} P̃_{Ln}(z, y)  (10.12)

P_{n}(x, y) ≤ \frac{C_{H}}{V (x, R)} ∑_{z∈B(x,R)} μ(z)P̃_{Ln}(z, y) = \frac{C_{H}μ(y)}{V (x, R)} ∑_{z∈V (x,R)} P̃_{Ln}(y, z) ≤ C \frac{μ(y)}{V (x, R)} ≤ C \frac{μ(y)}{V (x, f(n))}

The next step is to show (P H_{F}) ⟹ (P LE) and as a consequence (NLE). We need here a particular choice of the profile of the parabolic Harnack inequality since we should apply it twice. First we use it for a particular solution ũ of the parabolic equation with boundary conditions ũ_{k}(w) defined on U = [0, F (c_{4}2R)] × B(x, 2R), A = B(x, 2R), n = F (R) ( c_{4} specified later) as follows

u_{k}^{A}(w) = \{ \begin{matrix}1 if 0 ≤ k ≤ n \\ ∑_{z∈B(x,R)} P̃_{k−n}^{A}(w, z) if k > n \end{matrix} ,

then we apply (P H_{F}) to P_{m}^{A} getting P_{m}^{A}(z, y) ≤ C_{H} P̃_{Lm}^{A}(x, y) for z ∈ B(x, R). We define two series of constants c_{i}, c′_{i} for two profiles, C, C′ keeping η = η′ = \frac{1}{2} fixed. Assume c′_{1} < 1 < c′_{2}, i.e. F (c′_{1}R) < F (R) =: n < F (c′_{2}R). Let us fix c′_{3} > c′_{2} > 1 and L := C_{F} (c′_{3})^{ϕ} + 1 ≥ 2, where C_{F} is the constant from

(ED_{2}F). Finally c′_{4} = (\frac{L−1}{c_{0}})^{1/ε} where ε, c_{0} are the constants from (F +). With this choice it is clear that (L − 1) F (R) =: (L − 1) n > F (c′_{3}R) and (L − 1)n ≤ (L − 1)F (R) ≤ F (c′_{4}R). Thank to c_{0} < 1 < C_{F} and (F +) which imply ϕ ≥ 2 it follows that c_{3} < c_{4}. This profile is used to get the following estimate for ũ.

\frac{1}{C_{H}} = \frac{1}{C_{H}} u_{n}^{A}(x) ≤ u_{Ln}^{A}(y) = ∑_{z∈B(x,R)} P̃_{Ln−n}^{A}(y, z) ≤ C ∑_{z∈B(x,R)} P̃_{m}^{A}(y, z),

where m = (L − 1)F (R). The same construction of an other profile works starting with F (c_{1}R) < m < F (c_{2}R) using simply L instead of L − 1. We can apply (P H_{F}) to receive

∑_{z∈B(x,R)} P̃_{m}^{A}(y, z) ≤ ∑_{y∈B(x,R)} 2C_{H} P̃_{Lm}^{A}(x, y)\frac{μ(z)}{μ(y)} = \frac{2C_{H}V (x, R)}{μ(y)}P̃_{Lm}^{A}(x, y).

Our derivation ends with

P̃_{L(L−1)F (R)}^{A}(x, y) ≥ c\frac{μ(y)}{V (x, R)},

P̃_{k}^{A}(x, y) ≥ c\frac{μ(y)}{V (x, R)},  (PLE)

if F (R) ≤ k ≤ L(L − 1)F (R) and d(x, y) ≤ R, furthermore we have

P̃_{k}(x, y) ≥ c\frac{μ(y)}{V (x, f(k))}.

This proves (P LE) and (NLE).

References

[1] Aronson D.G. Non-negative solutions of linear parabolic equations. Ann. Scuola Norm. Sup. Pisa cl. Sci (3) 22 (1968), 607-694; Addendum 25 (1971), 221-228.

[2] Alexander S.; Orbach, R. Density of states on fractals,”fractions”,. J. Physique (Paris) Lett. 43 (1982), L625-L631.

[3] Barlow, M.T.; Nualart, D. Diffusion on Fractals. in: Lectures on probability theory and statistics. Lectures from the 25th Saint-Flour Summer School held July 10–26, 1995. Edited by P. Bernard. Lecture Notes in Mathematics, 1690. Springer-Verlag, Berlin, 1998.

[4] Barlow, M.T.; Bass, F.R., The Construction of the Brownian Motion on the Sierpisnki Carpet. Ann. Inst. H. Poincaré Probab. Statist. 25 (1989), no. 3, 225-257.

[5] Barlow, M.T.; Bass, F.R., Random walks on graphical Sierpinski carpets. in: Picardello, M. A.; Woess, W. (editors): ”Random Walks and Discrete Potential Theory”, Proceedings (Cortona 1997), Symposia Mathematica XXXIX, Cambridge University Press, 1999.

[6] Barlow, M.T., Bass, F.R., Divergence form operators on fractal-like domains. J. Funct. Anal. 175 (2000), no. 1, 214-247.

[7] Barlow, M.T., Coulhon, T., Grigor’yan, Manifolds and graphs with slow heat kernel decay. preprint.

[8] Barlow, M.T.; Hambly, B. Transition density estimates for Brownian motion on scale irregular Sierpinski gaskets. Ann. Inst. H. Poincaré Probab. Statist. 33 (1997), no. 5, 531-559.

[9] Chavel, I. Large time heat Diffusion on Riemannian manifolds. Lecture notes, (unpublished), 1998.

[10] Cheeger, J., Differentiability of Lipschitz functions on Metric Measure Spaces. Geom. Funct. Anal. 9 (1999), no. 3, 428-517.

[11] Cheeger J.; Yau, S.-T. A lower bound for the heat kernel. Comm. Pure Appl. Math. 34 (1981), no. 4,465-48.

[12] Coulhon, T. Analysis on infinite graphs with regular volume growth. JE 2070 No 17/18, (November 1997), Université de Cergy-Pontoise.

[13] Coulhon, T. Ultranontractivity and Nash type inequalities. J. Funct. Anal. 141 (1996), no. 2, 510–539.

[14] Coulhon, T.; Grigor’yan A. Random walks on graphs with regular volume growth. Geom. Funct. Anal. 8 (1998), no. 4, 656-701.

[15] Chung, F.R.K. Spectral Graph Theory CBMS Regional Conference Series in Mathematics, 92. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997.

[16] Delmotte, T.; Parabolic Harnack inequality and estimates of Markov chains on graphs. Rev. Mat. Iberoamericana 15 (1999), no. 1, 181–232.

[17] Davies, E.B. Heat kernels and spectral theory Cambridge University Press Cambridge, 1989.

[18] Doyle, P.G.; Snell, J.L. Random walks and electric networks Carus Mathematical Monographs, 22. Mathematical Association of America, Washington, DC, 1984.

[19] Einstein, A. Über die von der molekulakinetishen Theorie der Wärme gefoderte Bewegung von in ruhenden flüssigkeite suspendierten Teilchen. Annalen der Physik 17 (1905).

[20] Fukushima, M. Dirichlet forms and Markov processes. North Holland Kodansh, 1980.

[21] Fukushima, M.; Oshima, Y.; Takeda M. Dirichlet forms and symmetric Markov Processes de Gruyter Studies in Mathematics, 19. Walter de Gruyter & Co., Berlin, 1994.

[22] Fabes, E.; Stroock., D. A new proof of the Moser’s parabolic Harnack inequality using the old ideas of Nash. Arch. Rational Mech. Anal. 96 (1986), no. 4, 327–338.

[23] Grigor’yan, A. Gaussian upper bounds for the heat kernel on arbitrary manifolds. J. Differential Geometry 45 (1997), 33-52.

[24] Grigor’yan, A. Analytic and geometric background of recurrence and non-explosion of the Brownian motion on the Riemannian manifolds. Bull. Amer. Math. Soc. (N.S.) 36 (1999), no. 2, 135–249.

[25] Gromov M. Groups of polynomial growth and expanding maps. Publ. Math. Inst. H. Poincaré Probab. Statist. 53 (1981), 57-73.

[26] Grigor’yan, A.; Telcs, A. Sub-Gaussian estimates of heat kernels on infinite graphs. to appear in Duke Math. J.

[27] Hambly, B.M. Brownian motion on a random recursive Sierpinski gasket. Ann. Probab. 25 (1997), no. 3, 1059–1102.

[28] Holopainen, I. Volume growth, Green’s functions and parabolicity of ends. Duke Math. J. 97 (1999), no. 2, 319–346.

[29] Hebisch W.; Saloff-Coste, L. On the relation between elliptic and parabolic Harnack inequalities. preprint [30] Hebisch W.; Saloff-Coste, L. Gaussian estimates for Markov chains and random walks on groups. Ann.

Probab. 21 (1993), 673-709.

[31] Kesten, H. Subdiffusive behavior of random walks on a random cluster Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), 425-487.

[32] Kemeny, J.G.; Snell, J.L.; Knapp, A.W.; Denumerable Markov Chains. Springer, 1976.

[33] Lax, P.D. Linear Algebra. John Wiley & Sons, 1996.

[34] Ledoux, M. The geometry of Markov diffusion generators, lecture notes preprint, 1998.

[35] LinsdstrØm, T. Brownian motion on nested fractals Mem. Amer. Math. Soc. 83 (1990), no. 420.

[36] Moser, J. On Harnack’s Theorem for elliptic differential equations, Comm. Pure and Appl.Math. 16 (1964), 101-134.

[37] Moser, J. On Harnack’s theorem for parabolic differential equations Comm. Pure and Appl.Math 24 (1971), 727-740.

[38] Mandelbrot, B.B. The fractal geometry of nature W.H. Freeman San Francisco, 1992.

[39] Mathieu, P. Hitting times and spectral gap inequalities. Ann. Inst. H. Poincaré Probab. Statist. 33 (1997), no. 4, 437–465.

[40] Mosco, U. Dirichlet form and self-similarity, A.M.S. /IP Studies in Advanced Mathematics 8 1998.

[41] Osserman, R. The isoperimetric Inequality, Bull. A.M.S. 84:6 (1978), 1181-1238.

[42] Pittet, Ch.; Saloff-Coste, L. A survey on the relationship between volume growth, isoperimetry, and the behavior of simple random walk on Cayley graphs, with samples. preprint.

[43] Röckner, M.Dirichlet forms on infinite-dimensional ”manifold-like” state spaces: a survey of recent results and some prospects for the future. Probability towards 2000 (New York, 1995), 287–306, Lecture Notes in Statist., 128, Springer, New York, 1998.

[44] Sturm, K-Th Diffusion processes and heat kernels on metric spaces. Ann. Probab. 26:1 (1998), 1-55.

[45] Stannat, W. The theory of generalized Dirichlet forms and its application in analysis and stochastic Mem. Amer. Math. Soc. 142 (1999), no. 678.

[46] Saloff-Coste, L. Isoperimetric Inequalities and decay of iterated kernels for almost-transitive Markov chains Combinatorics Probability and Computing 4 (1995), 419-442.

[47] Saloff-Coste, L. A note on Poincaré, Sobolev and Harnack inequalities. Duke Math. J. IMRN 2 (1992), 27-38.

[48] Stroock, D.W.;Varadhan, S.R.S.; Multidimensional diffusion processes. Springer Berlin, 1979.

[49] Telcs, A. Random Walks on Graphs, Electric Networks and Fractals. Probab. Theory Related. Fields 82, (1989), 435-449.

[50] Telcs, A. Spectra of Graphs and Fractal Dimensions I. Probab. Theory Related. Fields 85 (1990), 489-497.

[51] Telcs, A. Spectra of graphs and Fractal dimensions II. J. Theoret. Probab. 8 (1995), 77-96.

[52] Telcs, A. Fractal Dimension and Martin Boundary of Graphs to appear in Studia Sci. Math. Hungar.

[53] Telcs, A. Local sub-Gaussian estimates on Graphs, the strongly recurrent case. to appear in Electron. J. Probab.

[54] Varopoulos, R. Th. Hardy-Littlewood theory for semigroups. J. Funct. Anal. 63 (1985), 215-239.

[55] Varopoulos, R.; Saloff-Coste, L.; Coulhon, Th.; Analysis and geometry on Groups. Cambridge University Press, 1993.

[56] Vicsek, T. Random walks on bond percolation clusters. Zeitschrift für Physik B 45, 153-157.

[57] Wang, F-Y. Functional inequalities, semigroup properties and spectrum estimates. preprint.

[58] Weaver, N. Lipschitz algebras. World Scientific to appear.

[59] Wiener N. Differential space. J. Math. Phys. Mass. Techn. 2 (1923), 131-174.

[60] Woess, W. Random walks on infinite graphs and groups - a survey on selected topics. Bull. London Math. Soc. 26 (1994), no. 1, 1–60.

András Telcs

IMC Graduate School of Business, Budapest Zrínyi u. 14 H-1051 Budapest Hungary

   E-mail: h197tel@ella.hu