11
$\begingroup$

This is a puzzle a colleague asked me recently.

Imagine you have $n$ balls in a bag that are colored from $1$ to $n$. At each turn you take two balls at random out that have different colors and color one the color of the other. You then put them both back in the bag. What is the expected number of turns before all the balls have the same color?

The pair of balls you choose is uniformly selected from the set of all pairs of different-colored balls. You choose uniformly at random whether to paint the first the same as the second or vice versa.

$\endgroup$
5
  • $\begingroup$ For large n, I would guess no bound. To get to two colors is nontrivial, but I would expect that to be reached within an exponential in n number of tries. Gerhard "Of Course I'm Just Guessing" Paseman, 2013.05.13 $\endgroup$ May 13, 2013 at 15:21
  • $\begingroup$ I think it is polynomial. To get from $k+1$ colours to $k$ colours, choose an existing colour and monitor the number of balls with that colour. It goes up or down (with equal probability) at least 1 in $n$ turns and is a standard random walk so it hits either 0 or n in polynomial expected time. $\endgroup$ May 13, 2013 at 18:01
  • $\begingroup$ Note that once the balls have been reduced to two colors, say $m$ red balls and $n-m$ green balls, this is exactly the Gambler's Ruin problem; the expected number of turns remaining at this point is exactly $m(n-m)$. $\endgroup$ May 13, 2013 at 18:22
  • 4
    $\begingroup$ An upper bound is $(n-1)^2$, which is what you get if you don't require the balls to be different colors. mathoverflow.net/questions/41939/a-balls-and-colours-problem $\endgroup$ May 13, 2013 at 19:42
  • 2
    $\begingroup$ See also: ma.huji.ac.il/hart/papers/n-colors.pdf $\endgroup$ May 14, 2013 at 2:33

4 Answers 4

15
$\begingroup$

I think you can verify Greg Martin's answer using indicator variables and linearity of expectation.

Let the random variable $X_i$ be the number of steps where one of the balls has the $i$th color before the $i$th color either disappears or becomes the only color.

The expected value of $X_i$ is as in the Gambler's Ruin, that is, $1 \cdot (n-1) = n-1$.

Each step involves two colors, hence the time to a single color is $\frac{1}{2} \sum X_i$.

The $\binom{n}{2}$ answer follows.

$\endgroup$
7
  • 2
    $\begingroup$ Nice argument.${}$ $\endgroup$ May 13, 2013 at 21:31
  • 1
    $\begingroup$ I don't fully understand this answer. For the variable $X_i$, are you pretending that there are only two colors, $i$ and not-$i$? If so, there are steps in the real game, involving two different not-$i$ colors, that don't affect the pretend game. Furthermore, why would the real game's expectation be the sum of the pretend expectations? - it seems to me that it should be the max of the pretend expectations. $\endgroup$ May 13, 2013 at 21:51
  • 4
    $\begingroup$ @Greg Martin: Every step in the real game involves 2 colors, say $i$ and $j$, and is counted by $X_i$ and $X_j$. Thus, the number of steps in the real game is half the sum of the $X_i$'s. (But as you note, for any fixed $i$, there are steps in the real game that are ignored by $X_i$.) Linearity of expectation then says that the expectation of the sum is the sum of the expectations. $\endgroup$ May 13, 2013 at 22:26
  • $\begingroup$ This is an example of the general technique of using indicator variables to calculate an expected value. Some more (easier) examples are worked out at mikespivey.wordpress.com/2011/12/01/indicator-variables or in your favorite Intro Probability textbook. $\endgroup$ May 13, 2013 at 22:29
  • 3
    $\begingroup$ @Russ: I like the proof. However, I think the explanation would be more clear if you had given a better definition of the random variable $X_i$. I think from the way you're using it in your proof, $X_i$ is the number of times when color $i$ is one of the two colors chosen. This makes it clear that $1/2 \sum_i X_i$ is the random variable of interest and makes it easy to see why each $X_i$ is just a gamblers ruin problem. $\endgroup$ May 14, 2013 at 13:00
