Absorbing Markov chains

The preceding two posts are devoted to solving the problem of determining mean time to absorption and the problem of determining the probability of absorption (using first step analysis here and using fundamental matrix here). The Markov chains in these problems are called absorbing Markov chains. This post summarizes the properties of such chains.

What are Absorbing Markov Chains?

A state in a Markov chain is said to be an absorbing state if the process will never leave that state once it is entered. That is, if the state i is an absorbing state, then P_{ii}=1. A Markov chain is said to be an absorbing Markov chain if it has at least one absorbing state and if any state in the chain, with a positive probability, can reach an absorbing state after a number of steps. The following transition probability matrix represents an absorbing Markov chain.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 \cr        0 & 1 & 0 & 0  & 0 & 0 & 0 \cr        1 & 0.5 & 0 & 0.5 & 0 & 0 & 0 \cr        2 & 0 & 0.5 & 0 & 0.5 & 0 & 0 \cr        3 & 0 & 0 & 0.5 & 0  & 0.5 & 0 \cr        4 & 0 & 0 & 0 & 0.5  & 0 & 0.5 \cr        5 & 0 & 0 & 0 & 0  & 0 & 1 \cr   } \qquad …………………………………………………………. (1)

The above matrix can be interpreted as a small scaled random walk or a small scaled gambler’s ruin. It has two absorbing states, 0 and 5. Once the process reaches these states, it does not leave these states. The other states (1, 2, 3 and 4) can reach an absorbing state in a finite number of steps with a positive probability. For example, state 1 can reach state 0 in one step with probability 0.5. State 1 can reach state 5 in four steps with probability 1/16.

As we will see below, any non-absorbing state in an absorbing Markov chain will eventually reach an absorbing state will probability 1. Thus any non-absorbing state in an absorbing Markov chain is a transient state. That is, when starting in a non-absorbing state, the process will only spend finite amount of time in non-absorbing states.

In order to be an absorbing Markov chain, it is not sufficient for a Markov chain to have an absorbing state. It must also have the property that all non-absorbing states must eventually reach an absorbing state. The following is an example of a chain that is not an absorbing Markov chain.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 \cr        0 & 0.5 & 0.3 & 0.2  & 0 & 0 & 0 \cr        1 & 0.4 & 0.3 & 0.3 & 0 & 0 & 0 \cr        2 & 0.3 & 0.4 & 0.3 & 0 & 0 & 0 \cr        3 & 0 & 0 & 0.3 & 0.3  & 0.4 & 0 \cr        4 & 0 & 0 & 0 & 0.4  & 0.3 & 0.3 \cr        5 & 0 & 0 & 0 & 0  & 0 & 1 \cr   } \qquad …………………………………………………………. (2)

Even though the above chain has one absorbing state (state 5), it is not an absorbing chain. Note that the states 0, 1 and 2 can never reach state 5.

Reaching Absorbing States with Certainty

Now we discuss several properties of such chains. The first one is that it does not matter what state the process is in initially, eventually the process reach an absorbing state, i.e. the process will be absorbed at some point in time. Suppose that the absorbing Markov chain has t non-absorbing states and r absorbing states. The transition probability matrix \mathbf{P} can be written in the following format

    \mathbf{P}=\left[\begin{array}{rr}     Q & R   \\      \mathbf{0} & I  \\        \end{array}\right] ……………………………………………………………………………………….. (3)

where Q is a t \times t matrix representing the transition probabilities from the non-absorbing states into the non-absorbing states and R is a t \times r matrix representing the transition probabilities from the non-absorbing states into the absorbing states. Furthermore, \mathbf{0} is an r \times t matrix consisting of zeros in its entries and I is the r \times r identity matrix. The following is the matrix in (1) arranged in the new format.

    \mathbf{P} =       \bordermatrix{ & 1 & 2 & 3 & 4 & \text{ } & 0 & 5 \cr        1 & 0 & 0.5 & 0  & 0 & \text{ } & 0.5 & 0 \cr        2 & 0.5 & 0 & 0.5 & 0 & \text{ } & 0 & 0 \cr        3 & 0 & 0.5 & 0 & 0.5 & \text{ } & 0 & 0 \cr        4 & 0 & 0 & 0.5 & 0  & \text{ } & 0 & 0.5 \cr        \text{ } & \text{ } & \text{ } & \text{ } & \text{ }  & \text{ } & \text{ } & \text{ } \cr        0 & 0 & 0 & 0 & 0  & \text{ } & 1 & 0 \cr        5 & 0 & 0 & 0 & 0  & \text{ } & 0 & 1 \cr   } \qquad …………………………………………………….. (4)

