Another colored balls puzzle (part II) 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.
 A: As Douglas Zare points out in a comment to Vincent Beffara's answer, in case 1 the expected time to completion of the process, starting from $(1,n-1)$ is $2^n-1$. To see this, consider a simple random walk on the $n$-th dimensional hypercube. When started at some vertex, say $00\ldots0$, the expected number of step to return to this vertex is exactly the number of vertices, $2^n$. On the other hand, if we only look at the hamming weight of the current vertex we see that the transition probabilities are exactly like in our case 1. Indeed, case 1 can be described as "choose a uniformly random ball and flip its color". Since we start at hamming weight 1 (corresponding to $(1,n-1)$) we get $2^n-1$ as the expected hitting time.
A: This feels a lot like Erdös-Renyi graphs ... How about a sub-problem with $n$ balls initially but only $2$ colors, red and blue. Let $X_t$ be the number of red balls. You always pick a red/blue pair, so everything maps to a random walk on the discrete interval $[0,n]$. Let $p_k$ be the jump probability to the right:
Case 1: $p_k = 1 - k/n$. The local drift is given by $2p_k-1$ so it point inward towards $n/2$. Let $\varepsilon_k = \log \frac {1-p_k} {p_k}$ and $V_k = \sum_{i=0}^{k} \varepsilon_k$. Then the random walk is exactly a walk in the potential $(V_k)$, which is very large towards the boundary. The time needed to exit the interval (and get to one color) behaves like the exponential of the height difference between the maximum of the potential and its minimum. Back-of-the-envelope computation: close to the left boundary $p_k=1$ so get $\varepsilon_k \simeq - \log k/n$. Summing to $n/2$ gives $- \log [(n/2)!/n^{n/2}]$ which is roughly linear in $n$, and the exit time is indeed exponential (update: the difference in potential can be estimated as a Riemann sum and it does scale like $n \log 2$ giving an expected exit time like $2^n$).
Case 2: $p_k = k/n$, now the drift is towards the boundary. The right asymptotic should be something diffusive while close to the middle, and then essentially deterministic (and ballistic) as soon as one catches positive enough drift. If the switch occurs at distance $n^\alpha$ from the boundary, where drift is of order $n^{\alpha-1}$, the first hitting time is like $n^{2\alpha}$ and the second one like $n/n^{\alpha-1} = n^{2-\alpha}$. $\alpha=2/3$ gives a bound of the form $n^{4/3}$.
All this up to computing errors, which are pretty likely. Going from $2$ colors to $n$ is left as an exercise to the reader ;-) but I am guessing similar behavior, exponential in case $1$ and polynomial in case $2$.
A: 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}$.
