CHEEGER’S INEQUALITIES FOR GENERAL SYMMETRIC

FORMS AND EXISTENCE CRITERIA FOR SPECTRAL GAP

Mu-Fa Chen and Feng-Yu Wang

(Beijing Normal University)

Abstract. In this paper, some new forms of the Cheeger’s inequalities are established for general (maybe unbounded) symmetric forms (Theorem 1.1 and Theorem 1.2), the resulting estimates improve and extend the ones obtained by Lawler and Sokal (1988) for bounded jump processes. Furthermore, some existence criteria for spectral gap of general symmetric forms or general reversible Markov processes are presented (Theorem 1.4 and Theorem 3.1), based on the Cheeger’s inequalities and a relationship between the spectral gap and the first Dirichlet and Neumann eigenvalues on local region.

1. Introduction

The Cheeger’s inequalities^{[1]} are well known and widely used in geometric analysis, they provide a practical way to estimate the first eigenvalue of Laplacian in terms of volumes. These inequalities were then established for bounded jump processes by Lawler and Sokal^{[7]} (in which, a detail comment on the earlier study and references is included). The first aim of the paper is to establish the inequalities for general (maybe unbounded) symmetric forms.

Let (E, E) be a measurable space with reference probability measure π. Consider the symmetric form D with domain D(D):

D(f, g) = \frac{1}{2} ∫ J(dx, dy)(f(x) − f(y))(g(x) − g(y)) + ∫ K(dx)f(x)g(x),  f, g ∈ D(D)
D(D) = {f ∈ L^{2}(π) : D(f, f) < ∞}.

where J is a symmetric measure: J(dx, dy) = J(dy, dx). Without loss of generality, we assume that J({(x, x)} : x ∈ E) = 0.

We are interested in the following two quantities:

λ_{0} = inf{D(f, f) : π(f^{2}) = 1},  (1.1)
λ_{1} = inf{D(f, f) : π(f) = 0, π(f^{2}) = 1}.  (1.2)

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 60J25, 60J75, 47A75.

Key words and phrases. Cheeger’s inequality, spectral gap, Neumann and Dirichlet eigenvalue, jump process.

Research supported in part by NSFC (No. 19631060), Qiu Shi Sci. & Tech. Found., DPFIHE, MCSEC and MCMCAS. Research at MSRI is supported in part by NSF grant DMS-9701755.

We remark that in these definitions, the usual condition “f ∈ D(D)” is not needed since D(f, f) = ∞ for all f ∈ L^{2}(π) \ D(D). We even do not assume in some cases the density of D(D) in L^{2}(π). In what follows, whenever λ_{1} is considered, the killing measure K(dx) is setting to be zero. In this case, we have λ_{0} = 0 and λ_{1} is known as the spectral gap of the symmetric form (D, D(D)).

Define the Cheeger’s constants as follows:

h = inf_{π(A)>0} \frac{J(A × A^{c}) + K(A)}{π(A)},  (1.3)
k = inf_{π(A)∈(0,1)} \frac{J(A × A^{c})}{π(A)π(A^{c})},  (1.4)
k′ = inf_{π(A)∈(0,1/2]} \frac{J(A × A^{c})}{π(A)} = inf_{π(A)∈(0,1)} \frac{J(A × A^{c})}{π(A) ∧ π(A^{c})},  (1.5)

where a ∧ b = min{a, b}. Clearly, k/2 ≤ k′ ≤ k and it is easy to see that k′ can be varied over whole (k/2, k). For instance, take E = {0, 1}, K = 0, J({i} × {j}) = 1 for i ≠ j and π(0) = p ≤ 1/2, π(1) = 1 − p. Then k′/k = 1 − p.

Recall that for a given reversible jump process, we have a q-pair (q(x), q(x, dy)): q(x, E) ≤ q(x) ≤ ∞ for all x ∈ E. Throughout the paper, we assume that q(x) < ∞ for all x ∈ E. The reversibility simply means that the measure π(dx)q(x, dy) is symmetric, which gives us automatically a measure J. Then, the killing measure is given by K(dx) = π(dx)d(x), where d(x) = q(x) − q(x, E) is called the non-conservative quantity in the context of jump processes. A jump process is called bounded if sup_{x∈E} q(x) < ∞. In this case (or more generally, if ∥J(·, E) + K∥_{op} < ∞, where ∥ · ∥_{op} denotes the operator norm from L_{+}^{1}(π) := {f ∈ L^{1}(π) : f ≥ 0} to ℝ_{+}, then), for the corresponding form, we have D(D) = L^{2}(π). For more details, refer to [2].

Theorem (Lawler & Sokal). Take J(dx, dy) = π(dx)q(x, dy) and suppose that ∥J(·, E)+ K/2∥_{op} ≤ M < ∞. Then, we have

h ≥ λ_{0} ≥ \frac{h^{2}}{2M} .  (1.6)

Next, if additionally K = 0, then

k ≥ λ_{1} ≥ max \{\frac{κk^{2}}{8M} , \frac{k^{′2}}{2M} \},  (1.7)

where

κ = inf_{X,Y} sup_{c∈ℝ} \frac{(𝔼|(X + c)^{2} − (Y + c)^{2}|)^{2}}{1 + c^{2}} ≥ 1,

the infimum is taken over all i.i.d. random variables X and Y with 𝔼X = 0 and 𝔼X^{2} = 1.

In what follows, we consider directly the general symmetric measure J whenever it is possible. In other words, we do not require the existence of a kernel of a modification of J(dx, ·)/π(dx), for which some extra conditions on (E, E) are needed.

We now turn to discuss our general setup. Note that the lower bounds given in (1.6) and (1.7) decrease to zero as M ↑ ∞. So the results would lost their meaning if we go directly from bounded case to the unbounded forms. More seriously, when we adopt a general approximation procedure to reduce the unbounded case to the bounded one (cf. [2; Theorem 9.12]), the lower bounds given above usually vanish as we go to the limit. To overcome the difficulty, one needs some trick. Here we propose a comparison technique. That is, comparing the original form with some other forms introduced below.

Take and fix a non-negative, symmetric function r ∈ E × E and a non-negative function s ∈ E such that

∥J^{(1)}(·, E) + K^{(1)}∥_{op} ≤ 1,  L_{+}^{1}(π) → ℝ_{+},  (1.8)

where

J^{(α)}(dx, dy) = I_{\{r(x,y)>0\}} \frac{J(dx, dy)}{r(x, y)^{α}},  K^{(α)}(dx) = I_{\{s(x)>0\}} \frac{K(dx)}{s(x)^{α}},  α ≥ 0.

For jump processes, one may simply choose

r(x, y) = q(x) ∨ q(y) = max{q(x), q(y)} and s(x) = d(x).

We remark that when α < 1, the operator J^{(α)}(·, E)+K^{(α)} from L_{+}^{1}(π) to ℝ_{+} may no longer be bounded. Correspondingly, we have symmetric forms D^{(α)} defined by (J^{(α)}, K^{(α)}). Therefore, with respect to the form D^{(α)}, according to (1.1)—(1.5), we can define λ_{0}^{(α)}, λ_{1}^{(α)} and the Cheeger’s constants h^{(α)}, k^{(α)} and k^{(α)′} (α ≥ 0). However, in what follows, we need only three cases α = 0, 1/2 and 1. When α = 0, we return to the original form and so the superscript “(α)” is omitted from our notations.

The next two results are our new forms of the Cheeger’s inequalities.

Theorem 1.1. Suppose that (1.8) holds. We have

λ_{0} ≥ \frac{h^{(1/2)}^{2}}{2 − λ_{0}^{(1)}} ≥ \frac{h^{(1/2)}^{2}}{1 + \sqrt{1 − h^{(1)}^{2}}} .  (1.9)

Theorem 1.2. Let K = 0 and (1.8) hold. Then, we have

λ_{1} ≥ (\frac{k^{(1/2)}}{\sqrt{2} + \sqrt{2 − λ_{1}^{(1)}}} )^{2} ,  (1.10)

λ_{1} ≥ \frac{k^{(1/2)}^{′2}}{1 + \sqrt{1 − k^{(1)}^{′2}}} .  (1.11)

When ∥J(·, E) + K∥_{op} ≤ M < ∞, the simplest choice of r and s are: r(x, y) ≡ M and s(x) ≡ M. Then, (1.8) holds and moreover h^{(1/2)} = h/\sqrt{M}, k^{(1/2)}′ = k′/\sqrt{M}, h^{(1)} = h/M and k^{(1)}′ = k′/M. Hence, by (1.9) and (1.11), we get

λ_{0} ≥ M(1 − \sqrt{1 − h^{2}/M^{2}} ) = \frac{h^{2}}{M(1 + \sqrt{1 − h^{2}/M^{2}} )} ∈ [\frac{h^{2}}{2M} , \frac{h^{2}}{M} ].

and

λ_{1} ≥ M(1 − \sqrt{1 − k^{′2}/M^{2}} ) = \frac{k^{′2}}{M(1 + \sqrt{1 − k^{′2}/M^{2}} )} ∈ [\frac{k^{′2}}{2M} , \frac{k^{′2}}{M} ].  (1.12)

