The same colleague as in Another colored balls puzzle asked me the following variant which she called "part II".
Imagine you have $n$ balls in a bag that are colored from $1$ to $n$. At each turn you take one ball uniformly at random from the bag and then a second uniformly at random from the remaining balls which have a different color to the first. You then color one ball the color of the other and put them both back in the bag.
What is the expected number of turns before all the balls have the same color if:
- You always paint the first ball the color of the second? Or…
- You always paint the second ball the color of the first?
My intuition is that in the first case you are likely to be decreasing the number of balls with a commonly occurring color and in the second you are likely to be increasing the number of balls with a commonly occurring color. Hence the time to get all colors the same will be much less in the second case than the first.
Simulations.
For rule 1 I get the following approximate expected values for $n = 2 \dots 6$.
$1$, $4$, $10.33$, $22.48$, $45.23$.
For rule 2 I get the following approximate expected values for $n = 2 \dots 6$.
$1$, $2.500$, $4.416$, $6.698$. $9.310$.
To get some feeling for how the problem scales I also tried some other values up to $n=100$. For rule 1 and $n=100$ my simulation didn't get to all balls being equal even once in the time I gave it. However for $n=10$ I get about $618$ and for $n=20$ I get very roughly $520,000$. For rule 2 I get a mean of roughly $865$ for $n=100$. My blind guess is now that the mean for rule is 1 is at least exponential (in fact it looks a little like $2^{n-1}$) but that for rule two it is not quite $\frac{e}{4} n^{1.55}$ but it may be something similar.
Best Answer
Ori Gurel-Gurevich pointed out that the transitions under Rule 1 are like the Hamming distances from $\vec{0}$ in a random walk on a hypercube $C$ (the Ehrenfest urn model). Further, the average number of steps for a random walk to return to a vertex in a regular connected graph is the number of vertices. We can use this idea on the quotient by the antipodal map to get that the average return time on $C/\sim$ is $2^{n-1}$, so on the hypercube, the average time before you either return to $00\ldots0$ or hit its antipode $11\ldots 1$ is $2^{n-1}$. The first step from $00\ldots0$ moves to a state with a single $1$ and $n-1$ $0$s, so the average time to reach either $(n,0)$ or $(0,n)$ from $(1,n-1)$ is $2^{n-1}-1$.
On the way to becoming a uniform color, the balls have to pass through a state with a single ball of one color, and $n-1$ of a second color. So, $2^{n-1}-1$ is an exponential lower bound for the expected number of steps from the original position with $n$ colors.
Here is a simple way to get an exponential upper bound for Rule 1. First, pick a color with $1$ element, and consider the probability that the next $n-1$ steps each increase the size of that color. This is at least $$p= \frac{n-1}{n}\frac{1}{n-1} \times \frac{n-2}{n}\frac{2}{n-1} \times ... \frac{1}{n}\frac{n-1}{n-1}= \frac{(n-1)!^2}{ n^{n-1}(n-1)^{n-1}}. $$
By Stirling's formula, $(n-1)! \sim \sqrt{2\pi (n-1)} ((n-1)/e)^{n-1}$ so
$$p \sim \frac{2\pi (n-1)^n}{n^{n-1} e^{2(n-1)}} \sim \frac{cn}{e^{2n}}.$$
The probability is even greater if you pick a color with more than one element, since you get the first few steps for free. Because the probability that the process will end in the next $n$ steps is at least $cn/(e^{2n})$, the expected number of steps until completion is at most $O(e^{2n})$.
Part of Johan Wästlund's answer to part 1 can be turned into bounds for Rule 2. Consider the number of pairs of balls which don't have the same color. This starts at $n \choose 2$. At each step, you choose an ordered pair of balls $(a,b)$. Conditioned on the choice of the unordered pair $\lbrace a, b \rbrace$, the expected number of pairs of balls of different colors decreases by at least $1$:
Suppose there are $c_a$ balls of the same color as $a$, and $c_b$ balls of the same color as $b$. The conditional probability that the ordering is $(a,b)$ is $(n-c_b)/(2n-c_a-c_b)$. The number of pairs of balls of different colors is decreased by $1 + c_a - c_b$. Conditioned on the event that the unordered pair was $\lbrace a, b\rbrace$, the number of pairs of balls of different colors is decreased on average by $1 + \frac{(c_a-c_b)^2}{2n-c_a-c_b} \ge 1.$
So, the expected number of steps under Rule 2 before all balls have the same color is at most $n \choose 2$.
This argument can be adjusted to give lower bounds which are better than linear. For $n \le x \le n^2/8$, if there are $x$ pairs of balls of the same color, then it takes an average of at least $k n$ steps for the number of pairs of balls of the same color to double to $2x$ for some constant $k$, since we can bound the numerator and denominator of $\frac{(c_a-c_b)^2}{2n-c_a-c_b}$ in terms of $x$. It takes about $\log_2 n - 2$ doublings to go from $n$ pairs the same color to $n^2/4$. This gives a lower bound of $\Omega(n \log n)$.
Here is an improved lower bound for rule 2. Suppose the number of ordered pairs of balls of the same color is $X \lt n^2/4$. $X = \sum_i c_i^2$ where $c_i$ is the number of balls of the $i$th color. We can estimate the expected change $E\bigg[2 + \frac{2(c_a-c_b)^2}{2n - c_a - c_b}\bigg] \le 2 + \frac{k}{n}E[c^2]$ where $k$ is some constant, and $c$ is the number of balls of the color of a random ball. $E[c^2] = \frac{1}{n} \sum_i c_i^3 \le \frac{1}{n} (\sum_i c_i^2)^{3/2} = \frac{1}{n}X^{3/2}$. (The inequality is that the $L^3$ norm is smaller than the $L^2$ norm.)
The number of ordered pairs of balls of the same color increases by at most $2 + \frac{k}{n^2}X^{3/2}$ per step on average. $X$ starts at $n$, and when $X \lt n^{4/3}$, the number of ordered pairs of balls of the same color increases by at most $2+k$ on average, so the expected number of steps for $X$ to reach $n^{4/3}$ (en route to $n^2$) is $\Omega (n^{4/3})$.
I believe that applying this up to $n^2$ would only give another factor of $\log n$, so this is still a bit off of the empirical result of about $n^{3/2}$.