What is the probability that throwing $m$ balls at random in $n$ urns at least one urn contains $c$ elements? 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.
 A: 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.
A: 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$$
A: 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.
