I know that the Inverse Transform method is not always a good option to sample from distributions because it is a analytical method dependent on the shape of the distribution function. For example, the inverse one dimensional Gaussian distribution is impossible to compute, however, the sampling gives good results. I could say that for me, this method is all I need. But, could the MCMC methods (Metropolis-Hastings or Rejection) perform better than Inverse Transform? Are the MCMC methods better than IT because they cover more rare events? Or, are there any other advantages? Some examples could help! Thanks!

  • 1
    This should probably have been closed until it was made clearer, but has some good answers, so I'll let things lie for now. There are several issues, including... 1. There are many methods for sampling from normal distributions -- including many variants on rejection sampling. So rejection sampling may be both better & worse than another approach 2 Better in what sense? 3. Some of the premises aren't correct. The inverse normal cdf can be computed (to any required level of accuracy, even), it just doesn't exist in closed form. We can compute it in the same sense that we can compute an arcsin. – Glen_b Sep 27 '16 at 10:04

It's not entirely correct to say that inverse methods are impossible to compute. There are perfectly good numerical approximations to the inverse Gaussian CDF. As far as I'm aware, plenty of methods use it to generate gaussian random variables. There are of course plenty of other, possibly simpler methods of generating Gaussians.

Concerning rejection sampling, this is a mixed bag. If $f(x)$ is the Gaussian pdf, then in rejection sampling, you need to find a PDF $g(x)$ which dominates $f(x)$: $f(x)\leq Mg(x)$, for some $M>0$. One interpretation for $M$ here is the expected number of rejections you need to make before accepting a sample, so the smaller $M$ is the better. This issue can make rejection sampling a huge pain because sometimes $M$ is huge. The rule here is, if you can't find a $g$ that makes $M$ tractable, you'll need to look at other methods, for example, the inverse transform method.

For example, the exponential distribution works for the normal distribution (actually the one sided normal, after which you can flip a coin to decide on the sign). In this case, you can work out $M=\sqrt{2\pi/e}=1.32$, which is great because the exponential is very easy to generate using the inverse cdf method and you only need to throw out roughly 2 samples on average. The nice thing about rejection sampling combined with MCMC is, when used in a clever way, you can simulate rare events without actually having to wait the lifetime of the universe for the event to occur.

  • 1
    Can you precise what you mean by the exponential works for the normal? Strictly speaking this is incorrect since the exponential has a smaller support, $\mathbb{R}^+$. – Xi'an Sep 27 '16 at 8:16
  • @Xi'an: fine print: generate a half Gaussian distribution using exponential and then flip a coin to decide on the sign. I suppose you could also use a Lorenz distribution directly – Alex R. Sep 27 '16 at 21:03

Comparisons between simulation methods are only about efficiency as they all produce an output that is supposed to be from the same target distribution. Hence, you cannot expect one simulation method (like MCMC) to produce more rare events than another one, as those rare events are supposed to occur at the correct (and rare) rate.

The inverse cdf transform approach, namely to return $F^{-}(U)$ when $U$ is $\mathscr{U}(0,1)$, as distributed from $F$. is mathematically correct. It may become inefficient when computing $F^{-1}$ is too demanding. If the software of your choice includes a code for this inverse, there is no need to seek further, unless you are worried at the precision of the inversion (but then need to find another method with a higher numerical precision!). If the inverse cdf is not coded and requires a heavy coding investment, it is more efficient to seek generic methods like Markov chain Monte Carlo methods, which suffer from the drawback of not guaranteeing simulations that come exactly from the target. These are asymptotic methods in that the distribution of the simulation only converges to the target distribution when the number of Markov steps grows to infinity (except in special cases where convergence can be validated after a finite number of steps). But these also are generic methods that require less coding and planning, hence more efficient methods in the sense that computer time is rather cheap, when compared with the coder's own time.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.