Variance expansion and Berry-Esseen bound for the number of vertices of a random polygon in a polygon

Gusakova, Anna; Reitzner, Matthias; Thäle, Christoph

Annales Henri Lebesgue, Tome 6 (2023), pp. 875-906

Fix a container polygon $P$ in the plane and consider the convex hull $P_n$ of $n\ge 3$ independent and uniformly distributed in $P$ random points. In the focus of this paper is the vertex number of the random polygon $P_n$. The precise variance expansion for the vertex number is determined up to the constant-order term, a result which can be considered as a second-order analogue of the classical expansion for the expectation of Rényi and Sulanke (1963). Moreover, a sharp Berry–Esseen bound is derived for the vertex number of the random polygon $P_n$, which is of the same order as one over the square-root of the variance. The latter is optimal and improves the earlier result of Bárány and Reitzner (2006) by removing the factor ${(loglogn)}^{60}$ in the planar case. The main idea behind the proof of both results is a decomposition of the boundary of the random polygon $P_n$ into random convex chains and a careful merging of the variance expansions and Berry–Esseen bounds for the vertex numbers of the individual chains. In the course of the proof, we derive similar results for the Poissonized model.

Fixons un polygone conteneur $P$ dans le plan et considérons l’enveloppe convexe $P_n$ de $n\ge 3$ points aléatoires indépendants et uniformément distribués dans $P$. Cet article est consacré à l’étude du nombre de sommets du polygone aléatoire $P_n$. Nous déterminons l’asymptotique précise de sa variance jusqu’au terme constant, un résultat qui peut être considéré comme un analogue au second ordre du développement classique pour l’espérance de Rényi et Sulanke (1963). De plus, nous obtenons une borne de Berry–Esseen précise pour le nombre de sommets du polygone aléatoire $P_n$, du même ordre que l’inverse de la racine carrée de la variance. Cette borne est optimale et améliore le résultat précédent de Bárány et Reitzner (2006) en supprimant le facteur ${(loglogn)}^{60}$ dans le cas planaire. L’idée principale dans la preuve des deux résultats est une décomposition du bord du polygone aléatoire $P_n$ en chaînes convexes aléatoires et une fusion soigneuse des asymptotiques de la variance et des bornes de Berry–Esseen pour le nombre de sommets des chaînes individuelles. Au cours de la preuve, nous obtenons des résultats similaires pour le modèle poissonisé.

Classification : 52A22, 60D05
Keywords: Berry–Esseen bound, central limit theorem, geometric probability, Poisson point process, random convex chain, random polygon, variance expansion

[BB93] Bárány, Imre; Buchta, Christian Random polytopes in a convex polytope, independence of shape, and concentration of vertices., Math. Ann., Volume 297 (1993) no. 3, pp. 467-498 | MR | DOI | Zbl

[BD97] Bárány, Imre; Dalla, Leoni Few points to generate a random polytope, Mathematika, Volume 44 (1997) no. 2, pp. 325-331 | MR | DOI | Zbl

[BR06] Bárány, Imre; Reitzner, Matthias Random polytopes, 2006 (Preprint available at https://citeseerx.ist.psu.edu/doc/10.1.1.77.2284)

[BR10a] Bárány, Imre; Reitzner, Matthias On the variance of random polytopes, Adv. Math., Volume 225 (2010) no. 4, pp. 1986-2001 | MR | DOI | Zbl

[BR10b] Bárány, Imre; Reitzner, Matthias Poisson polytopes, Ann. Probab., Volume 38 (2010) no. 4, pp. 1507-1531 | MR | DOI | Zbl

[Buc05] Buchta, Christian An identity relating moments of functionals of convex hulls, Discrete Comput. Geom., Volume 33 (2005), pp. 125-142 | MR | DOI | Zbl

[Buc12] Buchta, Christian On the boundary structure of the convex hull of random points, Adv. Geom., Volume 12 (2012), pp. 179-190 | MR | DOI | Zbl

[BV07] Bárány, Imre; Vu, Van Central limit theorems for Gaussian polytopes, Ann. Probab., Volume 35 (2007), pp. 1593-1621 | MR | Zbl

[CY17] Calka, Pierre; Yukich, Joseph E. Variance asymptotics and scaling limits for random polytopes, Adv. Math., Volume 304 (2017), pp. 1-55 | DOI | MR | Zbl

[Efr65] Efron, Bradley The convex hull of a random set of points, Biometrika, Volume 52 (1965), pp. 331-343 | MR | DOI | Zbl

[Eng81] Englund, Gunnar A Remainder Term Estimate for the Normal Approximation in Classical Occupancy, Ann. Probab., Volume 9 (1981), pp. 684-692 | MR | Zbl

[Gro88] Groeneboom, Piet Limit theorems for convex hulls, Probab. Theory Relat. Fields, Volume 79 (1988) no. 3, pp. 327-368 | Zbl | MR | DOI

[GT21] Gusakova, Anna; Thäle, C. On Random Convex Chains, Orthogonal Polynomials, PF Sequences and Probabilistic limit Theorems, Mathematika, Volume 67 (2021) no. 2, pp. 434-446 | Zbl | DOI

[Han82] Hanisch, Karl-Heinz On inversion formulae for $n$-fold Palm distributionsof point processes in LCS-spaces, Math. Nachr., Volume 106 (1982), pp. 171-179 | MR | DOI | Zbl

[LP18] Last, Günter; Penrose, Mathew Lectures on the Poisson Process, Institute of Mathematical Statistics Textbooks, 7, Cambridge University Press, 2018 | Zbl | MR

[LRSY19] Lachièze-Rey, Raphaël; Schulte, Matthias; Yukich, Joseph E. Normal approximation for stabilizing functionals, Ann. Appl. Probab., Volume 29 (2019) no. 2, pp. 931-993 | MR | Zbl | DOI

[Mat82] Matsunawa, Tadashi Some strong $\epsilon$-equivalence of random variables, Ann. Inst. Stat. Math., Volume 34 (1982) no. 2, pp. 209-224 | DOI | MR | Zbl

[Par11] Pardon, John Central limit theorems for random polygons in an arbitrary convex set, Ann. Probab., Volume 39 (2011) no. 3, pp. 881-903 | DOI | MR | Zbl

[Par12] Pardon, John Central limit theorems for uniform model random polygons, J. Theor. Probab., Volume 25 (2012) no. 3, pp. 823-833 | DOI | MR | Zbl

[Rei05] Reitzner, Matthias Central limit theorems for random polytopes, Probab. Theory Relat. Fields, Volume 133 (2005), pp. 483-507 | Zbl | MR | DOI

[RS63] Rényi, Alfréd; Sulanke, Rolf Über die konvexe Hülle von $n$ zufällig gewählten Punkten, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 2 (1963), pp. 75-84 | DOI | MR | Zbl

[Sch91] Schütt, Carsten The convex floating body and polyhedral approximation, Isr. J. Math., Volume 73 (1991), pp. 65–-77 | Zbl | MR | DOI

[Ver69] Vervaat, Wim Upper bounds for the distance in total variation between the binomial or negative binomial and the Poisson distribution, Stat. Neerl., Volume 23 (1969), pp. 79-86 | Zbl | DOI | MR

[Vu06] Vu, Van Central limit theorems for random polytopes in a smooth convex set, Adv. Math., Volume 207 (2006) no. 1, pp. 221-243 | DOI | Zbl | MR

[Zol76] Zolotarev, Vladimir M. Metric distances in spaces of random variables and their distributions, Math. USSR, Sb., Volume 30 (1976) no. 3, pp. 373-401 | DOI | Zbl | MR