On the variance of the number of maxima in random vectors and its applications
Open Access
- 1 August 1998
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 8 (3) , 886-895
- https://doi.org/10.1214/aoap/1028903455
Abstract
We derive a general asymptotic formula for the variance of the number of maxima in a set of independent and identically distributed random vectors in $\mathbb{R}^d$, where the components of each vector are independently and continuously distributed. Applications of the results to algorithmic analysis are also indicated.
Keywords
This publication has 16 references indexed in Scilit:
- Experimental Evaluation of Euler SumsExperimental Mathematics, 1994
- How many maxima can there be?Computational Geometry, 1993
- Fast linear expected-time algorithms for computing maxima and convex hullsAlgorithmica, 1993
- On the average number of maxima in a set of vectorsInformation Processing Letters, 1989
- Analysis of Data from thePlaces Rated AlmanacThe American Statistician, 1987
- A note on finding convex hulls via maximal vectorsInformation Processing Letters, 1980
- On the Average Number of Maxima in a Set of Vectors and ApplicationsJournal of the ACM, 1978
- Divide and conquer for linear expected timeInformation Processing Letters, 1978
- Estimate of the mathematical expectation of the number of elements in a Pareto setCybernetics and Systems Analysis, 1976
- On the Distribution of the Number of Admissible Points in a Vector Random SampleTheory of Probability and Its Applications, 1966