In this question we analyze a contention resolution system in a balls-and-bins framework. We have n resources (bins) and n jobs (balls); we allocate resources to jobs in rounds. In the first round, we throw all the n balls into n bins uniformly at random. After round i ≥ 1, we remove every ball that occupies a bin by itself in round i, and in the next round, i + 1, we throw the remaining balls into the n bins. (One can imagine the lonely balls getting service, whereas none of the colliding ones receive service.) The process continues until no balls are left. Prove that this process runs for at most c log log n rounds with high probability, where c is some constant. (Hint: Keep track of the number of balls remaining after every round.)
