On the deterministic interior body of random polytopes
Minas Pafis, Natalia Tziotziou · 2025
Read On the deterministic interior body of random polytopes by Minas Pafis, Natalia Tziotziou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-15261.txt.
Introduction
Throw random points into space and connect them into a shape, and a natural question arises: how much of a fixed inner region does the random polytope reliably cover? Pafis and Tziotziou revisit this problem for points drawn from any probability distribution.
They show that once the number of points passes a modest multiple of the dimension, the polytope contains a specific inner body with overwhelming probability. That body is defined by half-space depth, the share of the distribution lying on the thin side of any plane through the point. The result needs no extra assumptions on the distribution, so it improves a line of earlier theorems at once. For well-behaved distributions they also compare the depth body with centroid bodies and level sets, to size the coverage.
Catalog record
| CREATOR | Minas Pafis, Natalia Tziotziou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-15261
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the deterministic interior body of random polytopes Minas Pafis, Natalia Tziotziou Abstract Let { X i } i = 1 ∞ \{X_{i}\}_{i=1}^{\infty} be a sequence of independent copies of a random vector X X in ℝ n \mathbb{R}^{n} . We revisit the question to determine the asymptotic shape of the random polytope K N = conv { X 1 , … , X N } K_{N}={\rm conv}\{X_{1},\ldots,X_{N}\} where N > n N>n . We show that for any β ∈ ( 0 , 1 ) \beta\in(0,1) there exists a constant c ( β ) > 0 c(\beta)>0 such that the following holds true: If μ \mu is a Borel probability measure on ℝ n {\mathbb{R}}^{n} then, for all N ⩾ c ( β ) n N\geqslant c(\beta)n we have that K N ⊇ T β ln ( N n ) ( μ ) K_{N}\supseteq T_{\beta\ln(\frac{N}{n})}(\mu) with probability greater than 1 − exp ( − 1 2 N 1 − β n β ) 1-\exp(-\tfrac{1}{2}N^{1-\beta}n^{\beta}) , where T p ( μ ) T_{p}(\mu) is the convex set of all points x ∈ ℝ n x\in\mathbb{R}^{n} with half-space depth greater than or equal to e − p e^{-p} . Our approach does not require any additional assumptions about the measure μ \mu and hence it generalizes and/or improves a sequence of previous results. Moreover, for the class of strongly regular measures we compare the family { T p ( μ ) } p > 0 \{T_{p}(\mu)\}_{p>0} to other natural families of convex bodies associated with μ \mu , such as the L p L_{p} -centroid bodies of μ \mu or the level sets of the Cramér transform of μ \mu , and use this information in order to estimate the size of a random K N K_{N} . 1 Introduction Let \mu be a Borel probability measure on \mathbb{R}^{n} and consider a sequence \{X_{i}\}_{i=1}^{\infty} of independent random vectors distributed according to \mu . The geometry of the random polytopes K_{N}={\rm conv}\{X_{1},\ldots,X_{N}\} and S_{N}={\rm conv}\{\pm X_{1},\ldots,\pm X_{N}\} has been extensively studied in a series of works by several authors. The following typical result of Gluskin [ 22 ] concerns the Gaussian case, where \mu=\gamma_{n} is the standard Gaussian measure on \mathbb{R}^{n} with density (2\pi)^{-n/2}\exp(-|x|^{2}/2) (in what follows, |\cdot| denotes the Euclidean norm): For any \beta\in(0,1) and N\geqslant c_{1}(\beta)n one has that (1.1) S_{N}\supseteq c_{2}(\beta)\sqrt{\ln(eN/n)}\,B_{2}^{n} with probability greater than 1-2\exp(-c_{3}N^{1-\beta}n^{\beta}) , where c_{i}(\beta) are constants that depend only on \beta and c_{3} is an absolute positive constant. This result has been extended in [ 36 ] to random polytopes generated by a random vector X=(\xi_{1},\ldots,\xi_{n}) whose coordinates are independent copies of a random variable \xi with expectation \mathbb{E}(\xi)=0 and variance {\rm Var}(\xi)=1 , that satisfies \left(\mathbb{E}|\xi|^{p}\right)^{1/p}\leqslant L\sqrt{p} for some constant L>0 and every p\geqslant 1 (we then say that \xi is L -subgaussian). For any \beta\in(0,1) and N\geqslant c_{1}(\beta,L)n one has that (1.2) S_{N}\supseteq c_{2}(\beta,L)\Big(B_{\infty}^{n}\cap\sqrt{\ln(eN/n)}\,B_{2}^{n}\Big) with probability greater than 1-2\exp(-c_{3}N^{1-\beta}n^{\beta}) . A version of this fact for the special case where the \xi_{i} ’s are symmetric \pm 1 random variables had been previously obtained in [ 20 ] for N\geqslant n(\ln n)^{2} and with probability greater than 1-e^{-n} . A general study of the asymptotic shape of random polytopes when their vertices are assumed to have a log-concave distribution was initiated by Dafnis, Giannopoulos and Tsolomitis in [ 15 ] and [ 16 ] . Given a centered log-concave probability measure \mu on {\mathbb{R}}^{n} , for every N\geqslant n we consider N independent random vectors X_{1},\ldots,X_{N} distributed according to \mu and the random polytope S_{N}:={\rm conv}\{\pm X_{1},\ldots,\pm X_{N}\} . The main idea in these works was to compare S_{N} with the L_{p} -centroid body of \mu for a suitable value of p ; roughly speaking, S_{N} is close to the body Z_{\ln(eN/n)}(\mu) with high probability. Recall that the L_{p} -centroid bodies Z_{p}(\mu) , p\geqslant 1 , are defined through their support function h_{Z_{p}(\mu)} given by (1.3) h_{Z_{p}(\mu)}(y):=\|\langle\cdot,y\rangle\|_{L_{p}(\mu)}=\left(\int_{{\mathbb{R}}^{n}}|\langle x,y\rangle|^{p}d\mu(x)\right)^{1/p}. These bodies incorporate information about the distribution of linear functionals with respect to \mu . The L_{p} -centroid bodies were introduced, under a different normalization, by Lutwak and Zhang in [ 37 ] , while in [ 41 ] for the first time, and in [ 42 ] later on, Paouris used geometric properties of them to acquire detailed information about the distribution of the Euclidean norm with respect to \mu . The starting observation in [ 15 ] was that the deterministic body \sqrt{p}\,B_{2}^{n} that appears in ( 1.1 ) is approximately equal to Z_{p}(\gamma_{n}) and the deterministic body B_{\infty}^{n}\cap\sqrt{p}\,B_{2}^{n} that appears in ( 1.2 ) is approximately equal to Z_{p}(\nu_{n}) , where \nu_{n} is the uniform measure on the cube. It was proved in [ 15 ] that, given any centered log-concave probability measure \mu on {\mathbb{R}}^{n} and any cn\leqslant N\leqslant e^{n} , the random polytope S_{N} defined by N independent random vectors X_{1},\ldots,X_{N} which are distributed according to \mu satisfies the inclusion (1.4) S_{N}\supseteq c_{1}Z_{\ln(eN/n)}(\mu) with probability greater than 1-2\exp\left(-c_{3}N^{1-\beta}n^{\beta}\right)-{\mathbb{P}}(\|\Gamma:\ell_{2}^{n}\to\ell_{2}^{N}\|\geqslant\gamma\sqrt{N})\geqslant 1-\exp(-c_{0}\gamma\sqrt{N}), where \Gamma:\ell_{2}^{n}\to\ell_{2}^{N} is the random operator \Gamma(y)=(\langle X_{1},y\rangle,\ldots\langle X_{N},y\rangle) . The last inequality follows from the estimate {\mathbb{P}}(\|\Gamma:\ell_{2}^{n}\to\ell_{2}^{N}\|\geqslant\gamma\sqrt{N})\leqslant\exp(-c\gamma\sqrt{N}) for all N\geqslant\gamma n , that has been obtained in [ 1 ] . This approach was further extended to random polytopes with vertices that have an arbitrary symmetric distribution \mu on \mathbb{R}^{n} . Guédon, Krahmer, Kümmerle, Mendelson and Rauhut introduced in [ 26 ] (see also [ 39 ] and the earlier work [ 25 ] which was the motivation for [ 39 ] and [ 26 ] ) the family of sets \{U_{p}(\mu)\}_{p\geqslant 1} defined by (1.5) U_{p}(\mu)=\{y\in\mathbb{R}^{n}:\;\mu(\{x\in\mathbb{R}^{n}:\langle x,y\rangle\geqslant 1\})\leqslant\exp(-p)\} and showed that, under some assumptions on \mu , the random polytopes S_{N} and K_{N} contain \frac{1}{2}(U_{p}(\mu))^{\circ} with probability close to 1 , where A^{\circ} denotes the polar set of A . Their assumption on \mu is that there exists a norm \|\cdot\| on \mathbb{R}^{n} and some positive constants \gamma,\delta,r and L such that the small ball condition \mu(\{x\in\mathbb{R}^{n}:|\langle x,y\rangle|\geqslant\gamma\|y\|\})\geqslant\delta and the L_{r} -condition \big(\mathbb{E}_{\mu}|\langle\cdot,y\rangle|^{r}\big)^{1/r}\leqslant L\|y\| are satisfied for every y\in\mathbb{R}^{n} . The main result in [ 26 ] asserts that if \mu is a symmetric Borel probability measure on \mathbb{R}^{n} that satisfies a small ball condition and an L_{r} -condition with constants \gamma,\delta,r and L for some norm on \mathbb{R}^{n} then, for any 0<\beta<1 there exists a positive constant c_{0}:=c(\beta,\delta,r,L/\gamma) such that if N\geqslant c_{0}n and p=\beta\ln(eN/n) we have (1.6) S_{N}\supseteq\frac{1}{2}(U_{p}(\mu))^{\circ} with probability greater than 1-2\exp(-c_{1}N^{1-\beta}n^{\beta}) , where c_{1}>0 is an absolute constant. It is explained in [ 26 ] that the same inclusion holds for the random polytope K_{N} and that it implies ( 1.4 ), with the improved and optimal probability estimate stated above, when \mu is a centered log-concave probability measure (we shall discuss and further study the relation between U_{p}(\mu) and Z_{p}(\mu) in Sections 3 and 4 ). Let now \mu be an arbitrary Borel probability measure on \mathbb{R}^{n} . For any x\in{\mathbb{R}}^{n} we denote by {\cal H}(x) the set of all closed half-spaces H^{+} of {\mathbb{R}}^{n} containing x . The function \varphi_{\mu}(x)=\inf\{\mu(H^{+}):H^{+}\in{\cal H}(x)\} (introduced by Tukey in [ 46 ] ) is the Tukey half-space depth function of \mu . Note that the