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 \(cq^\star(x) > p^\star(x)\) for all \(x\)

Method

  1. Sample from proposal density \(q^\star(x)\)
  2. Evaluate \(c q^\star(x)\)
  3. Generate a uniform distribution \([0, c q^\star(x)]\) and sample \(u\) from it
  4. Evaluate \(p^\star(x)\)
  5. If \(u > p^\star(x)\), reject, else accept, and add \(x\) to the set of samples

Difficulties

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

Icon by Laymik from The Noun Project. Website built with ♥ with Org-mode, Hugo, and Netlify.