Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

The way it works is technically for step 2 you draw a uniform random variable on $[0,1]$ and if that random variable ends up being less than the quantity in part 2, you accept the sample. Equivalently, when you draw a proposal $X$, you plug it into part 2 and then throw a biased coin with probability of success equal again to part 2. So if the acceptance ratio is quite low, you're unlikely to accept and if its high, then you are likely to accept

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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