why we use uniform distribution on accept reject method?

Question

the accept-reject method have the following algorithm:

Given known random number generators $U \sim Unif(0,1)$ and $X \sim g$, we can generate $Y \sim f$ by the following algorithm. Let $c$ be a constant such that $f(x) \leq cg(x)$ for all $x$.

Step 1. Generate $X \sim g$, $U \sim Unif(0,1)$.

Step 2. Accept $Y = X$ if $U \leq \frac{f(X)}{cg(X)}$ otherwise go to Step 1.

I don't understand why we generate $U \sim \mathcal{U}(0,1)$

Can anybody help me? Thanks.

Answer 1

You left out an important condition: $X$ and $U$ are independent. While keeping this in mind, the proof of the algorithm is as follows: $\begin{align*} \mathbb{P}\left(Y \le y\right) &= \mathbb{P}\left(X\le x \middle | U\le \frac{f\left(X\right)}{cg\left(X\right)}\right)\\ &= \frac{\mathbb{P}\left(X \le x, U\le \frac{f\left(X\right)}{cg\left(X\right)}\right)}{\mathbb{P}\left(U\le \frac{f\left(X\right)}{cg\left(X\right)}\right)}\\ &= \frac{\int_{-\infty}^{y}\left[\int_{0}^{f\left(x\right)/cg\left(x\right)} \, du\right] g\left(x\right)\, dx}{\int_{-\infty}^{\infty} \left[\int_{0}^{f\left(x\right)/cg\left(x\right)} \, du\right]g\left(x\right)\, dx} \\ &= \frac{\int_{-\infty}^{y} \frac{f\left(x\right)}{cg\left(x\right)} g\left(x\right) \, dx}{\int_{-\infty}^{\infty} \frac{f\left(x\right)}{cg\left(x\right)} g\left(x\right) \, dx} \\ &=\int_{-\infty}^{y} f\left(x\right) \, dx \end{align*}$

Therefore, if you follow the algorithm and accept the ones that satisfy the condition, the cumulative distribution will be the same as the one you wanted to sample from. And if you differentiating both sides with respect to $y$, you will find that the density function of $Y$ is $f\left(y\right)$ which is basically the same but still we happen to be more comfortable with density functions.

[1] Introduction to Mathematical Statistics, 7th edition, Pearson, Hogg & McKean & Craig, p268

Answer 2

Because $g$ and $f$ are both normalized. Hence $c \ge 1$.

It is easy to show that the acceptance rate is $1/c$.

Let the PDF of $Y$ generated by the above algorithm be $F(Y)$. Then $F(Y)dY$ is the probability of having a $Y$ in $Y$ to $Y+dY$ in the sample of the accepted points. By your algorithm and conditional probability

$$F(Y)dY=P(X\in(Y,Y+dY)|\text{accepted})=\frac{P(X\in(Y+dY))\times P(X\text{ accepted})}{P(\text{accepted})}=\frac{g(Y)dY\times f(Y)/cg(Y)}{1/c}=f(Y)dY$$

So to answer your question, we generate uniform deviate in $(0,1)$ so that according to your algorithm,

$$P(X\text{ accepted})=\frac{f(X)}{cg(X)}$$