×

zbMATH — the first resource for mathematics

Maxima in hypercubes. (English) Zbl 1080.60007
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 W.-M. Chen, H.-K. Hwang and 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 M. E. Dyer and 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 Z.-D. Bai, C.-C. Chao, H.-K. Hwang and W.-Q. Liang, Ann. Appl. Probab. 8, 886–895 (1998; Zbl 0941.60021)]. 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 A. D. Barbour and 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.).

MSC:
60D05 Geometric probability and stochastic geometry
60C05 Combinatorial probability
52A22 Random convex sets and integral geometry (aspects of convex geometry)
60F05 Central limit and other weak theorems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bai, Ann Appl Probab 8 pp 886– (1998)
[2] Bai, Electron J Probab 6 (2001) · Zbl 0986.60007 · doi:10.1214/EJP.v6-76
[3] Bai, Electron J Probab 8 (2003) · Zbl 1065.60020 · doi:10.1214/EJP.v8-137
[4] , and , Poisson approximation, Oxford University Press, New York, 1992.
[5] Barbour, Adv Appl Probab 33 pp 727– (2001)
[6] Barndorff-Nielsen, Theory Probab Appl 11 pp 249– (1966)
[7] Baryshnikov, Probab Theory Related Fields 117 pp 163– (2000)
[8] Bentley, J ACM 25 pp 536– (1978)
[9] Berezovskii, Autom Remote Control 36 pp 1719– (1975)
[10] Blair, Math Program 35 pp 133– (1986)
[11] Buchta, Inform Process Lett 33 pp 63– (1989)
[12] Calpine, Omega Int J Management Sci 4 pp 141– (1976)
[13] Carlsund, Random Structures Algorithms 22 pp 440– (2003)
[14] Chen, Discrete Math Theor Comput Sci (Electron) 6 pp 107– (2003)
[15] Devroye, Inform Process Lett 11 pp 53– (1980)
[16] Lecture notes on bucket algorithms, Birkhäuser Boston, Boston, MA, 1986. · Zbl 0644.68086 · doi:10.1007/978-1-4899-3531-1
[17] Devroye, Algorithmica 23 pp 97– (1999)
[18] Dyer, Asia-Pacific J Oper Res 15 pp 159– (1998)
[19] Flajolet, Random Structures Algorithms 7 pp 117– (1995)
[20] Flajolet, Experiment Math 7 pp 15– (1998) · Zbl 0920.11061 · doi:10.1080/10586458.1998.10504356
[21] Flajolet, Theoret Comput Sci 144 pp 101– (1995)
[22] Golin, Algorithmica 11 pp 501– (1994)
[23] ”Phase changes in random recursive structures and algorithms,” Proceedings of the Workshop on Probability with Applications to Finance and Insurance (Hong Kong, July, 2002), , and (Editors), 82-97. World Scientific, Singapore, June 2004. (Preprint available at algo.stat.sinica.edu.tw).
[24] Ivanin, Kibernetika (Kiev) 3 pp 145– (1975)
[25] Cybernetics 11 pp 506– (1976) · Zbl 0978.01027
[26] ”Calculation of the dispersion of the number of elements of the Pareto set for the choice of independent vectors with independent components,” Theory of optimal decisions, 90-100. Akad. Nauk. Ukr. SSR Inst. Kibernet., Kiev, 1976 (in Russian).
[27] , and , Random graphs, Wiley, New York, 2000. · doi:10.1002/9781118032718
[28] Kuksa, Kibernetika (Kiev) 6 pp 37– (1972)
[29] Labelle, J Combinat Theory Ser A 69 pp 1– (1995)
[30] O’Neill, Math Oper Res 6 pp 571– (1980)
[31] ”Asymptotic behavior of the binomial distribution,” Selected translations in mathematical statistics and probability, Volume 1, 87-95. ISM and AMS, Providence, RI, 1961
[32] Russian Usp Mat Nauk 8 pp 135– (1953)
[33] Vout, Eureka 36 (1973)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.