Expectation of time until all balls are removed

Question

I'm thinking on the next model:

• a circular tube with the opening is filled with two kinds of balls [let call them blue and white] and (at least one) free space(s)
• at discrete times each ball moves in the positive (counter-clockwise) direction, if there is a free space there.
• if blue ball is at the opening it is removed, i.e. new free space is introduced instead.

Denote by

• $n$ - the length of the tube (in balls)
• $k$ - the number of blue balls (initially)
• $f$ - number of free spaces (initially)

What is the expectation of time until all the blue balls removed, if initially we uniformly place blue balls and empty spaces in the tube? (as a function of $n, k, f$)

I've started from tackling $f=1$. Blue balls are uniformly spread on the circle [order statistics?], so they are at distance $\frac{n}{2k}, \frac{n}{2k} + \frac{n}{k}, \ldots$ from the opening. Free space is moving at the speed of $1$ per time unit and every single ball move $1$ step forward on one full circle of the free space.

I.e. first ball will leave after $\frac{n}{2k}$ full revolutions of free space (up-to, maybe, half first revolution), each taking $n$ time steps. In total $\frac{n^2}{2k}$ time steps. After the first ball is extracted, the second one is at distance $\frac{n}{k}$ from the opening, but now $2$ free spaces revolves, i.e. one full revolution moves every ball $2$ steps forward.

Then it will take $\frac{n^2}{2k}$ time steps. After that $\frac{n^2}{3k}$, $\frac{n^2}{4k}$ etc.

So, in total $O(\frac{n^2}{k}\log k)$ time steps. Kind of counter intuitive, that more balls could be taken out faster.

Same reasoning brings time to $O(\frac{n^2}{k}(\log k - \log f))$.

How can I formalize this approach? Is it even right?

Answer 1

I will post an answer, assuming $f=1$ and ignoring first partial revolution of the empty space [as in the Grand Scheme of things, this at most needs $n$ time steps]

We index possible ball placements starting from $0$ to $n-1$ in a counter-clockwise direction, starting from the location where balls could be removed from the tube.

Given $k$ blue balls placed at $a_1, a_2, \ldots, a_k$ we will want to evaluate how many steps does it take to remove all the balls.

We start with the first ball located initially at $a_1$. There is only one free space, that moves $1$ space per time step, hence each step "forward" for the first ball translates into one full revolution of the empty space. Therefore we will need an $a_1n$ time steps [plus, maybe, $1$ another step] to remove the first ball.

Note, that once the first ball from index $a_1$ reaches $0$, all the other balls made $a_1$ steps towards $0$. And now are located at $a_2 - a_1, a_3 - a_1, \ldots, a_k - a_1$. But there are now two empty spaces and the process is twice as fast. Now, the full revolution of the empty space encapsulates two steps "forward" by each remaining ball. And in $\frac{a_2-a_1}{2}n$ time steps next blue ball will be removed.

Third ball will be removed in another $\frac{a_3-a_2}{3}n$ steps, etc.

Denote, $\mathbf{b_1} = a_1, \mathbf{b_2} = a_2 - a_1, \ldots, \mathbf{b_i} = a_i - a_{i-1}, \ldots$. Then the total time needed to remove all the balls is given by

$$\sum\limits_{i=1}^k\frac{b_i}{i}n$$

See my answer, that evaluates total number of steps for all possible initial configurations of blue balls.

Then the expectation is just the average :

$$\mathbb{E}(\text{completion time}) = \frac{{{n}\choose{k+1}}H_k \cdot n}{{n}\choose{k}} = \frac{H_k}{k+1} n(n-k),$$

where $H_k$ is the $k$th harmonic number.

Next step would be to generalize for initially more free space ($f$). Like in the previous explanation, the time until the next (including first) blue ball will be removed is reciprocally proportional to the number of available free spaces at the "moment". Therefore the equation should become

$$\mathbb{E}(\text{completion time}) = \frac{H_{f+k-1} - H_{f-1}}{k+1} n(n-k)$$

I've run some MATLAB tests and for low values of $k$ this seem to be a plausible equation (see the image below).

Unfortunately, everything breaks for $k = O(n)$. In the extreme case setting $k=n-1$ should lead to completion time measured to be at most $2n$ and at least $n$.