Metropolis–Hastings Sampling for Intractable Integrals

# Markov Chain Monte Carlo Sampling


# Markov Chain Monte Carlo Sampling












I have just been having a read about mcmc for path dependent options.

I am still trying to understand the logic of it, I don’t have the technical background to understand all the formulae etc. behind it.

So my confusion arises from the following. Say I have a set of x1,...,xn and I want to use an MCMC approach to estimate its distribution. How would I go about creating the samples?

I have read about the Metropolis-Hastings algorithm and understand that, but for the actual samples that I use, do I need to estimate what distribution my xi follow or is there another method?

Many thanks

## Answer by Dave Harris (score 3)

https://quant.stackexchange.com/a/68511

Markov Chain Monte Carlo is a tool to estimate an intractable integral. The Metropolis-Hastings algorithm is one of several such algorithms. It can be a good or bad algorithm depending on the problem and the data. If you could wait until the sample went to infinity, and if computers could actually process irrational numbers or numbers of arbitrary size, then you would be guaranteed to cover the entire density function.

If you have something drawn from function $f$ that may be unknown or in a form that is impractical to represent, then you can use proposal distribution $g$ to walk over the surface function $f$.

The Metropolis-Hastings algorithm is a simple rule. If given the opportunity to go uphill, always go uphill. If given the opportunity to go downhill or remain level, accept the new potential point probabilistically.

Skipping all of the math, it works out that the resulting distribution $h$ will be congruent to $f$ provided the algorithm has run long enough.

You can choose any candidate distribution $g$, though some distributions might be thought of as unwise. Using this method, you never need to know the true form of $\int{f}(x)\mathrm{d}x$.

Unfortunately, there isn't an automatic solution to this type of problem. It is a combination of math, art, domain knowledge, and a bit of science. While any continuous distribution $g$ will work, some might take days to converge, when others take five minutes.

The best solution is to choose simple integrals, with known analytic properties, and practice. If you can use some weirder shapes, like a torus or a two peaked distribution, then you may get to see the potential problems that you may face. You should start, however, with well-behaved, simple surfaces. The main thing is to know the answer to the integral before you try and simulate it.

This isn't a plug-and-play type of problem; you really just have to build up skills. Also, some of the software will make adjustments for bad choices that you may make, but they may make bad adjustments as well. As a result, you still need to be able to detect a problem with your work and not rely on the software to bail you out.

As to the question, do you need to know $f$, the answer is that non-parametric methods exist that get you out of that quandary, but you still need a functional form for $f$. You just don't need it for the integral.

For example, in the Bayesian problem where $f(x|\mu)\propto[1+(x-\mu)^2]^{-1}$ and you have observed $x\in\{1,5,6\}$ and $\Pr(\mu)\propto{1}$, then you end up with a formula of $$\Pr(\mu|x\in\{1,5,6\})=\frac{[1+(1-\mu)^2]^{-1}[1+(5-\mu)^2]^{-1}[1+(6-\mu)^2]^{-1}\times{1}}{\int_{-\infty}^\infty{[1+(1-\mu)^2]^{-1}[1+(5-\mu)^2]^{-1}[1+(6-\mu)^2]^{-1}}\mathrm{d}\mu}.$$

You would use MCMC to solve $$\int_{-\infty}^\infty{[1+(1-\mu)^2]^{-1}[1+(5-\mu)^2]^{-1}[1+(6-\mu)^2]^{-1}}\mathrm{d}\mu.$$

In that case, you would draw repeatedly for $\mu$ from $g$. The distribution doesn't really matter, but a normal distribution would be reasonable in this simple case.