Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 –  Gerhard Paseman May 13 '13 at 15:21
    
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. –  Brendan McKay May 13 '13 at 18:01
    
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)$. –  Greg Martin May 13 '13 at 18:22
4  
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 –  Douglas Zare May 13 '13 at 19:42
2  
See also: ma.huji.ac.il/hart/papers/n-colors.pdf –  Benjamin Dickman May 14 '13 at 2:33
add comment

3 Answers

up vote 13 down vote accepted

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.

share|improve this answer
2  
Nice argument.${}$ –  Douglas Zare May 13 '13 at 21:31
1  
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. –  Greg Martin May 13 '13 at 21:51
3  
@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. –  Russ Woodroofe May 13 '13 at 22:26
    
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. –  Russ Woodroofe May 13 '13 at 22:29
3  
@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. –  Jon Peterson May 14 '13 at 13:00
show 2 more comments

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$.

share|improve this answer
    
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 –  Gerhard Paseman May 13 '13 at 19:20
    
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. –  navid May 13 '13 at 19:42
    
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 –  Gerhard Paseman May 13 '13 at 21:08
add comment

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.$$

share|improve this answer
    
This is very nice, and it can be applied to part 2: mathoverflow.net/questions/130513/… –  Douglas Zare May 18 '13 at 22:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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