Empty Boxes in Random Allocation

Consider the random placement of n labelled balls into m labelled boxes. If each placement is independent and uniform, there are mⁿ equally likely outcomes in the sample space. This module determines the probability distribution of the number of empty boxes.

Worked Example

Let m = 3 boxes and n = 2 balls.

The total number of allocations is mⁿ = 3² = 9.
For k = 2 empty boxes, all 2 balls must be placed into the remaining 1 box. There are 3 ways to choose which box is non-empty, and for each, exactly 1 way to place all balls into it. So there are 3 ways to have 2 empty boxes.
For k = 1 empty box, 2 balls are distributed among the remaining 2 boxes such that neither is empty. There are 3 ways to choose the empty box. For the remaining 2 boxes, the 2 balls can be placed in 2² = 4 ways, minus the 2 ways where one of them is empty, leaving 2 valid placements. Thus, 3 × 2 = 6 ways to have 1 empty box.
The total ways for k = 2 is 3, and for k = 1 is 6. The sum is 9, covering all possible outcomes.

The expected number of empty boxes is m(1 − 1/m)ⁿ = 3(2/3)² = 12/9 = 4/3.

Experiment

Follow these steps to observe the exact PMF for varying allocation parameters.

Select the Boxes control to change the number of boxes. Notice how the total allocations update.
Adjust the Balls control. Observe the change in the PMF probabilities.
Change the Empty boxes probe to view the specific exact mass and decimal probability for that value.

For more details, visit https://riano.app/module/occupancy-empty-boxes.

Limitations

This implementation restricts the number of boxes to at most 4 and balls to at most 6 for exact calculation. It does not handle large populations where asymptotic approximations (such as Poisson limits) would be necessary.

References

The exact distribution formulas and enumeration methods for empty boxes can be verified in standard probability literature on finite sampling schemes.

Kyle Siegrist probability textbook, finite sampling

Empty Boxes in Random Allocation