Choose a random semicircle on a circle with uniform probability. Then choose another, and another and another until the circle is fully covered. What is the expected number of steps in this process?
I've been trying to use: $E(x)=1\cdot P(x=1) + 2\cdot P(x=2) + 3 \cdot P(x=3) ... + n\cdot P(x=n)$ and have found that the first two terms are zero.
I'm not 100% sure about $3 \cdot P(x=3)$ but I think $P(x=3)=1/4$ with similar reasoning as 3blue1brown in his video about points on a circle. https://www.youtube.com/watch?v=OkmNXy7er84
From there, I'm pretty stuck.
Firstly note that we can represent each semi-circle using its mid-point. Therefore, choosing a semi-circle uniformly at random is equivalent to choosing a point uniformly in the interval $[0, 2\pi)$. Consider a sample of $n$ such points given by $\{X_1, X_2, \dots, X_n\}$ and let $x_{\min}(n)$ and $x_{\max}(n)$ be the minimum and maximum values in this sample. Let us try to find the probability that this sample will not be able to cover the circle.
This sample will not be able to cover the circle if the semi-circles corresponding to $x_{\min}(n)$ and $x_{\max}(n)$ do not intersect. Since we are dealing with a circle, the interval of $[0, 2\pi)$ can be thought of as a periodic interval and the above condition can be written as $(2\pi + x_{\min}(n)) - x_{\max}(n) > \pi$ which is equivalent to $x_{\max}(n) - x_{\min}(n) < \pi$.
To compute the probability of the above event, first let us compute $\Pr(x_{\max}(n) < a + \pi | x_{\min}(n) = a )$ for some $a \in [0, 2\pi)$. Since the distribution is uniform, this evaulates to $\displaystyle \left(\frac{\pi}{(2\pi - a)}\right)^{n - 1}$. The exponent is $n - 1$ because only $n-1$ points remain after setting the minimum one equal to $a$. Using the distribution of the minimum of $n$ uniformly distributed random variables, one can write \begin{align} \Pr(x_{\max}(n) - x_{\min}(n) < \pi) & = n \int_{0}^{2\pi} \left(\frac{\pi}{(2\pi - a)}\right)^{n - 1} \left(1 - \frac{a}{2\pi}\right)^{n-1} \frac{da}{2 \pi} \\ & = \frac{n}{2^{n-1}} \end{align}
If $T$ denotes the random number of steps, then $P(T> n) = \Pr(x_{\max}(n) - x_{\min}(n) < \pi) = \frac{n}{2^{n-1}}$. Using the formula, $\displaystyle \mathbb{E}[T] = \sum_{n = 0}^{\infty} \Pr(T > n)$, you can compute the required value.