Decomposing \mathbf{P} into the form in (3) is a useful technique. It makes certain calculations simple to perform. We will get to that in a minute. First we prove an important fact showing that the non-absorbing states in an absorbing chain are indeed transient.

Theorem 1
In an absorbing Markov chain, the probability that the process will reach an absorbing state is 1. In other words, the probability of being in a non-absorbing state approaches zero as n goes to infinity, i.e. Q^n \rightarrow \mathbf{0} as n \rightarrow \infty.

Here’s a proof. For each non-absorbing state k, let C_k be the minimum number of steps to transition from state k to an absorbing state. For example, in the matrix (1), the minimum number of steps to go from state 1 to an absorbing state (state 0) is 1 with probability 0.5. In the same example, the minimum number of steps to go from state 3 to an absorbing state (state 5) is 2 with probability 0.25.

For each non-absorbing state k, let A_k be the probability that, starting from state k, the process will take more than C_k steps to reach an absorbing state. The probability A_k must be less than 1. If A_k=1, the process for certain will not reach an absorbing state in C_k steps, contradicting the property of C_k. Thus A_k<1.

Let C be the maximum of all C_k and let A be the maximum of all A_k. Taking maximum is possible here since the Markov chain has a finite state space. The probability of the process taking more than C steps to reach an absorbing state is less than or equal to A. This follows from the property of C_k and A_k.

Furthermore, the probability of the process taking more than 2 \times C steps to reach an absorbing state is less than or equal to A^2. This follows from the fact that the Markov chain is memoryless. After taking C steps and if the process still not in an absorbing state, the probability of the process taking additional C or more steps to reach an absorbing state is less than or equal to A. Thus multiply the two probabilities gives A^2. By an inductive reasoning, the probability of the process taking more than n \times C steps to reach an absorbing state is less than or equal to A^n. Since A<1, the numbers A^n approach zero as n goes to infinity.

It follows that as the integer n increases without bound, the probability that the process will take more than n steps to reach an absorbing state approaches zero. Turning it around, the probability that the process will reach an absorbing state in n or fewer steps approaches 1. As a result, for any non-absorbing states i and j, the transition probabilities P_{ij}^n approaches zero as n goes to infinity. Thus Q^n \rightarrow \mathbf{0} as n \rightarrow \infty. \square

The above theorem shows that in an absorbing Markov chain, the process will eventually land in an absorbing state (it cannot cycle among the non-absorbing states indefinitely). Thus in an absorbing Markov chain, the time spent in the non-absorbing states is finite. As a result, non-absorbing states in an absorbing Markov chain are called transient states. Since the time spent in transient states is finite, one of the problems of interest is the mean time spent in transient states. Of course, the answer depends on the initial state.

More Properties of Absorbing Markov Chains

Another important property is the fundamental matrix that can be computed from the transition probability matrix of an absorbing chain. Given the transition probability matrix \mathbf{P}, decompose \mathbf{P} according to (3). Recall that Q consists of the transition probabilities from the transient states to the transient states. Derive I-Q where I is the identity matrix of the same dimension as Q. The following three theorems capture more important properties of absorbing Markov chains.

Theorem 2
In an absorbing Markov chain with transition probability matrix \mathbf{P}, the matrix I-Q has an inverse W, i.e. W=(I-Q)^{-1}. The matrix W has the following properties:

  • W=I+Q+Q^2+Q^3+\cdots
  • An entry W_{ij} in the matrix W is the mean time spent in the transient state j given that the process starts at the transient state i. More specifically, W_{ij}=E[\text{number of times state } j \text{ is visited} \lvert X_0=i].

For an absorbing Markov chain with transition probability matrix \mathbf{P}, the matrix W=(I-Q)^{-1} is called the fundamental matrix of the absorbing Markov chain. A proof of Theorem 2 is sketched out in the preceding post. So we will not repeat it here.

Once the fundamental matrix is obtained by taking the inverse of I-Q, we can use it to solve two problems, stated in the following two theorems. The ideas of a proof are also sketched out in the preceding post.

