6
$\begingroup$

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the maximum load, and throw them to random bins.

What the expected number of balls in the bin with the maximum load is converges to?

A variation of the problem is described in https://www.cs.tau.ac.il/~azar/box.pdf, where instead of taken the bin with the maximum load, a random ball is selected at random.

In addition, by my experiments, it seems that for $n=\Theta(m)$ the bin with the maximum load converges $2n/m+1$ balls. I am trying to prove it.

$\endgroup$
  • $\begingroup$ In the random experiment, how many times does it do the step "take the balls from the bin with the maximum load, and throw them to random bins"? Just once? (I assume not, because surely the second-fullest bin will be almost as full.) Until all bins have the same number of balls (within 1)? (I assume not, because I'm guessing that this will happen eventually with probability 1, and if so it would trivialize your problem.) Perhaps you mean to do it $N$ times for some $N\rightarrow\infty$, and ask what the max load is at the end? $\endgroup$ – Neal Young Feb 7 at 20:59
  • $\begingroup$ @NealYoung Of course--> it was meant to do for $N$ times where $N$ is approaches to infinity $\endgroup$ – Mister R Feb 10 at 12:33
  • 1
    $\begingroup$ @MisterR I see you deleted the duplicate question on Computer Science, thanks. $\endgroup$ – Discrete lizard Feb 10 at 12:36
  • $\begingroup$ Does it help to think of this as a Markov chain with a stationary distribution? $\endgroup$ – usul Feb 12 at 13:27
  • $\begingroup$ @usul tried to think about it that way. It was complex for me, even for $m=2$ bins $\endgroup$ – Mister R Feb 13 at 10:42
1
$\begingroup$

Here's the lower bound that OP asks for. It may give some intuition for an upper bound as well.

Lemma 1. The random process described in the post moves on average at least $2n/(m+1)$ balls per time step. That is, for large $N$, the expected number of balls redistributed in the first $N$ steps is at least $(2n/(m+1))$ per step.

Proof. First consider a modified process that, instead of redistributing the balls from a bin with maximum occupancy at each time step, redistributes the balls from the bin that has least-recently been redistributed. That is, it chooses the bins in round-robin fashion.

When a given ball is redistributed at some time $t$, for each $d\in\{1,2,\ldots,m\}$, with probability $1/m$, the ball will land into the bin that will be next redistributed at time $t+d$. Hence, in expectation, the number of time steps between redistributions of the ball is $\sum_{d=1}^m (d-1)/m = (m-1)/2$, that is, the ball is redistributed in expectation once every $1+(m-1)/2 = (m+1)/2$ time steps. Since there are $n$ balls, in this modified (round-robin process), the average number of balls redistributed per time step is $2n/(m+1)$.

Now we relate this process to the original process by a coupling argument to show that, in the original process, balls are redistributed at least as fast. (I think I've got this right, but perhaps I'm making some subtle error.)

First, reimagine the modified (round-robin) process. Instead of using bins $1,2,\ldots,m$ over and over, use infinitely many bins $1,2,\ldots$ as follows. When a bin $t$ is redistributed, replace it with (new, empty) bin $t+m$. In this way, at any given time $t$, the bins in play are $t, t+1, \ldots, t+m-1$. The balls in bin $t$ are distributed randomly into bins $t+1, t+2,\ldots, t+m$ (and possibly into the new empty bin $t+m$). This is just renaming the bins over time, so does not change the rate of redistribution of the balls.

Next, define the signature of an outcome of this random process to be the collection of signatures of the balls, where, for each ball $b\in\{1,2,\ldots,n\}$, the signature of ball $b$ is $d_{b1}, d_{b2}, d_{b3}, \ldots$, where $d_{bj}$ is the amount that ball $b$'s bin number increases in its $j$'th relocation. Assume WLOG that all balls start in bin 1. So, ball $b$'s successive bin numbers are $1, 1+d_{b1}, 1+d_{b1}+d_{b2}, \ldots$. (The $d_{bk}$ are i.i.d. uniformly in $\{1,2,\ldots,m\}$, although we won't use this fact much.) The signature determines, and is determined by, the outcome of the random experiment.

Now consider any single outcome of the (round-robin) random experiment, and its corresponding signature. Suppose an adversary changes the signature (and, correspondingly, the outcome) by decreasing one or more $d_{ij}$'s. In the correspondingly modified outcome, every given ball is redistributed no less often than it was (that is, in the first $N$ time units, if a ball was redistributed, say, $Q$ times, then in the modified outcome it will be redistributed at least $Q$ times). So, the adversary's modification does not decrease the average number of ball-redistributions per time step. Likewise, if an adversary modifies the (round-robin) random experiment by changing every outcome in this way, yielding a new random experiment, in that new experiment the expected rate of ball redistributions is at least $2n/(m+1)$ per time step.

