The One-Choice Process

The simplest randomised balanced allocation process is the \(\OneChoice \) process. Here, each ball is allocate to a bin chosen independently and uniformly at random. As each allocation is done independently it means that there is no coordination required between the bins.

The \(\OneChoice \) process:
Iteration: At each step \(t = 1, 2, \ldots \),

  • • Sample one bin \(i^t\) uniformly at random.

  • • Allocate one ball to \(i^t\), i.e., \(x_{i^t}^{t+1} = x_{i^t}^t + 1\).

It is well-known that for \(m \leq n \log n\) the gap is w.h.p. \(\frac {m}{n} + \Theta (\frac {\log n}{\log (\frac {n}{m} \cdot \log n)})\) and for \(m > n \log n\) it is \(\frac {m}{n} + \Theta (\sqrt {\frac {m}{n} \cdot \log n})\).

Your browser does not support the HTML5 canvas tag.