A little over one year ago, this blog marked the beginning of the year of the rooster in this blog post. Now it’s time to celebrate the year of the dog.
The Lunar New Year actually falls on February 16 this year. To be precise, the latest year of the dog will span from February 16, 2018 to February 4, 2019. We mark the New Year by highlighting a math problem that is related to the Chinese zodiac signs. In fact, this problem was also discussed in the blog post on the year of the rooster.
The problem is this. There are 12 animal signs in Chinese zodiac – Rat, Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog and Pig. You ask people repeatedly their animal signs until all 12 signs have been represented. How many people do you have to ask in order to have encountered all 12 animal signs? We assume that the 12 animal signs are equally represented. This assumption makes the math more tractable.
The number of people you ask is a random quantity. Obviously the number of people you have to ask is at least 12. It is likely that you have to ask many more than 12 people. In the previous post, we discuss this problem in two different ways – through simulations and using a math formula based on the coupon collector problem. In this post we view this problem as an occupancy problem and solve it using the method of Markov chains.
The Occupancy Problem
Imagine there are 12 cells (e.g. boxes or urns). Balls are thrown into the cells one at a time at random (assuming that each ball always lands into one of the 12 cells). On average, how many balls do we need to throw so that each cell has at least one ball? In other words, how many balls do we need to throw so that there are no empty cell? This is one form of the occupancy problem. The occupancy problem being described here is a natural reformulation of the problem about asking people until all 12 animal signs are represented.
The problem can also be described as sampling with replacement. Put 12 balls labeled 1 through 12 in an urn. Draw balls at random one at a time with replacement. How many selections do we need to make so that each of the 12 numbers are drawn at least once?
Of course, there is nothing special about 12 cells. The number of cells in the occupancy problem can vary. Consider the problem of 6 cells. So balls are thrown until all 6 cells are occupied. Or an urn has 6 balls labeled 1 through 6. Then balls are drawn from the urn until all each of the 6 numbers has been chosen at least once. There is another way of looking at the 6-cell occupancy problem – rolling a die repeatedly until each face has appeared at least once.
Markov Chain Approach
There are more than one way to solve the occupancy problem (two ways are discussed in the previous posts).
The method to highlight here is to use Markov chains. A Markov chain is a series of random steps. Each random step is identified by a state. Each state is dependent only on the preceding state and not on the states prior to the preceding state. We use to denote the state after the th random step or at time .
In the 12-cell occupancy problem, a state is the number of occupied cells after a ball is thrown. For example, , which is the initial state (we assume that before throwing the first ball, the cells are empty). Then (after throwing one ball, one cell is occupied). After throwing the second ball, the number of occupied cells is random. For example, it could be that (if the second ball goes into the occupied cell holding the first ball) or it could be that (if the second ball goes into an empty cell). The first scenario has probability 1/12 and the second scenario has probability 11/12. Similarly, we can list out all the scenarios for (the number of occupied cells after throwing the third ball) and their probabilities. In fact, it will be much more efficient if we describe all these probabilities in a matrix.
The above matrix looks kind of huge. But there is an order behind it. The Markov chain of the 12-cell occupancy problem has 13 states (0, 1, 2, …, 12). In this case, a state refers to the number of occupied cells after a ball is thrown into the cells. So is the number of occupied cells after the th ball is thrown. For convenience, we can also think of the subscripts as time. The type of Markov chains discussed here would be called discrete-time Markov chains.
The above matrix is called the transition probability matrix. It contains the probabilities of transitioning from one state into various states. Here’s how to read the matrix. Pick a row, say the row labeled 2. This refers to the situation of the process being at a point when 2 of the 12 cells are occupied. The next state can be 2, meaning that the next ball goes into one of the two occupied cells. Since there are two occupied cells, the probability is 2/12. The next state can be 3, meaning that the next ball goes into one of the empty cells. Since there are 10 cells not occupied, the probability is 10/12.
In general, this matrix tells us that if the process starts at state , the process will remain at state in the next time period with probability and the process will transition to with probability .
The state 12 is an interesting one. When all the cells are occupied, any additional balls thrown at them will still mean that the cells are occupied. Thus when the process reaches state 12, the process remains at 12 indefinitely. A state is called an absorbing state if the process does not leave that state once that state is entered. Thus state 12 is an absorbing state in 12-cell occupancy problem. The other states (0 to 11) are called transient states.
The probabilities in the matrix are called one-step transition probabilities because these probabilities tell us how the process transitions from a given step to the next step. These probabilities are notated by , signifying the probability that the state in the next period is given that the process begins in state . For example, and . What about the two-step transition probabilities ? The quantity is the probability that the process will be in state after two steps given that the process is currently in state . The idea generalizes quite naturally. The quantity , a -step transition probability, is the probability that the process will be in state after steps are taken given that the process is currently in state .
To compute the -step transition probabilities, all we need to do is to raise the matrix to the th power. A matrix calculator will be helpful. Using this online matrix calculator, we raise to the 4th power, the following shows the non-zero elements in the first row.
After throwing 5 balls into 12 empty cells, the above probabilities tells us the likelihoods of the number of occupied cells. It is very unlikely to have 1 or 2 occupied cells. The most likely would be 4 or 5 occupied cells. To determine the likelihoods after throwing 6 balls into 12 empty cells, raise to 6 and so on.
For a detailed discussion on calculation of -step transition probabilities, see this blog post.
Solving the Occupancy Problem
We now give an indication on how to solve the 12-cell occupancy problem (or the 12 animal signs problem). Recall that state 12 is an absorbing state. Now consider the matrix obtained by removing state 12 from . Call this new matrix . It is a 12 x 12 matrix. Let be the 12 x 12 identity matrix. Compute the matrix . Then use an online matrix calculator to find the inverse matrix of . Let be the inverse. The sum of the all the elements in the first row of is the average number of steps that the Markov process takes to reach state 12. The following is the sum of the elements on the first row of .
On average, we need to throw 37.24 balls into the 12 cells to have no empty cells. With respect to the 12 animal signs, on average, it requires sampling 37.24 people to have encountered all 12 signs.
The matrix is called the fundamental matrix of the Markov chain represented by the matrix . The method is detailed in this blog post. That blog post also discusses the occupancy problem in some details.
The discussion here is a roundabout way and a long winded way to solve the coupon collector problem, which is discussed in this blog post from a year ago. However, the example discussed here is an excellent introduction to Markov chains. Further information can be found in the following blog posts.
Chapman-Kolmogorov equations (raising transition probability matrix to a power)
Dan Ma math blog
Daniel Ma math blogs
Dan Ma math
Daniel Ma math
Dan Ma mathematics
Daniel Ma mathematics