Expected Number of Loops from Tying Rope Ends
You have $N$ ropes, each with two free ends, giving $2N$ free ends total. At each step you pick two free ends uniformly at random and tie them together. This reduces the number of free ends by 2, so after $N$ steps every end is tied and the process stops.
The result is some collection of closed loops. What is the expected number of loops formed? Express your answer as a closed-form sum and give its asymptotic behavior for large $N$.
Hints
- At each step, once you pick the first free end, ask: what is the probability the second end you pick closes a loop? There is exactly one "bad" partner among all remaining ends.
- Define an indicator variable $L_k$ for whether step $k$ forms a loop. Use linearity of expectation: $E[L] = \sum_k P(L_k = 1)$. At step $k$ there are $2(N-k+1)$ free ends remaining.
- The probability of closing a loop at step $k$ is $\frac{1}{2(N-k+1)-1}$. Sum these from $k=1$ to $N$ and reindex to get the partial sum of odd reciprocals $\sum_{j=1}^{N} \frac{1}{2j-1}$.
Worked Solution
How to Think About It: Each tying step either closes a loop (the two chosen ends belong to the same connected piece) or merges two pieces into one. The trick is that at every step, once you pick the first end, there is exactly one "dangerous" partner among the remaining free ends -- the other end of the *same* piece -- that would close a loop. So the probability of forming a loop at that step is just $1/(\text{remaining ends} - 1)$, independent of how the pieces are arranged. Linearity of expectation then turns the whole problem into a sum of these per-step probabilities. Before grinding through algebra, let's get a number.
Quick Estimate: Take $N = 10$ (so $20$ free ends). The expected number of loops is $$1 + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{9} + \frac{1}{11} + \frac{1}{13} + \frac{1}{15} + \frac{1}{17} + \frac{1}{19}.$$ Computing: $1 + 0.333 + 0.200 + 0.143 + 0.111 + 0.091 + 0.077 + 0.067 + 0.059 + 0.053 \approx 2.13$. So from $10$ ropes you expect only about $2$ loops. Because this odd-reciprocal sum grows like $\tfrac{1}{2}\ln N$, the count is logarithmically small: even $N = 1000$ ropes gives only $\approx \tfrac12\ln 1000 + \ln 2 + \tfrac{\gamma}{2} \approx 4.4$ loops.
Approach: Define an indicator for each step that forms a loop, sum their probabilities by linearity of expectation, recognize the partial sum of odd reciprocals, and read off the large-$N$ asymptotics by writing it in terms of harmonic numbers.
Formal Solution:
Label the steps $k = 1, 2, \ldots, N$. Just before step $k$, the number of free ends remaining is $2(N - k + 1)$. Pick one end. Among the other $2(N - k + 1) - 1$ free ends, exactly one is the opposite end of the *same* connected component, and tying to it closes a loop. (Every connected piece is a simple path, so the chosen end has exactly one same-piece partner -- regardless of how many pieces currently exist.) Hence the probability of closing a loop at step $k$ is $$p_k = \frac{1}{2(N - k + 1) - 1} = \frac{1}{2N - 2k + 1}.$$
Let $L_k$ be the indicator that step $k$ forms a loop and $L = \sum_k L_k$ the total. By linearity of expectation, $$E[L] = \sum_{k=1}^{N} E[L_k] = \sum_{k=1}^{N} \frac{1}{2N - 2k + 1}.$$ Substituting $j = N - k + 1$ (so $j$ runs from $N$ down to $1$), $$E[L] = \sum_{j=1}^{N} \frac{1}{2j - 1} = 1 + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{2N - 1},$$ the partial sum of the reciprocals of the odd numbers.
*Asymptotics.* Write the sum in terms of harmonic numbers $H_n = \sum_{m=1}^{n} 1/m$ by removing the even terms from $H_{2N}$: $$\sum_{j=1}^{N} \frac{1}{2j-1} = \sum_{m=1}^{2N} \frac{1}{m} - \sum_{m=1}^{N} \frac{1}{2m} = H_{2N} - \frac{1}{2} H_N.$$ Using $H_n = \ln n + \gamma + o(1)$, $$H_{2N} - \tfrac{1}{2} H_N = \bigl(\ln(2N) + \gamma\bigr) - \tfrac{1}{2}\bigl(\ln N + \gamma\bigr) + o(1) = \tfrac{1}{2}\ln N + \ln 2 + \tfrac{\gamma}{2} + o(1),$$ since $\ln(2N) = \ln N + \ln 2$ and $\gamma - \tfrac{\gamma}{2} = \tfrac{\gamma}{2}$. Here $\gamma \approx 0.5772$ is the Euler-Mascheroni constant, so the constant term is $\ln 2 + \gamma/2 \approx 0.693 + 0.289 = 0.982$. The leading order is $\tfrac12 \ln N$. (Beware the tempting but wrong shortcut $\tfrac12\ln(2N) + \tfrac{\gamma}{2}$: that equals $\tfrac12\ln N + \tfrac12\ln 2 + \tfrac{\gamma}{2}$, which has only *half* of $\ln 2$ and is off by $\tfrac12\ln 2 \approx 0.347$.)
Answer: The expected number of loops is $$E[L] = \sum_{j=1}^{N} \frac{1}{2j-1} = 1 + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{2N-1} = H_{2N} - \frac{1}{2}H_N = \frac{1}{2}\ln N + \ln 2 + \frac{\gamma}{2} + o(1),$$ so to leading order $E[L] \sim \tfrac{1}{2}\ln N$ -- the number of loops grows logarithmically in $N$. (For $N = 10$ the exact sum is $\approx 2.13$.)
Intuition
This problem is a beautiful application of linearity of expectation to a process that seems complicated at first glance. The topology of the connected components keeps changing as you tie ends together, but you don't need to track any of that. The only thing that matters at each step is: does the second end I pick belong to the same piece as the first? And that probability is always $1/(\text{remaining ends} - 1)$, because there is always exactly one partner that would close the loop. This "one dangerous partner" structure is what makes the problem clean.
The result -- that $N$ ropes produce only about $\frac{1}{2}\ln(2N)$ loops -- is surprisingly small. With 100 ropes you expect roughly 3 loops; with 1000, roughly 4. The reason is that most tying steps merge two separate chains rather than closing a loop, because the one loop-closing partner is drowned out by all the other free ends. This same indicator-variable technique shows up constantly in combinatorics and interview problems: whenever a complex random process produces discrete events (loops, records, cycles), define an indicator for each opportunity and sum the probabilities. You never need to track the full state.