Therefore, for the lower bounds, (1.9) improves (1.6) and (1.11) improves (1.7). More essentially, the lower bound (1.11) is often good enough so that the approximation procedure [2; Theorem 9.12] mentioned above becomes practical. However, we will not go to this direction. In the context of Markov chains on finite graphs, (1.12) was obtained before by

Chung [5]. Applying (1.12) to J^{(1)}, we get λ_{1}^{(1)} ≥ 1 − \sqrt{1 − k^{(1)}^{′2}}. From this and (1.10),

we obtain λ_{1} ≥ (\frac{k^{(1/2)}}{\sqrt{2} + \sqrt{1 + \sqrt{1 − k_{1}^{(1)}^{′2}}}} )^{2} which is indeed controlled by (1.11) since

k^{(α)} ≤ 2k^{(α)′}. This means that (1.11) is usually more practical than (1.10) except a good lower bound of λ_{1}^{(1)} is known in advance. However, (1.10) and (1.11) are not comparable even in the case of E = {0, 1}. See also the discussion in the second paragraph below Lemma 2.2.

In view of Theorem 1.2, we have λ_{1} > 0 whenever k^{(1/2)} > 0. We now study some more explicit conditions for the Cheeger’s constants appeared in Theorem 1.2. To state the result, we should use the operators corresponding to the forms. For a jump process, the operator corresponding to (D^{(α)}, D(D^{(α)})) can be expressed by the following simple form

Ω^{(α)}f(x) = ∫ I_{[r(x,y)>0]} \frac{q(x, dy)}{r(x, y)^{α}}[f(y) − f(x)] + I_{[s(x)>0]} \frac{d(x)}{s(x)^{α}} f(x).

Next, we need some local quantities of λ_{0} and λ_{1}. First, for B ∈ E with π(B) ∈ (0, 1), let λ_{1}^{(α)}(B) and k^{(α)}(B) be defined by (1.2) and (1.4) with E, π and D replaced respectively by B, π^{B} := π(· ∩ B)/π(B) and

D_{B}^{(α)}(f, f) = \frac{1}{2} ∫_{B×B} J^{(α)}(dx, dy)(f(y) − f(x))^{2}.  (1.13)

Second, define

λ_{0}^{(α)}(B) = inf {D^{(α)}(f, f) : π(f^{2}) = 1, f|_{B^{c}} = 0}.

As usual, we call λ_{0}^{(α)}(B) and λ_{1}^{(α)}(B) respectively the (generalized) first Dirichlet and Neumann eigenvalue on B. It is a simple matter to check that as in (1.7), k^{(α)}(B) ≥ λ_{1}^{(α)}(B).

For A ∈ E, put M_{A}^{(α)} = ess sup_{π}_{A}J^{(α)}(dx, A^{c})/π(dx), where ess sup_{π} denotes the essential

supremum with respect to π.

Theorem 1.3. Let K = 0. Given α ≥ 0 and B ∈ E with π(B) > 1/2. Suppose that there exist a function φ^{(α)} with δ_{1}^{(α)}(φ^{(α)}) := ess sup_{J^{(α)}}|φ^{(α)}(x) − φ^{(α)}(y)| < ∞ and a symmetric operator (Ω^{(α)}, D(Ω^{(α)})) corresponding to the form (D^{(α)}, D(D^{(α)})) such that D(Ω^{(α)}) ⊃ {I_{A} : A ∈ E, A ⊂ B} and γ_{B^{c}}^{(α)} := − sup_{B^{c}} Ω^{(α)}φ^{(α)} > 0. Then, we have

k^{(α)} ≥ k^{(α)}′ ≥ \frac{k^{(α)}(B) γ_{B^{c}}^{(α)} [2π(B) − 1]}{k^{(α)}(B) δ_{1}^{(α)}(φ^{(α)}) [2π(B) − 1] + π(B)^{2}[δ_{1}^{(α)}(φ^{(α)})M_{B}^{(α)} + γ_{B^{c}}^{(α)}]}.

Usually, for locally compact E, we have k^{(α)}(B) > 0 and M_{B}^{(α)} < ∞ for all compact B. Then the result means that k^{(α)}′ > 0 provided δ_{1}^{(α)}(φ^{(α)}) < ∞ and γ_{B^{c}}^{(α)} > 0 for large enough B.

Up to now, we have discussed the lower bound of λ_{1} by using the Cheeger’s constants. However, Theorem 1.3 is indeed a modification of the second approach we are going to study. That is, estimating λ_{1} in terms of local λ_{0} and λ_{1} on subsets of E. The last method has been used recently in the context of diffusions by Wang [9] and it indeed works for general reversible processes. The details of the next two results for general situation are delayed to Section 3. Here, we restrict ourselves to the symmetric forms introduced above.

It is the position to state our first criterion for λ_{1} > 0.

Theorem 1.4. Let K = 0. Then for any A ⊂ B with 0 < π(A), π(B) < 1, we have

\frac{λ_{0}(A^{c})}{π(A)} ≥ λ_{1} ≥ \frac{λ_{1}(B)[λ_{0}(A^{c})π(B) − 2M_{A}π(B^{c})]}{2λ_{1}(B) + π(B)^{2}[λ_{0}(A^{c}) + 2M_{A}]}.  (1.14)

As we mentioned before, usually, λ_{1}(B) > 0 for all compact B. Hence the result means that λ_{1} > 0 iff λ_{0}(A^{c}) > 0 for some compact A. Because, we can first fix such an A and then make B large enough so that the right-hand side of (1.14) becomes positive.

Finally, we present an upper bound of λ_{1} which provides us a necessary condition for λ_{1} > 0 and can qualitatively be sharp as illustrated by Example 4.5.

Theorem 1.5. Let K = 0, r > 0, J-a.e. and (1.8) hold. If there exists φ ≥ 0 such that

0 < δ_{2}(φ) := ess sup_{J}|φ(x) − φ(y)|^{2}r(x, y) < ∞,

then

λ_{1} ≤ \frac{δ_{2}(φ)}{4} sup \{ε^{2} : ε ≥ 0, π(e^{εφ}) < ∞\}.

Consequently, λ_{1} = 0 if there exists φ ≥ 0 with 0 < δ_{2}(φ) < ∞ such that π(e^{εφ}) = ∞ for all ε > 0. In particular, when J(dx, dy) = π(dx)q(x, dy), δ_{2}(φ) can be replaced by δ′_{2}(φ) := ess sup_{π} ∫ |φ(x) − φ(y)|^{2}q(x, dy) < ∞, without using the function r and (1.8).

We mention that the study on the leading eigenvalue of a bounded integral operator is indeed included in our general setup. Consider the operator P on L^{2}(π): P f(x) = ∫ p(x, dy)f(y), generated by an arbitrary kernel p(x, dy) with M := sup_{x} p(x, E) < ∞. Let π(dx)p(x, dy) be symmetric for a moment. Clearly, the spectrum of P on L^{2}(π) is determined by the one of M − P. Note that

⟨f, (M − P)f⟩_{π} = \frac{1}{2} ∫ π(dx)p(x, dy)[f(x) − f(y)]^{2} + ∫ π(dx)[M − p(x, E)]f(x)^{2}.

Thus, the largest (non-trivial) eigenvalue of the integral operator P can be deduced from λ_{0} or λ_{1} treated in the paper. Finally, by using a symmetrizing procedure, all the results presented here can be extended to the non-symmetric forms. Refer to [2; Chapter 9] or [7] for instance.

The remainder of the paper is organized as follows. Section 2 is devoted to the proofs of Theorems 1.1—1.3. At the end of the section, a different approach to handle the unbounded symmetric forms is presented. A general existence criterion for spectral gap is presented in Section 3, which also contains the proofs of Theorems 1.4 and 1.5. All the results concerning with the spectral gap are illustrated by Markov chains in the last section.

2. Proofs of Theorems 1.1—1.3

We begin this section with the functional representation of the Cheeger’s constants. The proof is essential the same as in [7] and [8; §3.3] for the bounded situation and hence omitted.

Lemma 2.1. For every α ≥ 0, we have

h^{(α)} = inf \{\frac{1}{2} ∫ J^{(α)}(dx, dy)|f(x) − f(y)| + K^{(α)}(f) : f ≥ 0, π(f) = 1\},

k^{(α)} = inf {∫ J^{(α)}(dx, dy)|f(x)−f(y)| : f ∈ L_{+}^{1}(π), ∫ π(dx)π(dy)|f(x)−f(y)|=1}

= inf { ∫ J^{(α)}(dx, dy)|f(x) − f(y)| : f ∈ L_{+}^{1}(π), π(|f − π(f)|) = 1},

k^{(α)′} = inf \{\frac{1}{2} ∫ J^{(α)}(dx, dy)|f(x) − f(y)| : f ∈ L_{+}^{1}(π), min_{c∈ℝ} π(|f − c|) = 1\}.

Proof of Theorem 1.1. The idea of the proof is based on [7].

Let E^{∗} = E ∪ {∞}. For any f ∈ E, define f^{∗} on E^{∗} by setting f^{∗} = fI_{E}. Next, define J^{∗(α)} on E^{∗} × E^{∗} by

