3

A box contains $n$ ropes. You randomly tie up any two loose ends until there is none left. Let $X$ be the number of loops. What is $E(X)$?

I've only been able to solve the problem when the number of rope is defined (say, $n=2$ or $n=3$), but I approached the solution by calculating the probability of each possible $X$ value and calculating the expectation by the weighted average of the probability. I feel like there should be an easier solution to get to the general case.

Molly Pearson
  • 33
  • 1
  • 3

2 Answers2

5

When you tie the first pair of ends, you either make a loop or do not. You make a loop with probability $\frac 1{2n-1}$ In either case you are left with a box with $n-1$ ropes in it, so the expected number of loops from $n$ ropes is $\frac 1{2n-1}$ plus the expected number from $n-1$ ropes. The expected number then becomes $$\sum_{i=1}^n\frac 1{2i-1}$$

Ross Millikan
  • 374,822
  • 2
    In case this helps the reader: the probability of $\frac{1}{2n-1}$ comes from having $\binom{2n}{2}$ possible pairs to tie together, only $n$ of which lead to a loop (selecting both ends from the same rope). Hence the probability of making a loop is $\frac{n}{\binom{2n}{2}}=\frac{n}{(2n)(2n-1)/2}=\frac{1}{2n-1}$. – Christian Bueno Jan 26 '16 at 03:35
  • 5
    @ChristianBueno: more simply, you pick the first end at random, and it will not determine whether you have a loop. There are $2n-1$ ends left to pick the second and one of them forms a loop. – Ross Millikan Jan 26 '16 at 03:41
2

For $k=1$ to $n$, define random variable $X_k$ by $X_k=1$ if at Stage $k$ we form a loop, and by $X_k=0$ otherwise. Then the number $Y$ of loops is given by $Y=X_1+\cdots+X_n$.

By the linearity of expectation, we have $$E(Y)=E(X_1)+E(X_2)+\cdots +E(X_n).$$ At stage $k$, we have $2n-2k+2$ free ends. There are $\binom{2n-2k+2}{2}$ ways to pick two free ends. Of these, $n-k+1$ pairs will give us a loop. It follows that $$E(X_k)=\Pr(X_k=1)=\frac{n-k+1}{\binom{2n-2k+2}{2}}=\frac{1}{2n-2k+1}.$$ Add up, $k=1$ to $n$. There is no closed form, but the answer can be expressed in terms of harmonic numbers.

André Nicolas
  • 507,029