# generating process of acceptance-rejection algorithm

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$$.
• 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)})?$ Mar 12 '20 at 19:09