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?
Asked
Active
Viewed 2.2k times
35
-
@Asinomas trying to find the origin of this problem despite it being in textbooks. Per Gil Kalai's blog Rados calls the problem "classical" but I do not know who started it. Any journal entry ? – New Student Sep 13 '22 at 20:44
-
I see it earliest in The College Math. J. (15, 1984, p. 347), Which mathematician dreamt this up ? – New Student Sep 13 '22 at 20:55
2 Answers
47
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!
ShreevatsaR
- 41,374
-
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 02:29
-
-
@n0vakovic: Oops, thanks for pointing that out. I've fixed it. It gives the right answer for n=2 now (1+1/3 = 4/3). – ShreevatsaR Aug 12 '10 at 02:54
-
7In 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 06:55
-
1
-
2@ Casebash: I think that $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$. – falagar Aug 12 '10 at 14:09
-
Just for completeness: yes, $H_n = 1 + \frac12 + \dots + \frac1n$ (harmonic number), and the asymptotics $(\ln n)/2 + 0.98$ mentioned above does indeed give about $3.28$ for $n=100$. – ShreevatsaR May 05 '14 at 17:07
-
@ShreevatsaR the second tern in ur comment above is $-ln2$ and not $ln2$ – AgnostMystic Dec 20 '17 at 17:10
-
@sajjadveeri No the comment is correct. From $$H_n = \ln n + \gamma + \frac{1}{2n} + O(1/n^2),$$ we have $$\begin{align}H_{2n} - \frac{H_n}{2} &= \left( \ln n + \ln 2 + \gamma + \frac{1}{4n} + O(1/n^2) \right) - \left( (\ln n)/2 + \gamma/2 + \frac{1}{4n} + O(1/n^2) \right) \ &= (\ln n)/2 + \ln 2 + \gamma/2 + O(1/n^2)\end{align}$$ which is what I wrote in the comment above. – ShreevatsaR Dec 20 '17 at 18:14
-
-
https://math.stackexchange.com/questions/2574788/recurrence-relation-arsing-in-a-standard-probability-puzzle – AgnostMystic Dec 20 '17 at 18:36
-
@ShreevatsaR if possible plz have a look at the above provided question with given link – AgnostMystic Dec 20 '17 at 18:38
0
This question is very old (over 10 years), but there is a simpler solution to explain, with the same general idea as the accepted answer.
Suppose, at a given moment, there are $n$ loose ends. Once you choose the first loose end, you have $n-1$ other loose ends to tie the rope to, each with probability $\frac{1}{n-1}$. Note that only one of the loose ends is on the same rope as the first loose end.
When $n = 200$ (remember $n$ is the number of loose ends and there are 2 loose ends per rope), the answer is simply $\frac{1}{200-1}+\frac{1}{200-3}+\dots+\frac{1}{200-199}$. We add, since $n$ is arbitrary for any given moment and specifies a different time of you looping the rope.
Sirswagger21
- 1,841