Minimax grid matching and empirical measures (Q810990)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimax grid matching and empirical measures |
scientific article |
Statements
Minimax grid matching and empirical measures (English)
0 references
1991
0 references
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.
0 references
empirical measures
0 references
minimax grid matching problem
0 references
Prokhorov distance
0 references