On the variance of the number of maxima in random vectors and its applications
type: Item
instance of: scholarly article
title: On the variance of the number of maxima in random vectors and its applications
zbMATH Open document ID: 0941.60021
author: Chern-Ching Chao
author: Hsien-Kuei Hwang
author: Wen-Qi Liang
author: Zhidong Bai
published in: The Annals of Applied Probability
publication date: 2000-07-28T00:00:00Z
review text: Let \(X = \{\mathbf x_1, \mathbf x_2, \dots, \mathbf x_n\}\) be a set of independent and identically distributed (iid) random vectors in \(\mathbb R^d\). A point \(\mathbf x_i= (x_{i1},\dots, x_{id})\) is said to be dominated by \(\mathbf x_j\) if \(x_{ik} < x_{jk}\) for all \(k=1,\dots,d\), and a point \(\mathbf x_i\) is called a maximum of \(X\) if none of the other points dominates it. The paper considers the number of maxima of \(X\) which is denoted by \(K_{n,d}\). All results in the paper concerning the random variables \(K_{n,d}\) are under the assumption that \(\mathbf x_1, \mathbf x_2, \dots, \mathbf x_n\) are iid and that the components of each vector are identically and continuously distributed. The main result is the following theorem: Under the above assumptions, for \(d\geq 2\), \[ \operatorname {Var} (K_{n,d})= [(d-1)!]^{-1} (1+c_d)(\log n)^{d-1} (1+O((\log n)^{-1})), \quad n\to \infty, \] where \[ c_d=\sum_{l\geq 1}l^{-2} \sum_{1\leq p, q\leq l} \left(l\atop p\right) \left(l\atop q\right) (-1)^{p+q} pq ((p^{-1}+q^{-1})^{d-1} -p^{1-d}-q^{1-d}). \] Applications of the results to algorithmic analysis are also indicated.
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 1319837
zbMATH Keywords: maximal points
zbMATH Keywords: multicriterial optimization
zbMATH Keywords: Eulerian sums
reviewed by: Viktor Ohanyan
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1028903455
OpenAlex ID: W2127895666
cites work: Experimental Evaluation of Euler Sums
cites work: On the Distribution of the Number of Admissible Points in a Vector Random Sample
cites work: Fast linear expected-time algorithms for computing maxima and convex hulls
cites work: On the Average Number of Maxima in a Set of Vectors and Applications
cites work: Divide and conquer for linear expected time
cites work: Supervision of queues of requests in computer systems
cites work: On the average number of maximal in a set of vectors
cites work: A note on finding convex hulls via maximal vectors
cites work: Moment inequalities for random variables in computational geometry
cites work: A note on the expected time for finding maxima by list algorithms
cites work: Euler Sums and Contour Integral Representations
cites work: How many maxima can there be?
cites work: Multiple harmonic series
cites work: Q3875087
cites work: The Number of Outcomes in the Pareto-Optimal Set of Discrete Bargaining Games
cites work: Q3694703
cites work: Q3696852
cites work: Q4324348
DOI: 10.1214/AOAP/1028903455
description: scientific article; zbMATH DE number 1319837