How does a Markov Chain converge to a distribution we don't know?

Question

As succinctly stated in this answer:

it is possible to design a Markov chain with a stationary distribution equal to the posterior distribution, even though we don't know exactly what that distribution is.

To anyone without a rather deep understanding of the statistics behind Markov Chains, this sounds like pure magic. How can you construct a process that guarantees convergence to a distribution you don't know?

All the information I've found on the topic is quite mathematically involved, and not suitable for an introductory course for non-statisticians. How would you explain this property of Markov Chains in a simple way?

Answer 1

Let's emphasize the key part of the original statement.

it is possible to design a Markov chain with a stationary distribution equal to the posterior distribution, even though we don't know exactly what that distribution is.

While we don't know exactly what the distribution is, we can compute the density function up to a normalizing constant. This normalizing constant disappears when if we start thinking of ratios, i.e., if we have that $f$ is our posterior density (up to a multiplicative constant) then even without knowing that normalizing constant, if we know that

\begin{equation} f(\theta_1) = 2f(\theta_2) \end{equation}

then we know that $\theta_1$ is twice as likely as $\theta_2$ in the posterior. Note that this relation alone completely specifies the distribution; if you were able to make a function that could take random samples and in the long run, this relation of ratios is preserved, then you can take draws from the posterior exactly. This is the goal of an MCMC algorithm.

While there are a lot of different MCMC algorithms, the general theme is coming up with a really clever way of drawing samples where, in the long-run, one can reason that these ratios are preserved. For simplicity, let's think about the Metropolis-Hasting algorithm. Without going into a full proof, we can think that in the MH algorithm, we are taking draws from a random process (i.e. a random walk). We then essentially upweight draws that have very high posterior densities by getting "stuck" at that spot for several iterations, relative to spots that have low density in the posterior. Math that we apparently want to avoid tells us that in the long run, this will preserve the ratios given by the non-normalized posterior density function.

Answer 2

I think Ben overstates the resulting result a little in that answer. We do know something that is extremely useful, namely that we can query the function $\pi(\theta|x)$ in such a way that we always receive back $f(\theta|x)/Z$, where $Z^{-1} = \int_\Theta \pi(\theta|x) d\theta$, and $f(\theta|x) = L(x|\theta)p(\theta)$, the product of the likelihood and the prior. But this immediately implies another fact: that if we want to query a ratio of $\pi$ evaluated at two different values $\theta'$ and $\theta$, the ratio of $Z$s will immediately cancel, leaving the correct corresponding ratio. We can then proceed to design a clever Markov chain (via the Metropolis-Hastings method) that exactly uses this ratio when generating moves on $\Theta$.