Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 13 down vote accepted

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!

share|improve this answer
    
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
2  
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
1  
@ShreevatsaR: What is $H_n$? –  Casebash Aug 12 '10 at 11:12
2  
@ Casebash: I think that $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$. –  falagar Aug 12 '10 at 14:09
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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