2
$\begingroup$

I have the following passage from a set of lecture notes I am working on that I would like to understand a little better.

$\underline{\text{Algorithm for Rejection Sampling}}$:

Given two densities $f$, $g$, with $f(x) < M.g(x)$ for all $x$, and some constant $M$, we can generate a sample from $f$ by

  1. Draw $X \sim g$

  2. Accept $X$ as a sample from $f$ with probability

    $\large \frac{f(X)}{M.g(X)}$

    otherwise go back to step 1.

Now, I understand why this will generate samples from the distribution with density $f$, but I really do not understand how to use this algorithm in practice.

I draw an $X$ from the distribution with density $g$, and then I need to decide whether to keep it, or reject it. I don't understand the condition to accept it... do I accept it if the probability defined in 2. is greater than e.g. 0.5, or maybe 0.7? Is this probability up to me to decide?

Thanks for your insight and thoughts.

$\endgroup$
  • 2
    $\begingroup$ At step 2, you generate a random number in [0, 1], if the random number is <= f(X)/Mg(X) then accept else reject. $\endgroup$ – TenaliRaman Apr 19 '13 at 20:07
  • 2
    $\begingroup$ FWIW, just yesterday I posted a simple working example of this (in R) at stats.stackexchange.com/questions/56459/…. $\endgroup$ – whuber Apr 19 '13 at 20:16
2
$\begingroup$

draw an X from the distribution with density g, and then I need to decide whether to keep it, or reject it.

do I accept it if the probability defined in 2. is greater than e.g. 0.5, or maybe 0.7?

No. That would not accept it with the given probability.

Is this probability up to me to decide?

No, the probability with which you accept it is specified in the formula you gave! You don't compare it with a fixed value at all.

To get the right density, you need to accept a fraction, $\large \frac{f(X)}{M.g(X)}$ of the points, at random.

That is, you need to generate additional random numbers to tell you which of these random-numbers from $g$ to accept, in order that you end up with random numbers from $f$.

So in that step, after you have generated $x$ from $g_X(x)$ you generate a uniform random number on $[0,1]$ (or $(0,1)$ or - more usually on computers, $[0,1)$) and if it's less than $\large \frac{f(x)}{M.g(x)}$, you accept it. That means you accept the point with the stated probability.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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