Next: Importance sampling
Up: Monte Carlo methods
Previous: Estimating expectations by sampling
Let us assume we are able to generate points according to
, such that, given a constant ,
. We generate
and decide to accept it with probability
(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
and that it does not depend on the absolute normalization
(any normalization constant can be absorbed in the multiplicative constant ).
A trivial choice of
, 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.