Markov Chains Part 2

This post is the second in a series about Markov chains, a common stochastic modeling framework to simulate random phenomena. See Part 1 if you are not familiar with Markov chains, or if you simply need a refresher.

Often, when using a Markov chain to model a real-world phenomenon, it is important to study the end behavior of the Markov chain. For instance, does the chain always end in a single state, independent of the starting state? Are some - but not all - of the states possible in the long-term? If multiple states are possible, which are more likely, and can we quantify the probability of being in one state specifically? This post will attempt to explore these questions.

Absorbing Makrov Chains

An absorbing Markov chain has at least one absorbing state. State i is an absorbing state if the Markov chain cannot leave state i:

For example, in the simplest SIR model for infectious diseases, an individual develops immunity after recovering from the disease. The recovered compartment, therefore, would be modeled as an absorbing state, since there is no way for a recovered individual to transition to being either susceptible or infected. Note that if state i is not absorbing then it is transient, since the Markov chain can only be in state i for a finite amount of time before transitioning to an absorbing state that prevents a return to state i.

Let an absorbing Markov chain with have t transient states and r absorbing states. Then its transition probability matrix (TPM) can be written in the following block form:

where is a TPM from one transient state to another, is a TPM to go from a transient state to an absorbing state, is the zero matrix, and is the identity matrix, representing the TPM for the absorbing states.

The matrices are very important because they can be used in many important calculations. One of the most common questions when analyzing 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 Summing this for all k from 0 to infinity yields the fundamental matrix. It can be proven that where is the t-by-t identity matrix. The (i,j) entry of the fundamental matrix is the expected number of times the chain is in state j, given that the chain started in state i.

The name fundamental matrix derives from the fact that the matrix can be used to obtain many other useful quantities. For example, the expected number of steps before being absorbed when starting in transient state i is the ith entry of the vector Additionally, the probability of being absorbed by absorbing state j when starting in transient state i is given by the (i,j) entry of

Stationary Distribution

Many real-world phenomena are not described by an absorbing Markov chain. For example, consider a simple weather model of rainy days and sunny days. Rain clouds and sunshine are always possible, so neither state is transient nor absorbing. Instead, both states are recurrent. State i of a Markov chain is recurrent if the chain is guaranteed to return to state i within a finite amount of time once it leaves state i; equivalently, state i is recurrent if the Markov chain visits this state infinitely often.

When dealing with a Markov chain of only recurrent states, studying the end behavior becomes trickier. All states are possible in the long-term, so we can only talk in terms of probability when describing what will happen in the long-run. A probability vector¹ on a Markov chain state space is called a stationary distribution of the TPM if

Under special conditions², which are true in most applications, the stationary distribution exists and is unique. Moreover,

which, in words, means that, over the long run, independent of the starting state, the time that the Markov chain will spend in state j is approximately equal to the jth entry of the stationary distribution for all j. The stationary distribution, therefore, gives us a concise, mathematical description for the end behavior of the Markov chain!

¹ A probability vector has the property that the entries, all of which are non-negative, sum to 1.

² Specifically, the Markov chain needs to be irreducible and aperiodic.