Another colored balls puzzle (part II)

Question

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:

1. You always paint the first ball the color of the second? Or...
2. 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.

Answer 1

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}$.

Answer 2

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.

Answer 3

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$.

Answer 4

For given $n$ it is possible to calculate the expected number of turns from an absorbing Markov chain on the integer partitions of $n$.

Each state of the Markov process corresponds to the ordered list of the number of equally colored balls. The matrix of transition probabilities between the states is easily calculated according to rules 1 or 2,

e.g. Removing from position 1, adding to position 2 : {3,1,1} -> {2,2,1}
with probability p = P(choosing position 1 out of all balls) * P(choosing position 2 out of remaining balls) =3/5 * 1/2

Given the transition matrix with the unique absorbing state {n} and the initial state {1,1,1,...,1} it is possible to calculate the expected number of turns before absorption.

This is done in the Mathematica program below. Here some results where the first number is n, the second the numerical result, and the third the exact fraction:

Rule 1

{{2, 1., 1}, 

{3, 4., 4}, 

{4, 10.3333, 31/3}, 

{5, 22.4852, 16729/744}, 

{6, 45.2173, 33913/750},

{7, 87.7733, 26707139046097/304274018880}, 

{8, 168.252, 129857255359868261/771803525388385},

{9, 322.292, 4555917617310039296830835441635/14135986803865219963776139264}, 

{10,620.346,822838635777324535445878391148603051494611/1326419190860455039655669536523314862820}}

Only the numerical values for n>10:

{{11, 1202.04}, {12, 2344.58}, {13, 4599.07}, {14, 9062.01},

{15, 17916.8}, {16, 35513.4},{17, 70522.1}, {18, 140231.},{19, 279122.}, {20, 555989.}}

Rule 2

{{2, 1., 1}, 

{3, 2.5, 5/2}, 

{4, 4.41667, 53/12}, 

{5, 6.6994, 2251/336}, 

{6, 9.31157, 866023/93005}, 

{7, 12.2249, 1009285097/82560060},

{8, 15.4166, 2246993235815929/145751872750176}, 

{9, 18.868, 2285085765293281062003190373/121108796080566797904702840}, 

{10, 22.5637, 618224636000595187350171250435705332105433100763641/27399140168645771065204844597274355963355735154297}}

Only the numerical values for n>10:

{{11, 26.4901}, {12, 30.6358}, {13, 34.9907}, {14, 39.546}, {15, 44.2936}, {16, 49.2266}, {17, 54.3383}, {18, 59.6231}, {19, 65.0754}, {20, 70.6904}}

Program:

(*
Defining Rule 1:
  input : lst = Partition of n , e.g. {5,3,2,1} with n=11
        k, m :  Positions to be changed ; remove ball from position k and add to position m
 output : list containing changed partition and probability for this change

 E.g. PartMove[{5, 3, 2, 1}, 1, 3] -> {{4, 3, 3, 1}, 5/33}
*)
PartMove[lst_, k_, m_] :=
 Module[{ll = lst, len = Plus @@ lst, prob},
  prob = (ll[[k]]/len*ll[[m]]/(len - ll[[k]]));
  ll[[k]] -= 1; ll[[m]] += 1;
  If[ll[[k]] == 0, ll = Drop[ll, {k}]]; {Reverse[Sort[ll]], prob}]

