Consider a loop with a length of 1, then randomly select a continuous part on this loop with a length of 0.5 and cover it. Repeat this process for k times until the loop was fully covered. Find the mathematical expectation of k.
My personal thoughts are as belows.
I personally have considered the question for quite some time. Tried to discrete the question by considering the chance of the loop fully covered with 1,2,3 times of covering, thinking of adding them up to get the expectation of k later. When k=1 and k=2, obviously the chance is 0, when k=3 the chance can be displayed by an image. Take the starting point of the first covered line segment as the reference point, and respectively take the second and the third covered line segment as x and y on a coordinate plane. We can plot the image as below.img1
As we craft through all possibilities, we can have this image. The shadowed area expresses when x land on these specific points, where should y be to satisfy the requirements. by calculating the area of the shadow, we can arrive at the conclusion that when k=3, the chance of the loop fully covered is 0.25
But when I started up at the condition of k=4, it involves higher dimension of plotting which is way more difficult, and I became incapable of thinking clearly on that problem. Can anyone provide a fresh perspective on this problem? Or is there any elegant solution?
For simplicity, consider a circle $\mathbb{S}^1$ of unit circumference, and cover it by random arcs of lenght $\frac{1}{2}$. The probability of $k\geq 1$ segments not covering all of $\mathbb{S}^1$ is $\frac{2k}{2^k}$.
We prove this by exploiting a symmetry of the problem: For any diameter of the circle, the arcs on either side are chosen with equal probability. We can thus first choose $k$ diameters and then, for each diameter, one of the two arcs into which it dissects $\mathbb{S}^1$. Almost surely, all $k$ diameters are distinct and thus cut $\mathbb{S}^1$ into $2k$ pieces. For a particular piece to not be covered by any arc, each of the $k$ arcs has to fall on the side not containing the piece (probability $2^k$). Since at most one of the pieces won't be covered, these events are disjoint and the total probability of the loop not to be covered $k$ arcs is $\frac{2k}{2^k}$.
The probability that the $(n+1)^{st}$ arc finally covers the loop is thus $\sum_{j=1}^{2n} \frac{1}{2^n}\frac{1-2l_1}{2}$. This is the product of the chance that the first $n$ arcs fail to cover one of the $2k$ pieces, and the chance that the final arc covers this piece (of length $l_j$), which is half the chance that the relevant diameter does not intersect the piece. This sum evaluates to $\frac{n-1}{2^{n}}$, hence the expected value of $n+1$ is $\sum_{n=1}^\infty \frac{(n+1)(n-1)}{2^{n}}$.
Let $f(x) = \sum_{n=1}^\infty (n+1)(n-1)x^n$. We have $$f(x) = \frac{d}{dx}\left(\sum_{n=1}^\infty (n-1)x^{n+1}\right) = \frac{d}{dx}\left(x^3\sum_{n=0}^\infty nx^{n-1}\right) = \frac{d}{dx}\left(x^3 \frac{d}{dx}\frac{1}{1-x} \right) \\ = \frac{d}{dx}\left(\frac{x^3}{(1-x)^2} \right) = \left(\frac{3}{x} + \frac{2}{1-x}\right)\frac{x^3}{(1-x)^2}.$$ Therefore, $f(\frac{1}{2}) = 5$. The expected value of the number of arcs needed to cover a loop is, amazingly, $5$.