Jethro's Braindump

Rejection Sampling

Goal: To sample from unknown distribution $p (x)$ .

Assumptions

we cannot sample from $p (x)$
we have a simple proposal density $q (x)$ we can evaluate within a multiplicative factor $Z_{q}$
We know the value of a constant $c$ , such that $c q^{⋆} (x) > p^{⋆} (x)$ for all $x$

Method

Sample from proposal density $q^{⋆} (x)$
Evaluate $c q^{⋆} (x)$
Generate a uniform distribution $[0, c q^{⋆} (x)]$ and sample $u$ from it
Evaluate $p^{⋆} (x)$
If $u > p^{⋆} (x)$ , reject, else accept, and add $x$ to the set of samples

Difficulties

Works well only when $q (x)$ is a good approximation to $p (x)$ , keeping $c$ small
In high-dimensional settings, $c$ will generally be so large that acceptances will be rare

Links to this note