Threshold for the Measure of Random Polytopes
摘要
Starting with the work of Dyer, Füredi and McDiarmid who established a sharp threshold for the expected volume of random polytopes with independent vertices uniformly distributed in the discrete cube \(E_2^n=\{-1,1\}^n\) , in this survey article we focus on a very general variant of the problem. Let \(\mu \) be a log-concave probability measure on \({\mathbb R}^n\) and for any \(N>n\) consider the random polytope \(K_N=\textrm{conv}\{X_1,\ldots ,X_N\}\) , where \(X_1,X_2,\ldots \) are independent random points in \({\mathbb R}^n\) distributed according to \(\mu \) . We discuss an approach to the question if there exists a threshold for the expected measure \({\mathbb E}_{\mu ^N}[\mu (K_N)]\) of \(K_N\) , based on joint works with S. Brazitikos and M. Pafis, via the Cramér transform \(\Lambda _{\mu }^{*}\) of \(\mu \) . We show that, under some conditions, one has a sharp threshold for the expectation \({\mathbb E}_{\mu ^N}[\mu (K_N)]\) of the measure of \(K_N\) : it is close to 0 if \(\ln N\ll {\mathbb E}_{\mu }(\Lambda _{\mu }^{*})\) and close to 1 if \(\ln N\gg {\mathbb E}_{\mu }(\Lambda _{\mu }^{*})\) . The main condition is that the parameter \(\beta (\mu )=\textrm{Var}_{\mu }(\Lambda _{\mu }^{*})/({\mathbb E}_{\mu }(\Lambda _{\mu }^{*}))^2\) should be small.