Homework 13

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

Problems

1. In this problem, we refine our balls-and-bins analysis from the lecture. Show that, for any integer $\ell \in \mathbb{N}$, the max load with $n$ balls and $m \geq n^{1 + 1/\ell}$ bins is at most $1 + 2 \ell$ with probability $\geq 1 - \frac{1}{n (1 + 2 \ell)!}$.

2. In this problem, we consider the special case where the number of balls equals the number of bins. Show that, for $n$ balls and $n$ bins,

   $$\text{max load}\leq O \left(\frac{\log{n}}{\log \log n}\right)$$

   with probability $\geq 1 - 1/n$. (For example, show that the max load is at most $10 \log ({n}) / \log \log n$ for sufficiently large $n$.)¹