7
$\begingroup$

Let $\{X_i\}_{0\leq i\leq\infty}$ be i.i.d. random vectors in $\mathbb{R^d}$. I would like to show that the probability of one point being in the convex hull of the others goes to one with the number of points: $$\tag{1}\label{claim} \lim_{n\to\infty}\mathbb{P}(X_0\in\mathrm{Conv}(X_1, \ldots, X_n)) = 1, $$ where the probability is taken with respect to the realization of $(X_0, \ldots, X_n)$.

While this seems intuitive, the following is a counterexample: in $\mathbb{R}^2$, if the $X_i$ are uniformly sampled from the circle $\mathbb{S}^1$, every sampled point almost surely creates a new vertex of the convex hull, and therefore $\mathbb{P}(X_0\in\mathrm{Conv}(X_1, \ldots, X_n)) = 0$.

If the $(X_i)$ are sampled from a continuous distribution, is my initial claim $\eqref{claim}$ true?

Improve this question
$\endgroup$
9
  • $\begingroup$ In your counterexample the distribution is not discrete. What do you mean by "continuous" distribution? $\endgroup$
    – Dieter Kadelka
    Aug 24, 2020 at 23:55
  • 1
    $\begingroup$ This question is somewhat relevant, as it shows that it is indeed the case for a square. I suppose that's intuitively clear but there are also some quantitative estimates that might be helpful more generally. The probability that the n+1-st point is contained in the convex hull should be 1 minus the expected value of the area of the n-th convex hull (for unit area regions) mathoverflow.net/questions/93099/… $\endgroup$
    – Gabe K
    Aug 25, 2020 at 0:03
  • $\begingroup$ Hello, I meant absolutely continuous w.r.t. the Lebesgue measure, i.e. having a density. $\endgroup$
    – Maxim
    Aug 25, 2020 at 0:03
  • $\begingroup$ Thank you @Gabe K, I found some related results for uniform or normal distributions, and your link indeed seems to show it for a uniform distribution on a square; I was however curious about more general results for arbitrary continuous distributions $\endgroup$
    – Maxim
    Aug 25, 2020 at 0:12
  • 7
    $\begingroup$ Yes, if the distribution has density, you are fine. The reason is pretty straightforward: with probability $1$, the probability that a fixed $X_0$ is in the convex hull of $X_{m+1},\dots,X_{m+d+1}$ is positive for every $m$ (if $f$ is the density, that is true for every Lebesgue point of $f$, say). Thus, the probability $p(X_0,n)$ that $X_0$ is not in the convex hull of $X_1,\dots,X_n$ goes to $0$ and the dominated convergence theorem finishes the story. The interesting question is the speed of convergence, but then we need some restrictions on the density to make it meaningful. $\endgroup$
    – fedja
    Aug 25, 2020 at 0:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.