Matching random samples in many dimensions. (English) Zbl 0761.60007

Talagrand, Michel

Ann. Appl. Probab. 2, No. 4, 846-856 (1992).

Summary: Consider any norm \(N\) on \(\mathbb{R}^ d\), \(d\geq 3\), and independent uniformly distributed points \(X_ 1,\dots,X_ n\), \(\ldots;Y_ 1,\dots,Y_ n,\dots\) in \([0,1]^ d\). Consider the random variable \(M_ n=\inf\sum_{i\leq n} N(X_ i-Y_{\sigma(i)})\), where the infimum is taken over all permutations \(\sigma\) of \(\{1,\dots,n\}\). We show that for some universal constant \(K\), we have \[ \limsup_{n\to\infty} M_ n n^{-1+1/d}\leq r_ N\left(1+K{\log d\over d}\right)\quad\text{a.s.}, \] where \(r_ N\) is the radius of the ball for \(N\) of volume 1.

MSC:

60C05	Combinatorial probability
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

matching random samples; optimal matching