Derangements Count for 50 Players

This quant interview question is about randomness, cycles, and grouping structure in a permutation viewed through the lens of expectation. It connects a simple party story to the abstract idea of how random matchings partition a set into disjoint cycles and fixed points. It is a classic type of brainteaser that hides a clean probabilistic structure underneath an intuitive narrative, typical of high-level quant prep.

It trains your command of expected value, indicator variables, and reasoning about random permutations without brute-force enumeration. You must be comfortable translating a verbal game into a rigorous probabilistic model, isolating events of interest, and leveraging symmetry and exchangeability. It also builds intuition for how complex dependent structures can still yield very tractable expectations.

This matters for quant interviews because trading, risk, and derivatives problems often involve intricate dependencies that are intractable to model directly. Interviewers use such questions to see if you can spot the right probabilistic abstraction, work cleanly with linearity of expectation under dependence, and reason about combinatorial structures. Strong performance on this type of quant prep problem signals readiness for real-world modeling where structure is hidden inside noisy, high-dimensional systems.

What it tests

This problem class is governed by the principle that the expected number of cycles (or groups) in a random permutation of $n$ elements is the $n$th harmonic number, but in this variant, the construction of groups by sequential draws allows us to use indicator variables and linearity of expectation. The key is that for each participant, the probability that they start a new group is determined by whether their name has not already been drawn, and this probability is independent of the order in which the draws occur. The structure is underpinned by the fact that, in a random process where each element is mapped to another (possibly itself), the expected number of distinct cycles can be decomposed into the sum of probabilities that each element is the least-indexed member of its cycle. This is why indicator variables are so powerful: they let us count the expected number of 'beginnings' of cycles without worrying about dependencies between cycles. The pattern holds because the expected value of a sum is the sum of expected values, even when the events are not independent, as long as the indicators are well-defined.