Is there an intuitive way to understand a sequential Monte Carlo Markov Chain?

Question

I was wondering if there was an intuitive way to understand what a sequential Monte Carlo Markov Chain is. It also goes by the name of particle filtering. Is there an intuitive way to think about it/teach it to someone? Thanks!

Answer 1

The term is "Markov Chain Monte Carlo" and it is a technique used for approximating expectations/integrals involving probability distributions that are difficult to sample from.

Monte Carlo methods require sampling to approximate expectations. The Markov Chain is the tool used to sample. In particular this method is used when one has access to a non normalized probability mass/density function.

A Markov Chain is a probabilistic model for movement on a graph. I will let you look up the details. Consider a random walk on a Markov Chain with states $X_0, X_1, \dots$. Suppose we start the walk at state $s$. Now consider:

$$ P(X_n = t | X_0 = s). $$

When $n$ is small this depends greatly on the starting state, but as $n$ goes to infinity (under reasonable Markov Chain assumptions that I'll let you look up) this converges to a distribution that does not depend on $s$.

In MCMC we construct a Markov Chain whose stationary distribution is the distribution we're trying to sample from. Then a sufficiently long random walk on that Markov Chain closely resembles drawing samples from that distribution. The construction of this Markov Chain is too involved for this post, but you can look up Metropolis Hastings. I hope this helped with the intuition.

edit

My apologies. The word sequential didn't give me the sense that this was a separate idea (there are many sequences in MCMC already). As it appears that MCMC is a common technique used in sequential MC, I will leave this answer up.