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?

  • 0
    http://mathproblems.info/images/prob1.pdf2011-01-21

4 Answers 4

6

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$.

  • 1
    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 $f$orm, liable to the objection, but another presentation is logically valid.2011-01-21
6

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} }}$.

4

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}. $

1

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}}$.