Last step in an absorbing Markov chain

The preceding three posts are devoted to a problem involving absorbing Markov chains (finding the mean time to absorption and the probability of absorption). The links to these three posts are here, here and here. One method in solving this problem is to use the fundamental matrix. The same method can be used to solve a problem involving the last step before being absorbed. Here are two examples.

Example 1
Six coins are tossed all at once. The coins randomly fall heads or tails. For the coins that fall tails, you pick up and toss again. The process continues in such a way that after each toss, you pick up the coins that fall tails and toss again. The process stops until all coins show heads. Let Y be the number of coins in the last toss. Determine the probability distribution of the random variable Y.

Note that Y can range from 6 down to 1. If the first toss results in 6 heads, there is no need to toss again, meaning that Y=6, which is not very likely. The problem is to determine how likely it is for Y to be a given value.

Example 2
A maze has 7 areas with two of the areas being food sources (area 5 and area 7)

A maze with two food sources (areas 5 and 7)

A mouse is placed into this maze. When the mouse is in an area with food, it stays there and does not leave. When the mouse is in an area with no food, it moves into the adjacent areas at random. In other words, if the area has k exits, the mouse moves to one of these k areas with probability 1/k.

If the mouse is in one of the non-food areas, then the mouse will be absorbed into one of the food areas. We are interested in identifying the non-food area before reaching a food area. The areas adjacent to a food area would be 2, 4 and 6. These would be the entry points for food. When the mouse finds food, how likely is the entry point to be area 2, area 4 or area 6? More specifically, if the mouse is in area i where i=1,2,3,4,6, determine the probability that the mouse transitions into a food area from area k where k=2,4,6.

A common idea for these two examples and others like them is that we are interested in locating the transient state from which the process enters an absorbing state. We would like to find the probabilities of the various transient states being the entry point to absorption given an initial state. We discuss these two examples after demonstrating the method using a smaller example.

Illustrative Example

A Markov chain has 4 states (0, 1, 2 and 3). The process cycles among these states according to the following transition probability matrix.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 \cr        0 & 1 & 0 & 0  & 0 \cr        1 & 0.3 & 0.4 & 0.2 & 0.1 \cr        2 & 0.1 & 0.2 & 0.3 & 0.4 \cr        3 & 0 & 0 & 0 & 1  \cr           } \qquad

There are two absorbing states (0 and 3) and two transient states (1 and 2). If the process starts at a transient state, the process will eventually be absorbed (be transitioned into an absorbing state). The question we want to answer is this. What is the transient state from which the process enters an absorbing state? In this example, the process can enter an absorbing state from state 1 or state 2. Given that the process is in state 1 initially, what is the probability that the process enters absorption from state 1? Likewise from state 2? The same question can be asked if the process starts at state 2 initially.

Let \{ X_n,n=0,1,2,\cdots \} be the chain described by the above matrix. Let T=\text{min}\{ n \ge 0: X_n=0 \text{ or } X_n=3 \}. The quantity T is the random time to absorption. The quantity T-1 is the time period before absorption. Thus X_{T-1} is the last transient state before absorption. We calculate the following probabilities.

    P(X_{T-1}=1 \lvert X_0=1)

    P(X_{T-1}=2 \lvert X_0=1)

    P(X_{T-1}=1 \lvert X_0=2)

    P(X_{T-1}=2 \lvert X_0=2)

The first two probabilities form the conditional distribution of the last transient state given that the initial state is 1. The last two probabilities form the conditional distribution of the last transient state given that the initial state is 2. To find these probabilities, it will be helpful to perform calculations involving the fundamental matrix.

    Q=\left[\begin{array}{cc}     0.4 & 0.2  \\      0.2 & 0.3 \\     \end{array}\right]    \ \ \ \ \ \ \ \   I-Q=\left[\begin{array}{cc}     1 & 0  \\      0 & 1 \\     \end{array}\right]-  \left[\begin{array}{cc}     0.4 & 0.2  \\      0.2 & 0.3 \\     \end{array}\right]=  \left[\begin{array}{cc}     0.6 & -0.2  \\     - 0.2 & 0.7 \\     \end{array}\right]

    W=(I-Q)^{-1}=  \left[\begin{array}{cc}     0.6 & -0.2  \\     - 0.2 & 0.7 \\     \end{array}\right]^{-1}=  \left[\begin{array}{cc}     35/19 & 10/19  \\     10/19 & 30/19 \\     \end{array}\right]=    \left[\begin{array}{cc}     W_{11} & W_{12}  \\     W_{21} & W_{22} \\     \end{array}\right]

