Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces

Assaf Naor^{∗}  Yuval Peres^{†}  Oded Schramm^{‡}  Scott Sheffield^{§}

October 19, 2004

Abstract

A metric space X has Markov type 2, if for any reversible finite-state Markov chain {Z_{t}} (with Z_{0} chosen according to the stationary distribution) and any map f from the state space to X, the distance D_{t} from f(Z_{0}) to f(Z_{t}) satisfies 𝔼(D_{t}^{2}) ≤ K^{2} t 𝔼(D_{1}^{2}) for some K = K(X) < ∞. This notion is due to K. Ball (1992), who showed its importance for the Lipschitz extension problem. However until now, only Hilbert space (and metric spaces which embed bi-Lipschitzly into it) were known to have Markov type 2. We show that every Banach space with modulus of smoothness of power type 2 (in particular, L_{p} for p > 2) has Markov type 2; this proves a conjecture of Ball. We also show that trees, hyperbolic groups and simply connected Riemannian manifolds of pinched negative curvature have Markov type 2. Our results are applied to settle several conjectures on Lipschitz extensions and embeddings. In particular, we answer a question posed by Johnson and Lindenstrauss in 1982, by showing that for 1 < q < 2 < p < ∞, any Lipschitz mapping from a subset of L_{p} to L_{q} has a Lipschitz extension defined on all of L_{p}.

1 Introduction

K. Ball [2] introduced the notion of Markov type of metric spaces, defined as follows. Recall that a Markov chain {Z_{t}}_{t=0}^{∞} with transition probabilities a_{ij} := Pr(Z_{t+1} = j | Z_{t} = i) on the state space {1, …, n} is stationary if π_{i} := Pr(Z_{t} = i) does not depend on t and it is reversible if π_{i} a_{ij} = π_{j} a_{ji} for every i, j ∈ {1, …, n}.

Definition 1.1 (Ball [2]). Given a metric space (X, d) and p ∈ [1, ∞), we say that X has Markov type p if there exists a constant K > 0 such that for every stationary reversible Markov chain {Z_{t}}_{t=0}^{∞} on {1, …, n}, every mapping f : {1, …, n} → X and every time t ∈ ℕ,

𝔼 d(f(Z_{t}), f(Z_{0}))^{p} ≤ K^{p} t 𝔼 d(f(Z_{1}), f(Z_{0}))^{p}.

(Here and throughout, we omit some parentheses and write 𝔼 x^{p} for 𝔼(x^{p}), etc.) The least such K is called the Markov type p constant of X, and is denoted M_{p}(X).

∗Microsoft Research. Email: anaor@microsoft.com.

†Departments of Statistics and Mathematics, University of California, Berkeley. Email: peres@stat.berkeley.edu.

‡Microsoft Research. Email: schramm@microsoft.com.

§Department of Mathematics, University of California, Berkeley. Email: sheff@math.berkeley.edu.

Ball introduced this concept in his profound study of the Lipschitz extension problem [2] (see Section 2), and the notion of Markov type has since found applications in the theory of bi-Lipschitz embeddings [46, 4]. The main theorem in [2] states that Lipschitz functions from a subset of a metric space X having Markov type 2 into a Banach space with modulus of convexity of power type 2 (see the definition in (3) below) extend to Lipschitz functions defined on all of X. Ball showed that M_{2}(L_{2}) = 1, yet apart from Hilbert space and spaces which embed bi-Lipschitzly into Hilbert space, no other metric spaces were known to have Markov type 2. Ball asked in [2] whether L_{p} for 2 < p < ∞ has Markov type 2, and more generally, whether every Banach space with modulus of smoothness of power type 2 has Markov type 2. Recall that X has modulus of smoothness of power type 2 if for all x, y in the unit sphere of X, we have ∥x + τy∥ + ∥x − τy∥ − 2 ≤ K_{S}τ^{2} for some constant K_{S} = K_{S}(X) < ∞ and all τ > 0 (see also (5) below). Here we answer Ball’s question positively, and prove:

Theorem 1.2. Every normed space with modulus of smoothness of power type 2 has Markov type 2. Moreover, for every 2 ≤ p < ∞, we have M_{2}(L_{p}) ≤ 4\sqrt{p − 1}.

In conjunction with Ball’s extension theorem [2], this implies the following non-linear version of Maurey’s extension theorem [49] (see below), answering a question posed by Johnson and Lindenstrauss in [29].

Theorem 1.3. Let X be a Banach space with modulus of smoothness of power type 2 and let Y be a Banach space with modulus of convexity of power type 2. Then there exists a constant C = C(X, Y) such that for every subset A ⊆ X and every Lipschitz mapping f : A → Y, it is possible to extend f to f̃: X → Y such that ∥f̃∥_{Lip} ≤ C∥f∥_{Lip}.

In particular, for X = L_{p} and Y = L_{q} with 1 < q < 2 < p < ∞, we can take C = O(\sqrt{(p − 1)/(q − 1)}) (but even the finiteness of C in this case wasn’t known). Additional geometric applications of Theorem 1.3 will be discussed later in this introduction.

Our methods yield Markov type 2 for several new classes of spaces; in particular we have the following result, which answers positively a question posed in [56].

Theorem 1.4. There exists a universal constant C > 0 such that for every tree T with arbitrary positive edge lengths,

M_{2}(T) ≤ C.

In this theorem, as well as in Theorem 1.5 and Corollary 1.6 below, one can take e.g. C = 30. On the other hand, we show in Section 8 that the infinite 3-regular tree satisfies M_{2}(T) ≥ \sqrt{3}.

In fact, Theorem 1.4 is a particular case of the following result which holds for arbitrary Gromov hyperbolic spaces. One of many alternative definitions for Gromov-hyperbolic spaces is as follows (background material on this topic can be found in the monographs [23, 8, 24, 64]). Let (X, d) be a metric space. For x, y, r ∈ X the Gromov product with respect to r is defined as:

⟨x|y⟩_{r} := \frac{d(x, r) + d(y, r) − d(x, y)}{2}.  (1)

For δ ≥ 0, the metric space X is said to be δ-hyperbolic if for every x, y, z, r ∈ X,

⟨x|y⟩_{r} ≥ min {⟨x|z⟩_{r}, ⟨y|z⟩_{r}} − δ,  (2)

and X is Gromov-hyperbolic if it is δ-hyperbolic for some δ < ∞.

For trees, ⟨x|y⟩_{r} is precisely the distance of the least common ancestor of x and y from the root r. It is easy to conclude (and is well known) that every tree is 0-hyperbolic. Thus, the following theorem generalizes Theorem 1.4

Theorem 1.5. There exists a universal constant C > 0 such that for every δ-hyperbolic metric space X, every stationary reversible Markov chain {Z_{t}}_{t=0}^{∞} on {1, …, n}, every f : {1, …, n} → X and every time t ≥ 1,

𝔼 d(f(Z_{t}), f(Z_{0}))^{2} ≤ C^{2} t 𝔼 d(f(Z_{1}), f(Z_{0}))^{2} + C^{2} δ^{2} (log t)^{2}.

Hyperbolic groups are finitely generated groups on which the word metric is δ-hyperbolic for some 0 ≤ δ < ∞ (see [23]). Since the minimal distance in such metric spaces is 1, we have the following corollary of Theorem 1.5:

Corollary 1.6. There exists a universal constant C > 0 such that for every δ-hyperbolic group G equipped with word metric,

M_{2}(G) ≤ C(1 + δ).

In Section 5 we also prove the following result:

Theorem 1.7. Let X be an n dimensional, complete, simply connected Riemannian manifold with pinched negative sectional curvature, i.e., its sectional curvature takes values in the interval [−R, −r], where 0 < r < R < ∞. Then X has Markov type 2 and M_{2}(X) can be bounded by a function of n, r, R.

This paper is organized as follows. In Section 2 we discuss the history and motivation of Ball’s Markov type 2 problem, as well as the background we require from the geometry of Banach spaces. In Section 3 we briefly describe some applications of our results to the extension problem for Hölder functions and bi-Lipschitz embeddings. Section 4 deals with the behavior of Markov chains in smooth normed spaces, and contains the solution of Ball’s Markov type 2 problem. Section 5 deals with the case of trees and hyperbolic metric spaces. Section 7 proves that the Laakso graphs have Markov type 2. It is also proved there that doubling spaces and planar graphs have a weak form of Markov type 2. Finally, Section 8 contains some open problems.

2 Linear and non-linear type and cotype; the linear and Lipschitz extension problems

The classical Jordan-von Neumann theorem [31] states that Hilbert space is characterized among Banach spaces by the parallelogram identity ∥x + y∥^{2} + ∥x − y∥^{2} = 2∥x∥^{2} + 2∥y∥^{2}. Inductively it follows that the generalized parallelogram identity 2^{−n} ∑_{ε_{i}∈{−1,+1}} ∥ε_{1}x_{1} + … + ε_{n}x_{n}∥^{2} = ∑_{i=1}^{n} ∥x_{i}∥^{2} encodes the rich geometric structure of Hilbert space. In the early 1970’s, the work of Dubinsky-Pełczyńsky-Rosenthal [15], Hoffmann-Jørgensen [27], Kwapien [36], Maurey [48] and Maurey-Pisier [52] has led to the notions of (Rademacher) type and cotype, which are natural relaxations of the generalized parallelogram identity. A Banach space X is said to have type p > 0 if there exists a constant T > 0 such that for every n and every x_{1}, …, x_{n} ∈ X,

\frac{1}{2^{n}} ∑_{ε_{i}∈\{−1,1\}}∥∑_{i=1}^{n} ε_{i}x_{i}∥^{p} ≤ T^{p} ∑_{i=1}^{n} ∥x_{i}∥^{p}.

The least such constant T is called the type p constant of X, and is denoted T_{p}(X). Similarly, X is said to have cotype q if there exists a constant C > 0 such that for every n and every x_{1}, …, x_{n} ∈ X,

\frac{1}{2^{n}} ∑_{ε_{i}∈\{−1,1\}}∥∑_{i=1}^{n} ε_{i}x_{i}∥^{q} ≥ \frac{1}{C^{q}} ∑_{i=1}^{n} ∥x_{i}∥^{q}.

The least such constant C is called the cotype q constant of X, and is denoted C_{q}(X).

These seemingly simple parameters turn out to encode a long list of geometric and analytic properties of a normed space X, and in the past three decades the theory of type and cotype has developed into a deep and rich theory. We refer to the survey article [51], the books [44, 53, 60, 66, 14] and the references therein for numerous results and techniques in this direction.

A fundamental result of Maurey [49] states that any bounded linear operator from a linear subspace of a Banach space with type 2 into a Banach space of cotype 2 extends to a bounded linear operator defined on the entire space. More precisely:

Theorem 2.1 (Maurey’s extension theorem). Let X, Y be Banach spaces, Z a linear subspace of X and T : Z → Y a bounded linear operator. Then there exists a linear operator T̃ : X → Y such that T̃|_{Z} = T and ∥T̃∥ ≤ T_{2}(X) C_{2}(Y) ∥T ∥.

The extension problem for linear operators between Banach spaces is a linear variant of the classical Lipschitz extension problem which asks for conditions on a pair of metric spaces X, Y implying that every Lipschitz function defined on a subset of X taking values in Y can be extended to a Lipschitz function defined on all of X, with only a bounded multiplicative loss in the Lipschitz constant. Formally, let X, Y be metric spaces and denote by e(X, Y) the least constant K such that for every Z ⊆ X every Lipschitz function f : Z → Y can be extended to a function f̃: X → Y satisfying ∥f̃∥_{Lip} ≤ K∥f∥_{Lip} (if no such K exists we set e(X, Y) = ∞). Estimating e(X, Y) under various geometric conditions on X and Y is a classical problem which dates back to the 1930’s. We refer to [65, 6, 41] and the references therein for an account of known results on Lipschitz extension.

