Estimating the probability that a given vector is in the convex hull of a random sample

Abstract

For a $d$-dimensional random vector $X$, let $p_{n,X}(\theta )$ be the probability that the convex hull of $n$ independent copies of $X$ contains a given point $\theta$. We provide several sharp inequalities regarding $p_{n,X}(\theta )$ and $N_X(\theta )$ denoting the smallest $n$ for which $p_{n,X}(\theta )\ge 1/2$. As a main result, we derive the totally general inequality $1/2\le {\alpha }_X(\theta )N_X(\theta )\le 3d+1$, where ${\alpha }_X(\theta )$ (a.k.a. the Tukey depth) is the minimum probability that $X$ is in a fixed closed halfspace containing the point $\theta$. We also show several applications of our general results: one is a moment-based bound on $N_X(\mathbb{E}[X])$, which is an important quantity in randomized approaches to cubature construction or measure reduction problem. Another application is the determination of the canonical convex body included in a random convex polytope given by independent copies of $X$, where our combinatorial approach allows us to generalize existing results in random matrix community significantly.

34 pages

References in corpus (4)

• Monte Carlo construction of cubature on Wiener space
• Monte Carlo Cubature Construction
• A Randomized Algorithm to Reduce the Support of Discrete Measures
• Revisiting the Approximate Carathéodory Problem via the Frank-Wolfe Algorithm

Cited by in corpus (4)

• General, efficient, and robust Hamiltonian engineering
• Positively Weighted Kernel Quadrature via Subsampling
• Hypercontractivity Meets Random Convex Hulls: Analysis of Randomized Multivariate Cubatures
• Markov Chain Approximations to Stochastic Differential Equations by Recombination on Lattice Trees