Markov Chain Converge then Unconverge?

Question

I have a MCMC algorithm for which I know the transition matrix $T(x_{t+1},x_t)$. If the Markov chain has converged such that $x_{t-1} \sim \pi$, how do I show that $x_i$ is marginally distributed according to $\pi$ also?

My initial reaction is that I don't really understand the question. If the Markov chain has converged to $\pi$ at timestep $t$ then,by definition of convergence, how could it have any distribution other than $\pi$ at timestep $t+1$?

What do I actually need to do to show this? Is it a case of showing that there is a unique stationary distribution? Or is it detailed balance? I don't really understand what is being asked here.

Thanks.

Answer 1

If you're studying the Markov chain only by looking at simulations of its behavior, it is possible to miss an almost-absorbing class that is visited regularly over the very long run.

Suppose the chain mainly alternates between states 1 and 2 at the beginning. It looks as if the chain is reaching a limiting distribution. Then suddenly it visits state 3 and begins to alternate between states 3 and 4, appearing to disrupt the convergence. Over the long run it 'mixes' among all four states.

One reason that one must look at the history plot of a Gibbs Sampler is to make sure there are no 'sticking places' that will cause the limiting distribution to be something other than you first suppose.

Consider the chain with the following transition matrix, and starting in state 1:

P = matrix(c(.299, .7, .001,  0,
             .6,   .4,   0,   0,
              0,    0,  .5,  .5,
             .001,  0,  .5, .499), byrow=T, nrow=4)

set.seed(506)
m = 3000;  x = numeric(m);  x[1]=1
for (i in 2:m) {
 x[i] = sample(1:4, 1, prob=P[x[i-1],])
 }
par(mfrow=c(2,1))
 plot(x,ylim=c(1,4), type="l", 
      ylab="State", main="History")
 plot(cumsum(x)/(1:m), type="l", 
      ylab="Running Avg", main="Trace") 
par(mfrow=c(1,1))

Up until about step 1920 it looks as if the chain is alternating between states 1 and 2, and the trace is settling to a running average of about 1.54. But then the process "discovers" the other two states. (Over a sufficiently long run the average state will be about 2.5.)

Note: The stationary vector of an ergodic chain (which is also the limiting distribution) is proportional to the left eigenvector of $P,$ with the largest modulus. Thus the exact mean of the limiting distribution is 2.480258:

g=eigen(t(P))$vectors[,1]  # largest modulus listed first
sg = g/sum(g)              # distribution must sum to 1
sum((1:4)*sg)              # find mean
[1] 2.480249

Answer 2

The lovely answer by BruceET gives a good example of a case where you have "almost-separated" sets of states (i.e., sets of states that have an extremely low transition probability between each other). In this case you can run your chain for quite some time, and it can appear to have converged to its stationary distribution when, in fact, it has not entered a particular set of possible states yet. Alternatively, you may get a situation like he shows, where you have had only a single transition between sets of states, and so you cannot be confident that you have run the chain long enough to accurately determine the transition probabilities between these sets of states. That answer shows that we can never really be certain of how long we need to run to ensure convergence that is "close enough" to its stationary distribution, but we can sometimes tell from the trace plot that we need to run the chain longer.

Nevertheless, stepping back from this example, I think your question does indeed rest on what you mean when you say that your chain "has converged". The obvious follow-up question is: converged to what, and how closely? If the chain has indeed converged perfectly to its stationary distribution then you have $x_t \sim \pi$ and so ---by definition--- you also have $x_{t+k} \sim \pi$ for all $k \in \mathbb{N}$. This means that the stationary distribution is also the marginal distribution of each future value in the series. It doesn't even matter if the stationary distribution is not unique; if it has converged to any stationary distribution then this property holds (since it is the definition of what a stationary distribution is). There is not really anything to show here, since the conclusion you are seeking is a direct restatement of the definition of the stationary distribution.

In practice however, when we say that an MCMC chain "has converged" we usually mean something weaker than this. The whole idea of MCMC analysis is that we don't know the stationary distribution (that is what we are trying to estimate) and so we start the chain at some arbitrary starting distribution and then run it for a long time and hope it has "converged". For any starting distribution $\pi_0$ we have a sequence of true marginal distributions $\pi_0, \pi_1, \pi_2,...$ over all the future time periods, determined by the transition probabilities of the Markov chain. Assuming that the starting distribution is different to the stationary distribution (i.e., $\pi_0 \neq \pi$), we will generally have $\pi_t \neq \pi$ for all $t \in \mathbb{N}$ but we will also usually have $\pi_t \rightarrow \pi$ in the limit. That is, it is usually the case that the marginal distribution induced by the MCMC chain never perfectly matches the stationary distribution in a finite number of steps, but it does converge asymptotically. In practice we run the chain for a long time $T$ until we are confident that $\pi_T$ is "close enough" to $\pi$ that the chain "has converged". This is where things get complicated, and you need to look at the ergodic properties of Markov chains, and specify some greater detail on the nature of your "convergence".

So, in summary, if you actually mean that there is perfect convergence to a stationary distribution at some finite time $t$, then the result you are seeking is just a trivial restatement of the definition of the stationary distribution. If instead you mean something weaker than this (e.g., that the true marginal distribution is "close to" the stationary distribution) then it becomes more complicated.