Maximize Expected Heads with Pairwise Flips

This quant interview question is about understanding how constrained operations shape what outcomes are achievable, even when the randomness itself is simple. You see randomness from fair coin flips, but the key challenge is the structure of the allowed moves and how they restrict or enable transitions between different global configurations of heads and tails.

It trains your ability to analyze state spaces, track invariants, and reason about long-run behavior under repeated operations. Good quant prep for this puzzle sharpens intuition about reachability, absorbing configurations, and how subtle structural constraints can dominate naive probabilistic thinking. It also reinforces comfort with random processes that have hidden symmetries and conserved quantities.

This matters for quant interviews because trading strategies, risk systems, and execution algorithms often live in high-dimensional state spaces with constraints. Such questions are used to see whether you can dissect a process, spot what really can and cannot change, and reason to a clean conclusion under pressure.

What it tests

This problem class is governed by the principle of state reachability under allowed operations. When you can repeatedly apply a set of moves (like flipping pairs of coins), the key is to analyze the structure of the state space: which configurations are accessible from which others, and whether there are any unreachable or absorbing states. If every state can be transformed into a desired target (like all heads) through the allowed moves, then, given unlimited steps, the probability of reaching that target is 1. The underlying reason is that the operation set is sufficiently rich to connect the entire state space, often due to properties like parity or invariance being preserved or manipulated by the moves. Understanding which invariants are preserved or broken by each operation is crucial for determining reachability.