Answers are grounded in this paper and cite their sources.
Throughout most of this paper, we will denote by (Ui)i<n an independent sequence of points uniformly distributed over the unit sq~are [0, 1]2.We will be concerned with the study of the "fluctuations" of the set {U" ... , Un} and by how far these points are to be spread evenly in [0, 1]2.Consider fixed points "", ... , ~ "spread evenly" in [0, 1 f.For example, if m is the largest integer with m 2 ::; n, one can take for "", ... , Vn the points (kim, lim), 0::; k < m, 0::; l < m, together with any subset of n -m 2 of the points (kim, f 1m), 0 < k, f ::; m, k = m or l = m.A matching of (Ui)i<n and (~)i<n is a permutation 7C of {I, ... ,n} (that matches the point U~ with the pOInt ~(i))' We will study how "closely" the random points V, ' ... , Un can be matched to the fixed points "", ... , ~. (The investigation of different measures of "closeness" will be central to this work.)It was Ajtai, Komlos, and Tusnady who discovered the depth of the subject.Theorem 1.1 (The Ajtai-Komlos-Tusnady matching theorem [AKT]).With high probability, there exists a matching 7C such that L:i::;n II U i -V;rr(i) II ::; Ky'n logn.In this statement, lIu -vII is the euclidean distance of u and v and K denotes a universal constant.(Throughout the paper, unless mentioned otherwise, K will denote a universal constant, not necessarily the same at each occurrence.)With high probability means with probability close to one.(Soon we will indicate a general principle that allows one to compute precisely how close to one it is possible to get.) Theorem 1.1 is only half of the result of Ajtai, Komlos, and Tusnady.They prove that with high probability, for each matching 7C we have L:i::;n II U i -~(i) II ~ K-' y' n log n.The problem of lower bounds will not be adressed in the present paper.One reason is that much of the paper is devoted to extensions of Theorem 1.1, where the same lower bounds
No takes yet. Share an insight, caveat, or question.
M. Talagrand (1994) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: