Absorbing Markov chain

In the mathematical theory of probability, an absorbing Markov chain is a Markov chain in which every state can reach an absorbing state. An absorbing state is a state that, once entered, cannot be left.

Like general Markov chains, there can be continuous-time absorbing Markov chains with an infinite state space. However, this article concentrates on the discrete-time discrete-state-space case.

A Markov chain is an absorbing chain if

In an absorbing Markov chain, a state that is not absorbing is called transient.

Let an absorbing Markov chain with transition matrix P have t transient states and r absorbing states. Then

where Q is a t-by-t matrix, R is a nonzero t-by-r matrix, 0 is an r-by-t zero matrix, and I_r is the r-by-r identity matrix. Thus, Q describes the probability of transitioning from some transient state to another while R describes the probability of transitioning from some transient state to some absorbing state.

A basic property about an absorbing Markov chain is the expected number of visits to a transient state j starting from a transient state i (before being absorbed). The probability of transitioning from i to j in exactly k steps is the (i,j)-entry of Q^k. Summing this for all k (from 0 to ∞) yields the fundamental matrix, denoted by N. It is easy to prove that

where I_t is the t-by-t identity matrix. The (i, j) entry of matrix N is the expected number of times the chain is in state j, given that the chain started in state i. With the matrix N in hand, other properties of the Markov chain are easy to obtain.

The variance on the number of visits to a transient state j with starting at a transient state i (before being absorbed) is the (i,j)-entry of the matrix

where N_dg is the diagonal matrix with the same diagonal as N and N_sq is the Hadamard product of N with itself (i.e. each entry of N is squared).

The expected number of steps before being absorbed when starting in transient state i is the ith entry of the vector

where 1 is a length-t column vector whose entries are all 1.

The variance on the number of steps before being absorbed when starting in transient state i is the ith entry of the vector

...
Wikipedia