J^{∗(α)}(C) = \{ \begin{matrix}J^{(α)}(C), & C ∈ E × E, \\ K^{(α)}(A), & C = A × \{∞\} or \{∞\} × A, A ∈ E, \\ 0, & C = \{∞\} × \{∞\}. \end{matrix}

We have J^{∗(α)}(dx, dy) = J^{∗(α)}(dy, dx) and

∫ J^{(α)}(dx, E)f(x)^{2} + K^{(α)}(f^{2}) = ∫ J^{∗(α)}(dx, dy)f^{∗}(x)^{2},  (2.1)
D^{(α)}(f, f) = \frac{1}{2} ∫ J^{∗(α)}(dx, dy)(f^{∗}(y) − f^{∗}(x))^{2},  (2.2)
\frac{1}{2} ∫ J^{(α)}(dx, dy)|f(y)−f(x)|+∫ K^{(α)}(dx)|f(x)|= \frac{1}{2}∫ J^{∗(α)}(dx, dy)|f^{∗}(y)−f^{∗}(x)|. (2.3)

Therefore, for f with π(f^{2}) = 1, by (2.1)–(2.3), (1.8), part (1) of Lemma 2.1 and Cauchy-Schwarz inequality,

h^{(1)}^{2} ≤ \{\frac{1}{2} ∫ J^{∗(1)}(dx, dy)|f^{∗}(y)^{2} − f^{∗}(x)^{2}|\}^{2}

≤ \frac{1}{2}D^{(1)}(f, f) ∫ J^{∗(1)}(dx, dy)[f^{∗}(y) + f^{∗}(x)]^{2}

= \frac{1}{2}D^{(1)}(f, f)\{2 ∫ J^{∗(1)}(dx, dy)[f^{∗}(y)^{2}+f^{∗}(x)^{2}]−∫ J^{∗(1)}(dx, dy)[f^{∗}(y)−f^{∗}(x)]^{2}\}

≤ D^{(1)}(f, f)[2 − D^{(1)}(f, f)].

This implies that D^{(1)}(f, f) ≥ 1 − \sqrt{1 − h^{(1)}^{2}} and so

λ_{0}^{(1)} ≥ 1 − \sqrt{1 − h^{(1)}^{2}}.  (2.4)

Next, by (1.8), part (1) of Lemma 2.1 and another use of the Cauchy-Schwarz inequality, we obtain

h^{(1/2)}^{2} ≤ \{\frac{1}{2} ∫ J^{∗(1/2)}(dx, dy)|f^{∗}(y)^{2} − f^{∗}(x)^{2}|\}^{2}

≤ \frac{1}{2}D(f, f) ∫ J^{∗(1)}(dx, dy)[f^{∗}(y) + f^{∗}(x)]^{2}

≤ D(f, f)[2 − D^{(1)}(f, f)] ≤ D(f, f)[2 − λ_{0}^{(1)}].  (2.5)

¿From this and (2.4), the required assertion follows. □

Proof of Theorem 1.2. a) First, we prove (1.10). Let f ∈ D(D) with π(f) = 0 and π(f^{2}) = 1. Set g = f + c, c ∈ ℝ. Similar to (2.5), we have

{ ∫ J^{(1/2)}(dx, dy)|g(y)^{2} − g(x)^{2}|}^{2} ≤ 4D(f, f)[2(1 + c^{2}) − D^{(1)}(f, f)]
≤ 4D(f, f)[2(1 + c^{2}) − β]

for all β : 0 ≤ β < λ_{1}^{(1)} ≤ 2. Hence by Lemma 2.1, we have

D(f, f) ≥ \frac{1}{4[2(1 + c^{2}) − β]}\{ ∫ J^{(1/2)}(dx, dy)|g(y)^{2} − g(x)^{2}|\}^{2} ≥ \frac{κ_{β}}{4} k^{(1/2)}^{2}  (2.6)

where κ_{β} is the same as κ defined below (1.7) but replacing the denominator 1 + c^{2} with 2(1 + c^{2}) − β. To estimate κ_{β}, we adopt an optimizing procedure which will be used several times subsequently. Set γ = 𝔼|X| ∈ (0, 1]. It is known that

lim_{c→±∞} \frac{(𝔼|(X + c)^{2} − (Y + c)^{2}|)^{2}}{2(1 + c^{2}) − β} = 2(𝔼|X − Y |)^{2} ≥ 2(𝔼|X|)^{2} = 2γ^{2}

and when c = 0, 𝔼|X^{2} − Y^{2}| ≥ 2(1 − 𝔼|X|) = 2(1 − γ) (cf. [7] or [2; §9.2]). Thus,

κ_{β} ≥ inf_{γ∈(0,1]} max \{2γ^{2}, \frac{4(1 − γ)^{2}}{2 − β} \}.  (2.7)

We now need an elementary fact.

Lemma 2.2. Let f and g be continuous functions on [0, 1] and satisfy f(0) < g(0) and f(1) > g(1). Suppose that f is increasing and g is decreasing. Then

inf_{γ∈[0,1]} max{f(γ), g(γ)} = f(γ_{0}),

where γ_{0} is the unique solution to the equation f = g on [0, 1].

Applying Lemma 2.2 to (2.7), we get

κ_{β} ≥ \frac{4}{(\sqrt{2} + \sqrt{2 − β} )^{2}} .

Combining this with (2.6) and then letting β ↑ λ_{1}^{(1)}, we obtain (1.10).

It is worthy to mention that the estimate just proved can be sharp. To see this, simply consider E = {0, 1}, J({i}, {j}) = 1 (i ≠ j) and π_{0} = π_{1} = 1/2. Then k^{(1/2)} = λ_{1}^{(1)} = λ_{1} = 2. Moreover, the same example shows that in contract to (1.9), the analog of (1.9)

“λ_{1} ≥ k^{(1/2)}^{2}/[4(2 − λ_{1}^{(1)})]” or “λ_{1} ≥ k^{(1/2)}^{′2}/[2 − λ_{1}^{(1)})]” does not hold.

b) Define

D̃_{B}^{(α)}(f, g) = \frac{1}{2} ∫_{B×B} J^{(α)}(dx, dy)[f(y) − f(x)]^{2} + ∫_{B} J^{(α)}(dx, B^{c})f(x)^{2}.

It is easy to see that

λ_{0}(B) = inf {D̃_{B}(f, f) : π(f^{2}I_{B}) = 1}.

Let

h_{B}^{(α)} = inf_{A⊂B, π(A)>0}\frac{J^{(α)}(A×(B \ A))+J^{(α)}(A×B^{c})}{π(A)} = inf_{A⊂B, π(A)>0} \frac{J^{(α)}(A×A^{c})}{π(A)}.  (2.8)

Then by Theorem 1.1, we have λ_{0}(B) ≥ h_{B}^{(1/2)}^{2}/[1 + \sqrt{1 − h_{B}^{(1)}^{2}} ].

Next, we prove that

λ_{1} ≥ inf_{π(B)≤1/2} λ_{0}(B).

For each ε > 0, choose f_{ε} with π(f_{ε}) = 0 and π(f_{ε}^{2}) = 1 such that λ_{1} + ε ≥ D(f_{ε}, f_{ε}). Next, choose c_{ε} such that π(f_{ε} < c_{ε}), π(f_{ε} > c_{ε}) ≤ 1/2. Set f_{ε}^{±} = (f_{ε} −c_{ε})^{±} and B_{ε}^{±} = {f_{ε}^{±} > 0}. Then

λ_{1} + ε ≥ D(f_{ε} − c_{ε}, f_{ε} − c_{ε})

= \frac{1}{2} ∫ J(dx, dy)[|f_{ε}^{+}(y) − f_{ε}^{+}(x)| + |f_{ε}^{−}(y) − f_{ε}^{−}(x)|]^{2}

≥ \frac{1}{2} ∫ J(dx, dy)(f_{ε}^{+}(y) − f_{ε}^{+}(x))^{2} + \frac{1}{2} ∫ J(dx, dy)(f_{ε}^{−}(y) − f_{ε}^{−}(x))^{2}

≥ λ_{0}(B_{ε}^{+})π((f_{ε}^{+})^{2}) + λ_{0}(B_{ε}^{−})π((f_{ε}^{−})^{2})

≥ inf_{π(B)≤1/2} λ_{0}(B)π((f_{ε}^{+})^{2} + (f_{ε}^{−})^{2}) = (1 + c_{ε}^{2}) inf_{π(B)≤1/2} λ_{0}(B) ≥ inf_{π(B)≤1/2} λ_{0}(B).

Because ε is arbitrary, we obtain the required conclusion.

Finally, combining the above two assertions together, we obtain

λ_{1} ≥ inf_{π(B)≤1/2} \frac{h_{B}^{(1/2)}^{2}}{1 + \sqrt{1 − h_{B}^{(1)}^{2}}} ≥ inf_{π(B)≤1/2} \frac{inf_{π(B)≤1/2} h_{B}^{(1/2)}^{2}}{1 + \sqrt{1 − h_{B}^{(1)}^{2}}}

≥ \frac{inf_{π(B)≤1/2} h_{B}^{(1/2)}^{2}}{1 + \sqrt{1 − inf_{π(B)≤1/2} h_{B}^{(1)}^{2}}} = \frac{k^{(1/2)}^{′2}}{1 + \sqrt{1 − k^{(1)}^{′2}}} □

