Is Markov chain based sampling the "best" for Monte Carlo sampling? Are there alternative schemes available?

Question

Markov Chain Monte Carlo is a method based on Markov chains that allows us to obtain samples (in a Monte Carlo setting) from non-standard distributions from which we cannot draw samples directly.

My question is why Markov chain is "state-of-the-art" for Monte Carlo sampling. An alternative question might be, are there any other ways like Markov chains that can be used for Monte Carlo sampling? I know (al least from looking at the literature) that the MCMC has deep theoretical roots (in terms of conditions like (a)periodicity, homogeneity, and detailed balance) but wondering if there are any "comparable" probabilistic models/methods for Monte Carlo sampling similar to Markov chains.

Please guide me if I have confused some part of the question (or if it seems confusing altogether).

Answer 1

There is no reason to state that MCMC sampling is the "best" Monte Carlo method! Usually, it is on the opposite worse than iid sampling, at least in terms of variance of the resulting Monte Carlo estimators$$\frac{1}{T}\sum_{t=1}^T h(X_t)$$Indeed, while this average converges to the expectation $\mathbb{E}_{\pi}[h(X)]$ when $\pi$ is the stationary and limiting distribution of the Markov chain $(X_t)_t$, there are at least two drawbacks in using MCMC methods:

1. The chain needs to "reach stationarity", meaning that it needs to forget about its starting value $X_0$. In other words, $t$ must be "large enough" for $X_t$ to be distributed from $\pi$. Sometimes "large enough" may exceed by several orders of magnitude the computing budget for the experiment.
2. The values $X_t$ are correlated, leading to an asymptotic variance that involves $$\text{var}_\pi(X)+2\sum_{t=1}^\infty\text{cov}_\pi(X_0,X_t)$$ which generally exceeds $\text{var}_\pi(X)$ and hence requires longer simulations than for an iid sample.

This being said, MCMC is very useful for handling settings where regular iid sampling is impossible or too costly and where importance sampling is quite difficult to calibrate, in particular because of the dimension of the random variable to be simulated.

However, sequential Monte Carlo methods like particle filters may be more appropriate in dynamical models, where the data comes by bursts that need immediate attention and may even vanish (i.e., cannot be stored) after a short while.

In conclusion, MCMC is a very useful (and very much used) tool to handle complex settings where regular Monte Carlo solutions fail.

Answer 2

There are several ways to generate random values from a distribution, McMC is one of them, but several others would also be considered Monte Carlo methods (without the Markov chain part).

The most direct for univariate sampling is to generate a uniform random variable, then plug this into the inverse CDF function. This works great if you have the inverse CDF, but is troublesome when the CDF and/or its inverse are hard to compute directly.

For multivariate problems you can generate data from a copula, then use the inverse CDF method on the generated values to have some level of correlation between variables (though specifying the correct parameters to the copula to get the level of correlation desired often requires a bit of trial and error).

Rejection sampling is another approach that can be used to generate data from a distribution (univariate or multivariate) where you don't need to know the CDF or its inverse (and you don't even need the normalizing constant for the density function), but this can be highly inefficient in some cases taking a lot of time.

If you are interested in summaries of the generated data rather than the random points yourself, then importance sampling is another option.

Gibbs sampling which is a form of McMC sampling lets you sample where you don't know the exact form of the multivariate distribution as long as you know the conditional distribution for each variable given the others.

There are others as well, which is best depends on what you know and don't know and other details of the specific problem. McMC is popular because it works well for many situations and generalizes to many different cases.