Why not just run a Markov chain to get stationary probabilities?

Question

I'm reading Performance Modeling and Design of Computer Systems which contains some analysis of Markov chains. In particular, it emphasises various analytical methods for finding the stationary distribution of a Markov chain.

Here's what confuses me: when I have formally studied computer-intensive statistics (more specifically, Monte Carlo integration) in the past, a core theme has been about constructing Markov chains that have stationary distributions that approximate the distribution you want to draw from, and then running those Markov chains to get draws from the desired distribution.

So here we have one source preferring to analytically derive the distribution implied by a Markov chain, and another that prefers to imply a Markov chain and then run it to get draws from a distribution.

It seems much easier to me to just run the chain -- so why is it that is not preferred by some statisticians?

I get the argument for analytic solutions in some edge cases where running the chain might have extreme computational cost -- but that has not been the case in the examples I've seen.

Will I make a mistake in practical terms if I choose to run the chain instead of derive probabilities analytically?

Answer 1

In theory, some Markov chains will not have a stationary distribution. Hence, using theoretical approaches deriving the stationary distribution from the transition matrix itself should identify this issue, while simply running simulations could make it more difficult, especially if you are not careful about this potential issue.

Answer 2

I find it useful to draw a distinction between the standard use of Markov chains for statistical modelling purposes from use of MCMC techniques for integration. In the latter case, we are talking about a clever use of Markov chains to write an integral of interest as the stationary distribution of the chain, in order to allow a new form of numerical integration. This is essentially the reverse of the standard use of Markov chains, where the chain itself is specified, but its stationary distribution is derived from specification of the model.

Outside of the use of MCMC methods for numerical integration, Markov chains are most commonly used for direct statistical modelling of data. There are a number of results in this analysis that are made easier if you can derive the spectral decomposition of the transition probability matrix (or more generally, the Jordan normal form), which includes derivation of the stationary distribution(s). Knowledge of this form allows you to get a number of simplified results in the analysis, so it is a common early computational step. There are a few reasons that analytic derivation of the stationary distribution(s) is preferred over just running the chain for a long time:

• Derivation of the stationary distribution(s) is often just seen as one piece of the broader derivation of the spectral decomposition (or Jordan normal form) of the transition probability matrix. Once you derive all the eigenvalues and unit eigenvectors of this matrix, it is helpful for various aspects of later analysis. As part of this derivation you will have identified the stationary distribution(s) of the chain.

• There are cases of Markov chains where there are stationary distribution does not exist or is not unique. In the latter case, any convex combination of two stationary distributions is also a stationary distribution. Consequently, deriving the stationary distribution merely by running the chain for a long time may not work, and if it does it often misses the full specification of all possible stationary distributions in the chain.

• Direct analytic derivation of the stationary distribution is often computationally quicker and more accurate than derivation via running the chain for a long time.

Answer 3

The book I was reading pointed out in a later chapter the obvious that I had missed.

By learning to work on Markov chains analytically, it's possible to derive probabilities that are functions of inputs of high dimension, and answer more interesting counterfactuals in the form of "if I vary this one parameter out of five, what happens to the quantities involved?"

This is technically possible also numerically, but the higher dimensions of inputs start to hurt sooner -- both computationally and in trying to interpret the results, as they will always be conditional on a bunch of other values.