Markov Chains II - Absorbing States

In this lab we are encountering what are call *Absorbing States*.
These are states such that when you enter them, you never leave. So
if **k** is an absorbing state, then **p _{ki}** = 0
except when

When there are absorbing states the transition matrix is not regular as you can never get from an absorbing state to any other state. Also the steady-state distribution will only have non-zero entries in the absorbing state, and so if there is only one absorbing state then we know the steady-state distribution is (0,0,0,...,0,1). If there are more than one absorbing state, then the steady-state distribution will be betwee those absorbing states and will depend on the initial distribution.

For example, suppose we have a disease with 4 states: 1 = well, 2 = sick, 3 = dead and 4 = immune. 3 and 4 are absorbing states and the transition matrix would look like:

0.6 | 0.2 | 0.0 | 0.0 |

0.3 | 0.6 | 0.0 | 0.0 |

0.0 | 0.1 | 1.0 | 0.0 |

0.1 | 0.1 | 0.0 | 1.0 |

[ A 0 ] P = [ ] [ B I ]where A and B are matrices, 0 is the zero matrix and I is the identity. We call this a partition matrix when we write the elements of the matrix as matrices. Now, as long as we remember the rules of matrix arithmetic, we can compute with P as a partition matrix just like we do with a regular matrix. For example, compute P

[ AIt can be shown that as you take higher powers of P it tends toward:^{2}0 ] P^{2}= [ ] [ BA + B I ]

[ 0 0 ] PFrom the example above we have A = [0.6, 0.2; 0.3, 0.6] and B = [0.0, 0.1; 0.1, 0.1]; and so B(I-A)^{n}-> [ ] [ B(I-A)^{-1}I ]

[ 0.3 0.4] [ 0.7 0.6]This represents the eventual transition from states 1 and 2 into the absorbing states 3 and 4. So, for example, if you start out well, you have a 30% chance of dying and a 70% chance of becoming immune.

Another important component is F = (I-A)^{-1}. This
matrix represents the average time you spend in each non-absorbing
state before you get absorbed. In our example, F is

[ 4 2 ] [ 3 4 ]This says that if you are well, you'll spend, on average 4 time periods well and 3 time periods sick before you enter an absorbing state. If you are sick, you'll be well 2 times and sick 4 times before being absorbed.

Construct the 8 x 8 transition matrix for this game.

Assuming you start in state 'start', find out the probability that you win after 100 turns.

Compute the matrices F = (I-A)

2. Consider this gas molecule simulation in 1D. We have
**n** states representing the **n** places along
the x-axis that we can locate the molecule. Assume
states 1 and **n** are absorbing and that in the
other states you have 50% chance of not moving, 25% chance
of moving up (right)
and a 25% chance of moving left (down).

Pick a value for **n** (5 or larger)

Construct the **n** by **n** transition matrix.

Determine the probability that you will end up in the
**1** absorbing state from starting at each of the
other non-absorbing states.
that the molecule can

Make a change in the movement rules by (1) adding
a small chance of a double jump, (2) making the left-right
chances unbalanced, (3) adding a 3rd absorbing state in the center
(odd **n** only). Determine the probabilities of ending
in the various absorbing states under this new scheme.