A box contains $n$ balls of $n$ different colors. Each time, you randomly select a pair of balls, repaint the first to match the second, and put the pair back into the box. **Question:** What is the expected number of steps until all balls in the box are of the same color? By symmetry of the $n$ colors, conditioning on which color "wins" does not change the expected time. So $E[N_n] = E[N_n \mid F_1]$, where $F_1$ is the event that all balls end up with color 1. This lets you focus on tracking a single quantity: the number of color-1 balls. Once you condition on $F_1$, the number of color-1 balls $X_k$ evolves as a Markov chain on $\{1, 2, \ldots, n\}$ with $n$ absorbing. To compute the conditional transition probabilities $P_{i,j} \mid F_1$, use Bayes' theorem together with the key fact that $P(F_1 \mid X_k = i) = i/n$ (provable by relabeling the $i$ color-1 balls with distinct sub-labels). After plugging the conditional transitions into the first-step equation for $Z_i = E[N_n \mid F_1, X_0 = i]$ and dividing by $(n-i)$, define $b_i = (i+1)Z_{i+1} - i Z_i$. The recurrence telescopes: $b_{i-1} - b_i = \frac{n(n-1)}{n-i}$. Sum $b_k$ from $k=1$ to $n-1$ and use $Z_n = 0$ to extract $Z_1$. ### Preamble This is a genuinely difficult problem: the state of the box (the full color distribution) is high-dimensional, and a direct attack quickly becomes intractable. We will tackle it step by step, with each step setting up the next. We strongly recommend pausing at the end of each step to make sure you understand it before moving on — the logic is cumulative. **Notation we will use throughout (refer back here whenever a symbol appears):** - $N_n$: the random number of steps until all $n$ balls share the same color. - $F_i$ for $i = 1, \ldots, n$: the event that all balls end up with color $i$. - $X_k$: the number of color-1 balls after step $k$ (defined once we condition on $F_1$). - $P_{i,j}$: the unconditional one-step transition probability $P(X_{k+1} = j \mid X_k = i)$. - $P_{i,j} \mid F_1$: the transition probability conditioned on $F_1$, i.e., $P(X_{k+1} = j \mid X_k = i, F_1)$. - $Z_i = E[N_n \mid F_1, X_0 = i]$: the expected number of steps until absorption, given that we start with $i$ balls of color 1 and condition on $F_1$. By time-homogeneity of the chain, this also equals the expected **remaining** time whenever the chain is in state $i$. These are the only variables we will need. ### Step 1: Symmetry reduction By the law of total expectation: $$ E[N_n] = \sum_{i=1}^n E[N_n \mid F_i] \, P[F_i]. $$ By symmetry of the $n$ colors (no color is distinguished by the dynamics): $$ P[F_1] = P[F_2] = \cdots = P[F_n] = 1/n, $$ $$ E[N_n \mid F_1] = E[N_n \mid F_2] = \cdots = E[N_n \mid F_n]. $$ Therefore $E[N_n] = E[N_n \mid F_1]$, and we may assume the final color is color 1. ## Step 2: Markov chain modeling To compute $E[N_n \mid F_1]$, we model the problem as a Markov chain. Once we condition on $F_1$, color 1 is distinguished from the others, and the **number of color-1 balls** is a sufficient state variable. This is $X_k$. **State space and transition graph.** $X_k$ takes values in $\{1, 2, \ldots, n\}$: - State $n$ is the only absorbing state ($F_1$ achieved, all balls are color 1). - State $0$ does not appear: if color 1 ever vanished, $F_1$ would be impossible. Conditioning on $F_1$ excludes it. - From any state $1 \le i \le n-1$, the chain moves to $i-1$, stays at $i$, or moves to $i+1$. **Absorption equation.** $$ Z_i = 1 + Z_{i-1} \cdot P_{i,i-1} \mid F_1 + Z_i \cdot P_{i,i} \mid F_1 + Z_{i+1} \cdot P_{i,i+1} \mid F_1, $$ with boundary $Z_n = 0$ (if we start at the absorbing state, $N_n = 0$). Our target is $Z_1$, since initially there is exactly one ball of color 1 ($X_0 = 1$), so $E[N_n \mid F_1] = Z_1$. To make this equation usable, we now need to compute the three conditional transition probabilities $P_{i,i-1} \mid F_1$, $P_{i,i} \mid F_1$, and $P_{i,i+1} \mid F_1$. This is the goal of the next step. ## Step 3: Computing $P_{i,i-1} \mid F_1$ We rewrite this probability for a generic step $k$: $$ P_{i,i-1} \mid F_1 = P(X_{k+1} = i-1 \mid X_k = i, F_1) $$ $$ = \frac{P(X_k = i, X_{k+1} = i-1, F_1)}{P(X_k = i, F_1)} $$ $$ = \frac{P(F_1 \mid X_{k+1} = i-1, X_k = i) \cdot P(X_{k+1} = i-1 \mid X_k = i) \cdot P(X_k = i)}{P(F_1 \mid X_k = i) \cdot P(X_k = i)} \quad \text{(Bayes' theorem)} $$ $$ = \frac{P(F_1 \mid X_{k+1} = i-1) \cdot P(X_{k+1} = i-1 \mid X_k = i)}{P(F_1 \mid X_k = i)} \quad \text{(Markov property)} $$ We now compute the three quantities appearing in this expression. **(a) $P(F_1 \mid X_k = i) = i/n$.** Suppose currently $i$ balls have color 1 and we need to compute the probability that we end up with color 1. When we relabel the balls with distinct sub-labels $c_1, \ldots, c_i$ (this doesn't change the dynamics — we are just renaming), with $n$ distinct labels in total, the symmetry argument from Step 1 applies: each label has probability $1/n$ of being absorbing. The event $F_1$ corresponds to any of the $i$ sub-labels winning, so $P(F_1 \mid X_k = i) = i/n$. By the same argument, $P(F_1 \mid X_{k+1} = i-1) = (i-1)/n$. **(b) Unconditional transition $P(X_{k+1} = i-1 \mid X_k = i)$ ? :** There are $n(n-1)$ ordered pairs of distinct balls. For the count of color-1 balls to drop, the **first** ball (the one being repainted) must be color 1 ($i$ choices) and the **second** ball must be non-color-1 ($n-i$ choices), giving $i(n-i)$ favorable pairs. so we have : $$ P(X_{k+1} = i-1 \mid X_k = i) = \dfrac{i(n-i)}{n(n-1)} $$ **Putting it together:** $$ P_{i,i-1} \mid F_1 = \frac{\dfrac{i-1}{n} \cdot \dfrac{i(n-i)}{n(n-1)}}{\dfrac{i}{n}} = \frac{(n-i)(i-1)}{n(n-1)}. $$ $$ \boxed{ P_{i,i-1} \mid F_1 = \frac{(n-i)(i-1)}{n(n-1)}. } $$ ### Step 4: Computing $P_{i,i} \mid F_1$ and $P_{i,i+1} \mid F_1$ Same Bayes structure. **Up to $i+1$.** Unconditionally: the first ball is non-color-1 ($n-i$ choices) and the second ball is color 1 ($i$ choices), so $P(X_{k+1} = i+1 \mid X_k = i) = \dfrac{i(n-i)}{n(n-1)}$. With $P(F_1 \mid X_{k+1} = i+1) = (i+1)/n$: $$ P_{i,i+1} \mid F_1 = \frac{\dfrac{i+1}{n} \cdot \dfrac{i(n-i)}{n(n-1)}}{\dfrac{i}{n}} = \frac{(n-i)(i+1)}{n(n-1)}. $$ **Stay at $i$.** Unconditionally, $P(X_{k+1} = i \mid X_k = i) = 1 - 2 \cdot \dfrac{i(n-i)}{n(n-1)}$. Since $P(F_1 \mid X_{k+1} = i) = i/n = P(F_1 \mid X_k = i)$, the Bayes factors cancel: $$ P_{i,i} \mid F_1 = 1 - \frac{2i(n-i)}{n(n-1)} = \frac{n(n-1) - 2i(n-i)}{n(n-1)}. $$ ### Step 5: Recurrence for $Z_i$ Plugging the conditional transitions into the absorption equation from Step 2: $$ Z_i = 1 + \frac{(n-i)(i-1)}{n(n-1)} Z_{i-1} + \frac{n(n-1) - 2i(n-i)}{n(n-1)} Z_i + \frac{(n-i)(i+1)}{n(n-1)} Z_{i+1}. $$ Multiplying by $n(n-1)$ and rearranging: $$ (n-i) \cdot 2i \cdot Z_i = n(n-1) + (n-i)(i+1) Z_{i+1} + (n-i)(i-1) Z_{i-1}, \quad 1 \le i \le n-1, $$ with boundary $Z_n = 0$. Our goal is $Z_1$. ### Step 6: Solving the recurrence For $1 \le i \le n-1$, divide both sides by $(n-i)$: $$ 2i \, Z_i - (i-1) Z_{i-1} - (i+1) Z_{i+1} = \frac{n(n-1)}{n-i}. $$ **Telescoping trick.** Define $b_i = (i+1) Z_{i+1} - i Z_i$ for $0 \le i \le n-1$, with $b_0 = Z_1$ (taking $0 \cdot Z_0 = 0$). The equation rewrites as: $$ b_{i-1} - b_i = \frac{n(n-1)}{n-i}. $$ Telescoping from $i=1$ to $i=k$: $$ b_k = b_0 - n(n-1) \sum_{i=1}^{k} \frac{1}{n-i} = Z_1 - n(n-1) \sum_{j=n-k}^{n-1} \frac{1}{j}. $$ **Sum $b_k$ from $k=1$ to $k=n-1$.** The left side telescopes: $$ \sum_{k=1}^{n-1} b_k = \sum_{k=1}^{n-1} \big[(k+1) Z_{k+1} - k Z_k\big] = n Z_n - Z_1 = -Z_1. $$ The right side: $$ \sum_{k=1}^{n-1} \left[Z_1 - n(n-1) \sum_{j=n-k}^{n-1} \frac{1}{j}\right] = (n-1) Z_1 - n(n-1) \, S, $$ where $S = \sum_{k=1}^{n-1} \sum_{j=n-k}^{n-1} \frac{1}{j}$. **Computing $S$.** Swap the order of summation: for fixed $j \in \{1, \ldots, n-1\}$, the term $1/j$ appears whenever $k \ge n-j$, giving $j$ values of $k$. So: $$ S = \sum_{j=1}^{n-1} \frac{j}{j} = n-1. $$ **Conclusion.** $$ -Z_1 = (n-1) Z_1 - n(n-1)^2 \implies n Z_1 = n(n-1)^2 \implies Z_1 = (n-1)^2. $$ Therefore: $$ \boxed{ E[N_n] = (n-1)^2. } $$

Random Walk on a Cube

Answer