The acceptance-rejection algorithm is described as follows:

  • suppose you have RVs $X$ and $Y$ with densities $f_X$ and $f_Y$, respectively, and there exists a constant $c$ such that $\frac{f_X(t)}{f_Y(t)} \leq c$ for all $t,$ then
    1. generate random $y$ from distribution with density $f_Y$
    2. generate random $u$ from $\text{Uniform}(0, 1)$
    3. if $u < \dfrac{f_X(y)}{cf_Y(y)}$ accept $y$ and deliver $x = y$, otherwise repeat

As the generating process describe, we denote the generated RV $Z$ should have the PDF $f_Z(x)$:

$$f_Z(Z = x) = f_Y(Y = y)f_{U|Y}\left(U < \dfrac{f_X(Y)}{cf_Y(Y)}\Big|Y = y\right) = f_{Y,U}\left(Y = y, U < \dfrac{f_X(Y)}{cf_Y(Y)}\right).$$

But the correct deduction seems:

$$f_Z(Z = x) = f_{Y|U}\left(Y = x\Big|U < \dfrac{f_X(Y)}{cf_Y(Y)}\right) = f_X(X=x).$$

I know how to prove the last equation, however cannot understand why it is the generated RV.


The accepted $X$ can be written as $$X=Y_1\mathbb I_{U_1\le f_X(Y_1)/c f_Y(Y_1)}+Y_2\mathbb I_{U_1> f_X(Y_1)/c f_Y(Y_1)}\mathbb I_{U_2\le f_X(Y_2)/c f_Y(Y_2)}+\cdots$$ It is therefore the transform of the whole sequence $(Y_1,U_1,Y_2,U_2,Y_3,\ldots)$ and not of a single pair $(Y_1,U_1)$. To derive the distribution of such an $X$, one cannot proceed by a change of variable Jacobian formula (as attempted in the first formula) but rather compute the cdf $\mathbb P(X\le x)$ as*: \begin{align}\mathbb P(Y_1\le x,&U_1\le f_X(Y_1)/c f_Y(Y_1))\\ &+\mathbb P(Y_2\le x,U_1>f_X(Y_1)/c f_Y(Y_1),U_2\le f_X(Y_2)/c f_Y(Y_2))+\cdots\\ &=\int_{-\infty}^x \frac{f_X(y)}{c}\,\text{d}y+(1-c^{-1})\int_{-\infty}^x \frac{f_X(y)}{c}\,\text{d}y+\cdots\\ &=\int_{-\infty}^x f_X(y)\,\text{d}y\,c^{-1}\left[1+(1-c^{-1})+(1-c^{-1})^2+\cdots\right]\\ &=\int_{-\infty}^x f_X(y)\,\text{d}y \end{align}

* This is an illustration in dimension one. In larger dimensions consider instead $X\in A$.

  • $\begingroup$ agree with your deduction, however is there any simply understanding to illustrate the fact $P(X\leq x) = P(Y_1\leq x,U_1\le f_X(Y_1)/c f_Y(Y_1))+ P(Y_2\leq x,U_1>f_X(Y_1)/c f_Y(Y_1),U_2\leq f_X(Y_2)/c f_Y(Y_2))+\cdots = P(Y\leq x|U\leq \dfrac{f_X(Y)}{cf_Y(Y)})?$ $\endgroup$ – user6703592 Mar 12 '20 at 19:09
  • $\begingroup$ The events in each parenthesis are mutually exclusive, hence the probability of the union is the sum of the probabilities. $\endgroup$ – Xi'an Mar 13 '20 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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