6
$\begingroup$

Many sampling methods (e.g. rejection sampling) approach the sampling of a distribution $p$ as a problem of sampling from a different and somehow easier distribution $q$ and then correcting or accounting for the difference.

What makes some distributions easier or more difficult to sample than others? How does one find an easy distribution to sample from, for a more difficult one?

$\endgroup$

1 Answer 1

7
$\begingroup$

Computers can only do pseudo random sampling directly from a Uniform Distribution. Sampling from any other distribution requires some numerical transformations, such as Inverse Transform Sampling.

This method, however, only allows to sample from distribution that have a defined Cumulative Distribution Function that can be inverted - and this is the case for most common distributions such as Normal, Exponential, Beta, etc. - these are the "easy" ones.

However, often times we might need to sample from a distribution whose CDF we cannot (or do not want to) compute, and we only have a Probability Density Function. This is indeed pretty standard, as you can often easily create a PDF with a desired shape, but do not have the means to compute its integral.

These cases, where you cannot use inverse transform sampling, are the "hard" ones, where you need to use Rejection or Importance sampling, with the help of a known distribution that you can sample from directly (via ITS).

$\endgroup$
7
  • $\begingroup$ I'm surprised computers can only do pseudo random sampling from a Uniform distribution. Wouldn't sampling form a Normal distribution be just as easy if not easier given how ubiquitous it is in physical phenomena (e.g. via CLT)? Also, what do you mean by ITS? $\endgroup$
    – Josh
    Commented Jul 16, 2020 at 18:34
  • 1
    $\begingroup$ Sorry I wrote ITS for Inverse Transform Sampling :) $\endgroup$
    – Davide ND
    Commented Jul 16, 2020 at 20:42
  • 2
    $\begingroup$ Well, from a numerical perspective it's not even that easy to generate random numbers (following a uniform), there's a lot of research that went into that. Then of course when you use R or Python you can sample from a normal or other distributions, but what's happening under the hood is indeed a transformation of data that is sampled uniformly $\endgroup$
    – Davide ND
    Commented Jul 16, 2020 at 20:43
  • $\begingroup$ Thanks! and why is sampling from a uniform distribution easier? (any references or insight here would be great). What's special about it? $\endgroup$
    – Josh
    Commented Jul 16, 2020 at 21:49
  • $\begingroup$ Well, the uniform distribution represents complete randomness, as any outcome has the same probability. This is the most general definition of "generating a random number", and the one that is most useful in a Computer Science setting, so that's where all the research for Pseudo Random Number Generators went into. $\endgroup$
    – Davide ND
    Commented Jul 17, 2020 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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