[Math] Expected Value and Loops

probability

I have the following question:

Imagine you have $N$ pieces of rope in a bucket. You reach in and grab one end-piece, then reach in and grab another end-piece, and tie those two together. What is the expected value of the number of loops in the bucket?

In order to have a loop you need two pieces of rope. So would the answer be:

$$ \sum_{i=1}^{n} i \cdot p(i) $$

where $p(i)$ the number of loops would depend on having an even number of ropes?

Best Answer

I will assume for this answer that there are $N$ entirely unattached pieces of rope in the bucket, and that a loop may consist of any number of pieces of rope attached in a closed chain.

We can write a recurrence for this expected value, as follows. Suppose the expected number of loops for $N-1$ pieces of rope is denoted $L(N-1)$. Consider the bucket of $N$ pieces of rope; there are thus $2N$ rope ends.

Pick an end of rope. Of the remaining $2N-1$ ends of rope, only one end creates a loop—the other end of the same piece of rope; there are then $N-1$ untied pieces of rope. The rest of the time, two separate pieces of rope are tied together, and there are effectively $N-1$ untied pieces of rope. The recurrence is therefore

$$ L(N) = \frac{1}{2N-1}+L(N-1) $$

Clearly, $L(1) = 1$, so

$$ L(N) = \sum_{k=1}^N \frac{1}{2k-1} = H_{2N}-\frac{H_N}{2} $$

where $H_k$ is the $k$th harmonic number.

ETA: Since $H_k \doteq \gamma+\ln k$ for large-ish $k$, where $\gamma \doteq 0.57722$ is the Euler-Mascheroni constant, we have

$$ L(N) \doteq \ln 2N - \frac{\ln N}{2} = \ln 2\sqrt{N} $$