Maxima in hypercubes

Abstract

We derive a Berry-Esseen bound, essentially of the order of the square of the standard deviation, for the number of maxima in random samples from (0,1)d. The bound is, although not optimal, the first of its kind for the number of maxima in dimensions higher than two. The proof uses Poisson processes and Stein's method. We also propose a new method for computing the variance and derive an asymptotic expansion. The methods of proof we propose are of some generality and applicable to other regions such as d-dimensional simplex. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005