Rejection Sampling

In previous post, I mentioned about the naive sampling method.

I would like to mention about rejection sampling which is more efficient than the naive method.

You have the target distribution(F) which you would like to draw samples from.

And its probability density function is f(x).

If you want to use rejection sampling, you should find M (constant value) and a distribution(G) (whose probability density function is g(x) which you already know how to draw samples from.

And M and g(x) meet following requirements:

and for all

1. Draw a sample from G
2. Accept the sample with a probability (). Otherwise, reject it.
3. Repeat 1 and 2 util the sample’s probability distribution is close enough to the target.

Actually when you choose uniform distribution as G, then it’s the same method as the method that I explained in the previous previous post.

The following graph helps me understand it intuitively.

I’m going to give a proof for the rejection sampling next.