# Probabilistic Inference Using Markov Chain Monte Carlo Methods, Parts 3 & 4

These notes are based on the gnofai tutorial that covers Radford Neal’s MCMC review (pdf). Sanmi’s writeup is here. This post is mainly to index my scanned notes with keywords, so I can search for them.

We started off with a review of the motivation behind this tutorial series. What do we want? $E[f]$. Why? $P(y|x)$ can be written as $E[y|x]$

$E[f] = \int f(x)p(x)dx$, but we don’t know our distribution. So take some $z$ ~ $p(x)$. We want $\frac{1}{n} \sum f(z) \rightarrow E[f]$ as $n \rightarrow \infty$.

This is where markov chains come in: we get some $p_n(x) \rightarrow p(x)$; if our MC is ergodic, we’ll converge to $p(x)$ regardless of our starting state, $p_0$., i.e., we want to reach $p(x) = p(x)T(x)$.

The practical concerns Sanmi mentioned where work per transition, time to converge, and the number of steps we need to get IID draws from our distribution once we’ve converged.

Then there was a brief review of Gibbs sampling, to motivate the Metropolis algorithm. Recall that in Gibbs sampling, our local transitions, $B_k$, the marginals, $p(x_k | X_{\backslash k})$. With Gibbs, we fix all but one variable, sample from / change that variable, and iterate, but this requires getting the partials. Sometimes we can’t do that, and that’s when we want to use Metropolis, which is what today’s notes are about.

Unfortunately, the explosive decompression of a pen destroyed my notes for part 4, but as always, Sanmi has a nice writeup