Rejection sampling confusion 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:

*

*Sample point on x-axis from proposal distribution p(x).

*Draw vertical line at this x-position, up to the maximum y-value of the proposal distribution, p(x).

*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:

*

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

*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?
 A: 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.



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

*

*both densities $f$ and $p$ only need be known up to a normalising constant

*$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.

*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.

