twochoices

confirmedshipRust · CPUCluster & infrastructureJuly 16, 2026

the question

How does the maximum bin load scale when each of n balls picks the least loaded of d randomly sampled bins, for d in {1,2,3,4}?

what came out

Confirmed. With one choice the fullest bin climbed from 5 to 10 as n grew from 1e3 to 1e7 (~log n / log log n). Two choices stayed nearly flat at 3 to 4 (~log log n). The first extra choice cut worst-case load by 6, the second by 1, the third by 0.

method & receipts

Result: confirmed
Pre-registered — the prediction was written down and committed before the run.
Reproducible — one script re-runs the whole thing from scratch.
Tested — a correctness/benchmark suite ships alongside the code.

→ read the code and re-run it

github.com/v-code01/twochoices