7
$\begingroup$

What's the probability that a n-sided polygon made from n distinct random points on circle contain the centre?

$\endgroup$
  • 4
    $\begingroup$ Is the polygon assumed to be convex? If so then all the points have to be on 1 half of the circumference of the cricle $\endgroup$ – Benson Lin Oct 9 '16 at 14:54
  • $\begingroup$ Yes it is convex. Can you explain a little more? $\endgroup$ – Oliver Blue Oct 9 '16 at 17:19
  • 1
    $\begingroup$ I just found that this question discussed the case of $n=3$, and this answer tackles the case of arbitrary $n$ as well. $\endgroup$ – MvG Oct 13 '16 at 8:56
  • $\begingroup$ Possible duplicate of Three points on a circle $\endgroup$ – hardmath Jan 29 '18 at 16:46
6
$\begingroup$

If you pick $n$ distinct points on the circle, then the convex hull of these will not contain the center of the circle if and only if there is a line through the center such that all $n$ points lie on the same side of that line. Or in other words, if they all fit into an angle of less than $\pi$.

Probability distributions

I'll start with some pretty algebraic derivation. If you find this too complicated, skip to the last paragraph for a more intuitive description. If you feel your intuition might easily misguide you, stick to the more formal approach.

Based on the observation above, I'd concentrate on the angle $\alpha_n$ spanned by $n$ points. This is a random variable, so we can describe it using a probability density function or a cumulative distribution function. Let's write $F_n$ for the cumulative distribution function (i.e. $F_n(x) = \Pr(\alpha_n\le x))$ and $f_n=\frac{\mathrm d}{\mathrm dx}F_n$ for the probability density function.

As a foundation, the case of a single point can be expressed using the Dirac delta “function”, since the angle spanned by a single point is always exactly zero. So you get $f_1(x)=\delta(x)$ and $F_1(x)=1$ for non-negative $x$.

Then comes a recursive part, which might be easier to understand by using the cumulative distribution function first. What's the probability the angle is no larger than $x$?

$$F_{n+1}(x) = \int_{y=0}^x \frac{y+2(x-y)}{2\pi}f_n(y) \;\mathrm dy$$

How can you read this? Well, the probability that for the $(n+1)$-th point the angle is at most $x$, you have to consider all the cases where the previous $n$ points were distributed over some smaller angle $y$, and then how likely it is that the new point will lie either within this angle $y$ or within the extra amount $(x-y)$ on either side of that angle $y$. This formulation does not take wrap-around into account correctly, so it will fail for $x>\pi$, but in the end all we need is $x\le\pi$ so we should be fine. Let's split that function, so it becomes easier to integrate.

$$F_{n+1}(x) = \frac{x}{\pi}\int_{y=0}^x f_n(y)\;\mathrm dy - \frac1{2\pi}\int_{y=0}^x y\,f_n(y)\;\mathrm dy$$

Towards a closed form

So what formulas do we have explicitely? I put some of these formulas into my computer algebra system (Sage). All of the following formulas assume $0\le x\le\pi$.

\begin{align*} F_1(x) &= 1 & f_1(x) &= \delta(x) \\ F_2(x) &= \frac x\pi & f_2(x) &= \frac 1\pi \\ F_3(x) &= \frac{3x^2}{4\pi^2} & f_3 &= \frac{3x}{2\pi^2} \\ F_4(x) &= \frac{x^3}{2\pi^3} & f_4 &= \frac{3x^2}{2\pi^3} \\ F_5(x) &= \frac{5x^4}{16\pi^4} & f_5 &= \frac{5x^3}{4\pi^3} \\ F_6(x) &= \frac{3x^5}{16\pi^5} & f_6 &= \frac{15x^4}{16\pi^5} \\ F_7(x) &= \frac{7x^6}{64\pi^6} & f_7 &= \frac{21x^5}{32\pi^6} \\ &\;\vdots &&\;\vdots \end{align*}

Now it's time to spot a pattern here, for the left column in particular. It's easy to see the exponents for $x$ and $\pi$ increasing with every step. You may also notice that the numbers in the denominator tend to be powers of two. Assuming this much, it's not hard to find a rule for the remaining integer in the numerator. You end up with

$$F_n(x) = n\left(\frac{x}{2\pi}\right)^{n-1}\qquad f_n(x) = \frac{n(n-1)}{2\pi}\left(\frac{x}{2\pi}\right)^{n-2} = \frac{n}{2\pi}F_{n-1}(x)$$

Now we need $F_n(\pi)$ since we want to know the probability that all the points span an angle less than $\pi$.

$$F_n(\pi) = n\left(\frac{\pi}{2\pi}\right)^{n-1} = 2^{1-n}n$$

You get the values

\begin{align*} F_1(\pi)&=\frac11=1\\ F_2(\pi)&=\frac{2}{2}=1\\ F_3(\pi)&=\frac{3}{4}\\ F_4(\pi)&=\frac{4}{8}=\frac12\\ F_5(\pi)&=\frac{5}{16}\\ F_6(\pi)&=\frac{6}{32}=\frac{3}{16}\\ &\;\vdots \end{align*}

Remember that this is the probability of all points lying in one half, i.e. of the convex hull not containing the center. The chances of containing the center are obviously the opposite of that.

$$p=1-F_n(\pi)=1-2^{1-n}n$$

More intuitive derivation

There is also a different, less formal but more intuitive way to derive this formula. If I give you an oriented line through the center, what's the chances of a random point lying on the positive side of that line? Obviously $1/2$. If I start with one point $A_1$, and define a line from that through the center, then the chances of the following $n-1$ points lying on the positive side of that line are $(1/2)^{n-1}$. But this depends on picking the right point as the starting point. If we have three points, then we need to check whether all points are on the positive side of either the line defined by $A_1$ or the line defined by $A_2$ or the line defined by $A_3$. At most one of these can be the case (because if $A_i$ is on the positive side of the line defined by $A_j$, then $A_j$ has to be on the negative side of the line defined by $A_i$). So we can simply add probabilities, which means three times $(1/2)^2$ in this case, or $n\cdot(1/2)^{n-1}=2^{1-n}n$ in general. Which is what we derived for $F_n(\pi)$. The probability of the polygon containing the center is again the complement of this, $1-2^{1-n}n$.

$\endgroup$
0
$\begingroup$

Consider a $n$ sided random polygon on a circle. Draw diameters parallel to the edges of polygon. Now each diameter will create $2$ semicircles. Thus, we have $2n$ semicircles.

For the center to be outside the polygon, we need to have all the $n$ vertices of polygon to lie on $1$ of these $2n$ semicircles. Also, probability of all $n$ vertices to lie on a given semicircle is $(1/2)^n$.

We select a semicircle from these $2n$ semicircles and place all our $n$ vertices on this semicircle. Therefore the probability of center to lie outside the polygon is: $$ P(\text{center outside polygon}) = \frac{2n}{2^n} $$ And the probability of center to lie inside the polygon is: $$ P(\text{center inside polygon}) = 1-\frac{n}{2^{n-1}} $$

$\endgroup$

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