21
$\begingroup$

A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the first. Then, you put both balls back into the box. What is the expected number of times this needs to be done so that all balls in the box have the same colour?

Answer (Spoiler put through rot13.com): Gur fdhner bs gur dhnagvgl gung vf bar yrff guna a.

Someone asked me this puzzle some four years back. I thought about it on and off but I have not been able to solve it. I was told the answer though and I suspect there may be an elegant solution.

Thanks.

$\endgroup$
4
  • 5
    $\begingroup$ I think this question is borderline, but I would like to keep it open. It's borderline because you already know the answer, and that makes this more of a puzzle than a research question. On the other hand, I find "is there an elegant proof of this pretty combinatorial formula" to be a reasonable type of question. $\endgroup$ Oct 12, 2010 at 23:54
  • 4
    $\begingroup$ I first heard this problem at Mathcamp 2001. I believe the problem was invented there by Dave Savitt. I recall verifying it up to n=10 using linear relations among variables, one for each partition of n. Eventually, Dave and John Conway found a proof for all n. Their proof gave an explicit formula for the expected number of steps from any starting position, not just all distinct, and had a trivial inductive proof. IIRC, the formula involved harmonic numbers. While Ori Gurel-Gurevich's solution is very nice, I wonder if anyone can find the formula for all starting positions, which I have lost. $\endgroup$
    – aorq
    Oct 13, 2010 at 9:38
  • 4
    $\begingroup$ I certainly didn't invent the problem. IIRC I heard about it at a colloquium tea in the MIT common room (not 100% sure from whom, but maybe Greg Warrington?), put it aside at the time, and brought it out as a challenge problem at Mathcamp later that summer. The rest of Rex's story is accurate, I think. $\endgroup$
    – D. Savitt
    Oct 14, 2010 at 2:16
  • $\begingroup$ Of course, the mathematical solution is simple (though not elegant). I would like to see a more elegant solution. $\endgroup$ Oct 14, 2010 at 6:22

6 Answers 6

29
$\begingroup$

It can probably be done by looking at the sum of squares of sizes of color clusters and then constructing an appropriate martingale. But here's a somewhat elegant solution: reverse the time!

Let's formulate the question like that. Let $F$ be the set of functions from $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$ that are almost identity, i.e., $f(i)=i$ except for a single value $j$. Then if $f_t$ is a sequence of i.i.d. uniformly from $F$, and $$g_t=f_1 \circ f_2 \circ \ldots \circ f_t$$ then you can define $\tau= \min \{ t | g_t \verb"is constant"\}$. The question is then to calculate $\mathbb{E}(\tau)$.

Now, one can also define the sequence $$h_t=f_t \circ f_{t-1} \circ \ldots \circ f_1$$ That is, the difference is that while $g_{t+1}=g_t \circ f_{t+1}$, here we have $h_{t+1}=f_{t+1} \circ h_t$. This is the time reversal of the original process.

Obviously, $h_t$ and $g_t$ have the same distribution so $$\mathbb{P}(h_t \verb"is constant")=\mathbb{P}(g_t \verb"is constant")$$ and so if we define $\sigma=\min \{ t | h_t \verb"is constant"\}$ then $\sigma$ and $\tau$ have the same distribution and in particular the same expectation.

Now calculating the expectation of $\sigma$ is straightforward: if the range of $h_t$ has $k$ distinct values, then with probability $k(k-1)/n(n-1)$ this number decreases by 1 and otherwise it stays the same. Hence $\sigma$ is the sum of geometric distributions with parameters $k(k-1)/n(n-1)$ and its expectation is $$\mathbb{E}(\sigma)=\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)(1-\frac1{n}) = (n-1)^2 .$$

