3
$\begingroup$

I have a confusion about the "intuitive explanation" of rejection sampling given at this link on (apologies, I know it's not always a good source) Rejection Sampling. The text in the introduction reads as follows (emphasis and additions mine)

Rejection sampling works as follows:

  1. Sample point on x-axis from proposal distribution p(x).
  2. Draw vertical line at this x-position, up to the maximum y-value of the proposal distribution, p(x).
  3. Sample uniformly along this line $\alpha$ from 0 to the maximum of the probability density function p(x). If sampled value is greater than the value of the desired distribution at this vertical line f(x), reject the x-value and return to step 1; else the x-value is a sample from the desired distribution.

My confusion is in the use of the word "maximum." The mathematical formulation of the rejection criterion is based upon comparing the uniform random variable $\alpha$ as follows:

  1. Draw $\alpha \sim U(0, M p(x))$ where $M$ is the constant ensuring $Mp(x) > f(x)$ envelopes the desired distribution.
  2. If $\alpha > f(x)$ reject.

However, the text written above seems to suggest drawing $\alpha \sim U(0, \textrm{max}(p(x))$ which greatly increases the spread of the samples, since we would now include values of $\alpha > p(x)$.

Is the article incorrect, or is it assuming that the proposal distribution is uniform? Or have I misinterpreted the text and the use of the word "maximum?"

Related to this, the application of my question is to the following:

I want to use rejection sampling to improve the sampling of a function. Right now I am generating samples from a proposal, p(x), with a mechanism that approximates the desired distribution, f(x), but in such a way that I don't actually know p(x).

Is there a sampling method that allows me to accept or reject these samples according to their value of f(x) without knowing the exact value of p(x) for each sample x?

$\endgroup$
3
  • 1
    $\begingroup$ The whole idea of rejection sampling is to compare your function f, which can be arbitrarily hard to deal with, with a known and relatively simple function p. If your p is hard to evaluate than you have a chosen a bad p. The p function can be whatever, but it should always be greater than f, so you can imagine for ex. choosing a normal distribution multiplied by a factor of 2 for p. $\endgroup$ Mar 5, 2021 at 12:49
  • 1
    $\begingroup$ The way it is written in that section of the wikipedia article is confusing; it seems like an attempt to make it more intuitive. Your understanding of it is correct. The wikipedia article explains it better in the section after that. $\endgroup$
    – John L
    Mar 5, 2021 at 13:07
  • $\begingroup$ Ok, great, so the sample that is taken along their "vertical line" goes up to the proposal distribution at the point $x$, being $p(x)$ and not up to the maximum of the distribution? $\endgroup$
    – lux
    Mar 5, 2021 at 17:35

1 Answer 1

4
$\begingroup$

The explanation is doubly confusing in that (1) the "maximum" is meant as $p(x)$ rather than as $\max_x p(x)$. And (2) this maximum should be $Mp(x)$ where $M$ is an upper bound on $f(x)/p(x)$ over all $x$'s. Generating a pair $(x,\alpha)$ this way produces a Uniform generation over the sub-graph of the function $Mp(\cdot)$. In the event the pair $(x,\alpha)$ also belongs to the sub-graph of the function $f(\cdot)$, it is then a Uniform generation over this sub-graph. Therefore, the marginal density of the accepted $x$ is $f(x)$, which validates the algorithm. (This is also the principle behind slice sampling.)

Here is an illustration taken from our book (pp.53-54):

To simulate beta $\mathcal{B}e(\alpha, \beta)$ random variables, we can, however, construct a toy algorithm based on the Accept--Reject method, using as the instrumental distribution the uniform ${\cal U}_{[0,1]}$ distribution when both $\alpha$ and $\beta$ are larger than $1$. (The generic rbeta function does not impose this restriction.)

The upper bound $M$ is then the maximum of the beta density, obtained for instance by optimize (or its alias optimise):

 optimize(f=function(x){dbeta(x,2.7,6.3)},
         interval=c(0,1),max=T)$objective
 [1] 2.669744

Since the candidate density $g$ is equal to one, the proposed value $Y$is accepted if $M \times U < f(Y)$, that is, if $M \times U$ is under the beta density $f$ at that realization. Note that generating $U \sim {\mathcal U}_{[0,1]}$ and multiplying $U$ by $M$ is equivalent to generating $U \sim {\mathcal U}_{[0,M]}$. For $\alpha = 2.7$ and $\beta = 6.3$, an alternative \R implementation of the Accept--Reject algorithm is

   Nsim=2500
   a=2.7;b=6.3
   M=2.67
   u=runif(Nsim,max=M)    #uniform over (0,M)
   y=runif(Nsim)          #generation from g
   x=y[u<dbeta(y,a,b)]    #accepted subsample

and the left panel in the Figure below shows the results of generating $2500$ pairs $(Y,U)$ from ${\mathcal U}_{[0,1]}\times{\mathcal U}_{[0,M]}$. The black dots $(Y,Ug(Y))$ that fall under the density $f$ are those for which we accept $X=Y$, and we reject the grey dots $(Y,Ug(Y))$ that fall outside. It is again clear from this graphical representation that the black dots are uniformly distributed over the area under the density $f$. Since the probability of acceptance of a given simulation is $1/M$, with $M=2.67$ we accept approximately $1/2.67 = 37\%$ of the values.

enter image description here

Consider instead simulating $Y \sim \mathcal{B}e(2, 6)$ as a proposal distribution. This choice of $g$ is acceptable since

 optimize(f=function(x){dbeta(x,2.7,6.3)/dbeta(x,2,6)},
 max=T,interval=c(0,1))$objective
 [1] 1.671808

This modification of the proposal thus leads to a smaller value of $M$ and a correspondingly higher acceptance rate of $58\%$ than with the uniform proposal. The right panel of the Figure shows the outcome of the corresponding Accept--Reject algorithm and illustrates the gain in efficiency brought by simulating points in a smaller set.


When considering the second part of the question,given that the choice of $p(\cdot)$ is open, among those densities bounding $f(\cdot)$, computing $p(x)$ is not a primary issue when using Accept-Reject algorithms.

Is there a sampling method that allows me to accept or reject these samples according to their value of f(x) without knowing the exact value of p(x) for each sample x?

What matters is the ability to compute the ratio $f(x)/Mp(x)$ for any given $x$. This means that

  1. both densities $f$ and $p$ only need be known up to a normalising constant
  2. $p$ can be chosen towards eliminating the computation of intractable parts of $f$. That is, if $f(\cdot)=f_1(\cdot)f_2(\cdot)$ where $f_2(x)$ cannot be computed, choosing $p(\cdot)=p_1(\cdot)f_2(\cdot)$ eliminates the need to compute $f_2(x)$, providing $p(\cdot)$ can be simulated, i.e., is a generative model.
  3. if $f(x)$ can be written as$$f(x)=\int_\mathfrak Z \tilde f(x,z)\text dz$$ where the integral is intractable and $\tilde f(x,z)$ can be computed, using a proposal density $\tilde p(x,z)$ such that $\tilde f(x,z)/\tilde p(x,z)$ is bounded is sufficient for simulating $f$ even though $f(x)$ cannot be computed.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.