**Random embeddings **

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

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

Let be a finite metric space, and let be a family of finite metric spaces. A *stochastic embedding from into * is a random pair where and is a non-contractive mapping, i.e. such that for all . The *distortion of * is defined by

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 1Every -point metric space admits a stochastic embedding into the family of tree metrics, with distortion .

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

Theorem 2For every , there is a -bounded random partition of which satisfies, for every and ,

**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 for all with . Let be partitions of , where is -bounded. We will assume that and is a partition of into singleton sets.

Now we inductively construct a tree metric as follows. The nodes of the tree will be of the form for and . The root is . In general, if the tree has a node of the form for , then will have children

The length of an edge of the form is . This specifies the entire tree . We also specify a map by . We leave the following claim to the reader.

where is the largest index with .

Note, in particular, that is non-contracting because if for some , then since is -bounded, implying that .

Now we are ready to prove Theorem 1.

*Proof:* Again, assume that for all . For , let be the -bounded random partition guaranteed by Theorem 2. Let be a partition into singletons, and let . Finally, let be the tree constructed above, and let be the corresponding (random) non-contractive mapping.

Now, fix and an integer such that . Using Claim 1 and (1), we have,

where in the penultimate line, we have evaluated three disjoint telescoping sums: For any numbers ,

Since every tree embeds isometrically into , this offers an alternate proof of Bourgain’s theorem when the target space is . Since we know that expander graphs require distortion into , this also shows that Theorem 1 is asymptotically tight.