Calculating Expected Circles from 100 Noodles

This question belongs to the classic family of random pairings and cycle-structure problems, here framed in a tangible, interview-friendly way. It sits at the intersection of combinatorics and probability, a core part of quant prep for candidates targeting challenging quant interviews. The setup hides a deep structure: random matchings, cycles, and expectations over all possible configurations.

It trains your understanding of expected value in highly dependent systems, where outcomes are linked but linearity of expectation still applies cleanly. It also exercises comfort with random permutations, cycle decompositions, and recognizing when harmonic-like behavior appears in probabilistic models. You need to reason abstractly about configurations rather than compute brute-force probabilities.

This matters for quant interviews because many pricing, risk, and algorithmic problems reduce to expectations over complex random structures. Interviewers use such questions to see if you can map an informal story to a rigorous probabilistic model, navigate dependency without getting lost, and articulate clean, general reasoning under pressure.

What it tests

This problem class is governed by the principle of linearity of expectation applied to combinatorial structures formed by random pairings. When objects (like noodle ends) are randomly paired, the expected number of resulting cycles or circles can be decomposed into a sum over the possible ways cycles can be formed, often leading to a telescoping or harmonic series. The key is that each possible cycle of length $k$ has a calculable probability of forming, and the sum of these probabilities across all possible $k$ gives the expected count. This pattern holds because, regardless of dependencies between specific pairings, the expected value of the total number of cycles is simply the sum of the expected values for each possible cycle, thanks to the linearity of expectation. The harmonic structure emerges because the probability that a new pairing closes a cycle at each step is inversely proportional to the number of available ends, leading to terms like $1/(2n-1)$.