Absorbing states

A Markov chain is absorbing if and only if there is at least one absorbing state, of any non-absorbing state, an absorbing state can be attained. For any absorbing Markov chain and for any starting state, the probability of being in an absorbing state at time t tends to 1 when t tends to infinity.

When dealing with an absorbing Markov chain, one is usually interested in the following two questions:

  • How long will it take on average to arrive in an absorbing state, given its initial state?
  • If there are several absorbing states, what is the probability of falling into a given absorbing state?

If a Markov chain is absorbing, the absorbing states will be placed at the beginning; we will then have a transition matrix of the following form (I is a unit matrix and 0 is a matrix of 0):

proba24

The matrix N = (I-Q)-1 is called the fundamental matrix of the absorbing chain. Take the following stochastic matrix:

proba25

We have to calculate N:

proba26

The average number eij of passages in the (non-absorbing) state before absorption when starting from the i (non-absorbing) state is given by eij = (N)ij.
The average number of steps before absorption knowing that we start from the state i (non-absorbing) is the sum of the terms of the ith line of N.

In the previous example, the average number of steps before absorption is taken from the first line for state 1 : 320/37+160/37+100/37 = 15.67.

In an absorbent Markov chain with P put into canonical form, the term bij of the matrix B = NR is the absorption probability by the absorbing state knowing that we start from the state i.

In the previous example:

proba27

The probability of being absorbed by the single absorbing state is 1 whatever the initial state!

By linear equations

From a linear equations point of view, the vector of absorption probabilities is the smallest positive solution of the system:

markov13

The average reach time vector is the smallest positive solution of the system:

markov14