Rejection Sampling

Suppose we are using rejection sampling and we want to sample from a distribution, say $p$. In order to calculate the acceptance probability we use the ratio:

$$P(u < \frac{p(x)}{Mq(x)})$$

Therefore we still use the distribution of $p$ for the randomly generated values $x$.

So why do we use rejection sampling exactly? Why don't we sample directly from $p$? In other words, what makes a distribution difficult to sample from? Thank you.

Therefore we still use the distribution of p for the randomly generated values x.

Computing the density, $$p$$, isn't the same as sampling random variables from the distribution $$p$$ is the density for.

Why don't we sample directly from p?

I'm uncertain what you mean by "sample directly". How do you propose to sample directly from $$p$$ in general?

Consider the following density, for example: $$f_X(x) = c.\exp(-\sqrt{1+x^2})$$ (to my recollection, $$c$$ can be computed in terms of Bessel functions, but its value is unimportant right now). Maybe you can figure out how to sample from that "directly" (whatever you mean by that) if you're sufficiently clever ... but personally, I'm usually not quite that clever -- and generally I'd just use (a variant of) rejection sampling for something like that.

[One additional advantage of rejection sampling in this example is that I don't even need to know $$c$$ to use it; it affects the rejection rate, but not the progress of the algorithm. There are some simple proposal densities that will work nicely for this case.]

In other words, what makes a distribution difficult to sample from?

That depends on what tools you have for generating random variables. If you know many tools, some distributions are not difficult. If you only have a few tools, many more things become difficult to sample from.

(For example, if you only know how to generate random numbers by use of the probability integral transform, then any density whose inverse cdf is difficult to evaluate will be difficult to sample from. Any distribution whose inverse cdf is expensive to evaluate will be expensive to sample from.

You might like to consider a Tweedie distribution with $$p$$ between 1.7 and 1.8, say (where you only need a few observations at any one value of $$p$$). It has some point mass at 0, but that can be dealt with. Nevertheless, the inverse cdf for the continuous part is problematic, to say the least. Even the density involves an infinite sum (which, nonetheless, can be evaluated, though it's expensive to calculate). Rejection sampling - with some tweaks to reduce function evaluations to a minimum - is possible here. Inverse cdf? I don't know that it would be practical, even if it were possible. You might figure out a way to do it using the inverse cdf if you're really clever - I think it might be beyond me, but even if you do, it's going to take a while to get your numbers.)

Rejection sampling is a very important tool in that collection (or rather, rejection sampling is itself a class of tools, because there are many clever variations on the idea), perhaps one of the most important tools. Variations on it are very widely used.

• THE perfect answer to the question... Great work... @Glen_b – Qwerty Feb 25 '16 at 7:45
• Perfect answer! Solved my doubts. – Jinhua Wang Mar 6 at 17:07

Sampling from a distribution means getting a sample with its probability matching the pdf of that distribution. In rejection sampling, we take random samples and select such that the pdf of these samples donot exceed the pdf of given distribution. This is the rejection criteria. This way we have appropriate samples and by getting large number of random sample under this criteria will represent the total picture of distribution.

• This statement is not clear and is not technically correcr. – Michael Chernick Nov 20 '18 at 19:50
• There are two points discussed here.. please point out your comment clearly 1. Rejection criteria -P(u<p(x)Mq(x)) 2. Large number of samples so that samples represent true base. youtube.com/watch?v=Pk2pSMDIXww – Cva Arahunt Nov 20 '18 at 20:06