Balanced Allocations: A Simple Proof for the Heavily Loaded Case

We provide a relatively simple proof that the expected gap between the maximum load and the average load in the two choice process is bounded by (1 + o(1)) log logn, irrespective of the number of balls thrown. The theorem was first proven by Berenbrink et al. in [2]. Their proof uses heavy machinery from Markov-Chain theory and some of the calculations are done using computers. In this manuscript we provide a significantly simpler proof that is not aided by computers and is self contained. The simplification comes at a cost of weaker bounds on the low order terms and a weaker tail bound for the probability of deviating from the expectation. 1 A Bit of History In the Greedy[d] process (sometimes called the d-choice process), balls are placed sequentially into [n] bins with the following rule: Each ball is placed by uniformly and independently sampling d bins and assigning the ball to the least loaded of the d bins. In other words, the probability a ball is placed in one of the i heaviest bins (at the time when it is placed) is exactly1 (i/n)d. We remark that using this characterization there is no need to assume that d is a natural number (though the process is algorithmically much simpler when d is an integer). The main point is that whenever d> 1 the process is biased: the lighter bins have a higher chance of getting a ball. In this paper we are interested in the gap of the allocation, which is the difference between the number of balls in the heaviest bin, and the average. Th