On the variance of the number of maxima in random vectors and its applications (Q1296610)

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.