$\endgroup$
7
  • 1
    $\begingroup$ I do not take the point. Why $\sigma$ and $\tau$ have the same distribution? Equality of distributions at each time (not common distributions!), does it imply the equality oа distributions of the first stop? I do not think so. But hopefully we may fix it: expectation of $\sigma$ equals $\sum_{n=1}^{\infty} prob (\sigma\geq n)=\sum \prob(h_{n-1}\ne const)$, and in thi last we may replace $h$ to $g$. $\endgroup$ Oct 13, 2010 at 8:33
  • 5
    $\begingroup$ Aha! I now understand Ori's answer. At time $t$, considering all steps from step $t$ to the end, there will be $k$ balls whose colors are mapped to all the other balls at the end. Considering time step $t-1$, the only way to reduce $k$ is to choose two of these $k$ influential balls, and have the color of one mapped to that of another. This gives the recursion in his answer. Very nice, although it could be explained better. $\endgroup$
    – Peter Shor
    Oct 13, 2010 at 13:13
  • 3
    $\begingroup$ $P(\tau > t)=P(g_t \verb"is not constant")=P(h_t \verb"is not constant")=P(\sigma > t)$ $\endgroup$ Oct 13, 2010 at 17:08
  • $\begingroup$ Sorry I am a bit confused: 1. what is the domain and codomain of each f? Are we talking about a map between balls and colors, or just a transition between colors? Without this being clear I don't see why introducing the time reversal process is really magic. 2. In Peter's comment above, what are the ``influential balls"? At time t, if we define the influential balls to be the balls whose current color eventually wins in the end, then at time t+1 this number could increase, decrease or stays the same. Why do we have a geometric distribution? $\endgroup$
    – Ying Zhang
    Jun 27, 2014 at 16:45
  • $\begingroup$ 3. The choice of f being uniform from F at each step? Again this has to do with the definition of f. But this probably doesn't matter as long as the other steps make sense. $\endgroup$
    – Ying Zhang
    Jun 27, 2014 at 16:47
11
$\begingroup$

Consider just those sequences of selections that result in the final colour being $c$. If at some point during a sequence we have $k$ of the balls being this colour, we can define $E_k$ as the expected number of selections from here before all the balls are coloured $c$.

Doing this, we need to take account of the fact that not all selections are equally probable: each selection must be multiplied by the probability that it results in $c$ being the eventual colour. Happily, this probability is simply $k'/n$, where $k'$ is the number of balls coloured $c$ after this selection.

That gives us: $E_k = 1 + \frac{(k+1)(n-k)E_{k+1} + (k-1)(n-k)E_{k-1} + (n(n-1)-2k(n-k))E_k}{n(n-1)}$.

This simplifies to $2kE_k = \frac{n(n-1)}{n-k} + (k+1)E_{k+1} + (k-1)E_{k-1}$. We find from this that $E_1 = n/2 + E_2$, and generally if $E_{k-1} = w_{k-1}(n) + E_k$ then $E_k = w_k(n) + E_{k+1}$ with $w_k(n) = \frac{n(n-1)}{(n-k)(k+1)} + \frac{k-1}{k+1}w_{k-1}(n)$.

The required expectation, $E_1$, now resolves to:

$E_1 = \sum_{i=1}^{n-1}{w_i(n)}$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + \sum_{j=i+1}^{n-1}{ \prod_{k=i+1}^j{ \frac{k-1}{k+1} } }) }$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + \sum_{j=i+1}^{n-1}{ \frac{i(i+1)}{j(j+1)} }) }$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + i(i+1)(\frac{n-1}{n} - \frac{i}{i+1})) }$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{n} }$

$ = (n-1)^2$.

