Rejection Sampling

Algorithm Rejection Sampling
We want to sample from PDF $f(x)$, but this is difficult to do. Suppose we have proposed PDF $g(x)$, then we can:

1. Generate $x^{\star }$ from $g(x)$
2. Accept $x^{\star }$ with probability $\frac{f(x^{\star })}{Kg(x^{\star })}$
   Or equivalently,
3. Generate $x^{\star }$ from $g(x)$
4. Generate $y^{\star }$ from $\mathcal{U}(0,Kg(x^{\star }))$
5. Accept $x^{\star }$ if $y^{\star }\le f(x^{\star })$
   where we require $f(x)\le Kg(x)$ for all $x$. For efficiency, we can let $K={\max }_x\frac{f(x)}{g(x)}$.