Preliminaries

This is a continuation of Lab 5. You should review that material and Section 11.6 in the text.

Basics

As before we are studying random transitions between states and the focus is on the transition matrix P with entries p_ij where p_ij is the probability of a transition from state j to state i as we go forward one time step.

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 i = k and in that case the value is 1.

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

Note we still have each column sum to 1. Now if we start with the distribution x = (1, 0,0,0), i.e. all well, and apply the transition 100 times to get P¹⁰⁰x = (0,0,0.3,0.7). If instead we start with x = (0.9, 0.1, 0,0) we end with (0,0,0.31,0.69).

Theory with Partition Matrices

If we put all the absorbing states at the end, then the transition matrix looks like this:

    [  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² and we get

      [  A2        0 ]
P2  = [              ]
      [  BA + B    I ]

It can be shown that as you take higher powers of P it tends toward:

      [  0          0 ]
Pn -> [               ]
      [  B(I-A)-1   I ]

From 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)^-1 is

[ 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.

Exercises

1. Consider this simple dice game. The object is to roll the numbers 1, 2, 3, 4, 5 and 6 in order without repeating. There are 8 states: start, rolled 1, rolled 12, rolled 123, rolled 1234, rolled 12345, won, and out. If you are at the start you roll each turn until you get a 1. If you are in any of the rolled states, you roll the die on your turn. If you get the next number you move to that state (or the won state if you had 12345 and rolled a 6). If you roll the last number in your sequence, you're out and if you roll any other number you go back to the start.
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)^-1 and B*F. What is the probability that you win if you are in state 'rolled 1234' now? On average how many rolls does it take before you are either out or have won?

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.

---