# Probability that n points on a circle are in one semicircle

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

-
Have I taken too much of a simplistic view on the problem by thinking the probability is $\left$$\dfrac{1}{2}\right$$^n$? –  Noble. Mar 9 '13 at 1:10
@Noble: Yes, you have -- that's the probability that the points are all in one particular semicircle. –  joriki Mar 9 '13 at 1:10
@joriki I thought as much, it's a much more interesting problem then! –  Noble. Mar 9 '13 at 1:11
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. –  jay-sun Mar 9 '13 at 1:12
@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. –  Shu Xiao Li Mar 9 '13 at 1:14

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.

-
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? –  joriki Mar 9 '13 at 1:46
@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...) –  John Moeller Mar 9 '13 at 1:48
@joriki Since you've conditionally picked $i$, then you can arbitrarily choose the upper or lower halfplane as your "in the same semicircle" event. That's a coin-flip for each point, and they all have to be true, so it's $1/2^{n-1}$. (cont'd...) –  John Moeller Mar 9 '13 at 1:51
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 :-) –  joriki Mar 9 '13 at 2:02
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}$. –  sai Mar 9 '13 at 2:16

Find the largest angle gap, and number the points, say, clockwise such that that gap is between the last and first point. Then the probability density for the angle from the first to the last point to be $\phi\lt\pi$ is

$$n\frac1{2\pi}\left(\frac\phi{2\pi}\right)^{n-2}\;,$$

where the factor $n$ arises because we mapped $n$ numberings to one, $1/2\pi$ is the density for the angle between the first and last point, and $(\phi/2\pi)^{n-2}$ is the probability that the remaining $n-2$ points are between them. The integral

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

is the desired probability.

P.S.: Here's code that tests this result by simulations.

-
Could you elaborate the integral? –  Tunk-Fey Mar 29 at 17:47

See

http://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

http://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}}$

-

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

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

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

$$\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)=\frac n{2^{n-1}}\;.$$

-
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? –  sai Mar 9 '13 at 5:09
@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. –  joriki Mar 9 '13 at 8:23