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.
Asked
Active
Viewed 576 times
2 Answers
2
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$.
amakelov
- 3,520
- 12
- 25
0
You need a proposal function $g(x)$ which satisfies $f(x)<cg(x)$ and is easy to sample from. Here we define $c$ as: $$c=\sup_x\frac{f(x)}{g(x)}.$$ The first step is to generate $X$ from $g(x)$. For instance, using inverse sampling method. Next generate $U$ from the standard uniform distribution, $U[0,1]$. At last: if $U\leq \frac{f(X)}{cg(X)}$, then we accept $X$ or esle we repeat step 1.
esmo
- 97