Theorem 3 – mean time to absorption
In an absorbing Markov chain with transition probability matrix \mathbf{P}, consider the fundamental matrix W=(I-Q)^{-1}. The following calculation is of interest.

  • Given that the process starts in the transient state i, consider the row of the matrix W that corresponds to state i. The sum of all entries of W on that row is the mean time spent in transient states given that the process start in state i. The sum is the mean time to absorption.
Theorem 4 – probabilities of absorption
In an absorbing Markov chain with transition probability matrix \mathbf{P}, consider the fundamental matrix W=(I-Q)^{-1}. The following calculation is of interest.

  • Consider the matrix R in the decomposition of \mathbf{P}. The matrix W \times R, the product of W and R, gives the probabilities of absorption.
  • More specifically, the row in W corresponding to transient state i multiplying the column in R corresponding to the absorbing state k results in the probability of being absorbed into state k given that the process start in state i.
  • Even more specifically, assuming that the transient states are 0,1,2,\cdots,t-1, the following gives the probability of absorption into state k given that the process starts in state i.
      \displaystyle  \sum \limits_{j=0}^{t-1} \biggl( E[\text{number of times state } j \text{ is visited} \lvert X_0=i] \times P_{jk} \biggr)

Examples

Examples are available in the preceding posts (here and here). We work three examples.

Example 1
An urn initially contains 7 blue balls and 5 red balls. One ball is selected at random one at a time from the urn. If the selected ball is not red, the ball is put back into the urn. If the selected ball is red, it is removed from the urn. The process continues until all red balls are removed. Determine the expected number of selections in order to have all red balls removed.

Let X_n be the number of red balls in the urn after the nth selection. The states are 0, 1, 2, 3, 4 and 5. The initial state is X_0=5. The goal is to reach the absorbing state of 0 (all red balls are removed). The following is the transition probability matrix.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 \cr        0 & 1 & 0 & 0  & 0 & 0 & 0 \cr        1 & 1/8 & 7/8 & 0 & 0 & 0 & 0 \cr        2 & 0 & 2/9 & 7/9 & 0 & 0 & 0 \cr        3 & 0 & 0 & 3/10 & 7/10  & 0 & 0 \cr        4 & 0 & 0 & 0 & 4/11  & 7/11 & 0 \cr        5 & 0 & 0 & 0 & 0  & 5/12 & 7/12 \cr   } \qquad

There is only one absorbing state, the state 0. The states 1, 2, 3, 4 and 5 are transient states. Identify the matrix Q, which is the transition probabilities from the transient states into the transient states. Derive the matrix I-Q where I is a 5 x 5 identity matrix. The following is the inverse of I-Q.

    (I-Q)^{-1} =       \bordermatrix{ & 1 & 2 & 3 & 4 & 5  \cr        1 & 8 & 0 & 0 & 0 & 0  \cr        2 & 8 & 9/2 & 0 & 0 & 0  \cr        3 & 8 & 9/2 & 10/3 & 0  & 0  \cr        4 & 8 & 9/2 & 10/3 & 11/4  & 0  \cr        5 & 8 & 9/2 & 10/3 & 11/4  & 12/5  \cr   } \qquad

The 5th row of (I-Q)^{-1} gives the mean time spent in the transient states. The sum of the entries on the 5th row is 1259/60 = 20.9833. Thus it takes about 21 steps on average to remove all red balls from the urn.

Example 2
An urn initially contains 7 blue balls and 5 red balls. One ball is selected at random one at a time from the urn. If the selected ball is not red, the ball is put back into the urn. If the selected ball is red, it is removed from the urn and then a blue ball is put into the urn. The process continues until all red balls are removed. Determine the expected number of selections in order to have all red balls removed. Compare the expected value with the expected value in Example 1. Give an explanation for the difference.

As in Example 1, let X_n be the number of red balls in the urn after the nth selection. The states are 0, 1, 2, 3, 4 and 5. The initial state is X_0=5. The goal is to reach the absorbing state of 0 (all red balls are removed). The following is the transition probability matrix.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 \cr        0 & 1 & 0 & 0  & 0 & 0 & 0 \cr        1 & 1/12 & 11/12 & 0 & 0 & 0 & 0 \cr        2 & 0 & 2/12 & 10/12 & 0 & 0 & 0 \cr        3 & 0 & 0 & 3/12 & 9/12  & 0 & 0 \cr        4 & 0 & 0 & 0 & 4/12  & 8/12 & 0 \cr        5 & 0 & 0 & 0 & 0  & 5/12 & 7/12 \cr   } \qquad

