The (1+beta)-Choice Process and Weighted Balls into Bins

  • Yuval Peres
  • Kunal Talwar
  • Udi Wieder


Published by Society for Industrial and Applied Mathematics

Suppose m balls are sequentially thrown into n bins where each ball goes into a random bin. It is well-known that the gap between the load of the most loaded bin and the average is roughly sqrt(mlogn/n), for large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to O(log log n) independent of m. Consider now the following (1+beta)-choice” process for some parameter beta in [0,1]: each ball goes to a random bin with probability (1-beta) and the lesser loaded of two random bins with probability beta. How does the gap for such a process behave? Suppose that the weight of each ball was drawn from a geometric distribution. How is the gap (now defined in terms of weight) affected?

In this work, we develop general techniques for analyzing such balls-into-bins processes. Specifcally, we show that for the (1 + beta)-choice process above, the gap is O(log n/beta), irrespective of m. Moreover the gap stays at the same in the weighted case for a large class of weight distributions. No non-trivial explicit bounds were previously known in the weighted case, even for the 2-choice paradigm.