Proof of Theorem 1.3. The proof is split into two lemmas given below. Noticing that α is fixed, we may and will omit the superscript “(α)” everywhere in the next two lemmas and their proofs for simplicity. □

Lemma 2.3. Let B ∈ E with 2π(B) > 1. Then

k′ ≥ \frac{h_{B^{c}}k(B)(2π(B) − 1)}{k(B)(2π(B) − 1) + 2π(B)^{2}(M_{B} + h_{B^{c}})},

where h_{B} is defined by (2.8).

Proof. We need only to consider the case that h_{B^{c}}k(B) > 0. For any A ∈ E with π(A) ∈ (0, 1/2], let γ = π(AB)/π(A). Then

\frac{J(A × A^{c})}{π(A)} = \frac{1}{2π(A)}∫ J(dx, dy)[I_{A}(y)−I_{A}(x)]^{2} ≥ \frac{1}{2π(A)} ∫_{B×B}J(dx, dy)[I_{A}(y)−I_{A}(x)]^{2}
≥ \frac{k(B)π^{B}(A)π^{B}(A^{c})}{π(A)} ≥ \frac{π(B) − 1/2}{π(B)^{2}}k(B)γ.  (2.9)

Here, in the last step, we have used π(AB) ≤ π(A) ≤ 1/2. On the other hand, we have

h_{B^{c}}π(AB^{c}) ≤ \frac{1}{2} ∫ J(dx, dy)[I_{AB^{c}}(x) − I_{AB^{c}}(y)]^{2} = \frac{1}{2} ∫ J(dx, dy)|I_{A^{c}∪B}(x) − I_{A^{c}∪B}(y)|.

Noticing that J is symmetric and

|I_{A^{c}∪B}(x) − I_{A^{c}∪B}(y)| ≤ |I_{A^{c}}(x) − I_{A^{c}}(y)| + I_{B×B^{c}+B^{c}×B}|I_{AB}(x) − I_{AB}(y)|,

we obtain

h_{B^{c}}(1 − γ) = \frac{h_{B^{c}}π(AB^{c})}{π(A)} ≤ \frac{J(A × A^{c})}{π(A)} + M_{B}γ.

Combining this with (2.9) and applying Lemma 2.2, we get

\frac{J(A × A^{c})}{π(A)} ≥ inf_{γ∈[0,1]} max \{(π(B) − 1/2)π(B)^{−2}k(B)γ, h_{B^{c}} − (M_{B} + h_{B^{c}})γ\}

= \frac{h_{B^{c}}k(B)(2π(B) − 1)}{k(B)(2π(B) − 1) + 2π(B)^{2}(M_{B} + h_{B^{c}})}. □

Lemma 2.4. Let φ satisfy δ_{1}(φ) < ∞. If γ_{B} = − sup_{B} Ωφ > 0, then h_{B} ≥ γ_{B}/δ_{1}(φ) > 0.

Proof. For any A ⊂ B, we have

γ_{B}π(A) ≤ ∫_{A}[−Ωφ]dπ = \frac{1}{2} ∫ J(dx, dy)(I_{A}(x) − I_{A}(y))(φ(x) − φ(y))

≤ \frac{δ_{1}(φ)}{2} ∫ J(dx, dy)|I_{A}(x) − I_{A}(y)| = δ_{1}(φ)J(A × A^{c}).

Hence, h_{B} ≥ γ_{B}/δ_{1}(φ). □

To conclude this section, we discuss a different way to deal with the general symmetric forms. In contrast to the previous approach, we now keep (J, K) to be the same but change the L^{2}-space. To do so, let p be a measurable function and satisfy α_{p} := ess inf_{π}p > 0, β_{p} := π(p) < ∞ and ∥J(·, E) + K∥_{op} ≤ β_{p} (L_{+}^{1}(π_{p}) → ℝ_{+}), where π_{p} = pπ/β_{p}. For jump processes, one may take p(x) = q(x) ∨ r for some r ≥ 0. From this, one sees the main restriction of the present approach: ∫ π(dx)q(x) < ∞, since we require that π(p) < ∞. Except this point, the approach is not comparable with the previous one (see Example 4.5 and Example 4.7 given below).

Next, define h_{p}, k_{p} and k′_{p} by (1.3)–(1.5) respectively with π replaced by π_{p} and then divided by β_{p}. For instance, k′_{p} = inf_{π_{p}(A)≤1/2} J(A × A^{c})/π(pI_{A}).

Theorem 2.5. Let p, α_{p}, β_{p} and π_{p} be given above. Define λ_{p,i} (i = 0, 1) by (1.1) and (1.2) with π replaced by π_{p}. Then, we have

λ_{i} ≥ \frac{α_{p}}{β_{p}} λ_{p,i},  i = 0, 1.  (2.10)

In particular,

λ_{0} ≥ α_{p}(1 − \sqrt{1 − h_{p}^{2}} )  (2.11)

and when K = 0,

λ_{1} ≥ max \{\frac{κ}{8}α_{p}k_{p}^{2}, α_{p}(1 − \sqrt{1 − k_{p}^{′2}} )\}.  (2.12)

Proof. a) We prove that L^{∞}(π) is dense in D(D) in the D-norm: ∥f∥_{D}^{2} = D(f, f) + π(f^{2}). The proof is similar to [2; Lemma 9.7]. First, we show that L^{∞}(π) ⊂ D(d). Because 1 ∈ L^{1}(π_{p}) and ∥J(·, E) + K∥_{op} ≤ β_{p}, we have J(E, E) + K(E) ≤ β_{p} < ∞. Thus,

D(f, f) ≤ ∫ J(dx, dy)[f(y)^{2} + f(x)^{2}] + ∫ K(dx)f(x)^{2}
≤ 2∥f∥_{∞}^{2}(J(E, E) + K(E)) < ∞,

and hence f ∈ D(D). Next, let f ∈ D(D) and set f_{n} = (−n) ∨ (f ∧ n). Then f_{n} ∈ D(D),

|f_{n}(y) − f_{n}(x)| ≤ |f(y) − f(x)|  and  |f_{n}(x)| ≤ |f(x)|  (2.13)

for all x, y and n. Clearly, π((f_{n} − f)^{2}) → 0. Moreover, since D(f_{n} − f, f_{n} − f) ≤ 4D(f, f) < ∞ by (2.13), we have D(f_{n} − f, f_{n} − f) → 0 by (2.13) and the dominated convergence theorem. Therefore, ∥f_{n} − f∥_{D} → 0.

b) Here, we prove (2.10) for i = 1 only since the proof for i = 0 is similar and even simpler. Then, (2.11) and (2.12) follows from (1.7) and the comment right after Theorem 1.2 with M = β_{p}.

Because L^{∞}(π) ⊂ L^{2}(π_{p}) and L^{2}(π_{p}) is just the domain of the form D(f, f) on L^{2}(π_{p}), by definition of λ_{1} and λ_{1,p}, it suffices to show that π_{p}(f^{2})−π_{p}(f)^{2} ≥ [π(f^{2})−π(f)^{2}]α_{p}/β_{p} for every f ∈ L^{∞}(π). The proof goes as follows.

π_{p}(f^{2}) − π_{p}(f)^{2} = inf_{c∈ℝ} ∫ (f(x) − c)^{2}π_{p}(dx)

= β_{p}^{−1} inf_{c∈ℝ} ∫ (f(x) − c)^{2}p(x)π(dx)

≥ \frac{α_{p}}{β_{p}} inf_{c∈ℝ} ∫ (f(x) − c)^{2}π(dx)

= \frac{α_{p}}{β_{p}} [π(f^{2}) − π(f)^{2}]. □

3. A Criterion for the Existence of Spectral Gap. Proofs of Theorem 1.4 and Theorem 1.5

To state our main criterion, we need some preparation.

Let E be a locally compact separable metric space with Borel field E and supp(π) = E. Denote by C_{b}(E) (resp. C_{0}(E)) the set of all bounded continuous functions (resp. with compact support) on E.

Next, let (D, D(D)) be a regular conservative Dirichlet form on L^{2}(π). By Beurling-Deny’s formulae, the form can be expressed as follows

D(f, f) = D^{(c)}(f, f) + \frac{1}{2} ∫ J(dx, dy)(f(x) − f(y))^{2},  f ∈ D(D) ∩ C_{0}(E)  (3.1)

where D(D^{(c)}) = D(D) ∩ C_{0}(E) and satisfies a strong local property; J is a symmetric Radon measure on the product space E × E off diagonal. Moreover, there exists a finite, non-negative Radon measure μ_{⟨f⟩}^{c} such that

D^{(c)}(f, f) = \frac{1}{2} ∫_{E} dμ_{⟨f⟩}^{c}, f ∈ D(D) ∩ C_{b}(E).

Theorem 3.1. Let C ⊂ D(D)∩C_{0}(E) be dense in D(D) in the D-norm: ∥f∥_{D}^{2} = D(f, f)+ π(f^{2}). Set C_{L} = {f + c : f ∈ C, c ∈ ℝ}. Given A, B ∈ E, A ⊂ B with 0 < π(A), π(B) < 1. Suppose that the following conditions hold.

