Expected Number of Loops from Tying Rope Ends

MediumProbability

Reported in interviews at Citadel D. E. Shaw Jane Street Schonfeld Strategic Advisors Virtu Financial

Problem statement

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$.

Show hint

At a single tie, what decides whether a loop closes, and does that depend on how the current pieces look?

Relevant roles: Data Scientist, Applied Scientist and Research Scientist.

Related free problems