Still balls into bins.

Suppose there are N balls and N bins, with the power of two choices, i.e., for each ball, randomly select two bins and place the ball into the bin with least loads.

What's the probability for the maximum bin to have more than k balls?

Just want the expression between Probability, N and k.

Any more ideas?


  • 1
    $\begingroup$ What do you mean by, "with the power of two choices"? $\endgroup$ – Jonas Meyer May 7 '13 at 2:17
  • $\begingroup$ See: cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/… $\endgroup$ – Maazul May 7 '13 at 2:18
  • $\begingroup$ @JonasMeyer, that means each time randomly picking up two bins and placing the ball into least loaded bins $\endgroup$ – alexander May 7 '13 at 2:20
  • $\begingroup$ @Maazul, Hi, kinda of lost in the proof, since it prove with high probability, not with an expression. For the rough analysis, it is not exact probability. Does that mean for the same maiximum bin probability, the larger the N is, the larger k is? $\endgroup$ – alexander May 7 '13 at 2:24
  • $\begingroup$ Yes the proof implies that $k$ and $N$ are directly related for the same maximum bin probability but $k$ changes ridiculously slowly compared to $N$ in that case. $\endgroup$ – Maazul May 7 '13 at 2:34

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.