Metric Markov Cotype Two of ℓ₁

1 Introduction

Metric Markov cotype asks whether the values of a map on a finite reversible Markov chain can be modified so that their one-step variation becomes small, while the cost of the modification is controlled by the original variation over a longer time interval. The modified values are not prescribed linear averages. This freedom is essential for the result proved here.

We work first with the real Banach space

Write \N=\{1,2,\ldots\} and [n]=\{1,\ldots,n\}. A stochastic matrix A=(a_{ij})_{i,j\in[n]} has nonnegative entries and each row sum equal to one. It is reversible with respect to a probability vector \pi=(\pi_i)_{i\in[n]} if \pi_i a_{ij}=\pi_j a_{ji} for all i,j. Reversibility implies stationarity, \pi A=\pi. Zero coordinates of \pi are allowed.

This is [4, Definition 1.2]. Our main result is the following.

Thus the square of the constant in (1.1) may be taken to be 3024, independently of the number of points, the number of coordinates, and the time parameter. No optimization of this numerical constant is intended.

History and significance

Ball introduced Markov type and cotype in his study of Lipschitz extension [1]. His Markov cotype condition for Banach spaces uses specified linear averages, and \ell_1 fails that stronger condition. Ball also proposed a metric definition. Mendel and Naor developed the Cesàro formulation above, proved its equivalence to Ball’s metric definition, and asked explicitly whether N_2(\ell_1) is finite [4, Question 1.15 and Section 7]. Theorem 1.2 answers that question affirmatively.

For 1<p\leq2, the uniformly convex theory gives N_2(\ell_p)\leq C/\sqrt{p-1} with a universal constant C [1]; see also [4, Section 1.1]. These bounds deteriorate as p decreases to one and do not settle the endpoint treated here.

There is a second distinction worth making. Using a construction of Kalton, Mendel and Naor found a closed linear subspace of \ell_1 that fails metric Markov cotype at every finite exponent [4, Theorem 1.14]. This does not rule out Theorem 1.2, because the points y_i in Definition 1.1 need not belong to a given subspace containing the original data. Our construction uses this freedom.

One important consequence concerns extension of Lipschitz maps. For a map f between metric spaces, \Lip(f) denotes the least L\geq0 such that d(f(x),f(y))\leq Ld(x,y) for all x,y in its domain. Ball’s extension problem asks whether a Lipschitz map from an arbitrary subset of Hilbert space into \ell_1 admits an extension with a universal multiplicative loss in its Lipschitz constant. Mendel and Naor explain that an affirmative answer to their metric Markov cotype question gives such an extension [4, Corollary 1.13 and the discussion after Question 1.15]. The extension problem is also discussed in [5, Section 1]. We record the consequence precisely in Section 6; the proof of Theorem 1.2 itself is elementary and independent of extension theorems.

The nonlinear construction

Finite subsets of \ell_1 admit exact representations by weighted cuts; see [3]. We retain not only their distances but also a contractive map back to the given ambient \ell_1. Nonlinear cut smoothing with the cubic \phi(r)=3r^2-2r^3 also appears in the work of Cheng, Wang, and Xiang on sharp metric cotype [2]; metric cotype and metric Markov cotype are different invariants.

The additional ingredient here is a martingale estimate for the cubic. For a finite family \mathcal B of cuts, the representation gives binary vectors z_i\in\{0,1\}^{\mathcal B} in a weighted Hilbert space H, with

It also gives a map T with T(z_i)=x_i that is contractive for the weighted \ell_1 norm on the cut coordinates. Let Q=[0,1]^{\mathcal B}, and let \Phi:Q\to Q apply \phi coordinatewise. Stop an A-walk (X_s) after an independent nonnegative geometric number S of steps with mean t. Writing \E_i for expectation when the walk starts at i, we choose

For the estimate, start the walk from its stationary law \pi and record stopping as a separate transition after the S walk steps. Attach h_j to the current index j while alive and z_j when the walk stops at j, keeping that value thereafter. These values form a martingale. Because \phi' vanishes at the binary values, a fourth-power Hilbert potential controls the total squared weighted-\ell_1 variation after applying \Phi. Centering at z_{X_0} makes the terminal potential equal to \|x_{X_S}-x_{X_0}\|_1^2. The stopping jump accounts for the approximation cost, and the expected t preceding jumps account for the one-step variation. Contractivity of T transfers these bounds to \ell_1.

We prove the cut representation in Section 2 and the martingale estimate in Section 3. The comparison in Section 4, valid in any metric space, converts the terminal geometric endpoint cost to the Cesàro average in (1.1). These ingredients are assembled in Section 5. The resulting points have a simple interpretation: each y_i is the expected coordinatewise median of three independent geometric-walk endpoints started at i. This interpretation is established after the main proof.