(1) There exists a conservative Dirichlet form (D_{B}, D(D_{B})) on the square-integrable functions on B with respect to π^{B} such that C|_{B} ⊂ D(D_{B}) and

D(f, f) ≥ D_{B}(fI_{B}, fI_{B}), f ∈ C_{L}.

(2) There exists a function h ∈ C_{L}: 0 ≤ h ≤ 1, h|_{A} = 0 and h|_{B^{c}} = 1 such that

c(h) := sup_{f∈C_{L}} \frac{1}{π(f^{2}I_{B})}[\frac{1}{2} ∫ f^{2}dμ_{⟨h⟩}^{c} + ∫_{B×A^{c}} J(dx, dy)[f(1 − h)(y) − f(1 − h)(x)]^{2}] < ∞.

Then, we have

\frac{λ_{0}(A^{c})}{π(A)} ≥ λ_{1} ≥ \frac{λ_{1}(B)[λ_{0}(A^{c})π(B) − 2c(h)π(B^{c})]}{2λ_{1}(B) + π(B)^{2}[λ_{0}(A^{c}) + 2c(h)]}.

Proof. The upper bound is easy. Simply take f ∈ C_{L} with f|_{A} = 0 and π(f^{2}) = 1. Then

π(f^{2}) − π(f)^{2} = 1 − π(fI_{A^{c}})^{2} ≥ 1 − π(f^{2})π(A^{c}) = 1 − π(A^{c}) = π(A).

Hence λ_{1} ≤ D(f, f)/π(A) which gives us λ_{1} ≤ λ_{0}(A^{c})/π(A).

For the lower bound, let f ∈ C_{L} with π(f) = 0 and π(f^{2}) = 1. Set γ = π(f^{2}I_{B}).

a) By condition (1), we have

D(f, f) ≥ D_{B}(fI_{B}, fI_{B}) ≥ λ_{1}(B)π(B)^{−1}[π(f^{2}I_{B}) − π(B)^{−1}π(fI_{B})^{2}]
= λ_{1}(B)π(B)^{−1}[π(f^{2}I_{B}) − π(B)^{−1}π(fI_{B^{c}})^{2}]
≥ λ_{1}(B)π(B)^{−1}[γ − π(B)^{−1}π(f^{2}I_{B^{c}})π(B^{c})]
= λ_{1}(B)π(B)^{−2}[γ − π(B^{c})].  (3.2)

12 MU-FA CHEN AND FENG-YU WANG

b) Let ρ be the metric in E. By the construction of μ_{⟨f⟩}^{c} ([6; §3.2]), there exist a sequence of relatively compact open sets G_{ℓ} increasing to E, a sequence of symmetric, non-negative Radon measures σ_{β_{n}} and a sequence δ_{ℓ} such that

∫_{E} gdμ_{⟨f⟩}^{c} = lim_{ℓ→∞} lim_{β_{n}→∞} β_{n} ∫_{G_{ℓ}×G_{ℓ}, ρ(x,y)<δ_{ℓ}}[f(x) − f(y)]^{2}g(x)σ_{β_{n}}(dx, dy)
f, g ∈ D(D) ∩ C_{0}(E).

¿From this and

[(fh)(x) − (fh)(y)]^{2} ≤ 2h(y)^{2}[f(x) − f(y)]^{2} + 2f(x)^{2}[h(x) − h(y)]^{2},

it follows that

∫ dμ_{⟨fh⟩}^{c} ≤ 2 ∫ h^{2}dμ_{⟨f⟩}^{c} + 2 ∫ f^{2}dμ_{⟨h⟩}^{c},

first for f, g ∈ D(D) ∩ C_{0}(E) and then for f, g ∈ D(D) ∩ C_{b}(E) (cf. [6; §3.2]). Hence

D^{(c)}(fh, fh) = \frac{1}{2} ∫ dμ_{⟨fh⟩}^{c} ≤ 2D^{(c)}(f, f) + ∫ f^{2}dμ_{⟨h⟩}^{c}.  (3.3)

On the other hand, since

|(fh)(x) − (fh)(y)| ≤ |f(x) − f(y)| + I_{B×A^{c}∪A^{c}×B}(x, y)|f(1 − h)(x) − f(1 − h)(y)|, we have

∫ J(dx, dy)[(fh)(x) − (fh)(y)]^{2} ≤ 2 ∫ J(dx, dy)[f(x) − f(y)]^{2}
+ 4 ∫_{B×A^{c}} J(dx, dy)[f(1 − h)(x) − f(1 − h)(y)]^{2}.  (3.4)

Thus, combining (3.1), (3.3), (3.4) with condition (2) together, we get

D(fh, fh) ≤ 2D(f, f) + ∫ f^{2}dμ_{⟨h⟩}^{c} + 2 ∫_{B×A^{c}} J(dx, dy)[f(1 − h)(x) − f(1 − h)(y)]^{2}
≤ 2D(f, f) + 2c(h)π(f^{2}I_{B})
≤ 2D(f, f) + 2γc(h).

That is,

D(f, f) ≥ \frac{1}{2}D(fh, fh) − γc(h) ≥ \frac{1}{2}λ_{0}(A^{c})π(f^{2}h^{2}) − γc(h)
≥ \frac{1}{2}λ_{0}(A^{c})π(f^{2}I_{B^{c}}) − γc(h) = \frac{1}{2}λ_{0}(A^{c})(1 − γ) − γc(h).  (3.5)

Combining (3.2) with (3.5) together, we obtain

D(f, f) ≥ inf_{γ∈[0,1]} max \{\frac{λ_{1}(B)}{π(B)^{2}} (γ − π(B^{c})), \frac{1}{2}λ_{0}(A^{c})(1 − γ) − γc(h)\}
= λ_{1}(B)π(B)^{−2}(γ_{0} − π(B^{c})).  (3.6)

The assertion of the theorem now follows from (3.6) and Lemma 2.2. □

Theorem 3.1 is effective for diffusions was shown in [9] with a more direct proof (in this case the Dirichlet form is explicit). We now apply the theorem to jump processes.

Proof of Theorem 1.4. First, the topological assumptions of Theorem 3.1 are unnecessary in the present context. To see that condition (1) is fulfilled, simply take D_{B} to be the one defined by (1.13). For condition (2), take h = I_{A^{c}}. Then

∫_{B×A^{c}}J(dx, dy)[(fI_{A})(x) − (fI_{A})(y)]^{2} =∫_{A×A^{c}}J(dx, dy)f(x)^{2} ≤ M_{A}π(f^{2}I_{A}) ≤ M_{A}π(f^{2}I_{B}).

This means that condition (2) holds with c(h) = M_{A}. We have thus proved Theorem 1.4. □

The application of Theorem 3.1 (or Theorem 1.4) requires some estimates of λ_{0}(A^{c}) and λ_{1}(B), which may be obtained from Theorems 1.1—1.2. These estimates are usually in the qualitative sense good enough for λ_{1}(B), for which there are also quite a lot of publications including the authors’ study in the past years. However, for λ_{0}(A^{c}), the bound presented above may not be sharp enough, especially in the unbounded situation. For this reason, we now introduce a different result.

Theorem 3.2. Let E be a metric space with Borel field E and let (x_{t}) be a reversible right-continuous Markov process valued in E with weak generator Ω. Suppose that the corresponding Dirichlet form is regular. Next, fix a closed set B. Suppose additionally that the following conditions hold.

(1) There exists a positive function φ, φ|_{B} = 0 and

sup_{B^{c}} \frac{1}{φ}Ωφ =: δ < 0.

(2) There exists a sequence of open sets (E_{n}): E_{0} ⊃ B, E_{n} ↑ E such that φ is bounded below on each E_{n} \ B by a positive constant.

(3) The first Dirichlet eigenfunction of Ω on each E_{n} \ B is bounded above. Then we have λ_{0}(B^{c}) ≥ δ. In particular, for jump processes, the condition “φ|_{B} = 0” given in (1) can be removed.

Clearly, conditions (2) and (3) with compact B are fulfilled for diffusions or Markov chains. Thus, the key condition here is the first one.

Proof of Theorem 3.2. The last assertion follows by replacing φ with φI_{B^{c}}. Indeed,

Ω(φI_{B^{c}})(x) = ∫ q(x, dy)[(φI_{B^{c}})(y) − (φI_{B^{c}})(x)]
≤ ∫ q(x, dy)φ(y) − (φI_{B^{c}})(x) = Ωφ(x) ≤ −δ(φI_{B^{c}})(x) on B^{c}.

We are now going to prove the main assertion of the theorem. Set τ_{B} = inf{t ≥ 0 : x_{t} ∈ B}. Then, by condition (1) plus a truncating argument if necessary, we get

𝔼^{x}φ(x_{t∧τ_{B}}) ≤ φ(x), t ≥ 0, x ∉ B.

Next, let u_{n} (≥ 0) be the first Dirichlet eigenfunction of Ω on E_{n} \ B. Set τ = inf{t ≥ 0 : x_{t} ∉ E_{n} \ B}. Then, by conditions (2) and (3), there exists c_{1} > 0 such that u(x_{t∧τ}) ≤ c_{1}φ(x_{t∧τ_{B}}) and so

