Balls in Bins
   Nabil Mustafa

I will talk about properties of a process of allocating balls into
bins. One variant of such allocation is the following. Say there are N
bins, and a stream of N incoming balls. Pick each incoming ball and
allocate it to one of the bins, picked uniformly at random of all the
bins. Intuitively, each bin will, on the average, get one ball. So the
expected number of balls in a bin is one. Classically, it is known
that, with high probability, no bin gets more than O(log N / loglog N)
balls. First I give this (easy) result. The same question can be asked
for a different allocation procedure: for each incoming ball, two bins
are picked, uniformly at random, and the ball is placed in the bin
with the fewer number of balls. Surprisingly, now, with high
probability, no bin contains more than O(log log N) balls. This will
be the main described result of the talk.