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

• 成果类型: Article; Early Access
• 署名作者: Hayakawa, Satoshi; Lyons, Terry; Oberhauser, Harald
• 署名单位: University of Oxford
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-022-01186-1
• 发表日期: 2023
• 关键词: half-space depth; geometry; polytopes; cubature

摘要

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) >= 1/2. As a main result, we derive the totally general inequality 1/2 <= alpha(X)(theta)N-X(theta) <= 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(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.