u_{n}(x)e^{−λ_{0}(E_{n}\B)t} = 𝔼^{x}u_{n}(x_{t∧τ}) ≤ c_{1}𝔼^{x}φ(x_{t∧τ_{B}}) ≤ c_{1}φ(x)e^{−δt}, x ∈ E_{n} \ B.

This implies that λ_{0}(E_{n} \ B) ≥ δ. Finally, because the Dirichlet form is regular, it is easy to show that λ_{0}(B^{c}) = lim_{n→∞} λ_{0}(E_{n} \ B) and so the required assertion follows. □

For the remainder of this section, we turn to study the upper bound of λ_{1}.

Let (D, D(D)) be a general conservative Dirichlet form and let P (t, x, dy) be the corresponding transition probability. Fix φ ≥ 0. Suppose that φ ∧ n ∈ D(D) for every n ≥ 1. Set f_{n} = exp[ε(φ ∧ n)/2]. Since the function e^{αx} is locally Lipschitz continuous and φ ∧ n is bounded, by the elementary spectral representation theory, we have

D(f_{n}, f_{n}) = lim_{t→0} \frac{1}{2t} ∫ π(dx)P (t, x, dy)[f_{n}(x) − f_{n}(y)]^{2}

≤ \frac{ε^{2}}{4} C(φ, n) lim_{t→0} \frac{1}{2t} ∫ π(dx)P (t, x, dy)[(φ ∧ n)(x) − (φ ∧ n)(y)]^{2}

≤ \frac{ε^{2}}{4} C(φ, n)D(φ ∧ n, φ ∧ n) < ∞,

where C(φ, n) is the Lipschitz norm of e^{εx/2} on the range of φ∧n. This leads us to introduce the following constant

δ(ε, φ) = ε^{−2} sup_{n≥1} D(f_{n}, f_{n})/π(f_{n}^{2}).

Theorem 3.3. Let (D, D(D)), φ, f_{n} and δ(ε, φ) be as above. Then, we have

λ_{1} ≤ sup {ε^{2}δ(ε, φ) : π(e^{εφ}) < ∞}.

Proof. We need to show that if π(e^{εφ}) = ∞, then λ_{1} ≤ ε^{2}δ(ε, φ). For n ≥ 1, we have

λ_{1} ≤ \frac{1}{2} \frac{∫ J(dx, dy)[f_{n}(x) − f_{n}(y)]^{2}}{π(f_{n}^{2}) − π(f_{n})^{2}} .  (3.7)

For every m ≥ 1, choose r_{m} > 0 such that π(φ ≥ r_{m}) ≤ 1/m. Then

π(I_{[φ≥r_{m}]}f_{n}^{2})^{1/2} ≥ \sqrt{m} π(I_{[φ≥r_{m}]}f_{n}) ≥ \sqrt{m} π(f_{n}) − \sqrt{m} e^{εr_{m}/2}.

Hence

π(f_{n})^{2} ≤ [\sqrt{π(f_{n}^{2})}/\sqrt{m} + e^{εr_{m}/2}]^{2}.  (3.8)

On the other hand, by assumption, we have

D(f_{n}, f_{n}) ≤ ε^{2}δ(ε, φ)π(f_{n}^{2}).  (3.9)

Noticing that π(f_{n}^{2}) ↑ ∞, combining (3.9) with (3.7) and (3.8) and then letting n ↑ ∞, we obtain

λ_{1} ≤ ε^{2}δ(ε, φ)/[1 − m^{−1}].

The proof is completed by setting m ↑ ∞. □

Proof of Theorem 1.5. It suffices to prove the first assertion because the remainder of the proof is similar. Let f_{n} be given as in Theorem 3.3. Note that by the Mean Value Theorem, |e^{A} − e^{B}| ≤ |A − B|e^{A∨B} = |A − B|(e^{A} ∨ e^{B}) for all A, B ≥ 0. Hence

D(f_{n}, f_{n}) = \frac{1}{2} ∫ J(dx, dy)[f_{n}(x) − f_{n}(y)]^{2}

≤ \frac{ε^{2}}{8} ∫ J^{(1)}(dx, dy)[φ(x) − φ(y)]^{2}r(x, y)[f_{n}(x) ∨ f_{n}(y)]^{2}

≤ \frac{ε^{2}}{4} δ_{2}(φ)π(f_{n}^{2}).

The conclusion now follows from Theorem 3.3 with δ(ε, φ) = \frac{1}{4}δ_{2}(φ). □

4. Existence of Spectral Gap for Markov Chains.

Usually, the power of a result for general jump processes should be justified by Markov chains.

Let E be countable and (q_{ij}) be a regular and irreducible Q-matrix, reversible with respect to π = (π_{i}). As usual, let q_{i} = ∑_{j≠i} q_{ij}. Assume that q_{i} > 0 for all i to rule out the reducible case. Then K = 0 and Ωf(i) = ∑_{j≠i} q_{ij}[f_{j} − f_{i}]. The density of the symmetric measure with respect to the counting measure becomes J(i, j) = π_{i}q_{ij} (i ≠ j). For simplicity, we consider only two typical situations: E = ℤ_{+} or E = ℤ^{d} and take r(i, j) = 1/(q_{i} ∨ q_{j}). Denote by |i| the L^{1}-norm, i.e., |i| = ∑_{k=1}^{d} |i_{k}| for i = (i_{1}, ⋯, i_{d}) ∈ ℤ^{d}.

A combination of Theorem 1.2 and the next result provides us a simple condition for the existence of spectral gap for birth-death processes and the result seems to be new from our knowledge even in such a simple situation (cf. [3]).

Theorem 4.1. Consider the birth-death process on ℤ_{+} with birth rates (b_{i}) and death rates (a_{i}).

(1) Take r_{ij} = (a_{i} + b_{i}) ∨ (a_{j} + b_{j}) (i ≠ j). Then k^{(α)′} > 0 (equivalently, k^{(α)} > 0) iff there exists a constant c > 0 such that

\frac{π_{i}a_{i}}{[(a_{i} + b_{i}) ∨ (a_{i−1} + b_{i−1})]^{α}} ≥ c ∑_{j≥i} π_{j},  i ≥ 1.  (4.1)

Then, we indeed have k^{(α)′} ≥ c. Furthermore

k^{(α)} ≥ inf_{i≥1} \frac{π_{i}a_{i}}{[(a_{i} + b_{i}) ∨ (a_{i−1} + b_{i−1})]^{α}(1 − π_{i}) ∑_{j≥i} π_{j}} .

(2) Let ∑_{i} π_{i}(a_{i} + b_{i})<∞. Take p_{i} = a_{i} + b_{i}. Then we have k′_{p} >0 (equivalently, k_{p} >0)

iff inf_{i≥1} \frac{π_{i}a_{i}}{∑_{j≥i} π_{j}p_{j}} >0 and moreover

k′_{p} ≥ inf_{i≥1} \frac{π_{i}a_{i}}{∑_{j≥i} π_{j}p_{j}} , k_{p} ≥ inf_{i≥1} \frac{π_{i}a_{i}}{(1 − π_{i}p_{i}/β_{p}) ∑_{j≥i} π_{j}p_{j}} .

Roughly speaking, (4.1) holds if π_{j} has exponential decay. For polynomial decay, (4.1) can still be true when α = 1/2. See Example 4.5.

Proof of Theorem 4.1. Here we prove part (1) only since the proof of part (2) is similar. a) Let k^{(α)} > 0. Take A = I_{i} = {i, i + 1, ⋯ } for a fixed i > 0 and

J^{(α)}(i, j) = \frac{π_{i}q_{ij}}{[q_{i} ∨ q_{j}]^{α}} = \{ \begin{matrix}\frac{π_{i}a_{i}}{[(a_{i} + b_{i}) ∨ (a_{i−1} + b_{i−1})]^{α}} =: π_{i}ã_{i}, if j = i − 1 \\ \frac{π_{i}a_{i}}{[(a_{i} + b_{i}) ∨ (a_{i+1} + b_{i+1})]^{α}} =: π_{i}b̃_{i}, if j = i + 1. \end{matrix}

Then

k^{(α)′} ≤ k^{(α)} ≤ \frac{J^{(α)}(A × A^{c})}{π(A)π(A^{c})} = \frac{π_{i}ã_{i}}{( ∑_{j≥i} π_{j})( ∑_{j<i} π_{j})} ≤ \frac{π_{i}ã_{i}}{π_{0} ∑_{j≥i} π_{j}} .

This proves the necessity of the condition.

b) Next, assume that the condition holds. Then for each A with π(A) ∈ (0, 1), since the symmetry of J^{(α)}, we may assume that 0 ∉ A. Set i_{0} = min A ≥ 1. Then, A ⊂ I_{i_{0}}, A^{c} ⊂ E \ {i_{0}} and so

\frac{J^{(α)}(A × A^{c})}{π(A) ∧ π(A^{c})} ≥ \frac{π_{i_{0}} ã_{i_{0}}}{∑_{j≥i_{0}} π_{j}} ≥ c, \frac{J^{(α)}(A × A^{c})}{π(A)π(A^{c})} ≥ \frac{π_{i_{0}} ã_{i_{0}}}{(1 − π_{i_{0}}) ∑_{j≥i_{0}} π_{j}} .

Because A is arbitrary, we obtain the required assertions. □