(Sorry, couldn't find how to get working multiline equations under jsMath, so I split them up.)

$\endgroup$
8
  • $\begingroup$ It took me a while to arrive at the same expression as you for $E_k$. Could you expand on how you determined this relation so quickly? $\endgroup$
    – anonuser01
    May 8, 2020 at 15:32
  • $\begingroup$ The essence is: we have k balls of our target colour, what will the effect of the next pick be? We're making a pick, hence the +1, and then calculating the chances that we'll then have respectively k+1, k-1 or k balls coloured c after the pick, in each case weighted by the chance that c will be the final colour in this case. $\endgroup$ May 9, 2020 at 18:23
  • $\begingroup$ By weighted, do you mean conditioned on the chance $c$ will be the final color? I arrived at the same equation, but it look me like a lot of work :(. I basically did $$ E[N_n] = \sum_{i=1}^{n} E[N_n|F_i]P(F_i) $$ where $F_i$ is the event that all balls will end up the $i-th$ color and $N_n$ is the number of steps needed to make all balls the same color. Thus we have $$ E[N_n] = E[N_n|F_1] = \cdots = E[N_n|F_n] $$ $\endgroup$
    – anonuser01
    May 9, 2020 at 19:47
  • $\begingroup$ Then I just worked with E[N_n|F_1]. So we can write $$ E[N_i|F_1] = 1 + \sum_{j = \{i+1, i, i-1\}} p_{ij}|F_1 E[N_j|F_1] $$ $p_{ij}$ is the transition probability from state $i$ to $j$ and we are conditioning this on $F_1$ $\endgroup$
    – anonuser01
    May 9, 2020 at 19:49
  • $\begingroup$ My $E[N_j]|F_1]$ is equivalent to your $E_j$. But yeah, it took me a lot more work to get to where you got. $\endgroup$
    – anonuser01
    May 9, 2020 at 19:51
7
$\begingroup$

This answer is inspired by JBL's comment on Aaron's answer:

Fix $n$, so that I don't have to include it in my notation. In all other respects, copy Aaron's notation. JBL observes that there appear to be numbers $f(1)$, $f(2)$, ..., $f(n-1)$ such that $$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$

We will show that such $f$'s exist, and give formulas for them. In particular, it will be clear that $f(1) = (n-1)^2/n$, proving the result. For convenience, we set $f(0)=f(n)=0$.


It seems best to describe the $f$'s by the following relation $$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$

Our proof breaks into two parts: showing that there is a unique solution to $(**)$ and showing that the resulting $f$'s obey $(*)$. We do the second part first.


We must establish the Markov relation: $$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$ For any $k$ in $\lambda$, the modified partition $\mu$ contains either $k-1$, $k+1$ or $k$, depending on whether we lost a ball of the corresponding color, gained one, or kept the same number. The probabilities of these events are $k(n-k)/n(n-1)$, $k(n-k)/n(n-1)$, and $1-2 k(n-k)/n(n-1)$, respectively.

So we must show that $$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)}{n(n-1)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)}{n(n-1)} f(k+1)\right).$$ Canceling $\sum_{k \in \lambda} f(k)$ from both sides, we must show that $$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). $$

By $(**)$, the defining equation of the $f$'s, this is $$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$~ as desired.

So, if we can find $f$'s obeying $(**)$, we will have $(*)$.


Let $g_j$ be the length $(n-1)$ vector $$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$ The key feature of $g_j$ is that $$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$ where we set $g_j(0)=g_j(n)=0$. Let $f$ be the vector $(f(1), f(2), \ldots, f(n-1))$.

Rewrite $(**)$ as $$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$ So we see that $$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$

In particular, $$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$ as desired. More generally, $$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) + \sum_{k=j}^{n-1} \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$


$\endgroup$
1
  • 3
    $\begingroup$ Barring arithmetic errors, we can also rewrite your final expression as $\frac{(2j - 1)(n - 1)(n - j)}{n} - (n - 1)(n - j) \sum_{k = 1}^{j - 1} \frac{1}{n - k}$, which does indeed look fairly simple in terms of harmonic numbers, as A. Rex remembered. $\endgroup$
    – JBL
    Oct 13, 2010 at 21:41
2
$\begingroup$

Just wish to add some sense to $f(k)$...

Let:

$X_{i}$ - the number of balls of the color $i$ at time $t=0$.

$A_{i}$ - the event that in the end all the balls are of the color $i$.

Using this notation:

$E(T|X_{1}=\lambda_{1},\ldots ,X_{n}=\lambda_{n}) = \sum E(1_{A_{i}}T|X_{1}=\lambda_{1},\ldots,X_{n}=\lambda_{n})$.

But $E(1_{A_{i}}T|X_{1}=\lambda_{1},\ldots,X_{n}=\lambda_{n})$ depends only on $\lambda_{i}$ and is denoted by $f(\lambda_{i})$.

Using "first step" analysis we get:

$E(1_{A_{i}}T|X_{i}=k)=dE(1_{A_{i}}(T+1)|X_{i}=k+1)+ dE(1_{A_{i}}(T+1)|X_{i}=k-1)+(1-2d)E(1_{A_{i}}(T+1)|X_{i}=k)$

where $d=\frac{k(n-k)}{n(n-1)}$