The modern theory of the Lipschitz extension problem between normed spaces starts with the work of Marcus-Pisier [47] and Johnson-Lindenstrauss [29]. In [29] it is asked if there is a nonlinear analog of Maurey’s extension theorem. To investigate this question it is clearly necessary to develop non-linear variants of type and cotype. While there has been substantial progress in the past 20 years on non-linear notions of type, a satisfactory notion of non-linear cotype remains elusive. Enflo [17, 18, 19] studied the notion of roundness of metric spaces and subsequently in [20], generalized roundness to a notion which is known today as Enflo type. Let X be a metric space and fix n ∈ ℕ. An n-dimensional cube in X is a mapping ε ↦ x_{ε} from {−1, 1}^{n} to X. X is said to have Enflo type p with constant K if for every n and every n dimensional cube x : {−1, 1}^{n} → X,

∑_{ε∈{−1,1}^{n}} d(x_{ε}, x_{−ε})^{p} ≤ K^{p} ∑_{ε∼ε′} d(x_{ε}, x_{ε′})^{p},

where ε ∼ ε′ if ∥ε − ε′∥_{1} = 2.

In the case of normed spaces X, Enflo type p clearly implies Rademacher type p — this follows by considering cubes of the form x_{ε} = ∑_{i=1}^{n} ε_{i} y_{i}, where y_{1}, …, y_{n} ∈ X. A variant of Enflo type was introduced and studied by Bourgain, Milman and Wolfson in [9] (see also [59]). In [56], it was shown that for a wide class of normed spaces, Rademacher type p implies Enflo type p. Despite the usefulness of these notions of non-linear type to various embedding problems, they have not yielded extension theorems for Lipschitz functions.

A breakthrough on the Lipschitz extension problem was obtained in the paper of Ball [2], where he introduced the notion of Markov type p (which, as shown in [56], implies Enflo type p).

To state the main result of [2] we need to recall the notions of uniform convexity and smoothness of normed spaces (see [44] for a detailed account of this theory). Let (X, ∥ · ∥) be a normed space. The modulus of uniform convexity of X is defined for ε ∈ [0, 2] as

δ_{X}(ε) = inf \{1 − \frac{∥x + y∥}{2} : x, y ∈ X, ∥x∥ = ∥y∥ = 1, ∥x − y∥ = ε\} .  (3)

The normed space X is said to be uniformly convex if δ_{X}(ε) > 0 for all ε ∈ (0, 2]. Furthermore, X is said to have modulus of convexity of power type q if there exists a constant c such that δ(ε) ≥ c ε^{q} for all ε ∈ [0, 2]. It is straightforward to check that in this case q ≥ 2. By Proposition 7 in [3] (see also [21]), X has modulus of convexity of power type q if and only if there exists a constant K > 0 such that for every x, y ∈ X

2 ∥x∥^{q} + \frac{2}{K^{q}} ∥y∥^{q} ≤ ∥x + y∥^{q} + ∥x − y∥^{q}.  (4)

The least K for which (4) holds is called the q-convexity constant of X, and is denoted K_{q}(X). The modulus of uniform smoothness of X is defined for τ > 0 as

ρ_{X}(τ) = sup \{\frac{∥x + τy∥ + ∥x − τy∥}{2} − 1 : x, y ∈ X, ∥x∥ = ∥y∥ = 1\} .  (5)

X is said to be uniformly smooth if lim_{τ→0} \frac{ρ_{X}(τ)}{τ} = 0. Furthermore, X is said to have modulus of smoothness of power type p if there exists a constant K such that ρ_{X}(τ) ≤ Kτ^{p} for all τ > 0. It is straightforward to check that in this case necessarily p ≤ 2. By Proposition 7 in [3], ρ_{X}(τ) ≤ Kτ^{p} for every τ > 0 if and only if there exists a constant S > 0 such that for every x, y ∈ X

∥x + y∥^{p} + ∥x − y∥^{p} ≤ 2 ∥x∥^{p} + 2 S^{p} ∥y∥^{p}.  (6)

The least S for which (6) holds is called the p-smoothness constant of X, and is denoted S_{p}(X).

It was shown in [3] (see also [21]) that K_{2}(L_{p}) ≤ 1/\sqrt{p − 1} for 1 < p ≤ 2, and S_{2}(L_{p}) ≤ \sqrt{p − 1} for 2 ≤ p < ∞ (the order of magnitude of these constants was first calculated in [25]).

In [22, 21] (see also [44], Theorem 1.e.16.) it is shown that if a Banach space X has modulus of convexity of power type q then X also has cotype q. Similarly, if X has modulus of smoothness of power type p then X has type p. Observe that L_{1} has cotype 2 (see [44, 53]), but it is clearly not uniformly convex. There also exist spaces of type 2 which are not uniformly smooth [28, 61], but these spaces are much harder to construct. For all the classical reflexive spaces, the power type of smoothness and convexity coincide with their type and cotype, respectively.

Thus, in the context of uniformly convex and uniformly smooth spaces, one can ask the following variant of the Johnson-Lindenstrauss question: is it true that e(X, Y) < ∞ whenever X is a Banach space with modulus of smoothness of power type 2 and Y is a Banach space with modulus of convexity of power type 2? This is precisely the problem studied by Ball in [2], who proved the following theorem:

Theorem 2.2 (Ball’s extension theorem). Let X be a metric space, and Y a Banach space with modulus of convexity of power type 2. Then e(X, Y) ≤ 6 M_{2}(X) K_{2}(Y).

In particular, Ball showed that M_{2}(L_{2}) = 1, whence e(L_{2}, L_{p}) ≤ 6/\sqrt{p − 1} for 1 < p ≤ 2. Subsequently, in a difficult paper that is not based on the Markov type approach, Tsar’kov [63] showed that every Banach space X with modulus of smoothness of power type 2 satisfies e(X, L_{2}) < ∞.

Here we prove the following result:

Theorem 2.3. Fix 1 < q ≤ 2 and let X be a normed space with modulus of smoothness of powertype q. Then

M_{q}(X) ≤ \frac{8}{(2^{q+1} − 4)^{1/q}} S_{q}(X).

In particular, for every 2 ≤ p < ∞,

M_{2}(L_{p}) ≤ 4\sqrt{p − 1}.

In conjunction with Ball’s extension theorem, we obtain a non-linear analog of Maurey’s extension theorem:

Theorem 2.4. For every two Banach spaces X, Y,

e(X, Y) ≤ 24 S_{2}(X) K_{2}(Y).

In particular, for 2 ≤ p < ∞ and 1 < q ≤ 2,

e(L_{p}, L_{q}) ≤ 24\sqrt{\frac{p − 1}{q − 1}}.

3 Some additional geometric applications

In [55] the extension problem for Hölder functions was studied. Let X, Y be metric spaces. Recall that a function f : X → Y is α Hölder with constant K if for every x, y ∈ X, d(f(x), f(y)) ≤ Kd(x, y)^{α}. Following [55] We denote by A(X, Y) the set of all α > 0 such that for all D ⊆ X any α Hölder function f : D → Y can be extended to an α Hölder function defined on all of X with the same constant. Analogously, B(X, Y) denotes the set of all α > 0 for which there exists a constant C > 0 such that for all D ⊆ X any function f : D → Y which is α Hölder with constant K can be extended to a function defined on all of X which is α Hölder with constant CK. In [55] the following theorem was proved, which shows that the isometric and isomorphic extension problems for Hölder functions between L_{p} spaces exhibit a phase transition: for 1 < p, q ≤ 2 we have A(L_{p}, L_{q}) = (0, p/q^{∗}] while B(L_{p}, L_{q}) = (0, p/2], where q^{∗} = q/(q − 1) (note that for 1 < q < 2 we have p/q^{∗} < p/2). Additionally, for any p/2 < α ≤ 1 there is an α Hölder function from a subset of L_{p} to L_{q} which cannot be extended to an α Hölder function defined on all of L_{p}.

The sets A(L_{p}, L_{q}) were calculated in [65] for all values of p, q. It is shown there that:

