<p>This exact question is answered in this paper: <a href="https://arxiv.org/abs/1807.01804" rel="nofollow noreferrer">https://arxiv.org/abs/1807.01804</a></p>

CC BY-SA 4.0
2020-02-10T09:09:45.220Z
2020-02-10T09:09:45.220Z
Rob Johnson
<p>Here's the lower bound that OP asks for.  It may give some intuition for an upper bound as well.</p>

<p><strong>Lemma 1.</strong> <em>The random process described in the post moves on average at least <span class="math-container">$2n/(m+1)$</span> balls per time step.  That is, for large <span class="math-container">$N$</span>, the expected number of balls redistributed in the first <span class="math-container">$N$</span> steps is at least <span class="math-container">$(2n/(m+1))$</span> per step.</em></p>

<p><em>Proof.</em>  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.  </p>

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

<p>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.)</p>

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

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

<p>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 <span class="math-container">$d_{ij}$</span>'s.  In the correspondingly modified outcome, every given ball is redistributed no less often than it was (that is, in the first <span class="math-container">$N$</span> time units, if a ball was redistributed, say, <span class="math-container">$Q$</span> times, then in the modified outcome it will be redistributed at least <span class="math-container">$Q$</span> 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 <em>every</em> outcome in this way, yielding a new random experiment, in that new experiment the expected rate of ball redistributions is at least <span class="math-container">$2n/(m+1)$</span> per time step.  </p>

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

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

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

<p>The effect is equivalent to exchanging bins <span class="math-container">$t$</span> and bins <span class="math-container">$t+k$</span> 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: <em>What "equivalent" means here requires some elaboration. The modified process can be described as follows.  At each time <span class="math-container">$t$</span>, 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.)</em></p>

<p>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 <span class="math-container">$2n/(m+1)$</span>.<span class="math-container">$~~~~\Box$</span></p>

<p><strong>Remarks.</strong> 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 <span class="math-container">$2n/(m+1)$</span>.  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 <span class="math-container">$n/m$</span> is at least a large constant. There seem to be two effects.  First, in each step, the discrepancy <span class="math-container">$E$</span> (the number of balls moved in that step) should be small in expectation (maybe <span class="math-container">$O(\sqrt{n/m\log m})$</span> or less?).  Second, the distance <span class="math-container">$k$</span> that the <span class="math-container">$E$</span> balls are moved by the adversary (from the maximally occupied bin <span class="math-container">$t+k$</span> to the bin <span class="math-container">$t$</span>) should be small in comparison to the average random jump size <span class="math-container">$\Theta(m)$</span>, because the larger bins are the ones closer to bin <span class="math-container">$t$</span>.  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 <span class="math-container">$n/m$</span> is a large enough constant).  And if so the average ball-redistribution rate will also increase negligibly.  I think.</p>

<p>On the other hand, if <span class="math-container">$n/m$</span> is a small constant, the lower bound of <span class="math-container">$2n/(m+1)$</span> could be off by a constant factor larger than 1.  Consider e.g. <span class="math-container">$2n/(m+1) &lt; 1$</span>.  In the round-robin process, the expected number of balls in a bin that is about to be redistributed is about <span class="math-container">$2n/(m+1)$</span>, but in OP's process it is always at least 1. If <span class="math-container">$2n/(m+1)$</span> 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.</p>

CC BY-SA 4.0
2019-02-17T15:09:58.050Z
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
Mister R
CC BY-SA 4.0
2019-02-17T16:52:54.037Z
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)$.
Neal Young
CC BY-SA 4.0
2019-02-16T02:44:45.890Z
2019-02-16T21:42:20.117Z
2019-02-16T21:42:20.117Z
Neal Young
<p>Given <span class="math-container">$n$</span> balls and <span class="math-container">$m$</span> bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all <span class="math-container">$n$</span> balls are thrown, we take the balls from the bin with the maximum load, and throw them to random bins.</p>

<p>What the expected number of balls in the bin with the maximum load is converges to?</p>

<p>A variation of the problem is described in <a href="https://www.cs.tau.ac.il/~azar/box.pdf" rel="nofollow noreferrer">https://www.cs.tau.ac.il/~azar/box.pdf</a>, where instead of taken  the bin with the maximum load, a random ball is  selected at random.</p>

<p>In addition, by my experiments, it seems that for <span class="math-container">$n=\Theta(m)$</span> the bin with the maximum load converges <span class="math-container">$2n/m+1$</span> balls. I am trying to prove  it. </p>

CC BY-SA 4.0
2019-02-07T20:59:32.090Z
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?
Neal Young
CC BY-SA 4.0
2019-02-10T12:33:28.957Z
@NealYoung Of course--> it was meant to do for $N$ times where $N$ is approaches to infinity
Mister R
CC BY-SA 4.0
2019-02-10T12:36:59.277Z
@MisterR I see you deleted the duplicate question on [cs.se], thanks.
Discrete lizard
CC BY-SA 4.0
2019-02-12T13:27:46.547Z
Does it help to think of this as a Markov chain with a stationary distribution?
usul
CC BY-SA 4.0
2019-02-13T10:42:20.130Z
@usul tried to think about it that way. It was complex for me, even for $m=2$ bins
Mister R
<pr.probability>
Infinite process balls in bins problem
Mister R
# Infinite process balls in bins problem

(Asked by: username_0 on 2019-02-07)

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.

**Tags:** pr.probability

> **Comments:**
> **username_1**: 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?  
> **username_0**: @NealYoung Of course--> it was meant to do for $N$ times where $N$ is approaches to infinity  
> **username_2**: @MisterR I see you deleted the duplicate question on [cs.se], thanks.  
> **username_3**: Does it help to think of this as a Markov chain with a stationary distribution?  
> **username_0**: @username_3 tried to think about it that way. It was complex for me, even for $m=2$ bins  

---

## 2 answers

### Answer by username_4 on 2020-02-10. Score: 3 | Accepted answer

This exact question is answered in this paper: <https://arxiv.org/abs/1807.01804>


---

### Answer by username_1 on 2019-02-16. Score: 1

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.

> **Comments:**
> **username_0**: 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  
> **username_1**: 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)$.  

---

