2021/04/15 by William Q. Erickson, Erickson, William Q.
Computer Science · Mathematics · #05E10 (Secondary) #90C27 (Primary) #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Artificial intelligence #Bayesian Methods and Mixture Models #Combinatorics #Combinatorics (math.CO) #Computer science #Discrete mathematics #Earth mover's distance #FOS: Mathematics #Geometry #Histogram #Image (mathematics) #Lattice (music) #Mathematics #Physics #Plane (geometry)
paper · pdf · doi:10.48550/arxiv.2104.07273
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2021/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We consider two natural statistics on pairs of histograms, in which the n bins have weights 0, …, n-1. The difference (D) between the weighted totals of the histograms is, in a sense, refined by the earth mover's distance (EMD), which measures the amount of work required to equalize the histograms. We were recently surprised, however, by how little EMD actually does refine D in certain real-world applications, which led to the main problem in this paper: what is the probability that EMD = |D|? We derive a formula for this probability, as well as the expected value of |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 D as distance on the Type-A root lattice.