2
$\begingroup$

Let us fix a number of urns $n$ and a fixed capacity $c$. I would like to know which is the probability that $m$ balls, thrown at random in $n$ urns, "overflow", in the sense that at least one urn has assigned $\geq c$ balls.

There are several results in the literature about the maximum number of balls in an urn (in particular, Raab and Steeger's 1999 paper), but the results are all asymptotic with high probability. I need a precise analytical result.

$\endgroup$
  • $\begingroup$ Can you compute the probability that the first urn has more than $c$ balls? By linearity that gives you the expected number with more than $c$ balls, which is not the same as the probability that at least one has more than $c$ balls but is an indication if the probability is small. $\endgroup$ – Ross Millikan Feb 19 '18 at 16:02
  • $\begingroup$ People use asymptotic answers because the formulas get messy. One way to work it out is from the answer here: math.stackexchange.com/a/2117261/21585 $\endgroup$ – Louis Feb 20 '18 at 12:38
0
$\begingroup$

Hint:

Consider the equation $$x_1+x_2+...+x_n=m$$ where $x_i$ denotes the number of balls thrown in urn $i$. Now our question minds about cases where at least one $x_i$ is greater or equal to $c$. This is equivalent to find number of the answers of that equation where $x_1\ge c$ or the number of answers of the following equation$$(x_1-c)+x_2+...+x_n=m-c$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This does not reflect the times one bin gets more than $c$ nor the times more than one bin gets $c$. $\endgroup$ – Ross Millikan Feb 19 '18 at 16:03
  • $\begingroup$ Of course it does since there is no constraint on the rest of the $x_i$'s $\endgroup$ – Mostafa Ayaz Feb 19 '18 at 16:04
  • $\begingroup$ since $x_1-c=y_1\ge 0$ so it contains both cases $\endgroup$ – Mostafa Ayaz Feb 19 '18 at 16:05
  • $\begingroup$ The cases where more than one bin is overflowed is overcounted in this method (at least if you were thinking of taking the probability of $x_1\geq c$ and multiply by $n$). $\endgroup$ – Arthur Feb 19 '18 at 16:14
  • $\begingroup$ It's trivial that it does not work—just try $n=c=2$, $m=4$. $\endgroup$ – seba Feb 19 '18 at 20:04
0
$\begingroup$

The number of balls in each urn are Binomial($m,1/n$) distributed. They are independent conditioned on summing to $m$ (so in fact they are not independent at all, but all of their dependence is confined to this constraint). As a result, the overall joint PMF can be written as

$$f(x_1,\dots,x_n)=\begin{cases} Z^{-1} \prod_{i=1}^n {m \choose x_i} (1/n)^{x_i} (1-1/n)^{m-x_i} & \sum_{i=1}^n x_i=m \\ 0 & \text{otherwise} \end{cases}$$

where $Z$ is a normalization constant. Because $\prod_{i=1}^n (1/n)^{x_i} (1-1/n)^{m-x_i}$ does not depend on $\mathbf{x}$, this can be simplified to just

$$f(x_1,\dots,x_n)=\begin{cases} Z^{-1} \prod_{i=1}^n {m \choose x_i} & \sum_{i=1}^n x_i=m \\ 0 & \text{otherwise} \end{cases}$$

by taking a different (much larger) normalization constant. Now the probability of some overflow is $1$ minus the probability of no overflows. Thus the desired probability is

$$1-\sum_{x_1=0}^{c-1} \sum_{x_2=0}^{c-1} \dots \sum_{x_n=0}^{c-1} f(x_1,\dots,x_n).$$

These sums over constraint surfaces are always rather cumbersome, which is why you see asymptotic results all the time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I see, I made an equal probability assumption that is not valid. Lame. $\endgroup$ – Ian Feb 20 '18 at 10:44
  • $\begingroup$ Yep, I didn't specified “closed form”, but that's my problem. I have explicit bounds, too, but computing them, say, for $10^9$ balls, overflow at $10^4$ is out of question. $\endgroup$ – seba Feb 20 '18 at 14:30
0
$\begingroup$

It turns out that some information can be gathered by reversing the viewpoint, even in the case of non-uniform urns. Assume urn $i$ has probability $p_i$ of getting a ball. Consider an infinite ball-throwing process, in which balls are iteratively thrown into the urns. If you fix any window of $m$ balls, the number of balls going into urn $i$ has Poisson distribution with mean $mp_i$, and you are going to observe the same distribution when you throw $m$ balls. There are nice tail bounds for the Poisson distribution, and if $c$ is large enough they go down quite quickly, so you get a bound for urn $i$. You do the same for all urns and then apply the union bound.

| cite | improve this answer | |
$\endgroup$

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.