See here for more information on the calculation. The matrix Q is the part of \mathbf{P} consisting of the transient states. The matrix I-Q is the difference between the identity matrix and Q. The matrix W=(I-Q)^{-1}, the inverse of I-Q, is the fundamental matrix for the absorbing Markov chain.

The matrix W=(I-Q)^{-1} gives the mean times spent in transient states. For example, if the process starts in state 1, it spend 35/19 = 1.842 periods in state 1 and 10/19 = 0.526 periods in state 2. In total, it spends on average 45/19 = 2.368 periods in transient states before being absorbed (if the initial state is 1). The following shows the calculation for the case of initial state being 1.

    \displaystyle P(X_{T-1}=1 \lvert X_0=1)=W_{11} \times P_{10}+W_{11} \times P_{13}=\frac{35}{19} (0.3+0.1)=\frac{14}{19}=0.7368

    \displaystyle P(X_{T-1}=2 \lvert X_0=1)=W_{12} \times P_{20}+W_{12} \times P_{23}=\frac{10}{19} (0.1+0.4)=\frac{5}{19}=0.2632

The calculation shows that if the initial state is 1, it is much more likely for the process to enter an absorbing state from state 1 than from state 2 (almost 74% chance). Before giving an indication why the calculation works, here’s the calculation for the initial state being 2.

    \displaystyle P(X_{T-1}=1 \lvert X_0=2)=W_{21} \times P_{10}+W_{21} \times P_{13}=\frac{10}{19} (0.3+0.1)=\frac{4}{19}=0.2105

    \displaystyle P(X_{T-1}=2 \lvert X_0=2)=W_{22} \times P_{20}+W_{22} \times P_{23}=\frac{30}{19} (0.1+0.4)=\frac{15}{19}=0.7895

If the process starts from state 2 instead, it is more likely (almost 79% chance) that the process enters an absorbing state from state 2.

Here’s the thought process for obtaining these probabilities. Consider P(X_{T-1}=1 \lvert X_0=1). The starting transient state is 1 and the ending transient state is also 1. Then we look at the mean time in transient state W_{11}. From the ending transient state 1, the process can go into the absorbing state 0 or 3. Thus the desired probability is W_{11} \times P_{10}+W_{11} \times P_{13}=W_{11} (P_{10}+P_{13}).

If the starting state is 1 and the ending transient state is 2, we would take the sum of mean time W_{12} times P_{2k} for k=0,3. Thus P(X_{T-1}=2 \lvert X_0=2) would be W_{12} \times P_{20}+W_{12} \times P_{23}=W_{12} (P_{20}+P_{23}).

In general P(X_{T-1}=j \lvert X_0=i) is the sum of W_{ij} \times P_{jk} over all absorbing states k from which it is possible to go from j to k. To get a sense of why this idea works, let’s look at the the probabilities of absorption calculated from the fundamental matrix W.

    Q \times R=  \left[\begin{array}{cc}     W_{11} & W_{12}  \\     W_{21} & W_{22} \\     \end{array}\right] \times  \left[\begin{array}{cc}     P_{10} & P_{13}  \\     P_{20} & P_{23} \\     \end{array}\right]=    \left[\begin{array}{ccc}     W_{11} \cdot P_{10}+W_{12} \cdot P_{20} & \text{ } & W_{11} \cdot P_{13}+W_{12} \cdot P_{23}  \\     W_{21} \cdot P_{10}+W_{22} \cdot P_{20} & \text{ } & W_{21} \cdot P_{13}+W_{22} \cdot P_{23} \\     \end{array}\right]

To make it easier to see, we rewrite the last matrix on the right as follows.

    Q \times R =       \bordermatrix{ & 0 & \text{ } & 3 \cr                1 &  W_{11} \cdot P_{10}+W_{12} \cdot P_{20} & \text{ } & W_{11} \cdot P_{13}+W_{12} \cdot P_{23}  \cr        2 & W_{21} \cdot P_{10}+W_{22} \cdot P_{20} & \text{ } & W_{21} \cdot P_{13}+W_{22} \cdot P_{23}  \cr                   } \qquad

