On the Asymptotic Cost of Two-Dimensional Semi-Discrete Matching
Version 1 / Sep 30, 2026 / CC BY 4.0
Abstract
Let be independent uniform points in the unit square and let
denote Lebesgue probability measure. We prove that the normalized
expected 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 is unique under certain growth and regularity conditions, and the limiting constant .
Tools used
- OpenAI
- ChatGPTVersion 5.6Pro
References
- Ambrosio, Luigi; Stra, Federico; Trevisan, Dario. A PDE Approach to a 2-Dimensional Matching Problem. Probability Theory and Related Fields, vol. 173, pp. 433–477. 2019. \urlhttps://doi.org/10.1007/s00440-018-0837-x
- Crandall, Michael G.; Ishii, Hitoshi; Lions, Pierre-Louis. User's Guide to Viscosity Solutions of Second Order Partial Differential Equations. Bulletin of the American Mathematical Society, vol. 27, pp. 1–67. 1992. \urlhttps://doi.org/10.1090/S0273-0979-1992-00266-5
- Diening, Lars; Rolfes, Johannes; Salgado, Abner J. Pointwise Gradient Estimate of the Ritz Projection. SIAM Journal on Numerical Analysis, vol. 62, pp. 1212–1225. 2024. \urlhttps://doi.org/10.1137/23M1571800
- Evans, Lawrence C.; Gangbo, Wilfrid. Differential Equations Methods for the Monge–Kantorovich Mass Transfer Problem. Memoirs of the American Mathematical Society, vol. 137, no. 653. 1999. \urlhttps://doi.org/10.1090/memo/0653
- Fang, Xiao. Wasserstein-2 Bounds in Normal Approximation under Local Dependence. Electronic Journal of Probability, vol. 24, no. 35, pp. 1–14. 2019. \urlhttps://doi.org/10.1214/19-EJP301
- Talagrand, Michel. The Ajtai–Komlos–Tusnady Matching Theorem for General Measures. Probability in Banach Spaces, 8, vol. 30, pp. 39–54. 1992. \urlhttps://doi.org/10.1007/978-1-4612-0367-4_2
- Wang, Feng-Yu; Yan, Lixin. Gradient Estimate on the Neumann Semigroup and Applications. 2010. \urlhttps://arxiv.org/abs/1009.1965