Published
In this lesson
Wide tables, equations, and code scroll sideways. Swipe, or Tab to focus them and use the left and right arrow keys.
Power of two choices
You will learn: Explain how choosing the less loaded of two random bins suppresses high loads.
Start with: Events and probability · Expectation and variance
Uniform random allocation needs little coordination, but it can create crowded bins beside empty ones. A small change often makes the loads much more balanced: for each arriving ball, sample two bins and place it in the less loaded one.
This experiment compares that rule with ordinary one-choice allocation. Both see the same first candidate for each ball; the two-choice rule also sees a second independently sampled candidate. Sampling is with replacement, so both candidates can name the same bin. Equal loads are resolved by taking the first candidate.
Watch the decisions accumulate
Each ball samples two uniform bins independently with replacement. The one-choice rule uses the first; the two-choice rule uses the less loaded, taking the first on ties. Increasing the number placed continues the same candidate sequence.
Filled left: one choice. Open right: two choices. Total balls 20; average per bin 1.000000.
| Sample quantity | One choice | Two choices |
|---|---|---|
| Maximum load | 3 | 2 |
| Empty bins | 7 | 5 |
| Pairs sharing a bin | 9 | 5 |
Ball 20 sampled bins 7 and 1. Their two-choice loads before placement were 1 and 0; it entered bin 1. Repeated candidates are allowed.
| One-choice population quantity | Exact value | This one-choice sample |
|---|---|---|
| Expected empty bins | 7.169718 | 7 |
| Expected pairs sharing a bin | 9.500000 | 9 |
| Expected bins with k balls | 7.169718 | 7 |
| P(at least one shared bin) | 1 − 2.320196e-8 | Yes |
Inspect all bin loads
| Bin | One choice | Two choices |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 3 | 0 | 0 |
| 4 | 1 | 1 |
| 5 | 2 | 1 |
| 6 | 1 | 1 |
| 7 | 2 | 1 |
| 8 | 1 | 1 |
| 9 | 3 | 2 |
| 10 | 0 | 0 |
| 11 | 1 | 1 |
| 12 | 0 | 0 |
| 13 | 1 | 1 |
| 14 | 0 | 0 |
| 15 | 0 | 1 |
| 16 | 3 | 2 |
| 17 | 0 | 0 |
| 18 | 2 | 2 |
| 19 | 1 | 2 |
| 20 | 1 | 1 |
At the default twenty balls and twenty bins, the chosen seed gives maximum load three under one choice and two under two choices. Empty bins fall from seven to five, and sharing pairs from nine to five. These are observed values in one coupled comparison, not guaranteed outcomes for every seed.
The last-placement explanation reports both candidate bins, their loads immediately before placement under the two-choice process, and the selected bin. Add one ball to see the next decision. Changing the count reuses the same sequence prefix, so differences are caused by additional placements rather than resampling the earlier history.
Why two choices suppress high loads
Suppose a fraction f of bins currently have load at least h. Under one choice, the probability of sampling such a bin is f. Under two independent choices, the probability that both candidates have load at least h is f². A ball enters a bin already at level h or above only when both sampled loads are that high.
For instance, if one quarter of bins have load at least four, a one-choice ball reaches that set with probability 1/4. A two-choice ball reaches a bin at that level only if both candidates belong to the set, with probability 1/16. This is a calculation conditional on the current load vector. It explains the feedback that makes large loads harder to grow.
The argument does not make future placements independent. Each decision changes the load vector used by the next decision. Treating every step as an independent Bernoulli trial with a fixed success probability would lose that dependence.
A small worked placement
Suppose four bins currently have loads 2,1,0,1. If the sampled candidates are bins one and three, one choice puts the ball in bin one and raises its load to three. Two choices sees loads two and zero and selects bin three instead. If both candidates are bin one, the two-choice rule also raises that bin to three; it cannot choose an unseen empty bin.
Choosing the globally least-loaded bin would require inspecting all bins or maintaining additional information. The two-choice rule compares only the sampled candidates. Its benefit comes from this modest information gain, not from imposing perfect balance after every arrival.
What the large-system claim means
For the classical process with b balls placed into b initially empty bins, fully independent uniform choices, and fixed choice count two, the maximum load is of order log log b with high probability. Ordinary independent one-choice allocation has maximum load of order log b / log log b. These are asymptotic scale statements under a specific regime, not exact formulas for a twenty-bin experiment.
The mean load remains one in both processes when m = b, because the total number of balls is the same. The rules change the distribution of load across bins. When the sliders use m different from b, the mean changes to m/b, and the particular m = b asymptotic statement should not be applied unchanged.
Make a prediction
Could the independent one-choice empty-bin formula be used for the two-choice process just by substituting a new per-bin probability?
Explore the answer
Not in general. Two-choice decisions depend on current loads, so a bin’s selection probability changes with the entire allocation history. The one-choice Binomial(m,1/b) marginal and empty-bin formula rely on independent assignments with a fixed probability. The exact reference table is therefore explicitly limited to one choice.
Scope of this model
These are equal-size jobs arriving sequentially, with instantaneous knowledge of current loads and no departures. Unequal job sizes, stale load reports, constrained candidate sets, and service completion need different models. The display provides a transparent baseline rather than a performance guarantee for a particular production scheduler.
With one bin, both rules coincide. With no balls, both load vectors are zero. The sample comparison preserves these cases and includes repeated candidates and ties; it does not remove inconvenient allocations before reporting the maximum.
Reference
MIT’s two-choice analysis explains the high-load suppression argument and the need to account for dependence. Revisit balls in bins to derive the independent-allocation reference quantities shown here.