One may compute (using Doob's theorem or otherwise) that $E(1_{A_{i}}|X_{i}=k)=\frac{k}{n}$.

And using that we obtain David Speyer's equation (**) for $f(k)$.

$\endgroup$
1
$\begingroup$

For n=3, one turn takes you 2 of one color and 1 of another. To get to a single color you need to pick one of the 2 (prob=2/3), then pick the odd one (prob=1/2). So the expected number of turns is 1+3=4

$\endgroup$
0
$\begingroup$

edit I indeed was mistaken. The suggested answer is correct as far as I checked (n=10). It is easy enough to set up a system of equations for the expectations and compute. Here are the results to 6, the notation should be clear enough:

$$p_{12}=3,p_{111}=4 $$

$$p_{13}=11/2,p_{22}=7,p_{112}=8,p_{1111 }=9 $$

$$p_{14}={\frac {25}{3}},p_{23}={\frac {35}{3}} ,p_{1^23}={\frac {38}{3}},p_{12^2}=14,p_{1^32}=15,p_{1^5}=16 $$

` $p_{15}={\frac {137}{12}},p_{24}={\frac {101}{ 6}},p_{3^2}={\frac {37}{2}},p_{1^24}={\frac {107}{6}},p_{123} ={\frac {83}{4}}, p_{1^33}={\frac {87}{4}},p_{2^3}=22 ,p_{1^22^2}=23,p_{1^52}=24,p_{1^6}=25 $

AT least up to n=10, If two ones are replaced by a 2, the expected number of moves goes down by 1.

later in reply to a comment, here are results for 10. If anyone wants more, ask me. They are just kind of bulky at least the way I have them now. I think the notation should be clear.

[[1, 10], 81], [[1, 8], [2, 1], 80], [[1, 6], [2, 2], 79], [[1, 4], [2, 3], 78], [[1, 2], [2, 4], 77], [[2, 5], 76], [[1, 7], [3, 1], 623/8], [[1, 5], [2, 1], [3, 1], 615/8], [[1, 3], [2, 2], [3, 1], 607/8], [[1, 1], [2, 3], [3, 1], 599/8], [[1, 4], [3, 2], 299/4], [[1, 2], [2, 1], [3, 2], 295/4], [[2, 2], [3, 2], 291/4], [[1, 1], [3, 3], 573/8], [[1, 6], [4, 1], 2085/28], [[1, 4], [2, 1], [4, 1], 2057/28], [[1, 2], [2, 2], [4, 1], 2029/28], [[2, 3], [4, 1], 2001/28], [[1, 3], [3, 1], [4, 1], 3995/56], [[1, 1], [2, 1], [3, 1], [4, 1], 3939/56], [[3, 2], [4, 1], 955/14], [[1, 2], [4, 2], 951/14], [[2, 1], [4, 2], 937/14], [[1, 5], [5, 1], 3895/56], [[1, 3], [2, 1], [5, 1], 3839/56], [[1, 1], [2, 2], [5, 1], 3783/56], [[1, 2], [3, 1], [5, 1], 465/7], [[2, 1], [3, 1], [5, 1], 458/7], [[1, 1], [4, 1], [5, 1], 3529/56], [[5, 2], 1627/28], [[1, 4], [6, 1], 4399/70], [[1, 2], [2, 1], [6, 1], 4329/70], [[2, 2], [6, 1], 4259/70], [[1, 1], [3, 1], [6, 1], 16721/280], [[4, 1], [6, 1], 7883/140], [[1, 3], [7, 1], 15087/280], [[1, 1], [2, 1], [7, 1], 14807/280], [[3, 1], [7, 1], 3553/70], [[1, 2], [8, 1], 5869/140], [[2, 1], [8, 1], 5729/140], [[1, 1], [9, 1], 7129/280], [[10, 1], 0]

$\endgroup$
3
  • $\begingroup$ I agree with Ross Millikan's comment below. I have verified the claimed formula upto n=4. The only approach I can imagine for this problem is to draw out the Markov chain explicitly and find the expected time it takes for the chain to hit the one non-transient state. $\endgroup$
    – Hedonist
    Oct 12, 2010 at 23:48
  • $\begingroup$ I also confirm 4 for n=3. It's 1+1+2/3 +(2/3)^2+(2/3)^3 + .... I think you might have taken the ratio in the geometric series to be 1/3 be mistake. $\endgroup$ Oct 12, 2010 at 23:54
  • 1
    $\begingroup$ It seems very likely that there exist functions $f(n, k)$ such that $p_{\lambda} = \sum_{i} f(|\lambda|, \lambda_i)$. For example, it appears that $f(n, 1) = \frac{(n - 1)^2}{n}$ and $f(n, 2) = \frac{(2n - 1)(n - 2)}{n}$. Probably a little more data would be enough to guess the general form and proceed as in A. Rex's comment on the question. $\endgroup$
    – JBL
    Oct 13, 2010 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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