Return to Answer

even later The exact expectations for $n$ up to $20$ found by Karl support this. If $a_n$ is the expected number of steps to get from $n$ balls with $n$ different colors to all the same color and $a_n=2^{n-1}-1(1+\frac{b_n}{n})$ then we have these values for $b_n:$

even later The exact expectations for $n$ up to $20$ found by Karl support this. If $a_n$ is the expected number of steps to get from $n$ balls with $n$ different colors to all the same color and $a_n=2^{n-1}(1+\frac{b_n}{n})$ then we have these values for $b_n:$

LATER Concerning procedure 1: We know that the expected number of steps is greater than $2^{n-1}.$ However it appears that perhaps the expected number of steps is less than $2^{n-1}(1+\frac{2}{n})$ (provided $n \ge 10$).

There will be a stage (after at least $n-2$ steps) at which there are $n-1$ balls of the same color and $1$ of another color. As has been elegantly proved, from this point the expected number of steps until all balls are the same color is exactly $2^{n-1}-1.$ This provides a lower bound and, in fact, a surprisingly good one. For each value of $n$ from $3$ to $6$ I did $50,000$ trials and for each value of $n$ from $7$ to $13$ I did $5000$ trials of the first procedure for $n$ balls initially with $n$ distinct colors. Here are the rounded averages

In all cases this is less than $2^{n-1}(1+\frac{3}{n})$ and for the last four cases less than $2^{n-1}(1+\frac{2}{n}).$

LATER Concerning procedure 1: We know that the expected number of steps is greater than $2^{n-1}.$ However it appears that perhaps the expected number of steps is $2^{n-1}(1+\frac{1+o(n)}{n}).$ There will be a stage (after at least $n-2$ steps) at which there are $n-1$ balls of the same color and $1$ of another color. As has been elegantly proved, from this point the expected number of steps until all balls are the same color is exactly $2^{n-1}-1.$ This provides a lower bound and, in fact, a surprisingly good one. For each value of $n$ from $3$ to $6$ I did $50,000$ trials and for each value of $n$ from $7$ to $13$ I did $5000$ trials of the first procedure for $n$ balls initially with $n$ distinct colors. Here are the rounded averages

In all cases this is less than $2^{n-1}(1+\frac{3}{n})$ and for the last four cases less than $2^{n-1}(1+\frac{2}{n}).$

even later The exact expectations for $n$ up to $20$ found by Karl support this. If $a_n$ is the expected number of steps to get from $n$ balls with $n$ different colors to all the same color and $a_n=2^{n-1}-1(1+\frac{b_n}{n})$ then we have these values for $b_n:$

$ [5, 2.495], [6, 2.752], [7, 2.752], [8, 2.516], [9, 2.364], [10, 2.140], [11, 1.925], [12, 1.741],$$ [13, 1.600], [14, 1.488], [15, 1.404], [16, 1.341], [17, 1.294], [18, 1.258], [19, 1.231], [20, 1.210]$

Consider the related problem of just two colors of balls, white and black (wlog at least as many black as white.) This will give lower bounds since the given problem will eventually have two colors of balls before it has just one. Also, we can split the many colors into two groups (light and dark) and follow the process. This simplification amounts to not counting the steps that involve two colors from the same group. The expected number of steps to get from $1$ white and $b$ black to all the same color seems certain to be be exactly $2^b-1=2^{n-1}-1$ where $n=w+b$ is the total number of balls. If the number of white balls is at least $2$ of a total of $n$ then the expected number of steps appears to be roughly $2^{n-1}(1+\frac{1}{n}+\frac{w^2-w}{2n^2})$

Let $f(w,b)$ be the expected number of steps to get from $w$ white and $b$ black balls to a situation with all balls of the same color. Also, let $g(w)$ be $f(w,b)=f(w,n-w)$ as a function of $n=b+w.$ As Douglas observed, it seems certain that $f(1,b)=2^b-1$ (i.e. $g(1)=2^{n-1}-1$) and this is definitely true for $b \le 100.$ It appears that $f(b,b)=2^{2b-1}(1+o(b))$ of course $f(b,b) \gt f(1,2b-1)=2^{2b-1}-1$ (one conjectures) so almost all the time is taken up trying to get past the final step. Some numerical data is at the end.

This is sufficient to find the ratio of each of the $g(w)$ for fixed $w$ to $g(1)$ which it seems safe to bet is $g(1)=2^{n-1}-1.$ However let us just let $g(1)=Z=Z(n).$ Then the first few equations are

LATER Concerning procedure 1: We know that the expected number of steps is greater than $2^{n-1}.$ However it appears that perhaps the expected number of steps is less than $2^{n-1}(1+\frac{2}{n})$ (provided $n \ge 10$).

There will be a stage (after at least $n-2$ steps) at which there are $n-1$ balls of the same color and $1$ of another color. As has been elegantly proved, from this point the expected number of steps until all balls are the same color is exactly $2^{n-1}-1.$ This provides a lower bound and, in fact, a surprisingly good one. For each value of $n$ from $3$ to $6$ I did $50,000$ trials and for each value of $n$ from $7$ to $13$ I did $5000$ trials of the first procedure for $n$ balls initially with $n$ distinct colors. Here are the rounded averages

$[3, 4], [4, 10], [5, 22], [6, 45],[7, 88], [8, 172], [9, 322], [10, 610], [11, 1182], [12, 2388], [13, 4548]$

In all cases this is less than $2^{n-1}(1+\frac{3}{n})$ and for the last four cases less than $2^{n-1}(1+\frac{2}{n}).$

EARLIER Consider the related problem of just two colors of balls, white and black (wlog at least as many black as white.) This will give lower bounds since the given problem will eventually have two colors of balls before it has just one. Also, we can split the many colors into two groups (light and dark) and follow the process. This simplification amounts to not counting the steps that involve two colors from the same group. The expected number of steps to get from $1$ white and $b$ black to all the same color has been shown to be $2^b-1=2^{n-1}-1$ where $n=w+b$ is the total number of balls. If the number of white balls is at least $2$ of a total of $n$ then the expected number of steps appears to be roughly $2^{n-1}(1+\frac{1}{n}+\frac{w^2-w}{2n^2})$

Let $f(w,b)$ be the expected number of steps to get from $w$ white and $b$ black balls to a situation with all balls of the same color. Also, let $g(w)$ be $f(w,b)=f(w,n-w)$ as a function of $n=b+w.$ As Douglas observed for $b \le 100$ and Uri proved for all $b$, $f(1,b)=2^b-1$ (i.e. $g(1)=2^{n-1}-1$) It appears that $f(b,b)=2^{2b-1}(1+o(b))$ of course $f(b,b) \gt f(1,2b-1)=2^{2b-1}-1$ so almost all the time is taken up trying to get past the final step. Some numerical data is at the end.

This is sufficient to find the ratio of each of the $g(w)$ for fixed $w$ to $g(1)$ which we now know to be $g(1)=2^{n-1}-1.$ However (since I wrote this before I knew a proof of the value for $g(1)$) let us just define $g(1)=Z=Z(n).$ Then the first few equations are