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.

[Lester Mackey et.al]Matrix concentration inequalities via the method of exchangeable pairs; The second question of Poisson approximation can be answered by the result mentioned here (link.springer.com/article/10.1023/A:1022696125272) The third question of randomizing $k$ is no more than a two-layer hierachy model if I understand it correctly? $\endgroup$ – Henry.L Feb 22 '17 at 12:573more comments