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!

  • $\begingroup$ For $n=2$, there are ${4 \choose 2} = 6$ ways to choose two ends, and only $2$ ways would give two loops. $\endgroup$ – n0vakovic Aug 12 '10 at 2:29
  • $\begingroup$ Then answer for $n=2$ would be $\frac 43$ $\endgroup$ – n0vakovic Aug 12 '10 at 2:42
  • 6
    $\begingroup$ 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$. $\endgroup$ – ShreevatsaR Aug 12 '10 at 6:55
  • 1
    $\begingroup$ @ShreevatsaR: What is $H_n$? $\endgroup$ – Casebash Aug 12 '10 at 11:12
  • 2
    $\begingroup$ @ Casebash: I think that $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$. $\endgroup$ – falagar Aug 12 '10 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.