Proof of Rejection Sampling - nakaly’s notes

In previous post, I introduced the simple idea of rejection sampling algorithm. But the step 2 (Accept the sample with a probability ( $f(x) \, / Mg(x)$ )) should be elaborated when you actually use it.

Draw a sample from G (which is a known distribution that you already know how to draw samples from)
Draw a sample from uniform distribution (U) and accept it when $U \, \leq \, f(x) \, / Mg(x)$ is true. Otherwise, reject it.
Repeat 1 and 2 util the sample’s probability distribution is close enough to the target.

$F$ : a random variable whose probability density function(pdf) is $f(x)$ , which we want to draw samples.
$P(F)$ : a probability distribution of $F$
$G$ : a random variable whose pdf is $g(x)$
$P(F)$ : a probability distribution of $G$
$M$ : a constant value which meets $M \geq 1$ and $Mg(x) \, \geq \, f(x)$ for all $x$

I’m providing the proof that the sample’s probability distribution is equal to the target probability distribution, which is.

$P(F) \, = \, P(G | G \, is \, accept)$

Let’s start the proof:

$\displaystyle P(G | G \, is \, accept) \, = \, \frac{P(G \, and \, G \, is \, accept)}{P(G \, is \, accept)}$ (Bayes' theorem)
We need $\displaystyle P(G \, and \, G \, is \, accept) \,$ and $\displaystyle P(G \, is \, accept))$ .

1. $\displaystyle P(G \, and \, G \, is \, accept) \,$ can be transformed as follows:
$\displaystyle P(G \, and \, G \, is \, accept) \,$
$\displaystyle \, \, \, \, = \, \int h_{G \, , \, G \, is \, accept}(x) \, dx$ ( $h_{G \, , \, G \, is \, accept}(x)$ is a pdf of joint distribution of $G \, and \, G \, is \, accept$ )
$\displaystyle \, \, \, \, = \, \int i_{G \, is \, accept \, | \, G}(x) \, g(x) \, dx$ (Bayes' theorem for pdf and g(x) is a pdf of G)
$\displaystyle \, \, \, \, = \, \int \frac{f(x)}{M \, g(x)} \, g(x) \, dx$ ( $i_{G \, is \, accept \, | \, G}(x) \,= \, \frac{f(x)}{M \, g(x)}$ because we accept a sample from G with with a probability ( $f(x) \, / Mg(x)$ )
$\displaystyle \, \, \, \, = \, \frac{1}{M} \int f(x) \, dx$
$\displaystyle \, \, \, \, = \, \frac{P(F)}{M}$

2. $\displaystyle P(G \, and \, G \, is \, accept) \,$ can be transformed as follows: (Please refer this for details)
$\displaystyle P(G \, is \, accept)) \, = \, \frac{1}{M}$

As a result of 1 and 2, we can get the following result: $\displaystyle P(G | G \, is \, accept) \, = \, \frac{P(G \, and \, G \, is \, accept)}{P(G \, is \, accept)} \, = \frac{\frac{P(F)}{M} }{\frac{1}{M}} \, = \, P(F)$

Basically I refer to the following article:

monte carlo - How does the proof of Rejection Sampling make sense? - Cross Validated