To finish, we argue that the original experiment (which chooses the bin to redistribute at each time step by choosing a bin with maximum occupancy) can be obtained by an appropriate action of the adversary, as follows.

Consider any outcome of the round-robin experiment, and modify it as follows. Replay the outcome (following the signature), for $t=1,2,\ldots$, as follows. At time $t$, bin $t$ is about to be redistributed into bins $t+1,t+2,\ldots,t+m$, let bin $t+k$ (with $0\le k \le m-1$) be a bin with maximum occupancy. Suppose there are $E$ more balls in bin $t+k$ than in bin $t$.

Choose any $E$ balls in bin $t+k$. For each of the $E$ balls $b$, the most-recent redistribution of ball $b$ (into bin $t+k$) was from a bin numbered less than $t$, so the corresponding signature entry $d_{bx}$ is at least $k+1$. Modify that signature entry, reducing it by $k$. Correspondingly, move each of these $E$ balls into bin $t$. (This modification swaps the sizes of bin $t$ and bin $t+k$.) Now proceed with the redistribution of all balls in bin $t$ (including those $E$ balls), following the signature of each ball as usual (so each ball $b$ jumps forward by the corresponding (unmodified) $d_{b,x+1}$).

The effect is equivalent to exchanging bins $t$ and bins $t+k$ before the redistribution. That is, the maximally occupied bin is redistributed at each time step (and each redistributed ball is independently assigned to a new random bin). Thus, the modified process is equivalent to the process described by OP. (EDIT: What "equivalent" means here requires some elaboration. The modified process can be described as follows. At each time $t$, the modified process chooses the least-recently-distributed bin, then moves balls from the largest bin into the chosen bin so that the chosen bin and the largest bin exchange sizes, then redistributes all balls from the chosen bin. This process is statistically equivalent to OP's original process, although the processes are different in that, for a given signature, they give different outcomes, which is an important distinction for the proof, as we compare the round-robin process to the modified process outcome by outcome, comparing the two outcomes that have the same signature.)

On the other hand, this is an adversarial modification as described above, so does not decrease the expected ball-redistribution rate. So, the process described by OP has expected ball-redistribution rate at least $2n/(m+1)$.$~~~~\Box$

Remarks. Assuming there is no subtle error here, it would be interesting to try to estimate the extent to which the modification increases the ball-redistribution rate above $2n/(m+1)$. When a bin in the round-robin process comes up for redistribution, the expected difference between its size and the largest size should be boundable, at least if $n/m$ is at least a large constant. There seem to be two effects. First, in each step, the discrepancy $E$ (the number of balls moved in that step) should be small in expectation (maybe $O(\sqrt{n/m\log m})$ or less?). Second, the distance $k$ that the $E$ balls are moved by the adversary (from the maximally occupied bin $t+k$ to the bin $t$) should be small in comparison to the average random jump size $\Theta(m)$, because the larger bins are the ones closer to bin $t$. Due to these factors, modifying the round-robin experiment as described above should decrease the average ball jump-length by a negligible amount (at least if $n/m$ is a large enough constant). And if so the average ball-redistribution rate will also increase negligibly. I think.

On the other hand, if $n/m$ is a small constant, the lower bound of $2n/(m+1)$ could be off by a constant factor larger than 1. Consider e.g. $2n/(m+1) < 1$. In the round-robin process, the expected number of balls in a bin that is about to be redistributed is about $2n/(m+1)$, but in OP's process it is always at least 1. If $2n/(m+1)$ is a small constant (but larger than 1), perhaps there is a similar effect: in the round-robin process the probability that the redistributed bin is empty is bounded below by a positive constant.

$\endgroup$
  • $\begingroup$ I will look in to the proof. The optimal value by our simulation was $2n/m+1=3$ and not $2$, for example $n=m$. I will need to check why it holds $\endgroup$ – Mister R Feb 17 at 15:09
  • $\begingroup$ That makes sense. Per the remark following the proof, I think it should be $(2+ \epsilon(n/m))n/m$ where $\epsilon(x)\rightarrow 0$ as $x\rightarrow\infty$. In other words, $2n/m + o(n/m)$. $\endgroup$ – Neal Young Feb 17 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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