# Homework 15

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

## Problems

1. Consider the lecture notes. Where in the proof of Lemma 1.2 did we actually use 4-wise independence?
2. Suppose $n$ balls are thrown uniformly into $n$ bins with 4-wise independence. Show that for any fixed $\delta \in (0,1)$, the max-load is at most $O(n^{1/4} / \delta^{1/4})$ with probability at least $1-\delta$.
3. Let $X_1,\dots,X_n$ be a $k$-wise independent collection of $n$ random variables, where $k, n > 1$. Prove that conditional on $X_n = x_n$, for some fixed value $x_n$, the remaining variables $X_1,\dots,X_{n-1}$ are $(k-1)$-wise independent.