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.

  • 3
    $\begingroup$ I don't recall any derivatives here; can you provide a link? $\endgroup$
    – gunes
    Feb 9, 2019 at 20:54
  • $\begingroup$ Do you perhaps mean ratio instead of derivative? $\endgroup$ Feb 11, 2019 at 12:30
  • $\begingroup$ Radon-Nikodym derivative maybe? $\endgroup$
    – Taylor
    Feb 11, 2019 at 18:32
  • $\begingroup$ an old answer of mine has the proof. that might help you understand it a little better stats.stackexchange.com/questions/365902/… $\endgroup$
    – Taylor
    Feb 11, 2019 at 18:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – Taylor
    Feb 11, 2019 at 19:20

1 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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.