# Random tree embeddings

Random embeddings

When it is impossible to achieve a low-distortion embedding of some space ${X}$ into another space ${Y}$, we can consider more lenient kinds of mappings which are still suitable for many applications. For example, consider the unweighted ${n}$-cycle ${C_n}$. It is known that any embedding of ${C_n}$ into a tree metric incurs distortion ${\Omega(n)}$. On the other hand, if we delete a uniformly random edge of ${C_n}$, this leaves us with a random tree (actually a path) ${C'_n}$ such that for any ${x,y \in C_n}$, we have

$\displaystyle d_{C'_n}(x,y) \geq d_{C_n}(x,y) \geq \frac12\, \mathop{\mathbb E}[d_{C'_n}(x,y)].$

In other words, in expectation the distortion is only 2.

Let ${(X,d)}$ be a finite metric space, and let ${\mathcal F}$ be a family of finite metric spaces. A stochastic embedding from ${X}$ into ${\mathcal F}$ is a random pair ${(F,Y)}$ where ${Y \in \mathcal F}$ and ${F : X \rightarrow Y}$ is a non-contractive mapping, i.e. such that ${d_Y(F(x),F(y)) \geq d_X(x,y)}$ for all ${x,y \in X}$. The distortion of ${F}$ is defined by

$\displaystyle \max_{x,y \in X} \frac{\mathop{\mathbb E} \left[d_Y(F(x),F(y))\right]}{d_X(x,y)}\,.$

We will now argue that every finite metric space admits a surprisingly good stochastic embedding into tree metrics. The next result is from Fakcharoenphol, Rao, and Talwar, following work by Bartal and Alon, Karp, Peleg, and West.

Theorem 1 Every ${n}$-point metric space ${(X,d)}$ admits a stochastic embedding into the family of tree metrics, with distortion ${O(\log n)}$.

We will need the random partitioning theorem we proved last time:

Theorem 2 For every ${\Delta > 0}$, there is a ${\Delta}$-bounded random partition ${\mathcal P}$ of ${X}$ which satisfies, for every ${x \in X}$ and ${0 < r \leq \Delta/8}$,

$\displaystyle \mathop{\mathbb P}\left(B(x,r) \nsubseteq \mathcal P(x)\right) \leq \frac{8r}{\Delta} H\left(|B(x,\Delta/8)|,|B(x,\Delta)|\right). \ \ \ \ \ (1)$

From partitions to trees. Before proving the theorem, we discuss a general way of constructing a tree metric from a sequence of partitions. Assume (by perhaps scaling the metric first) that ${1 < d(x,y) \leq 2^M}$ for all ${x,y \in X}$ with ${x \neq y}$. Let ${P_0, P_1, \ldots, P_M}$ be partitions of ${X}$, where ${P_k}$ is ${2^k}$-bounded. We will assume that ${P_M = \{X\}}$ and ${P_0}$ is a partition of ${X}$ into singleton sets.

Now we inductively construct a tree metric ${T = T(P_0, P_1, \ldots, P_M)}$ as follows. The nodes of the tree will be of the form ${(k,S)}$ for ${k \in \{0,1,\ldots,M\}}$ and ${S \subseteq X}$. The root is ${(M,X)}$. In general, if the tree has a node of the form ${(j,S)}$ for ${j > 0}$, then ${(j,S)}$ will have children

$\displaystyle \{ (j-1, S \cap T) : T \in P_{j-1} \textrm{ and } S \cap T \neq \emptyset\}.$

The length of an edge of the form ${\{(j,S), (j-1,S')\}}$ is ${2^{j}}$. This specifies the entire tree ${T}$. We also specify a map ${F : X \rightarrow T}$ by ${F(x) = (0,\{x\})}$. We leave the following claim to the reader.

Claim 1 For every ${x,y \in X}$,

$\displaystyle d_{T}(F(x),F(y)) = 2 \sum_{k=1}^{j+1} 2^k = 2^{j+3}-4.$

where ${j \in \{0,1,\ldots,M\}}$ is the largest index with ${P_j(x) \neq P_j(y)}$.

Note, in particular, that ${F : X \rightarrow T}$ is non-contracting because if ${2^j < d(x,y) \leq 2^{j+1}}$ for some ${j \geq 0}$, then ${P_j(x) \neq P_j(y)}$ since ${P_j}$ is ${2^{j}}$-bounded, implying that ${d_{T}(F(x),F(y)) \geq 2^{j+3}-4 \geq 2^{j+1}}$.

Now we are ready to prove Theorem 1.

Proof: Again, assume that ${1 < d(x,y) \leq 2^M}$ for all ${x,y \in X}$. For ${0 < k < M}$, let ${\mathcal P_k}$ be the ${2^k}$-bounded random partition guaranteed by Theorem 2. Let ${\mathcal P_0}$ be a partition into singletons, and let ${\mathcal P_M = \{X\}}$. Finally, let ${\mathcal T=\mathcal T(\mathcal P_0, \ldots, \mathcal P_M)}$ be the tree constructed above, and let ${F : X \rightarrow \mathcal T}$ be the corresponding (random) non-contractive mapping.

Now, fix ${x,y \in X}$ and an integer ${h}$ such that ${2^h < d(x,y) \leq 2^{h+1}}$. Using Claim 1 and (1), we have,

$\displaystyle \mathop{\mathbb E}\left[d_{\mathcal T}(F(x),F(y))\right] \leq \sum_{j=0}^M \mathop{\mathbb P}[\mathcal P_j(x) \neq \mathcal P_j(y)] \cdot 2^{j+3}$

$\displaystyle \leq O(d(x,y)) + \sum_{j=h+3}^M \frac{8\,d(x,y)}{2^j} 2^{j+3} H\left(|B(x, 2^{j-3})|,|B(x,2^{j})|\right)$

$\displaystyle \leq O(d(x,y)) + \sum_{j=h+3}^M \frac{8\,d(x,y)}{2^j} 2^{j+3} H\left(|B(x, 2^{j-3})|,|B(x,2^{j})|\right)$

$\displaystyle \leq O(d(x,y)) + O(1) \,d(x,y) \sum_{j=h+3}^M H\left(|B(x, 2^{j-3})|,|B(x,2^{j})|\right)$

$\displaystyle \leq O(H(1,n))\,d(x,y)$

$\displaystyle \leq O(\log n)\,d(x,y),$

where in the penultimate line, we have evaluated three disjoint telescoping sums: For any numbers ${1 \leq a_1 \leq a_2 \leq \cdots \leq a_k}$,

$\displaystyle H(a_1,a_2)+H(a_2,a_3)+\cdots+H(a_{k-1},a_k)=H(a_1,a_k).$

$\Box$

Since every tree embeds isometrically into ${\ell_1}$, this offers an alternate proof of Bourgain’s theorem when the target space is ${\ell_1}$. Since we know that expander graphs require ${\Omega(\log n)}$ distortion into ${{\ell}_1}$, this also shows that Theorem 1 is asymptotically tight.