Concentration of random polytopes around the expected convex hull

Daniel J. Fresen (Yale University)
Richard A. Vitale (University of Connecticut)

Abstract


We provide a streamlined proof and improved estimates for the weak multivariate Gnedenko law of large numbers on concentration of random polytopes within the space of convex bodies (in a fixed or a high dimensional setting), as well as a corresponding strong law of large numbers.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-8

Publication Date: August 26, 2014

DOI: 10.1214/ECP.v19-3376

References

  • Artstein, Zvi. On the calculus of closed set-valued functions. Indiana Univ. Math. J. 24 (1974/75), 433--441. MR0360985
  • Artstein, Zvi; Vitale, Richard A. A strong law of large numbers for random compact sets. Ann. Probability 3 (1975), no. 5, 879--882. MR0385966
  • Aumann, Robert J. Integrals of set-valued functions. J. Math. Anal. Appl. 12 1965 1--12. MR0185073
  • Bárány, Imre. Random polytopes, convex bodies, and approximation. Stochastic geometry, 77--118, Lecture Notes in Math., 1892, Springer, Berlin, 2007. MR2327291
  • Bárány, I.; Larman, D. G. Convex bodies, economic cap coverings, random polytopes. Mathematika 35 (1988), no. 2, 274--291. MR0986636
  • Bárány, I.; Vitale, R. A. Random convex hulls: floating bodies and expectations. J. Approx. Theory 75 (1993), no. 2, 130--135. MR1249393
  • Dafnis, N.; Giannopoulos, A.; Tsolomitis, A. Asymptotic shape of a random polytope in a convex body. J. Funct. Anal. 257 (2009), no. 9, 2820--2839. MR2559718
  • Davis, Richard A.; Mulrow, Edward; Resnick, Sidney I. Almost sure limit sets of random samples in ${\bf R}^ d$. Adv. in Appl. Probab. 20 (1988), no. 3, 573--599. MR0955505
  • Debreu, Gerard. Integration of correspondences. 1967 Proc. Fifth Berkeley Sympos. Math. Statist. and Probability (Berkeley, Calif., 1965/66), Vol. II: Contributions to Probability Theory, Part 1 pp. 351--372 Univ. California Press, Berkeley, Calif. MR0228252
  • Dupin, C.: Applications de géométrie et de méchanique, a la marine, aux ponts et chaussées, etc., pour faire suite aux développements de géométrie. Paris (1822)
  • Fisher, Lloyd D., Jr. The convex hull of a sample. Bull. Amer. Math. Soc. 72 1966 555--558. MR0192526
  • Fisher, Lloyd. Limiting sets and convex hulls of samples from product measures. Ann. Math. Statist. 40 1969 1824--1832. MR0253391
  • Fresen, Daniel. A multivariate Gnedenko law of large numbers. Ann. Probab. 41 (2013), no. 5, 3051--3080. MR3127874
  • Geffroy, Jean. Localisation asymptotique du polyèdre d'appui d'un échantillon Laplacien à $k$ dimensions. (French) Publ. Inst. Statist. Univ. Paris 10 1961 213--228. MR0141148
  • Gnedenko, B. Sur la distribution limite du terme maximum d'une série aléatoire. (French) Ann. of Math. (2) 44, (1943). 423--453. MR0008655
  • Goodey, Paul; Weil, Wolfgang. A uniqueness result for mean section bodies. Adv. Math. 229 (2012), no. 1, 596--601. MR2854184
  • Goodman, Victor. Characteristics of normal samples. Ann. Probab. 16 (1988), no. 3, 1281--1290. MR0942768
  • Gruber, Peter M. The space of convex bodies. Handbook of convex geometry, Vol. A, B, 301--318, North-Holland, Amsterdam, 1993. MR1242983
  • Kinoshita, K.; Resnick, Sidney I. Convergence of scaled random samples in ${\bf R}^ d$. Ann. Probab. 19 (1991), no. 4, 1640--1663. MR1127719
  • Kudō, Hirokichi. Dependent experiments and sufficient statistics. Nat. Sci. Rep. Ochanomizu Univ. 4, (1954). 151--163. MR0067441
  • Lovász, László; Vempala, Santosh. The geometry of logconcave functions and sampling algorithms. Random Structures Algorithms 30 (2007), no. 3, 307--358. MR2309621
  • McBeth, Douglas; Resnick, Sidney. Stability of random sets generated by multivariate samples. Comm. Statist. Stochastic Models 10 (1994), no. 3, 549--574. MR1284552
  • Molchanov, Ilya. Theory of random sets. Probability and its Applications (New York). Springer-Verlag London, Ltd., London, 2005. xvi+488 pp. ISBN: 978-185223-892-3; 1-85233-892-X MR2132405
  • Mosler, Karl. Multivariate dispersion, central regions and depth. The lift zonoid approach. Lecture Notes in Statistics, 165. Springer-Verlag, Berlin, 2002. xii+291 pp. ISBN: 0-387-95412-0 MR1913862
  • Pisier, Gilles. The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics, 94. Cambridge University Press, Cambridge, 1989. xvi+250 pp. ISBN: 0-521-36465-5; 0-521-66635-X MR1036275
  • Schechtman, Gideon. Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. 200 (2006), no. 1, 125--135. MR2199631
  • Schechtman, G.; Zinn, J. On the volume of the intersection of two $L^ n_ p$ balls. Proc. Amer. Math. Soc. 110 (1990), no. 1, 217--224. MR1015684
  • Schneider, Rolf. Convex bodies: the Brunn-Minkowski theory. Second expanded edition. Encyclopedia of Mathematics and its Applications, 151. Cambridge University Press, Cambridge, 2014. xxii+736 pp. ISBN: 978-1-107-60101-7 MR3155183
  • Schütt, Carsten; Werner, Elisabeth. The convex floating body. Math. Scand. 66 (1990), no. 2, 275--290. MR1075144
  • Vitale, Richard A. Expected convex hulls, order statistics, and Banach space probabilities. Acta Appl. Math. 9 (1987), no. 1-2, 97--102. MR0900259
  • Vitale, Richard A. The Brunn-Minkowski inequality for random sets. J. Multivariate Anal. 33 (1990), no. 2, 286--293. MR1055274
  • Vitale, Richard A. Expected absolute random determinants and zonoids. Ann. Appl. Probab. 1 (1991), no. 2, 293--300. MR1102321
  • Vu, V. H. Sharp concentration of random polytopes. Geom. Funct. Anal. 15 (2005), no. 6, 1284--1318. MR2221249
  • Weil, Wolfgang. The estimation of mean shape and mean particle number in overlapping particle systems in the plane. Adv. in Appl. Probab. 27 (1995), no. 1, 102--119. MR1315581


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.