1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I don't recall any derivatives here; can you provide a link? $\endgroup$ – gunes Feb 9 at 20:54
  • $\begingroup$ Do you perhaps mean ratio instead of derivative? $\endgroup$ – Christoph Hanck Feb 11 at 12:30
  • $\begingroup$ Radon-Nikodym derivative maybe? $\endgroup$ – Taylor Feb 11 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 at 18:33
  • $\begingroup$ @Taylor Can you tell why do you take the ratio of f(x)/g(x)c? $\endgroup$ – Naveen Gabriel Feb 11 at 19:17
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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