Expected loops from tying 100 noodle ends

Question

A bowl contains $100$ noodles, giving $200$ free ends. Repeatedly pick two free ends at random and tie them together, until no free ends are left. What is the expected number of closed loops formed?

Short answer

$\sum_{k=1}^{100}\tfrac1{2k-1}\approx3.28$ . With $k$ strands left there are $2k$ ends; after picking one end, the second end closes a loop with probability $\tfrac1{2k-1}$ , and either way one strand fewer remains. Summing these expected contributions over $k=100,\dots,1$ gives the answer.

Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 4.5 Expected Value, Variance & Covariance, 'Connecting noodles', p.92; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Expectation, Variance and Covariance is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free