One big difference from Example 1 is that each red ball selected is replaced by a blue ball. Thus the urn always has 12 balls whereas in Example 1 the number of balls is dwindling. As before, identify Q and derive I-Q. The following is the inverse of I-Q.

    (I-Q)^{-1} =       \bordermatrix{ & 1 & 2 & 3 & 4 & 5  \cr        1 & 12 & 0 & 0 & 0 & 0  \cr        2 & 12 & 6 & 0 & 0 & 0  \cr        3 & 12 & 6 & 4 & 0  & 0  \cr        4 & 12 & 6 & 4 & 3  & 0  \cr        5 & 12 & 6 & 4 & 3  & 12/5  \cr   } \qquad

Since the initial state is 5, we focus on the 5th row of (I-Q)^{-1}. The sum of that row is 137/5 = 27.4. Thus it takes on average 27.4 selections to remove all red balls. Note that the process takes longer than in Example 1. By replacing each selected red ball with a blue ball, it becomes harder to remove red balls especially when the process is in the lower states.

Example 3
An urn initially contains 4 blue balls and 2 red balls. One ball is selected at random one at a time from the urn. Each selected ball is replaced by a ball of the opposite color. The process continues until all balls in the urn are of the same color.

  • Determine the probability that the process ends with the urn containing only red balls.
  • Determine the expected number of selections in order for the urn to consist of balls of the same color.

Let X_n be the number of red balls in the urn after the nth selection. There are 7 states in this chain – 0, 1, 2, 3, 4, 5 and 6. The initial state is X_0=2. The process will eventually reach either state 0 or state 6. We wish to find the probability of being absorbed into state 6 first. States 0 and 6 are the absorbing states. States 1, 2, 3, 4, and 5 are transient states. The following is the transition probability matrix.

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

As before, identify Q and derive I-Q. The following is the inverse of I-Q.

    W=(I-Q)^{-1} =       \bordermatrix{ & 1 & 2 & 3 & 4 & 5  \cr        1 & 48/13 & 105/13 & 10 & 90/13 & 30/13  \cr        2 & 42/13 & 126/13 & 12 & 108/13 & 36/13  \cr        3 & 3 & 9 & 13 & 9  & 3  \cr        4 & 36/13 & 108/13 & 12 & 126/13  & 42/13  \cr        5 & 30/13 & 90/13 & 10 & 105/13  & 48/13  \cr   } \qquad

To answer the probability question, multiply the matrices W and R. The following is the result.

    W \times R=\left[\begin{array}{rrrrr}     48/13 & 105/13 & 10 & 90/13 & 30/13 \\      42/13 & 126/13 & 12 & 108/13 & 36/13  \\      3 & 9 & 13 & 9  & 3 \\     36/13 & 108/13 & 12 & 126/13  & 42/13 \\     30/13 & 90/13 & 10 & 105/13  & 48/13          \end{array}\right] \times \left[\begin{array}{rr}     1/6 & 0 \\      0 & 0 \\      0 & 0  \\     0 & 0 \\     0 & 1/6           \end{array}\right]=\left[\begin{array}{rr}     8/13 & 5/13 \\      7/13 & 6/13 \\      1/2 & 1/2  \\     6/13 & 7/13 \\     5/13 & 8/13           \end{array}\right]

With the initial state being 2, the probability of being absorbed into state 6 (all red balls) is 6/13 = 0.4615. The expected time to absorption (all balls of the same color) is the sum of the second row of (I-Q)^{-1}, which is 36. Thus on average it will take 36 selections of balls for the urn to consist of balls of the same color.

Practice Problems

Practice problems to reinforce the concepts discussed here are available in a companion blog. There are two problem sets. The first one is here and the second one is here.

Dan Ma math

Daniel Ma mathematics

Dan Ma Markov chains

Daniel Ma Markov chains

\copyright 2018 – Dan Ma

Advertisements

5 thoughts on “Absorbing Markov chains

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

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

  3. Pingback: Last step in an absorbing Markov chain | Topics in Probability

  4. Pingback: Practice Problem Set 4 – Absorbing Markov Chains | Topics in Probability

  5. Pingback: Practice Problem Set 5 – Absorbing Markov Chains – Additional Problems | Topics in Probability

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