5
$\begingroup$

Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle?

$\endgroup$
6
$\begingroup$

Suppose the points are $x_1,\ldots,x_n$. If the points are indeed contained in a semicircle, then we can define a "leftmost" point, i.e. a point $x_i$ such that $x_j \in [x_i, x_i+\pi)$ (addition is modulo $2\pi$). There is only one leftmost point, and the probability that $x_i$ is leftmost is $1/2^{n-1}$, since the probability that $x_j \in [x_i, x_i+\pi)$ is $1/2$. Since there are $n$ possible leftmost points, we get $n/2^{n-1}$.

Now generalize the argument to $d$ dimensions.

Edit: The argument generalizes to show that the probability that all points lie in an $\alpha$-section of the circle is $n\alpha^{n-1}$ for $\alpha \leq 1/2$. You can challenge yourself by thinking about the case $\alpha > 1/2$.

$\endgroup$
  • $\begingroup$ I was once told the above approach confounds ex ante and ex post probabilities. Was that bu-, rubbish ? $\endgroup$ – Benji Jan 21 '11 at 0:46
  • 1
    $\begingroup$ What you're doing more formally is calculating the probabilities of the disjoint events "$x_j \in [x_i,x_i+\pi)"$ for all $j \neq i$", which together cover the event "all points belong to a semicircle". To calculate the probability of any particular event, you condition on the value of $x_i$; whatever that is, you get $2^{-n}$, so that in total the probability of the event is $2^{-n}$. $\endgroup$ – Yuval Filmus Jan 21 '11 at 0:58
  • 1
    $\begingroup$ You should ask whoever told you that what their objection exactly is, and then try to see whether it's valid or not; it can be that one can give this argument in a wrong form, liable to the objection, but another presentation is logically valid. $\endgroup$ – Yuval Filmus Jan 21 '11 at 0:59
6
$\begingroup$

Since the problem is trivial for $n \leq 2$, suppose that $n \geq 3$. Without loss of generality, assume that the circle has circumference one and that the first of $n$ points is located on its top (the next $n-1$ points are drawn independently and uniformly on the circumference).
Then, it is readily seen that the problem is equivalent to the following one. Let $U_1,\ldots,U_{n-1}$ be i.i.d. uniform rv's on $[0,1]$. What is the probability that $U_{\max} - U_{\min} \leq 1/2$?

As is well known (cf. this, for example) and easy to show (simple exercise in order statistics, upon conditioning on $U_{\max}$), $$ {\rm P}(U_{\rm max} - U_{\rm min} \leq x) = (n-1)x^{n - 2} - (n - 2)x^{n-1}, \;\; x \in [0,1]. $$ Substituting $x=1/2$ gives the desired result of $\frac{n}{{2^{n - 1} }}$.

$\endgroup$
4
$\begingroup$

Let $dp(\theta_1, \theta_2)$ be the probability density that $[\theta_1, \theta_2]$ is a minimal covering arc (i.e., it contains all $n$ points, and any proper sub-arc excludes at least one point). This is given by $$ dp(\theta_1, \theta_2) = n(n-1)\left(\frac{\theta_2 - \theta_1}{2\pi}\right)^{n-2} \frac{d\theta_1}{2\pi} \frac{d\theta_2}{2\pi}, $$ since one point must be at each end of the arc and the remaining $n-2$ must be in its interior. The probability density that the length of the unique minimal covering arc is $\theta$ is therefore $$ dp(\theta) = n(n-1)\left(\frac{\theta}{2\pi}\right)^{n-2}\frac{d\theta}{2\pi} $$ for $\theta \le \pi$. (Note that for $\theta > \pi$ there may be more than one minimal covering arc; for example, if all the points cluster around $0$, $2\pi/3$, and $4\pi/3$, there will be three distinct minimal covering arcs, each of length approximately $4\pi/3$.) The probability that all $n$ points lie in some arc of length $\Theta \le \pi$ is therefore $$ P(\Theta) = \int_{0}^{\theta} dp(\theta) = n\left(\frac{\Theta}{2\pi}\right)^{n-1}. $$

$\endgroup$
1
$\begingroup$

Lets consider n-dimensional cube $[0; 1) ^ n$. Let $M \in [0; 1)^n $ be a set of all "good" points, i.e. such $(x_1, \dots, x_n)$ that lie in some semicircle of $[0; 1)$ circle. Answer will be volume of $M$. Note that set of points that lie in $[0; \frac{1}{2})$ semicircle can be represented as $[0; \frac{1}{2})^n$. Hence, M is union of all sets $[a, a + \frac{1}{2})^n$ modulo $[0; 1)^n$ (modulo to take into account circle structure and cases when $a > \frac{1}{2}$). M can be represented as $Q$ + $t(1, 1, \dots, 1)$, where $t \in [0; 1)$ and Q denotes all points in $[0; \frac{1}{2})^n$ with one or more zero coordinates ($(0, y_2, y_3, \dots , y_n)$, $(y_1, 0, y_3, \dots y_n)$ etc.) Therefore, volume of M is $S \sqrt{n}$, $S$ is area of projection Q on plane orthogonal to $(1, \dots, 1)$, $\sqrt{n}$ is length of $(1, \dots, 1)$. There are $n$ equal surfaces of cube around point $(0, \dots, 0)$ , and area of each is $(\frac{1}{2})^{n - 1} \frac{1}{\sqrt{n}}$, so answer is $\frac{n}{2^{n - 1}}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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