Abstract
Let μ be an even compactly supported Borel probability measure on the real line. For every N > n consider N independent random vectors X 1, ..., X N in ℝn, with independent coordinates having distribution μ. We establish a sharp threshold for the volume of the random polytope K N ≔ conv{X 1, ..., X N }, provided that the Legendre transform λ of the cumulant generating function of μ satisfies the condition
, where α is the right endpoint of the support of μ. The method and the result generalize work of Dyer, Füredi and McDiarmid on 0/1 polytopes. We verify (*) for a large class of distributions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. R. Bahadur and R. Ranga Rao, On deviations of the sample mean, Annals of Mathematical Statistics 31 (1960), 1015–1027.
I. Bárány and A. Pór, On 0–1 polytopes with many facets, Advances in Mathematics 161 (2001), 209–228.
N. H. Bingham, C. M. Goldie and J. L. Teugels, Regular Variation, Cambridge University Press, Cambridge, 1987.
C. Buchta, On a conjecture of R. E. Miles about the convex hull of random points, Monatshefte für Mathematik 102 (1986), 91–102.
H. Carnal, Die konvexe Hülle von n-rotationssymmetrisch verteilten Punkten, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 15 (1970), 168–176.
A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Springer, New York, 1998.
M. E. Dyer, Z. Füredi and C. McDiarmid, Volumes spanned by random points in the hypercube, Random Structures Algorithms 3 (1992), 91–106.
W. Feller, An Introduction to Probability and its Applications, Vol. II, second edition, Wiley, New York, 1971.
D. Gatzouras, A. Giannopoulos and N. Markoulakis, Lower bound for the maximal number of facets of a 0/1 polytope, Discrete & Computational Geometry 34 (2005), 331–349.
D. Gatzouras, A. Giannopoulos and N. Markoulakis, On the maximal number of facets of 0/1 polytopes, in GAFA Seminar Volume 2004–2005 (V. D. Milman and G. Schechtman, eds.), Lecture Notes in Mathematics, Vol. 1910, Springer, 2007, pp. 117–125.
R. E. Miles, Isotropic random simplices, Advances in Applied Probability 3 (1971), 353–382.
R. Schneider, Discrete aspects of stochastic geometry, in Handbook of Discrete and Computational Geometry (J. E. Goodman, and J. O’Rourke, eds.), second edition, Chapman & Hall/CRC, Boca Raton, 2004, pp. 255–278.
D. Stroock, Probability Theory. An Analytic View, Cambridge University Press, Cambridge, 1993.
Author information
Authors and Affiliations
Corresponding author
Additional information
The project is co-funded by the European Social Fund and National Resources — (EPEAEK II) “Pythagoras II”.
Rights and permissions
About this article
Cite this article
Gatzouras, D., Giannopoulos, A. Threshold for the volume spanned by random points with independent coordinates. Isr. J. Math. 169, 125–153 (2009). https://doi.org/10.1007/s11856-009-0007-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-009-0007-z