Balls in bins

You will learn: Derive occupancy expectations and distinguish sharing pairs from collision probability.

Start with: Events and probability · Expectation and variance

Put twenty balls independently and uniformly into twenty bins. The average load is exactly one, but there is no reason for each bin to get one ball. Some bins are empty and others contain several balls. Random allocation spreads individual choices without enforcing a balanced result.

The model has b bins and m distinguishable balls. Each ball chooses one bin uniformly, independently of every other ball. There are no capacity limits or removals. The display records the actual load vector and compares selected statistics with their expectations over repeated allocations.

Place balls and inspect the load vector

Number of bins 20.00 Balls placed 20.00 Random seed 109.00

Each ball independently chooses one of the bins uniformly. Every bin can receive more than one ball. Increasing the number placed continues the same candidate sequence.

Bars show this sample, not expected bin loads. Total balls 20; average per bin 1.000000.

Sample quantity	One choice
Maximum load	3
Empty bins	7
Pairs sharing a bin	9

Occupancy k to count 0.00

One-choice population quantity	Exact value	This one-choice sample
Expected empty bins	7.169718	7
Expected pairs sharing a bin	9.500000	9
Expected bins with k balls	7.169718	7
P(at least one shared bin)	1 − 2.320196e-8	Yes

Inspect all bin loads

Bin	One choice
1	0
2	1
3	0
4	1
5	2
6	1
7	2
8	1
9	3
10	0
11	1
12	0
13	1
14	0
15	0
16	3
17	0
18	2
19	1
20	1

Sequential unit-size allocations with no removals. Exact expectations shown apply only to independent one-choice allocation. A single comparison is not a guarantee that two choices improve every statistic on every sample.

The default sample has maximum load three, seven empty bins, and nine unordered ball pairs sharing a bin. Those are sample results for the displayed seed. The exact expected empty-bin count is about 7.1697184, and expected shared-pair count is 9.5. Neither expectation must be an integer or match one sample exactly.

“Place next ball” continues the existing candidate sequence. Reducing the number of placed balls lets you inspect an earlier prefix. The button matching balls to bins sets mean load to one; it does not place one ball deliberately in each bin.

The load in one bin

Focus on a particular bin. Each of the m balls enters it with probability 1/b, independently across balls, so its load has a Binomial(m,1/b) distribution. The probability of exactly k balls is C(m,k)(1/b)ᵏ(1 − 1/b)ᵐ⁻ᵏ.

Multiply by b to obtain the expected number of bins containing exactly k balls. This uses linearity of expectation across bin indicators; it does not require the bin loads to be independent. They are dependent because their sum is fixed at m. A large load in one bin leaves fewer balls available for the others.

Set k = 0 to get expected empty bins b(1 − 1/b)ᵐ. For twenty balls and twenty bins, this is 20(19/20)²⁰, about 7.17. As b grows with m = b, the expected empty fraction approaches e⁻¹. An average of one still leaves roughly 37% empty in that limiting regime.

Count collisions without double-counting the question

Each unordered pair of balls has probability 1/b of landing together. There are m(m − 1)/2 pairs, so the expected number of sharing pairs is m(m − 1)/(2b). A bin containing four balls contributes six pairs, not one. Thus “number of sharing pairs,” “number of occupied bins with multiple balls,” and “whether any collision happened” are different statistics.

For m no greater than b, no collision has probability (b/b)((b − 1)/b)···((b − m + 1)/b). The first ball can go anywhere; each later ball must avoid all previously occupied bins. Subtracting this product from one gives the probability of any collision. If m exceeds b, collision is certain by the pigeonhole principle.

At m = b = 20, the collision probability is approximately 0.9999999768. This does not mean every bin is crowded; the same sample can have many empty bins. Crowding in some locations and absence in others are compatible consequences of independent choices.

Make a prediction

Can you multiply the probabilities that individual bins are empty to calculate the probability they are all empty?

Explore the answer

No. The empty-bin indicators are dependent. With any positive number of balls, all bins being empty is impossible. For two specified bins, their joint empty probability is (1 − 2/b)ᵐ when b is at least two, not the product of their individual empty probabilities.

The maximum is a different object

Mean load m/b is fixed for every allocation. Maximum load is random and depends on the joint vector of loads. Neither the mean of one bin nor the expected number of sharing pairs directly determines it. The chart shows a sample maximum and does not label it an exact expected maximum.

With zero balls, every bin is empty and collision probability is zero. With one bin, all balls go there. Values of k exceeding m are impossible. Extremely small positive expected bin counts are displayed logarithmically if ordinary floating-point arithmetic would underflow to zero.

Reference and next step

MIT’s balls-in-bins notes develop load distributions and maximum-load analysis. Continue to the power of two choices, where each ball uses a little load information before choosing its bin.

Reset all settings