Comparing weighted difference and earth mover's distance via Young diagrams

Abstract

We consider two natural statistics on pairs of histograms, in which the $n$ bins have weights $0,\dots ,n-1$. The difference ($\mathbf{D}$) between the weighted totals of the histograms is, in a sense, refined by the earth mover's distance ($\mathbf{EMD}$), which measures the amount of work required to equalize the histograms. We were recently surprised, however, by how little $\mathbf{EMD}$ actually does refine $\mathbf{D}$ in certain real-world applications, which led to the main problem in this paper: what is the probability that $\mathbf{EMD}=|\mathbf{D}|$? We derive a formula for this probability, as well as the expected value of $|\mathbf{D}|$, via the combinatorics of Young diagrams and plane partitions. We then generalize our results to an arbitrary number of histograms, where we realize this higher-dimensional $\mathbf{D}$ as distance on the Type-A root lattice.

arXiv comment35 pages, 3 figures, 2 tables