What is Rejection Sampling?

Question

I just start to learn this topic and I don't understand what rejection sampling is. can someone give a brief explanation about it? I need to do rejection sampling in R programming.

Answer 1

The way I like to think about it is the following: I want to sample a uniform element of some set $S$, but I only have access to uniformly random elements of a superset $A$ of $S$ (i.e., $S\subset A$). So quite naturally, what I do is sample elements uniformly from $A$ until I get an element $s$ from $S$; the content of the idea of 'rejection sampling' is basically that this element $s$ will then be uniformly distributed across $S$.

Why is this useful? Oftentimes, we don't have easy direct access to uniform samples of $S$, but we do have access to uniform samples from $A$. A very common situation is that $S$ is the set of all elements of $A$ satisfying some possibly complicated property which is however easy to verify for each given element. So rejection sampling saves you from the trouble of having to come up with a smart algorithm to sample over the elements of $A$ with this property, by just sampling over the entire $A$ until the property is fulfilled.

Does it generalize? There are many variations on this theme. For example, the distributions on $A$ and $S$ don't have to be uniform - but then they'll be related by the fact that the distribution on $S$ will be the distribution on $A$ conditioned on the fact that the outcome lies in $S$.