A(L_{p}, L_{q}) = \{ \begin{matrix}(0, p/q^{∗}] , & if 1 < p, q ≤ 2, \\ (0, p/q] , & if 1 < p ≤ 2 ≤ q < ∞, \\ (0, p^{∗}/q] , & if 2 ≤ p, q < ∞, \\ (0, p^{∗}/q^{∗}] , & if 2 ≤ p < ∞ and 1 < q ≤ 2. \end{matrix}

As noted in [55], the solution of Ball’s Markov type 2 problem (i.e., Theorem 2.3) completes the computation of the sets B(L_{p}, L_{q}):

B(L_{p}, L_{q}) = \{ \begin{matrix}(0, p/2] , & if 1 < p, q ≤ 2, \\ (0, p/q] , & if 1 < p ≤ 2 ≤ q < ∞, \\ (0, 2/q] , & if 2 ≤ p, q < ∞, \\ (0, 1] , & if 2 ≤ p < ∞ and 1 < q ≤ 2. \end{matrix}

We end with some applications of our results to the theory of bi-Lipschitz embeddings of finite metric spaces into normed spaces. Given two metric spaces X, Y and a one-to-one mapping f : X ↪ Y, its distortion is defined as dist(f) = ∥f∥_{Lip} · ∥f^{−1}∥_{Lip}. In [46, 4] it was shown that if G is a finite graph with girth g (i.e., the length of the shortest closed cycle in G is g) and average degree δ > 2, then every embedding of G (with the graph metric) into Hilbert space incurs distortion at least \frac{δ−2}{2δ} \sqrt{g}. In fact, the same proof shows that any embedding of G into a metric space X of Markov type p incurs distortion at least \frac{δ−2}{2M_{p}(X)}g^{(p−1)/p}. We thus obtain new classes of spaces into which large girth graphs cannot embed with low distortion. In particular, any embedding of G into L_{p} for p > 2, incurs at least the distortion \frac{δ−2}{8δ} \sqrt{g/p}.

In [4] the metric Ramsey problem for the Hamming cube Ω_{d} = {0, 1}^{d} (with the L_{1} metric) was studied, and it was shown that if A ⊆ Ω_{d} embeds in Hilbert space with distortion D, then |A| ≤ |Ω_{d}|^{1−c_{∗}/D^{2}}. (Here, c_{∗} is a universal constant. This estimate is shown in [4] to be optimal up to logarithmic terms.) The proof of this fact is heavily based on the analysis of Markov chains on subsets of the cube, and on the fact that Hilbert space has Markov type 2. The same result holds true for embeddings into any metric space X of Markov type 2, with the constant c replaced by c_{∗}/M_{2}(X)^{2}.

In [56] it was shown that any embedding of the Hamming cube {0, 1}^{d} into L_{p}, p > 2, incurs distortion at least c_{p}\sqrt{d}, where c_{p} depends only on p. Using Theorem 2.3 it is possible to obtain the optimal dependence of c_{p} on p, namely any embedding of {0, 1}^{d} into L_{p}, p > 2, incurs distortion at least \frac{1}{20} max\{1, \sqrt{d/p}\}. This follows directly from Theorem 2.3 by considering the Markov chain corresponding to the standard random walk on the Hamming cube. The fact that this lower bound is optimal follows from the following embedding. Let ε_{1}, … ε_{d} be i.i.d. symmetric ±1 valued Bernoulli random variables and map x ∈ {0, 1}^{d} to the random variable Y_{x} := ∑_{i=1}^{d} x_{i}ε_{i}. It is well

known (see e.g. [39]) that for every integer k ≤ d, (𝔼 |∑_{i=1}^{k} ε_{i}|^{p})^{1/p} = Θ (min\{k, \sqrt{pk}\}), implying

that for p ≤ d and x, y ∈ \{0, 1\}^{d}, c\sqrt{p/d} · ∥x − y∥_{1} ≤ (E|Z_{x} − Z_{y}|^{p})^{1/p} ≤ ∥x − y∥_{1}, where c is a universal constant. Thus the embedding x ↦ Z_{x} incurs distortion Ω(\sqrt{d/p}). An application of having good bounds in terms of p on the L_{p} distortion of the Hamming cube is the following. In [42] it was shown that if {0, 1}^{d} embeds into ℓ_{∞}^{k} with distortion D then k ≥ 2^{Ω(d/D^{2})}. This fact easily follows from the above discussion via an argument similar to that of [40]: By Hölder’s inequality ℓ_{∞}^{k} and ℓ_{p}^{k} are O(1) equivalent when p = log k. Thus, the fact that {0, 1}^{d} embeds into ℓ_{∞}^{k} with distortion D implies that D ≥ Ω(\sqrt{d/p}) = Ω(\sqrt{d/ log k}), which simplifies to give the claimed lower bound on k.

4 Markov chains in smooth normed spaces

We begin by recalling why the real line has Markov type 2. Let {Z_{t}}_{t=0}^{∞} be a stationary reversible Markov chain on {1, …, n}, with transition matrix A = (a_{ij}), and stationary distribution π. The Markov type 2 inequality (with constant 1) for ℝ simply says that for every x_{1}, …, x_{n} ∈ ℝ, we have ∑_{i,j} π_{i} (A^{t})_{ij} (x_{i} − x_{j})^{2} ≤ t ∑_{i,j} π_{i} a_{ij} (x_{i} − x_{j})^{2}. In fact, the stronger inequality

∑_{i,j} π_{i} (A^{t})_{ij} (x_{i} − x_{j})^{2} ≤ Λ(t) ∑_{i,j} a_{ij} π_{i} (x_{i} − x_{j})^{2}  (7)

holds, where Λ(t) := \frac{1−λ^{t}}{1−λ} = 1 + λ + ⋯ + λ^{t−1} and λ is the second largest eigenvalue of A. (Recall that −1 ≤ λ < 1.) Indeed, since π_{i} (A^{t})_{ij} = π_{j} (A^{t})_{ji}, expanding the square in (7) shows that inequality may be rewritten

⟨(I − A^{t})x, x⟩_{π} ≤ Λ(t) ⟨(I − A)x, x⟩_{π} ,  (8)

where x is the column vector (x_{1}, …, x_{n}), and ⟨·, ·⟩_{π} refers to the inner product in L^{2}(π). If x is an eigenvector, then (7) is clear; the general case follows by a spectral decomposition (note that A is self-adjoint on L^{2}(π)).

The proof of the following lemma is a slight modification of the proof of Lemma 3.1 in [2]. Let L_{q}(X) denote the collection of Borel measurable f : [0, 1] → X with 𝔼∥f∥^{q} = ∫_{0}^{1} ∥f∥^{q} < ∞. It is a Banach space with norm (𝔼∥f∥^{q})^{1/q}. (Of course, the choice of the interval [0, 1] as the domain for f is rather arbitrary. It may be replaced with any probability space equivalent to [0, 1].)

Lemma 4.1. Fix 1 < q ≤ 2 and let Z ∈ L_{q}(X). Then

𝔼∥Z∥^{q} ≤ ∥EZ∥^{q} + \frac{S_{q}(X)^{q}}{2^{q−1} − 1} · 𝔼∥Z − 𝔼Z∥^{q}.

Proof. Let θ ≥ 0 be the largest constant such that for every Z ∈ L_{q}(X),

θ (𝔼∥Z∥^{q} − ∥EZ∥^{q}) ≤ 𝔼∥Z − 𝔼Z∥^{q}.

Our goal is to show that θ ≥ (2^{q−1} − 1)S_{q}(X)^{−q}. To this end, fix ε > 0 and Z ∈ L_{q}(X) such that

(θ + ε) (𝔼∥Z∥^{q} − ∥EZ∥^{q}) > 𝔼∥Z − 𝔼Z∥^{q}.

By the definition (6) of S_{q}(X) applied to the vectors x = (Z + 𝔼Z)/2 and y = (Z − 𝔼Z)/2, we have the pointwise inequality:

∥Z∥^{q} + ∥𝔼Z∥^{q} ≤ 2∥\frac{1}{2}Z + \frac{1}{2}𝔼Z∥^{q} + 2 S_{q}(X)^{q}∥\frac{1}{2}Z − \frac{1}{2}𝔼Z∥^{q}.

Taking expectations, we find that

\frac{1}{θ + ε}𝔼∥Z − 𝔼Z∥^{q} < 𝔼∥Z∥^{q} − ∥EZ∥^{q}
≤ 2 (𝔼∥\frac{1}{2}Z + \frac{1}{2}𝔼Z∥^{q} − ∥𝔼 (\frac{1}{2}Z + \frac{1}{2}𝔼Z)∥^{q}) + 2 S_{q}(X)^{q} 𝔼∥\frac{1}{2}Z − \frac{1}{2}𝔼Z∥^{q}
≤ \frac{2}{θ} 𝔼∥\frac{1}{2}Z − \frac{1}{2}𝔼Z∥^{q} + 2 S_{q}(X)^{q} 𝔼∥\frac{1}{2}Z − \frac{1}{2}𝔼Z∥^{q}.

It follows that \frac{2^{q}}{θ+ε} ≤ \frac{2}{θ} + 2S_{q}(X)^{q}. Letting ε tend to zero, and simplifying, yields the required result.

The following theorem, first proved in [57] (without the explicit constant), is a simple corollary of Lemma 4.1 (see also Proposition 3.3 in [2]).

Theorem 4.2 (Pisier). Fix 1 < q ≤ 2 and let {M_{k}}_{k=0}^{n} ⊆ L_{q}(X) be a martingale in X. Then

𝔼∥M_{n} − M_{0}∥^{q} ≤ \frac{S_{q}(X)^{q}}{2^{q−1} − 1} · ∑_{k=0}^{n−1} 𝔼∥M_{k+1} − M_{k}∥^{q}.

Proof. Assume that {M_{k}}_{k=0}^{n} is a martingale with respect to the filtration F_{0} ⊆ F_{1} ⊆ ⋯ ⊆ F_{n−1}; that is, 𝔼 (M_{i+1}|F_{i}) = M_{i} for i = 0, 1, …, n − 1. By Lemma 4.1 with conditioned expectation replacing expectation,

𝔼 (∥M_{n} − M_{0}∥^{q}| F_{n−1}) ≤ ∥M_{n−1} − M_{0}∥^{q} + \frac{S_{q}(X)^{q}}{2^{q−1} − 1} · 𝔼(∥M_{n} − M_{n−1}∥^{q}|F_{n−1}).

Hence

𝔼∥M_{n} − M_{0}∥^{q} ≤ 𝔼 ∥M_{n−1} − M_{0}∥^{q} + \frac{S_{q}(X)^{q}}{2^{q−1} − 1} · 𝔼∥M_{n} − M_{n−1}∥^{q},

and the required inequality follows by induction.

The following lemma is motivated by the continuous martingale decompositions of Stochastic integrals constructed in [45].

Lemma 4.3. Let X be a normed space, {Z_{t}}_{t=0}^{∞} a stationary reversible Markov chain on {1, …, n} and f : {1, …, n} → X. Then for every t ∈ ℕ there are two X-valued martingales {M_{s}}_{s=0}^{t} and {N_{s}}_{s=0}^{t} (with respect to two different filtrations) with the following properties:

1. For every 1 ≤ s ≤ t − 1 we have that

f(Z_{s+1}) − f(Z_{s−1}) = (M_{s+1} − M_{s}) − (N_{t−s+1} − N_{t−s}).  (9)

2. For every 0 ≤ s ≤ t − 1 and q ≥ 1,

max {𝔼∥M_{s+1} − M_{s}∥^{q}, 𝔼∥N_{s+1} − N_{s}∥^{q}} ≤ 2^{q} 𝔼∥f(Z_{1}) − f(Z_{0})∥^{q}.  (10)

Proof. Let A = (a_{ij}) be the transition matrix of Z_{t}, and let π_{i} := Pr(Z_{0} = i). Define

Lf(i) = ∑_{j=1}^{n} a_{ij}[f(j) − f(i)] = ∑_{j=1}^{n} a_{ij}f(j) − f(i).

Then

𝔼(f(Z_{s})|Z_{0}, …, Z_{s−1}) = 𝔼(f(Z_{s})|Z_{s−1}) = Lf(Z_{s−1}) + Z_{s−1}.

Since {Z_{s}}_{s=0}^{∞} is reversible, we also have that for every 0 ≤ s < t,

𝔼(f(Z_{s})|Z_{s+1}, …, Z_{t}) = Lf(Z_{s+1}) + f(Z_{s+1}).

It follows that if we define M_{0} = f(Z_{0}) and for s ≥ 1:

M_{s} := f(Z_{s}) − ∑_{r=0}^{s−1} Lf(Z_{r}).

then

𝔼(M_{s}|Z_{0}, …, Z_{s−1}) = Lf(Z_{s−1}) + f(Z_{s−1}) − ∑_{r=0}^{s−1} Lf(Z_{r}) = M_{s−1},

i.e., {M_{s}}_{s=0}^{∞} is a martingale with respect to the natural filtration induced by {Z_{s}}_{s=0}^{∞}. Now, define N_{0} := f(Z_{t}) and for 1 ≤ s ≤ t

N_{s} := f(Z_{t−s}) − ∑_{r=t−s+1}^{t} Lf(Z_{r}).

Then for s ≥ 1,

𝔼(N_{s}|Z_{t−s+1}, …, Z_{t}) = N_{s−1},

i.e., {N_{s}}_{s=0}^{t} is a martingale with respect to the natural filtration induced by Z_{t}, Z_{t−1}, …, Z_{0} (in probabilistic terminology, {N_{t−s}}_{s=0}^{t} is a reverse martingale).

The identities

M_{s+1} − M_{s} = f(Z_{s+1}) − f(Z_{s}) − Lf(Z_{s}), N_{s+1} − N_{s} = f(Z_{t−s−1}) − f(Z_{t−s}) − Lf(Z_{t−s}).

imply (9). To prove (10) observe that for every s ≥ 0 and q ≥ 1,

𝔼∥Lf(Z_{s})∥^{q} = ∑_{i=1}^{n} π_{i}∥∑_{j=1}^{n} a_{ij}[f(j) − f(i)]∥^{q} ≤ ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}∥f(j) − f(i)∥^{q} = 𝔼∥f(Z_{1}) − f(Z_{0})∥^{q}.

Therefore,

𝔼∥M_{s+1} − M_{s}∥^{q} = 𝔼∥f(Z_{s+1}) − f(Z_{s}) − Lf(Z_{s})∥^{q}

≤ 2^{q−1} 𝔼∥f(Z_{s+1}) − f(Z_{s})∥^{q} + 2^{q−1} 𝔼∥Lf(Z_{s})∥^{q} ≤ 2^{q} 𝔼∥f(Z_{1}) − f(Z_{0})∥^{q},

and similarly, 𝔼∥N_{s+1} − N_{s}∥^{q} ≤ 2^{q} 𝔼∥f(Z_{1}) − f(Z_{0})∥^{q}.

Proof of Theorem 2.3. Let {Z_{s}}_{s=0}^{t}, f, {M_{s}}_{s=0}^{t} and {N_{s}}_{s=0}^{t} be as in Lemma 4.3. Assume first that t is even, and write t = 2m. Summing the identity (9) over s = 1, 3, 5, …, 2m − 1 we get

f(Z_{t}) − f(Z_{0}) = ∑_{k=1}^{t/2}(M_{2k} − M_{2k−1}) − ∑_{k=1}^{t/2}(N_{2k} − N_{2k−1}).

By Theorem 4.2 (applied to the martingales ∑_{k=1}^{s}(M_{2k} − M_{2k−1}) and ∑_{k=1}^{s}(N_{2k} − N_{2k−1})), we conclude that

𝔼∥f(Z_{t}) − f(Z_{0})∥^{q} ≤ 2^{q−1}𝔼 ∥∑_{k=1}^{t/2}(M_{2k} − M_{2k−1})∥^{q} + 2^{q−1}𝔼 ∥∑_{k=1}^{t/2}(N_{2k} − N_{2k−1})∥^{q}

≤ \frac{2^{q−1}S_{q}(X)^{q}}{2^{q−1} − 1} ∑_{k=1}^{t/2}(𝔼 ∥M_{2k} − M_{2k−1}∥^{q} + 𝔼 ∥N_{2k} − N_{2k−1}∥^{q})

≤ \frac{2^{q−1}S_{q}(X)^{q}}{2^{q−1} − 1} \frac{t}{2} 2^{q+1}𝔼 ∥f(Z_{1}) − f(Z_{0})∥^{q}.

When t is odd, apply the above reasoning at time t − 1, to get

𝔼 ∥f(Z_{t}) − f(Z_{0})∥^{q} ≤ 2^{q−1}𝔼 ∥f(Z_{t−1}) − f(Z_{0})∥^{q} + 2^{q−1}𝔼 ∥f(Z_{t}) − f(Z_{t−1})∥^{q}
≤ (\frac{2^{3q−2}S_{q}(X)^{q}}{2^{q−1} − 1} (t − 1) + 2^{q−1}) 𝔼 ∥f(Z_{1}) − f(Z_{0})∥^{q}
≤ \frac{2^{3q−2}S_{q}(X)^{q}}{2^{q−1} − 1} t 𝔼 ∥f(Z_{1}) − f(Z_{0})∥^{q}.

There are various natural variants of the notion of Markov type. The following theorem deals with other moment inequalities for Markov chains in uniformly smooth normed spaces:

Theorem 4.4. For every p ∈ (1, ∞) and q ∈ (1, 2] there is a constant C(p, q) ∈ (0, ∞) with the following properties. Let X be a normed space with modulus of smoothness of power type q. Then for every reversible Markov chain on {1, …, n}, {Z_{t}}_{t=0}^{∞}, and every f : {1, …, n} → X, if p ≤ q, then

𝔼 ∥f(Z_{t}) − f(Z_{0})∥^{p} ≤ C(p, q) S_{q}(X)^{q} t 𝔼 ∥f(Z_{1}) − f(Z_{0})∥^{p},

i.e., X has Markov type p. If p > q, then

𝔼 ∥f(Z_{t}) − f(Z_{0})∥^{p} ≤ C(p, q) S_{q}(X)^{p} t^{p/q} 𝔼 ∥f(Z_{1}) − f(Z_{0})∥^{p}.

Proof. Observe that by the definition of S_{q}(X), for every τ > 0, ρ_{X}(τ) ≤ S_{q}(X)^{q} τ^{q}. Since ρ_{X}(τ) ≤ τ, assuming p < q and ρ_{X}(τ) ≤ Kτ^{q}, where K ≥ 1, we have ρ_{X}(τ) ≤ Kτ^{p}. By (the proof of) Proposition 7 in [3], it follows that for 1 < p ≤ q, S_{p}(X) ≤ C S_{q}(X)^{q/p}, where C depends only on p, q. The first result now follows from Theorem 2.3.

Assume now that p > q. To prove the second assertion, observe that by a theorem of Figiel [21] (combined with [3, Proposition 7]), S_{q}(L_{p}(X)) ≤ CS_{q}(X), where C depends only on p, q. Recall that a sequence of elements x_{1}, x_{2}, … in a Banach space Y is called a monotone basic sequence if for every a_{1}, a_{2}, … ∈ ℝ and every integer n,

∥∑_{i=1}^{n} a_{i}x_{i}∥ ≤ ∥∑_{i=1}^{n+1} a_{i}x_{i}∥.

By a result of Lindenstrauss [43] (see also [57, Proposition 2.2]), for a Banach space Y, if ρ_{Y} (τ) ≤ Kτ^{q} for all τ, then for every monotone basic sequence {x_{i}}_{i≥0} in Y,

∥∑_{i=1}^{n} x_{i}∥^{q} ≤ 4^{q} K ∑_{i=1}^{n} ∥x_{i}∥^{q}.

Let {M_{i}}_{i≥0} ⊆ L_{p}(X) be an X-valued martingale. By convexity, it follows that {(M_{i} − M_{i−1})}_{i≥1} is a monotone basic sequence in L_{p}(X). Moreover, ρ_{Y} (τ) ≤ S_{q}(Y)^{q} τ^{q} for every normed space Y. Hence, for every n,

∥M_{n} − M_{0}∥_{L_{p}(X)}^{q} ≤ [4CS_{q}(X)]^{q} ∑_{i=1}^{n} ∥M_{i} − M_{i−1}∥_{L_{p}(X)}^{q}.

In other words,

𝔼 ∥M_{n} − M_{0}∥^{p} ≤ [4CS_{q}(X)]^{p} (∑_{i=1}^{n}(𝔼 ∥M_{i} − M_{i−1}∥^{p})^{q/p})^{p/q} = [4CS_{q}(X)]^{p} n^{p/q} 𝔼 ∥M_{1} − M_{0}∥^{p}.

We now conclude the proof exactly as in the proof of Theorem 2.3.

We now state the case X = ℝ, q = 2 of the second part of Theorem 4.4 with explicit constants.

Theorem 4.5. Let p ∈ (2, ∞). for every reversible stationary finite Markov chain {Z_{t}}_{t=0}^{∞} on {1, …, n} and every f : {1, …, n} → ℝ, we have for all t ≥ 1:

(𝔼|f(Z_{t}) − f(Z_{0})|^{p})^{1/p} ≤ 16 \sqrt{p t} (𝔼|f(Z_{1}) − f(Z_{0})|^{p})^{1/p} .

The proof follows from the above argument, using S_{2}(L_{p}) ≤ \sqrt{p − 1} for p > 2 ([3], see also [21]). By considering the standard random walk on {1, 2, …, n} it follows that the dependence on p in Theorem 4.5 is optimal, up to a universal multiplicative factor.

5 Markov chains in trees and hyperbolic metric spaces

In this section we prove Theorem 1.5 and Theorem 1.7. We do not attempt to optimize the constants. In particular, in the case of trees a more careful analysis shows that one may take C = 8 in Theorem 1.4. Since we do not believe that this is the optimal constant, we use rougher estimates. In Section 8 we show that the infinite 3-regular tree satisfies M_{2}(T) ≥ \sqrt{3}.

Lemma 5.1. Let {Z_{t}}_{t=0}^{∞} be a reversible Markov chain on {1, …, n} and f : {1, …, n} → ℝ. Then for every time t > 0,

𝔼 max_{0≤s≤t}[f(Z_{s}) − f(Z_{0})]^{2} ≤ 100 t 𝔼[f(Z_{1}) − f(Z_{0})]^{2}.

Naturally, the proof relies on Doob’s L^{2} maximal inequality for submartingales

𝔼 max_{0≤s≤t} M_{s}^{2} ≤ 4 𝔼|M_{t}|^{2} .  (11)

See, e.g., [16, §4.4].

Proof. Let {M_{s}}_{s=0}^{t} and {N_{s}}_{s=0}^{t} be as in Lemma 4.3. Observe that

max_{0≤s≤t}[f(Z_{s}) − f(Z_{0})]^{2} ≤ 2 max_{\begin{matrix}0≤s≤t \\ s even \end{matrix}}[f(Z_{s}) − f(Z_{0})]^{2} + 2 max_{\begin{matrix}1≤s≤t \\ s odd \end{matrix}}[f(Z_{s}) − f(Z_{s−1})]^{2}.
≤ 2 max_{\begin{matrix}0≤s≤t \\ s even \end{matrix}}[f(Z_{s}) − f(Z_{0})]^{2} + 2 ∑_{\begin{matrix}1≤s≤t \\ s odd \end{matrix}}[f(Z_{s}) − f(Z_{s−1})]^{2}.

Therefore,

𝔼 max_{0≤s≤t}[f(Z_{s}) − f(Z_{0})]^{2} ≤ 2 𝔼 max_{\begin{matrix}0≤s≤t \\ s even \end{matrix}}[f(Z_{s}) − f(Z_{0})]^{2} + (t + 1) 𝔼[f(Z_{1}) − f(Z_{0})]^{2}. (12)

For even s we have as in the proof of Theorem 2.3 that

f(Z_{s}) − f(Z_{0}) = ∑_{k=1}^{s/2}(M_{2k} − M_{2k−1}) − ∑_{k=1}^{s/2}(N_{2k} − N_{2k−1}).

Thus, Doob’s inequality gives

𝔼 max_{\begin{matrix}0≤s≤t \\ s even \end{matrix}}[f(Z_{s}) − f(Z_{0})]^{2} ≤ 2 𝔼 max_{0≤i≤t/2} [∑_{k=1}^{i}(M_{2k} − M_{2k−1})]^{2} + 2 𝔼 max_{0≤i≤t/2} [∑_{k=1}^{i}(N_{2k} − N_{2k−1})]^{2}

≤ 8 𝔼 [ ∑_{k=1}^{⌊t/2⌋}(M_{2k} − M_{2k−1})]^{2} + 8 𝔼 [ ∑_{k=1}^{⌊t/2⌋}(N_{2k} − N_{2k−1})]^{2}

= 8 ∑_{k=1}^{⌊t/2⌋} 𝔼(M_{2k} − M_{2k−1})^{2} + 8 ∑_{k=1}^{⌊t/2⌋} 𝔼(N_{2k} − N_{2k−1})^{2}  (13)
≤ 32 t 𝔼[f(Z_{1}) − f(Z_{0})]^{2},

where in (13) we have used the fact that the martingale differences are orthogonal and for the next inequality we used (10).

Together with (12), this concludes the proof.

In what follows we use the notation of the Gromov product (1).

Lemma 5.2. Let X be a δ-hyperbolic metric space. Then for every m ≥ 1 and r, x_{0}, …, x_{m} ∈ X

d(x_{0}, x_{m})^{2} ≤ 4 max_{0≤j<m}[d(x_{0}, r) − d(x_{j}, r)]^{2} + 4 max_{0<j≤m}[d(x_{m}, r) − d(x_{j}, r)]^{2} +

+ 4 ∑_{j=0}^{m−1} d(x_{j}, x_{j+1})^{2} + 16 δ^{2}⌈log_{2} m⌉^{2}.

Proof. Suppose first that m is a power of 2, m = 2^{k}. Then (2) gives

⟨x_{0}|x_{m}⟩_{r} ≥ min {⟨x_{0}|x_{m/2}⟩_{r}, ⟨x_{m/2}|x_{m}⟩_{r}} − δ.

Hence, induction gives,

⟨x_{0}|x_{m}⟩_{r} ≥ min{⟨x_{i}|x_{i+1}⟩_{r} : i = 0, 1, …, m − 1} − k δ .  (14)

This also holds when m is not a power of two, provided we take k := ⌈log_{2} m⌉ (for instance, define x_{i} := x_{m} for m < i ≤ 2^{k}). Let j be the index i ∈ {0, 1, …, m − 1} giving the minimum in (14). Then

d(x_{0}, x_{m}) = d(x_{0}, r) + d(x_{m}, r) − 2 ⟨x_{0}, x_{m}⟩
≤ 2 k δ + d(x_{0}, r) + d(x_{m}, r) − 2⟨x_{j}|x_{j+1}⟩
= 2 k δ + (d(x_{0}, r) − d(x_{j}, r)) + (d(x_{m}, r) − d(x_{j+1}, r)) + d(x_{j}, x_{j+1}) .

This implies

d(x_{0}, x_{m})^{2} ≤ 4 (2 k δ)^{2} + 4 (d(x_{0}, r) − d(x_{j}, r))^{2} + 4 (d(x_{m}, r) − d(x_{j+1}, r))^{2} + 4 d(x_{j}, x_{j+1})^{2} .

The lemma follows.

We can now prove Theorem 1.5:

Proof of Theorem 1.5. Fix r ∈ X. By Lemma 5.2 for every t ≥ 1,

𝔼 d(f(Z_{t}), f(Z_{0}))^{2} ≤ 4 𝔼 max_{0≤j≤t−1}[d(f(Z_{0}), r) − d(f(Z_{j}), r)]^{2} +

+ 4 𝔼 max_{0≤j≤t−1}[d(f(Z_{t}), r) − d(f(Z_{j+1}), r)]^{2} + 4 t 𝔼 d(f(Z_{1}), f(Z_{0}))^{2} +

+ 16 δ^{2}⌈log_{2} t⌉^{2}.

By Lemma 5.1 applied to the function g(i) := d(f(i), r) we get

𝔼 max_{0≤j≤t−1}[d(f(Z_{0}), r)−d(f(Z_{j}), r)]^{2} ≤ 100 t 𝔼 [d(f(Z_{1}), r)−d(f(Z_{0}), r)]^{2} ≤ 100 t 𝔼 d(f(Z_{1}), f(Z_{0}))^{2}.

Similarly, since the Markov chain is reversible,

𝔼 max_{0<j≤t}[d(f(Z_{t}), r) − d(f(Z_{j}), r)]^{2} ≤ 100 t 𝔼 d(f(Z_{1}), f(Z_{0}))^{2}.

The proof of Theorem 1.5 is thus complete.

5.1 A lower bound for the Markov type constant of trees

The following example shows that the infinite 3-regular tree Γ_{3} satisfies M_{2}(Γ_{3}) ≥ \sqrt{3}. Fix an integer h and let T_{h} be the complete binary tree of depth h rooted at r. For z ∈ T_{h} denote |z| = d(z, r). Consider the following transition kernel on T_{h}. If z has three neighbors, it goes to its neighbor closer to r with probability 1/2 and to each of the other two neighbors with probability 1/4. Otherwise (z has a single neighbor or z = r), it goes to any of its neighbors with equal probability. This is the transition kernel for a stationary reversible Markov chain {Z_{t}}_{t=0}^{∞} with stationary distribution Pr(Z_{0} = z) = 2^{−|z|}/(h + 1). Denote S̃_{t} = |Z_{0}| − |Z_{t}| and observe that for every positive integer n, conditioned on the event {n ≤ |Z_{0}| ≤ h − n}, the sequence {S̃_{t}}_{t≤n} has the same distribution as {S_{t}}_{t≤n}, the simple random walk on ℤ starting at 0. Denote M_{n} := max_{t≤n} S_{t} and M̃_{n} := max_{t≤n} S̃_{t}. By a theorem of Pitman [62], {2M_{n} − S_{n}}_{n≥0} has the same distribution as {S_{n}}_{n≥0} conditioned on S_{n} > 0 for all n > 0 (which is defined as the limit as m → ∞ of {S_{n}}_{n≥0} conditioned to hit m before revisiting 0). Let Ŝ_{n} denote this conditioned walk, which is a Markov chain with transition probabilities p(x, x ± 1) = (x ± 1)/(2x). Induction easily gives 𝔼Ŝ_{n}^{2} = 3 n, and therefore,

𝔼((2M̃_{n} − S̃_{n})^{2} | n ≤ |Z_{0}| ≤ h − n) = 3 n .

Since Pr(|Z_{0}| ∈ [n, h − n]) = 1 − \frac{2n}{h+1}, we get

𝔼(2M̃_{n} − S̃_{n})^{2} ≥ 3(1 − \frac{2n}{h + 1})n .  (15)

Let v be the (unique) vertex in {Z_{0}, …, Z_{n}} closest to the root, so that |Z_{0}| − |v| = M̃_{n}. Note that v need not be on the geodesic connecting Z_{0} to Z_{n}. Nevertheless, it is unlikely to be far from this geodesic. We now make this precise. Conditioned on Z_{0}, v, M̃_{n} and S̃_{n}, the vertex Z_{n} is distributed uniformly among the vertices u such that |u| = S̃_{n} that are descendents of v (that is, the simple path in T_{h} from u to the root contains v). Therefore conditioned on Z_{0}, v, M̃_{n} the random variable d(Z_{0}, Z_{n}) is distributed as follows: d(Z_{0}, Z_{n}) = 2 M̃_{n} − S̃_{n} − 2 k with probability 2^{−k−1} for integers k satisfying 0 ≤ k < min{M̃_{n}, M̃_{n} − S̃_{n}} and the conditioned probability is 2^{−k} for k = min{M̃_{n}, M̃_{n} − S̃_{n}}. Thus, setting ℓ = min{M̃_{n}, M̃_{n} − S̃_{n}} we have that

𝔼(d(Z_{0}, Z_{n})^{2} | Z_{0}, v, M̃_{n}, S̃_{n}) = ∑_{k=0}^{ℓ−1} 2^{−k−1}(2 M̃_{n} − S̃_{n} − 2 k)^{2} + 2^{−ℓ}(2 M̃_{n} − S̃_{n} − 2 ℓ)^{2}

≥ (2 M̃_{n} − S̃_{n})^{2} − (2 M̃_{n} − S̃_{n}) · ∑_{k=0}^{∞} \frac{4k}{2^{k}}
= (2 M̃_{n} − S̃_{n})^{2} − 8(2 M̃_{n} − S̃_{n}).

Taking expectations and applying Jensen’s inequality gives

𝔼 d(Z_{0}, Z_{n})^{2} ≥ 𝔼(2 M̃_{n} − S̃_{t})^{2} − 8 (𝔼(2 M̃_{n} − S̃_{n})^{2})^{1/2} .

Now, (15) yields

𝔼 d(Z_{0}, Z_{n})^{2} ≥ 3(1 − \frac{2n}{h + 1})n − 8\sqrt{3n} .

By considering, say, h = n^{2}, we deduce that sup_{h} M_{2}(T_{h})^{2} ≥ 3. It follows that M_{2}(Γ_{3})^{2} ≥ 3 for the infinite 3-regular tree Γ_{3}, since it contains all the finite trees T_{h}.

6 Embeddings in products of ℝ-trees and proof of Theorem 1.7

In what follows, given two metric spaces (X, d_{X}) and (Y, d_{Y}), the metric space X × Y is always assumed to be equipped with the metric d((x, y), (x′, y′)) = d_{X}(x, x′) + d_{Y} (y, y′).

A metric d on a space X is a path metric if for every x, y ∈ X there is a path in X from x to y whose length is d(x, y).

An ℝ-tree is a path metric space (T, d) such that for every two distinct points x, y ∈ T there is a unique simple path from x to y in T (see [13, 54]). (Some definitions appearing in the literature also require the metric to be complete.) Equivalently, an ℝ-tree is a 0-hyperbolic metric space whose metric is a path metric.

An r-separated set A in a metric space (X, d) is a subset A ⊆ X such that d(x, x′) ≥ r for every x ≠ x′ in A. An r-net is a maximal r-separated set. If A ⊆ X is an r-net, then X ⊆ ⋃_{a∈A} B(a, r). Clearly, every metric space has an r-net for every r > 0.

Lemma 6.1. Fix an integer n and let Z be an n-dimensional normed space. Let (X, d) be a metric space and D, ε > 0. Assume that every ball of radius ε in X embeds bi-Lipschitzly in Z with distortion at most D. Then there is an integer N = N(n, D), a constant Δ = Δ(n, ε, D) < ∞ and a mapping F : X → Z^{N} which is Lipschitz with constant Δ and for every x, y ∈ X

d(x, y) ≤ \frac{ε}{8} ⟹ d(x, y) ≤ ∥F (x) − F (y)∥.

Proof. Write X_{0} := X. Having defined X_{i} ⊆ X, let A_{i} be an ε-net in X_{i}. Define X_{i+1} = X_{i} \ ⋃_{x∈A_{i}} B(x, ε/4). Observe that if x ∈ X_{i} then for all j ∈ {1, …, i + 1} there is a point a_{j} ∈ A_{j} such that d(x, a_{j}) ≤ ε. Moreover, for j ≠ j′, d(a_{j}, a_{j′}) > ε/4. Our assumption is that for every x ∈ X there is a function ψ_{x} : B(x, ε) → Z such that ψ_{x}(x) = 0 and for all y, z ∈ B(x, ε) we have d(y, z) ≤ ∥ψ_{x}(y) − ψ_{x}(z)∥ ≤ D d(y, z). Then ∥ψ_{x}(a_{j})∥ ≤ ε D and the balls B(ψ_{x}(a_{j}), ε/8)⊆ B(0, ε (D + 1/8)) ⊆ Z are disjoint. Comparison of volumes therefore gives i + 1 ≤ (8D + 1)^{n}. We have shown that there exists an integer N ≤ (8D + 1)^{n} and disjoint subsets A_{1}, …, A_{N} ⊆ X such that for each j, if a, b ∈ A_{j} then d(a, b) > ε and X ⊆ ⋃_{j=1}^{N} ⋃_{a∈A_{j}} B(a, ε/4).

For every j ≤ N define for a ∈ A_{j} and x ∈ B(a, ε/2),

f_{j}(x) := \begin{cases}ψ_{a}(x) & if d(x, a) ≤ 3ε/8, \\ (4 − 8 ε^{−1} d(x, a)) ψ_{a}(x) & if 3ε/8 < d(x, a) ≤ ε/2. \end{cases}

We also set f_{j} to be 0 on X \ ⋃_{a∈A_{j}} B(x, ε/2). (Observe that this defines a function on X since the balls {B(a, ε/2)}_{a∈A_{j}} are disjoint.) It is straightforward to verify that f_{j} is Lipschitz with constant 4 D.

Now define F : X → Z^{N} by F = f_{1} ⊕ f_{2} ⊕ ⋯ ⊕ f_{N}. Then F is Lipschitz with constant 4 N D. Moreover, fix x, y ∈ X with d(x, y) ≤ ε/8. There exists 1 ≤ j ≤ N and a ∈ A_{j} such that d(x, a) ≤ ε/4. Hence d(y, a) ≤ d(x, y) + d(x, a) ≤ 3ε/8; so that x, y ∈ B(a, 3 ε /8) and

∥F (x) − F (y)∥ ≥ ∥f_{j}(x) − f_{j}(y)∥ = ∥ψ_{a}(x) − ψ_{a}(y)∥ ≥ d(x, y).

In what follows, a subset A of a metric space X is called ε-dense, if for every x ∈ X there is an a ∈ A such that d(x, a) ≤ ε.

Corollary 6.2. Let c ∈ (0, 1]. Let X, Y be metric spaces, Z an n-dimensional normed space, A ⊆ X an ε dense subset and φ : X → Y a 1 Lipschitz mapping such that for every a, b ∈ A, d(φ(a), φ(b)) ≥ c d(a, b). Assume that every ball of radius \frac{64ε}{c} in X embeds bi-Lipschitzly in Z with distortion at most D. Then there exists an integer N = N(n, D) and a K = K(n, ε, c, D) such that X embeds bi-Lipschitzly with distortion K into Y × Z^{N}.

Proof. Let F, N and Δ be as in Lemma 6.1 applied with ε replaced by 64 ε/c. Define g : X → Y ×Z^{N} by g(x) = (φ(x), F (x)). Then g has Lipschitz constant bounded by Δ + 1. Moreover, if x, y ∈ X are such that d(x, y) ≤ 8 ε/c then d(g(x), g(y)) ≥ ∥F (x) − F (y)∥ ≥ d(x, y). If, on the other hand, d(x, y) > 8 ε/c, then take x′, y′ ∈ A satisfying d(x, x′) ≤ ε and d(y, y′) ≤ ε. It follows that

d(g(x), g(y)) ≥ d(φ(x′), φ(y′)) − d(φ(x), φ(x′)) − d(φ(y), φ(y′))
≥ c d(x′, y′) − d(x, x′) − d(y, y′)
≥ c [d(x, y) − d(x, x′) − d(y, y′)] − d(x, x′) − d(y, y′)
≥ c d(x, y) − 2 ε (c + 1) ≥ \frac{c}{2} d(x, y).

The following lemma is known (it follows, for example, by specializing the results of [33]). However, since we could not locate a clean reference, we will include a short proof.

Lemma 6.3. Let X be a metric space, and let ϕ : A → T be a Lipschitz map from a subset A ⊂ X to a complete ℝ-tree T. Then ϕ may be extended to a map ϕ̃: X → T that agrees with ϕ on A and has the same Lipschitz constant as ϕ.

Proof. With no loss of generality, assume that the Lipschitz constant of ϕ is 1. We will use d_{X} and d_{T} to denote the metrics in X and T, respectively. Consider first the case where X contains only one point that is not in A. Say, X = A ∪ {x_{0}}. For any point a ∈ A, let B_{a} be the closed ball B(ϕ(a), d_{X}(x_{0}, a)) in T. Then any point in ⋂_{a∈A} B_{a} may be chosen as ϕ̃(x_{0}). Thus, we have to show that this intersection is nonempty. Consider a, a′ ∈ A. The triangle inequality in X shows that the sum of the radii of the two balls B_{a}, B_{a′} is at least as large as the distance between the centers. Thus, B_{a} ∩ B_{a′} contains a point on the unique simple path joining ϕ(a) and ϕ(a′) in T.

We claim that ℝ-trees satisfy the following Helly-type theorem. If F is a nonempty finite collection of convex subsets of T and every two elements F, F′ ∈ F intersect, F ∩ F′ ≠ ∅, then the whole collection intersects, ⋂_{F ∈F} F ≠ ∅. (Here, F convex means that the metric of T restricted to F is a path metric.) Indeed, suppose first that F = {F_{1}, F_{2}, F_{3}}. Let t_{1} ∈ F_{2} ∩ F_{3}, t_{2} ∈ F_{1} ∩ F_{3} and t_{3} ∈ F_{1} ∩ F_{2}. Since there are no cycles in T, it follows that the three paths, one joining t_{1} to t_{2}, one joining t_{2} to t_{3} and one joining t_{1} to t_{3} intersect. This intersection point will be in F_{1} ∩ F_{2} ∩ F_{3}. Now, suppose that F = {F_{1}, F_{2}, …, F_{n}}, where n > 3. By the previous case, we know that any two sets in the collection F′ := {F_{2} ∩ F_{1}, F_{3} ∩ F_{1}, …, F_{n} ∩ F_{1}} intersect. Induction then implies that the whole collection F′ intersects, which implies that F intersects.

Since balls in T are clearly convex, it follows that every finite subcollection of {B_{a}}_{a∈A} intersects. To prove that ⋂_{a∈A} B_{a} ≠ ∅, we must invoke completeness. Suppose now that B(t, r) and B(t′, r′) are two closed balls in T which intersect and none of these contains the other. Observe that B(t, r) ∩ B(t′, r′) is also a closed ball in T whose center is the unique point in T at distance (d_{T} (t, t′) + r − r′)/2 from t and at distance (d_{T} (t, t′) + r′ − r)/2 from t′, and whose radius is (r+r′−d_{T} (t, t′))/2 (here, a single point is considered as a ball of zero radius). Thus, the intersection I(A′) := ⋂_{a∈A′} B_{a}, where A′ ⊂ A is finite, is a nonempty ball. Let r_{∞} be the infimum radius of any such ball, and let a_{1}, a_{2}, … be a sequence in A such that the radius of the ball I({a_{1}, …, a_{n}}) converge to r_{∞}. Let c_{n} be the center of I({a_{1}, …, a_{n}}) and let r_{n} be the radius. If r_{∞} > 0, then the above formula for the radius of the intersection of two balls shows that c_{n} ∈ B_{a} for every a ∈ A and for every n such that r_{n} < 2 r_{∞}. Thus, clearly, ⋂_{a∈A} B_{a} ≠ ∅ in this case. In the case r_{∞} = 0, we have r_{n} ↘ 0, and it follows that c_{n} is a Cauchy sequence. Invoking completeness, we conclude that the limit c_{∞} := lim_{n} c_{n} exists. It follows that c_{∞} ∈ B_{a} for every a ∈ A, because I({a, a_{1}, …, a_{n}}) ≠ ∅ for every n. This completes the proof in the case X = A ∪ {x_{0}}. The general case follows by transfinite induction.

Theorem 6.4. Fix δ > 0, and assume that X is a δ-hyperbolic metric space whose metric is a path metric. Assume that there exists D, ε > 0 and n ∈ ℕ such that every ball of radius ε in X embeds in ℝ^{n} with distortion at most D. Then there exists an integer N and a K > 0 such that X embeds bi-Lipschitzly into a product of N ℝ-trees with distortion at most K.

The trees in the statement of the theorem are infinite degree simplicial trees whose edge lengths may be taken as 1. Though we will not need this, one can actually prove this with bounded degree trees [5] of edge length 1.

Proof. Since balls of radius ε embed in ℝ^{n} with distortion at most D, there is an upper bound (depending only on n and D) for the cardinality of any ε/2-separated set in X whose diameter is less than ε. In the terminology of [7], this means that X has bounded growth in some scale. By a theorem of Bonk and Schramm [7], there exists an integer m such that X is quasi-isometric to a subset of the m dimensional hyperbolic space ℍ^{m}. This means that there are constants a, a′, b > 0 and a mapping f : X → ℍ^{m} such that for all x, y ∈ X,

a d(x, y) − b ≤ d(f(x), f(y)) ≤ a′ d(x, y) + b.

(Actually, one may even take a = a′.) By a theorem of Buyalo and Schroeder [11], there is an ℝ-tree T such that ℍ^{m} is quasi-isometric to a subset of T^{m}. It follows that there is some R > 0, an R-net A of X and a bi-Lipschitz embedding g : A → T^{m}. Since the completion of an ℝ-tree is an ℝ-tree, we may as well assume that T is complete. Lemma 6.3 implies then that there is a Lipschitz extension φ : X → T^{m} of g. By scaling the distances in T we may also assume that φ is 1 Lipschitz and for every x, y ∈ A, d(φ(x), φ(y)) ≥ c d(x, y) for some constant c > 0.

Let A′ be an ε/8 net in X. Set Ψ(r) := sup_{a∈A′} |A′ ∩ B(a, r)|. We claim that Ψ(r) < ∞ for every r > 0. This holds true for r = ε, because balls of radius ε in X embed in ℝ^{n} with distortion at most D. Now let a_{1} ∈ A′, and let x ∈ B(a_{1}, r). Since X has a path metric, there is a point x′ ∈ X satisfying d(x′, a_{1}) = d(x′, x) = d(a_{1}, x)/2 ≤ r/2. Let a′ be a point in A′ satisfying d(a′, x′) < ε/8. Then a′ ∈ B(a_{1}, r/2 + ε/8) and x ∈ B(a′, r/2 + ε/8). Thus,

B(a_{1}, r) ⊆ ⋃_{a′∈A′∩B(a_{1},r/2+ε/8)} B(a′, r/2 + ε/8) .

Consequently, Ψ(r) ≤ Ψ(r/2 + ε/8)^{2}, which now implies that Ψ(r) < ∞ for every r.

We now show that for every r > 0 there is an n′ = n′(r) and a D′ = D′(r), both finite, such that every ball in X of radius r embeds in ℝ^{n′} with distortion at most D′. Indeed, let x ∈ X. Set A′_{x} = A′_{x}(r) := A′ ∩ B(x, r). Clearly, |A′_{x}| ≤ Ψ(r + ε/8). For every a ∈ A′ let ψ_{a} : B(a, ε) → ℝ^{n} be a bi-Lipschitz embedding with distortion at most D satisfying ψ_{a}(a) = 0, and let

ϕ_{a}(x) := \begin{cases}ψ_{a}(x) & if d(a, x) < ε/2, \\ 2 (1 − ε^{−1} d(a, x)) ψ_{a}(x) & if ε/2 ≤ d(a, x) ≤ ε, \\ 0 & otherwise. \end{cases}

Now the required bi-Lipschitz embedding from B(x, r) into ℝ^{n′} is given by x ↦ (ϕ_{a}(x))_{a∈A′_{x}} (with a padding of zeros to make n′ independent from x). It is immediate that this maps satisfies the requirements. Now an application of Corollary 6.2 completes the proof of the theorem (since the real line ℝ itself is an ℝ-tree).

The following corollary contains Theorem 1.7:

Corollary 6.5. Let X be an n dimensional complete simply connected Riemannian manifold with pinched negative sectional curvature (i.e., its sectional curvature takes values in the compact interval [−R, −r] ⊂ (−∞, 0)). Then there is an integer N = N(n, r, R) and D = D(n, r, R) > 0 such that X embeds bi-Lipschitzly into a product of N trees with distortion D. In particular, by Theorem 1.4, X has Markov type 2 and M_{2}(X) can be bounded by a function of n, r, R.

Proof. It is a standard fact [8] that X is δ hyperbolic (with δ proportional to 1/r). The fact that there exists ε > 0 such that all the balls of of radius ε in X embed bi-Lipschitzly in ℝ^{n} follows from Rauch’s comparison theorem (see [12] and Chapter 8_{+} in [24]). Thus the required result follows from Theorem 6.4.

G_{2} G_{3} G_{1} G_{0}

Figure 1: The Laakso graphs.

7 The Laakso graphs, doubling spaces and weak Markov type

Recall that a metric space X is said to be doubling with constant λ if every ball in X can be covered by λ balls of half the radius. Assouad’s theorem [1] states that if (X, d) is doubling with constant λ then for every ε > 0, (X, d^{1−ε}) embeds in Hilbert space with distortion C(λ, ε) < ∞. Thus X has Markov type 2 − ε with constant depending only on λ and ε. Similarly, it is shown in [42] that if G is a planar graph equipped with the graph metric d_{G}, then for every ε ∈ (0, 1), (G, d_{G}^{1−ε}) embeds in Hilbert space with distortion O(1/\sqrt{ε}) (and the dependence on ε is optimal). Thus G has Markov type 2 − ε with constant O(1/\sqrt{ε}). Is it true that a metric space with doubling constant λ has Markov type 2 with constant depending only on λ? Similarly, is it true that planar graphs have Markov type 2 with a universally bounded constant (this would be a generalization of our theorem on trees)? More generally, is it true that a Riemannian surface of genus g has Markov type 2 with constant depending only on g? The above embedding results are all optimal, so a proof of the Markov type 2 property for such spaces cannot go through embeddings in Hilbert space. The standard example showing that in both embedding results we must pass to a power of the metric is the family of graphs known as the Laakso graphs [37, 38], which are planar graphs whose graph metric is uniformly doubling, yet they do not uniformly embed into Hilbert space. These graphs G_{k} are defined recursively as in Figure 1.

Proposition 7.1. The Laakso graphs are uniformly of Markov type 2; that is sup_{k} M_{2}(G_{k}) < ∞.

This proposition may be viewed as some very limited indication that doubling spaces and planar graphs have Markov type 2.

Proof. Fix k ∈ ℕ. Let r be the leftmost point of G_{k}, and for an arbitrary vertex v in G_{k} set |v| := d(v, r). We claim that if v_{0}, v_{1}, …, v_{t} is a path in G_{k}, then there is some j ∈ {0, 1, …, t} such that

d(v_{0}, v_{t}) ≤ ||v_{0}| − |v_{j}|| + ||v_{j}| − |v_{t}||.  (16)

Indeed, let r′ be the rightmost endpoint of G_{k}. Note that for every vertex v in G_{k} we have d(v, r′) = |r′| − |v|. If v_{0} and v_{n} are on a geodesic path from r to r′, then d(v_{0}, v_{t}) = ||v_{0}| − |v_{t}||, and hence we may take j = 0. We now assume that there is no geodesic from r to r′ containing {v_{0}, v_{t}}. Let β be a geodesic path from v_{0} to r, and let γ be a geodesic path from v_{t} to r. Let u be the vertex in β ∩ γ at maximal distance from r. Similarly, we define u′ in the same way with r′ replacing r. It is easy to verify that {u, u′} separates v_{0} from v_{t} and separates {v_{0}, v_{t}} from {r, r′}. Consequently, there is some j ∈ {0, 1, …, t} such that v_{j} ∈ {u, u′} and that j satisfies (16).

Now suppose that Z_{0}, Z_{1}, …, Z_{t} are steps of a reversible stationary Markov chain on {1, …, n} and g is a mapping from {0, 1, …, n} to the vertices of G_{k}. Set W_{j} := g(Z_{j}). For each i = 1, 2, …, t, consider a path in G_{k} from W_{i−1} to W_{i} whose length is d(W_{i−1}, W_{i}). Putting these paths together gives a path (v_{0}, v_{1}, …, v_{n}) passing through the points W_{0}, …, W_{t} whose length n is ∑_{i=1}^{t} d(W_{i}, W_{i−1}). Set j_{i} := ∑_{s=1}^{i} d(W_{s}, W_{s−1}). Then v_{j_{i}} = W_{i}. Let j satisfy (16) and let i_{0} ∈ {1, …, t} be such that j_{i_{0}−1} ≤ j ≤ j_{i_{0}}. Then we have

d(W_{0}, W_{t}) ≤ ||W_{0}| − |v_{j}|| + ||v_{j}| − |W_{t}||
≤ ||W_{0}| − |W_{i_{0}−1}|| + d(W_{i_{0}−1}, W_{i_{0}}) + ||W_{i_{0}}| − |W_{t}||
≤ 2 ||W_{0}| − |W_{i_{0}−1}|| + d(W_{i_{0}−1}, W_{i_{0}}) + ||W_{0}| − |W_{t}||.

Thus

d(W_{0}, W_{t})^{2} ≤ 3(2 ||W_{0}| − |W_{i_{0}−1}||)^{2} + 3 d(W_{i_{0}−1}, W_{i_{0}})^{2} + 3 ||W_{0}| − |W_{t}||^{2}
≤ 15 max_{0≤i≤t}{(|W_{0}| − |W_{i}|)^{2}} + 3 ∑_{i=1}^{t} d(W_{i−1}, W_{i})^{2} .

Consequently, the proof is completed by two applications of Lemma 5.1, one with f(Z) = |g(Z)| and the other with f(Z) = −|g(Z)|.

It turns out that in many situations a similar argument proves a weak version of Markov type 2.

Definition 7.2. A metric space X has weak Markov type 2 if there is a finite constant C such that for every reversible stationary Markov chain Z on {1, …, n} and every map f : {1, …, n} → X, we have

∀t ∈ ℕ, ζ > 0 Pr(d(f(Z_{0}), f(Z_{t}))^{2} ≥ t ζ) ≤ C^{2} ζ^{−1} 𝔼(d(f(Z_{0}), f(Z_{1}))^{2}) .

The least C satisfying this inequality will be called the weak Markov type 2 constant of X and will be denoted M_{2}^{w}(X).

Note that Chebyshev’s inequality gives M_{2}(X) ≥ M_{2}^{w}(X).

Theorem 7.3. Let X be a metric space with doubling constant λ < ∞. Then X has weak Markov type 2, and M_{2}^{w}(X) is bounded by a finite function of λ.

Proof. Let R > 0 and let A be an R-net in X. Set E = {(a, a′) ∈ A × A : d(a, a′) ≤ 16 R}. Then G := (A, E) is a graph. Since every ball of radius 16 R in X can be covered by λ^{5} balls of radius R/2, it follows that the maximal degree in G is at most λ^{5}. Thus, the chromatic number of G is at most λ^{5} + 1. Consequently, there is a partition A = ⋃_{j=1}^{N} A_{j} of A into (16 R)-separated subsets with N ≤ λ^{5} + 1. Define f_{j}(x) := d(x, A_{j}), j = 1, 2, …, N. Then f_{j}(x) − f_{j}(y) ≤ d(x, y) holds for x, y ∈ X.

Now suppose that x, y ∈ X satisfy d(x, y) ∈ [3R, 4R]. Let a ∈ A be such that d(a, x) ≤ R and let j ∈ {1, …, N} be the index such that a ∈ A_{j}. Then f_{j}(x) ≤ d(a, x) ≤ R. Note that d(a, y) ≤ d(a, x) + d(x, y) ≤ 5 R, and since A_{j} is (16 R)-separated, it follows that f_{j}(y) = d(a, y) ≥ d(y, x) − d(a, x) ≥ 2 R.

Let (Z_{t}) be a reversible stationary Markov chain on {1, 2, …, n} and let f : {1, 2, …, n} → X. Set W_{i} := f(Z_{i}). Fix t ∈ ℕ. Let A be the event that d(W_{0}, W_{t}) ≥ 4 R, let B_{i} be the event that d(W_{i−1}, W_{i}) ≥ R, let C_{i} be the event d(W_{0}, W_{i}) ∈ [3R, 4R], and let C_{i}^{j} be the event |f_{j}(W_{0}) − f_{j}(W_{i})| ≥ 2 R. Clearly,

A ⊆ (⋃_{i=1}^{t} B_{i}) ⋃ (⋃_{i=1}^{t} C_{i}) .

The previous paragraph shows that

C_{i} ⊆ ⋃_{j=1}^{N} C_{i}^{j} .

Consequently,

Pr(A) ≤ ∑_{i=1}^{t} Pr(B_{i}) + ∑_{j=1}^{N} Pr ( max_{1≤i≤t} |f_{j}(W_{0}) − f_{j}(W_{i})| ≥ 2 R) .

The first of these sums is bounded by t 𝔼(d(W_{0}, W_{1})^{2}) R^{−2}, while Lemma 5.1 shows that the second sum is bounded by 50 N t 𝔼(d(W_{0}, W_{1})^{2}) R^{−2}. The theorem follows by choosing R to satisfy 16 R^{2} = t ζ.

Let (X, d_{X}), (Y, d_{Y}) be metric spaces. We shall say that (X, d_{X}) embeds weakly into (Y, d_{Y}) with distortion K if for every Δ > 0 there is a 1 Lipschitz mapping g_{Δ} : X → Y such that if x, y ∈ X satisfy d_{X}(x, y) ≥ Δ then d_{Y} (g_{Δ}(x), g_{Δ}(y)) ≥ Δ/K. Observe that in this case M_{2}^{w}(X) ≤ KM_{2}^{w}(Y). Indeed fix a reversible stationary Markov chain Z on {1, …, n} and a map f : {1, …, n} → X. For every time t ∈ ℕ and every ζ > 0,

Pr(d_{X}(f(Z_{0}), f(Z_{t}))^{2} ≥ tζ) ≤ Pr (d_{Y} (g\sqrt{tζ}(f(Z_{0})), g\sqrt{tζ}(f(Z_{t})))^{2} ≥ \frac{tζ}{K^{2}} )
≤ M_{2}^{w}(Y)^{2}K^{2}ζ^{−1} 𝔼 (d_{Y} (g\sqrt{tζ}(f(Z_{0})), g\sqrt{tζ}(f(Z_{t})))^{2})
≤ M_{2}^{w}(Y)^{2}K^{2}ζ^{−1} 𝔼 (d_{X}(f(Z_{0}), f(Z_{t}))^{2}) .

It follows from the results of [42, 35] that if X is doubling with constant λ then X embeds weakly into Hilbert space with distortion O(log λ). This yields an alternative proof of Theorem 7.3, with the concrete estimate M_{2}^{w}(X) = O(log λ). Moreover, the results of [42, 35] (specifically, see the proof of Lemma 5.2 in [42]) imply that any planar graph embeds weakly into Hilbert space with O(1) distortion. More generally, in combination with Corollary 3.15 in [41], any Riemannian surface S of genus g embeds weakly into Hilbert space with distortion O(g + 1). Thus M_{2}^{w}(S) = O(g + 1).

8 Discussion and open problems

1. In [59] (see also a related previous result in [9]) it is shown that for every p > 1, if a Banach space X has Rademacher type p then it also has Enflo type q for every q < p. No such result is known for Markov type. In [56] it is shown that if X is a UMD Banach space (see [10] for details on UMD spaces) of Rademacher type p, then X also has Enflo type p. It would be desirable to obtain a result stating that for a certain class of Banach spaces, the notions of Rademacher type p and Markov type p coincide (or almost coincide). The most daring conjecture would be that for every Banach space, Rademacher type p implies Enflo type p, or even Markov type p. This amounts to proving that for Banach spaces of type greater than 1 (also known as K-convex space. See [58] for the geometric and analytic ramifications of this assumption), the Rademacher type and Enflo type (or Markov type) coincide.

One simple example of a class of spaces for which we can prove that there is a strong connection between Rademacher type and Markov is Banach lattices. A Banach lattice is a Banach space (X, ∥ · ∥) which is partially ordered and satisfies the following axioms. For every x, y, z ∈ X, if x ≤ y then x + z ≤ y + z, and for every scalar α ∈ [0, ∞), x ≥ 0 implies that αx ≥ 0. It is also required that for all x, y ∈ X there exists a least upper bound x ∨ y and a greatest lower bound x ∧ y. For x ∈ X denote |x| = x ∨ (−x). The final requirement is that the partial ordering is compatible with the norm in the sense that if |x| ≤ |y| then ∥x∥ ≤ ∥y∥. Examples of Banach lattices are the classical function and sequence spaces, with the point-wise partial order. We refer to [44] for an account of the beautiful theory of Banach lattices.

A combination of a theorem of Figiel [21] and a theorem of Maurey [50] (see Theorem 1.f.1. and Proposition 1.f.17. in [44]) implies that a Banach lattice X of type 2 can be renormed to have a modulus of smoothness of power type 2. Thus by Theorem 2.3 X has Markov type 2.

2. Under what conditions on a metric space does Enflo type p imply Markov type p?

3. Is it true that if a metric space has Markov type p then it also has Markov type q for every q < p? For normed spaces this is indeed the case, by a straightforward application of Kahane’s inequality [32].

4. We conjecture that the factor of 24 in Theorem 2.4 is redundant. In particular it seems likely that for 2 ≤ p < ∞ and 1 < q ≤ 2, e(L_{p}, L_{q}) ≤ \sqrt{(p − 1)/(q − 1)}. If true, this would be a generalization of Kirszbraun’s classical extension theorem [34] (see also [65, 6]).

5. Since L_{1} has cotype 2 but isn’t uniformly convex, there is no known non-linear analog of Maurey’s extension theorem for L_{1}-valued mappings. In particular, it isn’t known whether e(L_{2}, L_{1}) is finite or infinite.

6. What is the best Markov type 2 constant for trees? More precisely, define M_{2}(tree) to be sup M_{2}(T) over all trees T. (It is clear that this sup is a max.) One can show using the methods of the present paper that M_{2}(tree) ≤ 8. The example in Subsection 5.1 shows that M_{2}(tree) ≥ \sqrt{3}.

7. As discussed in Section 7, we believe that planar graphs and doubling spaces have Markov type 2. Also, it seems likely that CAT(0) spaces have Markov type 2 (see [8] for a discussion of CAT(0) spaces).

8. Say that a metric space X has maximal Markov type p, if there exists a constant K such that for every finite stationary reversible Markov chain {Z_{t}}_{t=0}^{∞} on {1, …, n} and every mapping f : {1, …, n} → X, we have

𝔼 max_{1≤s≤t} d(f(Z_{s}), f(Z_{0}))^{p} ≤ K^{p}t 𝔼 d(f(Z_{1}), f(Z_{0}))^{p}.

for all t ∈ ℕ. In all the cases in which we proved that a metric space X has Markov type 2, the argument actually shows that it has maximal Markov type 2. This was explicit in the proofs for trees and hyperbolic spaces. To see this in the setting of Banach spaces with modulus of smoothness of power type 2, it suffices to note that Doob’s L_{2} maximal inequality (11) is also valid for a martingale {M_{s}}_{s≥0} in a Banach space, since by Jensen’s inequality, {∥M_{s}∥}_{s≥0} is a submartingale for the same filtration. We do not know whether in general, Markov type p implies maximal Markov type p.

Acknowledgement. We are grateful to Russ Lyons for helpful discussions at an early stage of this work, and to Terry Lyons for sending us his paper [45] with T. S. Zhang.

References

[1] P. Assouad. Plongements lipschitziens dans R^{n}. Bull. Soc. Math. France 111 429–448 (1983).

[2] K. Ball. Markov Chains, Riesz Transforms and Lipschitz Maps. Geom. Funct. Anal. 2, 137–172 (1992).

[3] K. Ball, E. A. Carlen and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. math. 115, 463–482 (1994).

[4] Y. Bartal, N. Linial, M. Mendel and A. Naor. On metric Ramsey-type phenomena. Ann. Math., to appear.

[5] I. Benjamini and O. Schramm. In preparation.

[6] Y. Benyamini and J. Lindenstrauss. Geometric Nonlinear Functional Analysis, volume 1. Amer. Math. Soc. Coll. Publ. 48 (2000).

[7] M. Bonk and O. Schramm. Embeddings of Gromov hyperbolic spaces. Geom. Funct. Anal. 10, 266–306 (2000).

[8] M. R. Bridson and A. Haefliger. Metric spaces of non-positive curvature. Springer-Verlag, Berlin (1999).

[9] J. Bourgain, V. Milman and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc. 294, no. 1, 295–317 (1986).

[10] D. L. Burkholder. Martingales and Singular integrals in Banach spaces. Handbook of the Geometry of Banach Spaces, volume 1, W. B. Johnson and J. Lindenstrauss eds., Elsevier, Amsterdam, 233–269 (2001).

[11] S. Buyalo and V. Schroeder. Embedding of hyperbolic spaces in the product of trees. Preprint (2004), available at http://arxiv.org/abs/math.GT/0311524.

[12] J. Cheeger and D. Ebin. Comparison Theorems in Riemannian Geometry. North Holland, New York (1975).

[13] I. M. Chiswell. Length functions and free products of groups Proc. London Math. Soc. 42, 42–58 (1981).

[14] J. Diestel, H. Jarchow and A. Tonge. Absolutely Summing Operators. Cambridge University Press (1995).

[15] E. Dubinsky, A. Pełczyńsky and H.P. Rosenthal. On Banach spaces X for which Π_{2}(L_{∞}, X) = B(L_{∞}, X). Sudia Math. 44, 617–648 (1972).

[16] R. Durrett. Probability: Theory and Examples, second edition. Duxbury Press, Belmont CA, (1996).

[17] P. Enflo. Topological groups in which multiplication on one side is differentiable or linear. Math. Scand. 24, 195–207 (1970).

[18] P. Enflo. Uniform structures and square roots in topological groups I. Israel J. Math. 8 230–252 (1970).

[19] P. Enflo. Uniform structures and square roots in topological groups II. Israel J. Math. 8 253– 272 (1970).

[20] P. Enflo. On infinite-dimensional topological groups. Séminaire sur la Géométrie des Espaces de Banach 1977-1978, Exp. no. 10–11, École Polytech., Palaiseau (1978).

[21] T. Figiel. On the moduli of convexity and smoothness. Studia Math. 56, 121–155 (1976).

[22] T. Figiel and G. Pisier. Séries aléatoires dans les espaces uniformément convexes ou uniformément lisses. C. R. Acad. Sci. 279, 611–614 (1974).

[23] E. Ghys and P. de la Harpe (eds.). Sur les groupes hyperboliques d’après Mikhael Gromov. Birkhäuser, Boston MA (1990).

[24] M. Gromov. Metric Structures for Riemannian and non-Riemannian Spaces. Birkhäuser, Boston (1999).

[25] O. Hanner. On the uniform convexity of L^{p} and l^{p}. Ark. Math. 3, 239–244 (1956).

[26] J. Heinonen. Lectures on Analysis in Metric Spaces. Universitext, Springer-Verlag, New York (2001).

[27] J. Hoffman-Jørgensen. Sums of independent Banach space valued random variables. Studia Math. 52, 159–186 (1974).

[28] R. C. James. Nonreflexive spaces of type 2. Israel J. Math. 30, 1–13 (1978).

[29] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 0f Contemp. Math., 189–206, Amer. Math. Soc., Providence RI (1984).

[30] W. B. Johnson, J. Lindenstrauss, D. Preiss and G. Schechtman. Lipschitz quotients from metric trees and from Banach spaces containing ℓ_{1}. J. Funct. Anal. 194, 332–346 (2002).

[31] P. Jordan and J. von Neumann. On inner products in linear metric spaces. Ann. of Math. (2) 36, no. 3, 719–723 (1935).

[32] J. P. Kahane. Series of Random Functions. Heath Math. Monographs, Lexington Mass., Heath and Co. (1968).

[33] N. V. Khue and N. T. Nhu. Lipschitz extensions and Lipschitz retractions in metric spaces. Colloquium Math. 45, 245–250 (1981).

[34] M. D. Kirszbraun. Über die zusammenziehenden und Lipschitzchen Transformationen. Fund. Math. 22, 77–108 (1934).

[35] R. Krauthgamer, J. R. Lee, M. Mendel and A. Naor. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal., to appear.

[36] S. Kwapien. Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients. Studia Math. 44, 583–595 (1972).

[37] T. J. Laakso. Ahlfors Q-regular spaces with arbitrary Q > 1 admitting weak Poincaré inequality. Geom. Funct. Anal. 10, no. 1, 111–123 (2000).

[38] U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87 (1–3), 285–307 (2001).

[39] R. Latała. Estimation of moments of sums of independent real random variables. Ann. Probab. 25, no. 3, 1502–1513 (1997).

[40] J. R. Lee and A. Naor. Embedding the diamond graph in L_{p} and dimension reduction in L_{1}. Geom. Funct. Anal. 14, no. 4, 745–747 (2004).

[41] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. math., to appear.

[42] J. R. Lee, M. Mendel and A. Naor. Metric structures in L_{1}: Dimension, snowflakes, and average distortion. European Journal of Combinatorics, to appear.

[43] J. Lindenstrauss. On the modulus of smoothness and divergent series in Banach spaces. Michigan Math. J., 10, 241–252 (1963).

[44] J. Lindenstrauss and L. Tzafriri. Classical Banach Spaces II. Springer-Verlag (1979).

[45] T. J. Lyons and T. S. Zhang. Decomposition of Dirichlet processes and its applications. Ann. Probab. 22, 494–524 (1994).

[46] A. Magen, N. Linial and A. Naor. Girth and Euclidean distortion. Geom. Funct. Anal. 12, no. 2, 380–394 (2002).

[47] M. B. Marcus and G. Pisier. Characterizations of almost surely continuous p-stable random Fourier series and strongly stationary processes. Acta Math. 152 (3–4), 245–301 (1984).

[48] B. Maurey. Espaces de cotype p, 0 < p ≤ 2. Séminaire Maurey-Schwartz 1972/73, École Polytech., Palaiseau (1973).

[49] B. Maurey. Théorèms de factorisation pour les operateurs linéaires a valuers dans un espace L^{p}. Asterisque, 11, Soc. Math. France (1974).

[50] B. Maurey. Type et cotype dans les espaces munis de structures locales inconditionnelles. Séminaire Maurey-Schwartz 1973/74, exposes 24–25, École Polytech., Palaiseau (1974).

[51] B. Maurey. Type, Cotype and K-Convexity. Handbook of the Geometry of Banach Spaces, volume 2, W. B. Johnson and J. Lindenstrauss eds., Elsevier, Amsterdam, 1299–1332. (2003).

[52] B. Maurey and G. Pisier. Séries de variables aléatoire vectorielles indépendants et propriétés géométriques des espaces de Banach. Studia Math. 58, 45–90 (1976).

[53] V. D. Milman and G. Schechtman. Asymptotic Theory of Finite Dimensional Normed Spaces. With an appendix by M. Gromov. Lect. Notes Math. 1200, Springer-Verlag, Berlin (1986).

[54] J. W. Morgan, P. B. Shalen. Valuations, trees, and degenerations of hyperbolic structures. Ann. of Math. (2) 120, 401–476 (1984).

[55] A. Naor. A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between L_{p} spaces. Mathematika 48, 253–271 (2001).

[56] A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math. 552, 213–236 (2002).

[57] G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math. 20, no. 3–4, 326–350 (1975).

[58] G. Pisier. Holomorphic semigroups and the geometry of Banach spaces. Ann. Math. (2), 115, no. 2, 375–392 (1982).

[59] G. Pisier. Probabilistic methods in the geometry of Banach spaces. Probability and Analysis (Varenna 1985), Springer Lect. Notes Math. 1206, 167–241 (1986).

[60] G. Pisier. The Volume of Convex Bodies and Banach Space Geometry. Cambridge University Press (1989).

[61] G. Pisier and Q. Xu. Random series in the real interpolation spaces between the spaces v_{p}. Geometrical Aspects of Functional Analysis, Springer Lect. Notes 1267, 185–209 (1986).

[62] J. W. Pitman. One dimensional Brownian motion and the three dimensional Bessel process. Adv. Appl. Prob. 7 511–526 (1975).

[63] I. G. Tsar’kov. Extension of Hilbert-valued Lipschitz mappings. Vestik Moskov. Univ. Ser. I Math. Mekh., 6, 9–16 (1999).

[64] J. Väisälä. Gromov Hyperbolic Spaces. Available at http://www.helsinki.fi/˜ jvaisala/grobok.pdf (2004).

[65] J. H. Wells and L. R. Williams. Embeddings and Extensions in Analysis. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84, Springer-Verlag, New York (1975).

[66] P. Wojtaszczyk. Banach Spaces for Analysts. Cambridge University Press, 1991.