Some generalizations of the Euclidean two-sample matching problem
This paper considers the two-sample Euclidean matching problem (or, the transportation cost problem). Here the i.i.d. random variables \(X_ 1,\dots, X_ n\), \(Y_ 1,\dots, Y_ n\), with some ``nice distribution \({\mathbf P}\) on the unit square or on the plane, become involved in the following functional of interest: \[ T_ p(n):= \inf_ \pi \biggl\{ (1/n) \sum_{n=1}^ n \| X_ i- Y_{\pi(i)} \|^ p \biggr\}^{1/p}, \] where \(\pi\) runs over all permutations of \(\{1,2, \dots, n\}\), and \(\|\cdot\|\) denotes the Euclidean norm. The main results of the paper are the following theorems. Theorem 1. (i) Let \(X_ i\) \(i\geq 1\), satisfy also \[ \sum_{j=1}^ \infty 2^ j \bigl[ \text{Pr} \{2^ j\leq \| X\|< 2^{j+1}\} \bigr]^{1/2} <\infty. \tag{*} \] Then there is a constant \({\mathbf C}\) such that, for all \(n\geq 1\), \[ {\mathbf E} \inf_ \pi \biggl\{ (1/n) \sum_{i=1}^ n \| X_ i- Y_{\pi(i)}\| \biggr\}\leq {\mathbf C}(\log n/n)^{1/2}. \] (ii) The condition (*) is sharp. Theorem 2. Let \({\mathbf P}\) be a probability measure on the unit square which has a density bounded below by a non-zero constant, say \({\mathbf m}\). If \({\mathbf P}\) has independent marginals, then there is a constant \({\mathbf K}\) such that for all \(\alpha\geq 3\) and \(n\geq 22\alpha^ 2\) there is a set \(A_ n:= A_ n(\alpha)\) with \({\mathbf P} (A_ n^ c) \leq n^{1-\alpha/2}\) such that \[ \biggl\{ {\mathbf E} \inf_ \pi n^{- 1} \sum_{i=1}^ n \exp \bigl[ \| X_ i- Y_{\pi(i)}\|/ \alpha{\mathbf K} (\log n/n)^{1/2} \bigr] \Biggr\} \text{\textbf{1}}_{A_ n} \leq 1. \] For the entire collection see [Zbl 0773.00018].
- On optimal matchings
- An integral representation of the variance of the number of correctly guessed pairs in the matching problem of a two-dimensional sample
- Euclidean semi-matchings of random samples
- Matching random samples in many dimensions
- A matching problem and subadditive Euclidean functionals
- The integrability of the square exponential transportation cost
- Scaling and non-standard matching theorems
- Some results on the optimal matching problem for the Jacobi model
- A simple Fourier analytic proof of the AKT optimal matching theorem
- On optimal matching of Gaussian samples
- Finer estimates on the 2-dimensional matching problem
- Euclidean random matching in 2D for non-constant densities
- An exposition of Talagrand's mini-course on matching theorems
- Correlation function for the grid-Poisson Euclidean matching on a line and on a circle
- Large and moderate deviations for matching problems and empirical discrepancies
- On optimal matching of Gaussian samples. III
- On optimal matching measures for matching problems related to the Euclidean distance.
- New estimates on the matching problem
- Matchings and the variance of Lipschitz functions
- Random matching in 2D with exponent 2 for Gaussian densities
- Convergence of empirical optimal transport in unbounded settings
- Minimax grid matching and empirical measures
This page was built for publication: Some generalizations of the Euclidean two-sample matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3139481)