This is a 2 x 2 matrix indicating the probability of absorption based on the initial states (the rows) and the absorbing states (the columns). The first column gives the probabilities of absorption into state 0 and the second column gives the probabilities of absorption into state 3. Each of the four elements is a sum of two quantities. We can rearrange these 8 quantities to get the desired probabilities. For example, P(X_{T-1}=1 \lvert X_0=1) would be the quantities corresponding to the initial transient state 1 and ending transient state 1, which would be W_{11} \cdot P_{10}+W_{11} \cdot P_{13}. The probability P(X_{T-1}=1 \lvert X_0=2) would be the sum of the quantities corresponding to the initial transient state 2 and ending transient state 1, which would be W_{21} \cdot P_{10}+W_{21} \cdot P_{13}.

Summary

Before tackling the examples stated earlier, we summarize the ideas in the preceding section. Suppose that \mathbf{P} is the transition probability matrix for a given absorbing Markov chain. For conceptual clarity, we can rewrite \mathbf{P} in the following form.

    \mathbf{P}=\left[\begin{array}{cc}     Q & R  \\      \mathbf{0} & I \\     \end{array}\right]

In this formulation, Q consists of the one-step transition probabilities from transient states into transient states, R consists of the one-step transition probabilities from transient states into absorbing states. Furthermore, all entries of \mathbf{0} are zero and I is the identity matrix of an appropriate size.

The next step is to obtain the fundamental matrix W=(I-Q)^{-1}, which is the inverse matrix of I-Q. The entries of W are mean times spent in transient states. For example, the entry W_{ij} is the mean time spent in state j given that the initial state is i. As mentioned, the entries of the matrix R are one-step probabilities from a transient state into an absorbing state. A typical entry of R is P_{ik} where i is a transient state and k is an absorbing state. As the above example demonstrates, the entries of W and R are used in finding the probability of the transient state from which the process enters an absorbing state.

Let T=\text{min} \{ n \ge 0: X_n \text{ is an absorbing state} \}, which is the random time to absorption. The goal is to find the probability of the form

    P(X_{T-1}=j \lvert X_0=i)

where i is the initial transient state and j is the ending transient state (the last transient state before absorption). This probability is obtained by combining the appropriate entries of the matrices W and R in the following way:

    \displaystyle P(X_{T-1}=j \lvert X_0=i)=\sum \limits_{k} \biggl( W_{ij} \cdot P_{jk} \biggr)=W_{ij} \sum \limits_{k} P_{jk}

where k is over all relevant absorbing states, i.e. all absorbing states k for which it is possible to transition from j to k.

Examples

We now solve the two examples indicated at the beginning.

Example 1
Let X_0=6, i.e. the 0th toss involves 6 coins. Let X_n be the number of coins in the (n+1)st toss. This is indeed a Markov chain since the next state depends only on the current state. The states decrease as more and more tosses are made. Thus the states of the chain are 6, 5, 4, 3, 2, 1 and 0 with state 0 being the absorbing state.

In each step in the chain, we observe the number of tails in tossing a number of coins. Thus each row in the transition probability matrix consists of the probabilities from a binomial distribution. Thus the following gives the transition probability matrix \mathbf{P}.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \cr        0 & 1 & 0 & 0  & 0 & 0 & 0 & 0 \cr        1 & 1/2 & 1/2 & 0 & 0 & 0 & 0 & 0 \cr        2 & 1/4 & 2/4 & 1/4 & 0 & 0 & 0 & 0 \cr        3 & 1/8 & 3/8 & 3/8 & 1/8  & 0 & 0 & 0 \cr        4 & 1/16 & 4/16 & 6/16 & 4/16  & 1/16 & 0 & 0 \cr        5 & 1/32 & 5/32 & 10/32 & 10/32  & 5/32 & 1/32 & 0 \cr        6 & 1/64 & 6/64 & 15/64 & 20/64  & 15/64 & 6/64 & 1/64 \cr   } \qquad

