9
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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}$ $\endgroup$ – ARi Jul 5 '13 at 12:13
  • $\begingroup$ ..."Previous work has been done on estimating the value of the maximum load" : any references ? $\endgroup$ – ARi Jul 5 '13 at 12:51
  • $\begingroup$ ic.unicamp.br/~celio/peer2peer/math/balls-into-bins.pdf $\endgroup$ – JoelO Jul 5 '13 at 14:26
  • $\begingroup$ 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 $\endgroup$ – JoelO Jul 9 '13 at 20:12
  • $\begingroup$ @R B , The first question can have a tight bound for $w_{max},w_{min}$ simultaneously if we treat the throwing process as one transition and use the exchangeable pair technique mentioned in [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:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.