Expected value and a Cayley-Menger type formula for the generalized earth mover's distance

Abstract

The earth mover's distance (EMD), also known as the 1-Wasserstein metric, measures the minimum amount of work required to transform one probability distribution into another. The EMD can be naturally generalized to measure the "distance" between any number (say $d$) of distributions. In previous work (2021), we found a recursive formula for the expected value of the generalized EMD, assuming the uniform distribution on the standard $n$-simplex. This recursion, however, was computationally expensive, requiring $\left(\genfrac{}{}{0ex}{}{d+n}{d}\right)$ many iterations. The main result of the present paper is a nonrecursive formula for this expected value, expressed as the integral of a certain polynomial of degree at most $dn$. As a secondary result, we resolve an unanswered problem by giving a formula for the generalized EMD in terms of pairwise EMDs; this can be viewed as an analogue of the Cayley-Menger determinant formula that gives the hypervolume of a simplex in terms of its edge lengths.

20 pages; the second half of this paper supersedes my preprint arXiv:2306.12030, and thus there is some overlap of exposition