5
$\begingroup$

What are the different methods by which we can generate random samples from the existing distribution which are computationally efficient?

One of the common methods given in statistics text is by applying a transformation called the inversion method. We start with a Uniform(0,1) distribution from which we can pick an arbitrary number, and then use the inverse of the CDF of the distribution (its quantile function) to find the member of the desired distribution corresponding to the randomly chosen number between 0 and 1.

What other methods exist for doing the same?

$\endgroup$
  • $\begingroup$ one issue with the inversion method is that if the quantile function isn't available in closed form (i.e. you can't invert it to get the member of the desired distribution as a simple function of the randomly chosen number between 0 and 1), then you have to numerically solve to get the inverse. So simple textbook examples using the inversion method don't necessarily generalize to more complex distributions. $\endgroup$ – TooTone Jul 22 '13 at 10:35
  • 1
    $\begingroup$ There are books largely or wholly about this: e.g. Morgan, Elements of Simulation, or Devroye, Non-Uniform Random Variate Generation. $\endgroup$ – Scortchi Jul 22 '13 at 10:39
  • $\begingroup$ Generating samples efficiently from general distributions is not possible. $\endgroup$ – ziggystar Jul 22 '13 at 12:26
  • 1
    $\begingroup$ @ziggystar I'm curious: could you provide some support for this provocative assertion, such as an example of a distribution where "efficient" sampling is impossible? $\endgroup$ – whuber Jul 22 '13 at 17:43
  • $\begingroup$ Take the uniform distribution over the solutions to a boolean formula. Coming up with any solution is NP-complete; generating one uniformly is supposedly even harder. Generating samples from a Markov network (or MRF) is intractable in general, too. I admit that these are non-trivial, multivariate distributions, but they are "distributions". Also I suppose that there are ways to encode any multivariate distribution over discrete variables into a single continuous univariate distribution. $\endgroup$ – ziggystar Jul 23 '13 at 7:39
5
$\begingroup$

Other methods include accept-reject methods and Markov Chain Monte Carlo (MCMC) methods. Note that the method described in the question is part of the so-called inverse transformation methods. There exists other ad-hoc simulation methods for specific distributions (e.g., the Box-Muller transform for univariate normal distribution).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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