I am aware of many forms of the solutions posted on SE. I am only interested in an approach using order statistics. The correct probability is $\frac{n}{2^{n-1}}$.

So n points are chosen randomly on a circle and I am interested in the probability that there exists a semi circle that covers all the points. We can think of it as unit circumference circle, and the sample of $n$ points can be modeled as $n$ iid standard uniform random variables, $U_1, ..., U_n$. Also let the two order statistics of this sample to be $U_\textrm{max}$ and $U_\textrm{min}$.

Here is my logic. In order for $n$ points to fall in a semicircle, $U_\textrm{max} - U_\textrm{min} \le 0.5$.

According to the First course in probability by Ross (sec. 6.6), $$\mathbb{P} \left(U_\textrm{max} - U_\textrm{min} \le x \right) = n (1 - x) x^{n-1} + x^n.$$

But using $x = 0.5$, I get probability of $\frac{n+1}{2^{n}}$, which is not the correct answer. In fact using the same distribution for order statistics of $U_1, ..., U_{n-1}$ leads to a correct answer according to this link, which says that I need to condition on $U_\textrm{max}$. But I don't get this idea. Why do we need to condition on the maximum value?

  • $\begingroup$ I do not agree with your logic. If e.g. $U_{min}=0.1$, $U_{max}=0.9$ and all other points take a value in $[0.1,0.2]$ then also a semicircle exists that contains all points. This in spite of $U_{max}-U_{min}=0.8>0.5$. $\endgroup$ – drhab Oct 12 '17 at 14:17
  • $\begingroup$ Oh, I see. But I am still not clear how conditioning on $U_\textrm{max}$ provides a correct logic. I think the link I provided says we can condition on $U_\textrm{max} = 1$. In this case, if the remaining points take values in [0.4, 0.7]. Among these $n-1$ points, let's say one takes 0.4 and another takes 0.7. In this case, $U_\textrm{max} - U_\textrm{min}\le 0.5 $ but we can't find a semicircle. $\endgroup$ – zcadqe Oct 12 '17 at 14:51
  • $\begingroup$ Are the U(i) you're generating the distance of these points from the center of the circle? If so, that's not a uniform-area distribution. However, I think I'm not understanding what you're doing. $\endgroup$ – barrycarter Oct 12 '17 at 15:35
  • $\begingroup$ $U_i$'s are the positions in the circumference. Since I am assuming the circumference is 1, the position is distributed Uniform(0, 1). $\endgroup$ – zcadqe Oct 12 '17 at 15:38

If we let one of the n points be 0.5, then the semi circle would never cross the zero point, because any semi circle crossing the zero point would not contains 0.5 . Furthermore, any semi circle not crossing the zero point would surely contains 0.5 .

The n points in a semi circle.

= The other n-1 points in a semi circle which contains 0.5

= The other n-1 points in a semi circle not cross zero.

= The other n-1 points satisfy Umax−Umin≤0.5

  • $\begingroup$ So I sample $n$ random points. Define the coordinate of the circle such that any one of the $n$ points to be at 0.5. Then remaining $n-1$ points have to satisfy $U_\textrm{max} - U_\textrm{min} \le 0.5$. Is this what you mean? But this depends on which of the $n$ points is chosen to be placed at 0.5. $\endgroup$ – zcadqe Oct 12 '17 at 21:20
  • $\begingroup$ It seems that I should condition on $U_\textrm{max} = 1$ such that the joint distribution of order statistics of remaining $n-1$ order statistics are distributed same as the order statistics of a sample of $n-1$ iid standard uniform variables. Then I can just plug in $n-1$ in place of $n$ in $\mathbb{P} \left(U_\textrm{max} - U_\textrm{min} \le x \right) = n (1 - x) x^{n-1} + x^n$ $\endgroup$ – zcadqe Oct 12 '17 at 21:22
  • $\begingroup$ We can randomly choose one point to be 0.5, it is not a condition. For example, we choose the first point. After the first point generated, we define the coordinate such that the first point is 0.5. Now the semi-circle requirement is equivalent to the following n-1 points satisfying Umax−Umin≤0.5. Making U1 = 0.5 will not affect the distribution of U2 to Un, they are still IID uniform between 0 and 1. Making Umax = 1 will change the distribution of the other points since it implies they are not the largest one. $\endgroup$ – Jeffrey Chen Oct 13 '17 at 1:11

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.