This week’s Riddler problem is short and sweet:
If N points are generated at random places on the perimeter of a circle, what is the probability that you can pick a diameter such that all of those points are on only one side of the newly halved circle?
Here is my solution:
[Show Solution]
Label the points $\{1,2,\dots,N\}$. Given one of the points $i$ on the perimeter, we’ll call this point a clockwise split if all remaining points lie on the semi-circle starting from point $i$ in the clockwise direction. For example, in the figure below, Point 1 is not a clockwise split because Point 4 is outside the semicircle that starts at Point 1. We can also observe that Points 2 and 3 are not clockwise splits, but Point 4 is.
If all $N$ points are located on the same half-circle, then exactly one of these points will be a clockwise split (almost surely). Meanwhile, if there exists no diameter that puts all the points on the same half-circle, then no point will be a clockwise split. Define the random variable $X_i$ as follows.
\[
X_i = \begin{cases}1 & \text{Point }i\text{ is a clockwise split} \\ 0 & \text{otherwise}\end{cases}
\]Based on the observations above, the probability that there exists a diameter such that all the points are one side of the newly halved circle (let’s call this probability $P$) is given by:
\begin{align}
P &= \text{Prob}(\text{one of the points is a clockwise split}) \\
&= \text{Expected total number of clockwise splits} \\
&= \mathbb{E}\left( \sum_{i=1}^N X_i \right) \\
&= \sum_{i=1}^N \mathbb{E}(X_i)
\end{align}By symmetry, $\mathbb{E}(X_i)$ is the same for each $i$, and it’s equal to $\frac{1}{2^{N-1}}$, since once we’ve fixed point $i$, there are $N-1$ remaining points and each one has a probability of $\tfrac{1}{2}$ of being in the correct half of the circle. Therefore, the probability we seek is:
$\displaystyle
P = \frac{N}{2^{N-1}}
$
The last step in the derivation relies on linearity of expectation. Even though the $X_i$’s are not independent (far from it, since at most one of them can be $1$), linearity of expectation still holds, and it allows us to make short work of what would otherwise be a complicated calculation.
Note: There are many ways to solve this problem. In fact, Derek commented that a previous Riddler problem is quite similar to this one, and in his comments suggested two different ways of solving the present problem, one year ago!
The generalization to portions of the circle larger than a semi-circle is pretty interesting!
That works. Why the digression through expectation, though? The probabilty of a disjunction of exclusive events is the sum.
Very elegant!! I did it with conditional probabilities and it was a mess (with the same result)