0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ I don't think you are certain to reach the stationary distribution in finite time $\endgroup$
    – jcken
    Jul 28 at 10:30
  • $\begingroup$ @jcken in fact, I think I'm guaranteed not to reach it! But in practical terms, as an industrial statistician facing ill-specified problems and decisions with some tolerance for error, I usually get close enough to it in a time span measured in minutes at worst, in my experience. And I can always verify whether I have with the bootstrap, so I don't think of that as an obstacle. $\endgroup$
    – kqr
    Jul 28 at 10:51
  • 2
    $\begingroup$ MCMC builds a Markov chain with a guaranteed stationary that is given in one form or another. This perspective is reversed: the Markov chain is given and the goal is to find its stationary, if any. $\endgroup$
    – Xi'an
    Jul 28 at 10:51
  • $\begingroup$ @Xi'an right, which implies to me that running the Markov chain is, at least in many cases, comparatively effective to find the stationary distribution. So why would the authors prefer analytical solutions? $\endgroup$
    – kqr
    Jul 28 at 14:30
  • 1
    $\begingroup$ Running a Markov chain "until" stationary provides one realisation from the stationary distribution (assuming one can be certain to be in the stationary regime). This is far from "finding" the stationary distribution. $\endgroup$
    – Xi'an
    Jul 29 at 5:43

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ While this is a valid concern, I'm not sure "some prefer analytical solutions because if you're not careful the numerical solution might be inappropriate" is an argument that flies with me, simply because you have to be very careful to get analytical solutions right too! $\endgroup$
    – kqr
    Jul 28 at 14:32
  • $\begingroup$ Fair enough! Both require some checks. $\endgroup$
    – FP0
    Jul 29 at 0:00
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is a general fact. Mathematical analysis always is superior to simulation in this respect. $\endgroup$
    – whuber
    Jul 30 at 16:28
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.