The following shows the calculation to obtain the fundamental matrix W.

    Q=  \left[\begin{array}{cccccc}     1/2 & 0 & 0 & 0 & 0 & 0  \\      2/4 & 1/4 & 0 & 0 & 0 & 0  \\      3/8 & 3/8 & 1/8  & 0 & 0 & 0 \\     4/16 & 6/16 & 4/16  & 1/16 & 0 & 0 \\     5/32 & 10/32 & 10/32  & 5/32 & 1/32 & 0 \\     6/64 & 15/64 & 20/64  & 15/64 & 6/64 & 1/64  \end{array}\right] \ \ \ \ \ \ \ \ \     R =       \bordermatrix{ & 0 \cr               1 & 1/2  \cr        2 & 1/4  \cr        3 & 1/8  \cr        4 & 1/16  \cr        5 & 1/32  \cr        6 & 1/64  \cr   } \qquad

    I-Q=  \left[\begin{array}{cccccc}     1/2 & 0 & 0 & 0 & 0 & 0  \\      -2/4 & 3/4 & 0 & 0 & 0 & 0  \\      -3/8 & -3/8 & 7/8  & 0 & 0 & 0 \\     -4/16 & -6/16 & -4/16  & 15/16 & 0 & 0 \\     -5/32 & -10/32 & -10/32  & -5/32 & 31/32 & 0 \\     -6/64 & -15/64 & -20/64  & -15/64 & -6/64 & 63/64  \end{array}\right]

    W=(I-Q)^{-1} =       \bordermatrix{ & 1 & 2 & 3 & 4 & 5 & 6 \cr               1 & 2 & 0 & 0 & 0 & 0 & 0 \cr        2 & 4/3 & 4/3 & 0 & 0 & 0 & 0 \cr        3 & 10/7 & 4/7 & 8/7  & 0 & 0 & 0 \cr        4 & 152/105 & 72/105 & 32/105  & 112/105 & 0 & 0 \cr        5 & 942/651 & 472/651 & 272/651  & 112/651 & 672/651 & 0 \cr        6 & 2820/1953 & 1428/1953 & 928/1953  & 528/1953 & 192/1953 & 1984/1953 \cr   } \qquad

To solve the problem at hand, first define the time to absorption T=\text{min} \{ n \ge 0: X_n=0 \}. The following calculation gives the probabilities of the last step.

    \displaystyle P(Y=1)=P(X_{T-1}=1 \lvert X_0=6)=W_{61} \times P_{10}=\frac{2820}{1953} \times \frac{1}{2}=\frac{1410}{1953}=0.7220

    \displaystyle P(Y=2)=P(X_{T-1}=2 \lvert X_0=6)=W_{62} \times P_{20}=\frac{1428}{1953} \times \frac{1}{4}=\frac{357}{1953}=0.1828

    \displaystyle P(Y=3)=P(X_{T-1}=3 \lvert X_0=6)=W_{63} \times P_{30}=\frac{928}{1953} \times \frac{1}{8}=\frac{116}{1953}=0.0594

    \displaystyle P(Y=4)=P(X_{T-1}=4 \lvert X_0=6)=W_{64} \times P_{40}=\frac{528}{1953} \times \frac{1}{16}=\frac{33}{1953}=0.0169

    \displaystyle \begin{aligned}P(Y=5)&=P(X_{T-1}=5 \lvert X_0=6)=W_{65} \times P_{50}=\frac{192}{1953} \times \frac{1}{32}=\frac{6}{1953}=0.003072  \end{aligned}

    \displaystyle \begin{aligned}P(Y=6)&=P(X_{T-1}=6 \lvert X_0=6)=W_{66} \times P_{60}=\frac{1984}{1953} \times \frac{1}{64}=\frac{31}{1953}=0.01587  \end{aligned}

Starting a 6 coins, the reduction in coins in tosses is gradual. There is a 72% chance that the coins will be reduced to one coin in the last toss. The most likely way to end the game is from tossing the last single coin. However, the calculation does not indicate how long it will take to reach the last step of one coin.

Example 2
The diagram of the maze is repeated here.

A maze with two food sources (areas 5 and 7)

There are 7 states in this Markov chain, representing the areas in the maze. The following gives the transition probability matrix.

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

