5
$\begingroup$

Setting: Assume I have $n$ buckets, where each can hold $w$ balls and initially there is one ball in each bucket. I do the following. I keep taking one ball from a random bucket and I put it into another random bucket. I do this $l$ times. I want to figure out with what probability one of the buckets will overflow, i.e. what the probability is that at some point I try to put more than $w$ balls into some bucket. Furthermore, I would like to know how large the buckets need to be s.t. the probability of such an overflow is below a threshold.

Question: I have trouble deciding what the correct approach to this problem is and it's somehow not clear to me how, generally, to decide what approach to take. There are several methods that seem somewhat unrelated, yet useful for this problem.

Approaches: For instance, I could look at an arbitrary, but fixed bucket and try to use the binomial formula to compute the probability that I will put $k$ out of $l$ balls into a specific bucket. However, I'm not sure how to consider the fact that I don't just put balls into buckets, but also remove them randomly. Also, I'm not sure whether looking at one bucket is really the same as looking at all of them.

Another, to me seemingly totally independent, approach would be to compute the expected value for the number of balls in a bucket (which should be 1) and then use the Chernoff bound to bound the probability that a specific bucket will overflow. Here, I'm not sure which Chernoff bound to use. There seem to be several very similar formulas, but I don't really understand the differences. Would I get some probability bound that depends on the number of iterations of my experiment, i.e. how often I randomly relocate a ball into some bucket?

$\endgroup$
3
  • $\begingroup$ @par I'm guessing OP wants to know the probability of overflowing in $k$ or less steps, otherwise the problem becomes trivial. OP, could you weigh in on this? $\endgroup$ Sep 5 '16 at 20:50
  • $\begingroup$ Yes, I think the overflow probability should be parameterized by the number of times I randomly reassign a ball to a new bin. So for instance, in my first approach I implicitly defined the number of rounds to be $l$. $\endgroup$
    – Cryptonaut
    Sep 5 '16 at 20:53
  • $\begingroup$ Hi again - I don't think you'll notified automatically when an answer on your question is edited, so here's this: I've just updated my answer to give a full solution (although not in closed form). Cheers! $\endgroup$ Sep 7 '16 at 18:38
3
$\begingroup$

EDIT: This is a combinatoric/thermodynamic approach. I will keep my first answer though, found below, because it was fun to write.


We have $N$ buckets and balls. After some number of steps, the system is in equilibrium (it starts out pretty much in equilibrium). In equilibrium, all microstates are assumed to be equally likely, but some macrostates are more abundant than others. By counting the total number of microstates, $\Omega$, as well as the number of microstates in which there is at least one bucket with $w$ or more balls in it, $\Omega_{\geq w},$ we can obtain the probability of having at least one bucket with $w$ or more balls in it, given as

$$P_{\geq w}=\Omega_{\geq w}/\Omega.$$

Now all we have to do is count these two.

$\Omega$ can be found via a simple application of stars and bars, giving $$\Omega=\binom{2N-1}{N}.$$

Figuring out $\Omega_{\geq w}$ is much more tricky. In fact, I couldn't do it, so I asked a question myself, the result of which (courtesy of Brian M. Scott) was

$$\Omega_{\geq w}=\sum_{i=1}^N(-1)^{i+1}\binom{N}i\binom{2N-1-iw}{N-1},$$

where any binomial coefficient with a negative argument is defined to be zero.

So

\begin{align} P_{\geq w}&=\Omega_{\geq w}/\Omega \\ {} \\ &= \frac{\sum_{i=1}^N(-1)^{i+1}\binom{N}i\binom{2N-1-iw}{N-1}}{\binom{2N-1}{N}}. \end{align}

You can see it plotted here for some different values of $N$ and $w$:

$N=30,w=10$:

enter image description here

$N=30,w=15$:

enter image description here

$N=30,w=25$:

enter image description here

Note that only $w$ really does something to the shape of the function. Compare, for instance, the following plot (in which $N=100,w=10$) with the first (in which $N=30,w=10$):

So there you have it! :)

enter image description here




Old answer:

Note: I'm a bit unsure of this approach (it seems too easy!), so if you, dear reader, would like to exercise some peer-review, I'd be grateful!


Consider one of the $n$ buckets. Let $X_t\leq n$ be the number of balls in this bucket after $t$ steps, with $X_0=1$.

In the $(t+1)$th step, there is a probability $\frac{1}{n-1}\left(1-\frac{X_t}{n}\right)$ that a ball is added, and a probability $\frac{X_t}{n}$ that a ball is removed.

We thus have

\begin{align} \langle X_1 \rangle&=\frac{1}{n-1}\left(1-\frac{X_0}{n}\right)(X_0+1)+\frac{X_0}{n}(X_0-1) \\ \\[-1pt] &=\frac{n+X_0^2(n-2)}{n(n-1)} \end{align}

We see that, given some number $X_{t-1}$, we have $$\langle X_t \rangle=\frac{n+X_{t-1}^2(n-2)}{n(n-1)}.$$

If we don't know the exact value of $X_{t-1}$, we should instead used the expected value of it, so we get

$$\langle X_t \rangle=\frac{n+\langle X_{t-1} \rangle^2 (n-2)}{n(n-1)},$$

which is a recursion that I unfortunately cannot solve. I can, however, do some numerical analysis, which shows that the expected value quickly drops to some value less than one. For instance, for $n=10$, the value $0.1122$ is reached after $t\sim 4$ (so very quickly), and it stays at that value thereafter, so it is a stable point.

We can find this stable point by finding the limit of our sequence. Since $\frac{n+x^2 (n-2)}{n(n-1)}$ is continuous, we have

\begin{align} L&=\lim_{k\rightarrow \infty} [a_k] \\ &= \lim_{k\rightarrow \infty} \left[\frac{n+a_{k-1}^2 (n-2)}{n(n-1)}\right] \\ &= \frac{n+\lim_{k\rightarrow \infty}\left[a_{k-1} \right]^2 (n-2)}{n(n-1)} \\ &= \frac{n+L^2 (n-2)}{n(n-1)} \quad \quad \implies \\ L&=\frac{n(n-1)-\sqrt{8n+n^2(n+1)(n-3)}}{2(n-2)}, \end{align}

so

$$\lim_{t\rightarrow \infty} [\langle X_t \rangle]=L.$$

$L(n)$ is a rather interesting function. You can see it below.

enter image description here

Note that $L(1)=\lim_{n\rightarrow 2}[L(n)]=1$ and $\lim_{n\rightarrow \infty} [L(n)]=0$, all of which makes intuitive sense.

Now, what does all this say about your question? Well, it seems that the probability for overflowing is vanishingly small, especially for large $n$, which is also what the principle of maximum entropy would suggest (the most likely state is one where the balls are "spread out" relatively evenly).

$\endgroup$
12
  • $\begingroup$ Hey thank you for the very detailed answer! I'll read it carefully in the next days and give you a proper answer. $\endgroup$
    – Cryptonaut
    Sep 7 '16 at 22:04
  • $\begingroup$ @user2585160 My pleasure! :) $\endgroup$ Sep 7 '16 at 22:07
  • $\begingroup$ @user2585160 Hey again, did you ever get a chance to read it? $\endgroup$ Sep 13 '16 at 20:24
  • $\begingroup$ doing that right now! :D $\endgroup$
    – Cryptonaut
    Sep 13 '16 at 20:25
  • $\begingroup$ @user2585160 Great! :D $\endgroup$ Sep 13 '16 at 20:27

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.