Sharp concentration of random polytopes
Fix a convex set \(K \subset {\mathbb R}^d\) of volume one. For \(n \geq 1\), denote by \(K_n\) the random polytope obtained by taking the convex hull of \(n\) independent points that are distributed uniformly in \(K\). Let \(V(K_n)\) stand for the volume of \(K_n\), and let \(N(K_n)\) stand for the number of vertices of \(K_n\). The asymptotics of \(V(K_n)\) and \(N(K_n)\) as \(n \rightarrow \infty\) are investigated in the reviewed paper. It is shown that both \(V(K_n)\) and \(N(K_n)\) are concentrated around their mean with a very thin tail, in various scenarios. For instance, it is proven that when \(\partial K\) is sufficiently smooth with an everywhere positive Gauss curvature, then for \(0 < t < c n^{(d-1) / (6d + 10)}\), \[ Prob \{ \left| V(K_n) - {\mathbb E} V(K_n) \right| \geq t \sigma \} \leq C e^{-c^{\prime} t^2} \] where \(c,C,c^{\prime} > 0\) depend solely on \(K\), and \(\sigma^2 = n^{-(d+3) / (d+1)}\) is claimed to have the order of magnitude of the variance of \(V(K_n)\). (In the reviewed paper it is written that M. Reitzner, in a yet-unpublished paper, showed that the variance of \(V(K_n)\) has the order of magnitude of \(n^{-(d+3) / (d+1)}\)). The main technical tool in the proofs is an interesting general martingale inequality, that was already developed and applied by the author in earlier papers. In the classical Azuma inequality, a concentration inequality is obtained when the martingale differences satisfy a certain \(L^{\infty}\) bound. Very roughly speaking, the author's new martingale inequality is based on \(L^2\) bounds rather than \(L^{\infty}\). The sharp concentration inequalities obtained in this paper demonstrate the strength and the potential of this new martingale inequality.
- Central limit theorem for the volume of random polytopes with vertices on the boundary
- Concentration and moderate deviations for Poisson polytopes and polyhedra
- Methods for estimation of convex sets
- Brownian limits, local limits and variance asymptotics for convex hulls in the ball
- On the variance of random polytopes
- Concentration on Poisson spaces via modified -Sobolev inequalities
- Multivariate normal approximation for functionals of random polytopes
- Deviation inequalities for random polytopes in arbitrary convex bodies
- Random polytopes and the wet part for arbitrary probability distributions
- Central limit theorems for Gaussian polytopes
- Uniform behaviors of random polytopes under the Hausdorff metric
- Random inscribing polytopes
- An inscribing model for random polytopes
- A concentration inequality for random polytopes, Dirichlet-Voronoi tiling numbers and the geometric balls and bins problem
- Random points in halfspheres
- Monotonicity of expected f-vectors for projections of regular polytopes
- Random points and lattice points in convex bodies
- The floating body and the hyperplane conjecture
- Concentration of random polytopes around the expected convex hull
- Variance estimates for random disc-polygons in smooth convex discs
- Random polytopes: central limit theorems for intrinsic volumes
- Extension complexity of low-dimensional polytopes
- Asymptotic normality for random polytopes in non-Euclidean geometries
- Limit theorems for random polytopes with vertices on convex surfaces
- Asymptotic methods for random tessellations
- The Exact Distribution of the Number of Vertices of a Random Convex Chain
- Concentration estimates for functions of finite high‐dimensional random arrays
- Gelfand-Tsetlin polytopes and random contractions away from the limiting shape
- Introduction to Stochastic Geometry
- Limit theory for the first layers of the random convex hull peeling in the unit ball
- Limit theorems for the volumes of small codimensional random sections of \(\ell_{p}^{n}\)-balls
- Convex hulls of random order types
- Poincaré inequality in mean value for Gaussian polytopes
- Intrinsic volumes and Gaussian polytopes: the missing piece of the jigsaw
- Finite admixture models: a bridge with stochastic geometry and Choquet theory
- A central limit theorem for random disc-polygons in smooth convex discs
- On the deterministic interior body of random polytopes
- Random inscribed polytopes in projective geometries
- Central limit theorems for random polytopes in a smooth convex set
- Poisson polytopes
This page was built for publication: Sharp concentration of random polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817672)
