100 Noodles Randomly Tied Together

Start with 100 separate noodles, each with 2 loose ends. Repeatedly pick two free ends uniformly at random and tie them together until no free ends remain. What is the expected number of closed loops formed?

The key idea

Suppose at some stage there are k open chains remaining. Then there are exactly 2k free ends.

Pick one free end. Among the remaining 2k - 1 possible ends you could tie it to, exactly one is the other end of the same chain, which closes a loop.

So at stage k, the probability that the next tie creates a new loop is:

P(create a loop when there are k chains) = 1 / (2k - 1)
k = 8
Free ends
16
Possible partners
15
Loop probability
1/15

Why we sum over k = 100, 99, ..., 1

Each tie reduces the number of open chains by exactly 1.

Tie two free ends Same chain Closes a loop k → k - 1 Different chains Merges two chains k → k - 1 Therefore we visit each k exactly once

Expected number of loops

Let L be the total number of loops formed. At each stage with k open chains, we get a new loop with probability 1 / (2k - 1).

By linearity of expectation:

k = 100
1/199
+
k = 99
1/197
+
⋯
+
k = 2
1/3
+
k = 1
1
E[L] = Σk=1100 1 / (2k - 1)
= 1 + 1/3 + 1/5 + ··· + 1/199
= H200 - (1/2)H100
E[L] ≈ 3.28434

Monte Carlo simulation

Click the button to simulate random pairings of all 200 ends and estimate the average number of loops.

Theoretical value: 3.28434

Final answer: the expected number of loops is 1 + 1/3 + 1/5 + ··· + 1/199 ≈ 3.28434.