4
$\begingroup$

We place $n$ points on the unit circle uniformly and independently . What is the probability that their convex hull does not contain the origin?

I came up with this:

If the convex hull does not contain the origin then there is one point $x$ such that the next point $y$ in clockwise order forms an angle $xOy$ larger than $\pi$. Therefore we just need to calculate the probaility that this happens at least once, but notice that this cannot happen more than once . Suppose that $x_1,x_2,\dots x_n$ are the points that are to be placed independently, then the probability that the next point after $x_i$ forms an angle larger than $\pi$ is $\frac{1}{2^{n-1}}$. Therefore the probability the hull does not contain the origin is $\frac{n}{2^{n-1}}$

I would greatly appreciate a proof verification, alternative proofs and insight as to whether this can be generalized to higher dimensions, when there are $d+2$ points it is possible, as is shown here.

$\endgroup$
4
$\begingroup$

Here is another approach for the case of $n$ points on a circle. Choose one of the $n$ points arbitrarily and denote the angle from the center of the circle to that point as zero. Measure the angles of the other $n-1$ points relative to the chosen point, so their angles are uniformly distributed from $-\pi$ to $\pi$. The convex hull of the points fails to contain the origin if and only if the range of the angles (max minus min) is less than $\pi$. This is equivalent to drawing $n-1$ points from a Uniform(0,1) distribution with range less than $1/2$, which has probability $$n \; \left( \frac{1}{2} \right)^{n-1}$$ by Example 6c in Ross, A First Course in Probability, Seventh Edition, Section 6.6.

(The example in Ross shows that the probability that $n$ Uniform (0,1) random variables have a range less than $a$ is $n(1-a)a^{n-1}+a^n$. We have the case $a=1/2$, with $n$ replaced by $n-1$.)

$\endgroup$
  • $\begingroup$ Effective, and that should work also for a sphere in whichever dimension ! $\endgroup$ – G Cab Jul 20 '17 at 22:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.