6
$\begingroup$

It seems there is little to add after Russ Woodroofe's nice answer, but anyway: If at each time $t=0,1,2,\dots$, we draw two balls without conditioning on them having different colors, then the probability of drawing two different colors at time $t$ is $$\left(1-\frac1{\binom{n}2}\right)^t.$$ This is because the number of pairs of balls of different color will stay the same every time we draw two balls of the same color, but decrease by one in expectation every time we draw two balls of different colors (that pair will become of the same color and everything else cancels!).

Running the process to infinity, the expected total number of times we draw balls of different color is $$\sum_{t=0}^\infty \left(1-\frac1{\binom{n}2}\right)^t = \binom{n}2.$$

$\endgroup$
1
5
$\begingroup$

I've calculated rigorously that the expectations for $n=1,2,3,4$ are $0,1,3,6$ respectively. For example, when $n=4$:

  • One turn brings the balls to a 211 state (meaning 2 balls of one color and 1 ball each of two more colors).
  • From a 211 state, there is a $2/5$ probability of going to another 211 state, a $2/5$ probability of going to a 31 state, and a $1/5$ probability of going to a 22 state.
  • In other words, there is a $2/5$ probability of staying in the 211 state and a $3/5$ probability of leaving it; the expected number of turns it takes to leave the 211 state is thus $1/(1-2/5) = 5/3$. When it does leave, there's a $2/3$ probability of being in a 31 state and a $1/3$ probability of being in a 22 state.
  • By Gambler's Ruin, the expected number of turns to go from the 22 state to the 4 state is $2(4-2)=4$, while the expected number of turns to go from the 31 state to the 4 state is $3(4-3)=3$.
  • Therefore, the total expected number of turns for the $n=4$ game is $1 + 5/3 + (\frac23\cdot 3 + \frac13\cdot 4) = 6$.

Moreover, I've run simulations for $n=5,6,7$. The data strongly suggests that the expectations are $10,15,21$ respectively.

I am thus persuaded to conjecture that the expected stopping time for $n$ balls in general is exactly $\binom n2 = n(n-1)/2$.

$\endgroup$
3
  • $\begingroup$ Why is 5 a denominator? Isn't the chance of a transition from 211 to 22 actually 1/3? Similarly for the other transitions out of 211? Gerhard "What Does Probability Really Mean?" Paseman, 2013.05.13 $\endgroup$ May 13, 2013 at 19:20
  • $\begingroup$ There are five pairs of balls with different colors in the 211 state. You can pick one of the pair with the same color and either one of the others. Or pick the other one of the pair with the same color and either of the others. Finally you could pick the pair which are uniquely colored. $\endgroup$
    – navid
    May 13, 2013 at 19:42
  • $\begingroup$ Ah, I misread it as different pairs of colors, not different pairs of colored balls. Also, I should have thought of difference in number of heads and tails being m, rather than a string of m heads, in the two color scenario with m balls of one color. Greg's analysis is looking good to me now. Gerhard "It's All About Good Looking" Paseman, 2013.05.13 $\endgroup$ May 13, 2013 at 21:08
2
$\begingroup$

Let $B_i$ denote the number of balls of color $i$ ($i=1,\ldots,n$) after some turns, and define a quantity $$ S=\sum_i B_i^2. $$ Suppose that on the next turn, we draw two balls of colors $j\neq k$, and choose one at random to receive the color of the other. The expected value of $S$ after this turn is $$ \frac{1}{2}\left(\sum_{i\neq j,k}B_i^2+(B_j+1)^2+(B_k-1)^2\right)+\frac{1}{2}\left(\sum_{i\neq j,k}B_i^2+(B_j-1)^2+(B_k+1)^2\right)=\sum_i B_i^2 +2. $$ The expected value of $S$ increases by $2$ each turn. The initial value of $S$ is $n$, and when all balls are the same color the value of $S$ is $n^2$, so the expected number of turns is $$ \frac{n^2-n}{2}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.