Question: Suppose that we sequentially place balls into boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. What will be the maximum occupancy?
Test your intuition before reading the rest of the entry.
Answer: A beautiful theorem of Yossi Azar, Andrei Broder, Anna Karlin, and Eli Upfal asserts that with high probability, the fullest box contains only balls—exponentially less than before. (The descripion follows Xueliang Li’s mathscinet review.) And here is a link to the paper. Here is a related post “Balls and Bins on Graphs” on Windows on Theory.