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 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 .
  3. Let be a -wise independent collection of random variables, where . Prove that conditional on , for some fixed value , the remaining variables are -wise independent.