The balls into bins (or balanced allocations) problem is a classic problem in probability theory that has many applications in computer science. The problem involves m balls and n boxes (or "bins"). Each time, a single ball is placed into one of the bins. After all balls are in the bins, we look at the number of balls in each bin; we call this number the load on the bin. The problem can be modelled using a Multinomial distribution, and may involve asking a question such as: What is the expected number of bins with a ball in them?

Obviously, it is possible to make the load as small as m/n by putting each ball into the least loaded bin. The interesting case is when the bin is selected at random, or at least partially at random. A powerful balls-into-bins paradigm is the "power of two random choices" where each ball chooses two (or more) random bins and is placed in the lesser-loaded bin. This paradigm has found wide practical applications in shared-memory emulations, efficient hashing schemes, randomized load balancing of tasks on servers, and routing of packets within parallel networks and data centers.

Balls into bins problem

Random allocation

When the bin for each ball is selected at random, independent of other choices, the maximum load might be as large as However, it is possible to calculate a tighter bound that holds with high probability. A "high probability" is a probability , i.e. the probability tends to when grows to infinity.

Balls into bins problem

For the case , with probability the maximum load is:

Balls into bins problem

.

Gonnet

gave a tight bound for the expected value of the maximum load, which for is , where is the inverse of the gamma function, and it is known that .

The maximum load can also be calculated for , and for example, for it is , and for it is , with high probability.

Exact probabilities for small can be computed as for defined in OEIS A208250.

Partially random allocation

Instead of just selecting a random bin for each ball, it is possible to select two or more bins for each ball and then put the ball in the least loaded bin. This is a compromise between a deterministic allocation, in which all bins are checked and the least loaded bin is selected, and a totally random allocation, in which a single bin is selected without checking other bins. This paradigm often called the "power of two random choices" has been studied in a number of settings below.

In the simplest case, if one allocates balls into bins (with ) sequentially one by one, and for each ball one chooses random bins at each step and then allocates the ball into the least loaded of the selected bins (ties broken arbitrarily), then with high probability the maximum load is:

which is almost exponentially less than with totally random allocation.

This result can be generalized to the case (with ), when with high probability the maximum load is:

which is tight up to an additive constant. (All the bounds hold with probability at least for any constant .) Note that for , the random allocation process gives only the maximum load of with high probability, so the improvement between these two processes is especially visible for large values of .

Other key variants of the paradigm are "parallel balls-into-bins" where balls choose random bins in parallel, "weighted balls-into-bins" where balls have non-unit weights, and "balls-into-bins with deletions" where balls can be added as well as deleted.

Infinite stream of balls

Instead of just putting m balls, it is possible to consider an infinite process in which, at each time step, a single ball is added and a single ball is taken, such that the number of balls remains constant. For m=n, after a sufficiently long time, with high probability the maximum load is similar to the finite version, both with random allocation and with partially random allocation.

Repeated balls-into-bins

In a repeated variant of the process, balls are initially distributed in bins in an arbitrary way and then, in every subsequent step of a discrete-time process, one ball is chosen from each non-empty bin and re-assigned to one of the bins uniformly at random. When , it has been shown that with high probability the process converges to a configuration with maximum load after steps.