48
$\begingroup$

Choose n points randomly from a circle, how to calculate the probability that all the points are in one semicircle? Any hint is appreciated.

$\endgroup$
8
  • 2
    $\begingroup$ Have I taken too much of a simplistic view on the problem by thinking the probability is $\left\(\dfrac{1}{2}\right\)^n$? $\endgroup$
    – Noble.
    Commented Mar 9, 2013 at 1:10
  • 4
    $\begingroup$ @Noble: Yes, you have -- that's the probability that the points are all in one particular semicircle. $\endgroup$
    – joriki
    Commented Mar 9, 2013 at 1:10
  • 1
    $\begingroup$ @joriki I thought as much, it's a much more interesting problem then! $\endgroup$
    – Noble.
    Commented Mar 9, 2013 at 1:11
  • 1
    $\begingroup$ Hint: Start with a point randomly on the circle and draw a diameter from that point. All you got to do now is ensure that rest of the $n-1$ points lie on the same side of the diameter (i.e., on a semi-circle). You can place the $n-1$ points using a coin toss. $\endgroup$
    – jay-sun
    Commented Mar 9, 2013 at 1:12
  • 2
    $\begingroup$ @jay-sun I dont think this is the correct way, three points could still be in one semicircle even if the last two are on two different sides of the diameter joining the first point and the center. $\endgroup$
    – NECing
    Commented Mar 9, 2013 at 1:14

6 Answers 6

44
$\begingroup$

A variation on @joriki's answer (and edited with help from @joriki):

Suppose that point $i$ has angle $0$ (angle is arbitrary in this problem) -- essentially this is the event that point $i$ is the "first" or "leading" point in the semicircle. Then we want the event that all of the points are in the same semicircle -- i.e., that the remaining points end up all in the upper halfplane.

That's a coin-flip for each remaining point, so you end up with $1/2^{n-1}$. There's $n$ points, and the event that any point $i$ is the "leading" point is disjoint from the event that any other point $j$ is, so the final probability is $n/2^{n-1}$ (i.e. we can just add them up).

A sanity check for this answer is to notice that if you have either one or two points, then the probability must be 1, which is true in both cases.

$\endgroup$
14
  • 2
    $\begingroup$ I don't understand this answer. (Strange, since you think it's a variation on mine. :-) I presume the "if" in "if the remaining points end up all in the upper halfplane" is intended to mean "if and only if"? If so, why is that? And why is the final probability simply the number of points times this one probability you calculated? $\endgroup$
    – joriki
    Commented Mar 9, 2013 at 1:46
  • 1
    $\begingroup$ @joriki Basically I'm breaking this down into conditional probabilities. The angle around the circle is just an arbitrary assignment, so conditionally pick $i$. All of these conditional probabilities are going to be identical, and there's $n$ of them, so whatever that probability is, multiply it by $n$. That's the easy part. (cont'd...) $\endgroup$ Commented Mar 9, 2013 at 1:48
  • 18
    $\begingroup$ I think I see now -- I find it rather confusingly formulated, but if I understand correctly, you mean something like this: The probability of the remaining $n-1$ points being in the semicircle clockwise of a given point is $1/2^{n-1}$. These $n$ events (one for each given point) are disjoint, and exactly one of them has to occur for the points to lie in a semicircle; thus the desired probability is their sum. That's a nice argument :-) $\endgroup$
    – joriki
    Commented Mar 9, 2013 at 2:02
  • 4
    $\begingroup$ There's a slight variation of this answer that uses the inherent symmetry: instead of picking $n$ points at random, pick $n$ random diameters of the circle and pick the $n$ points by randomly picking one of the 2 poles of each diameter. By essentially the same argument, you have the probability given by $(2n)/2^n=n/2^{n-1}$. $\endgroup$
    – sai
    Commented Mar 9, 2013 at 2:16
  • 1
    $\begingroup$ @Arrow: The events mentioned in the sentence before that: "the remaining $n−1$ points being in the semicircle clockwise of a given point". That defines one event per point, so $n$ events in all, and they're disjoint. $\endgroup$
    – joriki
    Commented Apr 5, 2016 at 15:08
13
$\begingroup$

Here's another way to do this:

Divide the circle into $2k$ equal sectors. There are $2k$ contiguous stretches of $k$ sectors each that form a semicircle, and $2k$ slightly shorter contiguous stretches of $k-1$ sectors that almost form a semicircle. The number of the semicircles containing all the points minus the number of slightly shorter stretches containing all the points is $1$ if the points are contained in at least one of the semicircles and $0$ otherwise; that is, it's the indicator variable for the points all being contained in at least one of the semicircles. The probability of an event is the expected value of its indicator variable, which in this case is