(*Alternatively
Defining Rule 2:
  input : lst = Partition of n , e.g. {5,3,2,1} with n=11
        k, m :  Positions to be changed ; add ball to position k and remove from  position m
 output : list containing changed partition and probability for this change

 E.g. PartMove[{5, 3, 2, 1}, 1, 3] ->   {{6, 3, 1, 1}, 5/33}
*)
 PartMove[lst_, k_, m_] :=
 Module[{ll = lst, len = Plus @@ lst, prob},
  prob = (ll[[k]]/len*ll[[m]]/(len - ll[[k]]));
  ll[[k]] += 1; ll[[m]] -= 1;
  If[ll[[m]] == 0, ll = Drop[ll, {m}]]; {Reverse[Sort[ll]], prob}]

  (*
Calculate all possible target partitions for a given partition with respective probabilities:
  input : lst = Partition of n , e.g. {5,3,2,1} with n=11

  output : list containing all possible changed partitions with their  probabilities
 Note: Depends on the chosen rule via PartMove

 E.g. for rule 1:
 Targets[{2, 1, 1}] -> {{{2, 2}, 1/6}, {{3, 1}, 1/3}, {{2, 1, 1}, 1/2}}
*)
  Targets[lst_] := Module[{len = Length[lst], pairs, res},
  If[len <= 1, {{lst, 1}},
   pairs = Select[Tuples[Range[len], 2], #[[1]] != #[[2]] &];
   res = Sort[PartMove[lst, #[[1]], #[[2]]] & /@ pairs];
    {#[[1, 1]], Plus @@ (#[[2]] & /@ #)} & /@ SplitBy[res, First]]]

(*  Define all possible states for chosen n (here n=4) *)

states = IntegerPartitions[4];

(* Define transition matrix PM for Markov chain *)
nn = Length[states];
Clear[PartIndex]; n = 1; (PartIndex[#] = n++) & /@ states;
PM = Table[0, {nn}, {nn}];
Do[(PM[[PartIndex[#[[1]]], k]] = #[[2]]) & /@
  Targets[states[[k]]], {k, 1, nn}]

(* Define submatrix Q for transient state changes *)
Q = (Drop[#, 1] & /@ Drop[PM, 1]);
(* Calculate fundamental matrix NPM of absorbing Markov chain*)
NPM = Inverse[ IdentityMatrix[Length[Q]] - Q];
(*Calculate expected number t of turns when starting from {1,1,..,1} = states[[-1]] *)
t = Plus @@ (#[[-1]] & /@ NPM);
{N[t], t} (*numerical and exact value of t*)

Answer 5

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

$[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}).$

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:$

$ [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]$

---

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.

Clearly

• $f(0,b)=0$
• for $w \gt 0$, $f(w,b)=1+\frac{w}{w+b}f(w-1,b+1)+\frac{b}{w+b}f(w+1,b-1)$ so

• $f(b,b)=1+f(b-1,b+1)$ and $f(b-1,b)=\frac{2b-1}{b-1}(1+f(b-2,b+1))$.

  For fixed $n=b+w$ this system of equations is sufficient to find all the values $f(w,n-w)$

  formulas

  The first two observations above are

  • $g(0)=0$
  • For $w \gt 0$, $g(w)=1+\frac{w}{n}g(w-1)+\frac{n-w}{n}g(w+1)$

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

$g(0)=0$

$g(1)=Z$ (by fiat) but also

$g(1)=1+\frac{n-1}{n}g(2)+\frac{1}{n}g(0)$ so $g(2)=\frac{n}{n-1}Z-\frac{n}{n-1} $

$g(2)=1+\frac{n-2}{n}g(3)+\frac{2}{n}g(1)$ so with a little work: $g(3)=\frac{n^2-2n-2}{(n-1)(n-2)}Z-\frac{n(2n-1)}{(n-1)(n-2)} $

$g(4)=\frac{n(n^2-5n+8)}{(n-1)(n-2)(n-3)}Z-\frac{n(3n^2-7n+8)}{(n-1)(n-2)(n-3)} $

$g(5)=\frac{n^4-9n^3+28n^2-32n+24}{(n-1)(n-2)(n-3)(n-4)}Z-\frac{n(4n^3-21n^2+47n-18)}{(n-1)(n-2)(n-3)(n-4)}$

This can be carried as far as desired. I satisfied myself that

$$g(w)=\frac{n^{w-1}-(\binom{n}{2}-1)n^{w-2}+o(n^{w-2})}{n^{w-1}-(\binom{n}{2})n^{w-2}+o(n^{w-2})}Z+o(n) \approx (1+\frac{1}{n}+\frac{w^2}{2n^2})Z.$$ This seems to agree well with the numerical calculations.

Numerical Results

The exact values of $f(b,b)$ for $1 \le b \le 19$ are

$1,8,37,{\frac {448}{3}},{\frac {1753}{3}},{\frac {11416}{5}},{\frac { 134471}{15}},{\frac {3713536}{105}},{\frac {4900661}{35}},{\frac { 35008504}{63}},{\frac {695863087}{315}},{\frac {10155396928}{1155}},{ \frac {121367279443}{3465}},$${\frac {898500004936}{6435}},{\frac { 1672315989611}{3003}},{\frac {100087214575616}{45045}},{\frac { 399474183415387}{45045}},{\frac {430350607437304}{12155}},{\frac { 15466270252272383}{109395}}$

and the base $2$ logs of these numbers are $0., 3., 5.20946, 7.22239, 9.19065, 11.1568, 13.1300, 15.1101, 17.0952, 19.0840, 21.0750,$$ 23.0678,25.0619, 27.0570, 29.0529, 31.0491, 33.0461, 35.0432, 37.0408$

For $20$ balls the exact expected number of steps to get to all the same color is

$555690+\frac{29}{63}={\frac {35008504}{63}},{\frac {35008441}{63}},{\frac {11669408}{21}}, {\frac {3889749}{7}},{\frac {1666984}{3}},{\frac {5000563}{9}},{\frac {4999360}{9}},{\frac {4994503}{9}},551880,524287,0.$

So $f(1,19)=2^{19}-1=524,287$ steps expected for a $1/19$ white/black split. An additional $27,593$ expected steps for $f(2,18)$ an $18/2$. In more detail the increases are $1., 3.44444, 7.66667, 17.0952, 43.2222, 133.667, 539.667, 3064.78, 27593, 524287 $ are the expected numbers of additional steps. So $f(10,10)$ is (of course) one more than $f(9,11)$ which is $3.44$ more than $f(8,12)$ etc.