Theorem 4.2. Let E = ℤ_{+}. Suppose that (q_{ij}) has finite range R, i.e., q_{ij} = 0 whenever |i − j| > R. Then, we have λ_{1} > 0 provided

\overline{lim}_{i→∞} ∑_{j} \frac{q_{ij}}{\sqrt{q_{i} ∨ q_{j}}} (j − i) < 0.

Proof. Simply take φ_{i} = i + 1 and B = {0, 1, ⋯, n} for large n in Theorem 1.3 and then apply Theorem 1.2. □

Similarly, we have the following result.

Theorem 4.3. Let E = ℤ^{d}. Suppose that (q_{ij}) has finite range R. Then, we have λ_{1} > 0 provided

\overline{lim}_{|i|→∞} ∑_{j} \frac{q_{ij}}{\sqrt{q_{i} ∨ q_{j}}} ∑_{k=1}^{d} [|j_{k}| ∨ R − |i_{k}| ∨ R] < 0.

Proof. Take φ_{i} = ∑_{k=1}^{d} |i_{k}| ∨ R + 1 in Theorem 1.3 and then apply Theorem 1.2. □

Theorem 4.4. Let E = ℤ^{d}. If there exists a positive function φ such that

\overline{lim}_{|i|→∞} \frac{1}{φ}Ωφ < 0,

then λ_{1} > 0.

Proof. Apply Theorem 1.2, Theorem 3.2 and then Theorem 1.4 to the finite sets {i : |i| ≤ n}. □

The following example, taken from [3], is especially rare and interesting since it exhibits the critical phenomena for the existence of spectral gap. It is now used to justify the power of our results and we should see soon what will happen. Similar example for diffusion was given in [4] and [9].

Example 4.5. Let E = ℤ_{+} and a_{i} = b_{i} = i^{γ} (i ≥ 1) for some γ > 0, a_{0} = 0 and b_{0} = 1. Then λ_{1} > 0 iff γ ≥ 2.

Proof. a) By part (1) of Theorem 4.1, we have k^{(1/2)} > 0 iff γ ≥ 2. Thus, by Theorem 1.2, we have λ_{1} > 0 for all γ ≥ 2.

b) Applying Theorem 1.5 to φ_{i} = 1 + i^{1−γ/2}, it follows that λ_{1} = 0 for all γ ∈ (1, 2).

c) The conditions of Theorem 4.2 hold whenever γ ≥ 2. Hence λ_{1} > 0 for all γ ≥ 2.

d) Next, taking φ_{i} = \sqrt{i} (i ≥ 1), we see that Ωφ(i)/φ_{i} = −\frac{1}{2γ(γ−1)}i^{γ−2} + O(i^{γ−3}). Then

lim_{i→∞} \frac{1}{φ_{i}} Ωφ(i) = \{ \begin{matrix}−∞, & γ > 2 \\ −\frac{1}{4}, & γ = 2. \end{matrix}

By Theorem 4.4, we have λ_{1} > 0 for all γ ≥ 2.

On the other hand, take f_{n}(i) = i^{\frac{γ−1}{2}} ∧ n^{\frac{γ−1}{2}} and A = \{0\}. Then

λ_{0}(A^{c}) ≤ \underline{lim}_{n→∞} \frac{∑_{i,j≥0} π_{i}q_{ij}[f_{n}(j) − f_{n}(i)]^{2}}{2 ∑_{i≥0} π_{i}f_{n}(i)^{2}} = \underline{lim}_{n→∞} \frac{∑_{i≥0} π_{i}q_{i,i+1}[f_{n}(i + 1) − f_{n}(i)]^{2}}{2 ∑_{i≥0} π_{i}f_{n}(i)^{2}}

≤ \underline{lim}_{n→∞} \frac{1 + (γ − 1)^{2} ∑_{i=1}^{n} i^{γ−3}}{∑_{i=1}^{n} i^{−1}} = 0, 1 < γ < 2.

By Theorem 1.4, we get λ_{1} ≤ λ_{0}(A^{c})/π(A) = 0. The case that γ ≤ 1 can be ignored since then the chain is not positive recurrent. □

Thus, we have seen that all the results presented in the paper, except Theorem 2.5 which does not work for this example, are qualitatively sharp for this example since every one covers the required region and there is no gap left. Finally, taking α = 0 in part (1) of Theorem 4.1, we obtain k ≥ ( ∑_{i=1}^{∞} i^{−γ})^{−1} > 0 for all γ > 1. In other words, we have k > 0 but λ_{1} = 0 for all γ ∈ (1, 2). Therefore, the condition “k > 0” is not but “k^{(1/2)} > 0” is sufficient for λ_{1} > 0.

The next two examples show that the two approaches used in the paper for the Cheeger’s inequalities may all attain sharp estimates but they are not comparable (remember that Theorem 2.5 is not suitable for Example 4.5). We mention that as far as we know, no optimal estimate provided by the Cheeger’s technique ever appeared before.

Example 4.6. Let E = ℤ_{+} and take a_{i} ≡ a > 0 and b_{i} ≡ b > 0. Then, both Theorem 1.2 and Theorem 2.5 are sharp.

Proof. This is a standard example which is often used to justify the power of a method. It is well known that λ_{1} = (\sqrt{a} − \sqrt{b} )^{2} (cf. [2; Example 9.22] and [3]).

a) By part (1) of Theorem 4.1, we have

k^{(α)}′ ≥ inf_{i≥1} \frac{π_{i}a_{i}}{(a + b)^{α} ∑_{j≥i} π_{j}} = \frac{a − b}{(a + b)^{α}} .

Then, by Theorem 1.2, we get λ_{1} ≥ (\sqrt{a} − \sqrt{b} )^{2}.

b) Take p_{i} ≡ a + b. Then by part (2) of Theorem 4.1,

k′_{p} ≥ inf_{i≥1} \frac{π_{i}a_{i}}{∑_{j≥i} π_{j}p_{j}} = \frac{a − b}{a + b}.

The same estimate as in a) now follows from Theorem 2.5. □

Example 4.7. Let E = ℤ_{+} and take q_{0k} = β_{k} > 0 (be careful to distinguish the sequence (β_{k}) and the constant β_{p}), q_{k0} = 1/2 for k ≥ 1 and q_{ij} = 0 for all other i ≠ j. Assume that q_{0} = ∑_{k≥1} β_{k} < ∞. Then, Theorem 2.5 is sharp for all q_{0} but Theorem 1.2 is sharp only for q_{0} ≤ 1/2.

Proof. From π_{0}q_{0k} = π_{k}q_{k0}, it follows that π_{k} = 2π_{0}β_{k}, k ≥ 1 and π_{0} = (1 + 2q_{0})^{−1}. An interesting point of the example is that the decay of ∑_{j≥i} π_{j} as i → ∞ can be arbitrary slow, not necessarily exponential. The last condition is necessary for λ_{1} > 0 for the birthdeath processes with rates bounded below (by a positive constant) and above (cf. [2; Corollary 9.19 (4)]).

a) Take p_{i} = q_{i} ∨ (1/2), then α_{p} = 1/2. Without loss of generality, assume that 0 ∉ A. Then

\frac{1}{β_{p}} · \frac{J(A × A^{c})}{π_{p}(A) ∧ π_{p}(A^{c})} = \frac{∑_{i∈A} π_{i}q_{i0}}{( ∑_{i∈A} 2π_{0}β_{i}p_{i}) ∧ (π_{0}p_{0} + ∑_{i∉A, i≠0} 2π_{0}β_{i}p_{i})}

= \frac{∑_{i∈A} β_{i}}{( ∑_{i∈A} 2β_{i}p_{i}) ∧ (p_{0} + ∑_{i∉A, i≠0} 2β_{i}p_{i})}

= \frac{∑_{i∈A} β_{i}}{( ∑_{i∈A} β_{i}) ∧ (p_{0} + ∑_{i∉A, i≠0} β_{i})} ≥ 1.

This gives us k′_{p} ≥ 1 and hence by Theorem 2.5,

λ_{1} ≥ α_{p}(1 − \sqrt{1 − k′_{p}^{2}} ) ≥ 1/2.

Actually, every equality in the last line must hold.

b) Again, assume that 0 ∉ A. Then

\frac{J^{(α)}(A × A^{c})}{π(A) ∧ π(A^{c})} = \frac{∑_{i∈A} π_{i}q_{i0}(q_{i} ∨ q_{0})^{−α}}{( ∑_{i∈A} 2π_{0}β_{i}) ∧ (π_{0} + ∑_{i∉A, i≠0} 2π_{0}β_{i})}

= \frac{1}{2} · \frac{∑_{i∈A} 2β_{i}}{(\frac{1}{2} ∨ q_{0})^{α}[( ∑_{i∈A} 2β_{i}) ∧ (1 + ∑_{i∉A, i≠0} 2β_{i})]}

= \frac{1}{2} · \frac{1}{(\frac{1}{2} ∨ q_{0})^{α}} · \frac{∑_{i∈A} β_{i}}{( ∑_{i∈A} β_{i}) ∧ (1/2 + ∑_{i∉A, i≠0} β_{i})}