$$2k\left(\frac k{2k}\right)^n-2k\left(\frac{k-1}{2k}\right)^n=\frac k{2^{n-1}}\left(1-\left(1-\frac1k\right)^n\right)\;.$$

The limit $k\to\infty$ yields the desired probability:

$$ \lim_{k\to\infty}\frac k{2^{n-1}}\left(1-\left(1-\frac1k\right)^n\right)=\lim_{k\to\infty}\frac k{2^{n-1}}\cdot\frac nk=\frac n{2^{n-1}}\;. $$

$\endgroup$
8
  • $\begingroup$ Why is $ \lim_{k\to\infty}k2^{-n}\left(1-\left(1-\frac2k\right)^n\right)=\lim_{k\to\infty}k2^{-n}\left(\frac{2n}k\right)$ true? $\endgroup$
    – sai
    Commented Mar 9, 2013 at 5:09
  • 2
    $\begingroup$ @sai: Apply the binomial theorem to the $n$-th power -- the first term cancels the $1$, the second term yields $2n/k$ and the remaining terms have more than one inverse power of $k$ and thus go to zero as $k\to\infty$. Note that $n$ is fixed; it's not a question of taking $n$ and $k$ to infinity simultaneously; we're just adding a finite number of terms, so the standard rules for adding convergent sequences apply. $\endgroup$
    – joriki
    Commented Mar 9, 2013 at 8:23
  • $\begingroup$ sorry for pinging you, but can we use this method for a quadrant (1/4 circle)? $\endgroup$ Commented Jun 30, 2016 at 16:54
  • 1
    $\begingroup$ In the first equation mentioned in the answer, shouldn't we get 1 - 1/k, instead of 1 - 2/k on the RHS? $\endgroup$
    – user10
    Commented Aug 8, 2016 at 18:32
  • $\begingroup$ It seems to me that there are two errors (that happen to given the correct limit) in the first equation. I think should be $$2k\left(\frac k{2k}\right)^n-2k\left(\frac{k-1}{2k}\right)^n= \frac{k}{2^{n-1}}\left(1-\left(1-\frac1k\right)^n\right) \to \frac{n}{2^{n-1}}$$ $\endgroup$
    – leonbloy
    Commented Jan 6, 2017 at 1:47
11
$\begingroup$

See

https://mathoverflow.net/questions/33112/estimate-probability-0-is-in-the-convex-hull-of-n-random-points

for the general problem (when the points have any distribution that is invariant w.r.t. rotation about the origin) and

https://mathoverflow.net/questions/2014/if-you-break-a-stick-at-two-points-chosen-uniformly-the-probability-the-three-re/2016#2016

for a nice application.

As a curiosity, this answer can be expressed as a product of sines:

Prove that $\prod_{k=1}^{n-1}\sin\frac{k \pi}{n} = \frac{n}{2^{n-1}}$

$\endgroup$
3
  • $\begingroup$ "when the points have any distribution that is invariant w.r.t. rotation about the origin", actually the theorem proved by J. G. Wendel pointed out in your first link is more general. We only need a distribution symmetric with respect to $0$ and the result apply to any dimension. $\endgroup$ Commented May 9, 2014 at 19:06
  • $\begingroup$ Also, I think it would be nice if you quote directly in your answer the theorem of Wendel (just in order people looking at the present question don't miss the fact this is a specific case of a much more general "classical" result) $\endgroup$ Commented May 9, 2014 at 19:31
  • $\begingroup$ @sai one one reason it can be expressed as a product of sines is that if you ask for the number of spanning trees on a cycle, which is just $n$, (for the same reason that the numerator is $n$ in this problem because there are $n$ points) then the matrix-tree theorem gives the determinant in terms of eigenvalues of the Adjacency matrix on a cycle which are directly related to those sines. I guess you are suggesting there is an iterative way to do it different than Josephine Moeller where the product arises naturally ... interesting. $\endgroup$ Commented Feb 1, 2022 at 12:07
6
$\begingroup$

Bull, 1948, Mathematical Gazette, Vol 32 No 299 (Dec), pp87-88 solves this problem in the context of the broken stick problem (he uses polytopes and relative volumes in his argument). Rushton, 1949, Mathematical Gazette, Vol 33 No 306 (May), pp286-288 points out that the problem can be re-stated in terms of placing points at random on the circumference of a circle. Ruston's answer is the clearest I have seen. Place $n$ points randomly on the circumference. Label them $X_1, X_2, ..., X_n$. Open up the circle at $X_n$ and produce a straight line. Label the line $OX_n$ (where $O$ is the part of the circle previously immediately adjacent to $X_n$). There are $n$ line segments: $OX_1, X_1X_2, ..., X_{n-1}X_n$. Each segment is equally likely to be longer than half the length of $OX_n$ (and thus correspond to greater than a semi-circle of the orginal circle). The probability that the first segment fulfils this condition is the probability that the remaining $n-1$ points lie upon the second half of the line $OX_n$. That is $(\frac{1}{2})^{(n-1)}$. The probability that there is one segment (note there can be at most one) greater than half the length of the circumference is the sum of the probabilities that each particular segment could be so (because these are mutually exclusive): $n(\frac{1}{2})^{(n-1)}$. So, the favorable probability is $1 -n(\frac{1}{2})^{(n-1)}$.

$\endgroup$
1
  • $\begingroup$ The answer should be n(1/2)^(n-1). 1−𝑛(1/2)^(𝑛−1) is interpreted as "not all points are in the same semi-circle" . $\endgroup$
    – S.B.
    Commented Jan 13, 2023 at 16:47
3
$\begingroup$

Another simpler approach,

1) Randomly pick $1$ out of $n$ points and call it $A$ : $\binom n1$ ways

