The occupancy problem

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 k balls into n cells. The following diagram shows the result of randomly distributing 8 balls into 6 cells (or boxes).

Figure 1 – Occupancy Problem – throwing balls into cells

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.

Figure 2 – Occupancy Problem – rolling die repeatedly and counting the 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 n cells, the action can be viewed as randomly selecting one of the n cells. Thus the occupancy problem can be viewed as randomly selecting k balls (one at a time with replacement) from an urn with n balls labeled 1,2,\cdots,n. 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 3 – Occupancy Problem – random selection of balls with replacement from an urn and counting the distinct numbers that are drawn

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 n-sided die k 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 k balls into n cells,

  • What is the probability that exactly j cells are occupied with balls where j=1,2,\cdots,n?
  • 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 6^8 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

The notion is Markov chains is introduced here. The calculation involving transition probability matrix is discussed here.

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 X_0 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 X_0=0. For n \ge 1, X_n be the number of occupied cells after the nth ball has been distributed. The resulting stochastic process \left\{X_n: n=0,1,2,\cdots \right\} is a Markov chain since the state X_{n+1} only depends on the preceding state X_n. The following is the transition probability matrix.

    \displaystyle \mathbf{P} =    \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \cr    0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr    1 & 0 & \frac{1}{6} & \frac{5}{6} & 0 & 0 & 0 & 0 \cr  \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  2 & 0 & 0 & \frac{2}{6} & \frac{4}{6} & 0 & 0 & 0 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  3 & 0 & 0 & 0 & \frac{3}{6} & \frac{3}{6} & 0 & 0 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  4 & 0 & 0 & 0 & 0 & \frac{4}{6} & \frac{2}{6} & 0 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  5 & 0 & 0 & 0 & 0 & 0 & \frac{5}{6} & \frac{1}{6} \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \cr  } \qquad

    The matrix \mathbf{P} 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 i occupied cells, then the next ball is either in one of the i occupied cells with probability i/6 (meaning the next state remains at i) or in one of the unoccupied cells with probability (6-i)/6 (meaning the next state is i+1). Since the number of occupied cells cannot decrease, the transition probabilities in \mathbf{P} 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 \mathbf{P} holds the key to answering the first question indicated above. In throwing k balls into 6 cells, the answer lies in the matrix \mathbf{P}^k, the kth power of \mathbf{P} (the matrix obtained by multiplying \mathbf{P} by itself k 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 \mathbf{P}^8.

      \displaystyle \mathbf{P}^8 =    \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \cr    0 & 0 & 0.00000357 & 0.00226838 & 0.06901578 & 0.36458333 & 0.45010288 & 0.11402606 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr    1 & 0 & 0.0000006 & 0.0007591 & 0.03602014 & 0.27756344 & 0.49661351 & 0.18904321 \cr  \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  2 & 0 & 0 & 0.00015242 & 0.01501534 & 0.18815015 & 0.50831619 & 0.28836591 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  3 & 0 & 0 & 0 & 0.00390625 & 0.10533658 & 0.47531221 & 0.41544496 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  4 & 0 & 0 & 0 & 0 & 0.03901844 & 0.38709919 & 0.57388236 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  5 & 0 & 0 & 0 & 0 & 0 & 0.23256804 & 0.76743196 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \cr  } \qquad

    Each entry in \mathbf{P}^8 is denoted by P_{ij}^8, the 8-step transition probability, located in the row corresponding to the state i and in the column corresponding to the state j. For example, P_{03}^8=0.069, 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: P_{13}^8=0.036. 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 \mathbf{P}^8 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 \mathbf{P}^8 gives the answers.

      P[\text{1 occupied cell}]=P_{01}^8=0.00000357

      P[\text{2 occupied cell}]=P_{02}^8=0.00226838

      P[\text{3 occupied cell}]=P_{03}^8=0.06901578

      P[\text{4 occupied cell}]=P_{04}^8=0.36458333

      P[\text{5 occupied cell}]=P_{05}^8=0.45010288

      P[\text{6 occupied cell}]=P_{06}^8=0.11402606

    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 Y be the number of occupied cells after 8 balls are thrown into 6 cells. The mean number of occupied cells is:

      \displaystyle \begin{aligned} E[Y]&=1 \times 0.00000357+2 \times 0.00226838+3 \times 0.06901578 \\&\ \ + 4 \times 0.36458333+5 \times 0.45010288+6 \times 0.11402606 \\&=4.60459175 \end{aligned}

    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.

    If the occupancy problem involves throwing balls into n cells, the state of the Markov chain is the number of occupied cells at any given time. Set up the one-step transition probability matrix \mathbf{P} as follows. Set P_{01}=1 and P_{n,n-1}=1. For 0<i<n, set P_{ii}=i/n, P_{i,i+1}=(n-i)/n. Then the matrix \mathbf{P}^k gives the probability distribution of the number of occupied cells after k balls are randomly distributed into the n cells. The row in \mathbf{P}^k corresponding to the state i gives the probability of the number of occupied cells when there are i occupied cells initially. If initially all cells are empty, then the first row of \mathbf{P}^k gives the probability distribution of the number of occupied cells.

    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 \mathbf{P}, 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.

      \displaystyle \mathbf{P} =    \bordermatrix{ & 1 & 2 & 3 & 4 & 5 & 6 \cr  1 & \frac{1}{6} & \frac{5}{6} & 0 & 0 & 0 & 0 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  2 & 0 & \frac{2}{6} & \frac{4}{6} & 0 & 0 & 0 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  3 & 0 & 0 & \frac{3}{6} & \frac{3}{6} & 0 & 0 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  4 & 0 & 0 & 0 & \frac{4}{6} & \frac{2}{6} & 0 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  5 & 0 & 0 & 0 & 0 & \frac{5}{6} & \frac{1}{6} \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  6 & 0 & 0 & 0 & 0 & 0 & 1 \cr  } \qquad

      Assuming that the first ball goes into one of the empty cells, we focus on the next 7 balls. So we compute the matrix \mathbf{P}^7.

        \displaystyle \mathbf{P}^7 =    \bordermatrix{ & 1 & 2 & 3 & 4 & 5 & 6 \cr    1 & 0.00000357 & 0.00226838 & 0.06901578 & 0.36458333 & 0.45010288 & 0.11402606 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr    2 & 0 & 0.00045725 & 0.02942101 & 0.26015947 & 0.50591564 & 0.20404664 \cr  \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  3 & 0 & 0 & 0.0078125 & 0.15214549 & 0.50951646 & 0.33052555 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  4 & 0 & 0 & 0 & 0.05852766 & 0.44110797 & 0.50036437 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  5 & 0 & 0 & 0 & 0 & 0.27908165 & 0.72091835 \cr    \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr  6 & 0 & 0 & 0 & 0 & 0 & 1 \cr    } \qquad

        Note that the first row of \mathbf{P}^7 is identical to the first row of \mathbf{P}^8 earlier. So a slightly different algorithm is to put one ball in a cell and then focus on the random behavior of the next k-1 balls. In other words, set up the transition probability matrix \mathbf{P} with only the states 1, 2,\cdots,n and then raise \mathbf{P} to k-1.

        Remarks

        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.

        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.

        • 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?

        \text{ }

        \text{ }

        \text{ }

        \copyright 2017 – Dan Ma

        Advertisements

4 thoughts on “The occupancy problem

  1. Pingback: Collapsing states into an absorbing state | Topics in Probability

  2. Pingback: First step analysis and fundamental matrix | Topics in Probability

  3. Pingback: Probability problems using Markov chains | A Blog on Probability and Statistics

  4. Pingback: Celebrate the year of the dog | All Math Considered

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s