Understanding Rejection sampling

Question

In acceptance rejection sampling, what is the intuition behind using the formula for finding c( a constant that envelops the target density function):

$$c\geq derivative\left(\frac{target\ distribution}{proposed\ distribution}\right)$$

I don't understand why or how this works.

Answer 1

Acceptance/Rejection sampling is an at-first clever but ultimately pedestrian (and often relatively inefficient) algorithm for generating random instances of a random variable $\mathbb{X}$ according to an arbitrary given pdf $f_{\mathbb{X}}$. The idea is to use a known distribution $f_0$ with an efficient random instance generator (e.g., in R: dnorm, dpois, dgamma, etc.) that has the same support as your $\mathbb{X}$. Then, as a trial number $x'$ is created from $f_0$, the algorithm decides whether to use $x'$ for $f_{\mathbb{X}}$ based on a test of a uniform-(0,1) $\rho$ by comparing the ratio $f_{\mathbb{X}}(x')/f_0(x')$ to $\rho$. If the ratio is less than $\rho$ then $x'$ is accepted as an instance of $f_{\mathbb{x}}$. Clearly, the ratio $f_\mathbb{X}/f_0$ has to be in the unit interval $(0,1)$ so $f_{\mathbb{X}}(x') \le f_0(x')$ for all $x'$. To achieve this -- and as engineering trick -- we may multiply $f_0$ by a constant $c$ (likewise we could divide the ratio by $c$) so that the ratio is always $\le 1$). $c$ is chosen to be $max ( f_\mathbb{X}(x')/f_0(x') ) $. This makes the algorithm as efficient as possible (often still not particularly efficient), as it minimizes the rejection events. Ideally the test distribution $f_0$ fits the desired distribution $f_{\mathbb{X}}$ "like a glove," enveloping it with little or no extra area between the curves. Inefficiency is defined as the fraction of $x'$s that are rejected. The value of the inefficiency is the ratio area-between-the-curves/$c$, and efficiency is $1-$ inefficiency.

You write that

$c \ge$ derivative(target distribution/proposed distribution)

which almost makes sense. How about this? The ratio $f/f_0$ evaluated at at $x=x^*$ is an extremum (probably maximum) then $(f/f_0)'|_{x^*} =0$. So it seems you are asked to show that $$ \frac{d}{dx} \frac{f_{\mathbb{X}}(x)}{f_0(x)} \biggr \lvert_{x^*} =0 $$ implies $$ \frac{f'_{\mathbb{X}}(x^*)}{f'_0(x^*)} =\frac{f_{\mathbb{X}}(x^*)}{f_0(x^*)} \le c $$ which follows from the quotient rule and the definition of $c$ above.

Now you are on the hook to show that the extremum is a maximum . . . You can do it!