What does it mean for MCMC to converge?

Question

I know that a Markov Chain is a discrete random process where the current state decides the next and in a random walk, the probability that we move from node u to v is 1/N(u). An MCMC sample will converge to a stationary distribution assuming aperiodicity and irreducibility - and this means that the probability of moving from node u to v is now derived from a stationary distribution and independent of the degree of node u - am I correct?

Also how is this distribution derived? And what exactly is a stationary distribution?

TIA, Craig

Answer 1

You should read Understanding the Metopolis-Hastings Algorithm which is one version of an MCMC algorithm. In essence, the idea behind MCMC sampling is as follows:

1. You wish to draw samples from a pdf, $f(\theta_1,\theta_2)$. The problem though is that $f(.)$ is either a non-standard density or perhaps numerical integration is computationally expensive because of the complexity of $f(.)$. The goal, of course, is to compute the moments of $\theta_1$ and $\theta_2$ (e.g., the mean and the variance etc).

2. In such a scenario, an MCMC sampler (e.g., the Gibbs sampler, the Metroplis-Hastings etc) constructs a markov chain with the following two properties:

   • The markov chain is constructed such that it is a reversible.

   • The markov chain's stationary distribution is $f(\theta_1,\theta_2)$ by construction.

   Therefore, MCMC algorithms converge to the target density by construction (at least in theory).

3. From an implementation perspective- we start from an initial set of values for $\theta_1, \theta_2$ and repeatedly sample $\theta_1, \theta_2$ using the MCMC sampler (See the details about the Gibbs algorithm's implementation at Wikipedia for one way to implement an MCMC sampler). In theory, the markov chain will eventually converge to the target distribution $f(.)$ by construction.

   However, there are practical difficulties as we often do not know how long to iterate the markov chain to ensure convergence. Thus, checking for the convergence of MCMC chains is very difficult and we often use heuristics (e.g., start the sampler from different starting points and monitor whether the trace plots of the draws eventually coincide etc).

Answer 2

Here's an intuitive way to understand what's going on.

Imagine that at each node there is a person with a piece of pie, and at each timestep they divide up their pie and give it out to their neighbors in different proportions. For example, someone might like one neighbor more than the others, and therefore give them a higher percentage of pie at each step. At the same time each person gives out their pie, they simultaneously receive pie their neighbors are giving. What is the steady-state distribution of pie among the people?

Well, if someone receives as much pie from each neighbor as they give to that neighbor, for all people, for all neighbors, then that would certainly qualify as a steady state. Under certain additional conditions (most importantly, ergodicity), this steady state exists and is unique.

Let $p_{ij}$ denote the fraction of pie that person $i$ gives to person $j$ at each step, and let $\pi_{i}(t)$ be the steady-state amount of pie that person $i$ has at time $t$. Then the amount of pie person $i$ gives to person $j$ at time $t$ is $p_{ij} \pi_i(t)$, and likewise the amount of pie given from person $j$ back to $i$ is $p_{ji} \pi_j(t)$. The steady state balance, wherein everyone recieves exactly as much pie from everyone else as they give, is then: $$p_{ij} \pi_i = p_{ji} \pi_j$$

Now in the above reasoning we assumed the transition probabilities $p_{ij}$ are known and the steady state distribution $\pi$ is unknown, but we can turn this around and apply it to the situation where $\pi$ is given and we want to find some $p_{ij}'s$ satisfying the above equation so that they are consistent with having $\pi$ as a steady state. This is the idea behind the Metropolis-Hastings algorithm, and MCMC more generally.