# Balanced Allocations: A Simple Proof for the Heavily Loaded Case

arXiv: https://arxiv.org/abs/1310.5367 · HTML: https://mlsanity.com/paper/1310.5367/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2013.

## Built on by (most cited first, 1 of 1)

- [Automating Food Drop: The Power of Two Choices for Dynamic and Fair Food Allocation](https://mlsanity.com/paper/2406.06363/) (2024)

## Abstract (arXiv)

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 log n, irrespective of the number of balls thrown. The theorem was first proven by Berenbrink et al. 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.