What is the probability that throwing $m$ balls at random in $n$ urns at least one urn contains $c$ elements?

442 Views Asked by At

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.

2

There are 2 best solutions below

5
On

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$$

0
On

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.