2 Finite cuts and reconstruction

We first replace finitely many vectors in \ell_1 by finitely many binary coordinates. The reconstruction map will allow us to choose new points in the full ambient space, rather than in the span of the data. This is the cut representation [3, Chapter 4], together with the ambient reconstruction given below.

3 A flat map and a quartic potential

By (2.2), squared \ell_1 distances between the original data are fourth powers of Hilbert distances between their binary encodings. We therefore seek a fourth-power potential that controls squared increments after the cubic map.

Fix a finite nonempty set \mathcal B and positive weights w_B, and use the two norms from Lemma 2.1. Write Q=[0,1]^{\mathcal B} and let \langle\cdot,\cdot\rangle_H be the weighted Hilbert inner product. Define

The map \Phi takes Q to itself and fixes its binary vertices. The key estimate controls its squared weighted-\ell_1 increment by a convexity remainder in H.

The linear term in (3.1) disappears on taking a conditional expectation along a Hilbert-valued martingale. It is important that the center may depend on the initial state.

4 Geometric and Cesàro endpoint costs

The stopped martingale will produce a geometric average of endpoint distances. The next estimate converts it to the finite average in Definition 1.1. This comparison is part of the resolvent approach in [4, Section 7, especially Lemma 7.1]. We give an elementary version with an explicit constant; only stationarity, not reversibility, is needed.

5 The stopped walk and the main theorem

We now construct the required points. Fix the data in Definition 1.1 with X=\ell_1. If all x_i coincide, choose y_i=x_i. Otherwise use Lemma 2.1 to obtain z_i,H,T, and use the map \Phi of Section 3.

Put p=1/(t+1), q=1-p, and define

This convex combination converges in the finite-dimensional space H and belongs to Q. Equivalently, h_i=\E_i z_{X_S}, where \E_i refers to an A-walk started at i and S is independent with \Prob(S=s)=pq^s. The first-step identity is

We take

In particular, each y_i belongs to \ell_1.

5.1 A martingale that realizes the two costs

Start a chain in an alive state with index distributed according to \pi. From an alive state of index i, it moves to the dead state of index i with probability p, and to the alive state of index j with probability qa_{ij}. Dead states are absorbing. Its filtration \calF_m records the initial state and the first m transitions only.

One realization uses an independent stationary A-walk (X_s)_{s\geq0} and successive independent survival trials, each successful with probability q. Let S be the number of successful trials before the first failure. Then \Prob(S=s)=pq^s and S is independent of the walk. There are S live index transitions followed by one death transition; the index at death is X_S.

Attach the value h_i to the alive state of index i and the value z_i to its dead state, and let M_m be the attached value at chain time m. Equation (5.2) shows that (M_m) is an H-valued martingale for the indicated filtration. It lies in Q and is eventually constant almost surely, with

The vector e=z_{X_0} is \calF_0-measurable and binary. Corollary 3.2 and (2.2) give

To compute the left side exactly, set

At time m, the event that the chain is alive has probability q^m and is independent of X_m. Stationarity gives \Prob(X_m=i)=\pi_i and \Prob(X_m=i,X_{m+1}=j)=\pi_i a_{ij}. Since \Phi(z_i)=z_i, the expected squared jump at time m is pq^m B+q^{m+1}E_A. Therefore

This identity explains why the killing probability was chosen to be 1/(t+1).

5.2 Completion of the proof

5.3 An expected-median interpretation

The construction has an intrinsic description in the original coordinates. Let

be the stochastic matrix of geometric endpoints. For fixed i, take independent indices J_1,J_2,J_3 with common law \Prob(J_a=j)=G_{ij}. For three real vectors, write \med(x,x',x'') for their coordinatewise median. This vector belongs to \ell_1, since its coordinatewise absolute value is at most |x|+|x'|+|x''|. Then

In each original coordinate, the median is at least a given threshold exactly when at least two of the three values are. The threshold decomposition in the proof of Lemma 2.1 therefore gives the pointwise identity

Each indicator has expectation 3h_i(B)^2(1-h_i(B))+h_i(B)^3=\phi(h_i(B)). Taking expectations in the finite sum proves (5.6).

6 Complex scalars and Lipschitz extension

For the extension consequence, recall that a metric space (Z,d_Z) has Markov type two with constant M>0 if

for every n,t\in\N, every stochastic matrix A reversible with respect to a probability vector \pi, and every u_1,\ldots,u_n\in Z. Hilbert spaces satisfy this inequality with M=1 [1]; see also [4, Definition 1.1 and the following discussion].