2) Starting from $A$, mark another point $B$ on circumference, such that $length(AB) = \frac12(Cirumference)$ [so that $AB$ and $BA$ are two semi-circles]

3) Now out of remaining $(n-1)$ points, each point can lie on either $AB$ or $BA$ with probability $\frac12$

4) For ALL the remaining $(n-1)$ points to lie on EITHER $AB$ OR $BA$ (i.e., all $(n-1)$ lie on same semi-circle), the joint probability is $\frac12*\frac12 ...(n-1) times$ $=$ $(\frac12)^{(n-1)}$

Since #1 above (randomly picking $A$) is an independent event, $\therefore$ $(\frac12)^{(n-1)}$ (expression in #4) will add $\binom n1$ times

$\implies$ Required probability is $\binom n1(\frac12)^{(n-1)}$ $=$ $n(\frac12)^{(n-1)}$

$\endgroup$
4
  • $\begingroup$ @joriki, Perhaps this would be simpler to understand. I have tried to put the same idea as John Moeller in a different way. $\endgroup$
    – Rahul
    Commented May 25, 2016 at 16:05
  • 2
    $\begingroup$ logic has flaws at step 4, as it should be $(1/2)^{n-2}$ $\endgroup$
    – fizis
    Commented Dec 2, 2016 at 9:23
  • 1
    $\begingroup$ @fizis You are right, he is missing a factor of 2 here. $\endgroup$
    – James LT
    Commented Apr 22, 2018 at 16:15
  • $\begingroup$ Perhaps the intended argument is as follows. If all $n$ chosen points lie on one semicircle, call the most anticlockwise chosen point $A$, and the diametrically opposite point $B$. Any of the $n$ chosen points can be $A$, and for success each of the other $n-1$ must lie on the clockwise arc $AB$. Hence $n/2^{n-1}$. $\endgroup$
    – Rosie F
    Commented Aug 12, 2023 at 5:55
1
$\begingroup$

Here is a brute force solution. We let $n > 2$. Let $X_1, \ldots, X_n$ be uniform random variables into the circle of circumference $1$, $S^1/2\pi$. We know that every configuration of $n$ points has two points on the outside. So now we calculate the probability $$ p_{i,j} = \mathbb{P}(\text{$X_1,\ldots,X_n$ lie in a semicircle} \wedge \text{$X_i,X_j$ are on the outside}) $$ where $\wedge$ means that the two events happen at the same time. Let us call the above event $E_{i,j}$. Let $\alpha(X_i,X_j)$ be the shorter distance of the two distances possible between $X_i$ and $X_j$. Now since the $X_i$ are independent, the variable $X_k$ is independent of $\alpha(X_i,X_j)$ for $k \neq i,j$. Thus we must have that $$ \mathbb{P}(E_{i,j}|\alpha(X_i,X_j) = \alpha_0) = \alpha_0^{n-2} $$ because the probability of $X_k$ landing in the shorter arc between $X_i$ and $X_j$ is just $\alpha(X_i,X_j)$. Note that $\alpha(X_i,X_j)$ is uniformly distributed on $[0,1/2]$. So we have that $$ \begin{aligned} p_{i,j} &= 2 \int_0^{1/2} \mathbb{P}(E_{i,j} | \alpha(X_i,X_j) = \lambda)d\lambda \\ &= 2\int_0^{1/2} \lambda^{n-2} d\lambda \\ &= \frac{2}{(n-1)2^{n-1}} \end{aligned} $$ Now we note that the probability these points lie in a semicircle is just $$ p = \sum_{\{i,j\} \subset \{1,\ldots,n\}} p_{i,j} = \frac{n(n-1)}{2}p_{1,2} $$ which gives us $$p = n/2^{n-1}$$

$\endgroup$
1
  • $\begingroup$ If you think this solution is bad/wrong please comment why. I don't get why you are downvoting it $\endgroup$ Commented Aug 26, 2023 at 0:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .