Due Monday, March 30 at 5:00 PM. Please refer to the homework policy here.
In this problem, we refine our balls-and-bins analysis from the lecture. Show that, for any integer , the max load with balls and bins is at most with probability .
In this problem, we consider the special case where the number of balls equals the number of bins. Show that, for balls and bins,
with probability . (For example, show that the max load is at most for sufficiently large .)1