Answers are grounded in this paper and cite their sources.
We introduce a new class of balanced allocation processes that bias towards underloaded bins (those with load below the mean load) either by skewing the probability by which a bin is chosen for an allocation (probability bias), or alternatively, by allocating additional balls if an underloaded bin is sampled (weight bias). A prototypical process satisfying the probability bias condition is {Mean-Thinning}: At each round, we sample one bin and if it is underloaded, we allocate one ball; otherwise, we allocate one ball to a { second} bin sample. Variants of this process have been in use since at least 1986. An example of a process, introduced by us, which satisfies the weight bias condition is {Twinning}: At each round, we sample only a single bin. If the bin is underloaded, then we allocate two balls; otherwise, we allocate only one ball. Our main result is that for any process with a probability or weight bias, with high probability (w.h.p.), the gap between maximum and minimum load is logarithmic in the number of bins. This result holds for any number of allocated balls (heavily loaded case), covers many natural relaxations of the {Two-Choice} process, and we also prove that it is tight for many such processes, including {Mean-Thinning} and {Twinning}. Our analysis employs a delicate interplay between linear, quadratic and exponential potential functions. It also hinges on a phenomenon we call ``mean quantile stabilization'', which holds in greater generality than our framework and may be of independent interest.
No takes yet. Share an insight, caveat, or question.
Los et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: