2
$\begingroup$

I recently studied Rejection Sampling as part of one of my University courses. When justifying why Rejection Sampling makes sense (to "prove", so to speak, that samples drawn using Rejection Sampling actually follow the target PDF, my Professor wrote the following argument. \begin{equation} \text{prob}(x \text{ ACCEPTED}) = \int_{0}^{c} \text{prob}((x, y) \text{ SAMPLED}) . \text{prob}(y < f(x)) \, dy \end{equation}

\begin{equation} \text{prob}((x, y) \text{ SAMPLED}) = \text{prob}(x \text{ SAMPLED}) \cdot \text{prob}(y \text{ SAMPLED}) = \frac{1}{c \cdot (b-a)} \end{equation} where $f(x)$ is the target PDF from which we want to sample, $\text{Support of } X = \{ x \mid a < x < b \}$ and $c$ is the height of the uniform bounding box we are using for Rejection Sampling. I cannot quite come to terms with how this can be a valid reasoning. Isn't the probability of a single tuple $(x,y)$ being sampled in a continuous domain equal to 0? What am I missing? Further, if I am correct, what is the correct approach to prove the validity of Rejection Sampling?
P.S. This Youtube lecture also uses a reasoning along the same lines and it has got me confused about my very foundations in the probability theory for continuous random variables.

$\endgroup$
1
  • 2
    $\begingroup$ The fact that you're integrating over $(0,c)$ and using the cumulative density $p(y < f(x))$ means you're dealing with probabilities, not densities, in the first expression. For the second, I wouldn't take the use of the word "prob" too literally, instead treating it as we do the use of the letter "p" in expressions like $p(x;\theta)$. $\endgroup$
    – jbowman
    Commented Nov 19, 2023 at 15:53

1 Answer 1

6
$\begingroup$

To quote from our book Monte Carlo Statistical Methods, the most straightforward way of validating Accept-Reject sampling is to see it as simulating uniformly on a set $B$ until the simulation belongs to another set $A$. If $A\subset B$, the outcome is uniformly distributed on $A$. The details proceed as follows:

There exists a fundamental (simple!) idea that underlies the Accept-Reject methodology, and also plays a key role in the construction of the slice sampler. If $f$ is the density of interest, on an arbitrary space, we can write \begin{equation}%\label{eq:fund} %\int_{-\infty}^x f(x^\prime) dx^\prime = \int_{-\infty}^x \int_{0}^{f(x^\prime)} du \; dx^\prime, f(x) = \int_{0}^{f(x)} du \,.\tag{1} \end{equation} Thus, $f$ appears as the marginal density (in $X$) of the joint distribution, \begin{equation}%\label{eq:fund2} (X,U) \sim {\cal U} \{(x,u):0<u<f(x)\}\,.\tag{2} \end{equation} Since $U$ is not directly related to the original problem, it is called an auxiliary variable.

Although it seems like we have not gained much, the introduction of the auxiliary uniform variable in (1) has brought a considerably different perspective: Since (2) is the joint density of $X$ and $U$, we can generate from this joint distribution by just generating uniform random variables on the constrained set $\{(x,u):0<u<f(x)\}$. Moreover, since the marginal distribution of $X$ is the original target distribution, $f$, by generating a uniform variable on $\{(x,u):0<u<f(x)\}$, we have generated a random variable from $f$. And this generation was produced without using $f$ other than through the calculation of $f(x)$! The importance of this equivalence is stressed in the following property:

Simulating $$\mathbf{ X \sim f(x)}$$ is equivalent to simulating $$\mathbf{ (X,U) \sim {\cal U} \{(x,u):0<u<f(x)\} \,.}$$

For example, in a one-dimensional setting, suppose that $$ \int_a^b f(x) dx = 1 $$ and that $f$ is bounded by $m$. We can then simulate the random pair $(Y,U) \sim {\cal U}(0<u<m)$ by simulating $Y \sim {\cal U}(a,b)$ and $U|Y=y \sim {\cal U}(0,m)$, and take the pair only if the further constraint $0<u<f(y)$ is satisfied. This results in the correct distribution of the accepted value of $Y$, call it $X$, because \begin{eqnarray}%\label{eq:fun1} P(X \le x)&=&P(Y \le x |U<f(Y)) \nonumber\\ &=& \frac{\int_a^x \int_0^{f(y)}du \; dy}{\int_a^b \int_0^{f(y)}du \; dy} = \int_a^x f(y)\; dy. \end{eqnarray} This amounts to saying that, if $A \subset B$ and if we generate a uniform sample on $B$, keeping only the terms of this sample that are in $A$ will result in a uniform sample on $A$ (with a random size that is independent of the values of the sample).

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