Minimax grid matching and empirical measures (Q810990)

Given two sets of points \(X:=\{x_ 1,...,x_ n\}\) and \(Y:=\{y_ 1,...,y_ n\}\), where \(x_ i\) and \(y_ i\in {\mathbb{R}}^ d\), let \[ L(X,Y):=\min_{\pi}\max_{1\leq i\leq n}e(x_{\pi (i)},y_ i), \] where e denotes Euclidean distance and the min is taken over all permutations \(\pi\) of the integers 1,...,n. Let \(S:=[0,1]^ d\), \(d\geq 2\), and G be a regularly spaced \(n^{-1/d}\times...\times n^{-1/d}\) array of n grid points on S \((n=k^ d\), \(k\in {\mathbb{N}}^+)\). Partition S into n congruent cubes of volume \(n^{-1}\) such that each cube is centered around a grid point. Let \(X:=\{X_ 1(\omega),...,X_ n(\omega)\}\) denote a random sample of i.i.d. \(X_ i\), \(1\leq i\leq n\), being uniformly distributed on S. The problem of finding the expected value of L(X,G) is called the minimax grid matching problem. The main theorem of the present paper shows that for \(d\geq 3\) there exist constants c and C depending only upon d such that \[ c\leq \liminf_{n\to \infty}(n/\log n)^{1/d} L(X,G)\leq \limsup_{n\to \infty}(n/\log n)^{1/d} L(X,G)\leq C\quad a.s. \] This result is used to determine the exact order of convergence for \(\rho (\lambda_ n,\lambda)\), where \(\rho (\lambda_ n,\lambda)\) denotes the Prokhorov distance between the n-th empirical measure \(\lambda_ n(\omega)\) pertaining to \(X_ 1(\omega),...,X_ n(\omega)\) and Lebesgue measure \(\lambda\), thus settling a long-open problem raised by R. M. Dudley in 1969.