Connecting Noodles

A bowl holds 100 noodles, so 200 loose ends. You repeatedly grab two loose ends uniformly at random and tie them together, until no loose ends are left. How many loops do you expect to have formed?

Reveal solutionHide solution

#One tie at a time

Suppose $2k$ loose ends remain. Pick up any one end. Among the other $2k-1$ ends, exactly one belongs to the same strand, and tying to it closes a loop while every other choice just lengthens a strand. So this tie closes a loop with probability

\frac{1}{2k-1}, \tag{1}

whatever happened on earlier ties. Each tie removes two ends, so the ties run through $2k = 200, 198, \dots, 2$ , that is $k = 100$ down to $1$ .

#Sum over ties by linearity

Let $X_k$ indicate that the tie made with $2k$ ends closes a loop. The loop count is $\sum_k X_k$ , and linearity of expectation adds the per-tie chances with no need for independence,

\E[\text{loops}] = \sum_{k=1}^{100} \frac{1}{2k-1} = 1 + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{199}. \tag{2}

A tie made with 2k loose ends closes a loop with probability 1/(2k-1), so the expected loop count is the sum of those odd reciprocals. It climbs like half the natural log, reaching about 3.28 by a hundred noodles.

#Read it off

The sum of the reciprocals of the first 100 odd numbers equals $H_{200} - \tfrac{1}{2}H_{100} \approx 3.28$ , close to $\tfrac{1}{2}\ln(200) + \tfrac{\gamma}{2}$ . A bowl of 100 noodles makes only about three loops, because the loop-closing chance starts at a slim $\tfrac{1}{199}$ and stays small until the very last ties.