MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of balls in a bin at the end of the process), where tight concentration bounds on $w_{max}$ are given as a function of $m$ and $n$.

My question is: can one provide similar bounds on the $w_{min}$, or even better, provide a good estimate of the distribution of $w_{min}$. Clearly, one can upper-bound the LHS-tail of the distribution of $w_{min}$, using the standard Chernoff and union bounds, but this is not good enough for what I need.

Generalizing this even further, I want to estimate the following: let $k \in \{1,\ldots,n\}$, I am interested in estimating the concentration of weight of a randomly sampled set bins of size $k$ containing the minimal-load bin.

share|cite|improve this question
Suppose we find $P_r$("at least e bins out of m are empty after the n balls have been thrown"); will that suffice? 0 in any case is the lower lim of $w_{min}$ – ARi Jul 5 '13 at 12:13
..."Previous work has been done on estimating the value of the maximum load" : any references ? – ARi Jul 5 '13 at 12:51
As it turns out, one could use the Poisson approximation to estimate the distribution of the minimum load. (cf. Corollary 5.11 in p. 103 in link. Asked a similar question about $n$ Poisson variables in a separate post:link – JoelO Jul 9 '13 at 20:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.