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 .
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:
The following is the probability that at least one of the events has occurred:
Note that when or , we have the following familiar formulas:
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,
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:
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 .
- Feller, W., An Introduction to Probability Theory and its Applications, Vol. I, 3rd ed., John Wiley & Sons, Inc., New York, 1968