# 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,

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

1 Hint: first show that $k! \geq (k/2)^{(k/2)}$.