# Understanding Rejection sampling

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.

• I don't recall any derivatives here; can you provide a link? Feb 9, 2019 at 20:54
• Do you perhaps mean ratio instead of derivative? Feb 11, 2019 at 12:30
• Radon-Nikodym derivative maybe? Feb 11, 2019 at 18:32
• an old answer of mine has the proof. that might help you understand it a little better stats.stackexchange.com/questions/365902/… Feb 11, 2019 at 18:33
• @NaveenGabriel you do it so that the proof works :) Intuitively, you can see that ratio is high when $x$ is in an area of high target density and/or low proposal density. This means proposals are accepted when they're in good spots, but also when you're not likely to generate that number again. Feb 11, 2019 at 19:20

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.
$$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.