Balanced Allocations: A Simple Proof for the Heavily Loaded Case

摘要

We give a new proof for the fact that the expected gap between the maximum load and the average load in the two-choice process is bounded by (1 + o(1)) log log n, irrespective of the number of balls thrown. The original proof of this surprising result, due to Berenbrink et al. in, uses tools from Markov chain theory, and a sophisticated induction proof involving computer-aided calculations. We provide a significantly simpler and more elementary proof. The new technique allows us to generalize the result and derive new and often tight bounds for the case of weighted balls. The simplification comes at a cost of larger lower order terms and a weaker tail bound for the probability of deviating from the expectation.