How long until all balls are the same colour?

Question

You have a bag containing $n$ balls of $n$ different colours. Select 2 balls randomly (in order, so there's a first and a second), repaint the first in the same colour as the second, and replace both balls in the bag. Keep on doing this once per minute until all balls in the bag are the same colour.
What is the expected time this will take?

_{(Edit to make sure the balls are all of different colours at the start. In the original version, it was $n$ balls of $m$ different colours. Apologies to anyone who started working on the problem in that form.)}

Answer 1

This question has been asked on Math Overflow. A beautiful answer was given by Ori Gurel-Gurevich, which I reproduce below.

Assume the balls and colors are both numbered $1,\dots,n$, with ball $i$ initially colored $i$.

Let $P(i,j)$ denote the action of painting ball $i$ the color of ball $j$. In this process, we perform a sequence of actions $P(i_1,j_1),P(i_2,j_2),\dots$, where $(i_k,j_k)$ is randomly chosen from the pairs where $i_k\neq j_k$, until all balls are the same color.

Here is a different process. Let $C(i,j)$ denote the action of taking every ball whose color is $i$ and painting it the color $j$. Perform the actions $C(i_1,j_1),C(i_2,j_2),\dots,$ with $i_k,j_k$ chosen randomly as before, until all balls are the same color. Call this the "new process".

The key to simplifying this problem is this brilliant observation: performing the actions $$ P(i_1,j_1),P(i_2,j_2),\dots, P(i_T,j_T) $$ to the initial setup has the same effect as performing the actions $$ C(i_T,j_T),C(i_{T-1},j_{T-1}),\dots, C(i_1,j_1) $$ to the initial setup. In words, reversing the order and replacing $P$ with $C$ does not change the resulting coloring.

It is somewhat difficult to explain why this is true (anyone who has an intuitive explanation should feel free to edit it in), but this example should convince you. Suppose have four balls, so the initial state is [1,2,3,4]. When we perform the actions $P(1,2), P(2,4), P(3,1), P(4,1)$, the resulting color distribution is [2,4,2,2], as shown below: $$ [1,2,3,4]\stackrel{P(1,2)}{\to}[2,2,3,4]\stackrel{P(2,4)}{\to}[2,4,3,4]\stackrel{P(3,1)}{\to}[2,4,2,4]\stackrel{P(4,1)}{\to}[2,4,2,2] $$ When the actions $C(4,1),C(3,1),C(2,4),C(1,2)$ are performed, the result is also [2,4,2,2], as claimed: $$ [1,2,3,4]\stackrel{C(4,1)}{\to}[1,2,3,1]\stackrel{C(3,1)}{\to}[1,2,1,1]\stackrel{C(2,4)}{\to}[1,4,1,1]\stackrel{C(1,2)}{\to}[2,4,2,2] $$

The symmetry implied by the bold statement means that the original process has the same average runtime as the new process, so we may analyze the expected runtime of the new process instead.

It turns out to be much easier to analyze the new process. If there are $k$ colors present at some point, then after performing a $C(i,j)$ action, the number of colors present will remain the same or decrease by $1$. It decreases by 1 with probability $\frac{k(k-1)}{n(n-1)}$, since this is the probability that both $i$ and $j$ are a color which was already present. Thus, the time it takes to decrease from $k$ colors to $k-1$ is a geometric random varaible, with expected time $\frac{n(n-1)}{k(k-1)}$, so the expected time it takes to go from $n$ colors to $1$ color is $$ \sum_{k=2}^n \frac{n(n-1)}{k(k-1)}=n(n-1)\sum_{k=2}^n\frac1{k-1}-\frac1{k}=n(n-1)\left(1-\frac1n\right)=(n-1)^2 $$ The first step follows since $\frac1{k(k-1)}=\frac1{k-1}-\frac1{k}$. The second follows since the sum is telescoping.

Thus, the expected time is $(n-1)^2$.

Answer 2

Summaries

BEST SOLUTION (based on values of $n_\omega$): $(n-1)^2$ minutes.
$n-1$ minutes is an ideal solution
$\infty$ is an invalid trollish solution.

Answer One - Invalid Troll

I say that the answer is $\infty$, by allowing the choosing and painting of balls to be an infinite time, meaning that the process is never completed. thus, the answer is $\infty$ and we're done! $■$

(after reading comments) So you do mean time... How interesting. I failed to observe the "once per minute" bit. My general solutions is this: $\color{blue}{\Phi(n)}$ (see lower down)

---

Answer Two - $n_\omega$

This assumes that "expected time" is the same as "number of steps".

Experimental trial

$Spawn$:$\{\color{green}{ball},\color{red}{ball},\color{purple}{ball},\color{blue}{ball}\}$
$Step\>1$:$\text{Choose: }(\color{blue}{4},\color{green}{1})$ $\text{Resultant set: }\{\color{blue}{ball},\color{red}{ball},\color{purple}{ball},\color{blue}{ball}\}$
$Step\>2$:$\text{Choose: }(\color{blue}{1},\color{purple}{3})$ $\text{Resultant set: }\{\color{blue}{ball},\color{red}{ball},\color{blue}{ball},\color{blue}{ball}\}$
$Step\>3$:$\text{Choose: }(\color{red}{2},\color{blue}{1})$ $\text{Resultant set: }\{\color{red}{ball},\color{red}{ball},\color{blue}{ball},\color{blue}{ball}\}$
$Step\>4$:$\text{Choose: }(\color{red}{2},\color{blue}{3})$ $\text{Resultant set: }\{\color{red}{ball},\color{red}{ball},\color{red}{ball},\color{blue}{ball}\}$
$Step\>5$:$\text{Choose: }(\color{red}{3},\color{blue}{4})$ $\text{Resultant set: }\{\color{red}{ball},\color{red}{ball},\color{red}{ball},\color{red}{ball}\}$

Conclusions

Five steps for an experiment of $n=4$. It makes sense that, within a few iterations, a good deal of colours will disappear; a minimum of one colour will disappear within the first iteration. In this example, by step 2, we see that the original population of colours has been reduced from 4 to 2.

---

Computer- & Math-aided Portion

(to be accomplished with computers! The answer is easier to find if you know what you are looking for.)

You can't hate python. FEEL THE POWER OF PYTHON! This is how I obtain $n_\alpha$.

from random import *

class Ball:
    def __init__(self,colour):
        self.colour = colour

    def change_colour(self,ball):
        self.colour = ball.colour

def allColour(list):
    b = list[0].colour
        for i in range(len(list)):
            if not (b == list[i].colour):
                return False
            b = list[i].colour
    return True

def ball_sim(n):
    rq = list(range(n))
    for i in range(n):
        rq[i] = Ball(i)
    trials = 0
    if n == 1 or int(n) != n:
        return 1
    while not allColour(rq):
        samp = sample(list(range(len(rq))),2)
        rq[samp[0]].change_colour(rq[samp[1]])
        trials += 1
    return trials

def s(n,m):
    avg = 0
    for qk in range(n):
        avg += ball_sim(m)
    return avg / n

while True:
    n = input("(integer) n = ")
    print(s(100000,int(n)))
    input("continue...")

Now, what this does, it takes an $n$ as an input, does 100,000 trials of a simulation of the steps, and takes the average step amount.

Outputs

Definition 1: Each $n$ has:

1. an upperbound (called $n_\mu$),
2. a lowerbound (called $n_\lambda$),
3. an average (given by python; called $n_\alpha$),
   1. a lowerbound with $t$ trials (designated $n_\alpha^t$; supposedly more accurate with higher values of $t$, and
4. a real answer (called $n_\omega$).

Also let $s(n)$ be the seed of $n$, that is, the colour list original to $n$, and let $s_i(n)$ be the colour list on the $i$th step.

Definition 2: Let $c(b_i)$ designate the colour of ball $b_i$; any two balls selected for a given step are ordered in a coordinate pair, $(b_i,b_j)$. $b_i$ represents the ball at the $i$th position in $s(n)$. (I assume that a possible objective is to find $n_\lambda$ for an arbitrary $n$, perhaps using a function rule(s).)

Let's call this function $\Phi(n)$.

For $n=1$: $n$ is below the domain. I take it that that $1_\mu=1_\lambda=1$.

For $n=2$:

Theorem 1: $2_\mu=2_\lambda=1$ Proof. Suppose that $(b_0,b_1)$ is selected. Then, $b_0$ is coloured the same as $b_1$, $c(b_0)=c(b_1)$, and, since $\{b_0,b_1\}=s(2)$, we are done. Suppose the flipside is true, that $(b_1,b_0)$ is selected. Likewise, $b_1$ is coloured the same as $b_0$, $c(b_1)=c(b_0)$, and we are done. $■$

Theorem 2: For $n>2$, $n_\mu\le+\infty$.
Proof.
Since there is the possibility (though however unlikely) that we will experience a cyclic behaviour in the choosing of balls (e.g. choosing $(b_i,b_j)$, then choosing $(b_j,b_i)$, then choosing $(b_i,b_j)$...). $■$

($n_\alpha$ based on a $100$-sized sample unless otherwise specified. This will become less and less accurate as $n$ increases; i.e., it is sufficiently accurate for ideally small values of $n$, where typically $\left|\left\lfloor n_\alpha\right\rceil-n_\alpha\right|\ll 0$)

For $n=3$: $3_\alpha=3.99$. To arrive at $3_\lambda$, we choose an ideal scenario: Each trial, one ball is converted. So, in the first trial, there are $2$ different colours, then, in the last trial, there is only one colour. So, there are two trials. Also note, it seems that $n_\omega=4$; it is expected that every $n_\omega\approx n_\alpha$.

Theorem 3: $n_\lambda=n-1$.
Proof.
This states that the absolute minimum for any $n$-bag is $n-1$. Consider that, before there are any balls painted, $n$ colours. Then, ideally, on turn $1$, there are $n-1$ balls. On turn $2$, there are $n-2$ balls, etc. So, on the $k$th turn, there are ideally $n-k$ colours left among the balls. Thus, on the $n-1$th turn, there are ideally $n-(n-1)=n-n+1=1$ colours left, and, since no lower number is possible for a remainder of colours, $n-1$ must be the last ideal turn.$■$

Definition 2: $I(n)=n-1$. (The Ideal function)

Note: The first claim is essentially proven in an ideal scenario; for a bag of $n$ balls of $n$ different colours, ideally, the time expected in an idealist scenario is $n-1$ minutes. Obviously, for $n\in\mathbb Z \land n>1$, as the other cases are trivial/impossible.

From now on, the results are computer-aided more. For $n=4$, $n_\alpha=9.00172^{10^5}$. We can infer that $n_\omega=9$.

n      = 4
trials = 1
4:9.0
Continue...
n      = 4
trials = 10
4:8.8
Continue...
n      = 4
trials = 100
4:8.96
Continue...
n      = 4
trials = 1000
4:9.024
Continue...
n      = 4
trials = 10000
4:9.0131
Continue...
n      = 4
trials = 100000
4:9.00172
Continue...

For $n=5$, $n_\alpha^{10^5}=16.00694$, and seems to imply $n_\omega=16$.

n      = 5
trials = 1
5:11.0
Continue...
n      = 5
trials = 10
5:13.7
Continue...
n      = 5
trials = 100
5:16.87
Continue...
n      = 5
trials = 1000
5:16.313
Continue...
n      = 5
trials = 10000
5:16.1092
Continue...
n      = 5
trials = 100000
5:16.00694
Continue...

(the code you see here is as follows:

while True:
    n=int(input("n      = "))
    t=int(input("trials = "))
    print(str(n)+":"+str(s(t,n)))
    input("Continue...")

; that is, the code used to find certain values of $n_\lambda^t$.)

I thereby conclude that $\Phi(n)=(n-1)^2$.

Tabulated Results

(also see here) $$\begin{array}{c|c|c|c|c}n&n_\omega&t&n_\alpha^t&(n-1)^2\\\hline 1&0&\varnothing&0&0\\ 2&1&\varnothing&1&1\\ 3&4&10^2&3.99&4\\ 4&9&10^5&9.00172&9\\ 5&16&10^5&16.00694&16 \end{array}$$

---

A Formal Proof

The former is a proof leaning on computers and their results. I want to find a mathematical proof of this fact.

We know the answer is $(n-1)^2$ (or at least, as it seems), so all that needs to be done is to prove it.

But first, what does the result being $(n-1)^2$ signify? (Note that this is my thought process; this does not yet reveal an actual answer.)

Doing some preliminary research, I found an interesting identity which holds for $k\le n$: $$(x+y)^n=\sum_{k=0}^n\binom nk x^{n-k}y^k$$ I thought this might yield some information, yet it revealed nothing new.

(WIP)

Answer 3

The answer is

$\binom{n}{2}$

Let's say $a(i)$ is the total of "rounds" in which the $i_{th}$ colour is present, before the colour $i$ disappears or becomes the only one.
This is equivalent to the Gambler's ruin problem, where the expected time of $a(i)$ is $n-1$.
We also believe in the linearity of expectation, and we already know that the colours are $n$ and the expectation of $a(n)$ is $n-1$.
Thus, we can deduce that the expected time $t(n)$ to make all the balls of the same colour is:

$t(n)=\frac{n(n-1)}{2}=\binom{n}{2}$

Why did we divide by $2$? Simply because each "round" involves two different colours!

Big credits to @Russ Woodroofe for his solution here