5.2 Various Sampling Methods
87
5.2.2 Rejection Sampling
Unfortunately, the indefinite integral of the probability density function P (x) is
not always known. Even in unknown case, we can use the rejection sampling
method. In the rejection sampling, we assume that a sampling from some probability
distribution Q(x) is possible. For example, we may use Q(x) for that we can use
the inverse transform method. Another assumption to use this method is
There exists some number M(>0), and for any x, MQ(x) ≥ P (x).
(5.31)
As long as this is satisfied, the sampling from P (x) is possible, as follows:
1. x candidate is sampled according to Q(x).
2. If
P (x candidate )
MQ(x candidate ) is larger than a random number 0 < r < 1, the sample x candidate
is adopted. This is called accepted. If the above condition is not met, we discard
x candidate . This is called rejected. 9
To understand why this method works, we use Bayes’ theorem (see the column in
Chap. 2) to find the x probability distribution for the acceptance,
P (x|accepted) =
P (accepted|x)Q(x)
P (accepted)
.
(5.32)
This is because
P (accepted|x) =
P (x)
MQ(x)
(5.33)
and we substitute
P (accepted) =
P (accepted|x)Q(x)dx =
1
M
(5.34)
into (5.32) to find
P (x|accepted) = P (x) .
(5.35)
Collecting only the accepted x candidate results in a sampling from the probability
distribution that we want. With this method, now we can sample from a fairly large
class of probability distributions.
9 Note that this operation is different from the rejection by the Metropolis method that will be
explained later.