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 \(cq^\star(x) > p^\star(x)\) for all \(x\)
Method
- Sample from proposal density \(q^\star(x)\)
- Evaluate \(c q^\star(x)\)
- Generate a uniform distribution \([0, c q^\star(x)]\) and sample \(u\) from it
- Evaluate \(p^\star(x)\)
- If \(u > p^\star(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