The states 5 and 7 are the areas with food, thus are absorbing states. The next step is the calculation surrounding the fundamental matrix W.

    Q =       \bordermatrix{ & 1 & 2 & 3 & 4 & 6 \cr                1 & 0 & 1 & 0 & 0 & 0 \cr        2 & 0 & 0 & 1/2 & 0 & 0  \cr        3 & 0 & 1/3 & 0 & 1/3  & 1/3 \cr        4 & 0 & 0 & 1/2 & 0 & 0 \cr                6 & 0 & 0 & 1/3 & 0 & 0 \cr           } \qquad \ \ \ \ \ \ \ \ \     R =       \bordermatrix{ & 5  & 7 \cr               1 & 0  & 0\cr        2 & 0  & 1/2 \cr        3 & 0 & 0 \cr        4 & 1/2 & 0 \cr                6 & 1/3 & 1/3 \cr   } \qquad

    I-Q=  \left[\begin{array}{ccccc}     1 & -1 & 0 & 0 & 0  \\      0 & 1 & -1/2 & 0 & 0  \\      0 & -1/3  & 1 & -1/3 & -1/3 \\     0 & 0  & -1/2 & 1 & 0 \\     0 & 0  & -1/3 & 0 & 1 \\       \end{array}\right]

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

The matrices W and R are all we need to finish the problem. Suppose that we place the mouse initially at either area 2, area 3 and area 6. We find the probabilities of the last transient state being 2, 4 and 6. Once again T is the random time to absorption and is defined by T=\text{min} \{ n \ge 0: X_n=5 \text{ or } X_n=7 \}.

First, the starting state is 2.

    \displaystyle P(X_{T-1}=2 \lvert X_0=2]=W_{22} \cdot P_{27}=\frac{13}{10} \cdot \frac{1}{2}=\frac{6.5}{10}=0.65

    \displaystyle P(X_{T-1}=4 \lvert X_0=2]=W_{24} \cdot P_{45}=\frac{3}{10} \cdot \frac{1}{2}=\frac{1.5}{10}=0.15

    \displaystyle P(X_{T-1}=6 \lvert X_0=2]=W_{26} \cdot (P_{65}+P_{67})=\frac{3}{10} \cdot \frac{2}{3}=\frac{2}{10}=0.2

Next, the starting state is 3.

    \displaystyle P(X_{T-1}=2 \lvert X_0=3]=W_{32} \cdot P_{27}=\frac{3}{5} \cdot \frac{1}{2}=\frac{1.5}{5}=0.3

    \displaystyle P(X_{T-1}=4 \lvert X_0=3]=W_{34} \cdot P_{45}=\frac{3}{5} \cdot \frac{1}{2}=\frac{1.5}{5}=0.3

    \displaystyle P(X_{T-1}=6 \lvert X_0=3]=W_{36} \cdot (P_{65}+P_{67})=\frac{3}{5} \cdot \frac{2}{3}=\frac{2}{5}=0.4

Lastly, the starting state is 6.

    \displaystyle P(X_{T-1}=2 \lvert X_0=6]=W_{62} \cdot P_{27}=\frac{1}{5} \cdot \frac{1}{2}=\frac{1}{10}=0.1

    \displaystyle P(X_{T-1}=4 \lvert X_0=6]=W_{64} \cdot P_{45}=\frac{1}{5} \cdot \frac{1}{2}=\frac{1}{10}=0.1

    \displaystyle P(X_{T-1}=6 \lvert X_0=6]=W_{66} \cdot (P_{65}+P_{67})=\frac{6}{5} \cdot \frac{2}{3}=\frac{4}{5}=0.8

The results agree with the intuition. If the mouse is placed in area 2 initially, it is most likely that the mouse enters food area from area 2 (65% chance). Because the mouse makes the moves at random, there is a small but not negligible chance that the entry to food is from area 4 or area 6.

The initial state of area 3 is more neutral. If the mouse is placed in area 3 at first, the entry to food is roughly equally likely to be from areas 2, 4 and 6, with area 6 having a slight edge. Note that area 6 has food areas on two sides.

If the mouse is placed in area 6 initially, the entry to food is mostly likely to be from area 6 since there are foods on two sides of area 6.

Practice Problems

Several practice problems to reinforce the concepts discussed here are available in a companion blog. See the problems at the end of this problem set.

Dan Ma math

Daniel Ma mathematics

Dan Ma Markov chains

Daniel Ma Markov chains

\copyright 2018 – Dan Ma

Advertisements