The occupancy problem is a classic problem in probability. The setting of the problem is that balls are randomly distributed into cells (or boxes or other containers) one at a time. After all the balls are distributed into the cells, we examine how many of the cells are occupied with balls. In this post, we examine the occupancy problem using Markov chains.
The Occupancy Problem
As indicated above, we consider the random experiment of randomly placing balls into cells. The following diagram shows the result of randomly distributing 8 balls into 6 cells (or boxes).
One ball is thrown into the 6 boxes for a total of 8 balls. In Figure 1, a total of four cells are occupied. In the current discussion, the focus is on the number of occupied cells and not on which of the cells are occupied. Since Figure 1 has 6 cells, we can also view the throwing a ball into the 6 boxes as rolling a fair die (the occupied cell would be the face value that turns up). Thus we can view the experiment in Figure 1 a rolling a die 8 times. Then at the end, we look at the number faces that appear.
The top of Figure 2 shows the 8 rolls of the die. Four faces turn up in these 8 rolls – faces 2, 4, 5 and 6, the same result described in Figure 1. Another way to look at the occupancy problem is that of random sampling. Each time a ball is thrown into cells, the action can be viewed as randomly selecting one of the cells. Thus the occupancy problem can be viewed as randomly selecting balls (one at a time with replacement) from an urn with balls labeled . The following diagram shows an urn with 6 balls labeled 1 through 6. Then Figure 1 and Figure 2 would be equivalent to randomly selecting 8 balls with replacement from this urn.
Figure 1 describes a generic setting of the occupancy problem – throwing balls at random into cells. The interpretation in Figure 2 is ideal for the setting of six cells. If the number of cells is not six, we can view the problem as rolling an -sided die times. The random selection of balls with replacement (Figure 3) is also a good way to view the occupancy problem. Regardless of how we view the occupancy problem, we consider the following questions. In randomly assigning balls into cells,
- What is the probability that exactly cells are occupied with balls where ?
- What is the expected number of occupied cells?
The first question is about the probability distribution of the number of occupied cells after the balls are thrown. The second question is about the mean of the probability distribution of the number of occupied cells. Once the probability distribution is known, we can calculate the distributional quantities such as the mean and variance. Thus the main focus is on the first question.
The occupancy problem has been discussed in a companion blog. In this blog post, the first question is answered by using the multinomial theorem (applied twice). Another blog post develops a formula for the probability distribution of the number of occupied cells. These previous blog posts use counting methods to solve the occupancy problem. For example, in throwing eight balls into 6 cells, there are many distinct outcomes. How many of these correspond to only one occupied cell, two occupied cells and so on? In this post, we present another way to answer the same question using Markov chain.
The occupancy problem discussed here and in the previous blog posts assumes that each ball is equally likely to be assigned into any one of the cells. Thus the occupancy problem where the weights of assignment of the cells are not uniform would be an interesting extension of the problem.
Applying Markov Chains
To demonstrate, we use the specific example of randomly distributing balls into 6 cells. First, define a Markov chain. The state of the Markov chain is the number of occupied cells at any given time. Let denote the number of occupied cells at the beginning of the experiment (before any balls are thrown). If all cells are unoccupied at the beginning, then . For , be the number of occupied cells after the th ball has been distributed. The resulting stochastic process is a Markov chain since the state only depends on the preceding state . The following is the transition probability matrix.
- Given the one-step transition probability matrix for the Markov chain describing the process of distributing candies to 4 children.
- What is the probability distribution of the number of children who have received candies?
- What is the probability all 4 children receiving candies?
- What is the mean number of children who have received candies?
- What is the probability that Marcus receives 1 candy, Issac receives 4 candies, Samantha receives 4 candies and Paul receives 2 candies?
- What is the probability that one of the children receives 1 candy, another child receives 4 candies, another child receives 4 candies and the last child receives 2 candies?
The matrix contains the one-step transition probabilities, i.e. the probabilities of the the next state given the current state. If the Markov chain is in state 0 (no occupied cells), the the next state is 1 for certain. If the current state is 1 (one occupied cell), then the next ball is is the occupied cell with probability 1/6 and is in one of the empty cells with probability 5/6. In general, if there are currently occupied cells, then the next ball is either in one of the occupied cells with probability (meaning the next state remains at ) or in one of the unoccupied cells with probability (meaning the next state is ). Since the number of occupied cells cannot decrease, the transition probabilities in have the appearance of moving diagonally from the upper left corner to the lower right corner. State 6 (all cells are occupied) is a called an absorbing state. When the Markov chain is transitioned to state 6, it stays there for ever no matter how many more additional balls are thrown into the cells.
The transition probability matrix holds the key to answering the first question indicated above. In throwing balls into 6 cells, the answer lies in the matrix , the th power of (the matrix obtained by multiplying by itself times). This can be done by using software, e.g. using an online matrix calculator.
Consider the example of throwing eight balls into 6 cells. The following is the matrix .
Each entry in is denoted by , the 8-step transition probability, located in the row corresponding to the state and in the column corresponding to the state . For example, , indicating that there is a 6.9% chance that 3 cells are occupied after eight balls are thrown (with all cells being empty at the beginning). Another example: . So if there is one occupied cell at the beginning, there is a 3.6% chance that 3 cells are occupied after throwing 8 balls into the 6 cells. So each row in gives a probability distribution of the number of occupied cells depending the initial state.
The first question stated above assumes that the all cells are empty at the beginning. Thus the first row of the matrix gives the answers.
In randomly throwing 8 balls into 6 cells, the more likely outcomes would be having 4, 5 or 6 occupied cells with the mostly likely being 4 occupied cells. Let be the number of occupied cells after 8 balls are thrown into 6 cells. The mean number of occupied cells is:
To give an indication that the probability distribution is correct, we simulate 8 rolls of a die 1,000 times using the =RANDBETWEEN(1, 6) function in Excel. The results: 0% (1 occupied cell), 0.4% (2 occupied cells), 7.3% (3 occupied cells), 35.2% (4 occupied cells), 47.3% (5 occupied cells) and 9.8% (6 occupied cells). These results are in general agreement with the calculated distribution. Of course, the larger the simulation, the closer the simulated results will be to the theoretical distribution.
Here’s the algorithm for solving the occupancy problem using the Markov chain approach.
We would like to make further comment on the example. Assuming that all cells are empty at the beginning, the example can be worked by eliminating the first row of , the row for state 0. The first ball will always go into one empty cell. Thus in throwing 8 balls, we can focus on 7 balls going into 6 cells with one cell already occupied (by the first ball). Thus we can focus on the following transition probability matrix.
Assuming that the first ball goes into one of the empty cells, we focus on the next 7 balls. So we compute the matrix .
Note that the first row of is identical to the first row of earlier. So a slightly different algorithm is to put one ball in a cell and then focus on the random behavior of the next balls. In other words, set up the transition probability matrix with only the states and then raise to .
As the above example demonstrates, the occupancy problem is a matter of calculating the power of a transition probability matrix. It is an algorithm that is suitable for computer implementation. It illustrates the versatility of the Markov chain method. The combinatorial approach of using multinomial theorem (discussed here and here) is also a valuable approach. Each approach provides its own unique insight. The post ends with an exercise.
Suppose that eleven candies are randomly distributed to 4 children. Suppose that the names of the 4 children are Marcus, Issac, Samantha and Paul.