Ball Repainting to All Same Color

This question looks at a randomly evolving system where objects repeatedly copy each other's state until eventually everything is uniform. The setup is a finite collection of distinguishable items, each starting in its own state, and a rule that selects a pair at random and forces one to adopt the other's state. The candidate is asked to determine how long, on average, this random dynamics takes to reach full consensus, where every item shares the same state. Similar consensus and coalescence models appear in probability-heavy quantitative research roles and in some hedge fund interviews that probe comfort with stochastic processes and random evolution over time.

Solving it leans heavily on Markov chain ideas, symmetry arguments, and expected hitting times for absorbing states. A strong answer usually involves identifying the right notion of "state" for the system, writing down transition probabilities between aggregated states, and deriving and solving a recurrence or linear system for expected times. Interviewers look for the ability to exploit exchangeability to simplify the chain, avoid overcomplicating the state space, and reason cleanly about absorption without getting lost in combinatorial bookkeeping.

What it tests

This problem class is governed by the dynamics of absorbing Markov chains, where the process transitions between states (here, the number of balls of a given color) until it reaches an absorbing state (all balls one color). The key is that each step can only increase, decrease, or leave unchanged the count of a particular color, and the process is symmetric across all colors. The expected time to absorption can be found by setting up and solving a recurrence relation based on the transition probabilities between states. The symmetry ensures that the expected time to reach any absorbing state is the same, allowing us to focus on a single color without loss of generality. The pattern holds because, in such processes, the expected time to absorption depends only on the structure of transitions and not on the specific labels of the states.