Rejection sampling

Let us assume we are able to generate points according to some function $g({\mbox{\boldmath$x$}})$, such that, given a constant $c$, $p({\mbox{\boldmath$x$}}) \le cg({\mbox{\boldmath$x$}})$. We generate ${\mbox{\boldmath$x$}}^*$ according to $g({\mbox{\boldmath$x$}})$ and decide to accept it with probability $p({\mbox{\boldmath$x$}}^*)/c g({\mbox{\boldmath$x$}}^*)$ (i.e. we extract another random number between 0 and 1 and accept the point if this number is below that ratio). It is easy to show that this procedure reshapes $g({\mbox{\boldmath$x$}})$ to $p({\mbox{\boldmath$x$}})$ and that it does not depend on the absolute normalization of $p({\mbox{\boldmath$x$}})$ (any normalization constant can be absorbed in the multiplicative constant $c$). A trivial choice of $g({\mbox{\boldmath$x$}})$, especially for simple one-dimensional problems, is a uniform distribution (this variation is known as the hit or miss method), though clearly it can be very inefficient.