The average height of all people in Cambridge can be obtained by measuring
the heights of all people in Cambridge and then averaging them:
Similarly, the following expectation can be approximated by
We can sample from directly. First find the accumlative density of
:
Assume we want to sample a complicated distribution which is not
normalized, i.e., the normalizing factor
(not necessarily
equal to 1) is unknown.The rejection sampling method makes use of a simpler
proposal distribution
, also not normalized with unknown
. Assume a scalar
can be obtained so that
is the upper bound of
for all range of
:
The accepted represent the desired distribution
, because
the rate of acceptance is proportional to the height of
. Rejection
sampling works best if the proposal distribution
is similar to the
actual distribution
, as otherwise many
values will be rejected.
Importance sampling is not a method for generating samples from ,
instead it is used to estimate the expectation of a function
.
Importance sampling can avoid the rejection (therefore wasted effort) in
previous method. To find the following expectation of
with respect
to a complicated distribution
with unknow scalar
:
If the normalizing scalars
and
are unknown, the above can still be obtained by
![]() |
![]() |
![]() |
|
![]() |
![]() |