In Section 3.13 we discussed the power of two choices for the balls and bins problem
with n bins. Instead of placing each ball in one random bin, we choose two random
bins for each ball, place it in the one that currently has fewest balls, and proceed in this
manner sequentially for each ball. Prove Equation (3.35).
Hint – the idea of the proof: Call Bi the number of bins with more than i balls at the
end. We wish to find an upper bound, βi for Bi. The probability that a ball is placed in
bin q with at least i + 1 balls in it is
It follows that the maximum number of balls in a bin is ln ln n ln 2 with high probability.