Homework 13

Due Monday, March 30 at 5:00 PM. Please refer to the homework policy here.


  1. 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 .

  2. 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


1 Hint: first show that .