Rejection sampling

An algorithm to sample from a distribution $f_X(x)$

Assumptions:

• Need a bounding distribution $g_X(x)$ that you can sample from easily
• The ratio of the functions is bounded, so $\frac{f_X(x)}{g_X(x)}\le M\le \infty$
• Define $h(x)=\frac{f(x)}{g(x)M}$

Algorithm

1. Generate some realization y from $g_X(x)$
2. Find $h(y)$
3. Sample $u$ from $U[0,1]$
4. If $u<h(y)$, accept $y$ If $u\ge h(y)$, reject $y$

The $\{acceptedy\}\sim f$ - they are realizations of f

---

References

Simulating distribution @rice2007 @lancaster2004 - Chapter 5