math.PR — Probability

On the Asymptotic $W_1$ Cost of Two-Dimensional Semi-Discrete Matching

Contributed by Heng Ma

Let $X_1,X_2,\ldots$ be independent uniform points in the unit square and let $\lambda$ denote Lebesgue probability measure. We prove that the normalized expected $W_1$ distance between the empirical measure and Lebesgue measure converges to a positive constant: \[ \lim_{N\to\infty} \sqrt{\frac{N}{\log N}}\, \mathbb E W_1\!\left(\frac1N\sum_{i=1}^N\delta_{X_i},\lambda\right) =c_\star. \] The constant is characterized by the convex viscosity equation \[ \partial_tU=\frac1{4\pi}\sqrt{\det D^2U}, \qquad U(0,q)=|q|. \] Its solution $U$ is unique under certain growth and regularity conditions, and the limiting constant $c_\star=U(1,0)/\sqrt2$.