Due Monday, April 6 at 5:00 PM. Please refer to the homework policy here.
- Consider the lecture notes. Where in the proof of Lemma 1.2 did we actually use 4-wise independence?
- Suppose balls are thrown uniformly into bins with 4-wise independence. Show that for any fixed , the max-load is at most with probability at least .
- Let be a -wise independent collection of random variables, where . Prove that conditional on , for some fixed value , the remaining variables are -wise independent.