= \frac{1}{2} · \frac{1}{(\frac{1}{2} ∨ q_{0})^{α}} · \frac{1}{1 ∧ [(1/2 + ∑_{i∉A, i≠0} β_{i})/ ∑_{i∈A} β_{i}]}.

Because (1/2 + ∑_{i∉A, i≠0} β_{i})/ ∑_{i∈A} β_{i} decreases when A increases, by setting A = {i} for a large enough i ≠ 0, it follows that

k^{(α)}′ = inf_{A: 0∉A} \frac{J^{(α)}(A × A^{c})}{π(A) ∧ π(A^{c})} = \frac{1}{2}(\frac{1}{2} ∨ q_{0})^{−α}.

By Theorem 1.2, we get

λ_{1} ≥ \frac{1}{2}\{1 ∨ (2q_{0}) + \sqrt{(1 ∨ (2q_{0}))^{2} − 1} \}^{−1}.

Thus, the lower bound is equal to 1/2 = λ_{1} iff q_{0} ≤ 1/2. □

The following counterexample shows the limitation of the Cheeger’s inequalities. Of course, the example can be easily handled with the help of some comparison technique. However, this suggests us that sometimes it is necessary to examine a model carefully before applying the inequalities.

Example 4.8. Consider the birth-death process with a_{2i−1} = (2i − 1)^{2}, a_{2i} = (2i)^{4} and b_{i} = a_{i} for all i ≥ 1. Then, we have k^{(1/2)′} = 0 and so Theorem 1.2 is not applicable.

Proof. First, applying Theorem 4.4 to φ_{i} = \sqrt{i} or comparing the chain with the one with rates a_{i} = b_{i} = (2i)^{2}, one sees that λ_{1} > 0. Next, because μ_{i} = 1/a_{i} (and hence π_{i} = μ_{i}/Z, where Z is the normalizing constant), we have ∑_{j≥i} μ_{j} = O(i^{−1}). However, \sqrt{a_{i} ∨ a_{i−1}} = O(i^{2}). Hence sup_{i≥1} \sqrt{a_{i} ∨ a_{i−1}} ∑_{j≥i} μ_{j} = ∞. This gives us k^{(1/2)′} = 0 by part (1) of Theorem 4.1.

Note that the choice r_{ij} = q_{i} ∨ q_{j} (i ≠ j) is usually not optimal in the sense for which (1.8) often becomes inequality rather than equality. However, the improvement provided by an optimal r_{ij} is still not enough to cover this example and so the problem is really due to the limitation of the technique. □

References

1. Cheeger, J. (1970), A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis, a symposium in honor of S. Bochner 195–199, Princeton U. Press, Princeton.

2. Chen, M. F. (1992), From Markov Chains to Non-Equilibrium Particle Systems, Singapore, World Scientific.

3. Chen, M. F. (1996), Estimation of spectral gap for Markov chains, Acta Math. Sin. New Ser. 12:4, 337–360.

4. Chen, M. F. and Wang, F. Y. (1997), Estimation of spectral gap for elliptic operators, Trans. Amer. Math. Soc. 349, 1209–1237.

5. Chung, F. R. K. (1997), Spectral Graph Theory, CBMS, 92, AMS, Providence, Rhode Island.

6. Fukushima, M., Oshima, Y. and Takeda, M. (1994), Dirichlet Forms and Symmetric Markov Processes, Walter de Gruyter & Co.

7. Lawler, G. F. and Sokal, A. D. (1988), Bounds on the L^{2} spectrum for Markov chain and Markov processes: a generalization of Cheeger’s inequality, Trans. Amer. Math. Soc. 309, 557–580.

8. Saloff-Coste, L. (1997), Lectures on Finite Markov Chains, LNM 1665, Springer-Verlag.

9. Wang, F. Y. (1997), Existence of spectral gap for diffusion processes, preprint.

5. Appendix. Proof of Lemma 2.1, for referee’s reference

Because α ≥ 0 is fixed, we can omit the superscript “(α)” everywhere in the proof. Denote by h̃, k̃ and k̃′ the right-hand sides of the above quantities. By taking f = I_{A}, we obtain h ≥ h̃, k ≥ k̃ and k′ ≥ k̃′. We now prove the reverse inequalities.

a) For any f ≥ 0 with π(f) = 1, let A_{γ} = {f > γ}, γ ≥ 0. By the symmetry of J, we have

\frac{1}{2} ∫ J(dx, dy)|f(y) − f(x)| + K(f) = ∫_{\{f(x)>f(y)\}} J(dx, dy)[f(x) − f(y)] + K(f)

= ∫_{0}^{∞} dγ{J({f(x) > γ ≥ f(y)}) + K({f > γ})}

= ∫_{0}^{∞} [J(A_{γ} × A_{γ}^{c}) + K(A_{γ})]dγ ≥ h ∫_{0}^{∞} π(A_{γ})dγ = hπ(f) = h.

Hence h̃ ≥ h.

b) For any f ∈ L_{+}^{1}(π) with ∫ π(dx)π(dy)|f(x) − f(y)| = 1, by a), we have

∫ J(dx, dy)|f(x) − f(y)| = 2 ∫ dγJ(A_{γ} × A_{γ}^{c})

≥ k ∫_{0}^{∞} dγ (π × π)(A_{γ} × A_{γ}^{c}) = k ∫_{0}^{∞} π(dx)π(dy)|f(x) − f(y)| = k.

This proves the first equality of k^{(α)}.

Next, we show that

∫ |f − π(f)|dπ = sup_{g: π(g)=0, inf_{c∈ℝ} ∥g−c∥_{∞}≤1} ∫ fgdπ,  (5.1)

where ∥ · ∥_{p} denotes the L^{p}-norm. First, let π(g) = 0 with inf_{c∈ℝ} ∥g − c∥_{∞} ≤ 1. Then, because π(g) = 0 and π(f − π(f)) = 0, we have

∫ fgdπ = ∫ (f − π(f))gdπ = ∫ (f − π(f))(g − c)dπ

for all c ∈ ℝ. Hence, by Hölder inequality, we have

| ∫ fgdπ| ≤ ∥f − π(f)∥_{1}∥g − c∥_{∞}

for all c. This gives us

| ∫ fgdπ| ≤ ∥f − π(f)∥_{1} inf_{c} ∥g − c∥_{∞} ≤ ∥f − π(f)∥_{1}.

On the other hand, for a given f ∈ L^{1}(π), set A_{f}^{+} = {f ≥ π(f)} and A_{f}^{−} = {f < π(f)}. Take g_{0} = I_{A_{f}^{+}} − I_{A_{f}^{−}} − π(A_{f}^{+}) + π(A_{f}^{−}). Then, g_{0} ∈ L^{∞}(π) and π(g_{0}) = 0. Finally, take

c_{0} = 1−2π(A_{f}^{+}). Then, it is easy to check that inf_{c} ∥g_{0} −c∥_{∞} = ∥g_{0} −c_{0}∥_{∞} = 1. Therefore, we have ∫ fg_{0}dπ = ∫ |f − π(f)|dπ as required.

We now prove the second equality of k^{(α)}. Let f ≥ 0 and set A_{γ} = {f ≥ γ}. Again, by using a) and (5.1), we have

∫ J(dx, dy)|f(y) − f(x)| ≥ 2k ∫_{0}^{∞} dγπ(A_{γ})π(A_{γ}^{c}) = k ∫_{0}^{∞} dγ ∫ |I_{A_{γ}} − π(A_{γ})|dπ

= k ∫_{0}^{∞} dγ sup_{g: π(g)=0, inf_{c∈ℝ} ∥g−c∥_{∞}≤1} ∫ I_{A_{γ}} gdπ

≥ k sup_{g: π(g)=0, inf_{c∈ℝ} ∥g−c∥_{∞}≤1} ∫_{0}^{∞} dγ ∫ I_{A_{γ}} gdπ

= k sup_{g: π(g)=0, inf_{c∈ℝ} ∥g−c∥_{∞}≤1} ∫ fgdπ = k ∫ |f − π(f)|dπ.

Therefore, we obtain k̃ ≥ k.

c) Choose c_{0} ∈ ℝ such that π(f < c_{0}), π(f > c_{0}) ≤ 1/2. Let f_{±} = (f − c_{0})^{±}. Then we have f_{+} + f_{−} = |f − c_{0}| and π(|f − c_{0}|) = min_{c} π(|f − c|). For any γ ≥ 0, define A_{γ}^{±} = {f_{±} > γ}. We have

\frac{1}{2} ∫ J(dx, dy)|f(y) − f(x)| = \frac{1}{2} ∫ J(dx, dy)[|f_{+}(y) − f_{+}(x)| + |f_{−}(y) − f_{−}(x)|]

= ∫_{0}^{∞} [J(A_{γ}^{+} × A_{γ}^{+c}) + J(A_{γ}^{−} × A_{γ}^{−c})]dγ

≥ k′ ∫_{0}^{∞} [π(A_{γ}^{+}) + π(A_{γ}^{−})]dγ = k′π(f_{+} + f_{−}) = k′π(|f − c_{0}|) = k′ min_{c} π(|f − c|).

This implies that k̃′ ≥ k′. □

Acknowledgement. The second named author would like to thank MSRI for a happy stay.

Department of Mathematics, Beijing Normal University, Beijing 100875, The People’s Republic of China.