Random Matching Between Distinct Distributions in Two Dimensions
Abstract
Given two independent n-point samples drawn from possibly distinct probability distributions on a compact 2-dimensional surface, we minimize the total squared distance over all perfect bipartite matchings. Under regularity assumptions, the expected matching cost minus n times the squared 2-Wasserstein distance between the sampling distributions grows logarithmically with n. We determine this difference up to an additive o(1) error, including the dependence of the logarithmic coefficient and constant term on geometry and sampling distributions, and establish the existence of a universal constant shared by these formulas. Our analysis expresses the expected matching cost in terms of the cost of transporting a heat-smoothed sample back to its original points. The reductions giving this relation hold in every dimension and for general costs under suitable assumptions, with consequences beyond the setting studied here. In two dimensions, the relation is exact up to an additive o(1) error, so determining the matching cost amounts to evaluating the smoothing cost with the same accuracy. We obtain this evaluation by subdividing the domain and exploiting cancellations between the sample and its own smoothing.
Related
- Fluctuations of the quadratic matching cost on the flat torus: dimensions five and higher
- Fluctuations of the quadratic matching cost on the flat torus: dimensions two, three and four
- Approximating Distributions on Vertex Degrees in Random Hypergraphs via Stein's Method
- Joint distributions of eigenvectors of symmetric random tensors
- Delocalization and Quantum Diffusion of Random Band Matrices in High Dimensions I: Self-energy Renormalization
BibTeX
@misc{xu2026random,
title = {{Random Matching Between Distinct Distributions in Two Dimensions}},
author = {Yunzong Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40509},
eprint = {2610.40509},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40509},
}
RIS
TY - UNPB
TI - Random Matching Between Distinct Distributions in Two Dimensions
AU - Yunzong Xu
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40509
UR - https://arxiv.org/abs/2610.40509
AB - Given two independent n-point samples drawn from possibly distinct probability distributions on a compact 2-dimensional surface, we minimize the total squared distance over all perfect bipartite matchings. Under regularity assumptions, the expected matching cost minus n times the squared 2-Wasserstein distance between the sampling distributions grows logarithmically with n. We determine this difference up to an additive o(1) error, including the dependence of the logarithmic coefficient and constant term on geometry and sampling distributions, and establish the existence of a universal constant shared by these formulas. Our analysis expresses the expected matching cost in terms of the cost of transporting a heat-smoothed sample back to its original points. The reductions giving this relation hold in every dimension and for general costs under suitable assumptions, with consequences beyond the setting studied here. In two dimensions, the relation is exact up to an additive o(1) error, so determining the matching cost amounts to evaluating the smoothing cost with the same accuracy. We obtain this evaluation by subdividing the domain and exploiting cancellations between the sample and its own smoothing.
ER -