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.
