# Expected number of loops

There are 100 ropes in a bag. In each step, two rope ends are picked at random, tied together and put back into a bag. The process is repeated until there are no free ends.
What is the expected number of loops at the end of the process?

-

Suppose you start with $n$ ropes. You pick two free ends and tie them together:

• If you happened to pick two ends of the same rope, you've added one additional loop (which you can set aside, since you'll never pick it now on), and have $n-1$ ropes

• If you happened to pick ends of different ropes, you've added no loop, and effectively replaced the two ropes with a longer rope, so you have $n-1$ ropes in this case too.

Of the $\binom{2n}{2}$ ways of choosing two ends, $n$ of them result in the first case, so the first case has probability $\frac{n}{2n(2n-1)/2} = 1/(2n-1)$. So the expected number of loops you add in the first step, when you start with $n$ ropes, is $$\left(\frac{1}{2n-1}\right)1 + \left(1-\frac{1}{2n-1}\right)0 = \frac{1}{2n-1}.$$

After this, you start over with $n-1$ ropes. Since what happens in the first step and later are independent (and expectation is linear anyway), the expected number of loops is $$\frac{1}{2n-1} + \frac{1}{2n-3} + \dots + \frac{1}{3} + 1 = H_{2n} - \frac{H_n}{2}$$

In particular, for $n=100$, the answer is roughly $3.28$, which come to think of it seems surprisingly small for the number of loops!

-
For $n=2$, there are ${4 \choose 2} = 6$ ways to choose two ends, and only $2$ ways would give two loops. –  n0vakovic Aug 12 '10 at 2:29
Then answer for $n=2$ would be $\frac 43$ –  n0vakovic Aug 12 '10 at 2:42
In case anyone cares: Asymptotically, the quantity is $(\ln n)/2 + \ln 2 + \gamma/2 + O(1/n^2) \approx (\ln n)/2 + 0.98$. –  ShreevatsaR Aug 12 '10 at 6:55
@ShreevatsaR: What is $H_n$? –  Casebash Aug 12 '10 at 11:12
@ Casebash: I think that $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$. –  falagar Aug 12 '10 at 14:09