Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Random Structures an...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Random Structures and Algorithms
Article . 2005 . Peer-reviewed
License: Wiley TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2005
Data sources: zbMATH Open
DBLP
Article . 2005
Data sources: DBLP
versions View all 3 versions
addClaim

Maxima in hypercubes

Authors: Zhi-Dong Bai; Luc Devroye; Hsien-Kuei Hwang; Tsung-Hsi Tsai;

Maxima in hypercubes

Abstract

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

Country
Singapore
Keywords

Berry-Esseen bound, Combinatorial probability, Random convex sets and integral geometry (aspects of convex geometry), central limit theorem, Central limit and other weak theorems, Geometric probability and stochastic geometry, Kolmogorov distance, asymptotic approximations

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    29
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
29
Top 10%
Top 10%
Top 10%
Related to Research communities
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!