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.
We will need the random partitioning theorem we proved last time:
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.
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.