Maxima in hypercubes
A point \(p\) in \(\mathbb R^d\) is said to dominate another point \(q\) if the difference \(p-q\) has only nonnegative coordinates. The nondominated points in a set of points are called maxima. The interest of studying dominance and maxima is multifold. First, dominance represents one of the most natural partial orders for multidimensional points, and has been widely used in many scientific disciplines [see \textit{W.-M. Chen, H.-K. Hwang} and \textit{T.-H. Tsai}, Discrete Math. Theor. Comput. Sci. 6, 107--122 (2003; Zbl 1036.68124)]. Second, the number of maxima is itself encountered in many applications like analysis of linear programming and of maxima-finding algorithms [see the paper mentioned above and \textit{M. E. Dyer} and \textit{J. Walker}, Asia-Pac. J. Oper. Res. 15, 159--168 (1998; Zbl 0917.90249)]. Finally, not much is known as far as probabilistic properties of the number of the maxima in dimensions higher than two are concerned. Asymptotic estimates for the mean are usually straightforward, but those for the variance are highly nontrivial even in the simplest case of hypercubes [see \textit{Z.-D. Bai, C.-C. Chao, H.-K. Hwang} and \textit{W.-Q. Liang}, Ann. Appl. Probab. 8, 886--895 (1998; Zbl 0941.60021)]. \textit{Y. Baryshnikov} [Probab. Theory Relat. Fields 117, 163--182 (2000; Zbl 0961.60017)] indicated that the number of maxima in hypercubes is asymptotically normally distributed but without complete proof [see also \textit{A. D. Barbour} and \textit{A. Xia}, Adv. Appl. Probab. 33, 727--750 (2001; Zbl 1005.60028)]. The aim of this paper is to i) derive an asymptotic expansion for the variance of the number of maxima in random samples independently and identically distributed in the hypercube \((0,1)^d\) and ii) derive a central limit theorem with convergence rate for the number of maxima. The main trick used in the paper is the log-transformation first suggested by Baryshnikov (loc. cit.). Switching to a Poisson sample size is introduced by Barbour and Xia (loc. cit.).
- Notes on the variance of the number of maxima in three dimensions
- Berry-{E}sseen bounds for the number of maxima in planar regions
- Explicit computation of the variance of the number of maxima in hypercubes
- Limit theorems for the number of maxima in random samples from planar regions
- The number of two-dimensional maxima
- Noncommutative algebra, multiple harmonic sums and applications in discrete probability
- Determination of maxima for arbitrary orders
- On the variance of the number of maxima in random vectors and its applications
- Maximality of the hypercube group
- Range-max queries on uncertain data
- Berry-{E}sseen bounds for the number of maxima in planar regions
- Diffusion approximations in the online increasing subsequence problem
- Gaussian approximation for sums of region-stabilizing scores
- Asymptotic properties of high-dimensional random forests
- On multisets, interpolated multiple zeta values and limit laws
- The Pareto record frontier
- How many maxima can there be?
- Consistency of random forests
- A random forest guided tour
- Mini-workshop: Random trees, information and algorithms. Abstracts from the mini-workshop held April 24--30, 2011
- scientific article; zbMATH DE number 4015797 (Why is no real title available?)
- On the Height of a Random Set of Points in a d-Dimensional Unit Cube
- From proximity to utility: a Voronoi partition of Pareto optima
- Explicit computation of the variance of the number of maxima in hypercubes
- Maxima-finding algorithms for multidimensional samples: A two-phase approach
- The number of two-dimensional maxima
- Optimal range max datacube for fixed dimensions
- Notes on the variance of the number of maxima in three dimensions
- Experimental evaluation of the height of a random set of points in a d-dimensional cube
- A new type of multivariate records: depth-based records
- A note on harmonic number identities, Stirling series and multiple zeta values
- Normal approximation for random sums
- Rooted edges of a minimal directed spanning tree on random points
- scientific article; zbMATH DE number 7650102 (Why is no real title available?)
- On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification
- Gaussian approximation for rooted edges in a random minimal directed spanning tree
- A phase transition for the probability of being a maximum among random vectors with general iid coordinates
- Sharpened localization of the trailing point of the Pareto record frontier
- Sharpened localization of the trailing point of the Pareto record frontier
- On the probability of a Pareto record
This page was built for publication: Maxima in hypercubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5704837)
