The occupancy problem in probability deals with the random assigment of balls into cells. One problem of interest is on the number of cells that are occupied or the number of cells that are empty. When randomly assigning balls into cells, what is the probability of finding any empty cell? What is the probability of finding exactly empty cells? In the previous post (The occupancy problem), we discussed the algorithm for solving this problem by the counting method based on the multinomial coefficients. In this post, we derive a direct formula for the probability of having empty cells when randomly placing balls into cells (see Theorem 2 below). The derivation is based on a theorem about the union of events (see Theorem 1 below). For more background information on the occupancy problem, see volume I of Feller in [1].

Theorem 1 concerns with the union of events. A provious post in this blog (The matching problem) presented a sketch of a proof of this theorem and a solution of one version of the matching problem. After proving Theorem 2, we present a direct calculation for the example in the previous post.

Suppose that we have the events . Define as the sum of all probabilities of many occuring simultaneously. Thus we have:

**Thoerem 1**

The following is the probability that at least one of the events has occurred:

Note that when or , we have the following familiar formulas:

**Theorem 2**

In randomly placing balls into cells, let be the number of empty cells. Then the probability that all cells are occupied (zero cell is empty) and the probability that exactly cells are empty are, respectively,

where .

* Proof*. Let be the event that the cell is empty, where . We proceed to derive the sums as in Theorem 1.

For the event to occur (the cell being empty), the balls in question are placed in the remaining cells. This can be done in ways. Thus .

For the event to occur (the and cells being empty), the balls are placed in the remaining cells. This can be done in ways. Thus we have .

Likewise, , and so on. For , we have .

Thus, the following is the probability that at least one cell is empty:

The probability of having no empty cell is:

If there are exactly empty cells, then the balls are placed in the remaining cells and these remaining cells are all occupied. Then the following is the probability of having exactly empty cells:

**Example**

In rolling a fair die times, what is the probability of having exactly faces appearing? This is the same example in the previous post (The occupancy problem). In this post we apply the formulas in Theorem 2.

Note that the rolling a die can be considered as the placing of a ball into one of the cells. Thus we have balls and cells. The probability of having cells occupied is the probability of empty cells. As in Theorem 2, is the number of empty cells when placing balls into cells at random. Thus the probability of having exactly cells occupied is .

**Reference**

- Feller, W.,
*An Introduction to Probability Theory and its Applications*, Vol. I, 3rd ed., John Wiley & Sons, Inc., New York, 1968

A very neat and interesting analysis. In theorem 2, did you yourself derive the formula for the probability that exactly j cells are empty, or has the proof been taken from an earlier source? Could you tell me the source, please, if there is one? I noticed similar reasoning for the matching problem.

Thank you.

Howard Walker

Howard, thanks for your comment. The source is Feller’s text listed under reference. See formulas 2.3 and 2.4 in page 102 of chapter 4 of Feller.

nice and clear 🙂

more examples can be added illustrating the idea….

Thank you, Dan, for your page!

With k < n, there are at least n-k empty cells.

I find that for j less than n-k the formula can be negative. For the remaining values of j, the distribution sums up to zero.

sums up to zero => sums up to one.

Awfully sorry.

Pingback: How long does it take to collect all coupons? | A Blog on Probability and Statistics

Pingback: The occupancy problem | Topics in Probability