# The Two-Choice Process

An improvement over the $$\OneChoice$$ process is the $$\TwoChoice$$ process, where for each ball two bins are chosen uniformly at random and the ball is allocated to the least loaded bin.

The $$\TwoChoice$$ process:
Iteration: At each step $$t = 1, 2, \ldots$$,

• • Sample two bins $$i_1 = i_1^t$$ and $$i_2 = i_2^t$$ uniformly at random.

• • Allocate one ball to bin $$i^t \in \{ i_1, i_2 \}$$ such that $$y_{i^t}^{t+1} = \min \{ x_{i_1}^t, x_{i_2}^t \}$$.

Azar, Broder, Karlin and Upfal (1999) (and implicitly Karp, Luby and Meyer auf der Heide (1996)) showed that the $$\TwoChoice$$ process achieves w.h.p. an $$\log _2 \log n + \Theta (1)$$ gap, which is an exponential improvement over the $$\Theta (\frac {\log n}{\log \log n})$$ gap of $$\OneChoice$$. Berenbrink, Czumaj, Steger and Vöcking (2006) extended the analysis to the heavily-loaded case (for any $$m \geq n$$) proving a gap of $$\log _2 \log n + \Theta (1)$$.

Your browser does not support the HTML5 canvas tag.

.

#### Power of two-choices

The difference in the gap of the $$\OneChoice$$ and $$\TwoChoice$$ process is known as the “power of two choices" phenomenon.

One-Choice

Your browser does not support the HTML5 canvas tag.

Two-Choice

Your browser does not support the HTML5 canvas tag.

#### References

•   Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM J. Comput., 29(1):180–200, 1999.

•   Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. Balanced allocations: the heavily loaded case. SIAM J. Comput., 35(6):1350–1385, 2006.

•   Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. Algorithmica, 16(4-5):517–542, 1996.