Some generalizations of the Euclidean two-sample matching problem (Q3139481)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 434648
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Some generalizations of the Euclidean two-sample matching problem |
scientific article; zbMATH DE number 434648 |
Statements
15 December 1994
0 references
probability metrics
0 references
two-sample Euclidean matching problem
0 references
transportation cost problem
0 references
0.9053836464881896
0 references
0.850497305393219
0 references
0.8272760510444641
0 references
0.8252149820327759
0 references
0.8244154453277588
0 references
Some generalizations of the Euclidean two-sample matching problem (English)
0 references
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].
0 references