Sharp concentration of random polytopes (Q817672)

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.